Simplex

Этап 1 1. Введем искусственные переменные в ограничения типа “≥” и “=”. В нашей

задаче это ограничения (12.2) и (12.4). Назовем искусственные переменные R1 и R2

r = R1 + R2 = 2 + x1 -2x2 +1s1 +1s3

Перепишем целевую функцию в виде:

r- 1x1 + 2x2 -1s1 -1s3 = 2

3.Построим начальную таблицу двухэтапного симплекс-метода.

Согласно условию оптимальности вводим в базис переменную x2 . На данном этапе невозможно однозначно определить переменную, которою необходимо выводить из базиса согласно условию допустимости.

Мы можем вывести из базиса как переменную R1, так и переменную R2, потому что отношения коэффициентов столбца решений к положительным коэффициентам рабочего столбца одинаковы, и равны единице. Остановим свой выбор на переменной R1. В результате операции замещения получачим таблицу:

Одна из базисных переменных (R2) равна нулю. Это означает, что соответствующее решение является вырожденным. С практической точки зрения ситуация полностью объясняется присутствием в модели одного избыточного ограничения. Продолжаем решение задачи по алгоритму симплексметода.

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

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

Итак, если в результате минимизации целевой функции R из базиса выводятся все искусственные переменные, и хотя бы одна из базисных переменных равна 0, то в текущей точке есть избыточное ограничение, и

при этом среди них нет линейно-зависимых.

Этап 2

Выполним последнюю итерацию:

Согласно условию оптимальности вводим в базис переменную s1 и согласно условию допустимости выводим из базиса переменную x1. Получаем таблицу:

Данная таблица - оптимальная, потому что в строке z коэффициенты при небазисных переменных – отрицательные (условие оптимальности для задачи на минимум). Задача решена.

Ответ: x1=0, x2 =1, z = 1.

Пример 12.4 (Наличие избыточных ограничений, которые есть линейной

комбинацией других ограничений.)

Очевидно, что задача уже имеет каноническую форму.

Этап 1 1. Введем искусственные переменные в ограничения типа “≥” и “=”. В нашей

задачи это ограничения (12.17), (12.18) и (12.19). Назовем искуственные переменные

R1 ,R2 и R3 соответственно. Тогда модель (12.16)-(12.20) будет иметь такой вид:

53

соответствено:

R1 = 4 - x1- x2 R2= 2 - x2 R3 = 6 - x1- 2x2

Получаем такую целевую функцию: r = R1 + R2 + R3 = 12 - 2x1 - 4x2

Перепишем целевую функцию в виде:

r+ 2x1 + 4x2 = 12

3.Построим начальную таблицу двухэтапного симплекс-метода.

Согласно условия оптимальности вводим в базис переменную x2, и, согласно условия допустимости, выводим из базиса переменную R2.

Получим таблицу:

продолжаем выполнять итерации симплекс-метода. Согласно условия оптимальности вводим в базис переменную x1, а согласно условия допустимости

54

можно вывести из базиса как переменную R1 так и переменную R3, остановимся на переменной R1. Получим таблицу:

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

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

Этап 2

В результате удаления избыточного ограничения и столбиков, отвечающих исскуственным переменным, получили такую таблицу:

Очевидно, что данная таблица - оптимальна. Задача решена.

Ответ: x1=2, x2 =2, z = 4.

Контрольные вопросы

1.Сколько избыточных ограничений соответствует вершине пространства решений для ЗЛП с двумя переменными, если на некоторой итерации симплексметода три базисные переменные равны нулю?

2.Сколько гиперплоскостей должно проходить через угловую точку в случае n-мерной ЗЛП, чтобы соответствующее решение было вырожденным?

3.Можно ли на основании проведенного обсуждения сделать вывод о том, что в случае вырожденности количество базисных решений больше числа вершин?

55

13. Альтернативные оптимальные решения

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

Такие решения называются альтернативными оптимальными решениями.

