Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

задаче, и y0 , допустимый в двойственной задаче, такие, что

cT x0 bT y0 , то x0 - решение исходной, а y0 - решение

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

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

Теорема 2. (Вторая теорема двойственности) Для того,

чтобы допустимая в исходной задаче точка x0 и допустимая в двойственной задаче точка y0 являлись соответственно

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

a y0

1, n

или (x0 )T (c

AT y0 )

0 ;

a y0

1, m

или ( y0 )T (b

Ax0 )

0 .

Замечание 1. B симплекс - процедуре осуществляется перебор базисов В (невырожденных) подматриц исходной матрицы А таким образом, что


1.		На каждой итерации метода вектор xB		x , где
			0
		B 1b , является допустимым в исходной задаче, т.е.
	x	B 1b , является допустимым в исходной задаче, т.е.
AxB b , xB 0 ;
2.		На заключительной итерации, кроме случая, когда

получена оптимальная точка, оценки всех векторов Aj неотрицательны:

cT B 1 A c 0 , j 1, n

j B j j

или

cBT B 1 A yT A AT y c ,

т.е. вектор cBT B 1 является допустимым в двойственной

113

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

выполняется в виде равенств ( AT y) j c j , j I , где I - множество базисных индексов (так как оценки базисных

векторов всегда равны нулю	j	0, j I ). Такие точки у
	j

называются базисными в двойственной задаче.

Пример 1. На основании графического анализа двойственной задачи исследовать разрешимость следующих задач, и в случае разрешимости найти оптимальное значение целевой функции.

à) 6x1	9x2 3x3				min		á) 2x1	x2	2x3		min
x1	2x2		x3	3,			x1	x2	x3	2,
3x1	x2	x3		1,			x1	3x2	2x3		1,
x1	0,	x2		0, x3		0.	x1	0,	x2	0,	x3 0.
â) 5x1	x2	x3	x4		max
4x1	x3	x4	16,
6x1	4x2	x3		x4	4,
x1	0, x2		0,	x3	0,	x4	0.

Решение.

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

3y1	y2		max
y1	3y2		6,
2 y1	y2		9,
y1	y2	3,
y1	0,	y2	0.

Графическое решение данной задачи (рис. 4.5.1) показывает,

что Y *	(4,1)	с z*	13.
max		max

114

x2	2
	2
	1
	3
	y*
	x1
Рисунок 4.5.1 – Графическое решение задачи

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

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

2 y1	y2	max
y1	y2	2,
y1	3y2	1,
y1	2 y2	2.

Графический анализ показывает (рис. 4.5.2), что двойственная задача неразрешима из-за неограниченности целевой функции, поэтому по свойству 3 исходная задача неразрешима из-за пустоты допустимого множества.

x2 1

Рисунок 4.5.2 – Неограниченная целевая функция

115

в) Двойственная задача запишется в виде:
16 y1		4 y2		min
4 y1		6 y2		5
4 y2		1
y1	y2		1
y1	y2		1
y1 , y2		0.
Графический анализ этой задачи показан на рис.4.5.3.
y2
				y1
				y*
Рисунок 4.5.3 – Графическое решение двойственной задачи

Оптимальным		решением	является вектор Y *		13	,	1	,

			min	8			4

zmin*	25 . На	основании	второй теоремы двойственности				для

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

x1* (4 y1*		6 y2* 5) 0 ,	x3* ( y1*		y2*	1) 0,
x* ( 4 y*		1) 0 ,	x* ( y*		y*	1) 0 .
2	2		4	1	2

Подставляя координаты вектора Y *		, получаем, что переменные x
	min	3
и x4	исходной задачи должны обращаться в ноль. Тогда из исходной
системы получаем 4x1 16 , откуда		x1 4 , и 6x1 4x2 4 , откуда
x2	5 . Следовательно, решением исходной задачи является вектор
	116

Xmax*	(4,5,0,0) . При этом zmax*	5* 4 5 25 .
	Задачи для самостоятельного решения

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

4.5.1 6 x1	+ 4 x2		min,	4.5.2	2 x1	+	3 x2	min,
2 x1	+	x2	3,		x1	+	5 x2	16,
x1 –		x2	1,		3 x1	+	2 x2	12,
– x1 + 2 x2			1;		2 x1	+	4 x2	16;
4.5.3 –6 x1 – 4 x2			max,	4.5.4	6 x1	+	4 x2	min,
2 x1 + x2			3,		2 x1 + x2			3,
x1 – 2 x2			2,		3 x1 + 2 x2			1,
3 x1 + 2 x2			1;		– x1 – x2			6;
4.5.5 7 x1	+	x2	min,	4.5.6	7 x1	+ 10 x2		min,
x1	+	x2	3,		2 x1	+	28 x2	17,
5 x1 + x2			5,		x1 + 2 x2			3;
x1	+ 5 x2		5;		x1	+ 17 x2		19;

4.5.7	x1 + x2 + 2 x3		min,
	2 x1 – x2 – 3 x3 + x4			= – 3,
	x1 – 3 x2 – 4 x3		+ x5 = – 1;
4.5.8 –15x1 – 33 x2			max,	4.5.9	x1	+ 2 x2	min,
	3 x1 +	2 x2	6,		2 x1	+ x2	18,
	6 x1 +	x2	6;		x1	+ 2 x2	14,
					x1 – 2 x2		10;

117

Источник: https://studfile.net/preview/16565974/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)