Метод искусственного базиса. Теорема о свойствах оптимального плана расширенной задачи

Аннотация лекции. Лекция посвящена симплекс-методу решения задачи линейного программирования (методу искусственного базиса). Рассмотрен алгоритм двухэтапного симплекс-метода.

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

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

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

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

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

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

max n

                                                                            ∑_{cj xj}

min ^ j 1=

(18)



∑n aij xj = bi ,    i =1,m

j 1=

 x_j ≥ 0,   j =1,n

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

m        min∑y_i

i 1=

                                                        ∑n aijx j + yi = bi,    i =1,m                              (19)

j 1=

^        x _j ≥ 0,   j =1,n 

                                                             y_i ≥ 0,  i =1,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). Теорема о свойствах оптимального плана расширенной задачи:

m

*

                  1).         > 0 ⇒ОДП(исходной задачи) =∅ 

i

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

m

                                    *                              ^{(0)                 *                *}

                  2)_.          = 0 ⇒_X = (x1 ,...,_xn)∈ОДП(исходной задачи)

i

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

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

14243

m первые n компонент взяты из плана X`, а все искусственные переменные равны нулю). U`∈ ОДП задачи (19), что легко проверить подстановкой его в систему ограничений этой задачи:

                 ^^∑j 1₌ⁿ aijx j`+ 0 = bi,    i =1,m ∑n <sub>a</sub>ij<sub>x</sub> j<sub>`</sub>= _bi_{,    i} =_1,m

    0^x ≥`≥00,   j =1,n    ⇔j 1= x <sub>j</sub>`≥ 0,   j =1,n    j

^

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

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

Вторая часть теоремы доказывается непосредственно подстановкой