2. Контрольные задания

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

1)	F=x1+x2→max		2)	F=3x1+x2→min
3)	F=3x1+3x2→min		4)	F=6x1-5x2→max
5)	F=8x1+2x2→max		6)	F=x1+2x2→max
7)	F=14x1+10x2+14x3+14x4→max		8)	F=2x1+3x2→min
9)	F=5x1+4x2+6x3→max		10)	F=-7x1+2x2→min
11)	F=6x1+4x2→min		12)	F=-x1-2x2→min
13)	F=3x1+3x2→max		14)	F=-2x1-x2→min
15)	F=7x1-2x2→max		16)	F=3x1+x2+2x3→max
17)	F=6x1-x2→min		18)	F=-3x1-2x2→max
19)	F=2x1+x2-3x3→max		20)	F=2x1+x2-3x3→max
21)	F=x1+2x2→max		22)	F=3x1-2x2+x3→max
23)	F=5x1-2x2→max		24)	F=5x1-2x2→max
25)	F=3x1+3x2→max		26)	F=5x1+6x2-2x3+3x4→min
27)	F=4x1-4x2-4x3+3x4+3x5→min		28)	F=3x1+42x2+6x3-4x4→min

Тема 3. Двойственный симплекс-метод

Основан на связи между решениями прямой и двойственной задач.

Рассмотрим задачу ЛП, представленную в канонической форме:

(3.1)

(3.2)

(3.3)

и задачу двойственную к ней

(3.4)

(3.5)

Пусть Y=(y₁, y₂, …, y_m)– опорный план задачи 4), 5).

Базисом опорного плана задачи 4), 5) либо сопряженным базисом, называется произвольная система mлинейно независимых векторовусловий задачи 1)-3), для которых не болееm ограничений 5) выполняются как строгие равенства и найденное решение удовлетворяет всем неравенствам 5).

Свяжем с каждым сопряженным базисом Б_у = m–мерный векторХ=(х₁, х₂, … , х_m), компоненты которого удовлетворяют условиям 2) исходной задачи.

Вектор Х=(х₁, х₂, … , х_m), компоненты которого равны коэффициентам разложения вектораА₀=(b₁,b₂, … ,b_m)по системеБ_у = называется псевдопланом задачи 1)-3).

Признак оптимальности. Если среди базисных компонентов псевдопланаХ=(х₁, х₂, … , х_m)нет отрицательных, т.е. все, то псевдоплан Х-решение задачи 1)-3).

Свяжем с каждым сопряженным базисом Б_у = матрицу(Х_ij), элементы которой совпадают с коэффициентами разложения векторов условийА_j задачи 1)-3) по системеБ_у.

Пусть среди базисных компонентов псевдоплана Х=(х₁, х₂, … , х_m) имеются отрицательные. Если среди компонентовх_iо<0 найдется хотя бы один, для которого всех_ij0, то целевая функция задачи 4)-5) не ограничена снизу на множестве ее планов, а прямая задача 1)-3) не разрешима.

Если среди базисных компонентов Хнайдется хотя бы один, для которого существуетх_ij<0, то псевдоплан можно улучшать.

Для того, чтобы получить базис нового псевдоплана Х^л, нужно вывести из базиса псевдопланаХвекторА_r(x_rj<0).

Если х_i0<0при нескольких значенияхr,из базиса нужно вывести вектор сminх_r0. Для определения вектора, который нужно ввести в базис, необходимо найти номерk, на котором достигается минимум отношения.

В базис вводится вектор Ак и определяются параметры следующей итерации по формуле:

F=8x₁+6x₂→max6)

2х₁+5х₂≤11

4х₁+х₂≤10 7)

х₁, х₂≥0 8)

Приведем к каноническому виду

А1	А2		А3	А4	А0
2х1	+ 5х2		+ 1х3	+ 0х4	= 11
4х1	+ х2	+0 х3		+ 1^.х4	= 10

Запишем двойственную к ней

F*=11у₁+10у₂→min

2y₁+4y₂≥8 A₁

5y₁+ y₂ ≥6 A₂

y₁ ≥0 A₃

y₂ ≥0 A₄

Возьмем в качестве сопряженного базиса вектора А₁, А₃и из системы

2у₁ +4у₂ = 8

у₁ = 0найдем значение опорного плана двойственной

задачи у₁ =0, у₂ =2

Данный базис не может быть взят в качестве сопряженного, т.к. второе ограничение не выполняется ().

Возьмем сопряженным базисом А₂, А₃. Из системы

5у₁ + у₂ = 6

у₁ = 0находим значенияу₁ =0, у₂ =6.

Неравенство при этих значенияху₁иу₂выполняется и, следовательно, система{ А₂, А₃} является сопряженным базисом.

Определяем коэффициенты разложения небазисных векторов по векторам базиса и находим псевдопланы исходной задачи:

А₀ = А₂х₂₀ +А₃х₃₀

х₂₀= 10; х₃₀= -39

А₁ = А₂х₂₁ +А₃х₃₁

х₂₁= 4; х₃₁ = -18

А₄ = А₂х₂₄ +А₃х₃₄

х₂₄= 1; х₃₄ = -5

Аб	Сб	А0	8	6	0	0
			А1	А2	А3	А4
А2	6	10	4	1	0	1
А3	0	-39	-18	0	1	-5
		60	16	0	0	6
	Θ	-	16/18	-	-	6/5

А2	6	4/3	0	1	2/9	1/9
А1	8	39/18 (13/6)	1	0		5/18	(-4)
		60	16	0	0	6

Двойственный симплекс-метод целесообразнее использовать при решении ЗЛП, в которой нужно вводить фиктивные переменные.

F=3x1+2x2+5x3→min 2x1-3x2+x3 ≥ 10 4x1+x2+2x3 ≥ 15 xj ≥ 0 (j=)		=-3x1-2x2-5x3→max 2x1-3x2+x3 –x4 = 10 4x1+x2+2x3 –x5= 15
		Двойственная задача F*=10у1+15у2→min 2у1+4у2 ≥-3 А1 -3у1+ у2 ≥-2 А2 у1 +2у2 ≥-5 А3 -у1 ≥ 0 А4 -у2 ≥ 0 А5

{А₄, А₅} – сопряженный базис→у₁=0; у₂=0

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

Аб	Сб	А0	-3	-2	-5	0	0
			А1	А2	А3	А4	А5
А4	0	-10	-2	3	-1	1	0
А5	0	-15	-4	-1	-2	0	1
		0	3	2	5	0	0
	θ		3/4	2	5/2

А4	0	-5/2	0	7/2	0	1	-1/2
А1	-3	15/4	1	1/4	1/2	0	-1/4	(2)
		-45/4	0	5/4	7/2	0	3/4
	θ

А5	0	5	0	-7	0	-2	1	(1/4)
А1	-3	5	1	-3/2	1/2	-1/2	0
		-15

Fmin = 15, x₁ = 5; x₂= … = 0