Контрольная работа: Математическое программирование
a2 +b1 =5;
a3 +b1 =2; a3 +b2 =3;
a4 +b2 =0; a4 +b3 =0;
Поскольку количество переменных меньше, чем уравнений, то положим: a1 =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c
a1 +b1 =0+6=6 ≤ 9; a1 +b2 =0+7=7 ≤ 8;
a2 +b2 =–1+7=6 ≤ 6; a2 +b3 =–1+7=6 ≤ 10; a2 +b4 =–1+4=3 ≤ 3;
a3 +b3 =–4+7=3 ≤ 5; a3 +b4 =–4+4=0 ≤ 7;
a4 +b1 =–7+6=–1 ≤ 0; a4 +b4 =–7+4=–3 ≤ 0;
Условие оптимальности выполняется для всех клеток, следовательно последний план является оптимальным. Его стоимость составляет 1970 у.е. Следует заметить, что потребители не дополучат 230 ед. груза.
2) Метод минимальной стоимости
Найдем опорный план методом минимальной стоимости [1, c. 142].
|
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 | ||||||
Стоимость начального плана перевозки:
z0 = 40 · 7+180 · 4+120 · 5+80 · 2+70 · 3+130 · 0+100 · 0 = 1970.
Для базисных клеток система потенциалов такая:
a1 +b3 =7; a1 +b4 =4;
a2 +b1 =5;
a3 +b1 =2; a3 +b2 =3;
a4 +b2 =0; a4 +b3 =0;
Поскольку количество переменных меньше, чем уравнений, то положим: a1 =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c
a1 +b1 =0+6=6 ≤ 9; a1 +b2 =0+7=7 ≤ 8;
a2 +b2 =–1+7=6 ≤ 6; a2 +b3 =–1+7=6 ≤ 10; a2 +b4 =–1+4=3 ≤ 3;
a3 +b3 =–4+7=3 ≤ 5; a3 +b4 =–4+4=0 ≤ 7;
a4 +b1 =–7+6=–1 ≤ 0; a4 +b4 =–7+4=–3 ≤ 0;
Условие оптимальности выполняется для всех клеток, следовательно последний план является оптимальным. Его стоимость составляет 1970 у.е. Следует заметить, что потребители не дополучат 230 ед. груза.
Также отмечаем совпадение решений двумя методами.
Ответ: 1970.
Література
1. Акулич И. Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. – 319 с.