Матан_ЛинПрог

	1		P2	-1		3	-2/3	1	-1/3	0	0		-----
	2		P4	0		8		0	-2/3	1	0		-----
							-1/3
II
	3		P5	0		5	5/3	0	1/3	0	1		5:5/3=3
	4		j		f1	4	-4/3	0	1/3	0	0		X1=(0;3;0;8;5)
							↑
	1		P2	-1		5	0	1	-1/5	0	2/5
III	2		P4	0		9	0	0	-3/5	1	1/5
	3		P1	2		3	1	0	1/5	0	3/5
	4		j		f2 1		0	0	2/5	0	1/5		Х*=(3;5;0;9;0)

Таблица II -ой итерации содержит только четыре строки, т.к. искусственный вектор из базиса исключен. В ней видно, что опорным является план X1 (0; 3; 0; 8; 5). Проверим его на оптимальность. Вычислим все j . Среди них есть отрицательное число (-4/3). Следовательно, данный

опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора P1. Из базиса исключается вектор P5 . Составим III

итерацию. В 4-ой строке среди j нет отрицательных чисел. Это означает,

что найденный опорный план исходной задачи																						X				(3; 5; 0; 9; 0)										является
оптимальным. При этом плане значение Fmax																			1 5 0 9 2 3 1.
Упражнения
Решить методом искусственного базиса задачи:
5.1. F x1									2x2					5x3			max	5.2. F 3x1								3x2							4x3		max
2x1 2x2 4x3 18																		2x1 x2 3x3 18
	2x x				2			3x				3	20					4x								5x					3		12
	1																			1
		3x2							6x3 19
5x1																		3x1 2x2 x3 14
x , x			2	, x			3		0									x , x				2	, x			3	0
	1																			1
5.3. F 6x1 x2														3x3			max	5.4. F 2x1								5x2							4x3 min
3x1 7x2 5x3 15																		4x1 2x2 3x3 9
		3x2							4x3 16																	5x3 8
2x1																		3x1 2x2
6x 5x						2			8x				3	12				x 3x					2		4x				3			12
	1																		1
x , x			2	, x			3		0									x , x			2	, x			3	0
	1																		1
5.5. F 3x1 4x2																6x3 min		5.6. F 2x1 2x2															3x3		4x4	max
2x1 3x2 x3 8																		x1 2x2 x3 x4 2
	3x 2x									2	2x				3	10			2x x					2	2x					3			3x	4	3
		1																		1
		4x2							x3 7																	5x3 2x4 4
5x1																		3x1 4x2
x , x			2	, x			3		0									x , x			2	, x			3	,х		4		0
	1																		1

5.7. F 2x1 x2 x3 x4 min

x1 x2 2x3 x4 2

2x1 x2 3x3 x4 6x1 x2 x3 x4 7

x1, x2, x3,х4 0

5.9. F 2x1 3x2 5/2x3 min

2x1 x2 3x3 6

2x1 4x2 3x3 16

3x1 4x2 2x3 12

x1, x2, x3 0

5.11. F 2x1 x2 x3 x4 min

x1 x2 2x3 x4 2

2x1 x2 3x3 x4 6x1 x2 x3 x4 7

x1, x2, x3,х4 0

5.13. F x1 2x2 x3 min

x1 4x2 2x3 6

x1 x2 2x3 62x1 x2 2x3 4

x1, x2, x3 0

5.15. F 2x1 x2 5x3 min

x1 x2 x3 4

x1 5x2 x3 52x1 x2 3x3 6x1, x2, x3 0

5.17. F x1 2x2 max

x1 x2 1

2x1 x2 2

x1 x2 4

x1 3

x , x 0

1 2

5.19. F x1 2x2 min

5.8. F 5x1 2x2 x3 max

2x1 x2 x3 5

3x1 2x2 x3 65x1 3x2 4x3 1x1, x2, x3 0

5.10. F 4x1 6x2 3x3 min

3x1 x2 2x3 9

		2x2				2x3 8
x1
x		6x			2		12
	1
x , x			2	, x		3	0
	1

5.12.F x1 2x2 3x3 10x4 max

x1 x2 2x3 6x4 1

