РЕФЕРАТ
Динамічне програмування
Введення
Динамічне програмування - метод оптимізації, пристосований до операцій, в яких процес прийняття рішення може бути розбитий на етапи (кроки). Такі операції називаються багатокроковими.
Початок розвитку динамічного програмування відноситься до 50-м рокам ХХ в. і пов'язане з ім'ям Річарда Ернеста Беллмана.
Якщо моделі лінійного програмування можна використовувати в економіці для прийняття великомасштабних планових рішень у складних ситуаціях, то моделі динамічного програмування застосовуються при вирішенні завдань значно меншого масштабу:
? при розробці правил управління запасами;
? при розподілі інвестиційних ресурсів між альтернативними проектами;
? при складанні календарних планів поточного та капітального ремонту складного обладнання і його заміни і т.п.
1. Загальна постановка задачі динамічного програмування
динамічний Беллман рівняння програмування
Розглядається керований процес, наприклад, процес розподілу коштів між підприємствами, використання ресурсів протягом ряду років, заміни обладнання і т.п. У результаті управління система (об'єкт управління) S перекладається з початкового стану s 0 в стан sn. Нехай, управління можна розбити на n кроків, тобто рішення приймається послідовно на кожному кроці, а управління, що переводить систему S з початкового стану в кінцеве, являє собою сукупність n покрокових управлінських рішень.
Позначимо через X k управлінське рішення на k-му кроці (k=1, 2, ..., n). Змінні X k задовольняють деяким обмеженням і в цьому сенсі називаються допустимими (X k може бути числом, точкою в n-вимірному просторі або якісною ознакою).
Нехай X=(X 1, X 2, ..., X n) - управління, що переводить систему S зі стану s 0 в стан sn. Позначимо через sk стан системи (що характеризується певним набором параметрів і конкретних їх значень) після k-го кроку управління. Причому стан системи sk наприкінці k-го кроку залежить тільки від попереднього стану sk - 1 і управлінського рішення на k-му кроці X k (тобто не залежить безпосередньо від попередніх станів і управлінських рішень). Дана вимога називається «відсутністю наслідки» і може бути висловлене такими рівняннями станів:
. (1)
Таким чином, отримуємо послідовність станів s0, s1, ..., sk - 1, sk, ..., sn - 1, sn. Тоді n-кроковий управлінський процес схематично можна зобразити таким чином:
Нехай показник ефективності k-го кроку виражається деякою функцією:
, (2)
а ефективність усього розглянутого багатокрокового процесу наступної адитивної функцією:
, (3)
або
. (4)
Тоді завдання покрокової оптимізації (задача динамічного програмування) формулюється так: визначити таке допустиме управління Х, що переводить систему S зі стану s0 в стан sn, при якому цільова функція Z приймає найбільше (найменше) значення.
Завдання динамічного програмування володіє наступн...
