Метод функціональних рівнянь.

Як показав Р. Бельман, знаходження оптимального рішення багатоетапного процесу зводиться до вирішення деякого функціонального рівняння. Роздивимося приклад багатоетапного процесу розподілу. Нехай є деяка кількість засобів х, які треба вкласти в розвиток двох неоднорідних підприємств. Відомо, якщо в перше підприємство вкласти у, а в 2-е - х - у засобів, то прибуток буде відповідно g(у) і h(х-у). Необхідно вибрати у так, щоб загальний прибуток

W1(х; у) = g(y) + h (x-y) (4.1.) був максимальний.

Таким чином, потрібно визначити max W1 (x; y)

Якщо g(y) і h(x-y) функції безперервні для х > 0, то така задача має рішення. Цей процес одноетапний.

Зауваження. х і g(y) можуть вимірюватися в різних величинах наприклад, х - грошова сума, g(y) кількість людино-годин, зекономлених у результаті застосування машин, куплених за засоби у.

Ускладнимо задачу. Розглянемо двохетапний процес. Припустимо, що за рахунок витрат, необхідних для одержання прибутку g(y), початкова кількість засобів зменшується до а. у, 0 < a < 1, аналогічно для 2-го підприємства: х-у зменшується до b(х-у), 0<b<1. Таким чином, після здійснення одноетапного процесу залишок засобів складає ау + b(х-у). Повторимо процес розподілу сумарного залишку, вважаючи, що ау + b(х-у) = х1 = у1 + (х11), де 0 < y1 < x1. У результаті цього розподілу на 2-ом етапі одержимо прибуток g(y1) + h(x1-y1), а повний прибуток за два етапи W2(x, y, y1) = g(y) + h(x-y) + g(y1) + h(x1-y1), причому max W2 (x, y, y1) знаходиться по двохмірної області 0 < y < x, 0 < y1 < x1.

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

WN(x; y; y1; ... ; yN-1)=g(y)+h(x-y)+g(y1)+h(x1-y1)+ ... +g(yN-1)+h(xN-1-yN-1) (1.1)

де x1 = ay + b(x-y); 0 < y < x

x2 = ay1 + b(x1 - y1) 0 < y1 < x1 (1.2)

xN-1 = ayN-2 + b(xN-2 - yN-2) 0 < yN-2 < xN-2 0 < yN-1 < xN-1

Одержуємо max WN по області (1.2.), N - мірної області. Рішення такої задачі складне. Тому вирішимо задачу поетапно, наслідуючи принципу умовної оптимальності в N-етапному процесі. Визначимо функцію fN(x) як максимум прибутку, отриманого від
N-етапного процесу, що починається з розміру х, для
N=1, 2, ..., і x > 0, тобто fN(x) = max WN(x; y; y1; ... ; yN-1) (1.3)

0<y<x

f1(x) = max g(y) + h(x-y) (1.4)

0<y<x

Розглянемо двохетапний процес. Повний прибуток складається з прибутків 1 і 2-го етапів, причому на 2-ому етапі для розподілу залишається сума ау+b(x-y). Необхідно одержати максимальний прибуток, тому якою б не була обрана у, сума, що залишилася до наступного етапу ау + b(х-у), повинна бути використана щонайкраще (принцип умовної оптимальності), тобто від другого етапу одержимо прибуток f1[ay + b(x-y)]. Тоді повний max прибуток за два етапи висловиться рекурентним співвідношенням

Метод функціональних рівнянь. - student2.ru f2(x) = max {g(y) + h(x-y) + f1[ay + b(x-y)]} (1.5)

0<y<x

Міркуючи аналогічно, у випадку N-етапного процесу отримуємо основне функціональне рівняння

Метод функціональних рівнянь. - student2.ru f(x) = max {g(y) + h(x-y) + fN-1[ay + b(x-y)]} (1.6)

0<y<x

Використовуючи (1.6.) знаходимо f1, потім f2 і т.д., причому на кожному k-етапі одержуємо й оптимальне уk(х).

Застосування розглянутого методу функціональних рівнянь до рішення задач Д.П. дозволяє призвести рішення однієї N-мірної задачі до послідовності однотипних рішень N одномірних задач.

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

Метод функціональних рівнянь. - student2.ru fN(x) = max [gN(yN) + fN-1(x-yN)] (1.7)

0<yN<x

