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

Запишем условие задачи в экономическом виде на основании таблицы, где заданы пункты отправления и назначения, запасы и потребности [1, c. 135].

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

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

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

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

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

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

a₁ +b₁ =9; a₁ +b₂ =8;

a₂ +b₂ =6;

a₃ +b₂ =3; a₃ +b₃ =5;

a₄ +b₃ =0; a₄ +b₄ =0.

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

a₁ +b₃ =0+10=10 > 7 [3]; a₁ +b₄ =0+10=10 > 4 [6];

a₂ +b₁ =–2+9=7 > 5 [2]; a₂ +b₃ =–2+10=8 ≤ 10; a₂ +b₄ =–2+10=8 > 3 [5];

a₃ +b₁ =–5+9=4 > 2 [2]; a₃ +b₄ =–5+10=5 ≤ 7;

a₄ +b₁ =–10+9=–1 ≤ 0; a₄ +b₂ =–10+8=–2 ≤ 0;

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

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

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

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

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

a₁ +b₁ =9; a₁ +b₄ =4;

a₂ +b₂ =6;

a₃ +b₂ =3; a₃ +b₃ =5;

a₄ +b₃ =0; a₄ +b₄ =0.