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

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

• необходимым и достаточным условием существования решения является баланс между спросом и предложением;

• по загруженным клеткам определяют систему потенциалов:

,

где – потенциал строки;

–потенциал столбца;

–тариф соответствующей клетки.

• в оптимальном распределении сумма потенциалов строки и столбца не должна превосходить тариф соответствующей незагруженной клетки;

• количество поставок должно быть равно величине , где - число поставщиков, - число потребителей.

Метод потенциалов осуществляется в три этапа:

1. Построение первоначального опорного плана (начальное распределение грузов).

2. 0ценка оптимальности распределения грузов с помощью системы потенциалов.

3. Улучшение плана перевозок, если оно возможно.

Второй и третий этапы повторяются до тех пор, пока решение не станет оптимальным.

I этап. Построение начального опорного плана

Начальное распределение можно выполнять различными способами: способом северо-западного угла, способом наименьших тарифов, двойного предпочтения, способом Фогеля, способом Лебедева-Тихомирова и др. Наиболее простым и легко реализуемым на ЭВМ является способ северо-­западного угла. Он заключается в том, что от каждого поставщика, начиная с первого, вывозят весь груз с учетом запросов потребителей. Распределение завершено, если весь груз от поставщиков вывезен, а каждый потребитель получил требуемый объем.

Рассмотрим пример: имеется три поставщика и три потребителя , указаны мощности поставщиков, спрос потребителей и тарифы на перевоз груза (табл. 1).

Таблица 1

Поставщики	Мощность
		200	250	200
	250	5 200	4 50 –	1 ^+(4)	0
	150	1 (3)	3 150	3 (1)	– 1
	250	1 (2)	2 50 +	3 – 200	– 2
		5	4	5	–

Установим, прежде всего, наличие баланса между спросом и предложением

250 + 150 + 250 = 650

200 + 250 + 200 = 650

Баланс есть. Теперь распределим груз, начиная с первой верхней клетки, отсюда и название способа - северо-западный угол. Распределение завершено, необходимо определить затраты (величину ) и оценить оптимальность решения.

.

II этап. Оценка оптимальности решения

По загруженным клеткам составим систему уравнений для потенциалов, предварительно проверив количество заполненных клеток. Их должно быть . Именно столько и есть. Сумма потенциалов строки и столбца должна равняться транспортным тарифам загруженных клеток; на основе чего получаем систему для потенциалов:

; ;

; ; .

Имеем систему из 5 уравнений с 6 неизвестными, поэтому один из потенциалов примем равным 0. Обычно берут и находят все остальные потенциалы:

; ; ; ; .

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

; ;

; .

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

III этап. Построение нового распределения

Из всех клеток, для которых условие оптимальности не выполняется, выбирают ту, в которой расхождение наибольшее. Если таких клеток несколько, то выбирают клетку с меньшим тарифом. Ее отмечают знаком “+”. Начиная от выбранной клетки, строят прямоугольную фигуру, все остальные вершины которой располагаются в заполненных клетках. Знаки вершин чередуют.

Прямоугольные фигуры могут быть следующих видов:

Реже встречаются фигуры такого вида:

Вид фигуры предопределен распределением поставок.

Из всех клеток, отмеченных знаком минус, выбирают наименьший груз. Его перемещают вдоль прямоугольной фигуры, прибавляя, если стоит знак “+”, и, вычитая, если стоит знак “–”. Все изменения отражают в новой таблице. Величины, не участвующие в перераспределении, в новую таблицу переносят без изменения. Обратимся к примеру: в таблице 1 знаком “–” отмечены две клетки, выбирают наименьший груз 50 и перемещают его вдоль прямоугольной фигуры. Все изменения отражают в табл. 2. Получено новое распределение: необходимо оценить его, поэтому возвращаемся ко II этапу алгоритма.

Таблица 2

Поставщики	Мощность
		200	250	200
	250	5 200 –	4 .	1 + 50	0
	150	1 (7) +	3 – 150	3 (1)	3
	250	1 (6)	2 + 100	3 – 150	2
		5	0	1	–

.

Проверим число заполненных клеток, их по-прежнему 5. Вновь находим потенциалы, причем можно не составлять систему, а использовать правила:

