2.3.2. Теоретичні основи методу динамічного програмування


Повернутися на початок книги
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], [3], [19].

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

Задачі, для розв’язування яких можливе застосування методу динамічного програмування, повинні задовольняти такі власти-вості:

•          можливості фактичного або умовного розподілу початкової задачі на окремі підзадачі, кожна з яких містить меншу кількість змінних (навіть до однієї);

•          однотипності підзадач;

•          можливості вимірювання однаковими одиницями ефекту від прийнятого рішення в результаті розв’язування кожної підзадачі;

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

Продемонструємо змістовну та обчислювальну сторони мето.у

якого ресурсу. Це може бути запас сировини, енергетичні ресур-си, фінансові, трудові тощо. Існують альтернативні варіанти ви-користання цього ресурсу.

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

Математична модель задачі. Для побудови математичної мо-делі задачі введемо такі позначення:

п — кількість різних технологічних процесів;

j — номер технологічного процесу, j = 1,п; Xj — кількість ресурсу, яка виділяється у'-му технологічному

процесу j = 1,п;

fj (xj) — прибуток від у'-го технологічного процесу, одержа-ний в результаті використання ресурсу в кількості х. одиниць,

j = 1, п ;

Ь — загальна кількість ресурсу.

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

п

(2.34)

F(x) = ^fj(Xj)

j=1

за обмежень no витратах ресурсу

п

(2.35)

2х/ — ь

та невід’ємності змінних

Xj > 0,     j = 1,п .       (2.36)

Процес розподілу ресурсу між п технологічними процесами можна розбити на п етапів, на кожному з яких будуть прийматись рішення по окремому технологічному процесу в залежності від стану запасу ресурсу. Постановка задачі дає можливість оцінити загальний прибуток як суму прибутків від кожного технологічно-го процесу. Врахування цих особливостей дає можливість вико-ристання методу динамічного програмування для розв’язування задачі (2.34)—(2.36).

Зрозуміло, що оптимальне значення загального прибутку за-лежить від кількості ресурсу Ь, а також від кількості різних тех-

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

п

gn (b) = max ^ /. (х.)

7=1

на множині, яка описується умовами (2.34), (2.35).

Функція gn (b) виражає максимальний прибуток, одержаний від розподілу Ь одиниць ресурсу між п технологічними процесами.

Побудуємо рекурентні співвідношення між величинами при-бутку від п технологічних процесів gn та від (п -1) -го технологі-чного процесу -g„_i . Для цього виберемо значення змінної хп, 0 < хп < b. Ресурси, які залишилися (Ь - хп), повинні бути викори-стані оптимальним чином, тобто необхідно знайти

я-1 g„-i Ф — хп) = max ^ f. (Xj),

7=1

за умов

п-\

~YJX, <b-xn,

j=\

х- > 0,   j = 1, n -1.

Ефективність цих двох кроків визначається сумою прибутків від и-го технологічного процесу та всіх інших:

fn (Хп ) + Sn-1 Ф ~ Хп) ■

Вимога максимальної ефективності від реалізації цих кроків еквівалентна запису:

gn (Ь) = max (fn (xn) + gn_l (b — xn)),

причому п-му технологічному процесу може бути виділена будь-яка кількість ресурсів у межах величини Ь.

3 аналогічних міркувань максимальний прибуток від розподі-лу залишку ресурсу (Ь-хп) визначається формулою:

Sn-l (У) =    ШаХ   (fn-1 (Хя-1 ) + Sn-2 (У ~ Хп-\ )) ■> 0<хп_\<у

ДЄ

У = Ь — хп.

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

Sk (У) = тах С/і (хк)+ St-i ІУ ~ хк))'   к = 2,п ,        (2.37)

0<х^ <у

де

п

у = b— £ х,.

j=k+l

Враховуючи, що на останньому кроці

у — Xj = 0 ,

природно вважати g0 (0) = 0 .

Таким чином, максимальний прибуток від розподілу ресурсу на п-му кроці дорівнює

gAy) = max /ЛхЛ,       (2.38)

0<у<Ь.

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

Алгоритм застосування методу розглянуто в темі 3 при розв'язуванні задачі розподілу інвестицій.

Запитання для самоперевірки знань

1.         Чи правильне твердження: «допустимим базисним розв 'язком є точка, вякгй цгльова функцгя приймає екстремальне значення?»

2.         Чи гснує ознака необмеженості цгльовог функцгг задачг лгнгйного програмування ?

3.         Чи завжди можна застосувати метод динамгчного програму-вання?

4.         Сформулюйте прищип оптимальностг Беллмана.

5.         Чи можливорозв 'язати транспортну задачу симплекс-методом?

ЖьиаЗ