Контрольная работа: Линейное программирование

4

10

9

8

-1

40

6

3

3

1

40

1

70

2

20

4

1

50

5

4

v_j

6

3

5

2

Исследуем этот план перевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяют уравнениям: v_j = c_{ij +} u_i .

Пусть u₁ = 0; по клетке (1; 2) находим v₂ = 3; по клетке (1; 4) находим v₄ = 2; по клетке (2; 2) находим u₂ = -1; по клетке (2; 1) находим v₁ = 6; по клетке (3; 4) находим u₃ = 1; по клетке (4; 1) находим u₄ = 4; по клетке (4; 3) находим v₃ = 5.

Для всех клеток матрицы перевозок найдем оценки клеток d_ij = (u_i + c_ij ) - v_j :