де f - критерій процесу, N - число етапів, х - змінна, що характеризує стан процесу на N-ому етапі, fN(x) - результуюче значення критерію, що може бути отримане за N- етапів, що залишилися, починаючи зі стану x, yN - керуюча перемінна, від вибору якої залежить величина fN; gN(xN) - величина критерію, отримана на N-ому етапі при оптимальному виборі yN, 0<yN<x; fN-1 (x-yN) - результуюче оптимальне значення критерію за N-1 етапів , що залишилися, починаючи зі стану x - yN.

Нехай на N-ому етапі обране оптимальне рівняння yN = yN*. Тоді стан системи на N-1 етапі описується функціональним рівнянням

Метод функціональних рівнянь. - student2.ru fN-1(x-yN*) = max [gN-1(yN-1) + fN-2(x-y*-yN-1)] (1.8)

0<yN-1 <x-yN*

Задача розподілу ресурсів

У розглянутої раніше задачі передбачалося, що повний прибуток залежить тільки від початкової кількості засобів і числа етапів N і не залежить від часу початку процесу. Припустимо, що в результаті розподілу засобів х на величини y і х-у на k-ому році отриманий прибуток gk(x; y) і для подальшого розподілу залишилася кількість засобів rk(x; y). Необхідно визначити керування, що дозволяє максимізувати повний прибуток N-етапного процесу.

Нехай ф. gk(x; y) і rk(x; y) неперервні для x > 0 і
0 < y < x; а rk(x; y) у цій області 0 < rk(x; y) < ax; а < 1 для k =1, 2.

Нехай fk N(x) повний прибуток від N - етапного процесу, що починається з величини х на k-ом році, якщо дотримувався принцип оптимальності. Тоді при N=1

Метод функціональних рівнянь. - student2.ru fk1(x) = max gk(x; y)

0<y<x

при N > 2, аналогічно міркуючи, отримаємо

Метод функціональних рівнянь. - student2.ru fkN(x) = max {[gk(x;y) + fk+1, N-1 [rk(x;y)]}

0<y<x

Для спрощення запису замість подвійних індексів будемо використовувати один. Положимо, що кожному етапу відповідають значення k = 1; 2; ...; N і визначимо fk(x) як повний прибуток від процесу, що починається з величини х на k-ому етапі і закінчується на N-ому етапі, якщо дотримується принцип оптимальності. Тоді маємо такі функціональні рівняння:

при k=N

Метод функціональних рівнянь. - student2.ru fN(x) = max gN(х; y) (1.9)

0<y<x

при k = N - 1, ... , 2, 1

Метод функціональних рівнянь. - student2.ru fk(x) = max {[gk(x;y) + fk+1 (rk+1(xk;y)] (1.10.)

0<y<x

Приклад 1.2. Для розвитку двох галузей 1 і II на 5 років виділено х засобів. Кількість засобів у, вкладених у галузь I, дозволяє одержати за один рік прибуток Метод функціональних рівнянь. - student2.ru (у) = у2 і зменшується до розміру Метод функціональних рівнянь. - student2.ru (у) =0,75у. Кількість засобів х - у, вкладених у галузь II, дозволяє одержати за один рік прибуток x(х-у) = 2(х-у)2 і зменшується до величини x(х-у) = 0,3 (х-у).

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

Рішення. П'ять років розіб'ємо на 5 етапів, тобто N=5; k = 1; 2, ..., 5, хоча процес безперервний, величини х та у для наочності будемо позначати індексами.

Умовну оптимізацію почнемо з 5-го етапу, розподіляючи залишок засобів ху. Для цього визначимо оптимальне значення у5. Складемо вираження для (4.9.)

g5(x4; x5) = Метод функціональних рівнянь. - student2.ru5) + Метод функціональних рівнянь. - student2.ru45) = y52 + 2(x4-x5)2

f5(x4) = max [y52 + 2(x4 - y5)2].

0<y<x

Так як для 5-го етапу х4 є постійною величиною, то потрібно знайти max функції на відрізку [0; x4].

Метод функціональних рівнянь. - student2.ru = 2у5 - 4(х4 - у5) = 0; у5 = Метод функціональних рівнянь. - student2.ru х4.

Метод функціональних рівнянь. - student2.ru = q44; у5) = 6 > 0; тобто точка у5 = Метод функціональних рівнянь. - student2.ru х4 точка min.

Визначимо значення ф. на кінцях: q5 (x4; 0) = 2x42;

q5 (x4; x4) = x42.

Одержимо, що ф. q5 (x4; х5) приймає max при у5 = 0, отже f5(x4) = 2x42.

Таким чином, max прибуток на 5-ому етапі досягається при вкладенні всіх засобів, що залишилися, у II галузь.

Для 4-го етапу, використовуючи рівняння (4.10)

Метод функціональних рівнянь. - student2.ru

Тут х4 - сума засобів , що залишилися, якщо на 4-ому етапі було витрачено у4 засобів у галузі I і х34 у галузі II.

Таким чином х4 = 0,75у4 + 0,3 (х3 - у4).

Тоді

Метод функціональних рівнянь. - student2.ru

Для рішення знаходимо

Метод функціональних рівнянь. - student2.ru = 2у4 - 4(х3 - у4) + 4(0,75-0,3) [(0,75y4 + 0,39x3 - y4)] = 0;

6,81 y4 - 3,46x3 = 0 y4 = 0,5x3

Метод функціональних рівнянь. - student2.ru = 6,81 > 0, тобто це точка min f4(x3) = 1,3 x32.

Знаходимо значення z4 на кінцях [0; x3]

z4(x3; 0) = 2x32 + 0,18x32 = 2,18 x32

z4(x3; x3) = x32 + 1,125x32 = 2,125 x32

Тоді max z4 при у4 = 0 і f4(x3) = 2,18 x32

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

Запишемо функціональне рівняння для III-го етапу

Метод функціональних рівнянь. - student2.ru

Тут х3 - сума засобів , що залишилися після 3 етапу, якщо на 3-му етапі було витрачено у3 засобів у галузі I і х23 у II галузі.

х3 = 0,75у3 + 0,3 (х2 - у3).

Тоді

Метод функціональних рівнянь. - student2.ru

Вирішуючи його, одержуємо: у точці min z3=0,5х2;
z3(x3; 0,5х2)=1,35x22 при у3=0 z3(x2; 0)=2,2x22
при у3 = х2 z3(x2; x2) = 2,23x22

Тоді f3(x2) = 2,23 x22

Одержимо max прибуток на 3-му етапі при вкладенні всіх засобів х2, що залишилися у I-у галузь.

Запишемо функціональне рівняння для II-го етапу

Метод функціональних рівнянь. - student2.ru

Так як х2 = 0,75у2 + 0,3 (х1 - у2), то

Метод функціональних рівнянь. - student2.ru

Вирішуючи це рівняння, одержуємо min z2 = 1,36х12
при у2 = 0,5х1 z2(x1; 0) = 2,21 x12; z2(x1; x1) = 2,25x12. Отже, f2(x1) = =2,25 x12

Таким чином, для одержання max прибутку на 2-ому етапі всі засоби, що залишилися після І етапу вкласти в I-у галузь.

Запишемо функціональне рівняння для I-го етапу

Метод функціональних рівнянь. - student2.ru

Вирішуючи, маємо: Метод функціональних рівнянь. - student2.ru z1(x;0)=2,2x2 z1(x; x) = 2,27x2

Тобто для одержання максимального прибутку на І-ому етапі всі засоби треба вкласти в I-у галузь.

Висновок. Оптимальне керування процесом розподілу виділених засобів полягає в наступному: на протязі перших трьох років усі засоби варто вкладати тільки в I-у галузь, а на протязі останніх двох - у II галузь.

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

I рік - усі засоби х в I галузь, залишок на початок 2-го року 0,75х

II рік - 0,75х в I-у галузь, залишок 0,752х = 0,56х

III рік - 0,56х вкладаємо в I-у галузь, залишок 0,75*0,56х = 0,42 х

IV рік - 0,42х вкладаємо в 2-у галузь, залишок 0,42*0,3х = 0,126х

V рік - 0,126х вкладаємо в 2-у галузь, залишок
0,3*0,126х = 0,038х.

При такому розподілі max прибуток за 5 років f(x) = 2,27х2.

Методом функціональних рівнянь можуть бути вирішені і більш складні задачі розподілу ресурсів.

Задача 1.3. Є деяка кількість засобів зв'язку х, яку можна використовувати N різноманітними засобами. Нехай xi - кількість засобів, використовувана при i-ому способі розподілу (i = 1; 2; N) qi(xi) прибуток, отриманий у цьому випадку. Необхідно визначити, яку кількість засобів і якого засобу варто використовувати, щоб одержати максимальний загальний прибуток.

Рішення. Запишемо математичну модель задачі

Метод функціональних рівнянь. - student2.ru

Максимальний загальний прибуток залежить тільки від Х та N. Тому можна визначити послідовність функцій

Метод функціональних рівнянь. - student2.ru для x>0 k = 1; ...; N

Одержуємо такі функціональні рівняння:

для одноетапного процесу

