Минимизация стоимостей перевозок

Минимизация стоимостей перевозок

Московский Государственный Колледж

Информационных Технологий

Курсовой проект

по предмету

« Языки программирования и разработка

программного обеспечения »

на тему :

« Минимизация стоимостей перевозок »

Работу выполнил

Работу проверили

студент группы П-407

Преподаватели

Чубаков А.С.

Капустина Р.Н.

Токарев С.Б.

1998 г.

КР. 2203 81 - 21

ВВЕДЕНИЕ

Развитие современного общества характеризуется повышением технического

уровня , усложнением организационной структуры производства , углублением

общественного разделения труда , предъявлением высоких требований к

методам планирования и хозяйственного руководства. В этих условиях только

научный подход к руководству к экономической жизни общества позволит

обеспечить высокие темпы развития народного хозяйства. В настоящие время

новейшие достижения математики и современной вычислительной техники находят

все более широкие применение в экономических исследованиях и планированияx.

Этому способствует развитие таких разделов математики . как математическое

программирование , теория игр , теория массового обслуживания , а так же

бурное развитие быстродействующей электронно - вычислительной техники.

Одной из основных ставится задача создания единой системы оптимального

планирования и управление народным хозяйством на базе широкого применения

математических методов в электронно - вычислительной техники в экономике.

Решение экстремальных экономических задач можно разбить на три этапа :

1. Построение экономико - математической задачи.

2. Нахождение оптимального решения одним из математических методов.

3. Промышленное внедрение в народное хозяйство.

Построение экономическо - математической модели состоит в создании

упрощенной математической модели , в которой в схематичной форме отражена

структура изучаемого процесса. При этом особое внимание должно быть уделено

отражении в модели всех существенных особенностей задачи и учет всех

ограничивающих

условий , которые могут повлиять на результат. Затем определяется цель

решения , выбирается критерий оптимальности и дают математическую

формулировку задачи.

Составными частями математического программирования являются линейное ,

нелинейное и динамическое программирование. При исследовании в большинстве

случаев имеют место задачи нелинейного программирования , аппроксимация их

линейными задачами вызвана только тем , что последние хорошо изучены.

Динамическое программирование как самостоятельная дисциплина

сформулировалась в пятидесятых годах нашего века. Большой вклад в ее

развитие внес американский математик Р. Бельман. Дальнейшие развитие

динамическое программирование получило

в трудах зарубежных ученых Робертса , Ланга и др.

В настоящие время оно в основном развивается в планировании приложений к

различным родам многоэтапным процессам.

КР. 2203 81 – 21

2. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Производственное предприятие имеет в своем составе три филиала которые

производят однородную продукцию

соответственно в количествах , равных 50 , 30 и 10 единиц. Эту продукцию

получают четыре потребителя , расположенных в разных

местах. Их потребности соответственны равны 30 , 30 , 10 и 20 единиц.

Тарифы перевозов единицы продукции от каждого филиалов соответствующим

потребителям задаются матрицей :

1 2 4 1

Сij = 2 3 1 5

3 2 4 4

Составить такой план прикрепления получателе продукции к ее поставщикам ,

при котором общая стоимость перевозок будет минимальной.

КП. 2203 81 - 21

2.МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

2. Математическая модель задачи

Имеется:

m (i=1,2,…,m) – филиалы.

Ai – количество единиц продукции «i» филиала.

n (j=1,2,…,n) – потребители

Bj – потребности «j» потребителя

Cij – стоимость перевозки 1 условной единицы продукции

от «i» филиала к «j» потребителю

Ограничения:

1. Балансовое ограничение.

Предполагается, что сумма всех запасов (ai) равна сумме всех заявок (bj):

[pic]

2. Ресурсное ограничение.

[pic]

[pic]

Суммарное количество груза, направленного из каждого пункта отправления во

все пункты назначения должно быть равно запасу груза в данном пункте. Это

даст m – условий равенств:

или

[pic]

3. Плановое ограничение.

[pic]

