матан 5

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

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

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

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

max(3,2,4) = 4

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

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

	1	2	3	4	5	Запасы
1	1	6	9	3[100]	4[100]	200
2	3[200][-]	2[200][+]	2	4	5	400
3	4	5[200][-]	4[200][+]	7	6[200]	600
4	1[+]	4	3[200][-]	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0	0[200]	200
Потребности	200	400	400	300	500

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

	1	2	3	4	5	Запасы
1	1	6	9	3[100]	4[100]	200
2	3	2[400]	2	4	5	400
3	4	5[0]	4[400]	7	6[200]	600
4	1[200]	4	3[0]	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0	0[200]	200
Потребности	200	400	400	300	500

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

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

u₅ + v₄ = 1; 3 + u₅ = 1; u₅ = -2

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

u₃ + v₅ = 6; 4 + u₃ = 6; u₃ = 2

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

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

u₃ + v₃ = 4; 2 + v₃ = 4; v₃ = 2

u₄ + v₃ = 3; 2 + u₄ = 3; u₄ = 1

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

u₆ + v₅ = 0; 4 + u₆ = 0; u₆ = -4

	v1=0	v2=3	v3=2	v4=3	v5=4
u1=0	1	6	9	3[100]	4[100]
u2=-1	3	2[400]	2	4	5
u3=2	4	5[0]	4[400]	7	6[200]
u4=1	1[200]	4	3[0]	9	8
u5=-2	7	9	7	1[200]	9
u6=-4	0	0	0	0	0[200]

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

Минимальные затраты составят:

F(x) = 3*100 + 4*100 + 2*400 + 4*400 + 6*200 + 1*200 + 1*200 + 0*200 = 4700

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 4-й магазин (100), в 5-й магазин (100)

Из 2-го склада необходимо весь груз направить в 2-й магазин

Из 3-го склада необходимо груз направить в 3-й магазин (400), в 5-й магазин (200)

Из 4-го склада необходимо весь груз направить в 1-й магазин

Из 5-го склада необходимо весь груз направить в 4-й магазин

Потребность 5-го магазина остается неудовлетворенной на 200 ед.

Задача имеет множество оптимальных планов, поскольку оценка для (3;2),(4;3) равна 0.