x1 x2 4x3 8x4 14x1 2x2 x3 4x4 3

x1, x2, x3,х4 0

5.14. F x1 2x2 3x3 10x4 min

2x1 x2 x3 1

4x1 2x2 x3 2

3x1 x3 5x1, x2, x3 0

5.16.F 2x1 2x2 3x3 4x4 max

x1 2x2 x3 x4 2

2x1 x2 2x3 3x4 33x1 4x2 5x3 2x4 4

x1, x2, x3,х4 0

5.18. F x1 3x2 min

x1 2x2 2

x1 2x2 3

x1 2x2 6

x1 x2 0

x , x 0

1 2

5.20. F 4x1 5x2 6x3 max

x1 x2				0		x1 x2 2x3 2
	2x x			2	3	x 5x				2	x		3	1
	1						1
x x			2	1		x x			2	3x			3	5
	1						1
x , x		2	0			x , x		2	, x		3	0
	1						1

§6. Двойственные задачи линейного программирования

Каждой задаче линейного программирования (1.1)-(1.3) можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной (сопряженной) по отношению к исходной (прямой).

Задача, состоящая в нахождении минимального (максимального) значения функции:

Z b1y1 b2 y2

... bn yn min ( max)

(6.1)

при условиях

a11y1 a21y2 ...

am1ym c1

a y a

22

y

2

...

a

m2

y

m

c

2

12

1

........................................

y1 a2l y2

aml ym

cl

(6.2)

a1l

...

a

y a

2l 1

y

2

... a

ml 1

y

m

c

l 1

1l 1 1

..........

..........

..........

..........

a y a

2n

y

2

...

a

mn

y

m

c

n

1n

1

yi

0 (i

, k m),

(6.3)

1,k

называется двойственной по отношению к задаче (1.1)-(1.3).

Задачи (1.1)-(1.3) и (6.1)-(6.3) образуют пару задач, называемую в линейном программировании двойственной парой.

Сравнивая две сформулированные задачи, видим, что двойственная задача по отношению к исходной составляется согласно следующим правилам:

1.Целевая функция исходной задачи (1.1)-(1.3) задается на максимум, а целевая функция двойственной (6.1)-(6.3) - на минимум.

2.Матрица A, составленная из коэффициентов при неизвестных в системе ограничений (1.2) исходной задачи, и аналогичная матрица A в двойственной задаче (6.2) получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками):

		а	а	...	а
		11	12	...	1n
A	а21		а22		а2n		,
			...	...	...
	...
		аm1	аm2	...
					аmn

		а	а		21	...	а	m1
		11				...
A	а12		а22				аm2
			... ... ...
	...
		а	а	2m		...	а	mn
		1n

.

3.Число переменных в двойственной задаче равно числу соотношений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.

4.Коэффициентами при неизвестных в целевой функции (6.1) двойственной задачи являются свободные члены в системе (1.2) исходной задачи, а правыми частями в соотношениях системы (6.2) двойственной задачи – коэффициенты при неизвестных в целевой функции (1.1) исходной задачи.

5.Если переменная xj исходной задачи может принимать лишь

положительные значения, то j-е условие в системе (6.2) двойственной задачи является неравенством вида « ». Если же переменная xj может принимать как положительные, так и отрицательные значения, то j-е соотношение в системе (6.2) представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i-е соотношение в системе (1.2) исходной задачи является неравенством, то i-я переменная двойственной задачи принимает положительное значение ( yi 0). В противном случае переменная yi может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. Если в симметричной паре двойственных задач ограничения (1.2) прямой задачи заданы только в виде неравенств « », а соотношения (6.2) двойственной задачи являются неравенствами вида « », то такие задачи называются симметричными. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

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

n

n

F cj xj

max

или

F cj xj

min

j 1

j 1

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

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

n

n

bi ,

(i 1,k)

bi ,

(i 1,k)

aij xj

aij xj

j 1

j 1

n

n

aij xj

bi ,

(i

)

aij xj

bi ,

(i

)

k 1,m

k 1,m

j 1

j 1

xj 0

( j

; l n)

xj 0

( j

; l n)

1,l

1,l

Каждая из задач двойственной пары (1.1)-(1.3) и (6.1)-(6.3) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.