Суммарное количество груза, доставляемого в каждый пункт назначения изо

всех пунктов отправления должно быть равно заявке (bj) поданной данным

пунктом. Это даст нам n – условий равенств:

[pic]

КП. 2203 81 - 21

или

[pic]

4. Реальность плана перевозок.

Перевозки не могут быть отрицательными числами:

[pic]

5. Требуется составить такой план перевозок, при котором все заявки

были бы выполнены и при этом общая стоимость всех перевозок была бы

минимальна, поэтому целевая функция или критерий эффективности:

[pic]

[pic]

[pic]

КП. 2203 81 – 21

3.ВЫБОР МЕТОДА РЕАЛИЗАЦИИ ПРОДУКЦИИ.

ОБОСНОВАНИЕ ВЫБОРА МЕТОДА.

Симплекс - метод является универсальным и применяется для решения любых

задач.

Однако существуют некоторые частные типы задач линейного программирования ,

которые в силу некоторых особенностей своей структуры допускают решение

более

простыми методами. К ним относится транспортная задача.

Распределительный метод решения транспортной задачи обладает одним

недостатком :

нужно отыскивать циклы для всех свободных клеток и находить их цены. От

этой

трудоемкой работы нас избавляет специальный метод решения транспортной

задачи , который называется методом потенциалов. Он позволяет автоматически

выделять циклы с отрицательной ценой и определять их цены.

В отличии от общего случая ОЗЛП с произвольными ограничениями и

минимизированной функцией , решение транспортной задачи всегда существует.

Общий принцип определения оптимального плана транспортной задачи методом

потенциалов аналогичен принципу решения задачи линейного программирования

симплекс - метода ,. а именно : сначала находят опорный план транспортной

задачи , а затем его улучшают до получения оптимального плана. Далее будет

рассматриваться сам метод потенциалов.

Решение транспортной задачи , как и любой другой задачи линейного

программирования начинается с нахождения опорного решения , или , как мы

говорим опорного плана. Для его нахождения созданы специальные методы ,

самым распространенным из них считается метод северо - западного угла.

Определение значений xi,j начинается с левой верхней клетки таблицы.

