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

Теорема 3. Если план X* = [х_ij*]_m×n транспортной задачи является оптимальным, то ему соответствует система из m + n чисел u_i*, v_j*, удовлетворяющих условиям u_i* + v_j* = cij для х_ij* >0 и u_i* + v_j* ≤ c_ij для х_ij* = 0 (i=1 , m; j = 1, n)

Числа u_i* и v_j*, называются потенциалами соответственно i-го поставщика и j-го потребителя.

Доказательство. Транспортную задачу (1) - (3) можно рассматривать как двойственную задачу к некоторой исходной задаче, решаемой на максимум. Построим эту задачу. Так, если i-му ограничению двойственной задачи х_i1 + х_i2 + ... + x_in = a_i в исходной задаче соответствует переменная u_i (i = l, m), а j-му ограничению х_1j + х_2j + ... + x_mj = b_i — переменная v_j (j = 1, n), то исходной будет задача: найти максимальное значение функции

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

u_i + v_j ≤ c_ij (i=1, m; j = 1, n).

Оптимальным для двойственной задачи является план х*, а для исходной у* = (u_i*; v_j*). Для пары взаимодвойственных задач на основании первой теоремы двойственности имеет место равенство ƒ_min = ƒ_max, а по второй теореме двойственности выполняются условия u_i* + v_j* = c_ij для х_ij*>0, u_i* + v_j* ≤ c_ij для х_ij* = 0 (i=l, m; j=l , n).

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

1) каждой занятой клетке в распределительной таблице соответствует сумма потенциалов, равная тарифу этой клетки, т. е. u_i + v_j = c_ij;

2) каждой свободной клетке соответствует сумма потенциалов, не превышающая тарифа этой клетки, т. е. u_i + v_j ≤ c_ij.

Доказанная теорема носит название теоремы о потенциалах. На ней основан специальный метод решения транспортной задачи, названный методом потенциалов. В соответствии с введенным понятием потенциалов и с учетом связей между моделями двойственных задач каждому поставщику (ограничению по запасам) поставим в соответствие потенциал u_i, (i = l, m), а каждому потребителю (ограничению по спросу) — потенциал v_j, (j = 1, n).

Согласно теореме о потенциалах, каждой занятой клетке будет соответствовать уравнение u_i + v_j = с_ij;. Так как всех занятых клеток должно быть m + n - 1, т. е. на единицу меньше числа потенциалов, то для определения чисел u_i, v_j, необходимо решить систему из m + n - 1 уравнений u_i + v_j = с_ij с m + n неизвестными. Система неопределенная, и, чтобы найти частные решения, одному из потенциалов придаем произвольное числовое значение, тогда остальные потенциалы определяются однозначно. Для облегчения расчетов одному из потенциалов придают обычно значение, равное нулю.

Для исследования плана на оптимальность для каждой свободной клетки проверяется условие u_i + v_j ≤ с_ij. Если хотя бы одна свободная клетка не удовлетворяет данному условию, то опорный план не является оптимальным, его можно улучшить за счет загрузки этой клетки. Если таких клеток несколько, то наиболее перспективной для загрузки является клетка, для которой разность (оценка) между тарифом клетки и суммой потенциалов наименьшая, т. е.

s_ij = с_ij - (u_i + v_j) < 0.

Если для всех свободных клеток оценки s_ij ≥ 0, то опорный план перевозок является оптимальным.

Итак, если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозок улучшается. Для наиболее перспективной свободной клетки строится замкнутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно приписываются знаки: свободной клетке - плюс, следующей по часовой или против часовой стрелки занятой клетке - минус, следующей - снова плюс и т. д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество λ груза, которое и перемещается по клеткам этого цикла: прибавляется к поставкам в положительных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушится (рис.6. 1).

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

Рис.5. 1.

Сформулируем алгоритм решения транспортной задачи методом потенциалов:

1)построить опорный план по одному из правил,

2)вычислить потенциалы поставщиков и потребителей u_i и v_j (i = 1, m, j = 1, n), решив систему уравнений вида u_i + v_j = с_ij;

3) вычислить оценки s_ij для всех свободных клеток по формуле s_ij = с_ij - (u_i + v_j). Если все s_ij ≥ 0, то полученный план является оптимальным. При этом если все s_ij >0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка s_ij = 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

Пример. Найти оптимальный план перевозок ТЗ, условие которой представлено в табл.5.2.

Таблица 5. 2

Поставщики	Потребители				Запас груза,т
	В1	В2	В3	В4
А1 А2 А3	4 6 8	10 7 9	5 2 12	3 8 11	60 100 70
Потребность в грузе,т	50	55	70	45	230

Решение Поскольку запасы грузов превышают спрос потребителей, вводится фиктивный потребитель, спрос которого

т.

Все тарифы фиктивного потребителя равны нулю: Имеем ТЗ закрытого типа, которую решаем методом потенциалов.

Исходное опорное решение получим, например, по правилу «минимального элемента» табл.5.3.

Таблица 5.3

аi\bj	50		55		70		45		10		ui
60	15	4		10		5	45	3		0	0
100	2 0	6		7	70	2		8	10	0	2
70	15	8	55	9		12		11		0	4
vj	4		5		0		3		2

Получен невырожденный план. Потенциалы поставщиков и потребителей определены непосредственно в таблице. Оценки свободных клеток следующие:

s₁₂ = 10 – 5 = 5, s₁₃ = 5 – 0 = 5, s₁₅ = 0 + 2 = 2,

s₂₂ = 7 – (2 + 5) = 0, s₂₄ = 8 – (2 + 3) = 3,

s₃₃ = 12 – 4 = 8, s₃₄ = 11 – (4 + 3) = 4,

s₃₅ = 0 – (4 - 2) = -2.

Среди оценок имеется отрицательная (s₃₅ = -2). План перевозок можно улучшить за счет загрузки клетки (3;5). В отрицательных вершинах построенного для клетки (3;5) цикла наименьшее количество груза равно min (10,15) = 10 ед.

После смещения по циклу 10 ед. груза получим новый план перевозок (табл.5.4).

Как и для предыдущего плана перевозок, все потенциалы поставщиков и потребителей определены в таблице. Оценки свободных клеток:

s₁₂ = 10 – 5 = 5, s₁₃ = 5 – 0 = 5, s₁₅ = 0 – (0 - 4) = 4,

s₂₂ = 7 – (2 + 5) = 0, s₂₄ = 8 – (2 + 3) = 3,

s₂₅ = 0 – (2 – 4) = 2, s₃₃ = 12 – 4 = 8,

s₃₄ = 11 – (4 + 3) = 4.

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

со значением целевой функции f(X*) = 1050 ден. ед.

Таблица 5.4

аi\bj	50		55		70		45		10		ui
60	15	4		10		5	45	3		0	0
100	30	6		7	70	2		8		0	2
70	5	8	55	9		12		11	10	0	4
vj	4		5		0		3		-4

Загрузка x₃₅ = 10 т для фиктивного потребителя указывает на остаток нераспределенного груза 10 т у поставщика А₃.