- •3. Методы получения оптимальных решений злп
- •3.1. Графический метод решения злп
- •3.1.1. Алгоритм решения графическим методом
- •3.1.2. Особые случаи решения злп графическим методом
- •3.2. Симплекс-метод решения злп
- •3.2.1. Аналитический симплекс-метод
- •3.2.2. Табличный симплекс-метод
- •Исходная таблица для симплекс-метод.
- •Исходная таблица для симплекс-метода
- •Итоговая таблица с оптимальным решением
- •3.2.3. Метод искусственного базиса (м-метод)
- •Исходная таблица для решения задачи м-методом
- •Промежуточный результат м-метода
- •Итоговая симплекс-таблица
- •3.2.4. Особые случаи решения злп симплекс-методом
- •Выбор разрешающей строки
- •Исходная таблица с базисом х3, х4
- •Решение с базисом х2, х3
3. Методы получения оптимальных решений злп
3.1. Графический метод решения злп
3.1.1. Алгоритм решения графическим методом
З
X
а) б)
Рис. 3.1. Выпуклое (а) и невыпуклое (б) множества
Для выпуклых множеств, справедливо утверждение, что пересечение выпуклых множеств есть выпуклое множество. Если X1 (x11, x21), X2 (x12, x22), то для выпуклого множества справедливо:
Установлено, что выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек. В теории линейного программирования доказывается, что оптимальный план, если он существует, соответствует координатам одной из угловых точек выпуклой области определения D.
Исходя из этого, и учитывая, что любая полуплоскость есть выпуклое множество, алгоритм графического метода решения ЗЛП для двух переменных x1 и х2 состоит в следующем:
-
Записывается ЗЛП для двух переменных x1 и х2.
(3.1)
(3.2)
(3.1)
. (3.3)
-
По ограничениям (3.2) и (3.3) строится множество всех допустимых решений D.
-
По целевой функции определяем градиент направления перемещения линии уровня = с1 х1 + с2 х2, которая перпендикулярна вектору :
-
Перемещаем линию уровня параллельно самой себе в направлении вектора . Первая точка встречи линии уровня с областью D соответствует точке min, а последняя – точке max. Если D Ø, то решений нет. Если линия уровня параллельна одной из сторон области допустимых решений D, то экстремум достигается во всех точках соответствующей стороны.
Пример. 3.1. Задача о диете и смесях.
Область ограничения представляет собой неограниченную многоугольную область. Её границы представлены уравнениями прямых:
Рис. 3.2. Графическое решение задачи о диете и смесях
Определяем
α = 4х1 + 6х2,
и
.
Перемещаем в направлении вектора и определяем, что точкой входа в область допустимых решений является точка В, координаты которой определяем из условия:
Откуда х1В = 2; х2В = 3
Пример 3.2. Задача об использовании ресурсов
Рис. 3.3. Графическое решение задачи об использовании ресурсов
С (312,5; 300).
Пример 3.3. Задача о банке
Рис. 3.4. Графическое решение задачи о банке
x1c = 70; x2c = 30.
.
Если r1=18 %, r2=12 %, то
3.1.2. Особые случаи решения злп графическим методом
-
max f (x1, x2)= 3x1 + 5x2,
x1,2 0.
Рис. 3.5 Случай отсутствия области решений D
2) max f (x1, x2)= 3x1 + 2x2,
x1,2 0.
Рис. 3.6 Значение целевой функции не ограниченно возрастает
3) max f (x1, x2)= 8x1 + 10x2,
x1 0.
Рис. 3.7. Случай неединственности оптимального решения
Неединственность решения: множество точек отрезка ВС (ВС׀׀α).