Находим значения x1,1 из соотношения x11 = min(a1,b1(.

Если ai < b1 то x11=a1 , строка i=1 исключается из дальнейшего рассмотрения

, а потребность первого потребителя b1 уменьшается на величину a1.

Если a1>b1 , то x11=b1 , столбец j=1 исключается из дальнейшего

рассмотрения , а наличие груза у первого поставщика a1 уменьшается на

величину b1.

Если a1=b1 , то x11=a1=b1 , строка i=1 и столбец j=1 исключаются из

дальнейшего рассмотрения.

Данный вариант приводит к вырождению исходного плана.

Затем аналогичные операции проделывают с оставшийся частью таблицы ,

начиная с его северо - западного угла. После завершения оптимального

процесса необходимо провести проверку полученного плана на вырожденность.

Если количество заполненных клеток равно m + n -1 , то план является

невырожденным. Если план вырожденный , т.е количество заполненных клеток

стало меньше m + n -1 , то незаполненные клетки с минимальными стоимостями

перевозок заполняются нулями , чтобы общие количество заполненных клеток

стало равным

m + n -1.

Транспортная задача с неправильным балансом называется открытой моделью .

Чтобы ее решить , необходимое сбалансировать. Достигается это следующим

образом:

Когда еai >еbj это транспортная задача с избытком запасов.

еxijеai , то такая задача называется – транспортная задача с избытком

запаса. Эту задачу можно свести к обычной задаче с правильным балансом ,

если ввести фиктивный пункт отправления Aф , приписав ему фиктивный запас

aф =еbj - еai . Добавляем фиктивную строку , где Cфi= 0 ( j=1,n).

Стоимости будут равны нулю . это значит , что часть заявок cфj останутся

неудовлетворенными. Среди них могут оказаться те потребности , которые

необходимо обязательно удовлетворить. Для этого вводим коэффициент:

R=еai : еbj и каждый запас bj умножаем на этот коэффициент. Таким образом

задача сведена к транспортной задаче с правильным балансом.

Построенный выше исходный план можно довести до оптимального с помощью

метода потенциалов.

Каждому поставщику Ai поставим в соответствии некоторые числа ai ,

называемые потенциалом , а каждому потребителю Bj – число bj.

Для каждой независимой клетки , т.е для каждой независимой переменной

рассчитываются так называемые косвенные тарифы ( Cўij) по формуле

Cўij= ai + bj. А для заполненных клеток , т.е базисных переменных Cўij

=Cij.

Проверяем полученный план на оптимальность. Если для каждой независимой

клетки выполняется условие Cўij - Cij Cij , то следует

приступить к улучшению плана.

Для правильного перемещения перевозок , чтобы не нарушить ограничений ,

строится цикл , т.е замкнутый путь , соединяющий выбранную свободную клетку

с той же самой , и проходящий через заполненные клетки. Цикл строится

следующим образом.

Вычеркиваются все строки и столбцы , содержащие ровно одну заполненную

клетку (выбранная при этом клетка считается заполненной). Все остальные

заполненные клетки составляют и лежат в его углах. Направление построения

цикла ( по часовой стрелке или против ) несущественно.

В каждой клетки цикла , начиная со свободной , проставляются поочередно

знаки

І + І и І - І . В клетках со знаком І - І выбирается минимальная

величина. Новый базисный план начинается путем сложений выбранной величины

с величинами , стоящих в клетках цикла со знаком І + І и вычитанием этой

величины из величины , стоящей в клетке со знаком І - І . Выбранная

минимальная величина будет соответствовать перемененной выводимой из

базиса.

КП. 2203 81 - 21

Значения переменных включенных в цикл , после описанной корректировки ,

переносятся в новую таблицу.

Все остальные переменные записываются в новую таблицу без изменения.

Осуществляется переход к шагу один. Дальше подсчитывается значение целевой

функции

F = ее Cij· cij min.

Метод потенциалов обеспечивает монотонное убывание значений целевой функции

и позволяет за конечное число шагов найти его минимум.

КР. 2203 81 - 21

5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

Слово « компьютер »означает « вычислитель » , т.е устройство для

вычислений.

Это связано с тем , что первые компьютеры создавались как устройства для

вычислений , грубо говоря , усовершенствованные , арифметические

арифмометры. Принципиальное отличие компьютеров от арифмометров и других

счетных устройств состояло в том , что арифмометры могли выполнять лишь

отдельные вычислительные операции(сложение , вычитание , умножение ,

деление и др.) , а компьютеры позволяли проводить без участия человека

сложные последовательные вычислительные операции по заранее заданной

инструкции - программе. Кроме того , для хранения данных , промежуточных и

итоговых результатов вычислений компьютеры содержат память.

Компьютер - это универсальный прибор для переработки информации. Но сам по

себе компьютер является просто ящиком с набором электронных схем. Он не

обладает знаниями ни в одной области своего применения. Все эти знания

сосредоточены в выполняемых на компьютере программах. Для того , чтобы

компьютер мог осуществить определенные действия , необходимо составить для

компьютера программу , т.е точную и пол=дробную последовательность

инструкций на понятном компьютере языке , как надо правильно обрабатывать

информацию. Меняя программы для компьютера , можно привести его в рабочие

место бухгалтера ил конструктора , статистика или агронома , редактировать

документ или играть в игры. Поэтому для эффективного использования

компьютера необходимо знать назначение и свойства необходимые при работе с

ним программ.

Программы . работающие на компьютеры можно разделить на три категории :

n Прикладные программы , непосредственно обеспечивающие выполнение

необходимых пользователям работ : редактирование текстов , рисование

картинок , обработку информационных массивов и т.д.

n Системные программы , выполняющие различные вспомогательные функции ,

например создание копий используемой информации , проверку

работоспособности устройств компьютера и т.д. Огромную роль среди всех

системных программ играет операционная система - программа ,

управляющая компьютером , запускающая все другие программы и

выполняющая для них различные сервисные функции.

n Инструментальные системы (системы программирования ) , обеспечивающие

создание новых программ для компьютера.

КР. 2203 81 - 21

6.ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА

В 1992 году фирма Borland International выпустила два пакета

программирования , основанные на использовании языка Паскаль - Borland

Pascal 7.0 и Turbo Pascal 7.0. Система программирования Turbo Pascal ,

разработанная американской корпорацией Borland

остается одной из самых популярных систем программирования в мире. Этому

способствует , с одной стороны , простота лежащего в ее основе языка

программирования Паскаль , а с другой - труд и талант сотрудников Borland

во главе с идеологом и создателем Turbo Pascal Андерсом Хейлсбергом ,

приложившим немало усилий к ее совершенствованию. Придуманный швейцарским

ученым Никласом Виртом как средство для обучения студентов программированию

, язык Паскаль стараниями А. Хейлсберга превратилась в мощною современною

профессиональную систему программирования , которой по плечу любые задачи -

от создания простых программ , предназначенных для решения несложных

вычислительных задач , до разработки сложнейших реляционных систем

управления базами данных. Появление Windows и инструментальных средств

Borland Pascal with Object и Delphi для разработки программ в среде Windows

лишний раз показало , какие поистине не исчерпывающие возможности таит он в

себе : и Borland Pascal , и используемый в Delphi язык Object Pascal

основываются на Турбо Паскале и развивают его идеи.

Пакет Turbo Pascal включает в себя как язык программирования - одно из

расширений языка Паскаль для ЭВМ типа IBM , так и среду , предназначенную

для написания , отладки и запуска программ.

Язык характеризуется расширенными возможностями по сравнению со стандартом

, хорошо развитой библиотекой модулей , позволяющей использовать

возможности операционной системы , создавать оверлейные структуры ,

организовывать ввод - вывод , формировать графические изображения и т.д.

среда программирования позволяет создавать тексты программ . компилировать

их , находить и справлять ошибки , компоновать программы из отдельных

частей . включая стандартные модули , отлаживать и выполнять отлаженную

программу. Пакет представляет пользователю большой объем справочной

информации , позволяет применять объектное - ориентированное

программирование , обладает встроенным ассемблером , имеет инструментальное

средство для создания интерактивных программ - Turbo Vision и т.д.

КР. 2203 81 - 21

7.РЕШЕНИЕ ЗАДАЧИ ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРРАММЫ.

| | | | | | | |

| |B1 |B2 |B3 |B4 |ai |ai |

| |1 |2 |0 |4 | | |

|A1 |1 |2 |4 |1 |50 |0 |

| | | | | | | |

| |30 |20 | | | | |

|A2 |2 |3 |1 |5 | | |

| |2 |3 |1 |5 |30 |1 |

| | | | | | | |

| | |10 |10 |10 | | |

|A3 |1 |2 |0 |4 | | |

| |3 |2 |4 |4 |10 |0 |

| | | | | | | |

| | | | |10 | | |

|заявки | | | | | | |

|bj |30 |30 |10 |20 |90 | |

| Bj | | | | | | |

| |1 |2 |0 |4 | | |

1,2 1,4

10

2,2 2,4

| |B1 |B2 |B3 |B4 |ai |ai |

| |1 |2 |0 |1 | | |

|A1 |1 |2 |4 |1 |50 |0 |

| | | | | | | |

| |30 |10 | |10 | | |

| |2 |3 |1 |2 | | |

|A2 |2 |3 |1 |5 |30 |1 |

| | | | | | | |

| | |20 |10 | | | |

| |4 |5 |3 |4 | | |

|A3 |3 |2 |4 |4 |10 |3 |

| | | | | | | |

| | | | |10 | | |

|bj | | | | | | |

| |30 |30 |10 |20 |90 | |

| | | | | | | |

|Bj |1 |2 |0 |1 | | |

1,1 1,4

10

3,1 3,4

КР. 2203 81 - 21

| | | | | | | |

| |B1 |B2 |B3 |B4 |ai |ai |

| |1 |2 |0 |1 | | |

|A1 |1 |2 |4 |1 |50 |0 |

| | | | | | | |

| |20 |10 | |20 | | |

| |2 |3 |1 |2 | | |

|A2 |2 |3 |1 |5 |30 |1 |

| | | | | | | |

| | |20 |10 | | | |

| |3 |4 |2 |3 | | |

|A3 |3 |2 |4 |4 |10 |2 |

| | | | | | | |

| |10 | | | | | |

| | | | | | | |

|bj |30 |30 |10 |20 |90 | |

| | | | | | | |

|Bj |1 |2 |0 |1 | | |

1,1 1,2

10

3,1 3,2

| | | | | | | |

| |B1 |B2 |B3 |B4 |ai |ai |

| |1 |-1 |-3 |1 | | |

|A1 |1 |2 |4 |1 |50 |0 |

| |30 | | |20 | | |

| |5 |3 |1 |5 | | |

|A2 |2 |3 |1 |5 |30 |4 |

| | |20 |10 | | | |

| |4 |2 |0 |4 | | |

|A3 |3 |2 |4 |4 |10+E |3 |

| | |10 | |E | | |

| | | | | | | |

|bj |30 |30 |10 |20+E |90+E | |

| | | | | | | |

|Bj |1 |-1 |-3 |1 | | |

1,1 1,2

10

2,1 2,2

КР. 2203 81 - 21

| | | | | | | |

| |B1 |B2 |B3 |B4 |ai |ai |

| |1 |2 |0 |1 | | |

|A1 |1 |2 |4 |1 |50 |0 |

| |10 |20 | |20 | | |

| |2 |3 |1 |2 | | |

|A2 |2 |3 |1 |5 |30 |1 |

| |20 | |10 | | | |

| |1 |2 |0 |1 | | |

|A3 |3 |2 |4 |4 |10 |0 |

| | |10 | | | | |

| | | | | | | |

|bj |30 |30 |10 |20 |90 | |

| | | | | | | |

|Bj |1 |2 |0 |1 | | |

Fmin=1·10 +2·20 +2·10 +1·10 +2·20 +20*1 = 140

Найден оптимальный план перевозок , равный 140.

КР. 2203 81 – 21

8.АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

В процессе решения транспортной задачи методом потенциалов было получено

решение , которое является оптимальным , потому , что для каждой

независимой клетки выполняется критерий оптимальности плана транспортной

задачи :

Cўij –Cij <=0

Так же суммарная стоимость перевозок груза с каждой последующей итерацией

уменьшалась и оказалась равной 140 рублям.

Еще одним немаловажным фактором является то , что потребность получателя в

грузе полностью удовлетворена , а поставщик реализовал весь свой груз.

Результат подсчитанный ручным счетом сходится с ответом , полученным на ЭВМ

с помощью составленной программы. Расхождений нет.

Вектор полученных результатов:

10 20 0 20

c= 20 0 10 0

0 10 0 0

КП. 2203 81 - 21

ЗАКЛЮЧЕНИЕ

Основной задачей данного курсового проекта являеся нахождение оптимального

плана перевозок груза от поставщиков к потребителям . нахождение

минимальной функции.

Эта задача сводится к транспортной задаче.

В процессе разработки курсового проекта былы составлена универсальная

программа для решения аналогичных задач. Правильность работы задачи

определяется с помощью задачи - теста . Для проверки правильности работы

работы программы были заданны : количество поставщиков и потребителей ,

наличие груза , заявки и тарифы перевозок. Результаты были подсчитаны

вручную , а их решение совпадает с результатом машинного счета. Полученный

верный результат позволяет применять данную программу к производственным и

транспорным задачам.[pic]

-----------------------

(1)

(2)

(3)

(4)

(5)