Navch._posibnuk_Ivaschyk

видів виробничих ресурсів (матеріалів, обладнання, праці, сировини тощо).

Введемо позначення: i – індекс ресурсу, i =1, n ; j – індекс технології, j =1, m ; l – індекс виду продукції, l =1,r ; aij – витрати ресурсу i-го виду на одиницю часу роботи технологічної лінії виду j; blj – вихід продукції виду l за одиницю часу роботи технологічної лінії виду j; Ai – обсяг запасів ресурсів i-го виду; Kl – коефіцієнт, який відображає частку продукції виду l в загальному обсязі кінцевої продукції; xj – час роботи технологічної лінії виду j; Z – загальний обсяг кінцевої продукції.

Тоді узагальнена модель оптимального планування матиме вигляд: знайти такий план {x j ≥ 0; j =1, m; Z ≥ 0}, який забезпечить

Z → max

при виконанні обмежень: а) за обсягом ресурсів

a x

+ a x

2

+ + a

x

m

≤

A

,

11 1

12

1m

1

(2.6)

a

x

+ a

n2

x

2

+ + a

nm

x

m

≤

A ;

n1 1

n

б) за структурою кінцевої продукції

b x +b x

2

+ +b

x

m

≥ K

Z,

11 1

12

1m

1

(2.7)

br1 x1 + ar 2 x2 + + arm xm ≥ Kr Z.

3)Задача про складання кормового раціону.

Вкормовий раціон для відгодівлі великої рогатої худоби (ВРХ)

входять п’ять видів кормів К1, К2, К3, К4 та К5. Для забезпечення заданого приросту ваги тварини повинні споживати поживні

речовини Р1, Р2 та Р3. Мінімальна кількість поживних речовин, потрібних тваринам, а також вміст кількості одиниць поживних речовин в 1 кг корму та вартість 1 кг корму наведені в таблиці.

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

51

Поживні	Мінімальна	Кількість одиниць поживних речовин в 1 кг корму
	кількість
речовини	поживних	К1	К2	К3	К4	К5
	речовин
Р1	b1	a11	a12	a13	a14	a15
Р2	b2	a21	a22	a23	a24	a25
Р3	b3	a31	a32	a33	a34	a35
Вартість 1 кг корму		с1	с2	с3	с4	с5

Побудуємо математичну модель задачі. Введемо позначення: хі – кількість корму (кг) Кі в раціоні (і=1, 2, 3, 4, 5);

Z – вартість добового раціону.

Оскільки вартість одного кілограма корму становить сі, а загальна кількість корму і-го виду, що потрібна для відгодівлі ВРХ становить хі кг (і=1, 2, 3, 4, 5), то перемноживши сі на хі і додавши ці

добутки, отримаємо вартість	добового раціону відгодівлі ВРХ:
Z = c1 x1 + c2 x2 + c3 x3 + c4 x4 + c5 x5 .	Для побудови обмежень задачі

перемножимо a11 – кількість поживних речовин Р1, що містяться в 1кг корму К1 на загальну кількість цього корму х1, a12 – кількість поживних речовин Р1, що міститься в 1 кг корму К2 на загальну

кількість цього корму х2, a13 на х3, a14 на х4, a15 на х5 і додамо ці добутки. В результаті отримаємо загальну кількість поживних

речовин Р1, отриманих від усіх п’яти кормів, а мінімальна кількість поживних речовин Р1 повинна становити b1, тому обмеження з

першого	виду	поживних	речовин	матиме		вигляд:
a11 x1 + a12 x2	+ a13 x3 + a14 x4 + a15 x5 ≥ b1 .		Аналогічно		записуються

обмеження з мінімальної кількості споживання поживних речовин Р2

та Р3.

Ми отримали математичну модель задачі про кормовий раціон:

Z = c1x1 + c2 x2 + c3 x3 + c4 x4																			+ c5 x5				(min),	(2.8)
a11x1 + a12 x2 + a13 x3 + a14 x4 + a15 x5 ≥ b1 ,
a	21	x	+ a	22	x	2	+ a			23	x	3	+ a		24	x		4	+ a		x		≥ b ,
		1																			25	5	2	(2.9)
