Метод искусственного базиса

4 Метод искусственного базиса. 72

4.1 Двухэтапный симплекс-метод. 72

4.2 Пример решения задачи методом искусственного базиса. 76

4.3 Вопросы и упражнения. 82

4 Метод искусственного базиса

Как было рассмотрено в разделе 3, для применения алгоритма симплекс-метода необходимо начать решение задачи линейного программирования с некоторого опорного плана. Чтобы этот план можно было построить, задача должна быть записана в канонической форме с неотрицательными свободными членами и иметь полный набор базисных переменных.

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

Рассмотрим одну из модификаций метода искусственного базиса – двухэтапный симплекс-метод.

4.1 Двухэтапный симплекс-метод

Пусть задача линейного программирования в канонической форме с неотрицательными свободными членами не содержит полного набора базисных переменных:

В этом случае, для того чтобы применить к ней симплекс-метод, используется метод искусственного базиса. Вводят m неотрицательных переменных у₁, у₂, . . . . у_m, по одной в каждое уравнение. Эти переменные называют искусственными, и составляют расширенную задачу, имеющую следующий вид*:

В этой задаче имеется m единичных столбцов при искусственных переменных, из которых и состоит искусственный базис.

Лемма. Задача (19) всегда разрешима.

Доказательство. Очевидно, что область допустимых планов (ОДП) этой задачи не может быть пуста: налицо хотя бы один допустимый план - тот опорный план, который соответствует исходному базису. В самом деле, план Х = (х₁, x₂, …, x_n, y₁, y₂, …, y_m) = (0, 0, …, 0, b₁, b₂, …, b_m) Î ОДП задачи (19).

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

Лемма доказана.

Пусть U^* = (x₁^*, . . . x_n^*, y₁^*, . . . y_m^*) - оптимальный план задачи (19).

Теорема о свойствах оптимального плана расширенной задачи:

1).  

Т.е. если оптимум расширенной задачи положителен (что эквивалентно утверждению о том, что хотя бы одна искусственная переменная в плане U^* положительна), то ОДП исходной задачи пуста.

2).

Другими словами, если в U^* все искусственные переменные равны 0, то план Х⁽⁰⁾, составленный из компонент x_j^* плана U^*, является допустимым для исходной задачи.

Доказательство первой части теоремы осуществляется от противного. Предположим, что существует у_i^* > 0, и ОДП задачи (18) при этом не пуста, т.е. существует план X` = (x<sub>1</sub>`,. . . . x_n`) Î ОДП задачи (18). Рассмотрим план U` = (x₁`,. . . x<sub>n</sub>`, ) (в нем первые n компонент взяты из плана X`, а все искусственные переменные равны нулю). U`Î ОДП задачи (19), что легко проверить подстановкой его в систему ограничений этой задачи:

Последняя система истинна, так как X`Î ОДП задачи (18).

На плане U` целевая функция задачи (19) Z` = 0 (сумма нулевых искусственных переменных). Однако по условию теоремы, оптимум задачи (19) положителен, т.е. больше Z`. Так как задача (19) на минимум, план U^* не может быть оптимальным, если есть допустимый план, на котором значение целевой функции меньше. Мы пришли к противоречию, первая часть теоремы доказана.

Вторая часть теоремы доказывается непосредственно подстановкой U^* U^* = (x₁^*, . . . x_n^*, 0, . . . 0)  в ограничения задачи (19). Так как этот план допустимый для задачи (19), уравнения системы обращаются в истинные равенства. Они в точности совпадают с уравнениями системы (18) при подстановке в нее плана Х⁽⁰⁾ = (x₁^*, . . . x_n^*) (и ограничения неотрицательности также выполняются):

Из выполнения ограничений задачи (19) следует выполнение ограничений задачи (18): следовательно, план Х⁽⁰⁾- допустимый для задачи (18).

Теорема доказана.

Смысл доказанной теоремы в том, что решить задачу линейного программирования будет возможно лишь в том случае, если удастся избавиться от всех искусственных переменных*. В самом деле, эти искусственные переменные при построении расширенной задачи были «втиснуты» между левой и правой частями уравнений. На самом деле левые части ограничений были РАВНЫ правым, никакой разницы между ними быть не должно. И задача будет разрешима лишь в том случае, если этот «зазор» - искусственную переменную – удастся свести к нулю во всех ограничениях.

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

На основании данной теоремы строится алгоритм двухэтапного симплекс-метода, который состоит в следующем:

1-й этап. Строится расширенная задача, которую решают обычным симплекс-методом.

2-й этап. Если оптимум расширенной задачи положителен, делается вывод о неразрешимости исходной задачи, так как ее ОДП = Æ. Если он равен нулю, то переходят к решению симплекс-методом исходной задачи, начиная с опорного плана, соответствующего значениям переменных x_j^*.