Navch._posibnuk_Ivaschyk

a

x

+ a

x

2

+... + a

x

n

= b ,

11

1

12

1n

1

a21x1 + a22 x2

+... + a2n xn

= b2 ,

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

(2.22)

a

x

+ a

m2

x

2

+... + a

mn

x

n

= b

,

m1 1

m

≥ 0,

j

=1,n.

x j

Нехай всі праві

частини обмежень

додатні (bi ≥ 0,

i =

).

1, m

Цього завжди можна досягнути, помноживши рівняння з від’ємним вільним членом на (–1).

Формально до лівих частин обмежень додамо по одній невідомій wj ( wj ≥ 0, j =1, m.), які будемо називати штучними, а

базис, утворений з цих невідомих – штучним базисом. В результаті система обмежень матиме вигляд:

a

x

+ a

x

2

+... + a

x

n

+ w

= b ,

11 1

12

1n

1

1

a21x1 + a22 x2

+... + a2n xn

+ w2

= b2 ,

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

(2.23)

a

x

+ a

m2

x

2

+... + a

mn

x

n

+ w

= b ,

m1 1

m

m

x

j

≥

0,

j

=

1,n;

w ≥ 0, i =

1,m.

i

До цієї системи обмежень додамо штучну оптимізуючу форму:

f = w1 + w2 +... + wm

(min).

(2.24)

Задача (2.24)-(2.23)

є

задачею

лінійного програмування, що

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

Система обмежень (2.23) називається сумісною в області

невід’ємних значень, якщо вона має хоча	б один допустимий
розв’язок.
Сформулюємо теорему.
Теорема. Для того, щоб система обмежень була сумісною в
області невід’ємних значень, необхідно і	достатньо,	щоб	на
розв’язках системи обмежень (2.23)
fmin = 0.		(2.25)
Наслідок. Якщо оптимальний план задачі (2.24)-(2.23) містить
хоча б одну штучну невідому wі, то початкова задача		не	має

81

розв’язку, оскільки вона не є сумісною в області допустимих планів (множина допустимих планів порожня).

Зробимо декілька зауважень щодо заповнення симплекс-таблиць при використанні методу штучного базису:

1.Щоб знайти опорний план, потрібно перевести штучні невідомі з базисних у вільні. З цією метою у методі штучного базису використовують редуковані симплекс-таблиці (не заповнюємо

стовпчиків коефіцієнтів при штучних невідомих wі), оскільки після переходу у вільні штучні невідомі нас вже не цікавитимуть.

2.Нульовий рядок заповнюємо за штучною оптимізуючою формою f. Його можна отримати формальним додаванням чисел рядків, що відповідають обмеженням з штучними змінними.

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

Приклад 2.6. Розв’язати задачу лінійного програмування:

z = 2x1 + 5x2 − 6x3 +10 (max),

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

x1 , x2 , x3 ≥ 0.

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

Для розв’язання цієї задачі симплексний метод одразу використати неможливо, оскільки не виконується одна з умов канонічності задачі (в системі обмежень немає базису). Тому застосуємо метод штучного базису. До лівих частин перших двох (основних) обмежень задачі додамо невід’ємні штучні змінні w1 та w2

x	− 2x						2	+ 2x		3	+ w			= 4,
1													1
− x1 + 3x2 + 2x3 + w2															= 2,			(2.26)
x	, x			, x				≥ 0;			w			,w		≥ 0.
1			2				3						1	2
Визначимо з системи обмежень штучні невідомі w1 та w2 через
вільні х1, х2 та х3 і підставимо в штучну оптимізуючу форму f:
w			= 4 − x + 2x									2	−2x				,
	1								1							3
w2 = 2 + x1 −3x2 −2x3 ,
x		, x			2	, x		3	≥ 0;				w , w				≥ 0.
	1													1		2

82

f = 4 − x1 + 2x2 − 2x3 + 2 + x1 −3x2 − 2x3 = −x2 − 4x3 + 6 (min) . (2.27)

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

				f + x2 + 4x3 = 6						(min),
			z −2x1 −5x2 +6x3 =10							(max)
