Экономико-математическое моделирование / Контрольная работа: Математическое программирование

Контрольная работа: Математическое программирование

a1 +b2 =0+2=2 ≤ 8; a1 +b3 =0+4=4 ≤ 7;

a2 +b1 =4+9=13 > 5 [8]; a2 +b3 =4+4=8 ≤ 10; a2 +b4 =4+4=8 > 3 [5];

a3 +b1 =1+9=10 > 2 [8]; a3 +b4 =1+4=5 ≤ 7;

a4 +b1 =–4+9=5 > 0 [5]; a4 +b2 =–4+2=–2 ≤ 0;

Для клетки A2 B1 (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(200, 160, 70, 120)=70.

Переходим к следующей итерации.

B

A

 1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
130 – 90 +
2 120 5 6 10 3 –4
70 + 50 –
3 150 2 3 5 7 –7
150
4 230 0 0 0 0 –4
0 + 140 90 –
b 9 10 4 4

Стоимость 2 плана перевозки:

z2 = 130 · 9+90 · 4+70 · 5+50 · 6+150 · 3+140 · 0+90 · 0 = 2630.

Для базисных клеток система потенциалов такая:

a1 +b1 =9; a1 +b4 =4;

a2 +b1 =5; a2 +b2 =6;

a3 +b2 =3;

a4 +b3 =0; a4 +b4 =0.


Поскольку количество переменных меньше, чем уравнений, то положим: a1 =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a1 +b2 =0+10=10 > 8 [2]; a1 +b3 =0+4=4 ≤ 7;

a2 +b3 =–4+4=0 ≤ 10; a2 +b4 =–4+4=0 ≤ 3;

a3 +b1 =–7+9=2 ≤ 2; a3 +b3 =–7+4=–3 ≤ 5; a3 +b4 =–7+4=–3 ≤ 7;

a4 +b1 =–4+9=5 > 0 [5]; a4 +b2 =–4+10=6 > 0 [6];

Для клетки A4 B2 (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(50, 130, 90)=50.

Переходим к следующей итерации.

B

A

 1 2 3 4 a
200 200 140 180
1 220 9 8 7 4 0
80 – 140 +
2 120 5 6 10 3 –4
120
3 150 2 3 5 7 –1
0 + 150 –
4 230 0 0 0 0 –4
50 + 140 40 –
b 9 4 4 4

Стоимость 3 плана перевозки:

z3 = 80 · 9+140 · 4+120 · 5+150 · 3+50 · 0+140 · 0+40 · 0 = 2330.

Для базисных клеток система потенциалов такая:


a1 +b1 =9; a1 +b4 =4;

a2 +b1 =5;

К-во Просмотров: 588
Бесплатно скачать Контрольная работа: Математическое программирование