Науковий керівник Клочко О.В.

Вінницький національний аграрний університет

Белякова О.В.

ДИНАМІЧНЕ ПРОГРАМУВАННЯ

Вступ.  У наш час наука приділяє велику увагу питанням організацій й керування, це приводить до необхідності аналізу складних цілеспрямованих процесів під кутом зору їхньої структури й організації. Потреби практики викликали до життя спеціальні методи, які зручно поєднувати за назвою «дослідження операцій». Під цим терміном розуміється застосування математичних, кількісних методів для обґрунтування рішень у всіх областях цілеспрямованої людської діяльності.  Метою динамічного програмування є визначення найкращого способу дії при рішенні того або іншого завдання. 
Для побудови математичної моделі необхідно мати строге подання про мету функціонування досліджуваної системи й мати інформацію про обмеження, які визначають область припустимих значень. Мета й обмеження повинні бути представлені у вигляді функцій. Практично всі методи динамічного програмування породжують алгоритми, які є ітераційними по своїй природі. Це має на увазі, що завдання вирішується послідовно (ітераціонно), коли на кожному кроці (ітерації) одержуємо рішення, що поступово сходяться до оптимального рішення. Ітераційна природа алгоритмів звичайно приводить до об'ємних однотипних обчислень. У цьому й полягає причина того, що ці алгоритми розробляються, в основному, для реалізації за допомогою обчислювальної техніки.[1,с.35].
 Результати.  Більшість методів дослідження операцій зв'язано в першу чергу із завданнями цілком певного змісту. Класичний апарат математики виявився малопридатним для рішення багатьох завдань оптимізації, що включають велике число змінних й/або обмежень у вигляді нерівностей. Безсумнівна привабливість ідеї розбивки завдання великої розмірності на підзадачі меншої розмірності, що включають усього по декількох змінних, і наступного рішення загального завдання вроздріб. Саме на цій ідеї заснований метод динамічного програмування. 
 Динамічне програмування (ДП)- являє собою математичний метод, заслуга створення й розвитку якого належить насамперед Беллману. Метод можна використати для рішення досить широкого кола завдань, включаючи завдання розподілу ресурсів, заміни й керування запасами, завдання про завантаження. Характерним для динамічного програмування є підхід до рішення завдання по етапах, з кожним з яких асоційована одна керована змінна. Набір рекурентних обчислювальних процедур, що зв'язують різні етапи, забезпечує одержання припустимого оптимального рішення завдання в цілому при досягненні останнього етапу. Походження назви динамічне програмування, імовірно, пов'язане з використанням методів ДП у завданнях прийняття рішень через фіксовані проміжки часу (наприклад, у завданнях керування запасами). Однак методи ДП успішно застосовуються також для рішення завдань, у яких фактор часу не враховується. Із цієї причини більше вдалим представляється термін багатоетапне програмування, що відбиває покроковий характер процесу рішення завдання. Фундаментальним принципом, покладеним в основу теорії ДП, є принцип оптимальності. Власне кажучи, він визначає порядок поетапного рішення завдання, що допускає декомпозицію, (це більше прийнятний шлях, чим безпосереднє рішення завдання у вихідній постановці) за допомогою рекурентних обчислювальних процедур. [2,c.75].
Динамічне програмування дозволяє здійснювати оптимальне планування керованих процесів. Під «керованими» розуміються процеси, на хід яких ми можемо в тім або іншому ступені впливати. Нехай передбачається до здійснення деякий захід або серія заходів («операція»), що переслідує певну мету. Запитується: як потрібно організувати (спланувати) операцію для того, щоб вона була найбільш ефективною? Для того, щоб поставлене завдання придбало кількісний, математичний характер, необхідно ввести в розгляд деякий чисельний критерій W, яким ми будемо характеризувати якість, успішність, ефективність операції. Критерій ефективності в кожному конкретному випадки вибирається виходячи із цільової спрямованості операції й завдання дослідження (який елемент керування оптимізується й для чого).
 Сформулюємо загальний принцип, що лежить в основі рішення всіх завдань динамічного програмування («принцип оптимальності»): «Який би не був стан системи S перед черговим кроком, треба вибрати керування на цьому кроці так, щоб виграш на даному кроці плюс оптимальний виграш на всіх наступних кроках був максимальним». Динамічне програмування – це поетапне планування багатокрокового процесу, при якому на кожному етапі оптимізується тільки один крок. Керування на кожному кроці повинне вибиратися з обліком всіх його наслідків у майбутньому. При постановці завдань динамічного програмування варто керуватися наступними засадами: – вибрати параметри (фазові координати), що характеризують стан S керованої системи перед кожним кроком; – розчленувати операцію на етапи (кроки); – з'ясувати набір крокових керувань xі для кожного кроку й обмеження, що накладають на них; – визначити який виграш приносить на і-ом кроці керування xі, якщо перед цим система могла S, тобто записати «функцію виграшу»; – визначити, як змінюється стан S системи S під впливом керування xі на і-ом кроці: воно переходить у новий стан; – записати основне рекурентне рівняння динамічного програмування, що виражає умовний оптимальний виграш Wі(S) (починаючи з і-го кроку й до кінця) через уже відому функцію Wі+1 (S). [3.c.102].
Висновок. Отже, динамічне програмування, використовуючи поетапне планування, дозволяє не тільки спростити рішення завдання, але й вирішити ті з них, до яких не можна застосувати методи математичного аналізу. Спрощення рішення досягається за рахунок значного зменшення кількості досліджуваних варіантів, тому що замість того, щоб один раз вирішувати складне різноманітне завдання, метод поетапного планування припускає багаторазове рішення щодо простих завдань. Плануючи поетапний процес, виходять із інтересів усього процесу в цілому, тобто при ухваленні рішення на окремому етапі завжди необхідно мати у виді кінцеву мету. Однак динамічне програмування має й свої недоліки. На відміну від лінійного програмування, у якому симплексний метод є універсальним, у динамічному програмуванні такого методу не існує.
 

Література:

1, Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:КНЕУ, 2010.- 35 с.

2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник А.Ф. Барвінський, І.Я ”, 20011. – 75 с.

3. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: „Рута”, 2008.-102 с.