Способ минимальной стоимости

1.Клетки с минимальной ценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем способе).

2. x_{3 2} = min {50,60} = 50

3. a ^'₃ =50-50=0, b ^'₂ = 100-50=50

4.Запрещаем строку 3.

1. Клетка с min ценой ~ (2,3)

2. x₂₃ = min {70,80} = 70

3. a₂ =70-70=0, b'₃ = 80-70=10

4. Запрещаем строку 2.

Χ	-	-
Χ			-

1. Клетка с min ценой ~ (1,1)

2. x ₁₁=min {120,60} = 60

3. a₁' =120-60 = 60, b₁' = 0

4.В первом столбце запрещать уже нечего. Текущая таблица содержит две клетки (1,2) и (1,3).

1.Выбираем клетку (1,2)

_{2 .} x ₁₂ = min {110,100} = 100

3. a₁ =110-100 = 10, b^'₁ = 0

4.Текущая таблица содержит одну клетку (1,3).

1. Выбираем последнюю клетку(1,3)

2. x₁₃ = min {10,10} = 10

3. a₁^' = b ₃ = 0

4.Таблица исчерпана. Конец.

Переходим к описанию следующего шага метода потенциалов.

ШАГ 2. Проверка текущего плана на оптимальность.

Признаком того, что текущий план перевозок является оптимальным, служит условие

ui +vj -cij ≤0

(1)

которое выполняется для всех клеток таблицы. Неизвестные здесь величины u_i и vj (называемые потенциалами) определяются из условий

ui + vj = cij

(2)

Условие (1) означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")

Так как заполненных клеток в таблице (m+n- 1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n -1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно (продолжаем работать с нашим "старым" примером и найдем потенциалы для начального плана, построенного способом МС).

Заполненные клетки Уравнения

(1,1) u₁ + v₁ =5

(1,2) u₁ + v₂ =10

(1,3) u₁ + v₃ =12

(2,3) u₂ +v₃ =4

(3,2) u₃ +v₂ =0

Положим, например, неизвестное u ₁ равным 0 (через него можно из первых трех уравнений найти v₁, v₂ и v₃). Последовательно из них находим u _2, u _3.

Этот метод можно сформулировать в виде единого правила: