|
Минимальная стоимость перевозок (6) в клетке а2b1 - отправляем весь груз из а2 потребителю b1 и строку а2 исключаем из дальнейшего рассмотрения.
Следующий минимум (7) в клетке а4b4 - отправляем весь груз из а4 потребителю b4 и строку а4 исключаем из дальнейшего рассмотрения.
Следующий минимум (10) в клетке а3b1 - закрываем потребность b1 поставкой из а3 и столбец b1 исключаем из дальнейшего рассмотрения.
Следующий минимум (12) в клетке а1b2 - весь груз из а1 отправляем в b2 и строку а1 исключаем из дальнейшего рассмотрения.
Следующий минимум (19) в клетке а3b2 - закрываем потребность b2 поставкой из а3 и столбец b2 исключаем из дальнейшего рассмотрения.
Поставкой остатка груза из а3 закрываем потребности b3 и b4.
Опорный план составлен.
Стоимость перевозок по этому плану:
Z1 = 105·12 + 70∙6 + 25∙10 + 55∙19 + 135∙22 + 25·27 + 85·7 = 7215 д.е.
Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:
Ui = Cij - Vj; Vj = Cij - Ui;
Определяем характеристики клеток, оставшихся свободными по формуле:
Eij = Cij - (Vj + Ui) (вписаны в левый нижний угол).
Среди характеристик свободных клеток есть одна отрицательная (Е22 = -4), значит полученный план не оптимален.
Строим для клетки а2b , цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2).
|
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |
|
|
1 |
2 |
3 |
4 |
| |
|
|
95 |
160 |
135 |
110 |
| |
1 |
105 |
17
10 |
12 105 |
17
-2 |
21
-3 |
U1 = 0 | |
2 |
70 |
6 15 |
11 55 |
20
2 |
28
5 |
U2 = -1 | |
3 |
240 |
10 80 |
19
4 |
22 135 |
27 25 |
U3 = 3 | |
4 |
85 |
18
28 |
14
19 |
23
21 |
7 85 |
U4 = -17 | |
Vj |
V1 = 7 |
V2 = 12 |
V3 = 19 |
V4 = 24 |
№2 |
Очевидно, что полученный план не является оптимальным, т.к. среди характеристик свободных клеток есть отрицательные.
Далее без комментариев повторяем итерацию с перемещением перевозки (15) по циклу в клетку a1b4 с отрицательной характеристикой (-3). Получаем третий план (табл. №3).
|