Если одна из пары двойственных задач - (1.1)-(1.3) или (6.1)-(6.3) - имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т.е.

Fmax (X*) Zmin (Y*). Если же целевая функция одной из пары двойственных задач не ограничена, то другая задача вообще не имеет планов.

Экономическая интерпретация двойственных задач

Двойственные задачи могут быть экономически интерпретированы следующим образом:

Исходная задача. Сколько и какой продукции xj ( j 1,n) необходимо произвести, чтобы при заданных стоимостях cj ( j 1,n) единицы продукции

и	размерах имеющихся ресурсов bi (i 1,m)	максимизировать					выпуск
продукции в стоимостном выражении.
	Двойственная задача. Какова должна быть цена уi (i					)	единицы
					1,m
каждого из ресурсов, чтобы при заданных количествах ресурсов bi							(i		)
								1,m
и	величинах стоимости единицы продукции cj	( j		) минимизировать
			1,n

общую стоимость затрат.

Переменные уi называются оценками или учетными, неявными ценами. Рассмотрим на примере.

Задача 1. Для производства трёх видов изделий A, B и C используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице.

	ВИДЫ СЫРЬЯ	НОРМЫ ЗАТРАТ СЫРЬЯ (КГ)
		НА ЕДИНИЦУ ПРОДУКЦИИ
		А	В	С
	I	4	2	1
	II	3	1	3
	III	1	2	5
	ЦЕНА ЕД.	10	14	12
	ПРОДУКЦИИ

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

Решение. Предположим, что производится x1 изделий A, x2 изделий B и x3 изделий C. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

Fmax 10x1 14x2	12x3	(1)
при следующих условиях:

4x 2x				x		180
	1		2		3	210	(2)
3x1 x2			3x3
x	2x	2	5x		3	244
1
x1 0,x2			0,x3			0	(3)
Припишем каждому из видов сырья,							используемых для производства

продукции, двойственную оценку, соответственно равную y1, y2, y3. Тогда общая оценка сырья, используемого на производства продукции, составит

Zmin 180y1 210y2

244y3.

(4)

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

4y		3y			y		10
	1	y2		2		3	14	(5)
2y1				2y3
y	3y		2	5y		3	12
1
y1 0, y2				0, y3			0	(6)

Как видно, задачи (1)-(3) и (4)-(6) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A, B, и C, а решение двойственной - оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой-либо одной из них. Так как система ограничений задачи (1)-(3) содержит лишь неравенство вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице.

Баз	C	В	10	14	12	0	0	0
			P1	P2	P3	P4	P5	P6
ис
P2	14	82	19/8	1	0	5/8	0	-1/8
P5	0	80	23/8	0	0	1/8	1	-5/8
P3	12	16	-3/4	0	1	-1/4	0	1/4
		F=1340	57/4	0	0	23/4	0	5/4

Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия B и 16 изделий C. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 тенге.

Из таблицы также видно, что оптимальным решением двойственной

задачи является y* 23/4;	y* 0;	y* 5/4.
1	2	3

Переменные y1* и y3* обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье I и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 тенге и станет равной 1340+5,75=1345,75 тенге. При этом числа, стоящие в столбце вектора P4 таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделии B на 5/8 ед. и сокращения выпуска изделии C на 1/4 ед. Вследствие этого использование сырья II вида уменьшается на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделии, при котором общая стоимость изготовляемой продукции возрастут на 1,25 тенге и составит 1340+1,25=1341,25 тенге. Это будет достигнуто в результате увеличения выпуска изделии C на 1/4 ед. и уменьшения изготовления изделии B на 1/8 ед., причем объём используемого сырья II вида увеличивается на 5/8 кг.

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

Zmin 180 (23/4) 210 0 244 (5/4) 1340,

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

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем:

4 (23/4) 3 0 5/4 10

2 (23/4) 0 2 (5/4) 14.

23/4 3 0 5 (5/4) 12

Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида A, выше цены этого изделия и, следовательно, выпускать изделия вида A не выгодно. Его производство и не

предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий B и C, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

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

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

Задача 2. Составить двойственную задачу по отношению к задаче,

