Методы оптимального решения транспортной задачи с дополнительными условиями (ограничениями)

 

Министерство  сельского хозяйства Р.Ф

Федеральное государственное  образовательное учреждение

высшего профессионального  образования

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

имени академика Д. Н. Прянишникова

 

 

 

 

                                                                                  Кафедра ИТАП

 

 

 

Курсовая работа по дисциплине «Методы оптимизации»

На тему: «Методы оптимального решения транспортной задачи с дополнительными условиями (ограничениями)»

 

 

 

 

 

                                                                          Исполнитель: студент группы ПИ-31

                                                      Бурягина Оксана Юрьевна

                                                 Руководитель: старший

                                                             преподаватель кафедры ИТАП                                                               

                                                                Гревцев Александр Михайлович                                                                                                                       

 

                                                                  

 

 

Пермь 2010

Содержание

Введение………………………………………….……………………………….….2

1. Транспортная  задача: общая постановка, алгоритм решения, основные методы построения ППП, ограничения…………………………………………….4

1.1.Формулировка транспортной  задачи……………………………………...…5

1.2 Общий алгоритм  решения транспортной задачи……………………………5

1.3 Основные  методы построения первоначального  опорного плана……………5

1.3.1 Метод северо  – западного угла………….……………………………………6

1.3.2 Метод минимальной  стоимости………………………………………………6

1.3.3 Метод аппроксимации  Фогеля………………………………………………..6

1.4 Транспортная  задача с дополнительными условиями…………………….......7

2. Примеры ограничений в транспортной задаче и методы их решения………8

2.1 Запрет перевозок…………………………………………………………………8

2.2 Обязательная  поставка…………………………………………………………10

2.3 Задача с  запретом поставки и обязательной  поставкой………………….......11

2.4 «Потолок» транспортных  перевозок………………………………………….20

2.5 «Пол» транспортных  перевозок……………………………………………….22

3. Решение транспортных задач с ограничениями с помощью ЭВМ…………...26

3.1 Решение транспортной  задачи с помощью MS Excel………………………..26

3.2 Программная реализация транспортной задачи с помощью Delphi 7………30

Заключение………………………………………………………………………….31

Список использованных источников……………………………………………...32 
Приложение 1 Блок-схема программы....................................................................33

Приложение 2 Программный  код............................................................................36

 

 

 

Введение

Линейное программирование — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. Одна из наиболее распространенных задач линейного программирования — транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот).

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

В настоящее  время разработано множество  различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Транспортная задача сама по себе может быть усложнена некоторыми существенными ограничениями. Например, потребитель заключает с поставщиком сделку на доставку определенного количества груза или устанавливается «потолок» объема перевезенного груза на одного или нескольких поставщиков. И таких ограничений может существовать огромное количество. Кроме того, следует учитывать, что математическая модель транспортной задачи позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью.

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

Для реализации данной цели в работе необходимо решить следующие задачи:

- рассмотреть  транспортную задачу, общую постановку, цели, задачи;

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

- охарактеризовать  методы решения транспортной  задачи с ограничениями;

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Транспортная  задача: общая постановка, алгоритм решения, основные методы построения ППП, ограничения.

1. Формулировка транспортной задачи.

Под названием  «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к  задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

 Пусть имеется m складов, в которых сосредоточен некоторый однородный продукт в количествах соответственно а_i(i=1,2,…,m) единиц. Имеется n потребителей этого продукта в количествах соответственно b_j(j=1,2,…,n) единиц. На основании опытов и расчетов известно, что на доставку одной единицы продукта с i-того склада j-тому потребителю затрачивается с_ij денежных единиц. Все значения c_ij являются постоянными величинами.

Обозначим через x_ij³0 (i=1,2,…,m; j=1,2,…n) количество продукта, планируемого для доставки с i-того склада j-тому потребителю. Естественно, что если x_ij=0, то доставка продукта с i-того склада j-тому потребителю не планируется.