a	31	x	+ a	32	x	2	+ a		33		x	3	+ a	34		x	4		+ a	35		x	≥ b ,
		1																				5	3
x		≥ 0,			i =
								1,5.
i

52

4) Задача про раціональний розкрій матеріалів.

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

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

m – кількість різних заготовок;

Bi – план випуску заготовок і-го виду;

n – кількість різних способів (варіантів) розкрою стандартного матеріалу;

аij – число заготовок і-го виду, одержаних за допомогою j-го способу розкрою;

сj – величина відходів при j-му варіанті розкрою. Схематично задачу можна представити у вигляді таблиці:

Варіант (спосіб)	Вихід заготовок з одиниці матеріалу				Відходи
розкрою
	1-го виду	2-го виду	…	m-го виду
1	a11	a12	…	a1m	c1
2	a21	a22	…	a2m	c2
…	…	…	…	…	…
n	an1	an2	…	anm	cn
План випуску	B1	B2	…	Bm
заготовок

Через невідому xj позначимо кількість одиниць вихідного матеріалу, які потрібно розрізати j-тим способом, а через Z – загальну кількість відходів.

Кількість заготовок i-го виду, одержана за всіма варіантами розкрою становитиме a1i x1 + a2i x2 +... + ani xn , а нам потрібно цих

заготовок в кількості Bi одиниць. Тому в якості обмеження з i-того виду заготовок буде рівність:

a1i x1 + a2i x2 +... + ani xn = Bi .

53

В загальному випадку математична модель задачі раціонального розкрою матеріалу матиме вигляд:

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

(min),

a

x

+ a

21

x

2

+... + a

n1

x

n

= B ,

11

1

1

a12 x1 + a22 x2

+... + an2 xn

= B2 ,

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

a

x

+ a

2m

x

2

+... + a

nm

x

n

= B

,

1m 1

m

≥ 0,

j

=1,n.

x j

(2.10)

(2.11)

Існуючі методи розв’язування задач лінійного програмування передбачають певні вимоги до системи основних обмежень (2.2), тому розрізняють дві стандартні форми запису задач лінійного програмування:

І-ша – з обмеженнями-рівняннями; ІІ-га – з обмеженнями-нерівностями.

Запишемо задачу лінійного програмування в першій стандартній формі:

Z = c0 + c1x1 + c2 x2 +... + cn xn

(extr) ,

a11 x1 + a12 x2

+... + a1n xn

= b1,

a

x

+ a

22

x

2

+... + a

2n

x

n

= b

,

21 1

2

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

a

x

+ a

m2

x

2

+... + a

mn

x

n

= b

,

m1 1

m

(i =1,n).

xi ≥ 0

(2.12)

(2.13)

Розв’язати задачу (2.12)-(2.13) – означає знайти такі розв’язки системи рівнянь (2.13), при яких цільова функція (2.12) набуває екстремального значення.

Задача лінійного програмування записана в другій стандартній формі в загальному випадку має вигляд:

F = s0 + s1x1 + s2 x2 +... + sk xk

(extr),

(2.14)

54

+ +α1k xk

≤ β1 ,

α11 x1 +α12 x2

α

21 x1 +α22 x2 + +α... 2k xk ≤ β2 ,

(2.15)

..........

..........

..........

..........

...

α

x +α

l 2

x

2

+ +α...

lk

x

k

≤ β

,

l1 1

l

(i =1, k ).

xi ≥ 0

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

В системі обмежень (2.15) ставимо знак нерівності «≤», оскільки цього можна завжди домогтися, помноживши праву і ліву частини нерівності на (–1).

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

Щоб перейти від другої стандартної форми до першої, достатньо до лівої частини кожного обмеження типу «≤» системи (2.15) додати додаткову додатну невідому, яка рівна різниці між правою та лівою частинами нерівності. Здійснимо це і в результаті отримаємо:

