Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Киевский национальный университет им. Т. Шевченко

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

ИсследованиеОпераций

.pdf

Скачиваний:

Добавлен:

07.03.2016

Размер:

1.89 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 78 / 118 9 10 11 > Следующая >>>

	1			0	0				1			0	0
		0	1		0	,	B	−1		0	1		0	,	x	0	T
B(0) =[ A , A , A ] =		0	1		0	,	B		(0) =	0	1		0	,	x		= (0;0;2;4;6) .
3 4 5		0		0	1					0		0	1
		0		0	1					0		0	1

Запишемо коефіцієнти задачі в допоміжну таблицю 15. Зміст її стовпчиків та рядків зрозумілий із відповідних позначень.

Допоміжна таблиця 15.

		№		A1		A2		A3		A4	A5		y0				y1						y2
	ряд.
			1	–1		1		1		0	0		0				0						0
			2	1		–1		0		1	0		0				4						1
			3	1		1		0		0	1		0				0						3
		c j		4		2		0		0	0	→ max
		∆0j		–4		–2		0		0	0	Основні формули, що
												використовуються:
		∆1j		0		–6		0		4	0	( ys )T		= cбT (s)B−1(s) ,				s =0,1,2,... ,
		∆2j		0		0		0		1	3	∆sj = ( ys )T Aj −c j , j =							1, n		.
				У основну таблицю 16 записуємо обернену до базисної матрицю
B−1 (s) , вектор						α0 ,	α0 = B−1(0) A , а також допоміжні інформаційні стовпчики,,
						0	0			0
зміст яких також зрозумілий з позначень.
				Пояснення				до	основної		таблиці.		Обчислюємо:					y0		= (c		б	,bs ) = 0,
						y30 = (cб,b3s ) = 0. Отже, (y0 )T = (0;0;0).												1				б		1
y20 = (cб,b2s ) = 0,						y30 = (cб,b3s ) = 0. Отже, (y0 )T = (0;0;0).
				Переписуємо вектор						y0 у відповідний стовпчик допоміжної таблиці,
та обчислюємо симплекс-оцінки: ∆0											= ( y0 ,	A ) −c		1	= −4,	∆0	= ( y0 ,			A ) −c				2	= −2,
										1		1		1		2				2				2
∆03 = ∆04 = ∆05 = 0.
				Початковий опорний план							x0 = (0;0;2;4;6)T неоптимальний,											оскільки
∆		j	<0	, з них найменша					∆0 = −4 . Вектор			A	введемо у базис. Переписуємо
		j							1			1
його у основну таблицю та обчислюємо												α0	= B−1(0) A			= (−1;1;1)T				. Знаходимо
												1			1
номер				l	направляючого					рядка	для	перетворення					Жордана-Гаусса:
l = arg minθi					= 2 .
			i=2,3
				Обчислюємо B −1 (1)						та вектор α1 ,			за формулами Жордана-Гаусса
												0
(8.12),				з ведучим 2-м рядком і стовпчиком α10 на частині основної симплекс-
											71

таблиці, що містить вектор α00					та матрицю B−1(0)			(обведена жирною лінією).
Результат записуємо у таблицю кроку 1.									Основна таблиця 16.
									Основна таблиця 16.
№	c	x	б	αs		B−1 (s)		A	α0	θ	i
кр.	б		б	0	bs	bs	bs	1	1		i
					1	2	3
	0		x3	2	1	0	0	–1	–1
0	0	← x4		4	0	1	0	1	1	θ2 = 4 1
	0		x5	6	0	0	1	1	1	θ3 = 6 1
	(y0 )T		L	0	0	0	0	A2	α21
	0		x3	6	1	1	0	1	0
1	4		x1	4	0	1	0	–1	–1
	0	← x5		2	0	–1	1	1	2
	(y1 )T		L	16	0	4	0
	0		x3	6	1	1	0
2	4		x1	5	0	1 2	1 2
	2		x2	1	0	−1 2	1 2
	(y2 )T		L	22	0	1	3
	Переходимо до кроку 1, виконавши який заповнюємо основну
