- •Скласти двоїсту задачу та визначити методи її розв’язання.
- •Привести злп до канонічної форми.
- •Знайти оптимальне рішення злп на першому етапі двохетапного симплекс-метода.
- •Визначити всі методи розв’язання злп. Знайти оптимальне рішення одним з них.
- •Метод Гомори
- •Розв’язати злп графічним методом.
- •Скласти двоїсту задачу та знайти її рішення.
-
Розв’язати злп графічним методом.
min Z=4X1 + Х2
при 2X1 + Х28
6Х1 + 4Х2 10
X1,X2 0
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Границы области допустимых решений
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений. Рассмотрим целевую функцию задачи F = 4x1+x2 → min. Построим прямую, отвечающую значению функции F = 0: F = 4x1+x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (4; 1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией. Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (5), то ее координаты удовлетворяют уравнениям этих прямых: 2x1+x2=8 x1=0 Решив систему уравнений, получим: x1 = 0, x2 = 8 Откуда найдем минимальное значение целевой функции: F(X) = 4*0 + 1*8 = 8
-
Скласти двоїсту задачу та знайти її рішення.
min Z=5X1+10Х2
при X1 + Х2 10
4Х1 + 3Х2 12
X1, Х2 0,
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Оптимальный план можно записать так: x1 = 10 F(X) = 5•10 = 50 Оптимальный план двойственной задачи равен: y1 = 5 y2 = 0 Z(Y) = 10*5+12*0 = 50