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

Цикломв транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке цикла совершает поворот на. Знаком «+» отмечают те вершины, в которых перевозки увеличиваются, а знаком «-« - те вершины цикла, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым, а стоимость плана может меняться.

Ценой цикланазывается изменение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком «+», а в отрицательных со знаком «-«.

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

Для нахождения циклов с отрицательной ценой вводится система платежей , и определяются величины, называемые «псевдостоимостями» перевозок единицы груза из пунктаiв пунктj. При этом цена цикла пересчета для каждой свободной клетки равна, если платежи , определять из условия:

для всех базисных клеток (i,j).

6.8. Вычислительная схема метода потенциалов

Шаг 1.Строим опорный план (методом северо-западного угла или методом минимальной стоимости) сбазисными клетками.

Шаг 2.Определяем платежи, из условий:для всех базисных клеток (ij). Один из платежей (в строке или столбце которого максимальное число базисных клеток) полагаем равным нулю.

Шаг 3.Считаем псевдостоимости для всех свободных клеток. Еслидля всех клеток, то план оптимален. Вычисляем значение целевой функциина этом плане и исследование прекращаем.

Шаг 4.Если есть свободная клетка, для которой, то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки.

Шаг 5.Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

6.9. Пример

Решить методом потенциалов транспортную задачу.

	1	2	3
1	3	8	2	35
2	7	4	8	30
	15	20	30	=

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

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

Из условий в базисных клетках получаем систему уравнений:

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

	1	2	3
1	15 3	[-] 20 8	12[+] 2	35	0
2	-1 7	[+] 0 4	[-] 30 8	30	-4
	15	20	30	=
	3	8	12

Стоимость перевозок по плану этой таблицы

Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки (1,3) цикл. Цена цикла. По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на. Для нового плана вычисляем новые значения платежей и псевдостоимостей:

	1	2	3
1	[-]15 3	-2 8	[+] 20 2	35	0
2	9 [+] 7	20 4	[-] 10 8	30	6
	15	20	30	=
	3	-2	2

Стоимость перевозок по плану этой таблицы

Полученная таблица имеет клетку (2,1) с отрицательной ценой . По циклу этой клетки переносим 10 единиц груза, при этом стоимость плана уменьшается наединиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:

	1	2	3
1	5 3	0 8	30 2	35	0
2	10 7	20 4	5 8	30	4
	15	20	30	=
	3	0	2

Стоимость перевозок по плану этой таблицы

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