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

Определение 9. Следующая задача называется двойственной к задаче (1,2).

Задача 3. Найти

, (19)

, , (20)

где матрицы A, b, c определяются по формулам (3), а .

В развернутой форме эта стандартная задача линейного программирования может быть записана в следующем виде.

Задача 3’. Найти минимум линейной функции

,

при ограничениях:

.

Задачи (1, 2) и (91, 92) называются взаимно двойственными задачами, а задача (1, 2) по отношению к задаче (91, 92) называется прямой.

Пример 9. Составить двойственные задачи к следующим задачам.

a) , .

b) , .

Решение. a) Число переменных в двойственной задаче совпадает с числом ограничений прямой задачи и равно 3. Обозначим их через Так как в прямой задаче требуется найти максимум, то знаки неравенств во всех ограничениях должны быть « ». Коэффициенты целевой функции двойственной задачи совпадают со свободными частями неравенств, а правые части неравенств двойственной задачи совпадают с коэффициентами целевой функции прямой задачи. В итоге мы получаем следующую задачу линейного программирования.

,

.

b) Прежде чем составить двойственную задачу следует прямую задачу преобразовать так, чтобы все неравенства в ней имели вид « ». Для этого мы умножим первые два неравенства на –1. После этого мы уже сможем записать двойственную задачу.

, (21)

. (22)

Для решения двойственной задачи можно применить те же методы решения, как и для прямой задачи: составление канонической задачи, поиск допустимого базисного плана, преобразование таблиц. Однако, всего этого можно избежать, если есть базисное решение прямой задачи. Базисное решение двойственной задачи можно взять из строки для целевой функции прямой задачи. А для проверки оптимальности полученного решения можно воспользоваться теоремой двойственности.

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

1. .

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

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

Пример 10. Найти решение двойственной задачи к задаче примера 8 и проверить его по теореме двойственности.

Решение. Двойственной задачей к задаче (15, 16) будет задача (21, 22). Итоговой таблицей прямой задачи будет таблица 11. Меняя знаки у чисел стоящей в последней строчке, мы укажем значения переменных двойственной задачи.

, , (23)

Проверим теперь допустимость полученного решения. Для этого подставим их в неравенства системы (22). Мы получим

, .

Следовательно, план является допустимым для задачи (15, 16). Вычислим теперь значение целевой функции на этом плане. У нас получиться:

.

Это значение совпадает с сосчитанным ранее значением целевой функции прямой задачи. А поэтому приведенный нами план двойственной задачи (23) будет оптимальным.

Пример решения задачи

Задача 4. Найти максимум линейной функции , если переменные удовлетворяют следующей системе ограничений:

.

В математических символах эта задача имеет следующий вид:

,

.

1. Запишем эту задачу в матричной форме. Для этого умножим первое и третье неравенство системы на –1. У нас получиться следующая система неравенств:

Следовательно, наша задача в матричной форме примет вид:

,

, ,

где

; ; ; (24)

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

.

Окончательно, каноническая задача линейного программирования для нашей задачи имеет вид:

при ограничениях

. (25)

(III)

3. Для того чтобы решить начальную задачу геометрически, построим прямые , ; , ; , ,.

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

L

(II)

(I)

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

Функция принимает свое максимальное на множестве значение равное в точке с координатами ; .

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

,

.

Составим симплекс-таблицу и применим симплекс метод. В таблицы включена также функция , а генеральные строки и столбцы таблиц заштрихованы.

		4*	-1					12/4
								–
	-1							10/2
			-1
	1/4		– 1/4			1/4
	5/2		1/2			– 1/2
	-3/2		1/2			– 1/2
	13/4		3/4			– 3/4	-9
						– 1

Из этой таблицы мы находим допустимый базисный план канонической задачи:

, , , , .

5. Исключим теперь из таблицы вспомогательную функцию , искусственную переменную и решим полученную задачу симплекс методом.

	1/4		– 1/4				–
	5/2		1/2
	– 3/2		1/2*
	13/4		3/4			-9
	– 1/2				1/2		–
	4*				–1
	– 3						–
	11/2				– 3/2	–15
				1/8	3/8
				1/4	– 1/4
				3/4	11/4
				–11/8	– 1/8	-37

Из последней таблицы мы получим оптимальное решение канонической задачи (25):

, , , , , ,

а следовательно функция принимает свое максимальное на множестве значение равное в точке с координатами ; .

6. Двойственная задача к искомой задаче будет иметь вид:

,

,

или в матричной форме: , , с матрицами (24) и матрицей .

7. Из последней симплекс таблицы мы найдем значения двойственных переменных:

, ,

Подставим эти числа в ограничения двойственной задачи и целевую функцию:

, , .

Так как выполнены все условия теоремы двойственности, то найденное решение:

, , ,

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

 

Варианты заданий

1 ,	2 ,	3 ,	4 ,
5 ,	6 ,	7 ,	8 ,
9 ,	10 ,	11 ,	12 ,
13 ,	14 ,	15 ,	16 ,
17 ,	18 ,	19 ,	20 ,
21 ,	22 ,	23 ,	24 ,
25 ,	26 ,	27 ,	28 ,
29 ,	30 ,	31 ,	32 ,

Литература

1. Ашманов С.А. Линейное программирование, М., Наука, 1981, 340с.
2. Галанова З.С., Родин В.И., Ермошин А.А., Конова С.Ю. Линейное программ­ми­рование, ч.1, Петербургский государственный университет путей сообщения, 1996, 40 с.
3. Луценко М.М. Линейная алгебра. Учебное пособие. СПб: Петербургский государственный университет путей сообщения, 1999. – 121 с.

 

Учебное издание

 

ЛУЦЕНКО МИХАИЛ МИХАЙЛОВИЧ

 

 

Отпечатано в авторской редакции

 

Подписано в печать с оригинал макета – 6.04.2006

Формат 60х80 1/16. Бумага для множ. апп. Печать офсетная.

Усл.печ.л. Уч.-изд.л. Тираж

Заказ Цена

Петербургский государственный университет путей сообщения.

190031, СПб., Московский пр., 9.