2 курс. Ден. ФК, УП, ЕП 12 / Економіко математичні методи та моделі (Оптимізаційні методи) Ч.1 Ден. 2010

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

Завдання для самостійної роботи

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

−використовуючи алгоритм Гоморі;

−знявши умови цілочисельності, ЗЛП розв’язати графічним методом та використовуючи нерівність Гоморі показати, яким чином проходить правильне відтинання.

F = 6x1 +10x2 → max

F = x1 + x2 → min

x

≤ 5

5x

− 2x

≥10

1.

1

2.

1

2

−3x1 + 2x2 ≤ 6

2x1 + 3x2 ≥ 8

x1 ≥ 0, x2 ≥ 0

x1 ≥ 0, x2 ≥ 0

x1,

x2 − цілі

x1,

x2 − цілі

F = 2x1 + 5x2 → max

F = 2x1 + 3x2 → min

x

≤ 4

x

+ 3x

≥ 9

3.

2

4.

1

2

3x1 − x2 ≤ 3

x1 + x2 ≥ 4

x1 ≥ 0, x2 ≥ 0

x1 ≥ 0, x2 ≥ 0

x1,

x2 − цілі

x1,

x2 − цілі

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

1.Яка задача ЛП називається цілочисловою ?

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

3.Навести приклади економічних задач, математичними моделями яких є задачі цілочислового програмування.

Бібліографічний список до теми

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

60

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

Мета: опрацювання питань згідно запропонованого плану вивчення теми, вивчення економічної сутністі, постановки та моделей окремих типів задач нелінійного програмування (НЛП) та методів їх розв’язання.

План вивчення теми

1.Задачі дробово-лінійного програмування (ДЛП). Основні методи розв’язування задач ДЛП.

2.Метод оптимізації задач НЛП на базі використання множників Лагранжа та їх економічна інтерпретація.

3.Опукле програмування. Необхідні та достатні умови існування сідлової точки. Теорема Куна-Таккера.

4.Деякі з основних методів розв’язування задач НЛП.

5.Методи аналізу оптимального плану задачі НЛП.

6.Економічна постановка та математичні моделі окремих задач квадратичного програмування (КП). Основні методи розв’язування задач КП.

Методичні рекомендації до самостійної роботи

Задачі дробово-лінійного програмування. Задача, яка полягає у знаходженні найбільшого (найменшого) значення цільової функції

		n
		∑c j x j
	F =	j =1	→ max(min)	(18)
		n
		∑d j x j

j =1

за обмежень

61

n
∑aij x j = bi , i =
			1,m.		(19)
j =1
x j ≥ 0, j =		,			(20)
	1, n

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

Припустимо, що ∑nj =1d j xi >0 в області допустимих розв’язків,

що відповідає системі обмежень (19), (20). Введемо нові змінні

1

y j

y

=

, y

x

= y

, x

=

, j =1,n.

(21)

0

∑nj =1 d j xi

0

j

i

j

y0

Тоді

y0 ∑nj=1 d j x j =1 = ∑nj=1 d j y j , y0 > 0,

F = y0 ∑nj=1 c j x j = ∑nj=1 c j y j =Ф,

n

n

y j

1

n

∑j=1ay x j = ∑j=1ay

=

∑j=1ay y j .

y0

y0

Запишемо задачу за допомогою нових позначень як задачу

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

Ф = ∑nj=1c j y j

→ max,

∑nj=1 aij y j −bi y0 = 0,i =

,

1, m

∑nj =1 d j y j =1,

y0 ≥ 0, y j ≥ 0, j =1, n.

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

62

Задачі нелінійного програмування. Розв’язуючи задачі оптимального управляння, доводиться враховувати нелінійний характер взаємозв’язків між економічними показниками. У загальному вигляді нелінійна економіко-математична модель має вигляд:

Z = f (x1, x2 ,..., xn ) → max(min)

за умов

qi (x1, x2 ,..., xn ){≤,=,≥}bi

(i =1, m),

де f (x1, x2 ,..., xn ) і qi (x1, x2 ,..., xn ) - нелінійні функції.

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

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

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

Розглянемо задачу нелінійного програмування:

Z = f (x1, x2 ,..., xn ) → max(min)

(22)

63

за умов

qi (x1, x2 ,..., xn ) = bi , (i =		) ,	(23)
	1,m

де функції f (x1, x2 ,..., xn ) і qi (x1, x2 ,..., xn ) - диференційовані.

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

Ця функція називається функцією Лагранжа і подається у вигляді:

m

L(x1, x2 ,..., xn ;λ1,λ2 ,...,λm ) = f (x1, x2 ,..., xn ) +∑λi (bi −qi (x1 , x2 ,..., xn ))

i=1

де λi –– не визначені поки що величини, так звані множники Лагранжа.

Знайшовши частинні похідні функції L за всіма змінними і прирівнявши їх до нуля:

∂L∂x j∂L

∂λj

= 0 ( j =1,n)

= 0	(i =1,m)

запишемо систему

∂f (x , x

,..., x

)

m

∂q

(x

, x

,..., x

)

( j =

)

= 0

1,n

1

2

n

+∑

i

1

2

n

∂x j

i=1

∂x j

bi −qi

(x1 , x2 ,..., xn ) = 0

(i =1,m)

що є, як правило, нелінійною.

Розв’язавши цю систему, знайдемо X * = (x1, x2 ,..., xn ) і

λ0 = (λ1,λ2 ,...,λm ) –– стаціонарні точки. Оскільки їх визначено з необхідної умови екстремуму, то в них можливий максимум або мінімум. Іноді стаціонарна точка є точкою перегину (сідлова точка).

64

Для перевірки стаціонарних точок і визначення типу екстремуму необхідно дослідити в околі стаціонарних точок виконання достатніх умов екстремуму, тобто дослідити в околі стаціонарних точок диференціали другого порядку, якщо для функцій (22), (23) існують другі частинні похідні і вони неперервні. Для цього будується матриця Гессе, що має блочну структуру розмірністю ( m + n )×( m + n ):

H= O′ P ,

P Q

де O - матриця розмірністю (m×m) , що складається з нульових елементів;

P - матриця розмірністю (m ×n) , елементи якої визначаються так:

	∂q ( x )
	1
	∂x1
P =	K
	∂qm ( x )
	∂x
	1

L ∂q1( x ) ∂xn

K K ,

L ∂qm ( x ) ∂xn

P′- транспонована матриця до P розмірністю ( n ×m ),

Q - матриця розмірністю ( n ×n ) виду:

		∂2 L( x,λ )
	Q =		, де i =1,m ,			j =1,n .
		∂xi ∂x j

Для визначення виду екстремуму використовують таки ознаки:

1)Точка X = (x1, x2 ,Kxn ) є точкою максимуму, якщо починаючи з головного мінору порядку (m +1) , наступні (n −m) головних мінорів матриці H утворюють знакозмінний числовий ряд, знак

першого члена якого визначається множником (−1)m+1.

2)Точка X = (x1, x2 ,Kxn ) є точкою мінімуму, якщо починаючи з головного мінору порядку (m +1) , наступні (n −m) головних

мінорів матриці H утворюють знакозмінний числовий ряд, знак першого члена якого визначається множником (−1)m .

65

У загальному вигляді нелінійна економіко-математична модель має вигляд:

Z = f (x1, x2 ,..., xn ) → max(min)						(24)
за умов
qi (x1, x2 ,..., xn ){≤,=,≥}bi						(25)
(i =		),
	1, m
x j ≥ 0,			j =
				1,n.		(26)
де f (x1, x2 ,..., xn ) і qi (x1, x2 ,..., xn )			- нелінійні функції.

Якщо в n −вимірному просторі Rn визначено множину обмежень М, що відповідає системі обмежень (25), то розв’язування задачі (24)-(26)

зводиться до відшукання в множині М такої точки X * = (x1*, x2* ,Kxn* )

(оптимальної точки, або розв'язку, через яку проходить гіперповерхня

F(x1, x2 ,..., xn ) = h найвищого рівня (в задачі на максимум) або найнижчого рівня (в задачі на минимум).

Алгоритм графічного розв'язку задач нелінійного програмування:

1.Знаходять область допустимих рішень задачі, обумовлену співвідношеннями (25)-(27), якщо вона порожня, то задача не має рішення.

2.Будують гіперповерхню F(x1, x2,..., xn ) = h для деякого значення h .

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

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

Завдання для самостійного розв’язання

1.Розв’язати задачу дробово-лінійного програмування.

66

F =

3x1 −2x2

→ max

F =

−5x1 + 4x2

→ max

x + 2x

2

min

−2x

−3x

2

min

1

1

2x + 4x

≤16

2x

−4x

≤12

1.1.

1

2

1.2.

1

2

−4x1 + 2x2 ≤8

− x1 + 2x2 ≤8

x +3x

2

≥9

x

+ x

2

≥10

1

1

x1 ≥ 0; x2 ≥ 0

x1 ≥ 0; x2 ≥ 0

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

F = x2 − x12 +6x1 → max

2x +3x

≤ 24

F = (x

−3)2 + (x

2

− 4)2 → min

1

1

2

3x1 + 2x2 ≥ 7

2.1.

x1

+ 2x2

≤15

≤ 24

2.2.

− x2 ≤ 8

3x + 2x

2

10x1

1

−18x

+ 4x

≤12

≤ 4

2

x2

1

x ≥ 0, x

2

≥ 0

x1 ≥ 0,

x2 ≥ 0

1

3. За методом Лагранжа знайти точку умовного екстремуму функції.

	F = 2x		2 + x	2	,				F = x2	− x2 ,
3.1.		1		2				3.2.	1	2
	2x1 + 3x2 = 5								3x1 + 4x2 =12
	F = x	2	+ 2x	2	+ 3x	2	,		F = x2	+ 2x + x	2	−5x	2	,
3.3.	1			2		3		3.4.	1	1	2
	x1 + 2x2 + x3 = 8								x1 + 3x2 = 6

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

1.Охарактеризуйте задачі дробово-лінійного програмування

(ДЛП).

2.Які існують методи розв’язання задач ДЛП?

3.Сформулюйте загальну задачу нелінійного програмування.

4.У чому полягає метод оптимізації задач НЛП на базі використання множників Лагранжа та у чому полягає їх економічна інтерпретація?

5.Визначте опукле програмування.

67

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

7.Які є основні методи розв’язування задач НЛП?

8.Які існують методи аналізу оптимального плану задачі НЛП?

9.Сформулюйте економічну постановку та математичні моделі окремих задач квадратичного програмування (КП).

10.Як формулюється теорема Куна - Такера для задач квадратичного програмування ?

11.Назовіть основні методи розв’язування задач КП.

Бібліографічний список до теми

[1], [3], [4], [5], [6], [7], [8], [10], [13], [14], [15], [16].

Тема 8. Динамічне програмування

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

План вивчення теми

1.Загальна постановка задачі динамічного програмування та її геометрична інтерпретація. Принцип оптимальності.

2.Знаходження розв'язку економічних задач методом динамічного програмування.

3.Деякі економічні задачі, які розв’язуються методами динамічного програмування

68

g(x)

Методичні рекомендації до самостійної роботи

При вивченні теми „Динамічне програмування” слід звернути увагу на те, що усі економічні процеси та явища є динамічними, оскільки функціонують і розвиваються не лише у просторі, а й у часі. Народне господарство, його галузі, регіони чи окремі підприємства мають розробляти стратегічні і тактичні плани. Перші визначаються з допомогою динамічних моделей, розв’язки яких знаходять методами динамічного програмування. Зауважимо, що сума оптимальних планів на окремих відрізках планового періоду T не завжди являє собою план, оптимальний на всьому такому періоді.

Розглянемо задачу оптимальності розподілу капітальних вкладень, які можуть бути використані двома способами: з метою розвитку рослинництва або тваринництва. Відомо, що за першого способу отримаємо прибуток , а за другого –– h( y). У такому разі однокрокову задачу можна подати у вигляді: Z = g(x) + h( y) → max за умов x + y = b , x ≥ 0, x ≥ 0.

Нехай Z = Z1, b = b1, x = x1, y = b1 − x1. Тоді дану задачу можна записати так: Z = g(x) + h(b1 − x1) → max .

Розглянемо її як задачу оптимального використання капітальних вкладень за окремими інтервалами планового періоду T , маючи на меті розподілити залишок капітальних вкладень на кінець j -го

інтервалу ( j =1,2,..., n) двома зазначеними способами. При цьому

критерій оптимізації не змінюється: максимізуємо обсяг прибутку за весь плановий період T .

Якщо на першому інтервалі використано b1 капітальних вкладень, то на його кінець залишилося їх b2 = cx1 + d(b1 − x1), де c, d –

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

69