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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

ФГБОУ ВПО «Уральский государственный  экономический университет»

 

Центр дистанционного образования

 

 

 

 

 

 

 

 

РЕФЕРАТ

по дисциплине: Методы оптимальных решение

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

 

 

 

 

 

 

 

Исполнитель: студентка

Направление Экономика

Профиль  Экономическая

безопасность

группа ЭПБп- 12 КГ

Ф.И.О Смоленцева Н.В.

 

 

 

 

 

 

Екатеринбург

2014

Содержание

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

 

1. Формулировка транспортной задачи …………………………………..4-5
2. Математическая модель транспортной задачи………………..……..5-6
3. Необходимое и достаточное условия разрешимости транспортной задачи ……………………………………………………………..……..7-8
4. Свойство системы ограничений транспортной задачи ……………….8
5. Опорное решение транспортной задачи …………………………….8-9
6. Методы построения начального опорного решения …………………9

6.1 Построение первоначального  плана по способу северо- западного угла …………………………………………………………………………….…9

6.2 Построение первоначального  плана по способу минимального  элемента ………………………………………………………………………….9

7. Переход от одного опорного решения к другому ……………………10
8. Распределительный метод …………………………………………..10-11
9. Метод потенциалов ………………………………………………….11-17
10. Особенности решения транспортных задач с неправильным балансом……………………………………………………………….17-18
11. Алгоритм решения транспортной задачи методом потенциалов…..18

11.1 Предварительный шаг …………………………………………18-19

11.2 Общий повторяющийся  шаг ………………………………….19-22

12. Транспортная задача с ограничениями на пропускную способность.22
13. Транспортная задача по критерию времени ………………………22-23
14. Применение транспортной задачи для решения экономических задач…………………………………………………………………..23-24

 

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

 

Список использованной литературы………………………………………..26

 

 

 

 

 

 

 

 

 

 

 

Введение

Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь  дело в экономике. Решение таких  задач сводится к нахождению крайних  значений (максимума и минимума) некоторых функций переменных величин.

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

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

Весьма типичной задачей, решаемой с помощью линейного  программирования, является транспортная задача.

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

 

 

 

 

 

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

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

Исходная информация:

M_i - количество единиц груза в i-м пункте отправления (i= 1, 2, …, k);

N_j - потребность в j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);

a_ij - стоимость перевозки единицы груза из i-гo пункта в j-й.

Обозначим через x_ij планируемое количество единиц груза для перевозки из i-ro пункта в j-й.

В принятых обозначениях:

- общая (суммарная) стоимость перевозок;

- количество груза, вывозимого из i-ro пункта;

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

В простейшем случае должны выполняться следующие очевидные  условия:

 

 

 

Таким образом, математической формулировкой транспортной задачи будет найти:

min

 

при условиях

;

;

xij0 (i=1,2,…, k; j=1,2,…, l)

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

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

Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:  найти

min

при условиях:

 

 

Xij0

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

 

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

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

Обычно начальные условия  таких задач записывают в таблицу. Например, для k поставщиков и l потребителей такая задача имеет следующий  вид:

 

Здесь показатели aij означают затраты на перевозку единицы груза от i-го поставщика (i= 1,2,…,k) к j- тому потребителю (j= 1,2,…,l), Mi- мощность i- того поставщика в планируемый период, Nj- спрос j- того потребителя на этот же период. Обозначим через xij поставку (количество груза), коnторая планируется к перевозке от i- того поставщика к j- тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, т.е. функции

F=a₁₁+x₁₁+a₁₂+x₁₂….+a_ij+x_ij+….+a_kl+x_kl

при ограничениях 1*

Если к этим ограничениям добавить еще одно: 2*

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

Задачам, в которых ограничение 2* отсутствует, т.е. , первоначально соответствует открытая модель.

Отметим некоторые особенности  экономико -математической модели транспортной задачи.

Система ограничений 1* сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.

Матрица коэффициентов при  переменных в системе (1) состоит  только из единиц и нулей.

Система ограничений 1* включает k уравнений, связывающих поставки i- того поставщика с мощностью Mi (i= 1,2,…,k) этого поставщика, и l уравнений, связывающих поставки j- тому потребителю со спросом Nj (j= 1,2,…,l) этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число - числу столбцов.

Число переменных xij, входящих в целевую функцию и в систему уравнений 1*, равно произведению kl, т.е. числу клеток таблицы.

Таким образом, система ограничений 1* есть система из k+l уравнений с kl переменными.

Любое решение транспортной задачи (x₁₁, x₁₂,…, xkl) называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях.

Оптимальному решению  транспортной задачи соответствует  оптимальное распределение поставок, при котором целевая функция F=a11+x11+a12+x12….+aij+xij+….+akl+xkl достигает своего минимума.

В ходе решения задачи и  нужно получить это оптимальное  распределение поставок, которому соответствует какое- то допустимое базисное решение системы ограничений 1*.

3. Необходимое и достаточное условие разрешимости транспортной задачи

Ограничение 1* и условия неотрицательности переменных, исключающие обратные перевозки xij>0; i= 1, 2, …, k; j= 1, 2,., l.

Эти условия образуют систему  ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.

Как видим, система ограничений задана в основном (k+l) уравнениями. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения.

Сложим элементы xij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим . Сложим те же элементы по столбцам, каждый столбец дает Nj, и в сумме получим . Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие .

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

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

Действительно, пусть . Рассмотрим такие числа:

      i=1,2,…k       j=1,2,….l

Убедимся, что эти числа  образуют допустимый план. Для этого  достаточно проверить, что они удовлетворяют  всем ограничениям задачи.

Просуммируем эти числа  по индексу i: .

Но величины Nj,   от индекса i не зависят и их можно вынести за знак суммы. В результате:

 

или

x1j+z2j+…..+xkj=Nj, j= 1,2,…,l.

Следовательно, взятые числа  удовлетворяют группе уравнений 1*.

Просуммируем эти числа  по индексу j:

 

Вынося постоянные Mi и за знак суммы и имея в виду, что , получаем:

 

или в развернутом виде

xi1+xi2+….+xil=Mi,    i= 1,2,…,k.

Как видим, наши числа удовлетворяют группе уравнений 1*. Эти числа неотрицательны, т.е. система ограничений полностью удовлетворяется. Таким образом, допустимый план существует, что и требовалось доказать.

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

 

4. Свойство системы ограничений транспортной задачи

Согласно теореме о  структуре координат опорного плана  задачи линейного программирования, в невырожденном опорном плане  должно содержаться r отличных от нуля координат, где r- ранг системы ограничений , (i=1,2,…,k)  , (j=1,2,…,l).

В этой системе ограничений  уравнений закрытой транспортной задачи имеется k+l-1 линейно- независимых уравнений, т.е. ранг системы ограничений равен k+l-1.

 

5. Опорное решение транспортной задачи

Опорное решение (опорный  план, базисное решение, basic solution)- одно из допустимых решений, находящихся в вершинах области допустимых решений. Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений.

При решении задачи линейного  программирования можно поступить  следующим образом: найти любое из таких «вершинных» решений, не обязательно оптимальное, и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен, если нет- последовательно проверяют, не будут ли оптимальными соседние вершинные точки. Ту из них, в которой план эффективнее, принимают снова за исходную точку и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся так называемый симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием «методы последовательного улучшения допустимого решения (МПУ)»: метод обратной матрицы, или модифицированный симплекс- метод, метод потенциалов для транспортной задачи и другие. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному.