Решение задачи линейного программирования симплекс-методом

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

Двойственная задача (ДЗ) – это вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при ПЗ. Трудо

ёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Для перехода к ДЗ необходимо, чтобы прямая задача была записана в стандартной канонической форме. При представлении ПЗ в стандартной форме в состав переменных включаются также избыточные и остаточные переменные.

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

m переменных, соответствующих числу ограничений прямой задачи;

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

Двойственная задача получается путём симметричного структурного преобразования условий прямой задачи по следующим правилам:

Каждому ограничению ПЗ соответствует переменная ДЗ;

Каждой переменной ПЗ соответствует ограничение ДЗ;

Коэффициенты при в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;

Коэффициенты при в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

Постоянные ограничений ПЗ становятся коэффициентами целевой функции ДЗ.

Рассмотрим правила составления двойственной задачи:

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

Остановимся более подробно на определении областей допустимых решений двойственных переменных при переходе от прямой задачи к двойственной.

Области допустимых решений для двойственных переменных

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

1. Рассмотрим ограничение (2) прямой задачи:

Область допустимых решений ДП () определяется знаками ограничений (8) и (9) двойственной задачи и знаком ограничения (2) прямой задачи. Для определения ОДР найдём ограничения ДЗ, соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции для остаточных переменных равны нулю ().Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак ограничения , соответствуют неотрицательные двойственные переменные: .

2. Рассмотрим ограничение (3) прямой задачи:

.

При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:

.

Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак равенства, соответствуют двойственные переменные, не ограниченные в знаке .

3. Рассмотрим ограничение (4) прямой задачи:

В целевой функции избыточные переменные имеют коэффициенты, равные нулю (), а искусственные переменные коэффициенты, равные величине штрафа со своим знаком, в результате для задачи максимизации получим:

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

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

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

 Скачать реферат