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

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

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

Пусть имеется каноническая задача линейного программирования

(4.20)

Без ограничения общности можно считать, что правые части уравнений системы ограничений неотрицательные, т. е. .

В дальнейшем для краткости записи при доказательствах используется компактная запись этой задачи

; (4.21)

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

Искусственными переменными называются неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом +1 и в целевую функцию в задаче на максимум – с коэффициентом -М, а в задаче на минимум – с коэффициентом +М. Число М сколь угодно большое по сравнению с единицей (М >> 1).

В общем случае расширенная задача на максимум имеет вид

(4.22)

, j = 1, 2, ..., n+m; , i = 1, 2, ..., m

или в компактной записи

, (4.23)

Данная задача имеет начальное опорное решение

с единичным базисом

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

Для обоснования метода докажем две леммы и три теоремы.

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

Доказательство. Пусть – допустимое решение. Тогда оно удовлетворяет системе ограничений и условиям неотрицательности задачи (4.23)

(4.24)

Дополним данное решение равными нулю переменными

, имеем . Подставим в систему ограничений расширенной задачи (4.23), получим

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

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

Отсюда .

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

Доказательство. Подставим и в целевую функцию расширенной задачи

Так как допустимое решение удовлетворяет условию неотрицательности и по условию леммы хотя бы одна из координат , то и .

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

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

Доказательство (от противного). Пусть расширенная задача на максимум имеет оптимальное решение ,
т. е. . По лемме 4.1 допустимому решению соответствует допустимое решение исходной задачи такое, что . Покажем, что - оптимальное решение исходной задачи, т. е. .

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

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

Доказательство (от противного). Пусть расширенная задача на максимум имеет оптимальное решение

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

Предположим, что исходная задача имеет некоторое допустимое решение . По лемме 4.1 ему соответствует допустимое решение расширенной задачи и . На основании леммы 4.2 имеем , что противоречит оптимальности . Теорема доказана.

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

Доказательство (от противного). Пусть расширенная задача на максимум не имеет решения ввиду неограниченности функции, то есть +¥. Предположим, что исходная задача имеет оптимальное решение . По лемме 4.1 ему соответствует допустимое решение расширенной задачи