Экономико-математическое моделирование

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


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

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



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

                                 по предмету


                    « Языки программирования и разработка
                         программного обеспечения »
                                  на тему :
                    « Минимизация стоимостей перевозок »



   Работу выполнил
 Работу проверили
   студент группы П-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 (i=1,m)



                                             КП. 2203 81 – 21
еxij=bj (j=1,n)
Здесь вводим фиктивного потребителя Bф и приписываем ему заявку bф=еai -
еbj . Вводим фиктивный сотолбец , т.е Ciф=0 (i =1,m). Все стоимости будут
равны нулю , это значит , что грузы ciф останутся невостребованными , т.е
введением фиктивного потребителя , мы свели транспортную задачу с
неправильным балансом к задаче с правильным балансом.
Если сумма подданных заявок превышает наличные запасы
еbj >е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 <=0 , то такой план является
оптимальным. Если хотя бы в одной свободной клетке Cўij > 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)




смотреть на рефераты похожие на "Минимизация стоимостей перевозок"