Основные положения теории двойственности

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

Теорема 4.1. Пусть – планы соответственно прямой и двойственной ЗЛП, тогда:

.

(4.12)

Теорема 4.2. Пусть – планы соответственно прямой и двойственной ЗЛП и , тогда – решения соответственно прямой и двойственной задач.

Теорема 4.3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем

. (4.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Теорема 4.4. Планы соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда

. (4.14)

Условия (4.14) называются условиями дополнительнойнежесткости.

Примечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:

. (4.15)

Примечание 2. Если прямая ЗЛП записана не в канонической форме, то условия дополнительной нежесткости для этой ЗЛП и двойственной к ней ЗЛП могут быть записаны в следующем виде:

если х_j^* > 0, то ,

если то y_i^* = 0, (4.16)

если y_i^* > 0, то

если , то х_j^* = 0.

Дата добавления: 2014-12-29