Інформаційні технології та моделювання бізнес-процесів - Томашевський О.М. - 8.2. Основне функціональне рівняння Белмана

Запишемо принцип оптимальності у формалізованій формі. Для цього позначимо через Fn (So) максимальний виграш, який одержується за n кроків при переході системи S з початкового стану So в кінцевий стан Sn при реалізації оптимальної стратегії керування U * = (u1*, u2*,..., un*), а через Fn-k (Sк) - максимальний виграш, який одержується при переході системи з будь-якого стану Sк в кінцевий стан Sn при оптимальній стратегії керування на останніх n - k кроках. Тоді

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

Покладемо в рекурентне співвідношення (8.1) k = п -1, одержимо

Отже, на n -му кроці знаходимо умовно оптимальні керування для будь-якого допустимого стану системи після (n - 1)-го кроку. Іншими словами, в який би стан система не перейшла після (n -1) -го кроку, нам вже відомо, яке оптимальне керування вибрати на n -му кроці і яке при цьому буде значення функції (8.2).

Після того, як знайдені всі умовно оптимальні керування на n -му кроці, переходимо до відшукання всіх умовно оптимальних керувань на (n -1) -му кроці. Для цього покладемо у формулу (8.1) k = и - 2. Одержимо

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

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

Для відшукання оптимальної стратегії керування, якій відповідатиме максимальний виграш, треба тепер пройти всю послідовність кроків від початкового до кінцевого. На першому кроці за оптимальне керування u1* беремо умовно оптимальне керування, знайдене на цьому кроці. Керування u1* переведе систему S із стану So в деякий стан S11*. Цей стан визначає знайдене умовно оптимальне керування на другому кроці, яке приймаємо за оптимальне керування u2* на другому кроці. Знаючи u2*, знаходимо стан S2, в який керування u2* переведе систему із стану S1*. На основі S2 знаходимо u3* і т. д. В результаті цього знайдемо оптимальну стратегію керування U* = (u1*, u2*,..., un*), якій відповідатиме максимальний виграш, тобто розв'яжемо задачу.

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

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

однокроковий, двокроковий і n -кроковий (n > 2) процеси, які складаються відповідно з одного, двох і п періодів.

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

Розглянемо спочатку цю задачу як однокроковий процес, який складається з одного періоду (наприклад, року). Нехай підприємству А виділено у ресурсів, а підприємству В - х - у. Якщо вважати, що впродовж визначеного періоду вкладені ресурси у приносять дохід р (у) , а ресурси х - у дохід q (х _ у), то загальний дохід від вкладених ресурсів становитиме

Позначимо через F1 (х) найбільший дохід, який можуть принести ресурси х при оптимальному розподілі їх між підприємствами А і В . Тоді

Тепер цю задачу розглянемо як двокроковий процес, який складається з двох періодів. Дохід одержується внаслідок випуску і реалізації продукції, тому на початок другого періоду підприємство А матиме ау ресурсів, а підприємство В - b (х - у), де 0 ≤ а ≤ 1, 0 ≤ b ≤ 1. Найбільший дохід, який можна одержати від сумарного залишку ау + b (х - у) на протязі другого періоду, дорівнює F1 (ау + b (х - у)). Позначимо через F2 (х) найбільший дохід, який може бути одержаний від суми х за обидва періоди. Цей дохід дорівнює максимальному значенню суми доходів першого і другого періодів за умови, що наявні на початок кожного періоду ресурси розподіляються найкращим чином, тобто

Приклад 8.1. Нехай для розвитку двох підприємств А і В на 5 років виділено х ресурсів. Кількість ресурсів у, вкладених у підприємство А , за рік дає дохід р (у) = у2 і зменшується до величини ф (у) = 0,75у . Кількість ресурсів х - у , вкладених у підприємство В , за рік дає дохід q (х - у) = 2 (х - у)2 і зменшується до величини ψ(х - у) = 0,3 (х - у). Треба так розподілити виділені ресурси між підприємствами по роках на період 5 років, щоб повний дохід був максимальним.

