Четвертое приближение

Второе приближение.

Проверим оптимальность сформированного плана перевозок. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₃ = 4; -1 + v₃ = 4; v₃ = 5

u₂ + v₃ = 5; 5 + u₂ = 5; u₂ = 0

u₂ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₃ + v₄ = 0; -1 + v₄ = 0; v₄ = 1

Сформированный план перевозок не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;3): 0 + 5 > 2; ∆₁₃ = 0 + 5 - 2 = 3

(1;4): 0 + 1 > 0; ∆₁₄ = 0 + 1 - 0 = 1

(2;4): 0 + 1 > 0; ∆₂₄ = 0 + 1 - 0 = 1

max(3,1,1) = 3

Выбираем максимальную оценку свободной клетки (1;3): 2

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных «-», «+», «-».

Цикл приведен в таблице (1,3 → 1,1 → 3,1 → 3,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 70. Прибавляем 70 к объемам грузов, стоящих в плюсовых клетках и вычитаем 70 из Х_ij, стоящих в минусовых клетках. В результате получаем новую таблицу.

Третье приближение.

Проверим оптимальность сформированного плана перевозок. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₄ = 0; -1 + v₄ = 0; v₄ = 1

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

u₂ + v₃ = 5; 2 + u₂ = 5; u₂ = 3

u₂ + v₂ = 1; 3 + v₂ = 1; v₂ = -2

Сформированный план перевозок не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;4): 0 + 1 > 0; ∆₁₄ = 0 + 1 - 0 = 1

(2;4): 3 + 1 > 0; ∆₂₄ = 3 + 1 - 0 = 4

max(1,4) = 4

Выбираем максимальную оценку свободной клетки (2;4): 0

Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных «-», «+», «-».

Цикл приведен в таблице (2,4 → 2,3 → 1,3 → 1,1 → 3,1 → 3,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получаем новую таблицу.

Четвертое приближение.

Проверим оптимальность сформированного плана перевозок. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

u₂ + v₃ = 5; 2 + u₂ = 5; u₂ = 3

u₂ + v₂ = 1; 3 + v₂ = 1; v₂ = -2

u₂ + v₄ = 0; 3 + v₄ = 0; v₄ = -3

u₃ + v₄ = 0; -3 + u₃ = 0; u₃ = 3

u₃ + v₁ = 1; 3 + v₁ = 1; v₁ = -2

Сформированный план перевозок не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(3;3): 3 + 2 > 4; ∆₃₃ = 3 + 2 - 4 = 1

Выбираем максимальную оценку свободной клетки (3;3): 4

Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных «-», «+», «-».

Цикл приведен в таблице (3,3 → 3,4 → 2,4 → 2,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 60. Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из Х_ij, стоящих в минусовых клетках. В результате получаем новую таблицу.