лекции(II курс)

Тема 5. Двойственные задачи.

Определение и составление двойственных задач, их экономический смысл. Основные теоремы двойственности и их экономический смысл. Объективно обусловленные оценки. Приложения.

5.1. Определение ДЗЛП.

Рассмотрим две задачи ЛП:

I	II
F = c1x1 + c2x2 + . . .	+ cnxn → max Z = b1y1 + b2y2 + . . . + bmym → min

	при ограничениях			при ограничениях
	a11x1 + a12x2 + . . . + a1nxn	b1;		a11y1 + a21y2 + . . . + am1ym	c1;
a21x1 + a22x2 + . . . + a2nxn		≤ b2;	a12y1 + a22y2 + . . . + am2ym		≥ c2;
	. . . . . . . . . . . . . . . . . . . . . . . . . . .	.≤. . . . .		. . . . . . . . . . . . . . . . . . . . . . . . . . .	.≥. . . . .
am1x1 + am2x2 + . . . + amnxn ≤ bm.			a1ny1 + a2ny2 + . . . + amnym ≥ cm.
	и условии неотрицательности		условии неотрицательности
			è
	x1 ≥ 0, . . . , xn ≥ 0		y1 ≥ 0, . . . , yn ≥ 0

Обе задачи обладают следующими свойствами:

1)В одной задаче ищут максимум линейной функции, в другой минимум.

2)Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.

3)Каждая задача задана в стандартной форме, причем в задаче максимизации все

неравенства вида ≤, а в задаче минимизации все неравенства вида ≥.

4) Матрицы коэффициентов при переменных в системах ограничений задач являются транспонированными друг к другу.

для первой задачи A =	a21	a22	. . . a2n
	a11	a12	. . .	a1n
		a. . .	.. .. ..	a. . .
	a. . .
	m1	m2		mn
для второй задачи A′ = a12		a22	. . . am2
	a11	a21	. . .	am1
		a. . .	.. .. ..	a. . .
	a. . .
	1n	2n		mn

5)Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6)Условия неотрицательности переменных имеются в обеих задачах.

Определение. Две задачи ЛП, обладающие указанными свойствами, называются симметричными взаимодвойственными задачами.

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

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

1) Привести все неравенства системы ограничений исходящей задачи к одному смыслу: если в исходной задаче ищут максимум целевой функции, то все неравенства системы

101

привести к виду "≤ а если минимум к виду "≥". Для этого неравенства, в которых

данное требование не выполняется, умножить на (-1).

2) Составить расширенную матрицу системы A1, в которую включить матрицу коэффициентов при переменных A, столбец свободных членов системы ограничений и строку коэффициентов при переменных в целевой функции.

3)Найти транспонированную матрицу A′1.

4)Сформулировать двойственную задачу на основании полученной матрицы A′1 è óñëî-

вия неотрицательности переменных.

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

F = −x1 + 2x2 → max

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

	2x1 − x2 ≥ 1;
		−			≤	≤
	−x1		+ 4x2				24;
x1			x2			3;
		+ x				5;
x				2	≥
	1
		≥ 0, x2 ≥ 0.
x1

Решение.

1) Так как исходная задача на максимум, то приведем все неравенства системы ограничений к виду ≤, для чего обе части первого и четвертого неравенства умножим на (-1).

Получим:

	−2x1 + x2 ≤ −1;
			−			≤
	−x1			+ 4x2 ≤ 24;
x1				x2			3;
		x			x			5;
	−			−			≤

x1 ≥ 0, x2 ≥ 0.

2)Составим расширенную матрицу системы

1 2

			−2	1	−1
			−1	4	24
A1	=		1	−1	3

−1 −1 −5

−1 2 F

3) Найдем матрицу A′1

A1′ =		−2	−1	1	−1	−1
		1	4	−1	−1	2
		−1	24	3	−5	Z

4) Сформулируем двойственную задачу:

	Z = −y1 + 24y2 + 3y3 − 5y4 → min
при ограничениях		2y1 − y2 + y3 − y4 ≥ −1;

y1 + 4y2 − y3 − y4 ≥ 2; y1 ≥ 0, y2 ≥ 0, . . . , y4 ≥ 0.