состоящей в максимизации функции

		F 2x1			x2		3x3 ,		(7)
	x 3x				5x			12
при		1		2			3	24	(8)
		2x1 x2			4x3
		3x	x		2	x	3	18
		1

x1, x2, x3 0						(9)
Решение. Для данной задачи
1 3		5	1	2	3
	1
A 2		4	и A 3	1 1 .
				4	1
3 1		1	5

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

системе (8), т.е. равно трем. Коэффициентами в целевой функции

двойственной задачи являются свободные члены системы уравнений (8), т.е.

числа 12, 24, 18.

Целевая функция исходной задачи (7)-(9) исследуется на максимум, а система условий (8) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида « ». Следовательно, для задачи (7)-(9) двойственная задача такова: найти минимум функции

F* 12 y 24 y			2	18 y				3
	1
	y 2y					3y			2
при условиях		1			2			3	1 .
		3y1	y2				y3
	5y 4y					2	y	3	3
		1

Задача 3. Для задачи, состоящей в минимизации функции

F 4x1 x2 4x3

2x1 x2 4x3 12

x1 3x2 2x3 13

при условиях

2x1 5x2 6x3 11

x1, x2, x3 0

сформулировать двойственную задачу.

Решение. Приведем сначала исходную задачу к соответствующему

виду, умножив первое и третье неравенства на (-1). Получим:

Fmin 4x1 x2 4x3

			2x1 x2 4x3 12
			x 3x				2	2x				3	13
при условиях				1											11.
			2x		5x					2	6x			3
				1
			x , x		2	,		x	3		0
				1
	Для данной задачи
2	1	4						2						1 2
A 1	3 2			и A 1										3 5 .
	5 6									4			2 6
2

Всоответствии с общими правилами задача, двойственная по отношению

кданной, формулируется следующим образом: найти максимум функции

F* 12 y1 13 y2 11 y3

	2y1 y2 2y3 4
	y	3y			2	5y			3	1
при условиях	1											4
	4y			2y				6y
		1					2				3
	y , y		3	0
	1

Упражнения

Сформулируйте двойственные задачи по отношению к задачам:

6.1. F 2x1 x2 x3 x4

min

6.2. F 2x1 2x2 3x3 4x4

max

x1 x2 2x3 x4 2

2x1 x2 3x3 x4 6

x1 x2 x3 x4 7x1, x2,х4 0

6.3. F x1 2x2 x3 minx1 4x2 2x3 6

x1 x2 2x3 6

2x1 x2 2x3 4x1, x3 0

6.5. F 2x1 x2 5x3 min

x1 x2 x3 4

x1 5x2 x3 5

2x1 x2 3x3 6x1, x2 0

6.7. F x1 2x2 max

x1 x2 1

2x1 x2 2

x1 x2 4

x1 3

x 02

6.9. F x1 2x2 min

x1 x2 0

2x1 x2 3x1 x2 1

x1 0

6.11. F x1 2x2 5x3 max

2x1 2x2 4x3 18

2x1 x2 3x3 20

5x1 3x2 6x3 19

x1,x3 0

6.13. F 6x1 x2 3x3 max

x1 2x2 x3 x4 2

2x1 x2 2x3 3x4 33x1 4x2 5x3 2x4 4

x1, x2, x3,х4 0

6.4. F x1 2x2 3x3 10x4 min

2x1 x2 x3 1

4x1 2x2 x3 2

3x1 x3 5x1, x2, x3 0

6.6. F x1 2x2 3x3 10x4 max

x1 x2 2x3 6x4 1

x1 x2 4x3 8x4 14x1 2x2 x3 4x4 3x2, x3,х4 0

6.8.F x1 3x2 min

x1 2x2 2

x1 2x2 3

x1 2x2 6

x1 x2 0

x , x 0

1 2

6.10. F 4x1 5x2 6x3 max

x1 x2 2x3 2

x1 5x2 x3 1x1 x2 3x3 5x1, x2, x3 0

6.12. F 3x1 3x2 4x3 max

2x1 x2 3x3 18

	4x	5x	3	12
	1
		2x2 x3 14
3x1
		x3 0
x2,

6.14. F 2x1 5x2 4x3 min