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

Из-за громоздкости симплексных таблиц, содержащих неизвестных, и большого объёма вычислительных работ для получения оптимального плана используются более простые методы. Самым распространённым является метод потенциалов.

Теорема 3.2. (признак оптимальности опорного решения).Если план опорныйтранспортной задачи является оптимальным, то ему соответствует совокупностьчиселичисел, удовлетворяющих условиям

(3.4)

для занятых клеток;

(3.5)

для свободных клеток.

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

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

Рассмотрим алгоритм решения транспортных задач методом потенциалов:

1. Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок.

2. Построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m + n –1) и убедиться в линейной независимости векторов условий.

3. Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений

приx_ij > 0,

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

приx_ij > 0,

если известен потенциал v_i , и

приx_ij > 0,

если известен потенциал u_j.

4. Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам

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

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

.

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «–», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «–», в которой достигается, остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равнымm + n – 1. Далее перейти к пункту 3 данного алгоритма.

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

Шаг 1.Составим систему соотношений:

соответствующих условиям (3.4). Система всегда содержит уравнений снеизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределённой и одному неизвестному придают произвольное значение (обычно нулевое). После этого остальные потенциалы определяются однозначно. В нашем примере 4+5-1=8 уравнений с 9 неизвестными. Составленный нами первоначальный опорный план содержал нулевую переменную. В этом случае обычно определяют строку, содержащую наибольшее число занятых клеток. В нашем случае это. Положим. Из последних трёх соотношений системы определяем,и. Из остальных уравнений получаем,,,,(табл. 3.5).

Таблица 3.5

Поставщики	Потребители														Запасы
		10		7		4	Θ		1			5	100
					0			100
		2	Θ	7		10			6			11	250
	200		50
		8		5		3			2			2	200
											200
		11		8	Θ	12			16			13	300
			150		100						50
Запросы	200		200		100			100			250			850

Шаг 2.Проверим условие оптимальности для незанятых клеток. Еслидля всех таких клеток, то план является оптимальным, если же для некоторых, то план – неоптимальный. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину разностии записываем её значение в левый нижний угол этой клетки. Получилось 3 таких клетки:,,.

Шаг 3. Теперь выбираем клетку, которую необходимо сделать базисной. Загрузке подлежит, в первую очередь, клетка, которой соответствует. В нашем случае это. Необходимо определить, сколько груза должно быть в неё распределено.

Шаг 4. Здесь необходимо выбрать клетку, которая выводится из базиса и определить величину перераспределения груза. Отмечаем знаком « + » незанятую клетку, которую надо загрузить. Вместе с ней в таблице сталозанятых клеток, следовательно, появится цикл (причём единственный), все вершины которого, за исключением клетки, находятся в занятых клетках. Начинаем движение по этому циклу от клетки, отмеченной знаком , расставляя поочерёдно во всех вершинах, в которых он меняет направление, знаки « – » и « + ». Затем находимв клетках, отмеченных знаком «–». Эта величина определяет, сколько единиц груза можно перераспределить по найденному циклу. Значениезаписываем в незанятую клетку, отмеченную знаком « + ». Двигаясь по циклу, вычитаемиз объёмов перевозок в клетках, отмеченных знаком « – » и прибавляем кв клетках, отмеченных знаком « + ».

Итак, строим цикл, в клетку заносим50 единиц и перераспределяем груз (табл. 3.6). Исключаем из базисных переменных и вводим.

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

Полагая , получим:,,,,,,,.

Таблица 3.6

Поставщики	Потребители																Запасы
		10			7			4			1			5	100
							50			50
		2			7			10			6			11	250
	200									50
		8			5			3			2			2	200
													200
		11			8			12			16			13	300
				200			50						50
Запросы	200			200			100			100			250			850

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

Замечание. В настоящее время решение задач ЛП успешно реализуется на ПК в Excel, а именно, с помощью надстройкиExcel−Поиск решения.