Прикладная математика 2 (стр. 4 из 10)
Обозначим через m
) вектор симплексных множителей или потенциалов. Тогда 
.Один из потенциалов можно выбрать произвольно, так как в системе (1) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток
. В данном случае получаем:D11 = 0, p1 + q1 - c11 = 0, q1 = 2
D14 = 0, p1 + q4 - c14 = 0, q4 = 4
D34 = 0, p3 + q4 – c34 = 0, p3 = -1
D33 = 0, p3 + q3 – c33 = 0, q3= 4
D21 = 0, p2 + q1 – c21 = 0, p2 = 2
D22 = 0, p2 + q2 – c22 = 0, q2 = -1
D44 = 0, p4 + q4 – c44 = 0, p4=-4
Теперь по формуле
вычисляем оценки всех свободных клеток:D12 = p1 + q2 – c12 = 0-1-3=-4
D13 = p1 + q3 – c13 = 0+4-6 =-2
D23 = p2 + q3 – c23 = 2+4-5 = 1 - max
D24 = p2 + q4 – c24 = 2+4-7 = -1
D31 = p3 + q1 - c31 = -1+2-5 = -4
D32 = p3 + q2 – c32 = -1-1-2 = -4
D41 = p4 + q1 – c41 = -4+2-0 = -2
D42 = p4 + q2 – c42 = -4-1-0 = -5
D43 = p4 + q3 – c43 = -4-4-0 = -8
Находим наибольшую положительную оценку max ( 
) = 1 = D23
Для найденной свободной клетки 23 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках.
Это будет 23-21-11-14-34-33-23:
| 30 | 5 | 30+  | 5- | 30 | 5 | |
| 0 | * |  | 0- | | | 0 |
| 44 | 36 | 44- | 36+ | 44 | 36 |
min =0 | потреб произв | b1=30 | b2=55 | b3=44 | b4=42 | |||||
| a1=35 | 30 | 2 | 3 | 6 | 5 | 4 | p1=0 | ||
| a2=55 | 4 | 55 | 1 | 0 | 5 | 7 | p2=1 | ||
| a3=80 | 5 | 2 | 44 | 3 | 36 | 3 | p3=-1 | ||
| a4=1 | 0 | 0 | 0 | 1 | 0 | p4=-4 | |||
| q1=2 | q2=0 | q3=4 | q4=4 | ||||||
D14 = 0, p1 + q4 - c14 = 0, q4=4
D34 = 0, p3 + q4 – c34 = 0, p3 = -1
D33 = 0, p3 + q3 – c33 = 0, q3= 4
D23 = 0, p2 + q3– c23 = 0, p2 = 1
D22 = 0, p2 + q2 – c22 = 0, q2 = 0
D44 = 0, p4 + q4 – c44 = 0, p4=-4
Теперь по формуле
вычисляем оценки всех свободных клеток:D12 = p1 + q2 – c12 = 0-3=-3
D13 = p1 + q3 – c13 = 0+4-6 =-2
D21 = p2 + q3 – c23 = 1+2-4 = -1
D24 = p2 + q4 – c24 = 1+4-7=-2
D31 = p3 + q1 - c31 = -1+2-5 = -4
D32 = p3 + q2 – c32 = -1+0-2=-3
D41 = p4 + q1 – c41 = -4+2=-2
D42 = p4 + q2 – c42 = -4+0=-4
D43 = p4 + q3 – c43 = -4+4-0 = 0
Итак,
, при 
Таким образом, пришли к оптимальному решениюОбщая стоимость перевозок:
денежных единиц.Для проверки полученного результата теперь решим задачу методом северо-западного угла.
Метод Северо-западного угла
| потреб произв | b1=30 | b2=55 | b3=44 | b4=42 | |||||
| a1=35 |   30 | 2 |  5 | 3 | 6 | 4 | p1=0 | ||
| a2=55 | 4 |  50 | 1 |  5 | 5 | 7 | p2=-2 | ||
| a3=80 |  * | 5 | 2 | 39 | 3 | 41 | 3 | p3=-4 | |
| a4=1 | 0 | 0 | 0 | 1 | 0 | p4=-7 | |||
| q1=2 | q2=3 | q3=7 | q4=7 | ||||||
денежных единиц | D11 = 0, p1 + q1 - c11 = 0, q1 = 2D12 = 0, p1 + q2 - c12 = 0, q2 =-3D22 = 0, p2 + q2 – c22 = 0, p2 = -2D33 = 0, p3 + q3 – c33 = 0, q3= 7D34 = 0, p3 + q4 – c34 = 0, q4 =7D44 = 0, p4 + q4 – c44 = 0, p4=-7 | Теперь по формуле вычисляем оценки всех свободных клеток:D13 = p1 + q3 – c13 = 0+7-6=1D14 = p1 + q4 – c14 = 0+7-4=3D21 = p2 + q1 – c21 = -2+2-1 =-1D24 = p2 + q4 – c24 = -2+7-7 = -2D31 = p3 + q1 - c31 = -4+2-5=7 ( max)D32 = p3 + q2 – c32 = -4+3-2=-3D41 = p4 + q1 – c41 = -7+2-0=-5D42 = p4 + q2 – c42 = -7+3=-4D43 = p4 + q3 – c43 = -7+7=0 |
Находим наибольшую положительную оценку max ( ) = 7 = D31
Для найденной свободной клетки 31 строим цикл пересчета:
| 30 | 5 | 30- | 5+ | 35 | |||
| 50 | 5 | | 50- | 5+ | | 20 | 35 |
| * | 39 | | 39- | 30 | 9 |
min =3