2014-02-04
347
| ПН | В1 | В2 | В3 | В4 | В5 | Запасы | αi | ||||||
| ПО | |||||||||||||
| А1 | |||||||||||||
| А2 | -2 | ||||||||||||
| А3 | -1 | ||||||||||||
| А4 | |||||||||||||
| Заявки | |||||||||||||
| βj | |||||||||||||
Полагаем α1 = 0.
В строке А1 две базисных клетки А1В1 и А1В2, которые связывают потенциал α1 с потенциалами β1 и β2. Определим эти потенциалы:
β1 = c11 – α1 =10 - 0 = 10,
β2 = c12 – α1 = 8 - 0 = 8.
Теперь поочерёдно просматриваем столбцы В1 и В2, для которых потенциалы уже определены. В столбце В1 нет больше базисных клеток, кроме А1В1. В столбце В2 имеется базисная клетка А2В2, которая связывает потенциал α2 с потенциалом β2: α2 = c22 – β2 = 6 – 8 = -2.
В строке А2 базисная клетка А2В3 связывает потенциалы α2 и β3: β3 = c23 – α2 = 4 – (-2) = 6.
|
|
|
Потенциал α3 определяем с помощью клетки А3В3: α3 = c33 – β3 = 5 – 6 = -1.
Далее определяем потенциалы β4, β5 и α4: β4 = c34 – α3 = 4 – (-1) = 5,
β5 = c35 – α3 = 3 – (-1) = 4,
α4 = c45 – β5 = 8 – 4 = 4.
| ПН | В1 | В2 | В3 | В4 | В5 | Запасы | αi | ||||||
| ПО | |||||||||||||
| А1 | |||||||||||||
| А2 | -2 | ||||||||||||
| А3 | -1 | ||||||||||||
| А4 | |||||||||||||
| Заявки | |||||||||||||
| βj | |||||||||||||
Для каждой свободной клетки суммируем потенциалы, на пересечении которых стоит эта клетка. Сумму потенциалов записываем в левый нижний угол клетки.
Сравниваем сумму со стоимостью cij, стоящей в этой клетке.
Для строки А 1:
6 < 9, 5 < 6, 4 < 5.
Для строки А 2:
8 > 5!, 3 ≤ 3, 2 < 8.
Для строки А 3:
9 ≤ 9, 7 ≤ 7.
Для строки А 4: 14 ≤ 14, 12 > 10!, 10 > 8!, 9 > 8!.
Таким образом, имеются четыре клетки, в которых нарушено условие оптимальности.
Перемещение грузов по циклу осуществляется для той свободной клетки, для которой отрицательная γij больше по модулю.
| ПН | В1 | В2 | В3 | В4 | В5 | Запасы | αi | ||||||
| ПО | |||||||||||||
| А1 | 
| ||||||||||||
| А2 | -2 | ||||||||||||
| А3 | -1 | ||||||||||||
| А4 | |||||||||||||
| Заявки | |||||||||||||
| βj | |||||||||||||
γij = cij - (αi + βj)
|
|
|
γ21 = 5 – 8 = -3
γ42 = 10–12= -2
γ43 = 8–10= -2
γ44 = 8 – 9 = -1
Нужно сделать базисной клетку А2В1.
В результате переноса по циклу 13 ед. груза получен новый опорный невырожденный план, который снова подлежит проверке на оптимальность.
| ПН | В1 | В2 | В3 | В4 | В5 | Запасы | αi | ||||||
| ПО | |||||||||||||
| А1 | |||||||||||||
| А2 | -5 | ||||||||||||
 19
|  3
| ||||||||||||
| А3 |  5
| -4 | |||||||||||
| А4 | 
|  8
| |||||||||||
| Заявки | |||||||||||||
| βj | |||||||||||||
Для этого строится новая система потенциалов.
| ПН |  В1
| В2 | В3 | В4 | В5 | Запасы | αi | ||||||
| ПО | |||||||||||||
| А1 |  10
| ||||||||||||
| А2 | 
| -5 | |||||||||||
| А3 |  7
| -4 | |||||||||||
| А4 | -1 | ||||||||||||
| Заявки | |||||||||||||
| βj | |||||||||||||
| ПН | В1 | В2 | В3 | В4 | В5 | Запасы | αi | ||||||
| ПО | |||||||||||||
| А1 | |||||||||||||
| А2 | -3 | ||||||||||||
| А3 | -2 | ||||||||||||
| А4 | |||||||||||||
| Заявки | |||||||||||||
| βj | |||||||||||||
План является оптимальным.
L = 21∙8 + 4∙6 + 17∙5 +
+15∙4 + 6∙5 + 10∙4 +
+24∙3 + 20∙8 = 639 (ден.ед.)
