Правила построения двойственной задачи к исходной задаче ЛП в общем виде

Двойственность в линейном программировании

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

Прямая задача , ,.

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

Экономически пара взаимно двойственных задач может быть интерпретирована, например, так.

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

Двойственная задача. Какова должна быть оценка единицы каждого из ресурсов,, чтобы при заданных количествах ресурсов, величина стоимости единицы продукции, и нормах расходов,, минимизировать общую оценку затрат на все ресурсы?

Переменные, называют оценками или учетными (неявными, теневыми) ценами.

Прямая задача , , , - произвольные,

Двойственная задача ,   - произвольные, , ,

1. Упорядочивается запись исходной задачи: если целевая функция задачи исследуется на max, то ограничения должны иметь знак или =, а если на min, то ограничен ия должны иметь знак или =.

2. Каждому ограничению исходной задачи ставится в соответствие двойственная переменная,, и, наоборот, т.е. число переменных двойственной задачи равно числу ограничений прямой задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

3. Если целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи используется на min, и наоборот.

4. Коэффициенты целевой функции прямой задачи становятся свободными членами системы огранич е ний двойственной задачи.

5. Свободные члены системы ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи.

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

7. Если на переменную, прямой задачи наложено ограничение на знак, то j-е ограничение двойственной задачи записывается в виде неравенства и наоборот.

8. Если переменная, исходной задачи произвольная, то j-е огарничение двойственной задачи имеет знак равенства.

9. Если в прямой задаче имеются ограничения-равенства, то на соответствующие переменные двойственной задачи не налагаются условия неотрицательности.

Пример 6.

Дата добавления: 2013-12-13