Navch._posibnuk_Ivaschyk

Несиметричні

Z = c0 +c1x1 +c2 x2 +...+cn xn (max),

a

x

+ a

x

+...+ a

x

= b

,

11

1

12

2

1n n

1

a21x1 + a22 x2 +...+ a2n xn

= b2 ,

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

a

x

+ a

x

2

+...+ a

x

= b

,

m1 1

m2

mn n

m

≥ 0,

j

=1,n.

xj

Z = c0 +c1x1 +c2 x2 +...+cn xn (min),

a x

+a

x

+...+a

x =b ,

11

1

12

2

1n

n

1

a21x1 +a22x2 +...+a2n xn

=b2 ,

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

a

x

+a

x

+...+a

x

=b

,

m1 1

m2

2

mn n

m

≥ 0,

j =1,n.

xj

z* = c0 + b1 y1 + b2 y2 +... + bm ym (min),

a11 y1 + a21 y2 +... + am1 ym ≥ c1 ,a12 y1 + a22 y2 +... + am2 ym ≥ c2 ,

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

a1n y1 + a2n y2 +... + amn ym ≥ cn ,

y ] − ∞;+∞[.i

z* = c0 + b1 y1 + b2 y2 +... + bm ym (max),

a11 y1 + a21 y2 +... + am1 ym ≤ c1 ,a12 y1 + a22 y2 +... + am2 ym ≤ c2 ,

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

a1n y1 + a2n y2 +... + amn ym ≤ cn ,

y ] − ∞;+∞[.i

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

3.2. Основні теореми двоїстості

Між прямою та двоїстою задачами лінійного програмування існує тісний взаємозв’язок, який випливає з наведених нижче теорем.

Перша теорема двоїстості. Якщо одна з пари двоїстих задач має оптимальний план, то інша задача також має оптимальний розв’язок, причому значення цільових функцій для оптимальних планів дорівнюють одне одному, тобто maxZ = minZ*, і навпаки.

Якщо ж цільова функція однієї з пари двоїстих задач необмежена, то друга задача взагалі не має розв’язків.

Якщо одна з пари не має розв’язку, то цільова функція другої задачі або необмежена, або також не має розв’язку.

101

Якщо пряма задача лінійного програмування має оптимальний план Хопт, знайдений симплекс-методом, то оптимальний план Yonm двоїстої задачі визначається за формулою:

Yопт = сбаз. D−1 ,

де cбaз – вектор-рядок, який складається з коефіцієнтів при невідомих цільової функції прямої задачі, що є базисними в оптимальному плані; D-1 – матриця, обернена до матриці D, що складається з базисних векторів оптимального плану, компоненти яких узято з початкового опорного плану задачі. Обернена матриця D-1 завжди знаходиться в останній симплекс-таблиці задачі в тих стовпчиках, де в першій таблиці знаходилась одинична матриця.

Друга теорема двоїстості. Якщо в результаті підстановки оптимального плану прямої задачі в систему обмежень цієї задачі і-те обмеження виконується як строга нерівність, то відповідний і-ий компонент оптимального плану двоїстої задачі дорівнює нулю.

Якщо і-ий компонент оптимального плану однієї з пари двоїстих задачі додатний, то відповідне і-те обмеження другої задачі виконується для оптимального плану як рівняння.

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

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

3.3. Двоїстий симплекс-метод

Розглянемо метод знаходження опорних планів, в якому використовується поняття двоїстості. Ми знаємо, що двоїстою задачею до задачі:

Z = c0 + c1 x1 + c2 x2 +... + cn xn (max),

102

a x

+ a x

2

+... + a

x

n

≤ b ,

11 1

12

1n

1

a21 x1 + a22 x2 + + a2... n xn ≤ b2 ,

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

a

x

+ a

m2

x

2

+ + a...

mn

x

n

≤ b

,

m1 1

m

j

=1,n,

x j ≥ 0,

або у векторно-матричній формі:

z = c0 +(c, x) (max) Ax ≤ b, x ≥ 0

є задача:

z* = с0 +b1 y1 +b2 y2 +...+bm ym (min),

		+ a21 y2 + + am1 ym							≥ c1,
a11 y1
a12 y1 + a22 y2 + + am2 ym... ≥ c2 ,
.............................................
a y		+ a	y	2	+ + a y...			m	≥ c ,
1n	1	2n					mn		n
y	≥ 0,		i =				,
						1, m
i

або у векторно-матричній формі:

z* = c0 +	(b, y) (max)
AT y ≥ c,	y ≥ 0 ,

де AТ – матриця, транспонована до A;

(c,x), (b,y) – скалярні добутки відповідних векторів.

Якщо пряму задачу привести до канонічного виду і заповнити симплекс-таблицю, то ми бачимо, що стовпчики прямої задачі стануть рядками двоїстої, і навпаки. Тому нема потреби окремо розв’язувати вихідну задачу, а окремо – двоїсту, оскільки розв’язки обох можна знайти за одними й тими ж симплекс-таблицями, пам’ятаючи, що невідомим однієї задачі відповідають стовпчики, а невідомим другої – рядки.

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

103

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

Нехай в нас є задача, в базисі якої деякі плани від’ємні. Тоді ті базисні невідомі, що мають від’ємні плани, повинні бути виключені з базису.

Припустимо, що невідома xk має від’ємний план (βk<0). Розглянемо k-тий рядок. Якщо в ньому всі члени додатні (за винятком βk), то двоїста задача, а разом з нею і вихідна не мають розв’язку через необмеженість форми.

В іншому випадку виділяємо стовпчики, в яких числа k-го рядка від’ємні. Для кожного з виділених стовпчиків складаємо відношення

елементів стовпця «План» до елементів виділених стовпців ( βk ) за

aik

принципом: додатні до додатних, від’ємні до від’ємних, і вибираємо найменші відношення, які позначимо через 1 , 2 ,..., а числа

нульового рядка відповідних стовпчиків через α1 ,α2 ,... .

До базису вводимо вільну невідому, для якої (при знаходженні максимуму цільової функції):

αr r	= min{αi i } .
	l≤i≤n

Розглянемо цей метод на прикладі.

Приклад 3.1. Знайти максимальне значення функції

z = 3x1 + 2x2 +3x3 −7

при обмеженнях:

3x1 + 4x2 + 2x3 ≥ 2,2x1 + x2 + x3 ≤8,

x1 , x2 , x3 ≥ 0.

♦ Розв’язування.

Помножимо першу нерівність системи обмежень на (–1):

−3x1 −4x2 −2x3 ≤ −2,

2x1 + x2 + x3 ≤8.

Щоб отримати обмеження-рівняння до лівих частин обмежень введемо додаткові невід’ємні невідомі х4 та х5:

104

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

2x1 + x2 + x3 + x5 =8.

Формально заповнюємо симплекс-таблицю:

№ таблиці	рядка№	Базис	План	Коефіцієнти при невідомих
				х1	х2	х3↓	х4	х5
	0	Z	–7	–3	–2	–3	0	0
1	1	←	–2	–3	–4	–2	1	0	:(–2)
		х4
	2	х5	8	2	1	1	0	1

Виділяємо рядок з найменшим (від’ємним) планом. В нашому випадку – це перший рядок. Невідому x4 (з від’ємним планом) потрібно вивести з базису. В цьому рядку є три від’ємні числа (–3) в стовпчику x1, (–4) в стовпчику х2 та (–2) в стовпчику х3. Щоб визначити, яку з невідомих потрібно ввести в базис, знаходимо відношення елементів стовпця «План» до елементів стовпців, що відповідають змінним x1, х2 та х3 (від’ємні до від’ємних, додатні до додатних), а також запишемо значення α компонент нульового рядка, що відповідають стовпчику, до елементів якого знаходимо відношення:

	− 2			8				2							2				α1
1	= min	−3	;					= min				;	4	=				;		= −3;
				2											3
								3
	− 2			8				1							1				α2
2	= min	− 4	;					= min				;	8	=				;		= −2;
				1											2
								2
	− 2			8				= min(1;				4)=1;							α3
3	= min	− 2	;																	= −3.
				1

Тоді знаходимо

min{αi i		2		1			−1; −3} = −3.
	} = min		(−3);		(−2); 1 (−3)	= min{− 2;
				2
	3

Отже, в базис потрібно ввести невідому х3. На перетині першого рядка і стовпця, що відповідає невідомій х3 знаходиться генеральний (ключовий) елемент (–2). Ділимо перший рядок на ключовий елемент і, за правилами роботи з симплекс-таблицями, переходимо до другої таблиці:

105

№	№	Базис	План									Коефіцієнти при невідомих
таблиці	рядка											х1						х2									х3				х4						х5
	0	Z		–4									3						4									0			−		3				0
												2																					2
2	1	х3		1									3						2									1			−		1				0		·3; ·(–1)
												2																					2
	2	х5		7									1					–1										0				1					1
												2																			2
В	другій	таблиці	ми вже маємо опорний план. Задача записана в
канонічній формі:								3												3
		z = −							x			− 4x					+				x					− 4					(max),
								2												2
				3						1						2								4
							x			+		2x			+ x					−		1			x				=1,
				2																		2
								1						2		1			3									4
				1				x1			− x2 +							x4 + x5 = 7,
				2												2
																			i =1,5.
											xi ≥ 0,
Але ми шукаємо максимальне значення цільової функції, а в
нульовому рядку другої таблиці ще є від’ємне число (−																																						3 ), значить,
																																						2

знайдений опорний план не є оптимальним. Тому далі задачу розв’язуємо звичайним симплекс-методом:

№	№	Ба-	План	Коефіцієнти при невідомих
таблиці	рядка	зис
				х1			х2	х3		х4						х5
	0	Z	– 4	3			4	0	↓− 3							0
				2					2
2	1	х3	1		3		2	1				1				0
				2					− 2									1
	←			1
		х5	7				– 1	0		1						1	:
	2
				2						2								2
	0	Z	17	3			1	0	0							3
3
	1	х3	8	2			1	1	0							1		3				1
	2	х4	14	1			– 2	0	1							2	·			; ·
																		2				2

106

В третій таблиці ми отримали оптимальний розв’язок задачі:

xопт. = (0; 0; 8; 14; 0),

zmax =17.

Якби друга ітерація не дала опорного плану, то процес треба повторювати до тих пір, доки його не здобудемо. Із алгоритму двоїстого симплекс-методу випливає, що його доцільно застосовувати тоді, коли обмеження задачі містять нерівності різних знаків. ♦

3.4.Економіко-математичний аналіз оптимальних розрахунків

Економічну інтерпретацію двоїстої задачі розглянемо на прикладі оптимального використання обмежених ресурсів.

Для виробництва n видів продукції використовується m видів

ресурсів, запаси яких обмежені значеннями bі

(i =1, m). Норма витрат

кожного виду ресурсу

на

одиницю

продукції

становить

aij

(i =1, m;

j =

). Дохід від одиниці продукції j-го виду дорівнює

1, n

cj

( j =

) .

Знайти план виробництва

продукції, що

забезпечить

1, n

максимальний сумарний дохід.

Математична модель задачі:

Z = c1 x1 +c2 x2 +...+cn xn

(max),

a

x

+ a

x

2

+

...+ a

x

n

≤ b ,

11

1

12

1n

1

a21 x1 + a22 x2 +...+ a2n xn

≤ b2 ,

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

a

x

+ a

m2

x

2

+...+ a

mn

x

n

≤ b

,

m1 1

m

≥ 0,

j

=1,n.

x j

Пряма задача полягає у визначенні такого оптимального плану виробництва продукції Хопт, який дасть найбільший дохід. Двоїста задача до окресленої задачі матиме вигляд:

z* = b1 y1 +b2 y2 +...+bm ym (min),

a11 y1 + a21 y2 + + am... 1 ym ≥ c1 ,

a y + a

22

y

2

+ + a...

m2

y

m

≥ c

2

,

12

1

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

a y + a

2n

y

2

+ + a...

mn

y

m

≥ c

n

,

1n

1

≥ 0,

i =1,m.

yi

107

Економічний зміст двоїстої задачі полягає в тому, щоб визначити таку оптимальну систему двоїстих оцінок уi ресурсів, що використовуються для виробництва продукції, при яких загальна вартість усіх ресурсів буде найменшою. Оскільки двоїсті змінні означають цінність одиниці ресурсу, то їх інколи ще називають

тіньовою ціною відповідного ресурсу.

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

Ресурси, що використовуються для виробництва продукції, умовно можна поділити на дефіцитні та недефіцитні, залежно від того, повне чи часткове їх використання передбачено оптимальним планом прямої задачі. Якщо двоїста оцінка уi в оптимальному плані двоїстої задачі дорівнює нулю, то відповідний і-тий ресурс при виробництві продукції повністю не використовується і є недефіцитним. Якщо ж двоїста оцінка yі>0, то і-тий ресурс використовується повністю для оптимального плану виробництва продукції і називається дефіцитним. В цьому випадку величина двоїстої оцінки показує, наскільки збільшиться значення цільової функції Z, якщо запас відповідного ресурсу збільшити на одиницю.

Аналіз рентабельності продукції, що виготовляється,

виконується за допомогою двоїстих оцінок і обмежень двоїстої задачі. Ліва частина кожного обмеження є вартістю всіх ресурсів, які використовуються для виробництва одиниці j-тої продукції. Якщо ця величина перевищує дохід від одиниці продукції (сj), то виготовляти цю продукцію не вигідно, вона нерентабельна і в оптимальному плані прямої задачі відповідна хj=0. Якщо ж загальна оцінка всіх ресурсів дорівнює доходу від одиниці продукції, то виготовляти таку продукцію доцільно, вона рентабельна і в оптимальному плані прямої задачі відповідна змінна хj > 0.

Приклад 3.2.

1.Скласти двоїсту задачу до вихідної задачі прикладу 2.3.

2.Виписати оптимальний план двоїстої задачі з останньої симплекстаблиці розв’язаної задачі і зробити її економічний аналіз.

3.Визначити статус ресурсів прямої задачі та інтервали стійкості двоїстих оцінок відносно зміни запасів дефіцитних ресурсів.

4.Визначити план виробництва продукції та зміну загального доходу підприємства, якщо запас першого ресурсу збільшити на 100

108

одиниць, другого – зменшити на 5 одиниць, а запас третього ресурсу збільшити на 15 одиниць.

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

6.Розрахувати інтервали можливої зміни доходу, отриманого від реалізації одиниці кожного виду продукції.

♦Розв’язування.

1.Математична модель прямої задачі мала вигляд:

Z = 9x1 + 6x2 (max),

4x1 + 5x2 ≤ 275,13x1 + 8x2 ≤ 680,

x1 + x2 ≤ 60,x1 ≥ 0,

x ≥ 0.2

Побудуємо двоїсту задачу до вихідної:

Відповідно до кожного основного обмеження початкової задачі ставимо двоїсту змінну: першому обмеженню – у1, другому – у2, третьому – у3:

Z = 9x1 + 6x2			(max),
4x1 + 5x2		≤ 275		y1
13x1 + 8x2		≤ 680		y2
x1 + x2 ≤ 60				y3
x	≥ 0
1
	≥ 0.
x2

Якщо цільова функція вихідної задачі досліджується на максимум, то двоїстої – на мінімум. Запишемо цільову функцію двоїстої задачі. Для цього праві частини основних обмежень початкової задачі почленно перемножимо на двоїсті змінні, що відповідають кожному з цих обмежень і додамо. Отримаємо:

Z * = 275y + 680y	2	+ 60y	3	(min).
1

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

109

двоїстої задачі. Враховуючи, що в основних обмеженнях початкової задачі знак нерівності «≤», то в обмеженні двоїстої задачі знак нерівності буде «≥». Правою частиною обмеження двоїстої задачі є коефіцієнт при невідомій х1 в цільовій функції початкової задачі. Ми отримали перше обмеження двоїстої задачі: 4y1 +13y2 + y3 ≥ 9.

Аналогічно отримаємо

друге

обмеження:

5y1 +8y2 + y3 ≥ 6 . В

результаті маємо двоїсту задачу:

Z *

= 275y

+ 680y

2

+ 60y

3

(min),

1

4y +13y

2

+ y

3

≥ 9,

1

5y1 + 8y2 + y3 ≥ 6,

y

, y

2

, y

3

≥ 0.

1

2. Розв’язок двоїстої задачі виписуємо з нульового рядка останньої (в нашій задачі – третьої) симплекс-таблиці:

№	№	Базис	Опорний				Коефіцієнти при невідомих
таблиці	рядка		план				х1			х2	х3	х4						х5
	0	Z	480				0			0	0	3					6
												5					5
	1	х3	15				0			0	1		1				−		33
												5
3																	5
	2	х1	40				1			0	0		1				−			8
												5
																	5
	3	х2	20				0			1	0	−		1			13
																		5
												5
Zmin* = Zmax = 480 при			y1 = 0, y2 =	3		,	y3 =	6		. Значення двоїстих змінних
				5				5

беремо із клітинок нульового рядка, що відповідають базисним змінним початкової задачі, тобто y1 → x3 , y2 → x4 , y3 → x5 .

Оптимальний план двоїстої задачі також можна знайти, використавши формулу:

110