F = s0 + s1 x1 + s2 x2 +... + sk xk

(extr) ,

+... +α1k xk + xk +1

= β1 ,

α11 x1 +α12 x2

α21 x1 +α22 x2

+... +α2k xk + xk +2 = β2 ,

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

α

x +α

l 2

x

2

+... +α

lk

x

k

+ x

k +l

= β

,

l1 1

l

xi ≥ 0

(i =

1, k + l

).

(2.16)

(2.17)

Задача (2.16)-(2.17) записана в першій стандартній формі. Розглянемо задачу лінійного програмування з обмеженнями-

рівностями (2.12)-(2.13).

Нехай x1 ,x2 ,…,xk – вільні змінні. Тоді xk +1 ,xk +2 ,…,xn – базисні змінні. Виразимо значення базисних змінних через вільні, використовуючи перетворення Жордана-Гауса:

55

xk +1 = d11 x1 + d12 x2 +…+ d1k xk + d1 ,
xk +2 = d21 x1 + d22 x2 +…+ d2k xk + d2 ,
	… … … … … … … …
	xn = ds1 x1 + ds 2 x2 +…+ dsk xk + ds .
Маємо s базисних змінних і k вільних (s+k=n).
Оскільки x j ≥ 0; j =1,n			, то

d11x1 + d12 x2 +…+ d1k xk + d1 ≥ 0,
d21x1 + d22 x2 +…+ d2k xk + d2 ≥ 0,
	… … … … … … …
	ds1x1 + ds 2 x2 +…+ dsk xk + ds ≥ 0.
або
d11x1 + d12 x2 +…+ d1k xk ≥ −d1,
d21x1 + d22 x2 +…+ d2k xk ≥ −d2 ,
	… … … … … … …
	ds1x1 + ds2 x2 +…+ dsk xk ≥ −ds .
Помножимо всі нерівності на (-1), тоді знаки нерівностей
стануть «≤». Змінні xk+1 ,xk+2 ,…,xn		цільової функції виразимо через
змінні x1 ,x2 ,…,xk .	У результаті	отримуємо задачу лінійного

програмування з обмеженнями-нерівностями.

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

Приклад 2.1. Задачу лінійного програмування

Z = 3x1 − 2x2		− 5x3 +10x4 − 2 (min),			(2.18)
	+ x2	+ 2x3 + x4 = 5,
x1
x1 − x2		− x3 + 2x4 =1,			(2.19)
	≥ 0	(i =1,4)
xi

записати в другій стандартній формі.

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

Випишемо матрицю коефіцієнтів при невідомих в основних обмеженнях системи (2.19):

56

1	1	2	1
A =				.
	−1	−1	2
1

Знайдемо ранг цієї матриці, який рівний найвищому порядку

мінора, відмінного від нуля.
rangA = 2, оскільки, наприклад		2	1		= 4 +1 = 5 ≠ 0.
		−1	2

Отже, базисними невідомими беремо х3 та х4. Розв’яжемо систему основних обмежень відносно х3 та х4 методом ЖорданаГауса:

	№	№	Коефіцієнти при невідомих								Праві частини обмежень
	таблиці	рядка	х1			х2			х3	х4	bi
	І	1	1			1			2	1	5
		2	1			–1			–1	2	1
	ІІ	1	1			1			2	1	5
		2	–1			–3			–5	0	– 9
		1		3		−	1		0	1	7
				5								5
	ІІІ					5
			1			3					9
		2							1	0
			5			5					5

З останньої таблиці запишемо систему рівнянь:

	3	x		−	1			x		+ x		=		7		,
									2		4
	5		1	5								5
	1	x		+		3		x		+ x		=	9		.
									2		3
			1	5								5
5

Оскільки x3 ≥ 0,

75 − 53 x1 + 15 x2 ≥ 0,

9 − 1 x1 − 3 x2 ≥ 0.

5 5 5

	x		=		7		−		3		x	+		1		x	,
		4
			5					5			1		5			2	(2.20)
				9				1					3
	x		=				−			x		−			x		.
		3
			5					5			1		5			2

