|
Т.о. получен опорный план с ценой: Z1 = 6660 ден. ед.
Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:
Ui = Cij - Vj; Vj = Cij - Ui;
Определяем характеристики клеток, оставшихся свободными по формуле:
Eij = Cij - (Vj + Ui) (вписаны в правый нижний угол).
|
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |
|
|
1 |
2 |
3 |
4 |
5 |
| |
|
|
95 |
135 |
135 |
110 |
25 |
| |
1 |
105 |
17
14 |
12 55 |
17
2 |
21 25 |
0 25 |
U1 = 0 | |
2 |
70 |
6
4 |
11 70 |
20
6 |
28 8 |
0 1 |
U2 = -1 | |
3 |
240 |
10 95 |
19 10 |
22 135 |
27
-1 |
0
-7 |
U3 = 7 | |
4 |
85 |
18
27 |
14
16 |
23
20 |
7 85 |
0 14 |
U4 = -14 | |
Vj |
V1 = 3 |
V2 = 12 |
V3 = 15 |
V4 = 21 |
V5 = 0 |
№1 |
Среди характеристик свободных клеток есть отрицательные, значит полученный план не оптимален. По аналогии производим итерации по перемещению груза в клетки с отрицательными характеристиками.
Второй план (табл. №2) с ценой Z2 = 6590 д.е.
Таблица |
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |
|
|
1 |
2 |
3 |
4 |
5 |
| |
|
|
95 |
135 |
135 |
110 |
25 |
| |
1 |
105 |
17
7 |
12 65 |
17
5 |
21 25 |
0 15 |
U1 = 0 | |
2 |
70 |
6
3 |
11 70 |
20
1 |
28 8 |
0 1 |
U2 = -1 | |
3 |
240 |
10 95 |
19
21 |
22 135 |
27
6 |
0 10 |
U3 = 0 | |
4 |
85 |
18
22 |
14
16 |
23
15 |
7 85 |
0 14 |
U4 = -14 | |
Vj |
V1 = 10 |
V2 = 12 |
V3 = 22 |
V4 = 21 |
V5 = 0 |
№2 |
|