Минимизация стоимостей перевозок
Московский Государственный Колледж
Информационных Технологий
Курсовой проект
по предмету
« Языки программирования и разработка
программного обеспечения »
на тему :
« Минимизация стоимостей перевозок »
Работу выполнил Работу проверили
студент группы П-407 Преподаватели
Чубаков А.С. Капустина Р.Н.
Токарев С.Б.
1998 г.
КР. 2203 81 - 21
ВВЕДЕНИЕ
Развитие современного общества характеризуется повышением технического
уровня , усложнением организационной структуры производства , углублением общественного разделения труда , предъявлением высоких требований к методам планирования и хозяйственного руководства. В этих условиях только научный подход к руководству к экономической жизни общества позволит обеспечить высокие темпы развития народного хозяйства. В настоящие время новейшие достижения математики и современной вычислительной техники находят все более широкие применение в экономических исследованиях и планированияx. Этому способствует развитие таких разделов математики . как математическое программирование , теория игр , теория массового обслуживания , а так же бурное развитие быстродействующей электронно - вычислительной техники. Одной из основных ставится задача создания единой системы оптимального планирования и управление народным хозяйством на базе широкого применения математических методов в электронно - вычислительной техники в экономике.
Решение экстремальных экономических задач можно разбить на три этапа :
Построение экономико - математической задачи.
Нахождение оптимального решения одним из математических методов.
Промышленное внедрение в народное хозяйство.
Построение экономическо - математической модели состоит в создании упрощенной математической модели , в которой в схематичной форме отражена структура изучаемого процесса. При этом особое внимание должно быть уделено отражении в модели всех существенных особенностей задачи и учет всех ограничивающих
условий , которые могут повлиять на результат. Затем определяется цель решения , выбирается критерий оптимальности и дают математическую формулировку задачи.
Составными частями математического программирования являются линейное , нелинейное и динамическое программирование. При исследовании в большинстве случаев имеют место задачи нелинейного программирования , аппроксимация их линейными задачами вызвана только тем , что последние хорошо изучены.
Динамическое программирование как самостоятельная дисциплина сформулировалась в пятидесятых годах нашего века. Большой вклад в ее развитие внес американский математик Р. Бельман. Дальнейшие развитие динамическое программирование получило
в трудах зарубежных ученых Робертса , Ланга и др.
В настоящие время оно в основном развивается в планировании приложений к различным родам многоэтапным процессам.
КР. 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» потребителю
Ограничения:
Балансовое ограничение.
Предполагается,
что сумма всех запасов (ai) равна сумме
всех заявок (bj):
2. Ресурсное ограничение.
Суммарное количество груза, направленного из каждого пункта отправления во все пункты назначения должно быть равно запасу груза в данном пункте. Это даст m – условий равенств:
или
3. Плановое ограничение.
Суммарное
количество груза, доставляемого в каждый
пункт назначения изо всех пунктов
отправления должно быть равно заявке
(bj) поданной данным пунктом. Это даст
нам n – условий равенств:
КП. 2203 81 - 21
или
4. Реальность плана перевозок.
Перевозки не могут быть отрицательными числами:
5. Требуется составить такой план перевозок, при котором все заявки были бы выполнены и при этом общая стоимость всех перевозок была бы минимальна, поэтому целевая функция или критерий эффективности:
КП. 2203 81 – 21
3.ВЫБОР МЕТОДА РЕАЛИЗАЦИИ ПРОДУКЦИИ.
ОБОСНОВАНИЕ ВЫБОРА МЕТОДА.
Симплекс - метод является универсальным и применяется для решения любых задач.
Однако существуют некоторые частные типы задач линейного программирования ,
которые в силу некоторых особенностей своей структуры допускают решение более
простыми методами. К ним относится транспортная задача.
Распределительный метод решения транспортной задачи обладает одним
недостатком :
нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой
трудоемкой работы нас избавляет специальный метод решения транспортной
задачи , который называется методом потенциалов. Он позволяет автоматически
выделять циклы с отрицательной ценой и определять их цены.
В отличии от общего случая ОЗЛП с произвольными ограничениями и
минимизированной функцией , решение транспортной задачи всегда существует.
Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплекс - метода ,. а именно : сначала находят опорный план транспортной задачи , а затем его улучшают до получения оптимального плана. Далее будет рассматриваться сам метод потенциалов.
Решение транспортной задачи , как и любой другой задачи линейного программирования начинается с нахождения опорного решения , или , как мы говорим опорного плана. Для его нахождения созданы специальные методы , самым распространенным из них считается метод северо - западного угла.
Определение значений x>i,j >начинается с левой верхней клетки таблицы. Находим значения x>1,1 >из соотношения x>11> = min{a>1>,b>1>}.
Если a>i> < b>1 >то x>11>=a>1> , строка i=1 исключается из дальнейшего рассмотрения , а потребность первого потребителя b>1> уменьшается на величину a>1>.
Если a>1>>b>1> , то x>11>=b>1> , столбец j=1 исключается из дальнейшего рассмотрения , а наличие груза у первого поставщика a>1> уменьшается на величину b>1>.
Если a>1>=b>1> , то x>11>=a>1>=b>1> , строка i=1 и столбец j=1 исключаются из дальнейшего рассмотрения.
Данный вариант приводит к вырождению исходного плана.
Затем аналогичные операции проделывают с оставшийся частью таблицы , начиная с его северо - западного угла. После завершения оптимального процесса необходимо провести проверку полученного плана на вырожденность.
Если количество заполненных клеток равно m + n -1 , то план является невырожденным. Если план вырожденный , т.е количество заполненных клеток стало меньше m + n -1 , то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями , чтобы общие количество заполненных клеток стало равным
m + n -1.
Транспортная задача с неправильным балансом называется открытой моделью .
Чтобы ее решить , необходимое сбалансировать. Достигается это следующим образом:
Когда åa>i >>åb>j >это транспортная задача с избытком запасов.
åx>ij><= a>i>> >(i=1,m)
КП. 2203 81 – 21
åx>ij>=b>j >(j=1,n)
Здесь вводим фиктивного потребителя B>ф> и приписываем ему заявку b>ф>=åa>i> - åb>j >. Вводим фиктивный сотолбец , т.е C>iф>=0 (i =1,m). Все стоимости будут равны нулю , это значит , что грузы c>iф> останутся невостребованными , т.е введением фиктивного потребителя , мы свели транспортную задачу с неправильным балансом к задаче с правильным балансом.
Если сумма подданных заявок превышает наличные запасы
åb>j> >åa>i> , то такая задача называется – транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом , если ввести фиктивный пункт отправления A>ф> , приписав ему фиктивный запас a>ф> =åb>j> - åa>i> . Добавляем фиктивную строку , где C>фi>= 0 ( j=1,n).
Стоимости будут равны нулю . это значит , что часть заявок c>фj> останутся неудовлетворенными. Среди них могут оказаться те потребности , которые необходимо обязательно удовлетворить. Для этого вводим коэффициент:
R=åa>i> : åb>j> и каждый запас b>j> умножаем на этот коэффициент. Таким образом задача сведена к транспортной задаче с правильным балансом.
Построенный выше исходный план можно довести до оптимального с помощью метода потенциалов.
Каждому поставщику A>i> поставим в соответствии некоторые числа a>i> , называемые потенциалом , а каждому потребителю B>j> – число b>j>.
Для каждой независимой клетки , т.е для каждой независимой переменной рассчитываются так называемые косвенные тарифы ( C¢>ij>) по формуле
C¢>ij>= a>i>> >+ b>j>. А для заполненных клеток , т.е базисных переменных C¢>ij>> >=C>ij>.
Проверяем полученный план на оптимальность. Если для каждой независимой клетки выполняется условие C¢>ij> - C>ij ><=0 , то такой план является оптимальным. Если хотя бы в одной свободной клетке C¢>ij> > C>ij> , то следует приступить к улучшению плана.
Для правильного перемещения перевозок , чтобы не нарушить ограничений , строится цикл , т.е замкнутый путь , соединяющий выбранную свободную клетку с той же самой , и проходящий через заполненные клетки. Цикл строится следующим образом.
Вычеркиваются все строки и столбцы , содержащие ровно одну заполненную клетку (выбранная при этом клетка считается заполненной). Все остальные заполненные клетки составляют и лежат в его углах. Направление построения цикла ( по часовой стрелке или против ) несущественно.
В каждой клетки цикла , начиная со свободной , проставляются поочередно знаки
² + ² и ² - ² . В клетках со знаком ² - ² выбирается минимальная величина. Новый базисный план начинается путем сложений выбранной величины с величинами , стоящих в клетках цикла со знаком ² + ² и вычитанием этой величины из величины , стоящей в клетке со знаком ² - ² . Выбранная минимальная величина будет соответствовать перемененной выводимой из базиса.
КП. 2203 81 - 21
Значения переменных включенных в цикл , после описанной корректировки , переносятся в новую таблицу.
Все остальные переменные записываются в новую таблицу без изменения. Осуществляется переход к шагу один. Дальше подсчитывается значение целевой функции
F
=
åå
C>ij>·
c>ij>
min.
Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти его минимум.
КР. 2203 81 - 21
5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.
Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений.
Это связано с тем , что первые компьютеры создавались как устройства для вычислений , грубо говоря , усовершенствованные , арифметические арифмометры. Принципиальное отличие компьютеров от арифмометров и других счетных устройств состояло в том , что арифмометры могли выполнять лишь отдельные вычислительные операции(сложение , вычитание , умножение , деление и др.) , а компьютеры позволяли проводить без участия человека сложные последовательные вычислительные операции по заранее заданной инструкции - программе. Кроме того , для хранения данных , промежуточных и итоговых результатов вычислений компьютеры содержат память.
Компьютер - это универсальный прибор для переработки информации. Но сам по себе компьютер является просто ящиком с набором электронных схем. Он не обладает знаниями ни в одной области своего применения. Все эти знания сосредоточены в выполняемых на компьютере программах. Для того , чтобы компьютер мог осуществить определенные действия , необходимо составить для компьютера программу , т.е точную и пол=дробную последовательность инструкций на понятном компьютере языке , как надо правильно обрабатывать информацию. Меняя программы для компьютера , можно привести его в рабочие место бухгалтера ил конструктора , статистика или агронома , редактировать документ или играть в игры. Поэтому для эффективного использования компьютера необходимо знать назначение и свойства необходимые при работе с ним программ.
Программы . работающие на компьютеры можно разделить на три категории :
Прикладные программы , непосредственно обеспечивающие выполнение необходимых пользователям работ : редактирование текстов , рисование
картинок , обработку информационных массивов и т.д.
Системные программы , выполняющие различные вспомогательные функции , например создание копий используемой информации , проверку работоспособности устройств компьютера и т.д. Огромную роль среди всех системных программ играет операционная система - программа , управляющая компьютером , запускающая все другие программы и выполняющая для них различные сервисные функции.
Инструментальные системы (системы программирования ) , обеспечивающие создание новых программ для компьютера.
КР. 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 |
a>i> |
a>i> |
|
|
A1 |
1 1
30 |
2 2
20 |
0 4
|
4 1
|
50 |
0 |
|
A2 |
2 2 |
3 3
10 |
1 1
10 |
5 5
10 |
30 |
1 |
|
A3 |
1 3 |
2 2 |
0 4 |
4 4
10 |
10 |
0 |
|
заявки b>j> |
30 |
30 |
10 |
20 |
90 |
|
|
B>j> |
1 |
2 |
0 |
4 |
1,2 1,4
10
2,2 2,4
|
B1 |
B2 |
B3 |
B4 |
a>i> |
a>i> |
|
|
A1 |
1 1
30 |
2 2
10 |
0 4
|
1 1
10 |
50 |
0 |
|
A2 |
2 2
|
3 3
20 |
1 1
10 |
2 5
|
30 |
1 |
|
A3 |
4 3 |
5 2 |
3 4 |
4 4
10 |
10 |
3 |
|
b>j> |
30 |
30 |
10 |
20 |
90 |
|
|
B>j> |
1 |
2 |
0 |
1 |
1,1
1,4
10
3,1 3,4
КР. 2203 81 - 21
|
B1 |
B2 |
B3 |
B4 |
a>i> |
a>i> |
|
|
A1 |
1 1
20 |
2 2
10 |
0 4 |
1 1
20 |
50 |
0 |
|
A2 |
2 2 |
3 3
20 |
1 1
10 |
2 5 |
30 |
1 |
|
A3 |
3 3
10 |
4 2 |
2 4 |
3 4 |
10 |
2 |
|
b>j> |
30 |
30 |
10 |
20 |
90 |
|
|
Bj |
1 |
2 |
0 |
1 |
1,1 1,2
10
3,1 3,2
|
B1 |
B2 |
B3 |
B4 |
a>i> |
a>i> |
|
|
A1 |
1 1 30 |
-1 2 |
-3 4 |
1 1 20 |
50 |
0 |
|
A2 |
5 2 |
3 3 20 |
1 1 10 |
5 5 |
30 |
4 |
|
A3 |
4 3 |
2 2 10 |
0 4 |
4 4 E |
10+E |
3 |
|
b>j> |
30 |
30 |
10 |
20+E |
90+E |
|
|
B>j> |
1 |
-1 |
-3 |
1 |
1,1 1,2
10
2,1 2,2
КР. 2203 81 - 21
|
B1 |
B2 |
B3 |
B4 |
a>i> |
a>i> |
|
|
A1 |
1 1 10 |
2 2 20 |
0 4 |
1 1 20 |
50 |
0 |
|
A2 |
2 2 20 |
3 3 |
1 1 10 |
2 5 |
30 |
1 |
|
A3 |
1 3 |
2 2 10 |
0 4 |
1 4 |
10 |
0 |
|
b>j> |
30 |
30 |
10 |
20 |
90 |
|
|
B>j> |
1 |
2 |
0 |
1 |
F>min>=1·10 +2·20 +2·10 +1·10 +2·20 +20*1 = 140
Найден оптимальный план перевозок , равный 140.
КР. 2203 81 – 21
8.АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
В процессе решения транспортной задачи методом потенциалов было получено решение , которое является оптимальным , потому , что для каждой независимой клетки выполняется критерий оптимальности плана транспортной задачи :
C¢>ij> –C>ij> <=0
Так же суммарная стоимость перевозок груза с каждой последующей итерацией уменьшалась и оказалась равной 140 рублям.
Еще одним немаловажным фактором является то , что потребность получателя в грузе полностью удовлетворена , а поставщик реализовал весь свой груз.
Результат подсчитанный ручным счетом сходится с ответом , полученным на ЭВМ с помощью составленной программы. Расхождений нет.
Вектор полученных результатов:
10 20 0 20
c= 20 0 10 0
0 10 0 0
ÊÏ. 2203 81 - 21
ЗАКЛЮЧЕНИЕ
Основной задачей данного курсового проекта являеся нахождение оптимального плана перевозок груза от поставщиков к потребителям . нахождение минимальной функции.
Эта задача сводится к транспортной задаче.
В
процессе разработки курсового проекта
былы составлена универсальная программа
для решения аналогичных задач. Правильность
работы задачи определяется с помощью
задачи - теста . Для проверки правильности
работы работы программы были заданны
: количество поставщиков и потребителей
, наличие груза , заявки и тарифы перевозок.
Результаты были подсчитаны вручную , а
их решение совпадает с результатом
машинного счета. Полученный верный
результат позволяет применять данную
программу к производственным и транспорным
задачам.