Твердження 4. Якщо у   є оптимальний розв’язок допоміжної


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

—*

ЗЛП, то х , (компоненти якого обчислюються через компоненти у за формулами (2.22), якщо покласти уі = у*, г = 1, п +1) є опти-мальним розв’язком ЗДЛП. Оптимальне значення цільової функ-ції ЗДЛП збігається з оптимальним значенням цільової функції допоміжної ЗЛП.

Алгоритм розв'язування задачі дробово-лінійного програмування

1-й крок. Переконатися в існуванні допустимих планів ЗДЛП, додатності та обмеженості на цій множині лінійної функції U\x), що знаходиться в знаменнику функції цілі ЗДЛП.

2-й крок. Шляхом введення нових змінних скласти відповідну допоміжну ЗЛП та знайти її розв’язок.

3-й крок. За інформацією про розв’язок допоміжної ЗЛП за формулами (2.22) обчислити розв’язок ЗДЛП.

Застосування цього методу надано в розділі 3.5 при дослі-дженні проблеми оптимізації рентабельності підприємства.

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

Найбільше поширення на практиці та найбільш вивченими (дослідженими) є задачі з нелінійною цільовою функцією та лі-нійною системою обмежень.

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

Знайти х > 0,   і = 1,п,           (2.23)

які в області G , визначеній умовами типу:

п                    

XSi/(ХІ) — Ь■ ,   j = 1,m ,     (2.24)

максимізують цільову функцію:

п

F(x) = 2 Уї (ХІ ) .        (2.25)

і=1

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

п

f(x) = ^ft(xi) •   (2.26)

і=\

Відомо, що функція f(x) може бути апроксимована з наперед заданим ступенем точності дробово-лінійною функцією f{x) [19], [25].

Використовуючи цю можливість, замінимо   f.(x.)   (/ = 1,п)  їх

дробово-лінійними аналогами /. (ху.); gtJ (ху.) — відповідно gtJ (х.).

Тоді для задачі (2.23)—(2.25) отримаємо її наближений аналог:

Знайти Xj > 0,   j = \,n,          2.23')

які в області G , визначеній обмеженнями:

2 Sij (хj) - b,:,   i = 1, т,( 2.24')

максимізують функцію:

 

 

F(x) = Х/(х ) • В основі методів розв'язування задач сепарабельного типу лежить трьохкрокова процедура:

1.         Дробово-лінійна апроксимація функцій gtJ (ху.) і /. (ху.);

2.         Побудова апроксимуючої задачі.

3.         Застосування видозміненого симплекс-методу для розв'язуван-ня апроксимуючої задачі.

Природно, що в загальному випадку можна знайти локальний оптимум наближеної, і відповідно початкової, задачі. Зауважимо, якщо g9(xj) і fj(Xj) мають властивості, які забезпечують існу-вання єдиного екстремуму початкової задачі, наближена задача має ту саму властивість.

Побудова апроксимуючоїзадачі і визначення локального максимуму

Нехай функції gy (xj), fj (xj) неперервні i відомі допустимі інтервали зміни змінних ху ,j = \,n.

Розіб’ємо їх точками xkj для кожного j та обчислимо значен-ня функцій в цих точках, тобто:

g(P = g.. (х,.),    і = 1, т,    j = 1,п

f(p = fj (х,.),    j = 1, п .

Побудуємо дробово-лінійну апроксимацію цих функцій за фо-рмулами:

ˆ. (х -) =

к=0

ЕЧ-/Г  (2.27)

r;

g.. (xj) = X ^kjSf) ,   i = 1,m    (2.28)

де: r. — кількість інтервалів, на які точками хіу. розбивається ін-

тервал [0,ау]   зміни х,   Xkj — деякі числа, які задовольняють

умову А.

Умова А: для довільного х. не більше двох причому сусідніх Xkj в виразі

Xj = Y.'kyXy   (2.29)

к=0

можуть бути додатними, тобто для довільного х, яке знаходиться між хк й хк+1, тобто хк < х < хк+1 можливе представлення:

х = Ххк+1 + (1 - Х)хк, де X є [0,1].

Відмітимо, що в виразах для fj(xj) і gy(Xj) використовується одне і те саме розбиття інтервалу зміни ху.,   j = 1,п .

Враховуючи (2.27)—(2.29), запишемо допоміжну для (2.23)— (2.25) задачу:

г;

Знайти Xj = ^ХщХу,   j = 1,п ,         (2.30)

к=0

які в області G , визначеній умовами:

 

/=1к=0

 

g(k)<bt,    і = 1,т,        (2.31)

 

Гі

kj к=0

Х^ь = 1,   ^ь ^ 0 для всіх к та j,        (2.32)

максимізують функцію:

п    ГІ

/(х) = ZiL^kjfP .          (2.33)

у'=1 к=0

Задача (2.31)—(2.33) відносно  Xkj  називається апроксимую-

чою задачею в X — формі. Розв’язок задачі (2.31)—(2.33) може бути одержаний симплекс-методом, видозміненим відповідно до додаткової умови А на введені змінні.

Нехай X(0j — оптимальний розв’язок задачі (2.31)—(2.33), тоді наближений розв’язок початкової задачі визначається за форму-лою (2.30), в якій Xkj = Х(к^.

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

Опишемо процед—ру ділення.

Нехай gf) ,fjk)       значення, одержані при діленні інтервалу,

якому належить змінна ху., (j = 1,п) з кроком h, їм відповідає задача типу (2.31)—(2.33), х*х — точка її локального оптимуму. Окіл точки х* розіб’ємо інтервал з кроком й/2 і знайдемо нові значення gf) ,fjk) в точках ділення. Побудуємо і розв’яжемо нову задачу типу (2.31)—(2.33), яка апроксимує початкову зада-чу (2.23)—(2.25). Нехай х*+1 — точка її локального оптимуму.

Якщо   х*-х*+1 <р, де р — задане значення, то х* — розв’язок

початкової задачі. Зрозуміло, величина кроку h впливає на роз-мірність задачі типу (2.31)—(2.33), тому вона не може бути до-сить малою. Якщо деяка змінна хт входить в умови задачі і ці-

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

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

—        знайдений розв’язок в загальному випадку визначає точку локального оптимуму;

—        немає способу встановити ступінь близькості знайденої то-чки локального оптимуму до глобального оптимуму.

Існує важливий окремий випадок, коли локальний екстремум сепарабельної задачі (2.23)—(2.25) співпадає з її глобальним екс-тремумом. Цей факт встановлює наступна теорема:

Якщо /•(*•) —опуклі вниз, множина G можливих розв’язків

опукла, то розв’язуючи задачу (2.31)—(2.33) як задачу лінійного програм’вання (без врахування умови (А)), одержимо оптималь-ний розвязок наближеної задачі.

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