47509 (665840), страница 4

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

Текст из файла (страница 4)

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

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

Этап 1.

Минимизация

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

							Решение

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

Этап 2. Исходную задачу сформулируем следующим образом:

минимизировать

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

Теперь, приравняв x3=0, получим НДБР

Для решения задачи необходимо подставить в целевую функцию выражения для базисных переменных x1 и x2:

5. Двойственность.

Двойственная задача – вспомогательная задача ЛП, формулируемая с помощью определённых правил непосредственно из исходной, или прямой задачи.

Прямая задача ЛП в стандартной форме:

максимизировать (минимизировать)

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

В состав включаются избыточные и остаточные переменные.

Для формулировки двойственной задачи расположим коэффициенты прямой задачи согласно схеме:

• каждому ограничению прямой задачи соответствует переменная двойственной задачи;

• каждому переменной прямой задачи соответствует ограничение двойственной задачи;

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

Информация о других условиях двойственной задачи (направление оптимизации, ограничения и знаки двойственных переменных) представлена в таблице:

Прямая задача в стандартной форме.	Двойственная задача
Целевая функция	Целевая функция	Ограничения	Переменные
Максимизация	Минимизация		Не ограничены в знаке
Минимизация	Максимизация		Не ограничены в знаке

Рассмотрим пример:

Прямая задача:

максимизировать

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

Прямая задача в стандартной форме:

максимизировать

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

Двойственная задача:

минимизировать

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

(означает, что y1>0). y1, y2 не ограничены в знаке.

Характеристики

Список файлов реферата