Розв'язування. Розіб'ємо період часу 5 років на 5 етапів, причому кожному етапу поставимо у відповідність період в один рік.

Відшукання оптимального розв'язку почнемо з п'ятого етапу. Припустимо, що на початок п'ятого етапу треба розподілити між підприємствами А і В залишок ресурсів х4. Для цього треба визначити оптимальну кількість ресурсів у5 , які треба вкласти в підприємство А , щоб, вклавши х4- у5 ресурсів в підприємство В , одержати максимальний дохід на п'ятому етапі. Цей дохід визначається за формулою:

то для знаходження максимального значення функції ф5 (у5) на проміжку [0, х4 ] досить знайти значення функції ф5 (у5) в точках у5 = 0 і у5 = х4, бо ф5 (у5) є параболою вітками вгору і точка, в якій ф5 (у5) = 0 , є точкою мінімуму функції. Оскільки

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

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

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

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

Звідси випливає, що максимальний дохід на третьому етапі досягається у випадку, коли на початку третього етапу всі ресурси, що залишилися після другого етапу, вкласти в розвиток підприємства А .

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

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

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

Це означає, якщо на першому етапі всі ресурси вкласти в розвиток підприємства А , то на цьому етапі матимемо максимальний дохід.

Таким чином, ми знайшли на кожному етапі умовно оптимальні рішення. Процес оптимального розподілу ресурсів, який принесе максимальний дохід від вкладених ресурсів за п'ять років є таким: на протязі перших трьох років ресурси треба вкладати в розвиток тільки підприємства А , а на протязі двох останніх - тільки в розвиток підприємства В .

Якщо для розвитку підприємств А і В на 5 років виділено х ресурсів, то оптимальний розподіл цих ресурсів по роках виглядає так:

Таблиця 8.1. Оптимальний розподіл ресурсів по роках

При такому розподілі ресурсів за п'ять років буде одержаний максимальний дохід, який становитиме 2, 27х2 одиниць.

Приклад 8.2. Для збільшення обсягу випуску продукції, що виготовляється трьома підприємствами, виділено капіталовкладень в обсязі 700 тис. грошових одиниць. Використання і -м підприємством хj тис. грошових одиниць із вказаної суми забезпечує приріст продукції на величину fі (хj). Скласти оптимальний план розподілу капіталовкладень між підприємствами, який забезпечує максимальне збільшення випуску продукції, якщо величини хj і fі (хj) задані таблицею 8.2.

Розв'язування. Процес розв'язування цієї задачі розіб'ємо на три кроки. На першому кроці визначимо максимальний приріст випуску продукції при розподілі хj = 100j, j = 0,1,...7, грошових одиниць для першого підприємства. На другому кроці визначимо максимальний mприріст випуску продукції при розподілі хj = 100}, j = 0,1,... 7, грошових одиниць для першого і другого підприємства. І, нарешті, на третьому кроці визначимо максимальний приріст випуску продукції при розподілі 700 грошових одиниць між трьома підприємствами.

Таблиця 8.2. Залежність приросту продукції від капіталовкладення

Позначимо Fі (х), і = 1,2,3, - приріст випуску продукції при розподілі

х грошових одиниць серед перших і підприємств; Fi*(х), і = 1,2,3, - максимальний приріст випуску продукції при розподілі х грошових одиниць серед перших і підприємств. На першому кроці

Таблиця 8.3. Приріст випуску продукції

Таблиця 8.4. Дані обчислення приросту F3 (700)

Із табл.8.4 бачимо, що F3* (700) = 270.

Оптимальний план розподілу капіталовкладень між трьома підприємствами визначається наступним чином. Оскільки F3* (700) = 270 і досягається для k = 6, то третьому підприємству треба виділити 600 тис. грошових одиниць. Далі треба розподілити 100 тис. грошових одиниць між першими двома підприємствами. Із табл. 1 при хj = 100 маємо F2* (100) = 50 і досягається для k = 1. Це означає, що для другого підприємства треба виділити 100 тис. грошових одиниць, а першому підприємству не попаде нічого.

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