і розв’яжемо задачу (2.27)-(2.26) симплекс-методом:
	№ таблиці	рядка№	Базис		Опорний план	Коефіцієнти
						при невідомих
						х1			х2	х3
		0	f		6	0			1	4↓
		′	Z		10	–2			–5	6
	1	0
		1	w1		4	1			–2	2	4:2=2
		2	w2←		2	–1			3	2	2:2=1(min) :2
		0	f		2	2↓			–5	0
		′	Z		4	1			–14	0
		0
	2	1	w1←		2	2			–5	0
		2	x3		1	−	1		3	1	• (-4); •(-6); •(-2)
									2
						2
		0	f		0	0			0	0
		′	Z		3	0			− 23	0
		0							2
	3
		1	x1		1	1			− 5	0
									2
		2	x3		3	0			1	1
					2				4

В результаті встановлено, що fmin = 0, а це означає, що початкову задачу звели до канонічної форми. Випишемо її з останньої симплекстаблиці:

	z =	23	x		+ 3 (max),
		2		2

83

				x				−		5		x				=1,
														2
						1			2
						1												3
								x2	+ x3							=				,
						4												2
											, x					≥
						x , x			2				3					0.
						1
	Розв’яжемо цю задачу симплекс-методом, відкинувши в третій
таблиці рядок, в якому знаходилась інформація про функцію f:
	№ таблиці	рядка№	Базис	Опорний план		Коефіцієнти при
								невідомих
						х1									х2					х3
		0	Z	3		0						−			23			↓ 0
															2
3		1	x1	1		1							−			5				0
																2						1
		2	x3←	3		0									1					1	:
				2											4							4
		0	Z	72		0									0					69
4		1	x1	16		1									0					10			23		5
		2	x2	6		0									1					4	•			; •
																						2
																								2

Оскільки цільова функція досліджувалась на максимум і в нульовому рядку останньої (четвертої) симплекс-таблиці відсутні від’ємні числа, то це означає, що ми отримали оптимальний розв’язок задачі:

Zmax = 72 при x1 =16, x2 = 6, x3 = 0.

Перевірка: Zmax = 2 16 +5 6 −6 0 +10 = 32 +30 +10 = 72.♦

Розглянемо задачі з мішаними обмеженнями.

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

На практиці часто трапляються випадки, коли система обмежень складається як із рівнянь, так і з нерівностей (навіть різних знаків):

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

змінну (яка і буде базисною), в результаті чого отримаємо

84

обмеження-рівняння, а в ліві частини обмежень-рівнянь вводимо штучні невідомі і за ними будуємо штучну оптимізуючу форму.

2.Якщо крім нерівностей типу «≤» і рівнянь з додатною правою частиною в системі обмежень є ще й обмеження типу «≥» з додатною правою частиною, то потрібно від лівої частини цих

обмежень відняти додаткові невід’ємні невідомі, щоб звести обмеження типу «≥» до обмежень-рівнянь, а потім в ліві частини цих рівнянь включити штучні невідомі.

Приклад 2.7. Знайти розв’язок задачі лінійного програмування:

z = 3x1 + 3x2

− x3 −5 (min),

2x

+

2x

2

+ x

3

= 8,

1

x1

+ 2x2

+ 3x3

≤12,

4x

+

8x

2

+

3x

3

≥ 24,

1

x

, x

, x

3

≥ 0.

1

2

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

Вище зазначена задача також не записана в канонічній формі,

тому використаємо метод штучного базису. Але спочатку до лівої частини другого обмеження задачі додамо додаткову невід’ємну змінну х4, а від лівої частини третього обмеження віднімемо додаткову невід’ємну невідому х5, щоб перейти до рівнянь. В результаті отримаємо:

2x1 + 2x2 + x3 = 8,

x

+ 2x

2

+ 3x

+ x

4

=12,

1

3

4x

+ 8x

2

+ 3x

3

− x

5

= 24,

1

≥ 0,

i =1,5.

xi

У другому рівнянні-обмеженні є базисна невідома х4, а в першому і третьому немає. Тому в ліві частини першого та третього

обмеження задачі вводимо штучні невід’ємні змінні w1 та w2.

2x1 + 2x2 + x3 + w1 = 8,

x

+ 2x

2

+ 3x

3

+ x

4

=12,

1

4x

+ 8x

2

+ 3x

3

− x

5