102

Экономический смысл ДЗЛП.

Пусть первая задача задача об использовании ресурсов (планирование производства), переменные x1, x2, . . . , xn план выпускаемой продукции P1, P2, . . . , Pn. F прибыль от реализации всей продукции. xn+1, xn+2, . . . , xn+m остатки ресурсов.

Двойственная задача: переменные y1, y2, . . . , yn договорные (учетные) цены еди- ницы ресурса каждого вида, целевая функция Z выражает общую стоимость запасов

ресурсов.

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

5.2. Основные теоремы двойственности и их экономический смысл.

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

Сначала сформулируем достаточный признак оптимальности.

Теорема 5.1. Åñëè X = (x1, x2, . . . , xn) è Y = (y1, y2, . . . , yn) допустимые решения взаимно двойственных задач, для которых выполняется равенство

F (X ) = Z(Y ),

(1)

òî X оптимальное решение исходной задачи I, а Y оптимальное решение двой-

ственной задачи II.

Кроме достаточного признака оптимальности двойственных задач существуют и другие важные соотношения между их решениями. Прежде всего возникают вопросы: всегда ли для каждой пары двойственных задач есть одновременно оптимальные решения; воз-

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

Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых функций равны:

Fmax = Zmin или наоборот Fmin = Zmax

Если целевая функция одной из задачи не ограничена, то условия другой задачи противоречивы.

Рассмотрим пример, подтверждающий справедливость первой теоремы двойственно-

ñòè.	I					II
F = 2x1 + 3x2 → max					Z = 18y1 + 16y2 + 5y3 + 21y4 → min
при ограничениях						при ограничениях
	x1 + 3x2			≤	18;	y1 + 2y2 + 3y4		2;
	2x1 + x2				16;
						{
		≤	5;	≤		3y1 + y2 + y3	≥
x2								≥3;
и условии неотрицательности						и условии неотрицательности
	3x1 ≤ 21;
x1 ≥ 0, x2 ≥ 0						yi ≥ 0(i = 1, 2, 3, 4).

Задача I была решена в примере §3 темы 5 и получен оптимум: Fmax = 24. Решим двойственную задачу, используя симплексный метод.

103

Введем дополнительные неотрицательные переменные y5 è y6 со знаком минус, т.к. неравенства имеют вид ≥. Получим:

{

y1 + 2y2 + 3y4 − y5 = 2 ; 3y1 + y2 + y3 − y6 = 3 .

Если на первом шаге в качестве базисных переменных взять дополнительные переменные, то получим недопустимое базисное решение (0; 0; 0; 0; −2; −3). В данном случае в

качестве базисных удобно взять переменные y3 è y4 (это согласуется с правилом выбора

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

допустимое базисное решение.

ØÀÃ 1.

y3, y4 базисные, y1, y2, y5, y6 свободные.

Выражаем основные переменные через свободные

{

y3 = 3 − 3y1 − y2 + y6 ; y4 = 2/3 − 1/3y1 − 2/3y2 + 1/3y5 .

Первое базисное решение:

2

Y1 = (0; 0; 3; 3; 0; 0) допустимо.

Выражаем целевую функцию

Z = 18y1+16y2+5y3+21y4 = 18y1+16y2+5(3−3y1−y2+y6)+21(2/3−1/3y1−2/3y2+1/3y5) =

= 29 − 4y1 − 3y2 + 7y5 + 5y6. Z1 = Z(Y1) = 29

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

нем с этой переменной.

Составим оценочное отношение

y1 = min{1, 2} = 1,

первое уравнение разрешенное, y3 переходит в свободные переменные.

ØÀÃ 2.

y1, y4 базисные, y2, y3, y5, y6 свободные.

После преобразований, получим

{

y1 = 1 − 1/3y2 − 1/3y3 + 1/3y6 ; y4 = 1/3 − 5/9y2 + 1/9y3 + 1/3y5 − 1/9y6 .

Второе базисное решение Y2 = (1; 0; 0; 1/3; 0; 0) допустимо. Выражаем целевую функцию

Z = 25 − 5/3y2 + 4/3y3 + 7y5 + 11/3y6, Z2 = Z(Y2) = 25.

Данное значение не является минимальным, переводим переменную y2 в базисные

y2 = min{3; 3/5} = 3/5,

104

второе уравнение разрешающее и y4 переходит в свободные.

ØÀÃ 3.

y1, y2 базисные, y3, y4, y5, y6 свободные.

После преобразований, получим

{

y1 = 4/5 − 2/5y3 + 3/5y4 − 1/5y5 + 2/5y6 ; y2 = 3/5 + 1/5y3 − 9/5y4 + 3/5y5 − 1/5y6 .

Третье базисное решение Y3 = (4/5; 3/5; 0; 0; 0; 0) оптимально, т.к в выражении для Z нет свободных переменных с отрицательными коэффициентами. Поэтому Zmin = Z3 =

Z(Y3) = 24.

Вывод: Рассмотренный пример подтверждает заключение первой части основной теоремы двойственности, а именно то, что Fmax = Zmin.

Экономический смысл основной теоремы двойственности.

Экономический смысл первой теоремы двойственности можно интерпретировать так: предприятию безразлично, производить ли продукцию по оптимальному плану X =

(x1, x2, . . . , xn) и получить максимальную прибыль (выручку) Fmax либо продавать ре- сурсы по оптимальным ценам Y = (y1, y2, . . . , ym) и возместить от продажи равные ей

минимальные затраты Zmin.

Пример. Даны две взаимно двойственные задачи:

			I						II
Z = −8y1 + 2y2 → min						F = x1 − x2 → max
	−y1 + 2y2 ≥ 1;						x1 + 2x2 ≥ 8;
	−2y1 + y2 ≥ −1;						2x1 + x2 ≤ 2, ;
		≥	0, y2	≥	0.			≥	0, x2	≥	0.
y1						x1

Из рисунка 1 следует, что если линию уровня перемещять в направлении убывания

−→

целевой функции (т.е. в направлении, противоположном вектору q ), то она всегда бу- дет пересекать многоугольник решений, следовательно, целевая функция неограниченно убывает. Итак, конечного оптимума целевой функции нет, т.е. Zmin = −∞.

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

Вывод: Заключение второй части основной теоремы двойственности выполняется.

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

Пример: Даны две двойственные задачи:

I. F = 3x1 + 5x2 → max						II. Z = 5y1 − 7y2 → min
	3x1		4x2	≤	5;		3y1 + 2y2				3 ;
	2x1		− −7;		0.		−4y1 ≥ 5,≥				;
x1			≥0, x2	≥		y1		≥	0, y2	≥	0 .
		≥

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

105

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

Между компонентами исходной и двойственной задачами существует связь, которую можно записать в виде таблицы:

Переменные исходной задачи I

Первоначальные					Дополнительные
x1	x2	. . .	xi	. . . xn	xn+1 xn+2		. . . xn+i	. . . xn+m
↕	↕		↕	↕	↕	↕	↕	↕
ym+1 ym+2 . . .			ym+j	. . . ym+n	y1	y2	. . . yj	. . . ym
Дополнительные					Первоначальные
			Переменные двойственной задачи II

Теорема 5.2. Положительным (ненулевым) компонентам оптимального решения

одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, . . . , m è j = 1, 2, . . . , n: åñëè xi > 0, òî ym+j = 0; åñëè xn+i > 0, òî yi = 0, и аналогично, если yj > 0, òî xn+i = 0; åñëè ym+j > 0, òî xi = 0.

Рассмотренная теорема является следствием следующей теоремы.

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

Убедимся в справедливости второй теоремы двойственности для следующих взаимо двойственных задач

	I					II
F = 2x1 + 3x2 → max					Z = 18y1 + 16y2 + 5y3 + 21y4 → min
при ограничениях						при ограничениях
	x1 + 3x2			≤	18;	y1 + 2y2 + 3y4		2;
	2x1 + x2				16;
						{
		≤	5;	≤		3y1 + y2 + y3	≥
x2								≥3;
	3x1 ≤ 21;
и условии неотрицательности						и условии неотрицательности
x1 ≥ 0, x2 ≥ 0						yi ≥ 0(i = 1, 2, 3, 4).

Решение. На основании таблицы 1. установим следующее соответствие между пере-

менными:

Переменные исходной задачи I

Первоначальные Дополнительные

x1 x2	x3 x4 x5 x6
↕ ↕	↕ ↕ ↕ ↕
y5 y6	y1 y2 y3 y4

Дополнительные Первоначальные

Переменные двойственной задачи II

Ранее эти задачи были решены симплексным методом. На последнем шаге решения каждой задачи получено:

В исходной задаче I:

F = 24 − 4/5x3 − 3/5x4,

106

F (X ) = Fmax = 24, при оттимальном базисном решении	X = (6; 4; 0; 0; 1; 3).
В двойственной задаче II:
Z = 24 + y3 + 3y4 + 6y5 + 4y6,
Z(Y = Zmin) = 24, при оптимальном базисном решении	Y = (4/5; 3/5; 0; 0; 0).
Компоненты оптимального решения двойственной задачи y1	= 4/5, y2 = 3/5,	y3 =
0, y4 = 0, y5 = 0, y6 = 0 равны (по абсолютной величине) коэффициентам при		ñîîò-

ветствующих переменных целевой функции F = 24 − 4/5x3 − 3/5x4, которую можно представить в виде

F= 24 − 4/5x3 − 3/5x4 − 0x5 − 0x6 − 0x1 − 0x2,

àкомпоненты оптимального решения исходной задачи x1 = 6, x2 = 4, x3 = 0, x4 = 0, x5 = 1, x6 = 3 равны коэффициентам при соответствующих переменных целевой

функции Z = 24 + y3 + 3y4 + 6y5 + 4y6, которую можно представить в виде

Z = Z = 24 + y3 + 3y4 + 6y5 + 4y6 + 0y1 + 0y2 + 1y3 + 3y4.

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

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

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

	F = −x1 + 2x2 → max
при ограничениях		−2x1 + x2 ≤ −1,
		x1 − 4x2 ≥ −24,
		x1 − x2 ≤ 3,
		x1 + x2 ≥ 5,
			≥
		x1	0,
		x2	≥ 0.

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

ственности.

Решение. Решая задачу симплексным методом, получим на последнем шаге решения (рекомендуем убедиться в этом самостоятельно): F = 10 − 2/7x3 − 3/7x4, ò.å. Fmax = 10 при оптимальном базисном решении X = (4, 7, 0, 0, 6, 6).

В данной задаче таблица 1 примет вид:

Переменные исходной задачи I

Первоначальные Дополнительные

x1 x2	x3 x4 x5 x6
↕ ↕	↕ ↕ ↕ ↕
y5 y6	y1 y2 y3 y4

Дополнительные Первоначальные

Переменные двойственной задачи II

107

На основании первой теоремы двойственности Zmin = Fmax = 10. На основании второй теоремы двойственности оптимальное решение двойственной задачи Y = (2/7, 3/7, 0, 0, 0, 0)

ò.ê. y1 = 2/7, т.е. коэффициенту при соответствующей переменной x3 в выражении це- левой функции F, аналогично: y2 = 3/7, y3 = y4 = y5 = y6 = 0 из за отсутствия соот-

ветствующих переменных в выражении F. Итак, в двойственной задаче Zmin = 10 ïðè

Y = (2/7, 3/7, 0, 0, 0, 0).

Метод, при котором вначале симплексным методом решается двойственная зада-

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

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

Тема 6. Транспортная задача.

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

6.1. Экономико математическая модель ТЗ.

Простейшими ТЗ являются задачи о перевозке некоторого однородного груза из пунктов отправления (от поставщиков) в пункты назначения (к потребителю) при обеспечении минимальных затрат на перевозки.

Обычно начальные условия таких задач записывают в таблицу.

Например, для k поставщиков с мощностями a1, a2, . . . , ak и l потребителей с потреби- тельским спросом b1, b2, . . . , bl такая таблица имеет следующий вид:

Поставщики	Мощности
	поставщиков	1		2		. . .	l
		b1		b2		. . .	bl
1	a1	c11		c12		. . .	c1l
			x11		x12	. . .	x1l
2	a2	c21		c22		. . .	c2l
			x21		x22	. . .	x2l
. . .	. . .	. . .		. . .		. . .	. . .
k	ak	ck1		ck2		. . .	ckl
			xk1		xk2	. . .	xkl

Здесь показатели cij означают затраты (тарифы, коэффициенты затрат) на перевозку единицы груза от i−го поставщика к j−му потребители.

Составим экономико математическую модель задачи. Обозначим через xij поставку (количество) груза, которое планируется к перевозке от i−го поставщика к j−òîìó ïî-

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

F = c11x11 + c12x12 + . . . + cijxij + . . . + cklxkl → min .

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

	x11 + x12 + . . . + x1l;
		+ x22 + . . . + x2l;
x21
		. . .
		+ xk2 + . . . + xkl.
xk1

(1)

(2)

108

	x11 + x21 + . . . + xk1;
		+ x22	+ . . . + xk2;
x12
			. . .
			+ . . . + xkl.
x1l + x2l
		xij	≥ 0.

Задача (1) (4) и является экономико математической моделью ТЗ.

Особенности экономико математической модели ТЗ.

(3)

(4)

1)Система функциональных ограничений ТЗ есть система уравнений, т.е. модель ТЗ задана в каноническом виде.

2)Все коэффициенты при переменных в системах равны 1 или 0.

3)Каждая переменная xij входит в систему функциональных ограничений дважды,

поэтому число основных переменных решения такой системы на каждом шаге должно быть k + l − 1. Это условие является условием допустимости (базизности) решения.

4) В каждой ТЗ ищем min целевой функции.

Специфичность экономико математической модели ТЗ привела к появлению особого метода ее решения распределительного метода, а в дальнейшем к различным его модификациям. Однако теоретические предпосылки симплексного метода, сохраняются.

Определение. Любое решение ТЗ (x11; x12; . . . xkl) называется распределением поста- вок. Т.к. поставки xij не могут быть отрицательными, то любое решение ТЗ всегда

является допустимым.

При распределительном методе решения ТЗ последовательно используются расчетные таблицы, соответствующие тому или иному шагу решения. Каждая такая таблица вклю- чает определенное распределение поставок. Т.к. распределение поставок должно соответствовать базисному решению, то и клетки таблицы должны соответствовать основным

(базисным) и свободным переменным.

Определение. Если суммарные мощности всех поставщиков равны суммарному потребительскому спросу всех потребителей, т.е.

k	l
∑	∑
ai =	bj,
i=1	j=1

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

В этом случае, заполненных клеток ровно k + l − 1 .

Пример.

Поставщики	Мощности
	поставщиков	1		2		3		4
		10		50		60		10
1	20	5		3		1		4
			10		10
2	50	2		1		6		7
					30		20
3	40	3		2		2		4
							40
4	20	4		2		5		1
					10			10

109

Данная задача является закрытой, т.к.

∑	∑j
k	l
ai =	bj = 130.
i=1	=1

Количество заполненных клеток 4 + 4 − 1 = 7.

6.2. Первоначальное распределение поставок.

Существует два метода:

1)Метод северо западного угла;

2)Метод учета наименьших затрат.

Метод северо западного угла: Заполнение таблицы начинается с клетки 11 (с северозападного угла), ступенями спускаются вниз до клетки kl, вычеркивая либо строку,

либо один столбец. На последнем шаге вычеркивается последняя kя строка и последний l−й столбец. При практическом заполнении таблицы вычеркивание строк и столбцов

производится лишь мысленно.

Пример.

	85	65	80	75	70
100	4	2	3	1	2
	85	15
125	6	5	3	4	3
		50	75
75	1	2	5	6	5
			5	70
75	6	4	5	2	3
				5	75

Количество заполненных клеток равно 8.

F1 = 340 + 30 + 250 + 225 + 25 + 420 + 10 + 210 = 1510 äåí.åä.

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

Пример. Заполним предыдущую таблицу методом учета наименьших затрат

	85	65	80	75	70
100	4	2	3	1	2
		25		75
125	6	5	3	4	3
			80		45
75	1	2	5	6	5
	75
75	6	4	5	2	3
	10	40			25

110