Застосування методу динамічного програмування до детермінованих задач

Тема: Застосування методу динамічного програмування до детермінованих задач. 

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

Теоретичні відомості

    Моделі  динамічного програмування

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

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

    Позначимо множину можливих управлінь через U. Тоді задача полягає в тому, щоб із множини можливих управлінь U знайти таке управління U^*, яке дасть змогу перевести систему S із початкового стану в кінцевий таким чином, щоб критерій W(U) досягнув оптимального значення W^*(U). Стан економічної системи S можна описати числовими параметрами, як правило техніко-економічними та іншими показниками, які у методах динамічного програмування отримали термін “координати системи”. Тоді, перехід системи S із одного стану S₁ в інший S₂ можна виразити деякою траєкторією точки S. Управління U означає вибір певної траєкторії переміщення S, тобто визначення закону руху S. Сукупність станів, у які може переходити система , називають областю можливих станів. Суть задачі динамічного програмування зводиться до того, щоб з області можливих станів системи вибрати таку, на якій критерій W приймає оптимальне значення.

    Динамічне програмування являє собою поетапне планування багатокрокового процесу. Починають планувати із останнього k-го кроку і поступово переходять до (k-1)-го, (k-2)-го і т.д., поки не прийдуть до початкового стану системи S₀. Для того, щоб спланувати k-ий крок, необхідно знати стан системи на (k-1)-му кроці. Якщо цей стан не відомий, то роблять різні припущення про можливий стан системи на цьому кроці. Позначимо стани системи на цьому кроці як точки S_k-1,1, S_k-1,2, …, S_k-1,r. На останньому кроці знайдемо для кожного з них оптимальне управління . При цьому критерій має відповідати оптимальному з множини . Таким чином k-ий крок спланований. На (k-1)-му кроці потрібно знати стани системи на (k-2)-му кроці і т.д., поки не прийдемо у початковий стан системи. Для цього стану вибираємо оптимальні управління таким чином, щоб досягнути оптимальної суми критеріїв W^* на двох попередніх кроках . Якщо тепер взяти остаточне значення критерію оптимальності на нульовому кроці, то цей критерій повинен мати властивість адитивності, тобто , де – кількість кроків процесу.

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

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

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

    Розглянемо  одну із типових задач – задачу розподілу ресурсів.

    Вісім умовних одиниць певного ресурсу (наприклад, мільйонів гривень) можуть бути інвестовані (вкладені) у розвиток трьох підприємств (k = 1,2 3). Позначимо через g_k(x), k = 1,2,3 прибуток в тих же умовних одиницях, що отримується від k-го підприємства, якщо в його розвиток інвестовано x одиниць ресурсу. Величини прибутків g_k(x), k = 1,2,3 для різних можливих значень x наведені в таблиці 1. Зауважимо, що ця ж таблиця містить інші дані, зміст яких пояснюється далі.

    Таблиця 1

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

    Нехай x_k, k=1,2,3 – об’єм інвестицій у k-е підприємство. Тоді формальна постановка задачі така: шукається вектор x=(x₁,x₂,x₃):

    Оскільки  цільова функція є адитивною, застосуємо метод динамічного програмування  до розв’язання цієї задачі. Отже, розглядаємо  трьохетапний процес планування, кожен з 3-х етапів якого є виділення ресурсу відповідному підприємству. Зауважимо, що оптимальний розв’язок задачі не залежить від того, в якому порядку перенумеровані підприємства. Розглядаємо останній (3-й) етап планування і нехай на перших двох етапах не використана жодна одиниця ресурсу, тобто до третього етапу ми прийшли, маючи 8 одиниць ресурсу. Тоді для отримання максимального прибутку потрібно всі 8 одиниць інвестувати в розвиток третього підприємства, тому що g₃(x) – зростаюча функція (див. табл. 1). При цьому максимальний прибуток від інвестування f₃(8)=g₃(8)=53 одиниць і для цього потрібно вкласти в розвиток третього підприємства d₃(8)=8 одиниць ресурсу. Для розв’язання задачі методом динамічного програмування потрібні також значення f₃(x), d₃(x) при x=0,1,2,…7. Вони знаходяться аналогічно і наведені в табл.2. Отже, ми зробили всі можливі припущення відносно закінчення передостаннього (2-го) етапу планування і отримали відповідні умовні оптимальні рішення для 3-го кроку.

    Таблиця 2

    Нехай тепер 8 одиниць ресурсу розподіляються між другим та третім підприємствами і z – об’єм інвестування в друге підприємство. Використовуючи значення f₃(x) з таблиці 2, легко підраховуємо:

    тобто за цих умов у розвиток другого  підприємства потрібно вкласти d₂(8)=5 одиниць ресурсу. Аналогічно знаходяться f₂(x) та d₂(x) при x=0,1,2,…,7 (табл.3). Отже, ми отримали умовні величини прибутків для 2-го та 3-го етапів (f₂(x)) та умовний оптимальний об’єм інвестування в друге підприємство (d₂(x)) за умови різних закінчень 1-го етапу. 

    Таблиця 3

    Розгляд першого етапу планування еквівалентний  розв’язанню вихідної задачі. Нехай з 8 одиниць ресурсу z одиниць інвестується у перше підприємство, (8-z) – у друге та третє. Використовуючи значення f₂(x) з таблиці 3, знаходимо

    Тобто d₁(8)=4. Отже, максимальний прибуток в 140 одиниць отримується при такому розподілі інвестицій: d₁(8)=4 одиниці в перше підприємство, d₂(4)=4 в друге та d₃(0)=0 одиниць в третє.

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

    де  f_i(x) – максимальний прибуток від інвестування x одиниць ресурсу в підприємства i,i+1,…,3, d_i(x) – оптимальне інвестування в i-те підприємство, якщо в підприємства i,i+1,…,3 інвестується x одиниць ресурсу. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Задание: Найти оптимальное распределение средств между 5 предприятиями при условии, что прибыль f(x), полученная от каждого предприятия, является функцией от вложенных в него средств х. Выписать все оптимальные управления.

     Исходные  данные. 

I этап. Условная оптимизация.

1-ый шаг. k = 3.