+ w

= 24,

1

2

x

≥ 0,

i =

w ,w ≥ 0.

i

1,5;

1

2

Визначимо з системи обмежень штучні невідомі w1 та w2 через

вільні х1, х2, х3 та х5 та підставимо в f:

w

= 8 − 2x

− 2x

2

− x

,

1

1

3

w2 = 24 − 4x1 −8x2 −3x3 + x5 .

85

f = w1 + w2 = 8 − 2x1 − 2x2 − x3 + 24 − 4x1 −8x2 − 3x3 + x5 = = −6x1 −10x2 − 4x3 + x5 + 32.

Перенесемо всі невідомі штучної оптимізуючої форми та цільової функції в ліву сторону:

			f + 6x1 +10x2					+ 4x3 − x5 = 6						(min),
			z − 3x1 − 3x2 + x3 = −5												(min)
і розв’яжемо отриману задачу:
№ таблиці	№ рядка	Базис	Опор-			Коефіцієнти при невідомих
			планний	х1				х2		х3				х4		х5
	0	f	32	6				10↓		4				0		–1
	′	Z	–5	–3				–3		1				0		0
	0
1	1	w1	8	2				2		1				0		0
	2	х4	12	1				2		3				1		0
	3	w2←	24	4				8		3				0		–1
	0	f	2	1↓				0			1			0			1
										4						4
	′	Z	4	3				0		17				0		3
	0			− 2						8						− 8
2	1	w1←	2	1				0		1				0		1
										4						4
	2	х4	6	0				0		9				1		1
										4						4
	3	х2	3		1			1			3			0		−			1
				2						8
																8
	0	f	0	0				0		0				0		0
	′	Z	7	0				0		5				0		0
	0									2
3	1	х1	2	1				0		1				0		1
										4						4
	2	х4	6	0				0			9			1			1
										4						4
	3	х2	2	0				1			1			0		−		1
										4
																4

8:2=4

12:2=6

24:8=3(min) :8

2:1=2 (min)

(–10);•3;•(–2);•(–2)

3: 12 =6

(–1);• 32 ;•(– 12 )

86

Маємо fmin=0, а значить, ми отримали канонічну форму початкової задачі.

	z = −	5	x		+ 7 (min),
		2		3

				x				+		1		x			+	1			x								= 2,
														3										5
					1					4						4
					9											1
							x3 + x4								+					x5							= 6,
					4											4
											1						1
				x2				+					x3		−				x5 = 2,
										4						4
								≥ 0,							i =1,5.
				xi
	Розв’яжемо цю задачу симплекс-методом:
табл№ .	рядка№		Опор-		Коефіцієнти при невідомих
		Базис	ний	х1									х2									х3							х4			х5
			план
	0	Z	7	0									0								5				↓					0				0
																				2
	1	х1	2	1									0										1							0				1
3																				4														4
	2	х4←	6	0									0									9								1				1
																						4												4
	3	х2	2	0									1									1								0	− 1
																				4														4
	0	Z	1	0									0							0									−	10	−				5
			3																											9				18
	1	х1	4	1									0							0									− 1					2
4			3																											9				9
	2	х3	8	0									0							1										4				1
			3																											9				9
	3	х2	4	0									1							0									− 1		−			5
			3																													18
																														9

2:		1	=8
	4
6:	9		=2,67 :	9
	4		min	4
2:	1		=8
	4

В нульовому рядку останньої (четвертої) симплекс-таблиці немає додатних чисел, а оскільки цільова функція досліджується на

87

мінімум, то це означає, що ми отримали оптимальний розв’язок

задачі:	Z		=	1		при	x =		4	,		x		=	4	,	x =	8	.
		min											2
			3				1	3						3			3	3
							4				4		8							8		1
Перевірка:						Zmin = 3		+3				−		−5 = 4 + 4 −							−5 =		.♦
							3				3		3							3		3

2.5.Розв’язування задач лінійного програмування

здопомогою пакетів прикладних програм

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

Для ознайомлення користувача з основними характеристиками системи LINA, способами вводу інформації та виконання кожної команди в системі LINA існує команда HELP. Щоб отримати інформацію про певну команду, необхідно після HELP ввести ім’я команди, яка нас цікавить.