задачи, видно, что нельзя найти единственную точку, которая была бы оптимальным решением. Фактически это означает, что прямая, представляющая целевую функцию, параллельна прямой, соответствующей одному из связывающих ограничений. Это обусловливает наличие альтернативных оптимальных решений.

(Каждая точка участка прямой (соответствующей ограничению (34)) от точки B до

точки C - альтернативный оптимум).

Табличный симплекс-метод.

Приведем задачу к канонической форме:

56

Переменная x1 вводится в базис. Переменная s3 выводится из базиса.

Итерация 1.

Переменная x2 вводится в базис. Переменная s1 выводится из базиса.

Итерация 2.

Переменная s3 вводится в базис. Переменная s2 выводится из базиса.

Итерация 3.

Таблица 26

Оптимум, соответствующий точке B (z=6), получен на итерации 2. Каким образом по результатам этой итерации можно узнать о наличии альтернативных оптимальных решений? Рассмотрим z-строку. Нулевые значения коэффициента

небазисной переменной s3 свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению значений других переменных. Именно это и происходит на итерации 3, когда s3 вводится вместо s2.

В результате имеем новое оптимальное решение, соответствующее точке C.

Итак, с помощью симплекс-метода удается идентифицировать вершины B и C. Каждое решение, соответствующее точке

принадлежащей отрезку BC, можно определить как положительно взвешенное среднее двух полученных оптимальных базисных решений, соответствующих точкам

B и C:

B:x1=1, x2=5,

C:x1=5, x2=1.

Полагая 0≤ λ ≤1, можно выразить координаты каждой точки отрезка BC:

x)1 = λ (1) + (1 − λ) (5) = 5 − 4λ, x2 = λ (5) + (1 − λ) (1) = 1 + 4λ.

Признак наличия бесконечного множества решений ЗЛП. Нулевое

значение коэффициента небазисной (-ых) переменной (ых) в z-строке.

14. Неограниченность пространства решений и целевой функции

Пример 14.1

58

MAX z = x1 + x2;

Графическое решение.

X2

4

2

По рис.5 видно что, увеличивая целевую функцию, мы никогда не дойдем до оптимального решения. Исходя из этого, можно сделать вывод, что пространство

решений данной задачи неограниченно, и значение целевой функции z может быть сколь угодно большим.

Табличный симплекс-метод. Приведем задачу к каноническому форме:

MAX z = x1 + x2 + 0s1 + 0s2;

− x1 +2x2 + s1 =2; x1 −4x2 + s2 =4;

x1, x2 ,s1,s2 ≥0.

Запишем начальную симплекс-таблицу.

Таблица 27

59

Как видно из полученной таблицы, отрицательные коэффициенты z-строки при переменных x1 и x2 равны по абсолютной величине. Следовательно, можно на

этом шаге вводить в базис как переменную x1 так и переменную x2. Рассмотрим x1.

Итерация 0.

Таблица 28

`

Переменная x1 вводится в базис. Переменная s2 выводится из базиса.

Итерация 1.

Таблица 29

На второй итерации возникла ситуация: имеется отрицательный коэффициент z-строки при переменной x2. Заметим, однако, что во всех ограничениях коэффициенты при x2 отрицательны (переменные s1 и x1 не могут быть выведены из базиса, т.к. имеют отрицательные коэффициенты в ведущем столбце). Это означает, что x2 можно бесконечно увеличивать, не нарушая ни одного из ограничений модели. Так как прирост переменной x2 на 1 приводит к увеличению функции z на 5, становится ясно, что при неограниченном возрастании x2 будет неограниченно увеличиваться и значение целевой функции z. Поэтому, не приводя дальнейших вычислений, можно заключить, что решение сформулированной задачи не ограниченно.

Теперь вернемся к начальной симплекс-таблице. Будем вводить в базис переменную x2 и посмотрим, изменится ли ситуация.

Итерация 0.

Таблица 30

60