таблицю кроку 2, яка містить оптимальний розв'язок задачі x(2) = (5;1;6;0;0)T ,
оскільки всі оцінки ∆2j				(див. допоміжну таблицю) невід'ємні.
	Оптимальне значення цільової функції L( x(2) ) = 22 .

8.4. Вправи.

Розв’язати задачі модифікованим симплекс-методом, при необхідності використати один із методів штучного базису:

1) L = −2x3 + 2x4 + x5 → max,

2) L = x1 + x2 + 2x3 + 8x4 → min,

− 2x

+ x

+ x = 4,

− x

+ 3x

− 2x = 3,

x2 + 3x3 − x4

+ 2x5 = 2,

+ 3x2 −4x3

+ 4x4 =1,

− x1

≥0, j =1,4.

x j ≥0, j = 1,5.

x j

3)L = 5x1 + 4x2 +6 x3 → max,

x1 + x2 + x3 ≤ 6,2x1 + x2 + x3 ≥ 9,

3x1 + x2 + 2x3 ≥ 11,x1, x2 , x3 ≥0.

5)L = x1 − x2 → max,

4x1 −3x2 − x3 + x4 + x5 = 6,
	x		+ 4x	+ x		+ x		= 15,
		1	2	3		5
2x			−4x	− x		+ x	= −3,
		1	2	3		4
x		≥0, j
x	j	≥0, j		=	1,5	.
	j

7)L = x1 − 2x2 + 3x3 − x4 → max,

	2x		− x + 2x					−3x ≤ 5,
		1		2	3			4
	x1 + 2x2 − x3							+ x4 ≤ 3,
	x , x , x , x ≥						0.
		1	2	3	4
9)	L = 2x1 + 4x2 + x4 → min,
		x	− 2x		+ x			≤ 4,
		1		2	3
	2x1 + 3x2 − x3 ≥ 2,
	x , x			≥0.
		1	3
11)	L =6 x1 + 9x2 + 3x3 → min,
	− x		+ 2x		+ x			≥ 2,
		1		2	3
		3x1 + x2 − x3 ≥ 1,

		x ≥0, i			= 1,3.
		x ≥0, i			= 1,3.
		i
13)	L = 2x1 + x2 + 2x3 → min,
	− x			+ x		+ x = 2,
		1		2				3
		x1 −3x2 − 2x3 =1,

		x ≥0, i			=1,3.
		x ≥0, i			=1,3.
		i

4) L = 4x1 − 2x2 + x3 − x4 → max,

	x	− x	+ 4x	− 2x = 2,
	1	2	3	4
		+ 2x2 − x3 + 4x4 = 3,
3x1		+ 2x2 − x3 + 4x4 = 3,

			j = 1,4.
x j ≥0,			j = 1,4.

6)L = x1 + 2x2 + x3 − x4 −6 x5 → min,

− x			+ 5x			+ x				+ x	+ x	= 10,
2x		1	− x	2		+ x		3		−3x4	5	= 6,
	1		2			3				4
			10x		+ x				+ 2x		+ 3x	= 25,
			2			3				4	5
x
x	j	≥0, j =					1,5			.
	j

8)L = −x1 + x2 + x3 → max,

2x1 + x2 − 2x3 ≥1,

x1 −3x2 + x3 ≥ 4,

x1, x2 , x3 ≥0.

10)	L = 2x1 − x2 + 4x3 −6 x4 → max,
	3x		− x		+ 2x ≤ 15,
		1	2			4
		x1 + 2x2		− x3 − 2x4 ≥ −4,
		x1 + 2x2		− x3 − 2x4 ≥ −4,


	x j ≥0, j = 1,4.

12)	L = 2x1 − 2x2 + x3 + 3x4 → min,
	2x		+ 2x	− x		− x = 1,
		1	2	3		4
	− x1 + x2 + 3x3 + x4 =1,

		x	≥0, i	= 1,4.
		x	≥0, i	= 1,4.
		i
14)	L = 2x1 + 4x2 + 23x3 + 4x4 → min,
		x		−3x		+ x ≤ −2,
		1		3		4
	− x1 − x2 − 2x3 + 3x4 ≤ 2,

		x	≥0, i	= 1,4.
		x	≥0, i	= 1,4.
		i
73

15) L = 3x1 −12x2 + 4x3 → min,			16) L = 3x1 − x2 − x3 + x4 → max,
x	+ 3x	+ x ≤ −2,	3x		+ 5x	+ x	+ x = 32,
1	2	3		1	2	3	4
x1 − 4x2 + 4x3 ≥1,				x1 −3x2 − x3 + x4 = −8,

		i = 1,3.		x	≥0, i = 1,4.
x ≥0,
	i			i

9. Побудова двоїстих задач та застосування теорем двоїстості у лінійному програмуванні

9.1. Економічна інтерпретація двоїстості. Взаємодвоїсті задачі ЛП.

Розглянемо два об‘єкти, які умовно назвемо “виробництво” і “ринок” та відповідно позначимо як “В” і “Р”. Об‘єкт “В” виробляє деякі продукти і продає їх об‘єкту “Р” за фіксованими цінами. При виробництві цих продуктів об‘єкт “В” використовує деякі ресурси, обмежені запаси яких він має. Об‘єкт “В” може реалізувати довільний план виробництва продуктів, докупивши у об‘єкта “Р” необхідну кількість ресурсів, але за вільними цінами. За цими ж цінами об‘єкт “В” може також продати об‘єкту “Р” залишки невикористаних ресурсів.

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

За розглянутих умов можна ставити дві оптимізаційні задачі взаємодії об‘єктів “В” і “Р”:

а) максимізації прибутку “виробництва” при мінімізації

витрат “ринку” на обслуговування “виробництва”;
б)	мінімізації	витрат “ринку”			на обслуговування
“виробництва” при максимізації прибутку “виробництва”.
Нехай A =[A1 ,..., An		] – матриця технологічних способів виробництва,
в якій вектор	j − го способу Aj = (a1 j , a2 j ,...,anj )T ( j =				) характеризує витрати
				1, n
ресурсів на виробництво одиниці			j − го виробу; b = (b1 , b2 ,..., bm )T – вектор,
який характеризує запаси ресурсів;			c = (c1, c2 ,..., cn )T – вектор цін на вироблені
продукти на “ринку”.					x = (x1, x2 ,..., xn )T ,
Введемо два невід‘ємні вектори змінних:						який
характеризує фактичне виробництво продуктів;					y = (y1, y2 ,..., ym )T ,	який
характеризує фактичні ціни на ресурси на “ринку”.
			74

Тоді загальний прибуток “виробництва” (або, що те саме, загальні витрати “ринку”) з урахуванням можливих додаткових витрат на закупівлю

ресурсів та з оцінкою можливого прибутку від продажу запасів

невикористаних ресурсів

описується

функцією

L(x, y)= (c, x)−(y, Ax −b)

задача а) полягає у відшуканні

max min L(x, y),

(9.1)

x≥0 y≥0

а задача б) − у відшуканні

min max L(x, y).

(9.2)

y≥0 x≥0

Розглянемо задачу (9.1). Маємо:

max min L(x, y)= max min[(c, x)−(y, Ax −b)]=

x≥0 y≥0

(c, x)

при

b − Ax ≥ 0(Ax

≤ b),

= max{(c, x): Ax ≤ b}, (9.3)

= max

x≥0 (c, x)−∞

віншому випадку

x≥0

оскільки

b − Ax ≥ 0(Ax ≤ b),

min(y, Ax −b)= 0

при

y≥0

−∞ віншомувипадку.

Аналогічно, розглядаючи задачу (9.2), отримаємо

min max L(x, y)= min max[(c, x)

−(y, Ax −b)]=

y≥0 x≥0

= min max[(b, y)+(x,c − AT y)]=

