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

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

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

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

по предмету

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

Работу выполнил Работу проверили
студент группы П-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 начинается с левой верхней клетки таблицы. Находим значения 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 >еa­i , то такая задача называется – транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом , если ввести фиктивный пункт отправления 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.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений.
Это связано с тем , что первые компьютеры создавались как устройства для вычислений , грубо говоря , усовершенствованные , арифметические арифмометры. Принципиальное отличие компьютеров от арифмометров и других счетных устройств состояло в том , что арифмометры могли выполнять лишь отдельные вычислительные операции(сложение , вычитание , умножение , деление и др.) , а компьютеры позволяли проводить без участия человека сложные последовательные вычислительные операции по заранее заданной инструкции — программе. Кроме того , для хранения данных , промежуточных и итоговых результатов вычислений компьютеры содержат память.
Компьютер — это универсальный прибор для переработки информации. Но сам по себе компьютер является просто ящиком с набором электронных схем. Он не обладает знаниями ни в одной области своего применения. Все эти знания сосредоточены в выполняемых на компьютере программах. Для того , чтобы компьютер мог осуществить определенные действия , необходимо составить для компьютера программу , т.е точную и пол=дробную последовательность инструкций на понятном компьютере языке , как надо правильно обрабатывать информацию. Меняя программы для компьютера , можно привести его в рабочие место бухгалтера ил конструктора , статистика или агронома , редактировать документ или играть в игры. Поэтому для эффективного использования компьютера необходимо знать назначение и свойства необходимые при работе с ним программ.
Программы . работающие на компьютеры можно разделить на три категории

Прикладные программы , непосредственно обеспечивающие выполнение необходимых пользователям работ редактирование текстов , рисование картинок , обработку информационных массивов и т.д.
Системные программы , выполняющие различные вспомогательные функции , например создание копий используемой информации , проверку работоспособности устройств компьютера и т.д. Огромную роль среди всех системных программ играет операционная система — программа , управляющая компьютером , запускающая все другие программы и выполняющая для них различные сервисные функции.
Инструментальные системы (системы программирования ) , обеспечивающие создание новых программ для компьютера.

КР. 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
ai

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

заявки 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

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

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

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

bj
30
30
10
20
90

B­j
1
2
0
1

1,1 1,2
10
3,1 3,2

B1
B2
B3
B4
ai
ai

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

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

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

bj
30
30
10
20
90

Bj
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 –Cij <=0
Так же суммарная стоимость перевозок груза с каждой последующей итерацией уменьшалась и оказалась равной 140 рублям.
Еще одним немаловажным фактором является то , что потребность получателя в грузе полностью удовлетворена , а поставщик реализовал весь свой груз.
Результат подсчитанный ручным счетом сходится с ответом , полученным на ЭВМ с помощью составленной программы. Расхождений нет.
Вектор полученных результатов

10 20 0 20
c= 20 0 10 0
0 10 0 0

КП. 2203 81 — 21

ЗАКЛЮЧЕНИЕ

Основной задачей данного курсового проекта являеся нахождение оптимального плана перевозок груза от поставщиков к потребителям . нахождение минимальной функции.
Эта задача сводится к транспортной задаче.
В процессе разработки курсового проекта былы составлена универсальная программа для решения аналогичных задач. Правильность работы задачи определяется с помощью задачи — теста . Для проверки правильности работы работы программы были заданны количество поставщиков и потребителей , наличие груза , заявки и тарифы перевозок. Результаты были подсчитаны вручную , а их решение совпадает с результатом машинного счета. Полученный верный результат позволяет применять данную программу к производственным и транспорным задачам.