1. В 1 строке берем 0.

2. Неизвестный потенциал столбца равен разности между издержками заполненной клетки и известным потенциалом строки.

3. Неизвестный потенциал строки равен разности между издержками заполненной клетки и известным потенциалом столбца.

Чередуя эти правила, найдем потенциалы.

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

В нашем примере самое большое расхождение между суммой потенциалов и тарифами – в клетке (2;1). Строим прямоугольную фигуру и замечаем, что две клетки, отмеченные знаком “–”, имеют одинаковую наименьшую величину 150, – этот факт ведет к вырожденному распределению. И действительно, после перемещения получим таблицу 3, в которой число загруженных клеток равно 4.

Таблица 3

Поставщики	Мощность
		200	250	200
	250	5 50 –	4 + (2)	1 200	0
	150	1 150	3 	3 	– 4
	250	1 0 +	2 – 250	3 	– 4
		5	6	1	–

Вырожденность может появиться и исчезнуть при переходе от таблицы к таблице. Чтобы продолжить решение в случае вырожденной задачи, вводят нулевые поставки, соответствующие клетки считают условно заполненными. Нулей будет столько, сколько недостает поставок. Их вписывают в клетки, имеющие малые издержки, и при этом следят, чтобы не получался замкнутый цикл (прямоугольная фигура, во всех вершинах которой - заполненные клетки). В данном примере следует вписать один ноль и лучше всего в клетку (3; 1). В остальном решение обычное: находят потенциалы, проверяют условие оптимальности. После очередного перераспределения получим таблицу 4.

Таблица 4

Поставщики	Мощность
		200	250	200
	250	5 	4 50	1 200	0
	150	1 150	3 	3 	– 2
	250	1 50	2 200	3 	– 2
		3	4	1	–

Задача вновь стала невырожденной - число загруженных клеток равно 5. Условие оптимальности выполняется. Размещение грузов видно из таблицы. Найденные суммы издержек на каждом этапе решения: , , , . На каждом этапе получали решение лучше предыдущего.

Замечание 1. Если мы имеем дело с открытой транспортной задачей, то для ее решения необходимо первоначально обеспечить баланс между спросом и предложением. Для этого вводят дополнительного поставщика, если спрос превышает предложение, в противном случае вводят дополнительного потребителя. Если добавляют поставщика, то его “мощностью” будет величина, недостающая до баланса, транспортные тарифы берут равными нулю. Аналогично поступают, если добавляют потребителя. В дальнейшем решение проводят по изложенному выше алгоритму. Введение дополнительного поставщика или потребителя имеет вполне определенное экономическое объяснение. В первом случае мы определяем, какому потребителю выгоднее недопоставить груз, исходя из интересов всех участников, во втором случае – у какого поставщика целесообразнее всего оставить часть груза.

Замечание 2. Ранее был подробно рассмотрен способ северо-западного угла для начального распределения грузов. Число итераций (таблиц) можно уменьшить, если воспользоваться способом наименьших тарифов. Он заключается в анализе всей матрицы тарифов, выборе наименьших значений и максимальном заполнении соответствующих клеток таблицы. Эти действия выполняются до тех пор, пока не будет распределен весь груз и удовлетворен спрос всех потребителей. В результате заполнения одной из клеток исключается из рассмотрения какой-то поставщик или потребитель. При этом условные участники транспортной задачи принимаются во внимание в последнюю очередь.

Рассмотрим пример транспортной задачи.

Поставщики	Мощность
		250	300	100	200
	100	2	6	3	5
	400	9	4	2	7
	200	3	2	5	4

Баланса между спросом и предложением нет, необходимо ввести условного поставщика с мощностью 150 тыс. единиц. Распределение выполним способом наименьших тарифов

Поставщики	Мощность
		250	300	100	200
	100	2 100	6 -	3 -	5 -	0
	400	9 -	4 100	2 100	7 200	3
	200	3 0	2 200	5 -	4 -	-2
	150	0 150	0 -	0 -	0 -
		2	1	-1	4	-

Полученный план не оптимален, следует перейти к лучшему. Это можно сделать на основе изложенного алгоритма.