1 случай. Область допустимых решений пуста и ЗЛП решений не имеет.
Пример. Система ограничений имеет вид:
х1 + 2х2 = -10
Х1 | 0 | -10 |
Х2 | -5 | 0 |
2 случай. ОДР – незамкнутый многоугольник в направлении оптимизации целевой функции. Задача ЛП не имеет решений.
3 случай. Решений бесконечно много. Если прямая, соответствующая целевой функции (линия уровня), окажется параллельной одной из сторон многоугольника при его покидании, тогда любая точка этой стороны соответствует оптимальному решению.
Основы симплекс-метода,
Процедуры решения с естественным и искусственным базисом
Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод.
Примечание. Поясним названия метода. В геометрии есть понятие «симплекс». Симплексом тела в n-мерном пространстве называют совокупность п +1 его вершин.
Для прямой п =1, симплекс – две вершины отрезка.
Для плоскости п = 2, симплекс – три вершины треугольника.
|
|
Для 3-х мерного пространства п = 3, симплекс – четыре вершины тетраэдра.
А идея симплекс-метода – перебор вершин по специальному алгоритму, который обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается.
Симплекс-метод состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).