ai
bj
|
50
|
10
|
30
|
10
|
Потенциал
|
40
|
3
20
|
9
10
|
4
Х
|
5
10
|
U
1
|
10
|
1 10
|
8
Х
|
5 Х
|
3
Х
|
U 2
|
30
|
7
Х
|
2 Х
|
4
Х
|
U
3
|
20
|
2 20
|
4 Х
|
10 Х
|
6
Х
|
U 4
|
Потенциал
|
V 1
|
V 2
|
V 3
|
V4
|
|
Проверим план на оптимальность.
Для составления уравнений потенциалов заполним
две клетки нулями.
Найдем оценки свободных клеток
Δij = cij-
(ui + vj ) от тарифа отнимем сумму потенциалов
Δ13 = c13- (u1 + v3 )=5-(0+4)=1
Δ22 = c22.- (u2 + v2
)=8-(-2+9)=1
Δ24 = c24 - (u2 + v4
)=3-(-2-1)=6
Δ23 = c23 - (u2 + v3
)=5-(-2+4)=3
Δ31 = c31 - (u3+ v1
)=7-(-3+3)=7
Δ32 = c32 - (u3+ v2
)=2-(-3+9)=-4
Δ34 = c34 - (u3+ v4
)=4-(-3-1)=8
Δ42 = c42 - (u4+ v2
)=4-(-1+9)=-4
Δ43 = c43 - (u4+ v3
)=10-(-1+4)=7
Δ44 = c44 - (u4+ v4
)=6-(-1-1)=4
Так как имеются отрицательные оценки
план не является оптимальным.
Возьмем в качестве перспективной
клетку (3;2).
Построим на ее базе цикл.
Присвоим перспективной клетке знак
+, далее по часовой стрелке клеткам присвоим знаки, чередуя их.
Будем перемешать минимальный груз,
получивший знак минус. Этот груз равен 10. Если встречаем клетку со знаком плюс
прибавляем в нее груз 10, если со знаком минус, вычитаем этот груз. В итоге
получим следующий цикл.
После применения распределительного
метода имеем таблицу
ai
bj
|
50
|
10
|
30
|
10
|
Потенциал
|
40
|
3
20
|
9
Х
|
4
10
|
5
10
|
U
1
|
10
|
1 10
|
8
Х
|
5 Х
|
3
Х
|
U 2
|
30
|
7
Х
|
2 10
|
1 20
|
4
Х
|
U
3
|
20
|
2 20
|
4 Х
|
10 Х
|
6
Х
|
U 4
|
Потенциал
|
V 1
|
V 2
|
V4
|
|
Проверим найденный план на оптимальность.
Уравнения потенциалов имеют вид:
Δ22 = c22 - (u2 + v2
)=8-(-2+5)=5
Δ24 = c24 - (u2 + v4
)=3-(-2-1)=6
Δ23 = c23 - (u2 + v3
)=5-(-2+4)=3
Δ31 = c31 - (u3+ v1
)=7-(-3+3)=7
Δ34 = c34 - (u3+ v4
)=4-(-3-1)=8
Δ42 = c42 - (u4+ v2
)=4-(-1+5)=0
Δ43 = c43 - (u4+ v3
)=10-(-1+4)=7
Δ44 = c44 - (u4+ v4
)=6-(-1+5)=5
Таким образом, план оптимален, так
как все оценки положительны.
Нулевая оценка свидетельствует о
том, что план не является единственным.
Найдем стоимость плана
Ответ: