Navch._posibnuk_Ivaschyk

№ таблиці	№ рядка		Опорний план								Коефіцієнти при невідомих
		Базис
								х1			х2	х3	х4					х5					х6	х7
	0	f			1			–2			0	0	−		1			−		1			0	–1
			2
													2					2
	′	Z	14					1			0	0	5					1					0	0
	0
			3					3					2					2
	1	х3			5			5			0	1		3					1				0	0
3			2										2					2
	2	х2	3					2			1	0	1					1					0	0
			2										2					2
	3	х6	5					5			0	0	0					0					1	0
	4	u			1			–2			0	0	−		1			−		1			0	–1
			2
													2					2

Оптимізуюча форма f досліджувалась на мінімум і ми отримали, що в нульовому рядку останньої симплекс-таблиці вже

немає додатних чисел, а це свідчить про те, що ми знайшли fmin=	1	,
	2

тобто не рівне 0. Крім цього, базис містить штучну невідому и, значить задача (5.13)-(5.14) не має розв’язку.

Отже, оптимальним розв’язком початкової задачі буде розв’язок задачі(5.11)-(5.12): Zmax=8; хопт.=(0; 1; 2; 0; 1; 5; 0). ♦

5.3.Прикладні моделі задач цілочислового лінійного програмування

5.3.1.Модель формування оптимальної інвестиційної програми при заданому бюджеті

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

181

Для побудови моделі зробимо такі припущення:

1)представлені на вибір інвестиційні об’єкти рівнозначні;

2)фінансові ресурси неможливо залучити в необмеженій кількості за вказаною відсотковою ставкою;

3)інвестиційна програма визначається тільки на початок планового періоду, а початкові витрати при цьому не перевищують зазначений бюджет;

4)інвестиційні об’єкти реалізуються як єдине ціле.

Для побудови моделі введемо такі позначення: і – індекс інвестиційного об’єкта, i =1, n ; Сі – вартість капіталу і-го інвестиційного об’єкта; Аі0 – затрати на придбання і-го інвестиційного об’єкта; Q – загальний обсяг бюджетних коштів; хі – бінарна змінна (хі = 0 або 1), значення котрої визначає, буде для і-го інвестиційного об’єкта виділене фінансування чи ні.

Враховуючи введені позначення, економіко-математична модель формування оптимальної інвестиційної програми при окресленому

бюджеті матиме вигляд.
Знайти такий розв’язок {xi	≥ 0, i =		}, який	забезпечить
		1, n
сумарну максимальну вартість інвестиційної програми:
n
Z = ∑Ci xi → max				(5.15)
i=1
при умовах:
1) з використання наявного обсягу бюджетних коштів
n
∑ Ai0 xi	≤ Q ;			(5.16)

i=1

2)з реалізації інвестиційних об’єктів як єдиного цілого

(неподільності інвестиційних об’єктів).

	1, якщореалізаціiя і-гоінвестиційногооб’єкта здійснюється,
xi
	=
	0, якщореалізаціяі- гоінвестиційногооб’єкта відхиляється,і =1,n.

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

Приклад 5.3. Акціонерне товариство має шість реальних інвестиційних об’єктів, характеристика нетто-платежів яких представлена в табл. 5.1. Обсяг бюджетних коштів становить 350 тис. грн., розрахункова відсоткова ставка складає 20 %.

182

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

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

За умовою задачі відсоткова ставка однакова для всіх планових періодів. Вартість капіталу (Сі) для і-го інвестиційного об’єкта на початок планового періоду (t=0) знайдемо, використовуючи формулу:

	Ci	= −Ai0 + ∑T		(eit − ait )(1 + r )−t	= −Ai0	+ ∑T (eit	− ait )q −t ,	(5.17)
	Аі0		t =1		і–го	t =1
де		–	затрати	на придбання		інвестиційного		об’єкта,
Ai0	= −(ei0		− ai0 ); t	– індекс планового періоду,			t =1,T ;	eit (ait ) –

поступлення (виплати) для і-го інвестиційного об’єкта в момент часу t; (1 + r)−t = q −t – коефіцієнт дисконтування для моменту часу t.

Таблиця 5.1

Платіжні нетто-ряди для інвестиційних об’єктів і вартість капіталу

Інвестиційні	Нетто-платежі в момент часу, тис. грн.						Вартість
							капіталу,
об’єкти	t = 0	t = 1		t = 2	t = 3	t = 4
							тис. грн.
IO1	–80	50		35	40	45	30,83
IO2	–120	60		45	40	55	10,92
IO3	–60	30		35	25	40	28,28
IO4	–90	50		45	50	30	26,33
IO5	–110	60		30	40	50	8,09
IO6	–40	20		25	15	30	17,18
Розрахована різниця (eit			− ait ) для і-го об’єкта на момент часу t

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

Нехай x1 , x2 ,…, x6 – невідомі величини, що вказують на

можливу реалізацію відповідно першого, другого, …, шостого інвестиційних об’єктів.

Для побудови числової економіко-математичної моделі задачі знайдемо значення вартості капіталу (Сі) і-го інвестиційного об’єкта.

Наприклад, для першого інвестиційного об’єкта маємо:

183

4

C1 = −A10 + ∑(e1t −a1t )q−t =

t=1

=−80 +50 1.2−1 +35 1.2−2 + 40 1.2−3 + 45 1.2−4 =

=−80 + 41.67 + 24.31+ 23.15 + 21.70 = 30.83.

Аналогічно знаходимо вартості капіталу для інших інвестиційних об’єктів. Отримані результати заносимо в табл. 5.1.

Числова модель задачі матиме вигляд. Знайти

Z = 30.83x1 +10.92x2 + 28.28x3 + 26.33x4 + 8.09x5 +17.18x6 → max

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

1)з використання наявного обсягу бюджетних коштів

80x1 +120x2 + 60x3 + 90x4 +110x5 + 40x6 ≤ 350 ;

2)стосовно неділимості інвестиційних об’єктів

	xi	1,	якщореалізаціяі- гоінвестиційногооб'єкта здійснюється;
		=
			якщо реалізаціяі- гоінвестиційногооб'єкта відхиляється; і =1,6.
		0,

Для знаходження цілочислового розв’язку використаємо процедуру INT програмного продукту LINA.

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

x1 =1, x2 = 0, x3 =1, x4 =1, x5 = 0, x6 =1.

Реалізація інвестиційної програми буде виконуватися при загальних витратах на придбання об’єктів обсягом 270 тис. грн. (80+60+90+40=270) і сумарній вартості капіталу розміром 102,62 тис.

грн. (30,83+28,28+26,33+17.18= =102,62).

Визначимо вигідність інвестиційної програми через величину нормативу вартості капіталу (НВК):

НВК =	[Сумарна вартість капіталу]	=	102,62		= 0,38.♦
	[Обсяг витрат на придбання]			270

5.3.2. Задача про призначення

Припустимо, що для виконання n робіт фірма має n працівників. Позначимо: і – індекс претендента на виконання певної роботи,

i =1,n ; cij – сумарні витрати на виконання i-го виду роботи j-тим працівником; j – індекс виду роботи, j =1,n . Приймемо таку умову:

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

184

Невідомою величиною в задачі буде

1, якщо i −й кандидат виконує j − ту роботу; xij = 0, в протилежному випадку.

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

Тоді економіко-математична модель задачі матиме вигляд. Знайти

n	n
Z = ∑∑cij xij → min		(5.18)
i=1	j=1

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

1) кожним кандидатом виконується тільки одна робота

n
∑xij	=1, i =1, n;	(5.19)

j=1

2)кожна робота може виконуватися одним працівником

n
∑xij =1 , j =1,n			;				(5.20)
i=1
3) відносно двійкових змінних
xij {0;1} ,i =							(5.21)
		1,n, j =1,n ;

5.4.Питання для самоконтролю

1.Яка задача математичного програмування називається цілочисловою?

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

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

4.Охарактеризуйте методи відтинання.

5.На чому базуються комбінаторні методи цілочислової оптимізації?

6.Опишіть алгоритм методу Гоморі.

7.Опишіть алгоритм методу «віток і меж».

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

9.Побудуйте формалізовану математичну модель задачі про призначення.

185

Розділ 6. Нелінійні оптимізаційні моделі економічних систем

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

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

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

Z = f (x1, x2 ,..., xn )

max(min),

(6.1)

q

(x , x

2

,..., x

n

){≤,

=, ≥}b ,

1

1

){≤,

1

q

2

(x , x

2

,..., x

n

=, ≥}b ,

1

2

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

(6.2)

q

m

(x

, x

2

,..., x

n

){≤, =, ≥}b

,

1

m

≥ 0,

j =1, n,

x j

де f (x1, x2 ,..., xn ) та qi (x1, x2 ,..., xn )

– нелінійні функції.

Часто задачу нелінійного програмування намагаються привести

до лінійного виду. Наприклад, якщо функція

задається у

вигляді

z = a +b 1 ,

то

заміною

y =

1

ми

отримаємо лінійну

функцію

x

x

z = a +by .

За

такої

заміни

похибки немає,

але заміна

функції

z = −ax2 +bx + c

деякою лінійною z = c + dy

призводить до значних

похибок, що зображено на рис. 6.1.1. В точках х1 та х3 значення обох функцій співпадають, а в точці х2 відрізняються значною мірою.

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

186

y

y2

y3

y1

х1	х2	х
		х3

Рисунок 6.1.1

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

1)знайдено оптимальний розв’язок;

2)задача суперечлива, тобто її розв’язку не існує;

3)цільова функція необмежена, отже, розв’язку також немає.

Для задач нелінійного програмування не існує універсального

методу розв’язування, тому кожного разу треба доводити існування розв’язку задачі, а також його єдиність. При розв’язуванні нелінійних задач використовують наближені методи, більшість яких дають змогу знаходити локальні оптимуми, а вже знайшовши всі локальні оптимуми, методом порівняння значень цільової функції у кожній з точок локального оптимуму можна знайти глобальний. Наприклад, на рис. 6.1.2 маємо на деякому відрізку локальні оптимуми в точках х1, х2, х4, х5, х6, х7, х9 та х10, а глобальні – в точках х3 та х8. Проте для практичних розрахунків такий метод не завжди ефективний, тому що часто наближені методи не «вловлюють» глобального оптимуму, особливо коли глобальний оптимум лежить досить близько до локального.

187

y

x1	x3	x5	x7	x9	x
x2	x4	x6	x8		x10

Рисунок 6.1.2

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

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

Z = x12 + x22 − 4x1 − 2x2 +5

за обмежень

x1 + x2 ≤ 5,x1, x2 ≥ 0.

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

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

Цільову функцію запишемо у вигляді

Z = x12 + x22 − 4x1 − 2x2 +5 = (x1 − 2)2 + (x2 −1)2 .

188

y C

5

1	A	B
		B
O		x
	2	5
		5

Ми отримали рівняння кола з центром в точці А(2;1) та радіусом

R = Z . Значить, значення функції Z буде зростати, якщо збільшуватиметься радіус кола і, навпаки, буде зменшуватися, якщо буде зменшуватися радіус кола. Ми бачимо, що коло найбільшого радіуса, яке перетинає крайню точку многокутника розв’язків – це коло з центром в точці А. Воно проходить через точку С, яка має координати (0;5). Підставимо їх в цільову функцію і маємо:

Zmax = (x1 − 2)2 + (x2 −1)2 = (0 − 2)2 + (5 −1)2 = 4 +16 = 20.

Очевидно, що найменшого значення функція досягатиме в точці

А(2;1):

Zmin = (x1 − 2)2 + (x2 −1)2 = (2 − 2)2 + (1−1)2 = 0.

В цьому прикладі ми бачимо, що точка максимуму є граничною,

аточка мінімуму – внутрішньою точкою многокутника розв’язків. ♦ Приклад. 6.2. Розв’язати графічним методом задачу нелінійного

програмування.

Z = 2x1 − x12 + x2 → extr,

2x1 +3x2 ≤ 6,

2x1 + 2x2 ≤ 4, x1 ≥ 0, x2 ≥ 0.

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

Зробимо перетворення виразу цільової функції.

189

Z = 2x − x2				+ x		,
	1	1		2			−(x2 − 2x +1)+1 = x
2x − x2		+ x	2	= x	2					2	−(x −1)2	+1,
1	1						1	1			1
Z = x2 −(x1 −1)2 +1.								x2 = (x1 −1)2
Якщо Z=0,	то маємо вираз								−1,		який є рівнянням

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

Рівняння ліній системи обмежень.

l1 : 2x1 +3x2 = 6, (0;2), (3;0); l2 : 2x1 + 2x2 = 4, (0;2), (2;0); l3 : x1 = 0;

l4 : x2 = 0.

Тоді знаходимо многокутник розв’язків ОАС, що відповідає системі обмежень.

x2

l2

l1 A 2

D

		C
O	1	2	3	x1
Знаходимо координати точки дотику параболи та лінії l2.
Знаходимо кут	нахилу	лінії	l2 до Ох1. З рівняння	2x2 + 2x2 = 4

випишемо х2:

190