Математическое программирование

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

Стоимость 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];

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

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

Стоимость 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;

a3+b2=3;

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];

Для клетки A3B1 (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(80, 40, 150)=40.

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

 Скачать реферат