Метод функціональних рівнянь. - student2.ru (1.11)

для N - етапного процесу

Метод функціональних рівнянь. - student2.ru N = 2; 3; ... (1.12)

Використовуючи (1.12-1.13) вирішимо задачу про завантаження літака.

Задача 1.4. Нехай є літак вантажопідіймальністю W і його варто завантажити предметами N різноманітних типів і різноманітної цінності. Необхідно завантажити літак предметами максимальної цінності, якщо відомо, що Pi - вага одного предмета i-го типу, xi - число предметів i-го типу. Ci - вартість предмета i-го типу i = 1; ...; N.

Рішення. Складемо математичну модель задачі.

Знайти max F (x1; x2; ...; xn) = Метод функціональних рівнянь. - student2.ru Cixi

при Метод функціональних рівнянь. - student2.ru Рixi < W, xi = 0; 1; 2; ...

У силу цілочисленості xi це не задача Л.П.

Вирішимо задачу, рахуючи W - довільною величиною.

Якщо завантажувати літак тільки предметами 1-го типу, то рішення очевидно x1 = [W/Рi] - ціла частина. f1(W) = [W/Р1] . C1

Нехай літак завантажується предметами 1-го і 2-го типів.

Позначимо max вартість у цьому випадку f2(W).

Якщо завантажувати x2 - предметів 2-го типу, то вага предметів 1-го типу не повинна перевищувати W2 - P2x2, а їхня вартість C2x2.

Тоді max вартість вантажу предметів І типу - f1(W - P2x2)

Метод функціональних рівнянь. - student2.ru

Продовжуючи процес, додаючи предмети нових типів, через N кроків

Метод функціональних рівнянь. - student2.ru

де fN-1 (W - PNxN) - максимальна вартість вантажу, що складається з предметів N-1 типу, загальна вага котрих < W - PNxN.

Умови. Нехай W = 83 од., а вага і вартість предметів відповідно рівні: Р1 = 24; Р2 = 22; Р3=16; Р4=10; С1=96; С2=85; С3=50; С4=20.

Тому що для знаходження значень fN(W) необхідно знати значення fN-1 (W-PNxN), то при рішенні будуть потрібні значення функції f(W) для всіх W 0 < W < 83.

Нехай літак завантажують тільки предметами 1-го типу. Тоді можна завантажити максимальну кількість [83/24]=3, тобто х1 = 0; 1; 2; 3.

Тоді таблиця 1 f1(W) має вигляд.

Таблиця 1 Таблиця 2

W f1(W) x1   W f2(W) x2 x1
0-23   0-21
24-47   22-23
48-71   24-43
72-83   44-45
        46-47
        48-67
        68-69
        70-71
        72-83

Нехай літак завантажують предметами першого і 2-го типів (2 етап) Тому що Р2 = 22 од., то х2 = 0; 1; 2; 3 ([W/P2] = [83/22] = 3.

Розмір вантажопідіймальності розбиваємо на інтервали, з огляду на Р1 і Р2. За допомогою таблиці 1 і функціонального рівняння

Метод функціональних рівнянь. - student2.ru

Переходимо до 3-го і 4-го етапів, що полягають відповідно в послідовному завантаженні літака предметами 1-го, 2-го, 3-го типу і 1-го, 2-го, 3-го і 4-го типу. На 3-му етапі, використовуючи таблицю 2, складаємо таблицю 3.

Таблиця 3 Таблиця 4

W f3(W) х3 x2 x1   W f4(W) х4 х3 x2 x1
0-15   0-9
16-21   10-15
22-23   16-21
24-31   22-23
32-37   24-31
38-39   32-37
40-43   38-39
44-45   40-43
46-47   44-45
48-63   46-47
64-67   48-57
68-69   58-63
70-71   64-67
72-83   68-69
            70-71
            72-81
            82-83

На підставі таблиці 4 можна зробити висновок, що max вартість завантаження вантажу 308 од., причому першого типу 3 од. і 4-го типу 1 од.

Висновок. Знайдено оптимальні рішення не тільки вантажопідіймальністю W = 83 од., але і для літаків будь-якої вантажопідіймальності 0 < W < 83 од.. Це характерна риса динамічного програмування.

Інша інтепретація задачі: стрижень довжиною W потрібно розкроїти на заготовки довжиною L1, L2, L3, L4 з вартостями відповідно, C1, C2, C3, C4, так щоб сумарна вартість була max.

Таким чином, метод Д.П. можна успішно застосовувати і для розкрою матеріалів.

Наши рекомендации