2.3. Определение оптимального плана перевозок методом потенциалов

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

Таблица 6

Прямая задача	Двойственная задача
z=	w=

Переменные ДЗ называются:

u_i – потенциал поставщика A_i, i=1m;

v_j – потенциал потребителя B_j, j=1n.

Сформулируем в терминах потенциалов критерий оптимальности плана перевозок.

Теорема 4. Пусть Х*=  – план перевозок ТЗ. Для того, чтобы этот план был оптимальным, необходимо и достаточно, чтобы существовали потенциалы поставщиков u_i, i=1m, и потенциалы потребителей v_j, j=1n, удовлетворяющие условиям:

– сумма потенциалов каждого поставщика и каждого потребителя не превосходит соответствующей стоимости перевозки единицы груза, т.е.

; (6)

– если по плану Х* имеет место перевозка от поставщика A_i потребителю B_j, то сумма их потенциалов равна соответствующей стоимости перевозки единицы груза, т.е. если >0, то

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

u_i+v_j=с_ij. (7)

Т.к. занятых ячеек (а, значит, и уравнений (7)) т+п-1, а неизвестных потенциалов т+п, то одному из неизвестных нужно придать произвольное значение (обычно полагают u₁=0), и тогда остальные потенциалы определяются однозначно. Затем для свободных ячеек проверяются условия (6), или

_ij=u_i+v_j-с_ij≤0 (6)

(_ij называется оценкой соответствующей ячейки). Если все эти неравенства выполняются, то, согласно приведённому выше критерию (теор. 4), план перевозок оптимальный. Если хотя бы одно из неравенств (6) не выполняется, то план не является оптимальным. В этом случае из свободных ячеек с положительной оценкой выбирается та, для которой эта оценка является наибольшей. Если наибольших оценок несколько, то выбирается та из ячеек, где меньше тариф.

В транспортной таблице для выбранной свободной ячейки проводится замкнутая ломаная прямая, звенья которой лежат только в строках или столбцах и соединяют какие-либо две ячейки, а вершины (кроме начальной) расположены в занятых ячейках. Такая ломаная прямая называется циклом. Для каждой ячейки можно построить только один цикл. Вершинам цикла приписываются чередующиеся знаки «+» и «-», причём свободная ячейка снабжается знаком «+». В ячейках, соответствующих отрицательным вершинам цикла, отыскивается наименьшее значение объёма перевозок, α=min , которое перераспределяется по ячейкам цикла, т.е. прибавляется к переменным в ячейках со знаком «+» и вычитается от переменных в ячейках со знаком «-». В ячейках, не вошедших в цикл, переменные остаются неизменными. Ячейка «-», по которой определялась величина α (для неё х_ij=α), остаётся пустой. Если таковых ячеек несколько, то одна из них (желательно с большим тарифом) остаётся пустой, а в остальных проставляются нули.

В результате перераспределения перевозок по циклу получается новый план с меньшими затратами. Примеры некоторых циклов показаны на рисунке 1.

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

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

Алгоритм решения ТЗ методом потенциалов.

Этап 1. Составление начального плана перевозок.

Этап 2. Вычисление потенциалов поставщиков и потребителей; проверка оптимальности плана перевозок. Если план оптимальный, то задача решена; иначе следует переход к этапу 3.

Этап 3. Построение нового (улучшенного) плана перевозок, для которого транспортные затраты меньше или, по крайней мере, равны затратам для предыдущего плана. Далее следует переход к этапу 2.

Пример 3. Рассмотрим применение метода потенциалов для нахождения оптимального плана ТЗ, опорный план которой найден МНС (таблица 5).

Для определения потенциалов составляем систему уравнений (для занятых ячеек)

u₁+v₂=1, u₁+v₃=2, u₂+v₁=3, u₂+v₃=3, u₃+v₃=5, u₃+v₄=2, u₄+v₁=0.

Полагая u₁=0, находим v₂=1, v₃=2, u₂=1, v₁=2, u₃=3, v₄=-1, u₄=-2.

Потенциалы проставлены в табл 7 (столбец ui и строка vj), которую мы обозначим «Итерация 0». Потенциалы можно вычислять и непосредственно в таблице, не выписывая систему уравнений. Если известны потенциал и тариф занятой ячейки, то из соотношения ui+vj=сij легко определить неизвестный по-		Таблица 7 (Итерация 0)
		Вj Аi	45	35	55	65	ui
		40	4 –	1 35	2 5	5 –	0
		60	3 35	2 –	3 25	7 –	1
		90	4 –	4 –	5 25	2 65	3
		10	0 10	0 –	0 –	0 –	-2
		vj	2	1	2	-1

тенциал (из суммы вычесть известное слагаемое).

Определим оценки свободных ячеек (_ij=u_i+v_j-с_ij):

₁₁=0+2-4=-2, ₁₄=0+(-1)-5=-6, ₂₂=1+1-2=0, ₂₄=1+(-1)-7=-7, ₃₁=3+2-4=1, ₃₂=3+1-4=0, ₄₂=(-2)+1-0=-1, ₄₃=(-2)+2-0=0, ₄₄=(-2)+(-1)-0=-3.

Далее оценки будем также вычислять непосредственно в таблице, помещая их в левом нижнем углу каждой свободной ячейки. Т.к. среди оценок есть положительная, то план Х₀=Х_н.ст не является оптимальным. Перейдём к этапу 3 – улучшению плана Х₀. Для этого выберем ячейку (3,1) (она имеет положительную оценку 1). Из этой ячейки проводим цикл (табл.8). В цикл войдут ячейки (3,1) (отмечается знаком «+»), (3,3) (отмечается знаком «-»), (2,3) (отмечается знаком «+»), (2,1) (отмечается знаком «-»). Наименьшее значение груза, стоящее в вершинах цикла со знаком «-», α=min(25,35)=25. Это число прибавляется к переменным в ячейках со знаком «+» и вычитается от переменных в ячейках со знаком «-». В результате получается новый план с меньшими затратами (таблица 9, итерация 1).

Таблица 8							Таблица 9 (Итерация 1)
Вj Аi	45	35	55	65	ui		Вj Аi	45	35	55	65	ui
40	4 -2	1 35	2 5	5 -6	0		40	4 -2	1 35	2 5	5 -5	0
60	Ө 3 35	2 0	 3 25	7 -7	1		60	3 10	2 0	3 50	7 -6	1
90	4 1	4 0	Ө 5 25	2 65	3		90	4 25	4 -1	5 -1	2 65	2
10	0 10	0 -1	0 0	0 -3	-2		10	0 10	0 -1	0 0	0 -2	-2
vj	2	1	2	-1			vj	2	1	2	0

Для нового плана Х₁ определяем новые потенциалы и оценки свободных ячеек (табл.9). Все оценки неположительные. Следовательно, полученный план

Х^=

является оптимальным (фиктивного поставщика в ответе не указываем). Кроме того, план не вырожден (базисные переменные не равны нулю) и альтернативен (некоторые оценки ₂₁=₄₃=0). При данном плане стоимость перевозок

z_min=135+25+310+350+425+265=455 (ден. ед.).