Соотношения двойственности

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

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

Системы ограничений ПЗ и ОЗ примут вид:

, ;

, .

Первоначальным (свободным) переменным прямой задачи соответствуют допол­нительные (базисные) переменные обратной задачи, а дополнительным (базисным) пе­ременным ПЗ соответствуют первоначальные (свободные) переменные ОЗ.

Пример 2).

прямая задача			двойственная задача
ОЗЛП			ОЗЛП

Соответствие между переменными

Чтобы найти оптимальное решение ОЗ по известному оптимальному решению ПЗ, нужно воспользоваться следующим правилом: значение переменной ОЗ равно коэффициенту в целевой функции при соответствующей переменной ПЗ, взя­тому с противоположным знаком из последней симплексной таблицы.

Р е ш е н и е ПЗ.

	Bi	x1	x2	x3	x6
z1			-1	-1
x4		-1
x5			-1
z2					-1
W	6M	3M-1
- искусственные переменные

	Bi	z1	x2	x3	x6
x1
x4
x5
z2					-1
W

	Bi	z1	z2	x3	x6
x1
x4
x5
x2
W	-4

	Bi	z1	z2	x3	x4
x1
x6
x5
x2
W	-10

Ответ ПЗ: при , .

Ответ ОЗ: при , , .

Пример 3).

прямая задача			двойственная задача
ОЗЛП			ОЗЛП

Соответствие между переменными

	основные (свободные)
		дополнительные (базисные)

		ПЗ
		ОЗ

	дополнительные (базисные)		основные (свободные)

Чтобы найти оптимальное решение ПЗ по известному оптимальному решению ОЗ, нужно воспользоваться следующим правилом: значение переменной ПЗ равно коэффициенту в целевой функции при соответствующей переменной ОЗ, взя­тому с противоположным знаком из последней симплексной таблицы.

Р е ш е н и е ОЗ.

Bi

y1

y2

y3

Bi

y1

y5

y3

Bi

y4

y5

y3

y4

-1

y4

y1

y5

-2

y2

y2

-1

-3

-2

-2

Ответ ОЗ: при ; ; .

Ответ ПЗ: при ; .

Двойственный симплекс-метод (ПР № 8)

В результате использования двойственного симплекс-метода сначала получается решение, для которого выполняется условие оптимальности, но которое не является допустимым.

Этот метод обеспечивает выполнение условия оптимальности решения и система­тическое ‘приближение’ его к области допустимых решений. Когда получен­ное решение оказывается допустимым, процесс вычисления заканчивается, т.к. это ре­шение является и оптимальным.

Алгоритм метода

1. В столбце ‘ В ’ выбирается наибольшая по абсолютной величине отрицатель­ная базисная переменная; если все базисные переменные неотрицательны, то процесс вычислений заканчивается, т.к. полученное решение допустимое и оптимальное.

2. Включаемая в базис переменная выбирается из числа свободных следующим об­разом. Вычисляются отношения коэффициентов строки целевой функции к соответствующим коэффициентам ключевой строки. Отношения с положи­тельным или нулевым значением знаменателя не учитываются. Вводимой пе­ременной должно соответствовать наименьшее из указанных отношений.

Если знаменатели всех отношений равны нулю или положительные, то задача не имеет допустимых решений.

3. После выбора ключевого столбца для получения следующего решения осущест­вляется обычная процедура пересчёта элементов симплексной таб­лицы.

Пример. ОЗЛП

Решение. Выберем в качестве начальных базисных переменных .

Приравняем свободные переменные к нулю и найдём первоначальное решение: , , , , . Так как и , то это решение не является допустимым. Но поскольку все коэффициенты при свободных переменных в целевой функции не положительны, то для начального решения выполняется условие оптимальности.

Bi

x1

x2

Bi

x1

x4

Bi

x3

x4

x3

-3

-3

-1

x3

-1

x1

x4

-6

-4

-3

x2

x2

x5

x5

-1

x5

-1

L

-2

-1

L

L

1/2

1/3

2/5

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

Ответ: при ;

Пример 2. Составить ОЗ к данной задаче, решить ОЗ двойственным симплекс-мето­дом. Записать ответ ПЗ по известному решению ОЗ.

.

Р е ш е н и е. ОЗ формулируется следующим

образом:

Нахождение оптимального решения ОЗ двойственным симплекс-методом.

ОЗЛП В качестве первоначальных базисных переменных

выбираются :

	Bi	y1	y2			Bi	y5	y2
y3	-6	-1	-1		y3	-4
y4	-8	-1	-4		y4	-6
y5	-10	-5	-1		y1
F		-2	-1		F
		2/5						3/19
	Bi	y5	y4			Bi	y5	y3
y3					y4
y2					y2
y1					y1
F					F
		7/3	3/4

Ответ ОЗ: , , .

Чтобы записать ответ ПЗ, нужно воспользоваться соответствием между перемен­ными прямой и обратной задач.

Ответ ПЗ: , , , .

Задания к практической № 7 (Двойственность в ЛП)

Задание 1. Составить обратные (двойственные) задачи к данным задачам ЛП.

(по примеру 1)

Задача а)

Задача б)

Задание 2. Составить обратные (двойственные) задачи к данной задаче ЛП. Запи­сать ответ по известному решению прямой задачи. (по примеру 3)

Дата добавления: 2014-01-07