Контрольная работа: Математическое программирование
a4 +b2 =0; a4 +b3 =0; a4 +b4 =0.
Поскольку количество переменных меньше, чем уравнений, то положим: a1 =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c
a1 +b2 =0+4=4 ≤ 8; a1 +b3 =0+4=4 ≤ 7;
a2 +b2 =–4+4=0 ≤ 6; a2 +b3 =–4+4=0 ≤ 10; a2 +b4 =–4+4=0 ≤ 3;
a3 +b1 =–1+9=8 > 2 [6]; a3 +b3 =–1+4=3 ≤ 5; a3 +b4 =–1+4=3 ≤ 7;
a4 +b1 =–4+9=5 > 0 [5];
Для клетки A3 B1 (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(80, 40, 150)=40.
Переходим к следующей итерации.
|
B A | 1 | 2 | 3 | 4 | a | |||||
| 200 | 200 | 140 | 180 | |||||||
| 1 | 220 | 9 | 8 | 7 | 4 | 0 | ||||
| 40 | – | 0 | + | 180 | ||||||
| 2 | 120 | 5 | 6 | 10 | 3 | –4 | ||||
| 120 | ||||||||||
| 3 | 150 | 2 | 3 | 5 | 7 | –7 | ||||
| 40 | + | 110 | – | |||||||
| 4 | 230 | 0 | 0 | 0 | 0 | –10 | ||||
| 90 | + | 140 | – | |||||||
| b | 9 | 10 | 10 | 4 | ||||||
Стоимость 4 плана перевозки:
z4 = 40 · 9+180 · 4+120 · 5+40 · 2+110 · 3+90 · 0+140 · 0 = 2090.
Для базисных клеток система потенциалов такая:
a1 +b1 =9; a1 +b4 =4;
a2 +b1 =5;
a3 +b1 =2; a3 +b2 =3;
a4 +b2 =0; a4 +b3 =0;
Поскольку количество переменных меньше, чем уравнений, то положим: a1 =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c
a1 +b2 =0+10=10 > 8 [2]; a1 +b3 =0+10=10 > 7 [3];
a2 +b2 =–4+10=6 ≤ 6; a2 +b3 =–4+10=6 ≤ 10; a2 +b4 =–4+4=0 ≤ 3;
a3 +b3 =–7+10=3 ≤ 5; a3 +b4 =–7+4=–3 ≤ 7;
a4 +b1 =–10+9=–1 ≤ 0; a4 +b4 =–10+4=–6 ≤ 0;
Для клетки A1 B3 (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(40, 110, 140)=40.
Переходим к следующей итерации.
|
B A | 1 | 2 | 3 | 4 | a | |||||
| 200 | 200 | 140 | 180 | |||||||
| 1 | 220 | 9 | 8 | 7 | 4 | 0 | ||||
| 40 | 180 | |||||||||
| 2 | 120 | 5 | 6 | 10 | 3 | –1 | ||||
| 120 | ||||||||||
| 3 | 150 | 2 | 3 | 5 | 7 | –4 | ||||
| 80 | 70 | |||||||||
| 4 | 230 | 0 | 0 | 0 | 0 | –7 | ||||
| 130 | 100 | |||||||||
| b | 6 | 7 | 7 | 4 | ||||||
Стоимость 5 плана перевозки:
z5 = 40 · 7+180 · 4+120 · 5+80 · 2+70 · 3+130 · 0+100 · 0 = 1970.
Для базисных клеток система потенциалов такая: