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