Метод потенциалов

из всей таблицы стоимостей выбирают наименьшую и в клетку, которая

ей соответствует, помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

вида:

к следующему. Представим себе что каждый из пунктов отправления 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 , а по ним вычислить псевдостоимости для каждой свободной клетки.
Если оказалось, что все эти псевдостоимости не превосходят стоимостей, то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости, то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке.

всех незаполненных ячеек выполняются условия αi + βj ≤ сi,j,

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

находят незаполненную ячейку (r, s), в которой αr + βs

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

трёх складов в пять магазинов. На складах имеется соответственно 15,

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

"минимального элемента" Х11=3, Х12=12, Х21=2, Х24=8, Х25=15, Х31=15, Х33=5. Все

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

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

Х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