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

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

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

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

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

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

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

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

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

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

    

, (2.2.1)

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

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

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

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

    Таблиця 1

x 0 1 2 3 4 5 6 7 8
g1(x) 0 5 15 40 80 90 95 98 100
g2(x) 0 5 15 40 60 70 73 74 75
g3(x) 0 4 26 40 45 50 51 52 53

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

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

    

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

    Таблиця 2

x 0 1 2 3 4 5 6 7 8
g1(x) 0 5 15 40 80 90 95 98 100
g2(x) 0 5 15 40 60 70 73 74 75
g3(x) 0 4 26 40 45 50 51 52 53
f3(x) 0 4 26 40 45 50 51 52 53
d3(x) 0 1 2 3 4 5 6 7 8

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

    

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

    Таблиця 3

x 0 1 2 3 4 5 6 7 8
g1(x) 0 5 15 40 80 90 95 98 100
g2(x) 0 5 15 40 60 70 73 74 75
g3(x) 0 4 26 40 45 50 51 52 53
f3(x) 0 4 26 40 45 50 51 52 53
d3(x) 0 1 2 3 4 5 6 7 8
f2(x) 0 5 26 40 60 70 86 100 110
d2(x) 0 1 0 0 4 5 4 4 5

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

    

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

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

    

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

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

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

f1 f2 f3 xi
0 0 0 0
11 8 7 1
26 23 20 2
60 54 53 3
98 91 89 4
 
 
 

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

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

e2 u3 e3 = e2 - u3 f3(u3) F*3(e3) u3(e3)
1 0 1 0      
   1 0 7 7 1
2 0 2 0      
   1 1 7      
   2 0 20 20 2
3 0 3 0      
   1 2 7      
   2 1 20      
   3 0 53 53 3
4 0 4 0      
   1 3 7      
   2 2 20      
   3 1 53      
   4 0 89 89 4
 
 
 

2-ый шаг. k = 2. 

e1 u2 e2 = e1 - u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
1 0 1 0 7 7      
   1 0 8 0 8 8 1
2 0 2 0 20 20      
   1 1 8 7 15      
   2 0 23 0 23 23 2
3 0 3 0 53 53      
   1 2 8 20 28      
   2 1 23 7 30      
   3 0 54 0 54 54 3
4 0 4 0 89 89      
   1 3 8 53 61      
   2 2 23 20 43      
   3 1 54 7 61      
   4 0 91 0 91 91 4
 
 
 
 
 
 
 
 
 

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

e0 u1 e1 = e0 - u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
1 0 1 0 8 8      
   1 0 11 0 11 11 1
2 0 2 0 23 23      
   1 1 11 8 19      
   2 0 26 0 26 26 2
3 0 3 0 54 54      
   1 2 11 23 34      
   2 1 26 8 34      
   3 0 60 0 60 60 3
4 0 4 0 91 91      
   1 3 11 54 65      
   2 2 26 23 49      
   3 1 60 8 68      
   4 0 98 0 98 98 4
 

Ход решения:

Столбцы 1, 2 и 3 для  всех трех таблиц одинаковы, поэтому  их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).

В столбце 7 записывается максимальное значение предыдущего  столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.

Из таблицы 3-го шага имеем F*3(e0 = 4) = 98. То есть максимальный доход всей системы при количестве средств e0 = 4 равен 98

Из этой же таблицы  получаем, что 1-му предприятию следует  выделить u*1(e0 = 4) = 4

При этом остаток средств  составит:

e1 = e0 - u1

e1 = 4 - 4 = 0

Из таблицы 2-го шага имеем F*2(e1 = 0) = 1. То есть максимальный доход всей системы при количестве средств e1 = 0 равен 1

Из этой же таблицы  получаем, что 2-му предприятию следует  выделить u*2(e1 = 0) = 23

При этом остаток средств  составит:

e2 = e1 - u2

e2 = 0 - 23 = -23

Последнему предприятию  достается -23 
 

Ответ: инвестиции в размере 4 необходимо распределить следующим образом:

1-му предприятию  выделить 4

2-му предприятию  выделить 0

3-му предприятию  выделить 0

Что обеспечит максимальный доход, равный 98

Застосування методу динамічного програмування до детермінованих задач 📙 Контрольная → 🆔 32741

Застосування методу динамічного програмування до детермінованих задач 📙 Контрольная → 🆔 32741

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