Материал: конспект 2

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

Решение ЗЛП симплексными процедурами всегда начинается с определения какого-либо опорного плана. В рассмотренном ранее примере первоначальный опорный план выделялся за счет балансовых переменных.

С точки зрения геометрии это означало, что ОДР ЗЛП примыкало к началу координат. Однако такой случай встречается на практике не часто. В этой связи для выделения первоначального опорного плана обращаются к методу искусственного базиса. Заметим, что метод искусственного базиса позволяет не только выделить первоначальный опорный план, но и ответить на вопрос совместности системы ограничений ЗЛП в области неотрицательных значений переменных. Пусть некоторая ЗЛП представлена в одной из своих канонических форм.

(29)

(30)

(31)

Задача (29) – (31) называется исходной. На ее основании составляют так называемую расширенную задачу.

Предполагая, что все в каждое из ограничений (30) вводят по искусственной переменной. Далее составляют искусственную линейную форму f, которая равна сумме всех искусственных переменных.

Итак, в расширенной задаче будет переменных. Искусственные переменные будут образовывать базис, который называют искусственным. Основные переменные на первом этапе решения задачи будут свободными переменными.

(32)

(33)

(34)

(35)

Представим расширенную задачу (32) – (35) в виде, разрешенном относительно базисных переменных

(36)

(37)

(38)

(39)

Вполне очевидно, что в системе ограничений (38) переменные входят в состав свободных. Тогда при условии имеем

Выделение первоначального опорного плана исходной задачи с помощью искусственных переменных основано на применении следующих теорем.

Теорема 1

Для того, чтобы система ограничений (30) – (31) исходной задачи имела допустимые решения необходимо и достаточно, чтобы минимум искусственной линейной формы (33) был равен нулю, то есть .

Доказательство необходимости.

Пусть система ограничений равенств исходной задачи (30) имеет допустимые планы. Например, это следующий набор чисел

Тогда, подставляя эти числа в систему ограничений (34) расширенной задачи, получим:

Тогда очевидно, что .

Таким образом, если система ограничений имеет решение, то выполняется условие .

Доказательство допустимости.

Пусть минимум искусственной формы равен нулю ( ). Это условие соответствует некоторому решению системы ограничений (34) расширенной задачи. Пусть это решение представляет собой набор чисел

(40)

Проанализируем набор чисел (40). Ясно, что такой набор будет удовлетворять системе ограничений (34), а значит, и системе ограничений (30). Из этого следует, что исходная система ограничений имеет по крайней мере одно допустимое решение, что и следовало доказать.

Теорема доказывает существование допустимых решений системы ограничений исходной задачи. Однако из существования допустимых решений следует существование опорных решений.

Для получения опорных решений необходимо из расширенной задачи вывести искусственный базис.

Теорема 2

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

Доказательство аналогично доказательству теоремы 1.

Теорема 3

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

Доказательство аналогично доказательству теоремы 1.

Метод искусственного базиса называют еще двухфазовым симплексным методом. Это объясняется следующим:

– Первая фаза решения задачи связана с оптиматизацией искусственной линейной формы f. На этом этапе решения выделяется первоначальный опорный план. Основная линейная форма F при этом ведет себя пассивно. Особенность первой фазы состоит в исключении из задачи искусственных переменных при условии выполнения прямодопустимости решения ЗЛП.

– Вторая фаза решения состоит в оптимизации основной линейной формы F, которая на этом этапе ведет себя активно.

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

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

Рассмотрим пример, в котором для выделения первоначального опорного плана используется искусственный базис.

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

Расширенная задача примет вид:

Далее составляют первоначальную жордановскую таблицу

ξ не участвует в оптимизации линейной формы и ликвид.

3 не нарушает условие прямодок. решения

3 остальн. отрицат.

Далее переходят ко 2-ой фазе решения задачи. На этой фазе основная линейная форма F начинает вести себя активно. Анализ такой линейной формы позволяет отметить, что в процессе выхода на первоначальный опорный план, такая целевая функция уже оптимизировалась, поскольку последняя жордановская таблица уже содержит признак opt min. (В строке линейной формы все коэффициенты отрицательны, за исключением быть может свободных членов).