(9.4)

y≥0 x≥0

y ≤ 0(c

приc − A

≤ A

(b, y)

y),

= min{(b, y): c ≤ A

y},

= min

y≥0 (b, y)+∞

віншомувипадку

≥0

оскільки

при

c − A

≤0,

max(x, c − AT y)= 0

x≥0

∞ віншомувипадку.

Задачі (9.3), (9.4) називаються взаємодвоїстими задачами лінійного програмування. Надалі задачу (9.3) відшукання оптимального плану виробництва будемо називати прямою задачею лінійного програмування, а задачу (9.4) відшукання оптимальних цін ринку на ресурси − двоїстою.

Запишемо їх так:

пряму:

cT x → max
Ax ≤ b,	(9.5)
x ≥0.
	75

двоїсту:

bT y → min
AT y ≥ c,	(9.6)
y ≥ 0.

Пару двоїстих задач (9.5), (9.6) називають симетричною. Якщо пряма задача задана у стандартній формі


n
∑c j x j → max					(9.7)
j=1
n
∑aij x j = bi , i = 1, m ,					(9.8)
j=1
x j ≥0, j =		,			(9.9)
	1, n
то двоїстою для неї називається задача
m
∑bi yi → min					(9.10)
i=1
m
∑aij y j ≥ c j , j =			1, n	.	(9.11)

i=1

Ці ж задачі, записані у матрично-векторній формі, мають вигляд:

пряма:

cT x → max
Ax = b,	(9.12)

x ≥0,

двоїста:

bT y → min

(9.13)

AT y ≥ c.

Задачі (9.12), (9.13) називають несиметричною парою двоїстих задач.

Зауважимо, що двоїста задача, записана правильно, якщо двоїста задача, записана по відношенню до двоїстої, буде збігатися з прямою.

Тому покажемо, що задача (9.12) збігається з двоїстою задачею,

двоїста

побудованою для задачі (9.13) за правилом (9.12) (9.13). Приведемо задачу (9.13) до стандартної форми. Маємо:


	bT y → min		або	−bT y → max
	AT y ≥ c,			− AT y ≤ −c.

