Транспортная задача

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

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

 u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

u₁ + v₂ = 9; 0 + v₂ = 9; v₂ = 9

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

u₂ + v₃ = 6; 15 + u₂ = 6; u₂ = -9

u₁ + v₅ = 18; 0 + v₅ = 18; v₅ = 18

u₃ + v₅ = 29; 18 + u₃ = 29; u₃ = 11

u₃ + v₄ = 11; 11 + v₄ = 11; v₄ = 0

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

(3;1): 11 + 13 > 16; ∆₃₁ = 11 + 13 - 16 = 8

(3;2): 11 + 9 > 4; ∆₃₂ = 11 + 9 - 4 = 16

(3;3): 11 + 15 > 10; ∆₃₃ = 11 + 15 - 10 = 16

 max(8,16,16) = 16

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

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

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

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

 u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

u₁ + v₂ = 9; 0 + v₂ = 9; v₂ = 9

u₃ + v₂ = 4; 9 + u₃ = 4; u₃ = -5

u₃ + v₄ = 11; -5 + v₄ = 11; v₄ = 16

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

u₂ + v₃ = 6; 15 + u₂ = 6; u₂ = -9

u₁ + v₅ = 18; 0 + v₅ = 18; v₅ = 18

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

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

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

 Для этого  в перспективную клетку (1;4) поставим  знак «+», а в остальных вершинах  многоугольника чередующиеся знаки  «-», «+», «-». Цикл приведен в таблице.

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

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

 u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

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

u₂ + v₃ = 6; 15 + u₂ = 6; u₂ = -9

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₃ + v₄ = 11; 3 + u₃ = 11; u₃ = 8

u₃ + v₂ = 4; 8 + v₂ = 4; v₂ = -4

u₁ + v₅ = 18; 0 + v₅ = 18; v₅ = 18

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

(3;1): 8 + 13 > 16; ∆₃₁ = 8 + 13 - 16 = 5

(3;3): 8 + 15 > 10; ∆₃₃ = 8 + 15 - 10 = 13

 max(5,13) = 13

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

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

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