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

Поскольку запасы и потребности не совпадают, имеем задачу с неправильным балансом или открытую, следовательно введем фиктивный пункт отправления с количеством 230 единиц груза.

1) Диагональный метод

Найдем опорный план диагональным методом [1, c. 140].

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

z0 = 200 · 9+20 · 8+120 · 6+60 · 3+90 · 5+50 · 0+180 · 0 = 3310.

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

a1+b1=9; a1+b2=8;

a2+b2=6;

a3+b2=3; a3+b3=5;

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

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

a1+b3=0+10=10 > 7 [3]; a1+b4=0+10=10 > 4 [6];

a2+b1=–2+9=7 > 5 [2]; a2+b3=–2+10=8 ≤ 10; a2+b4=–2+10=8 > 3 [5];

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

a4+b1=–10+9=–1 ≤ 0; a4+b2=–10+8=–2 ≤ 0;

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

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

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

z1 = 200 · 9+20 · 4+120 · 6+80 · 3+70 · 5+70 · 0+160 · 0 = 3190.

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

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

a2+b2=6;

a3+b2=3; a3+b3=5;

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

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

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;

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

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