Покладемо y = y / − y // , де y / ≥ 0 ,				y // ≥ 0 . Отримаємо:
	−bT (y/	− y// )→ max
	− AT (y/	− y// )≤ −c,		y/	≥ 0, y//	≥ 0.
Вводячи	вектор		балансних		змінних		z = (z1, z2 ,..., zn )T , остаточно
матимемо:	−bT (y /	− y // )→ max

	− AT (y /	− y // )+ Ez = −c,
	y / ≥0, y // ≥0, z ≥0.
Остання	задача		має	стандартну форму, аналогічну (9.12).
Записуємо двоїсту до неї за правилом (9.12)						двоїста
							(9.13):
	−cT x → min				cT x → max
	− Ax ≥ −b,		Ax ≥ b,	або Ax = b,
	Ex ≥0,				x ≥0,
що і треба було довести.

9.1.1. Приклади.

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

1) кожному i − му

(i =

1, m

) обмеженню (або рядку Ai = (a

, a

, ...,a )

матриці

A ) вихідної задачі відповідає змінна yi двоїстої задачі і, навпаки,

кожному

j − му

( j =

)

обмеженню двоїстої задачі відповідає змінна

x j

1, n

(або стовпчик

= (a

, a

2 j

,...,a

матриці A ) вихідної задачі,

тому ліва

1 j

частина

j − го

( j =

)

обмеження двоїстої задачі є скалярним добутком

1, n

вектора двоїстих змінних y на стовпчик Aj , тобто yT A j , а ліва частина

i − го (i = 1, m) обмеження вихідної задачі є скалярним добутком Ai x ;

2) вільні члени обмежень однієї із двоїстих задач є коефіцієнтами при відповідних змінних у цільовій функції іншої задачі, до того ж при переході до двоїстої задачі змінюється критерій оптимізації на протилежний− максимізація заміняється мінімізацією, і навпаки;

3) у вихідній задачі знак обмежень повинен бути узгодженим з критерієм оптимізації − при максимізації всі обмеження повинні бути типу “ ≤ ” або “=”, при мінімізації всі обмеження повинні бути типу “ ≥ ” або “=”, тому для уникнення помилок перед записом двоїстої задачі всі обмеженнянерівності вихідної задачі доцільно звести до рівнянь введенням балансних змінних;

кожному

i − му

(i =

1, m

) обмеженню-нерівності

вихідної

задачі

відповідає

у двоїстій

задачі

умова невід’ємності

yi ≥0 ,

а для обмежень-

рівнянь

така умова

відсутня, відповідна двоїста

змінна

вважається

вільною за знаком; навпаки,

невід’ємній змінній x j ≥0

( j =

)

у двоїстій

1, n

задачі

відповідає

j − е обмеження-нерівність,

при

відсутності

умови

невід’ємності − рівняння.

Приклад 1. Побудувати двоїсту для такої задачі ЛП:

+ x2 − x3

− 2x5 → min,

+ x4

= -3,

x1 − 2x2

x3 − 2x4

= 2,

3x2

− x4 + x5 ≤ 5,

+ x5 ≥ 3,

x j ≥0, j = 2, 4.

Розв’язування. Зводимо систему обмежень до системи рівнянь шляхом введення у ліву частину третього та четвертого обмеження балансних

змінних x6 ≥ 0 та x7		≥ 0 з відповідними знаками. Отримаємо задачу:
x1		+ x2 − x3	− 2x5 → min,
	− 2x2		+ x4				= -3,	y1

x1
		x3 − 2x4					= 2,	y2
		3x2	− x4 + x5 + x6				= 5,	y3

		x2		+ x5		− x7 = 3,		y4

		x j ≥ 0, j = 2, 4, 6, 7.


Відповідно кожному рівнянню-обмеженню цієї задачі вводимо вільну
за знаком двоїсту змінну yi			(i =		)	(ці змінні зображені за вертикальною
				1,4

рискою). На змінні вихідної задачі x1 , x3 , x5 не накладені умови невід’ємності,

тому відповідні цим змінним 1-е, 3-є та 5-е обмеження двоїстої задачі будуть рівняннями. Всі інші обмеження двоїстої задачі будуть нерівностями типу “ ≤ ”, оскільки критерієм оптимізації двоїстої задачі є максимізація.

Записуємо двоїсту				задачу, починаючи з		її цільової	функції
L* ( y) = yT b , де	y = ( y , y	2	, y , y )T		− вектор двоїстих	змінних, b	− вектор
	1	2	3	4

вільних членів системи обмежень вихідної задачі. Далі, використовуючи скалярні добутки вектора y на вектори умов Aj ( j =1,7) , коефіцієнти c j

цільової функції вихідної задачі та умови невід’ємності змінних вихідної задачі (або їх відсутність) записуємо двоїсту задачу:

yT b → max,

−3y1 + 2 y2 + 5 y3 + 3y4 → max,

= c ,

A2 ≤ c2 ,

+ 3y3 + y4 ≤ 1,

− 2 y1

yT A3

= c3 ,

= −1,

або

y − 2 y

− y

≤ 0,

≤ c ,

= c ,

y3 + y4 = − 2,

≤ c6 ,

≤

− y ≤

≤ c ,

9.1.2. Вправи.

Побудувати двоїсті задачі та показати взаємоспряженність

відповідних пар задач для таких задач ЛП:

1) L = x1 − 2x2 + 3x3 − x4 → max,

2) L = 3x2 − x4 → max,

− x

+ 2x

−3x

≤ 5,

− 2x

+ x = 8,

x1 + 2x2 − x3

+ x4 ≤ 3,

x2 + x3 −3x4 =6,

x , x , x , x ≥

x , x , x , x ≥ 0.

3) L = 2x1 − x2 + x3 −3x4 + x5 → min,

