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

Страницы работы

Фрагмент текста работы

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

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

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

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

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

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

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

max n

                                                                            ∑cj xj

min  j 1=

(18)

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

j 1=

 xj ≥ 0,   j =1,n

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

m        min∑yi

i 1=

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

j 1=

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

                                                             yi ≥ 0,  i =1,m

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

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

Доказательство. Очевидно, что область допустимых планов (ОДП) этой задачи не может быть пуста: налицо хотя бы один допустимый план - тот опорный план, который соответствует исходному базису. В самом деле, план Х = (х1, x2, …, xn, y1, y2, …, ym) = (0, 0, …, 0, b1, b2, …, bm) ∈ ОДП задачи (19). 

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

Пусть U* = (x1*, . . . xn*, y1*, . . . ym*) - оптимальный план задачи (19). Теорема о свойствах оптимального плана расширенной задачи:

m

*

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

i

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

m

                                    *                              (0)                 *                *

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

i

Другими словами, если в U* все искусственные переменные равны 0, то план Х(0), составленный из компонент xj* плана U*, является допустимым для исходной задачи.

Доказательство первой части теоремы осуществляется от противного. Предположим, что существует уi* > 0, и ОДП задачи (18) при этом не пуста, т.е. существует план X` = (x1`,. . . . xn`) ∈ ОДП задачи (18). Рассмотрим план U` = (x1`,. . . xn`, 0 ... 0 ) (в нем

14243

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

                 j 1=n aijx j`+ 0 = bi,    i =1,m ∑n aijx j`= bi,    i =1,m

    0x ≥`≥00,   j =1,n    ⇔j 1= x j`≥ 0,   j =1,n    j

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

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

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

Похожие материалы

Информация о работе