Програмна система LINA призначена для знаходження оптимального розв’язку та проведення післяоптимізаційного аналізу загальної задачі лінійного програмування (максимальний розмір задачі: 229 змінних і 118 обмежень з урахуванням максимізації або мінімізації цільової функції). У своєму складі вона має 36 команд, об’єднаних в 10 категорій.

Розглянемо структуру команд системи за категоріями:

1)інформації

HELP COM CAT;

2)входу

MAX MIN RETR TAKE LEAN; 3) індексації

PIC TABL LOOK NONZ SHOC SOLU RANGE; 4) запису у файл

SAVE DIVE PVRT SDBC; 5) розв’язку

GO PIV;

88

6) редагування

ALT EXT DEL SUB APPC;

7)виходу

QUIT;

8)цілочислового та параметричного програмування

INT PARA BIP;

9)формату індикації

WIDТH TERS VERB BAT RAGE; 10) інші

STAT.

Приклад 2.8. Припустимо, що нами планується організувати випуск продукції трьох видів за допомогою чотирьох технологічних способів виробництва на основі чотирьох видів ресурсів, запаси яких обмежені. Запас та витрати ресурсів на одиницю часу роботи відповідних технологічних ліній та вихід продукції від них наведені в табл. 2.4. Необхідно розрахувати оптимальний план виробництва, який забезпечить максимум кінцевої продукції, якщо частка продукції A в кінцевій становить 0,2, продукції B – 0,5, а продукції С

– 0,3.

								Таблиця 2.4
		Технологічні способи							Обсяг
	Показники	(витрати ресурсів,
			вихід продукції)						ресурсів
		І		ІІ	ІІІ		IV
Ресурси	Обладнання, маш.-год.	1,9		3,2	2,1		2,8		295
	Праця, люд.-год.	3,3		2,4	4,5		2,7		410
	Електроенергія, кВт.год.	4,6		3,8	2,7		4,1		505
	Фінансові кошти, грн.	6		7	5		4		890
Продукція	А, шт.	–		3	2		4
	В, шт.	2		–	1		1
	С, шт.	3		2	1		–

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

Для побудови математичної моделі введемо позначення:

х1, х2, х3, х4 – час роботи відповідних технологічних ліній виробництва;

Z – обсяг виробництва кінцевої продукції.

89

Враховуючи введені позначення, математична модель задачі має вигляд: знайти такий план {x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, Z ≥ 0}, який

забезпечить

Z → max

при виконанні умов:

1)з використання обладнання

1.9x1 + 3.2x2 + 2.1x3 + 2.8x4 ≤ 295;

2)з використання праці

3.3x1 + 2.4x2 + 4.5x3 + 2.7x4 ≤ 410;

3)з використання електроенергії

4.6x1 + 3.8x2 + 2.7x3 + 4.1x4 ≤ 505;

4)з використання фінансових коштів

6x1 + 7x2 + 5x3 + 4x4 ≤ 890;

5)з структури кінцевої продукції відносно:

–продукції А

3x2 +2x3 +4x4 ≥0.2Z або − 0.2Z + 3x2 + 2x3 + 4x4 ≥ 0;

– продукції В

2x1 + x3 + x4 ≥ 0.5Z або −0.5Z + 2x1 + x3 + x4 ≥ 0;

– продукції С

3x1 +2x2 + x3 ≥0.3Z або −0.3Z +3x1 +2x2 +x3 ≥0.

Розв’яжемо задачу з допомогою пакету LINA. Введення цільової функції та системи обмежень задачі здійснюється таким чином:

: max Z

?st

?1.9x1+3.2x2+2.1x3+2.8x4<=295

?3.3x1+2.4x2+4.5x3+2.7x4<=410

?4.6x1+3.8x2+2.7x3+4.1x4<=505

?6x1+7x2+5x3+4x4<=890

?-0.2Z +3x2+2x3+4x4>=0

?-0.5Z+2x1+x3+x4>=0

?-0.3Z+3x1+2x2+x3>=0

?end

Для отримання оптимального розв’язку та післяоптимізаційного аналізу задачі використовуємо команду GO. В результаті отримаємо розв’язок задачі (значення цільової функції, час роботи відповідних технологій, використання ресурсів):

90