Особые случаи симплексного методаНеединственность оптимального решения (альтернативный оптимум): Решим симплексным методом задачу: F=3x1 + 3х2 à max при ограничениях: х1 + х2 <= 8
Геометрическое решение:
Оптимум в любой точке отрезка АВ. Т.к. линия уровня параллельна этому отрезку. При решении задачи симплекс-методом наличие альтернативного оптимума проявляется следующим образом: На очередном шаге получим: осн пер – х1, х2, х5; неос п - х3, х4. Выражение основных через неосн: Х1 = 5 – (2/3)Х3 – (1/3)Х4 Х2 = 3 – (1/3)Х3 + (1/3)Х4 Х5 = 9 – Х3 – Х4 Х1 = (3; 5; 0; 0; 9) – ДБР, соответствует угловой точке А (3; 5). Линейная функция F = 24 – Х3. В выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен, т.е. Х1 – оптим БР, Fмакс = 24. Однако в последнем выражении для F = 24 – Х3 отсутствует неосновная переменная Х4 (входит с нулевым к-ом), поэтому изменение этой переменной не приведет к изменению цел функции.
Вырожденность базисного решения: Решим симплексным методом задачу: F=2x1 - х2 à max при ограничениях: х1 - х2 <= 2 6х1 - 4х2 <= 14 х1, х2 >= 0 На первом шаге получим: осн пер – х3, х4, х5; неос п - х1, х2. Выражение основных через неосн: Х3 = 2 - Х1 + Х2 Х4 = 6 – 3Х1 + 2Х2 Х5 = 14 – 6Х1 + 4Х2 Х1 = (0; 0; 2; 6; 14) – допустимое БР. Линейная функция F = 2x1 - х2. Переводя Х1 в основные, получаем Х1 = min{2; 6/3; 14/6} = 2. Оценочные отношения в первых двух совпадают. Любое выбираем.
На втором шаге получим: осн пер – х1, х4, х5; неос п - х2, х3. Выражение основных через неосн: Х1 = 5 + Х2 – Х3 Х4 = 0 – Х2 + 3Х3 Х5 = 2 – 2Х2 + 6Х3 Х2 = (2; 0; 0; 0; 2) – вырожденное БР, т.к. осн переменная Х4 = 0. Линейная функция F = 4 + Х2 – 2Х3. Переводя Х2 в основные, получаем Х2 = min{¥; 0; 1} = 0, поэтому на следующем шаге изменения целевой функции не произойдет (0 * 1). Это нарушение принципа улучшения решения. Поэтому принцип – не ухудшить. Следующий шаг данного примера тоже приведет к вырожденному БР. Этот шаг, хоть и не вызвал увеличения значения цел функции, привел к новому БР. Наличие «пустых» шагов может привести к «зацикливанию» - не рассматриваем. Вывод: Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающее – любое из них. На очередном шаге получим вырожденное БР. Отсутствие конечного оптимума: Решим симплексным методом задачу: F=2x1 - 3х2 + 1à min при ограничениях: х1 + х2 >= 4
х1, х2 >= 0
Выражение основных через неосн: Х1 = 5/3 + 1/3 Х3 + 1/3 Х4 Х2 = 7/3 + 2/3 Х3 – 1/3 Х4 Х5 = 4 + Х3 – Х4 Х1 = (5/3; 7/3; 0; 0; 4) – допустимое БР. Линейная функция F = -8/3 - 4/3x3 + 4/3х4. Переводя Х3 в основные (т.к. имеет отрицательный коэффициент, а ищем мин), получаем Х3 = min{¥; ¥; ¥} = ¥, т.к. во все уравнения эта переменная входит со знаком свободного члена. Уравнения не ограничивают рост Х3, поэтому и целевая функция неограниченно убывает. Вывод: Если на каком-либо шаге получаем, что во всех уравнениях системы бесконечны оценочные отношения той переменной, которую переводим в основные, то задача не имеет конечного оптимума.
|