его как ведущей строки симплекс-таблицы позволяют получить оптимальную г-строку путем выбора переменной л:, в качестве вводимой. Таким образом становится возможным применить двойственный симплекс-метод к модифицированной задаче с искусственным ограничением.

4. Используя процедуру введения искусственного ограничения, описанную в предыдущем упражнении, решите двойственным симплекс-методом следующие задачи ЛП. Во всех задачах укажите, будет окончательное решение допустимым, недопустимым или неограниченным.

a) Максимизировать z = 2х3 при ограничениях

-я, + 2х2 - 2х3 > 8,

-дс, + х2 + х3 <4, 2хх -х2 + 4х3 < 10, х1У х2, х3>0.

b) Максимизировать z = хх - Зх2 при ограничениях

х1~х2<2, + х2> 4, 2хг-2х2>3, хг, х2>0.

c) Минимизировать z = -хх + х2 при ограничениях

х, - 4х2> 5, х,-3х2<1, 2х, - 5х2> 1, х х2 > 0.

d) Максимизировать z = 2х3 при ограничениях

-х1 + 3х2-7х3>5, -х1 + х2-х3<1, Зх, + х2 - 10х3 < 8, х х2, х3>0.

5. Решите следующую задачу ЛП тремя различными методами (используя в качестве инструмента программу TORA). Определите, какой метод будет наиболее эффективным при вычислениях.

Минимизировать z = 6х, + 7х2 + Зх3 + 5х4

при ограничениях

5x, + 6х2 - Зх3 + 4х4 > 12, х2 - 5jc3 - 6х4 > 10, 2xl + 5x2 + x3 + xi>&, х х2, х3, х4>0.

4.4.2. Обобщенный симплекс-метод

В прямом симплекс-методе (см. главу 3) начальное решение допустимо, но не оптимально. В двойственном симплекс-методе данное решение оптимально (точнее, супероптимально ), но не допустимо. Возникает естественный вопрос: можно ли начать решение задачи ЛП с неоптимального и недопустимого решения? Мы видели, что в прямом симплекс-методе при отсутствии допустимого начального решения используются искусственные переменные. В двойственном симплекс-методе при отсутствии оптимального начального решения также применяются искусственные ограничения. Хотя задача этих процедур и состоит в обеспечении автоматического выполнения вычислений, необходимо не терять из виду основную идею симплексных алгоритмов, а именно то, что оптимальное решение задачи ЛП достигается в одной из крайних (угловых) точек пространства допустимых решений. С учетом этих замечаний можно разработать симплексный алгоритм решения задач ЛП, в котором начальное решение будет и неоптимальным, и недопустимым. Следующий пример показывает, как можно обобщить симплексный алгоритм.

Пример 4.4.2

Рассмотрим задачу из упражнения 4.4.1.4, а. В качестве начальной таблицы можно принять следующую симплекс-таблицу, где представлено начальное решение (х4, х5, хв), которое не оптимально (из-за переменной х,) и не допустимо (так как xt = -8). (Заметим, что в этой таблице первое равенство умножено на -1 для того, чтобы показать недопустимость решения непосредственно в столбце Решение .)

Решение задачи ЛП без использования каких-либо искусственных переменных или ограничений может быть следующим. Сначала освобождаемся от свойства недопустимости базисного решения путем применения версии двойственного условия допустимости. В нашем примере это приведет к выбору переменной х4 в качестве исключаемой из базиса. Чтобы определить вводимую переменную, надо найти в д:4-строке строго отрицательный коэффициент, соответствующий небазисной переменной. Выбор вводимой переменной можно осуществить без удовлетворения требования оптимальности решения, так как в данном случае это не существенно (сравните с двойственным условием оптимальности). В результате получим следующую таблицу.

Решение в последней таблице допустимо, но не оптимально. Далее можно использовать прямой симплекс-метод для получения оптимального решения. В общем случае, если на очередной итерации полученное решение неопустимо, то описанная процедура повторяется до тех пор, пока не будет получено допустимое решение. Далее основное внимание уделяется оптимальности решения путем применения условия оптимальности прямого симплекс-метода.

Пример 4.4.2 показывает гибкость симплексного метода. В литературе описано большое количество вариаций симплекс-метода (например, метод одновременного решения прямой и двойственной задач, симметричный, перекрестный и мультиплексный методы), причем создается впечатление, что каждый из них существенно отличается от других, тогда как все они просматривают экстремальные точки пространства решений с различной степенью автоматизации вычислений и вычислительной эффективности.

УПРАЖНЕНИЯ 4.4.2

1. Задача ЛП из упражнения 4.4.1.4, с не имеет допустимого решения. Покажите, что это свойство задачи ЛП можно определить с помощью обобщенного симплексного алгоритма.

2. Задача ЛП из упражнения 4.4.1.4, d не имеет ограниченного решения. Покажите, что это свойство задачи ЛП можно определить с помощью обобщенного симплексного алгоритма.

4.5. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ

Анализ чувствительности оптимальных решений задач ЛП на элементарном уровне рассмотрен в разделе 2.3. В этом разделе, используя соотношения двойственности и матричное представление симплексных вычислений, мы проведем анализ чувствительности значительно глубже.

Анализ чувствительности выполняется уже после получения оптимального решения задачи ЛП. Его цель - определить, приведет ли изменение коэффициентов исходной задачи к изменению текущего оптимального решения, и если да, то как эффективно найти новое оптимальное решение (если оно существует).

В общем случае изменение коэффициентов исходной задачи может привести к одной из следующих четырех ситуаций.

Результат изменения исходной задачи

Текущее базисное решение остается оптимальным и допустимым

Текущее решение становится недопустимым

Текущее решение становится неоптимальным

Текущее решение становится неоптимальным и недопустимым

Рекомендуемые действия Никаких действий не производится

Используется двойственный симплекс-метод для восстановления допустимости решения

Используется прямой симплекс-метод для восстановления оптимальности решения

Используется обобщенный симплекс-метод для получения нового решения

Первые три ситуации рассмотрены в этом разделе. Четвертая ситуация как комбинация второй и третьей представлена в комплексной задаче 4.3.