Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

Завдання динамічного програмування

Реферат: Завдання динамічного програмування

I.Основные поняття і позначення.

Динамічний програмування – це математичний метод пошуку оптимального управління, спеціально пристосований до многошаговым процесам. Розглянемо приклад такої процесу.

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

Ставиться питання : як на початку кожного року розподіляти наявні кошти між підприємствами, щоб сумарний прибуток від всіх підприємств за N років було максимальним?

Перед нами типова завдання динамічного програмування, у якій розглядається керований процес – функціонування групи підприємств. Управління процесом полягає у розподілі (і перерозподілі) коштів. Керуючим впливом (УВ) є выделене якихось коштів кожному з підприємств у новому році.

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

Справді, припустимо, що у розглянутим групі підприємств одні зайняті випуском предметів споживання, інші виробляють при цьому машини. Причому метою є одержання N років максимального обсягу випуску предметів споживання. Нехай плануються капіталовкладення перший рік. Виходячи із вузьких інтересів даного кроку (року), ми мала б усі засоби вкласти у виробництво предметів споживання, пустити наявні машини на повну міць і домогтися під кінець року максимального обсягу продукції. Але правильним буде таке рішення, у цілому? Вочевидь ні. З огляду на майбутнє, необхідно виділити якусь крихту засобів і виробництва машин. У цьому обсяг продукції протягом першого року, природно, знизиться, зате буде створено умови, дозволяють збільшувати його виробництво наступні роки.

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

N – число кроків.

– вектор,описывающий стан системи на k-м кроці.

– початкова стан, т. е. cостояние на 1-му кроці.

– кінцеве стан, т. е. cостояние на останньому кроці.

Xk – область допустимих станів на k-ом кроці.

– вектор УВ на k-ом кроці, який би перехід системи зі стану xk-1 до стану xk.

Uk – область допустимих УВ на k-ом кроці.

Wk – величина виграшу, отриманого у результаті k-го кроку.

P.S – загальний виграш за N кроків.

– вектор оптимальної стратегії управління чи ОУВ за N кроків.

Sk+1() – максимальний виграш, отримуваний під час переходу із будь-якої стану в кінцеве стан при оптимальної стратегії управління, починаючи з (k+1)-го кроку.

S1() – максимальний виграш, отримуваний за N кроків під час переходу системи з початкового стану в кінцеве при реалізації оптимальної стратегії управління . Вочевидь, що P.S = S1(), якщо –фіксоване.

Метод динамічного програмування спирається на умова відсутності післядії і умова аддитивности цільової функції.

Умова відсутності післядії. Стан , у якому перейшла система за k-й крок, залежить стану і обраного УВ та залежною від цього, як система прийшла б у стан , тобто

Аналогічно, величина виграшу Wk залежить стану і обраного УВ , тобто

Умова аддитивности цільової функції. Загальний виграш за N кроків обчислюється за такою формулою

Визначення. Оптимальною стратегією управління називається сукупність УВ , тобто , у результаті яких система за N кроків переходить з початкового стану в кінцеве і навіть загальний виграш P.S приймає найбільше значення.

Умова відсутності післядії дозволяє сформулювати принцип оптимальності Белмана.

Принцип оптимальності. Яке було дозволене стан системи перед черговим i-м кроком, треба вибрати дозволене УВ у цьому кроці те щоб виграш Wi на i-м кроці плюс оптимальний виграш усім наступні кроки був максимальним.

Як приклад постановки завдання оптимального управління продовжимо розгляд завдання управління фінансуванням групи підприємств. нехай у початку i-го року групі підприємств виділяються відповідно кошти: сукупність цих значень вважатимуться управлінням на i-м кроці, тобто . Управління процесом загалом є сукупність всіх шаговых управлінь, тобто .

Управління може слугувати гарним чи поганим, ефективним чи неефективним. Ефективність управління оцінюється показником P.S. Постає питання: як вибрати відчутні управління , щоб величина P.S звернулася до максимум ?

Завдання, поставлене є саме оптимального управління, а управління, у якому показник P.S сягає максимуму, називається оптимальним. Оптимальний управління многошаговым процесом складається з сукупності оптимальних шаговых управлінь:


Схожі реферати

Статистика

[1] 2 3 4 5 6