Линейное программирование (стр. 6 из 8)

Т.к. в оптимальном решении отсутствуют искусственные переменные, имеющие положительное значение, то данное решение – допустимое оптимальное решение задачи в её стандартной постановке.

3. Двухэтапный метод

Этап 1. Вводятся искусственные переменные, необходимые для получения стартовой точки. Записывается новая целевая функция, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях, видоизменённых за счёт искусственных переменных. Если минимальное значение новой целевой функции равно нулю (т.е. все искусственные переменные в оптимуме равны нулю), то исходная задача имеет допустимое решение и переходим к Этапу 2.

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

Рассмотрим на примере.

Этап 1.

Минимизация

при ограничениях

							Решение

Т.к.

, можно переходить к Этапу 2.