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

Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:

(10)

Характерная особенность задачи (10) – известное базисное допустимое решение

Чтобы применить симплекс-метод для решения задачи ЛП в произвольной форме, необходимо привести эту задачу к виду (10), т.е. выделить начальное допустимое базисное решение.

Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса и состоит в следующем.

Вычислительная схема метода искусственного базиса.

Шаг 1. Приводим задачу ЛП к канонической форме

(11)

с неотрицательными правыми частями .

Шаг 2. В каждую i-ю строку ограничений (11) вводим искусственную неотрицательную переменную x_i и строим вспомогательную задачу ЛП вида:

(12)

Эта задача имеет допустимое базисное решение и легко может быть сведена к виду (11). Для этого целевую функцию необходимо выразить через свободные переменные :

Шаг 3. Для построенной вспомогательной задачи строим симплексную таблицу

	b		…
			…
			…
…	…	…………..
			…

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

Шаг 4. Если и все переменные являются небазисными, то m переменных из войдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид:

(13)

Так как переменные , то их исключили из системы (13), не нарушив при этом равенств. Выражая целевую функцию основной задачи через небазисные переменные системы (13), получим исходную задачу (12) в виде (11).

Шаг 5. Если , но в базисе остались искусственные переменные , для которых (вырожденный случай), то проводим для каждой искусственной переменной из базиса следующее преобразование симплексной таблицы:

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

В этом случае строка искусственной переменной будет ведущей и после стандартного преобразования симплексной таблицы (шаг 6 из прямого симплекс – метода) искусственная переменная выведется из базиса.

В результате получим симплексную таблицу, соответствующую шагу 4.

Шаг 6. Если , то допустимого решения в исходной задаче (11) не существует (не могут все искусственные переменные быть равными нулю в задаче (18), а значит система ограничений задачи (11) несовместна) – процесс решения исходной задачи (11)

Дата добавления: 2015-07-26; просмотров: 259; Нарушение авторских прав

Мы поможем в написании ваших работ!