Теоремы двойственности

Приведем без доказательства следующие две теоремы.

Первая теорема двойственности. Прямая задача разрешима тогда и только тогда, когда разрешима двойственная. При этом f_max=φ_min.

Вторая теорема двойственности. Для того чтобы два допустимых решения x₁', x₂',...,x_n' и у₁', у₂',…,y_m' пары двойственных задач были оптимальными, необходимо и достаточно, чтобы эти решения удовлетворяли условиям

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

Пример 2. Дана задача

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

Обратим внимание, что, данная задача записана в форме (4.4) - (4.6). Так как имеет место принцип взаимной двойственности, то будем записывать двойственную задачу в форме (4.1) - (4.3). Получим:

Решим геометрически двойственную задачу. Построим на координатной плоскости граничные прямые (1) 8у₁–5у₂=11; (2) –у₁+3у₂=1; (3) –2у₁–7у₂=–7; находим полуплоскости, определяем ОДР, а затем находим на ОДР оптимальную точку А (см. рисунок). Для отыскания координат точки А решаем систему уравнений

Получаем у₁=2, у₂=1. Подставив эти значения переменных в целевую функцию, получим φ_max=7.

					Y2
									(5)
		(3)
										A
											•									(4)					Y1
						0,3			ОДР
				-1					1,4
													3,5
	(2)
							-2,2
	(1)

Рис. 4.1.

Для отыскания оптимального решения исходной задачи воспользуемся второй теоремой двойственности. Для этого запишем систему равенств (4.7) и (4.8)

Подставив у₁=2, у₂=1, после очевидных преобразований получим систему

Решив полученную систему, найдем х₁= 9/19; х₂=34/19; х₃=0; f_min= 7.

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