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

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

(4)

f= (5).

Пусть опорный план имеет вид, приведенный в таблице

	В Р1	В Р2	Мощности поставщиков
Из М1
Из М2
Потребности

При этом заполненными оказались n+m-1=3 ячейки, а ячейка (2-1) осталась свободной.

Метод потенциалов заключается в введении для каждого столбца и каждой строки чисел (потенциалов) так, что для заполненных клеток выполняются условия

.

При этом мы получает три уравнения (по числу заполненных клеток) и четыре неизвестных. Поэтому одной неизвестной можно дать произвольное значение. Положим . Тогда

В каком случае план перевозок будет оптимальным? Выразим базовые переменные (те, которым соответствуют заполненные клетки) через свободную переменную (которой соответствует свободная клетка) Получим

, , .

f= =

План поставок будет оптимальным, если

(6)

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

Так как , то (6) можно записать в виде

или .

Таким образом, условия оптимальности полученного плана поставок :

для заполненных клеток, (7)

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

Данные условия оптимальности (7), (8) справедливы и для транспортных задач в общем случае ( причем, если для некоторой свободной клетки в (8) выполняется равенство, то оптимальное решение не будет единственным).

Рассмотрим, как можно улучшить опорный план поставок. Для этого рассмотрим опорный план поставок, полученный нами в предыдущем пункте методом «северо-западного угла».

	В Р1	В Р2	В Р3	В Р4	Мощности поставщиков	Потенциал
Из М1	-	+			40	0
Из М2		-		+	60	-3
Из М3	+			-	50	0
Потребности	30	50	30	40
Потенциал	4	5	4	5

Определим потенциалы строк и столбцов, полагая и пользуясь условиями (7).

, ,

Найдем следующие величины, которые мы будем называть оценками свободных клеток:

, ,

,

,

Условию оптимальности (8) не удовлетворяют клетки (1-3) и (3-1). Выбираем клетку (3-1), в которой оценка свободной клетки наибольшая, и будем изменять поставки. Изменения поставок будем производить по циклу. Циклом будем называть замкнутую ломаную, удовлетворяющую следующим свойствам:

1. Цикл начинается и заканчивается в выбранной нами свободной клетке;

2. Вершины ломаной лежат в заполненных клетках и в одной свободной клетке, а звенья ломаной расположены вдоль строк или столбцов таблицы;

3. Цикл начинается и заканчивается в выбранной нами свободной клетке и имеет четное число вершин.;

4. В каждой вершине цикла направление ломаной меняется на 90⁰;

5. В вершине свободной клетки ставим знак + , что означает увеличение поставки, далее в соседних клетках ставим противоположные знаки (знак – означает уменьшение поставки).

Ищем в цикле вершину, имеющую знак минус, с минимальной поставкой. В нашем примере это будет ячейка (1-1) с поставкой 30. Эту поставку мы и будем перемещать по циклу (нельзя брать поставку больше и нельзя брать меньше). При этом клетка (1-1) станет свободной (это означает, что переменную х₁₁ мы перевели в свободные переменные), а клетка (3-1) станет заполненной (это означает, что переменную х₁₃ мы перевели в базисные переменные). При этом получим следующее распределение поставок:

	В Р1	В Р2	В Р3	В Р4	Мощности поставщиков	Потенциал
Из М1		-	+		40	0
Из М2		+	-		60	-3
Из М3					50	0
Потребности	30	50	30	40
Потенциал	1	5	4	5

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

f=40 =400,

(напомним, что в предыдущем распределении было f= 410).

Выясним, будет ли данное распределение оптимальным.

Определим потенциалы строк и столбцов, полагая и пользуясь условиями (7).

, ,

Найдем оценки свободных клеток:

, , ,

,

Условию оптимальности (8) не удовлетворяет клетка (1-3). Строим замкнутый цикл и находим минимальную поставку, имеющую знак - , она будет равна 20. Перемещаем поставку по циклу. При этом получим следующее распределение поставок:

	В Р1	В Р2	В Р3	В Р4	Мощности поставщиков	Потенциал
Из М1					40	0
Из М2					60	-3
Из М3					50	0
Потребности	30	50	30	40
Потенциал	1	5	3	5

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

f=20 =380.

Определим потенциалы строк и столбцов, полагая .

,

Найдем оценки свободных клеток:

, , ,

,

Таким образом, полученное нами распределение поставок оптимальное (так как , то данное оптимальное распределение не единственно).