Главная | Обратная связь | Поможем написать вашу работу!

Рекурентне співвідношення

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

Нехай задана така математична модель задачі:

знайти

при обмеженнях

та умові і цілочисловості змінних.

На кожному кроці оптимізації розглядаються всі допустимі значення поточних ресурсів у діапазоні , а потім у діапазоні – усі допустимі значення змінних із заданим кроком їх зміни (часто – це точність розв’язування за умовами задачі). Якщо є додаткове обмеження на змінні , то діапазон корегується цими доповненнями.

При такому „двоступовому” задані діапазонів на кожному кроці оптимізації знаходяться дві величини від поточного стану : значення та ефективність використання ресурсів .

Кожний процес планування має такий крок розрахунку, на якому загальна мета збігається з метою цього кроку оптимізації. Таким кроком є останній п -й крок. На ньому знаходиться такий розв’язок, який дає загальну ефективність згідно з принципом оптимальності, тобто з умов останнього кроку без подальшого наслідку.

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

де – поточний залишок ресурсів.

Цільова функція для змінних має вигляд

Ця величина залежить від залишків ресурсів , тому можна записати

Тоді загальний вид цільової функції буде такий

, (6.1)

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

Отже, для всіх можливих значень змінної у заданому діапазоні знаходиться оптимум за умовами, що всі значення для залишків ресурсів () відомі. У цьому випадку розв’язування зводиться до пошуку тільки однієї змінної на п -му кроці.

На жаль, на п -му кроці невідома друга складова (6.1). Тому аналогічно розглядається передостанній - й крок, але для залишків ресурсів. Тоді

де змінна задається у діапазоні , а залишки ресурсів для (п -2) кроків дорівнює .

За аналогією, для будь-якого -го кроку цільова функція має вигляд

а для першого кроку

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

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

Із заданим дискретним кроком для усіх значень знаходяться величини першого кроку:

(6.2)

На другому кроці розрахунок ведеться за формулою

де – величина попереднього кроку, яка вже знайдена за (6.2).

За аналогією для будь-якого -го кроку

а на останньому кроці

. (6.3)

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

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

Перевага рекурентного підходу – його пристосування до розрахунків на ЕОМ, тобто процес розв’язування є ітераційним.

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

Така цільова функція має властивість мультиплікативності.

Задачі, які мають таку цільову функцію, можна звести до адитивного виду. Для цього треба взяти логарифм . Але в цьому немає потреби, тому що задачу з мультиплікативною цільовою функцією можна записати таким рекурентним співвідношенням:

При цьому процедура розрахунків і всі положення є такими самими, як і при адитивній цільовій функції.

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

Таблиця оптимальних розв’язків

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

Якщо позначимо через значення змінної -го кроку при стані ресурсів , то таблиця оптимальних розв’язків для всіх допустимих розв’язків задачі має таку структуру для цілочислових значень:

	...	...
...

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

Значення відповідає другому кроку оптимізації , для якого рекурентне співвідношення дорівнює:

у загальному вигляді

для конкретної величини ресурсу

Знайдене значення (максимум чи мінімум) заноситься у таблицю до колонки другого крока та рядка поряд з .

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

де – залишки ресурсів на всіх кроках від першого до -го, а – кількість ресурсів, що розподілені з -го до останнього -го кроку включно.

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

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

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

У загальному вигляді значення змінних відповідно таблиці оптимальних розв’язків такі:

п -й крок: ,