Свої здібності людина може дізнатися, тільки спробувавши докласти їх. (Сенека)
Принцип оптимальності Беллмана дозволяє вирішувати або осмислити багато цікаві завдання, що виникають в реальному житті, наприклад, задачу про раціональної експлуатації генеруючого підприємства (ТЕЦ, ГЕС), вибору економічного складу агрегатів і ін.
При експлуатації гідростанцій і теплових станцій виникає необхідність періодичної зупинки агрегатів при зниженні навантаження і включення агрегатів, що знаходяться в резерві, коли навантаження збільшується. Включення в роботу певних агрегатів впливає на величину і розміщення резервів системи, на режим електричної мережі, на перетоки по міжсистемних ліній електропередачі, на витрату палива і тд.
Якщо на станціях є n агрегатів і кожен з них може бути або включений, або вимкнений, то все безліч всіх варіантів для роботи з будь-потужністю складе 2 певною мірою n.
Навіть для n = 50 число варіантів стає дуже великим!
У загальному вигляді такі завдання є нелінійними, цілочисельними, багатоекстремального, на склад агрегатів впливає режим електричних мереж, який слід оцінювати і прогнозувати статистичними методами. Для вирішення таких завдань звичайний математичний апарат не підходить.
В окремому випадку методи динамічного програмування дозволяють вирішувати подібні завдання при числі агрегатів близько 20-30.
Наведемо приклади завдань, в яких принцип динамічного програмування ефективно працює і дозволяє знайти оптимальне рішення.
Завдання про графік експлуатації електростанція. Станція має L агрегатів, відома продуктивність одного агрегату і ціна одиниці виробленої електроенергії.
Заданий графік оплаченої електроенергії, надлишково вироблена електроенергія не оплачується.
Відомі витрати на підтримку в робочому агрегатів, витрати на консервацію і витрати на пуск. Потрібно визначити оптимальний режим експлуатації.
Цікаві завдання про розподіл інвестицій і ресурсів.
Задача про розподіл інвестицій: є кілька підприємств, між якими потрібно розподілити цю суму інвестицій. Відома ефективність вкладення цієї суми коштів в кожне підприємство.
Задача про розподіл ресурсу: є N підприємств, кожне з яких приносить дохід, який залежить від частки виділеного ресурсу. Потрібно найкращим способом розподілити між ними обмежений ресурс a на частки x 1. xN (x 1 ≥ 0. xN ≥ 0, x 1 +. + XN ≤ a).
Завдання про найкращу завантаженні транспорту: транспорт, має вантажопідйомність a. завантажується вантажами N типів. Кожен тип вантажу має вартість yi і вага zi.
Потрібно знайти оптимальний варіант завантаження, при якому вартість взятих на борт предметів максимальна.
Завдання про заміну автомобіля: автотранспортне підприємство планує придбати автомобіль і експлуатувати його протягом N років.
Можна або купити новий автомобіль віку x 0 = 0 років і вартості p. або був в експлуатації віку x 0> 0 років за вартістю, яка залежить від часу експлуатації.
Показники експлуатації автомобіля включають: f (t) - вартість вироблених за рік виробів на обладнанні віку t років; r (t) - витрати на експлуатацію протягом року автомобіля віку t.
В процесі експлуатації автомобіль можна продавати по ліквідної вартості і купити новий. В кінці терміну експлуатації автомобіль також продається по ліквідної вартості. Визначити оптимальний вік автомобіля при покупці і оптимальний графік його заміни.
Всі ці та багато інших завдань можуть бути вирішені за допомогою принципу оптимальності Беллмана.
Наведемо формально принцип Беллмана і пояснимо його сенс.
Ключовим є поняття керованого об'єкта, до якого застосовується принцип Беллмана.
Нехай є змінюється в часі об'єкт, на який здійснюється зовнішній вплив u (t) або управління. а x (t) - опис цього об'єкта в момент часу t.
Якщо при відомому управлінні до моменту t1. знаючи опис x (t) в момент часу t. можна однозначно визначити його значення x (t) для будь-якого t> t1. то такий опис називають повним.
Повний опис називають станом. безліч можливих станів - простором станів.
Сам об'єкт, що допускає можливість повного опису, називають динамічною системою.
Будемо розглядати тільки дискретні моменти часу і в ці моменти управляти системою.
Кожному переходу зі стану xk в наступний стан ставиться у відповідність функція витрат, що залежить від стану xk. моменту часу і застосовуваного управління.
Потрібно знайти таке початковий стан і такий допустимий набір управлінь, що переводить систему в одне з кінцевих станів, щоб загальні витрати, які є адитивною функцією витрат на окремих кроках, були мінімальні.
Отже, на кожному кроці ми вносимо плату за межі встановленого управління, далі плата, внесена на кожному кроці, підсумовується і підводиться підсумок.
Ми бажаємо таким чином управляти об'єктом, щоб загальна сума витрат була мінімальною.
Це і є загальна постановка задачі динамічного програмування або керування динамічною системою.
Іншими словами, нам потрібна програма дій на кожному кроці, що дозволяє мінімізувати витрати.
Загальний принцип формулюється так: незалежно від того, яким чином керований процес на етапі k потрапив в стан xk. далі треба застосовувати управління, оптимальне для цього стану в завершальному (N - k) -шаговом процесі з урахуванням оптимального продовження.
Це одна з можливих формулювань принципу Беллмана в формі достатньої умови.
Нехай Yk - безліч станів, з яких (при використанні допустимих управлінь) можна рівно за k кроків потрапити в одне з станів фінального безлічі X N.
Можна вважати, що Y 0 = X N.
Візьмемо довільне xN -k ∈Yk і позначимо через Sk (xN -k) функцію, яка описує залежність оптимальних витрат від стану xN -k за k останніх кроків, які переводять систему з xN -k в X N.
Такі функції називають функціями Беллмана.
Оскільки для станів xN -1 з безлічі Y 1 перехід в XN відбувається за один крок, то функція оптимальних витрат S 1 (xN -1) може бути записана наступним чином:
Друге обмеження необхідно для того, щоб гарантувати досягнення заданого фінального безлічі X N.
Значення uN. при якому досягається мінімум в цьому співвідношенні, позначимо через u * N (xN-1).
Нескладно зрозуміти (зробіть це!), Що функція оптимальних витрат Sk +1 (xN -k -1) кожної наступної задачі рекуррентно виражається через попередню Sk (xN -k)
u * N -k (xN -k - 1) - управління, при якому досягається мінімум витрат в (2).
Вираз u * k (xk-1) - визначає для кожного моменту часу оптимальні правила управління у вигляді функцій від поточного стану динамічного процесу, ставлять закон оптимального управління в формі оптимального регулятора за станом.
Оптимальне початковий стан x * 0 можна отримати з вирішення наступного завдання:
Систему (1) - (3) називаютрекуррентнимі рівняннями Беллмана.
Значення оптимального управління в явному вигляді можна послідовно визначити наступним чином:
Стартуємо з початкового стану x0.