Лекция: Метод искусственного базиса.

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

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

Алгоритм метода искусственного базиса.

Шаг 1.

Приводим задачу ЛП к каноническому виду с неотрицательными правыми частями, .

(35.1)

Шаг 2:

Строим вспомогательную задачу ЛП

(35.2)

.

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

Вспомогательная задача ЛП всегда имеет решение, причем оптимальное значение целевой функции

Приводим вспомогательной задачи ЛП к специальному виду. Для этого целевую функцию выражаем через небазисные переменные.

(35.3)

Шаг 3:

Решаем вспомогательную задачу ЛП симплекс-методом.

Шаг 4:

Если, то допустимого решения в исходной задаче не существует. Задача не разрешима и процесс решения исходной задачи завершается.

Шаг 5:

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

Двойственность задач линейного программирования. Таблица соответствий.

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

Рассмотрим пару задач ЛП вида:

Таблица 36.2

Трудности в решении задач линейного программирования зависят не от количества переменных n, а от количества ограничений m, определяющих число итераций симплекс-метода. Поэтому, если прямая задача линейного программирования, еще не приведенная к стандартной форме, содержит большое количество ограничений (m>n), то в этом случае целесообразно перейти к двойственной задаче. Сформированная двойственная задача линейного программирования будет иметь m переменных и n ограничений, т.е. количество итераций при этом уменьшится.

Задачу (I) называют прямой задачей ЛП, а (II) — двойственной. Ограничения задач (I) и (II), соответствующие друг другу, называются сопряженными. Заметим, что задача двойственная к (II), есть исходная прямая задача, т.е. соотношение двойственности взаимное. Поэтому можно любую из такой пары задач считать прямой, а другую — двойственной.

Грубо говоря, двойственная задача — это на 900повернутая исходная прямая задача. В этой связи полезно усвоить следующую схему соответствия.