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

Метод минимального (максимального) элемента Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел a i и b j. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Задание Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

Задание Найти опорный план для задачи Поставщики Потребители Запасы груза В1В1 В2В2 В3В3 В4В4 А1А X=X= А2А А3А Потребность в грузе

Метод потенциалов Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё ровно куда) какую-то сумму i ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму j. Эти платежи передаются некоторому третьему лицу (перевозчику). i + j ( i=1..m ;j=1..n) будем называть псевдостоимостью перевозки единицы груза из Ai в Bj. Заметим, что платежи i и j не обязательно должны быть положительными; не исключено, что перевозчик сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах ( i и j) одна и та же и от плана к плану не меняется.

Метод потенциалов До сих пор мы никак не связывали платежи ( i и j ) и псевдостоимости с истинными стоимостями перевозок Ci,j. Теперь мы установим между ними связь. Предположим, что план (xi,j) невырожденный (число базисных клеток в таблице перевозок ровно (m + n -1). Для всех этих клеток xi,j>0. Определим платежи ( i и j ) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям: i + j = сi,j, при xi,j >0. Что касается свободных клеток (где xi,j = 0), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

Метод потенциалов Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана (xi,j > 0) i + j = сi,j, (1) а для всех свободных клеток ( xi,j =0) i + j сi,j, (2) то план является оптимальным и никакими способами улучшен быть не может. Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных ровны нулю. План обладающий этим свойством называется потенциальным планом, а соответствующие ему платежи ( i и j) потенциалами пунктов Ai и Bj ( i=1,...,m ; j=1,...,n ).

Метод потенциалов Для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: Какова бы ни была система платежей ( i и j ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке.

Процедура построения потенциального (оптимального) плана В качестве первого приближения к оптимальному плану берётся любой допустимый план. В этом плане m+n-1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи ( i и j), так, чтобы в каждой базисной клетке выполнялось условие : i + j = сi,j (3) Уравнений (3) всего m+n-1, а число неизвестных равно m+n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m+n-1 уравнений (3) можно найти остальные платежи i, j, а по ним вычислить псевдостоимости для каждой свободной клетки. Если оказалось, что все эти псевдостоимости не превосходят стоимостей, то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости, то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке.

Критерий оптимальности Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия i + j сi,j, то Х0 является оптимальным планом транспортной задачи. Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались. Цикл перерасчёта таблицы - это последовательность ячеек, удовлетворяющая условиям: одна ячейка пустая, все остальные занятые; любые две соседние ячейки находятся в одной строке или в одном столбце; никакие три соседние ячейки не могут быть в одной строке или в одном столбце. Пустой ячейке присваивают знак +, остальным - поочерёдно знаки - и +.

Метод потенциалов Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой r + s = сr,s, и строят соответствующий цикл; затем в минусовых клетках находят число X=min(Xi,j). Далее составляют новую таблицу по следующему правилу: В плюсовых клетках добавляем Х; Из минусовых клеток вычитаем Х; Все остальные клетки вне цикла остаются без изменения. Получим новую таблицу, дающую новое решение Х, такое, что F(X1)

Пример Найдём оптимальный план задачи. Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.

Пример В качестве опорного плана возьмем план, полученный с помощью метода "минимального элемента" Х11=3, Х12=12, Х21=2, Х24=8, Х25=15, Х31=15, Х33=5. Все остальные элементы равны 0. Составим систему уравнений для нахождения потенциалов решения, найдем сумму соответствующих потенциалов для каждой свободной ячейки и пересчитаем тарифы (стоимости) для каждой свободной ячейки.

Пример Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета 22. Получим:

Строим следующую транспортную таблицу

Пример Проверим полученный план на оптимальность. Теперь ячейка 12 не заполнена.

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

Пример Строим следующую транспортную таблицу.

Пример Проверим построенный план на оптимальность. Полученный план является оптимальным. Х11=15, Х22=12, Х24=8, Х25=5, Х31=5, Х33=5, Х35=10. Все остальные Хij=0. F=1*15+1*12+3*8+3*5+4*5+1*5+3*10=121

Задания