Очевидно, можно  предложить большое число планов обеспечения потребителей, но при выборе любого из них должны быть учтены условия:

                                                           (1)

                                                                   (2)

Выражение (1) определяет, что с любого склада можно взять продукта не более имеющихся там запасов. Выражение (2) означает, что каждый потребитель обеспечивается полностью его заявке. По смыслу задачи должно выполняться условие:

                                                                                       (3)

Последнее выражение (3) означает, что запасов на складах достаточно для снабжения всех потребителей.[1]

2. Общий алгоритм решения транспортной задачи:

1) Составить таблицу специального вида решения транспортной задачи.

2) Определение типа модели (открытая или закрытая)

3) Определение ранга для закрытой модели.

4) Нахождение  первоначального плана поставок (ППП) любым из методов. (Северо-западного угла, минимальной стоимости, методом Фогеля).

5) Нахождение  оптимального плана поставок (методом потенциалов или любым другим методом).

1.3 Основные методы построения первоначального опорного плана.          

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

Невырожденный опорный план транспортной задачи содержит m+n-1 положительных компонент или перевозок.    

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

    Занятые  клетки соответствует неизвестным,  и для невырожденного опорного  плана их количество равно  m+n-1.

Всякий план транспортной задачи, содержащий более m+n-1  занятых клеток, не являются опорным, так как ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл, с помощью которого уменьшают число занятых клеток до m+n-1.

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

1.3.1 Метод северо-западного угла

     При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях с помощью ЭВМ. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок.[2]

1.3.2 Метод минимальной стоимости

 При использовании метода минимальной стоимости запасы поставщиков перераспределяются потребителям по минимальным стоимостям. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.  В данном методе не учитываются величины тарифов, в методе же наименьшей стоимости эти величины учитываются, и часто последний метод приводит к плану с меньшими общими затратами, хотя это и не обязательно.[2]

1.3.3 Метод аппроксимации Фогеля

Кроме рассмотренных  выше способов иногда используется, так  называемый, метод Фогеля. Суть его  состоит в следующем: В распределительной  таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.[2]

1.4 Транспортная задача с дополнительными условиями.

Существует  множество способов решения транспортной задачи, которые не составляют труда  для их решения. Однако это в том  случае, если на рынке все идеально. То есть то количество товара, которое  поставщик может дать, соответствует  тому количеству товара, которое потребитель готов купить и не существует помех к обмену. Однако в нашей жизни ничего идеального не бывает. Рассмотрим небольшой пример: допустим, все как на идеальном рынке, то есть потребности потребителей и поставщиков совпадают. Но введем еще один пункт, у поставщика ограниченное количество транспортных средств. Что же делать тогда? В этом случае должны быть введены дополнительные ограничительные условия, учитывающие возможность транспортных путей и средств. Какие же еще ограничения могут существовать в решении транспортной задачи? Дальше я постараюсь ответить на этот вопрос.

 

 

 

 

 

 

 

 

 

 

 

2  Примеры  ограничений в транспортной задаче  и методы их решения

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

2.1 Запрет перевозок.

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

Рассмотрим частный случай транспортной задачи – задачу о  назначениях. Пусть у нас имеется 6 поставщиков и 6 потребителей. Поставщикам необходимо перевезти некоторое количество коробок шоколадных конфет, затраты на перевозку указаны в матрице. Причем 5 поставщик из-за обвала дороги не может доставить груз 4 потребителю. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки. Решим данную задачу венгерским методом (рисунок 1).

5	4	7	8	6	3
6	2	5	1	3	10
7	8	6	4	9	2
1	9	3	9	7	8
6	7	6	50	1	2
4	8	5	4	9	6

2	1	4	5	3	0
5	1	4	0	2	9
5	6	4	2	7	0
0	8	2	8	6	7
5	6	5	49	0	2
0	4	1	0	5	2