Метод потенциалов основан на второй теореме двойственности для задачи линейного программирования для двойственной задачи.
Если переменная Xij≠0, то соответствующее решение двойственной задачи:
Xij≠0 Ui + Vj = Cij =› Ui º 0
xlk = 0 Ul + Vk < Clk Clk - Ul - Vk > 0
alk > 0, если нет, то строим новое начальное решение и т.д.
Если alk = 0, то имеет место альтернативный оптимум и выполняется еще одна операция и этот элемент выбирается за разрешающий.
Vj Ui | V1 | V2 | V3 | V4 | |||||||||
U1 | 2 | 3 | 2 | 4 | 3 | ||||||||
U2 | -1 | 4 | 5 | 1 | 3 | 1 | 2 | ||||||
U3 | -2 | 2 | 2 | 1 | 4 | 4 | 1 | 2 | |||||
U4 | -2 | 0 | -1 | 0 | 0 | 0 | -1 | 0 |
U1 + V1 = 2 U1 = 0
U1 + V2 = 3 V1 = 2
U1 + V3 = 1 V4 = 3
U1 + V4 = 3 V2 = 3
U2 + V3 = 1 U2 = -1
U2 + V4 = 2 V3 = 2
U3 + V2 = 1 U3 = -2
U4 + V1 = 0 U4 = -2
Ui + Vj = Cij
Ui = Cij - Vj
Vj = Cij – Ui, U1 º 0
Ui + Vj < Cij
Vxij* = 0
Ui + Vj < Cij
alk = Clk - Ui - Vi > 0
alk = 0
Решение не оптимальное, находим следующее решение.
(r, s) = {l; k │ min alk < 0} = (4,2)
min alk = -1
X0= | +20 | 40- | ||||
-30 | 0*+ |
Строим цикл, начиная с разрешающего элемента 0*, таким образом, чтобы в вершинах его были ненулевые элементы.
|
|
Помечаем вершины, начиная с разрешающего нуля, чередованием знаков + -.
Θ1 = min {xlk-}= min {40,30} = 30
X1= | +10 | 30- | ||||
-30 | 0*+ |
fo(x1) = 2·50 + 3·10 + 3·30 + 1·20 + 2·10 + 1·40 + 0·30 = 300
fo(x1) = fo(x0) + Θ1 (∑Cpq+ - ∑Cef-) = 330 + 30 · (2 + 0 – 3 + 0) = 300
Vj Ui | V1 | V2 | V3 | V4 | |||||||||
U1 | 2 | 3 | 2 | 4 | 3 | ||||||||
U2 | -1 | 4 | 5 | 1 | 3 | 1 | 2 | ||||||
U3 | -2 | 2 | 2 | 1 | 4 | 4 | 4 | 2 | |||||
U4 | -3 | -1 | 0 | 0 | 1 | 0 | -1 | 0 |
На каждом этапе необходимо делать проверку:
Cij = Ui + Vj – проверка.
alk = Clk – Ul - Vk
a44 = 0, то имеет место альтернативный оптимум.
Q2 = min [30-; 30-] = 0
X2*= | 40 | |||||
0- |
fo(x2*) = 2·50 + 3·40 + 1·20 + 2·10 + 1·40 + 0·30 = 300
fo(x2*) = fo(x1*) + 30*(3 + 0 – 3 – 0)
Vj Ui | V1 | V2 | V3 | V4 | |||||||||
U1 | 2 | 3 | 2 | 4 | 3 | ||||||||
U2 | -1 | 4 | 5 | 1 | 3 | 1 | 2 | ||||||
U3 | -2 | 2 | 2 | 1 | 4 | 4 | 1 | 2 | |||||
U4 | -3 | 1 | 0 | 0 | 1 | 0 | 0 |
Ответ: fo(x*) = 300
X2*= | ||||||
Для нахождения значимого нуля выбирается минимальное из оставшихся Cij, если при этом нельзя найти потенциалы, то значимый ноль выбирается таким образом, чтобы можно было найти потенциалы.
|
|