x4 ≥ 0, то

3 x − 1 x ≤ 7 ,5 1 5 2 5

1 x1 + 3 x2 ≤ 9.

5 5 5

Помножимо обидві нерівності на 5:

57

3x1 − x2 ≤ 7,x1 + 3x2 ≤ 9.

Підставимо в цільову функцію (2.18) формули (2.20) (вираження невідомих х3 та х4 через х1 та х2):

				9		1			3
	Z = 3x1 − 2x2 −5x3 +10x4 − 2 = 3x1 − 2x2	−5			−		x1	−		x2	+
				5		5			5

	+10		7	−	3	x1	+	1	x2		− 2	= 3x1	− 2x2	−9 + x1 +3x2 +14 −6x1 + 2x2 − 2 =
			5		5			5

= −2x1 +3x2 +3.

Отже, ми отримали задачу

Z =−2x1 +3x2 +3 (min),

3x1 − x2 ≤ 7,x1 + 3x2 ≤ 9,

x1 ≥ 0, x2 ≥ 0,

яка записана в другій стандартній формі і рівносильна задачі (2.18)- (2.19). ♦

2.2.Графічний метод розв’язування задач лінійного програмування

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

Множина D в n-мірному евклідовому просторі називається опуклою множиною, якщо для будь-яких двох точок цієї множини X(1), X(2) D точки X = λX (1) + (1 −λ) X (2) належать множині D для всіх

значень λ, які належать відрізку [0; 1]. Геометрично це означає, що якщо дві точки належать множині D, то й відрізок прямої, що їх з’єднує, такожналежитьдо множини D.

Прикладами опуклих множин на площині є відрізок, пряма, круг, півплощина, квадрат і т.д.

58

Х(1)

Х(2)

Х(1)

Х(1)

Х(2)

Х(2)

а)		б)		в)
			Х(1)	(2)
				Х
	Х(1)
	Х(2)
	г)			д)
		Рисунок 2.2.1

На рис. 2.2.1 (а, б, в, г) зображено опуклі множини, рис. 2.2.1 (д) – неопукла множина, оскільки відрізок, який з’єднує точки X(1) та X(2) не повністю належить множині D. Опуклі множини можуть бути обмеженимиінеобмеженими.

Множина D називається обмеженою, якщо її можна помістити в кулю (коло) скінченого радіуса з центром в будь-якій точці множини, і необмеженою – в протилежному випадку. На рис. 2.2.1 множини б, в, г, д – обмежені, а – необмежена.

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

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

Сукупністьграничних точок множиниутворює їїграницю. Найпростішими прикладами опуклих множин є опуклі

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

Перетином областей D1, D2, ..., Dk називають множину точок, що належать кожній зцихобластей.

Перетин будь-якого числаопуклихмножин є опуклою множиною.

59

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

Вектор Х=(х1, х2, ... , хп), координати якого задовольняють систему обмежень (2.2) і (2.3), називають допустимим розв’язком (планом)

задачі. Сукупність допустимих розв’язків задачі утворює область допустимих розв’язків.

Опорним планом задачі лінійного програмування називається план, що утворений координатами вершин многогранника планів задачі. Отже, опорний план – це план, який задовольняє не менш ніж п лінійно незалежних обмежень (2.2) та обмеження (2.3) щодо знака у виглядістрогихрівностей.

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

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

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

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

Розглянемо алгоритм графічного методу розв’язування задач лінійного програмування. Слід зауважити, що окреслений метод використовується для розв’язування певного класу задач лінійного програмування, зокрема задач, число невідомих яких не перевищує 3. Хоча вже в трьохвимірному просторі важко побудувати многогранник допустимих розв’язків, а задачу лінійного програмування, яка містить більше трьох змінних графічно зобразити практично неможливо. Тому найчастіше графічним методом розв’язують задачі лінійного програмування, які містять дві невідомі і записані в другій стандартній формі (зобмеженнями-нерівностями).

60