4) L = x1 − 2x2 + x3 − x4 + x5 → min,

− x

+ x

−3x

− x = 10,

−

+ x +

− 2x

=6,

x1 + 2x2 − x3 + 2x4 + x5 ≥ 8,

2x1 + 3x2 − 2x3 − x4

+ x5 ≤ 4,

− x

+ 3x

− x

+ 2x ≤ 4,

+ 3x

−4x

≥ 8,

x , x , x

≥0.

x , x , x

≥ 0.

5) L = −x1 + x2 + x3

→ max,

6) L = 2x1 + 4x2 + x4 → min,

+ x

−2x

≥1,

−

+ x ≤ 4,

x1 −3x2 + x3 ≥ 4,

2x1 + 3x2 − x3 ≥ 2,

, x

≥0.

, x

≥0.

7) L = 3x1 −12x2 + 4x3 → min,				8) L = x1 +14x2 −3x4 → min,
x −	4x		+ 4x ≥ 1,		x	−	13x +	3x ≤ −1,
1		2	3		1		2	3
x1 + 3x2			+ x3 ≤ −2,	2x1 +17 x2 −7 x3 ≥ 2,
x , x	2	≥0.		x , x , x ≥0.
1	2				1	2	3

9.2. Теореми двоїстості.

Лема (про зв‘язок значень цільових функцій двоїстих задач на їх допустимих розв‘язках).

Для довільних допустимих розв‘язків прямої задачі (9.12) −

= (x

2 ,...,

n )T і двоїстої

задачі (9.13) −

(

2 ,...,

m )T має місце

нерівність

≤ bT

(9.14)

Якщо для деяких

= bT

(9.15)

то x і y − оптимальні розв‘язки відповідно задач (9.12) і (9.13).

Теорема 9.1 (перша або основна теорема двоїстості, теорема дає умови розв’язності пари взаємодвоїстих задач ЛП).

1.Якщо одна з пари двоїстих задач (9.12), (9.13) має оптимальний розв‘язок, то і двоїста їй також має оптимальний розв‘язок, причому їх оптимуми збігаються.

2.Якщо цільова функція однієї з пари двоїстих задач не обмежена на допустимій області (для (9.12) зверху, для (9.13) знизу), то двоїста їй не має допустимих розв‘язків.

Теорема 9.2 (друга теорема двоїстості, теорема дає необхідні і достатні умови оптимальності в лінійному програмуванні).

Допустимі розв‘язки x = (x1 , x2 ,..., xn )T і y = (y1 , y2 ,..., ym )T

відповідно прямої (9.12) і двоїстої (9.13) задач є їх оптимальними розв‘язками тоді і тільки тоді, коли виконуються умови

(ATj y −c j )x j =0, j =		(9.16)
	1, n.

Зауваження 9.1. Досить часто другу теорему двоїстості формулюють так:

Нехай x = (x1 , x2 ,..., xn )T і y = (y1, y2 ,..., ym )T − допустимі розв‘язки

відповідно прямої (9.12) і двоїстої (9.13) задач. Якщо для кожного j , такого, що

<<< < Предыдущая 1 2 3 4 5 6 78 / 118 9 10 11 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
19.03.201558.07 Кб184Инструкция по учету Агентуры.docx
#
07.03.2016577.32 Кб15Интроверт.pdf
#
19.03.201545.04 Кб9Информационные.docx
#
08.07.20191.67 Mб1Иоанна Хмелевская -- (Nie)Boszczyk maz_POL.doc
#
19.03.201573.33 Кб5иппв.docx
#
07.03.20161.89 Mб17ИсследованиеОпераций.pdf
#
19.03.201554.77 Кб6Исторія модуль 2.docx
#
28.04.2019197.84 Кб1Историография. Шпоры.docx
#
23.12.2018332.8 Кб4история 2 - 2003.doc
#
19.03.2015199.17 Кб5история дипломатии том 2 ГЛАВА 7.doc
#
07.03.20162.04 Mб52История Медицины. Т.1..pdf