4.4.2. Обобщенный симплекс-метод
В прямом симплекс-методе (см. главу 3) начальное решение допустимо, но не оптимально. В двойственном симплекс-методе данное решение оптимально (точнее, "супероптимально"), но не допустимо. Возникает естественный вопрос: можно ли начать решение задачи ЛП с неоптимального и недопустимого решения? Мы видели, что в прямом симплекс-методе при отсутствии допустимого начального решения используются искусственные переменные. В двойственном симплекс-методе при отсутствии оптимального начального решения также применяются искусственные ограничения. Хотя задача этих процедур и состоит в обеспечении автоматического выполнения вычислений, необходимо не терять из виду основную идею симплексных алгоритмов, а именно то, что оптимальное решение задачи ЛП достигается в одной из крайних (угловых) точек пространства допустимых решений. С учетом этих замечаний можно разработать симплексный алгоритм решения задач ЛП, в котором начальное решение будет и неоптимальным, и недопустимым. Следующий пример показывает, как можно обобщить симплексный алгоритм.
Пример 4.4.2
Рассмотрим задачу из упражнения 4.4.1.4, а. В качестве начальной таблицы можно принять следующую симплекс-таблицу, где представлено начальное решение (х4, х5, хв), которое не оптимально (из-за переменной х,) и не допустимо (так как xt = -8). (Заметим, что в этой таблице первое равенство умножено на -1 для того, чтобы показать недопустимость решения непосредственно в столбце "Решение".)
Решение задачи ЛП без использования каких-либо искусственных переменных или ограничений может быть следующим. Сначала освобождаемся от свойства недопустимости базисного решения путем применения версии двойственного условия допустимости. В нашем примере это приведет к выбору переменной х4 в качестве исключаемой из базиса. Чтобы определить вводимую переменную, надо найти в д:4-строке строго отрицательный коэффициент, соответствующий небазисной переменной. Выбор вводимой переменной можно осуществить без удовлетворения требования оптимальности решения, так как в данном случае это не существенно (сравните с двойственным условием оптимальности). В результате получим следующую таблицу.
Базис | | | | | | | Решение |
| | | | | | | |
| -1/2 | | | -1/2 | | | |
| -1/2 | | | | | | |
| | | | -1/2 | | | |
Решение в последней таблице допустимо, но не оптимально. Далее можно использовать прямой симплекс-метод для получения оптимального решения. В общем случае, если на очередной итерации полученное решение неопустимо, то описанная процедура повторяется до тех пор, пока не будет получено допустимое решение. Далее основное внимание уделяется оптимальности решения путем применения условия оптимальности прямого симплекс-метода.
Пример 4.4.2 показывает гибкость симплексного метода. В литературе описано большое количество вариаций симплекс-метода (например, метод одновременного решения прямой и двойственной задач, симметричный, перекрестный и мультиплексный методы), причем создается впечатление, что каждый из них существенно отличается от других, тогда как все они просматривают экстремальные точки пространства решений с различной степенью автоматизации вычислений и вычислительной эффективности.
УПРАЖНЕНИЯ 4.4.2
1. Задача ЛП из упражнения 4.4.1.4, с не имеет допустимого решения. Покажите, что это свойство задачи ЛП можно определить с помощью обобщенного симплексного алгоритма.
2. Задача ЛП из упражнения 4.4.1.4, d не имеет ограниченного решения. Покажите, что это свойство задачи ЛП можно определить с помощью обобщенного симплексного алгоритма.
4.5. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ
Анализ чувствительности оптимальных решений задач ЛП на элементарном уровне рассмотрен в разделе 2.3. В этом разделе, используя соотношения двойственности и матричное представление симплексных вычислений, мы проведем анализ чувствительности значительно глубже.
Анализ чувствительности выполняется уже после получения оптимального решения задачи ЛП. Его цель - определить, приведет ли изменение коэффициентов исходной задачи к изменению текущего оптимального решения, и если да, то как эффективно найти новое оптимальное решение (если оно существует).
В общем случае изменение коэффициентов исходной задачи может привести к одной из следующих четырех ситуаций.
Результат изменения исходной задачи
Текущее базисное решение остается оптимальным и допустимым
Текущее решение становится недопустимым
Текущее решение становится неоптимальным
Текущее решение становится неоптимальным и недопустимым
Рекомендуемые действия Никаких действий не производится
Используется двойственный симплекс-метод для восстановления допустимости решения
Используется прямой симплекс-метод для восстановления оптимальности решения
Используется обобщенный симплекс-метод для получения нового решения
Первые три ситуации рассмотрены в этом разделе. Четвертая ситуация как комбинация второй и третьей представлена в комплексной задаче 4.3.
Для объяснения различных процедур анализа чувствительности используем модель фабрики игрушек TOYCO из примера 4.3.2. Напомним, что фабрика TOYCO собирает три вида детских игрушек: модели поездов, грузовиков и легковых автомобилей. Сборка модели каждого вида требует последовательного применения трех операций. В задаче необходимо определить объемы производства каждого вида игрушек, максимизирующие общий доход. Для удобства изложения материала повторим формулировки прямой и двойственной задач.
Прямая задача
Двойственная задача Минимизировать w = 430yi + 460у2 + 420уз при ограничениях
У\ + Зу2 + уз > 3,
2yi + 4у3 > 2,
У: + 2у2 > 5,
У1.У2, Уз 5 0.
Максимизировать z= 3xi + 2х2 + 5хз
при ограничениях
xi + 2x2 + х3 < 430 (операция 1), 3xi + 2х3 < 460 (операция 2), xi + 4х2 < 420 (операция 3), Хь х2, х3> 0.
Оптимальное решение
xi = 0, х2 = 100, х3 = 230, z = 1350 долл.
Оптимальное решение у, = 1, у2 = 2, уз = 0, w = 1350 долл.
Приведем симплекс-таблицу, содержащую оптимальное решение прямой задачи.
4.5.1. Изменения, влияющие на допустимость решения
К недопустимости текущего оптимального решения может привести, во-первых, изменение правых частей ограничений и, во-вторых, введение в множество ограничений задачи нового ограничения. В любом случае недопустимость решения проявится в том, что по крайней мере один элемент в правой части ограничений в оптимальной симплекс-таблице (столбец "Решение") станет отрицательным, т.е. одна или несколько базисных переменных примут отрицательные значения.
Изменение правых частей ограничений. Изменение правых частей ограничений исходной задачи требует повторных вычислений правых частей ограничений в симплекс-таблице, для чего используется формула 1 из раздела 4.2.4.
Обратная матрица ГНовый столбец правых из симплекс-таблицы на /-й итерации
Новый столбец правых частей ограничений в симплекс-таблице на i-й итерации
частей ограничении исходной задачи
Напомним, что в столбце правых частей ограничений симплекс-таблицы (столбец "Решение") приводятся значения базисных переменных. В следующем примере показано применение приведенной формулы.