ДОКАЗАТЕЛЬСТВО. Воспользуемся леммой 2 и следствием теоремы 1:

1) Необходимость

Воспользуемся леммой 2 и следствием теоремы 1:

Получим

2) Достаточность

Распишем скалярное произведение

Т.к. правые части совпадают, что левые совпадают. По следствию теоремы 1 получаем требования ¤

ЗАМЕЧАНИЕ

Для канонической задачи и двойственной к ней условия «дополняющей нежесткости» имеют вид:

1)

2)

ПРИМЕР

1) Решить прямую задачу и двойственную к ней

Решим задачу симплекс методом, приведя ее к канонической форму.

Строим симплекс таблицу:

		-1				-
			-1
		-4	-2

		1/3	5/3			33/5
		-1/3	4/3
		1/3	-1/3			-
		4/3	-10/3

		3/4	-5/4
		-1/4	3/4
		1/4	1/4
		1/2	5/2

Оптимальное решение прямой задачи .

Строим двойственную задачу к исходной:

Чтобы построить оптимальное решение двойственной задачи, воспользуемся формулой

– дополнительные переменные из таблицы. Количество уравнений равно рангу матрицы

2) Иллюстрация применения теоремы 2.

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

Эта задача ЛП с параметром . Применим 2ю теорему двойственности и условия «дополняющей нежесткости».

Напомним формулировку:

оптимальные решения задач

I)

II)

1) Если

2) Если

3) Если

4) Если

Нам нужны условия 1 и 2:

1) Проверим, что – допустимое решение задачи. Легко убедится, что так оно и сеть.

2) Выписать систему линейных уравнение из условия «дополняющей нежесткости» относительно неизвестной двойственной переменной .

Анализируем координаты вектора :

Нам нужна двойственная задача. Строим ее:

Если координата = 0, то условий нежесткости для случая нет.

Подставим , в условия ограничений:

Получаем

Если построенная система окажется противоречива, исследование завершается и делаем вывод, что – неоптимальное решение.

Если ли среди найденый решений на шаге 2 допустиое решение двойственной задачи (подставить решение в условия двойственной)

Задача решена.

Это так называемый анализ чувствительности

Поиск по сайту: