Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Задачі динамічного програмування.

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

Назва:
Задачі динамічного програмування.
Тип:
Реферат
Мова:
Українська
Розмiр:
6,52 KB
Завантажень:
428
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4 
Реферат на тему:
Задачі динамічного програмування.


План.
1. Загальна характеристика задач динамічного програмування.
2. Геометрична та економічна сутність.
3. Деякі основні типи задач та моделі динамічного програмування (ДП).
4. Принципи оптимальності Белламана.
5. Література


Загальна характеристика задач динамічного програмування.
В розглянутих вище задачах лінійного та нелінійного програмування ми знаходили їх розвязок ніби в один етап чи в один крок. Такі задачі отримали назву одноетапних чи однокрокових.
На відміну від цих задач задачі ДП є багатоетапними чи багатокроковими. Іншими словами, знаходження розвязку конкретних задач методами ДП включають декілька етапів чи кроків, на кожному з яких визначається розвязок деякої окремої задачі, обумовленою початковою. Тому термін “динамічне програмування” не стільки визначає собою тип задач, скільки характеризує методи знаходження розвязку окремих класів задач математичного програмування, які можуть відноситися до задач як лінійного, так і нелінійного програмування. Не дивлячись на це, доцільно дати загальну постановку задачі ДП і визначити єдиний підхід до її розвязку.
Припустимо, що дана фізична система S знаходиться в деякому початковому стані S0 S0 та є направляючою. Таким чином, завдяки здійсненню деякого управління U вказана система переходить з початкового стану S0 в кінцевий стан Sкін SR. При цьому якість кожного з реалізуючих управлінь U характеризується відповідним значенням функції W(U). Задача полягає в тому, щоб з більшості можливих управлінь U знайти таке U* , при якому функція W(U) приймає екстремальне значення W(U*). Сформульована задача і є загальною задачею ДП.
Дамо геометричну інтерпретацію цієї задачі. Припустимо, що стан системи характеризується деякою точкою S на площині x1Ox2 (мал.1) і ця точка завдяки здійснюваному управлінню її рухом переміщується удовж лінії, яка зображена на мал.1, з області можливих початкових станів S0 в область допустимих кінцевих станів SR . Кожному управлінню U рухом точки, а саме кожній траєкторії руху точки, поставимо у відповідність значення деякої функції W(U) (наприклад, довжину відстані, пройденої точкою під впливом даного управління). Тоді задача полягає в тому, щоб з усіх допустимих траекторій руху точки S знайти таку, яка виходить в результаті реалізації управління U*, що забезпечує екстремальне значення функції W(U*). До означення такої “траекторії” зводиться і задача ДП у випадку, коли допустимі стани системи S визначаються точками n-вимірного простору.
мал.1
Економічну інтерпретацію загальної задачі ДП розглянемо на конкретних прикладах.
У розпорядження міністерства, у підпорядкуванні якого знаходиться k підприємств, виділено кошти в розмірі К тис. грн. для використання їх на розвиток підприємств протягом m років. Ці кошти на початку кожного господарського року, тобто в моменти t1, t2, …, tm , розприділяються між підприємствами. Одночасно з цим між підприємствами розподіляється отриманий ними за минулий рік прибуток. Таким чином, на початок кожного і-го року періоду, який нас цікавить j-те підприємство отримує в своє розпорядження хi( j ) тис.грн. Задача полягає у визначенні таких значень xi( j ) , тобто в знаходженні таких розподілів виділених коштів між підприємствами і прибутку що ними отримується, при яких за m років забезпечується отримання максимального прибутку всіма підприємствами.
Сформулювати поставлену задачу в термінах загальної задачі ДП.
Розвязок. Припускаючи, що j-му підприємству на і-ий рік виділяється xi(j) тис. грн., будемо розглядати даний розподіл коштів як реалізацію деякого управління ui . Таким чином, управління ui полягає в тому, що на і-му кроці першому підприємству виділяється xi(1) тис. грн., другому - xi(2) тощо. Сукупність чисел xi(1), xi(2), …, xi(k) визначає всю сукупність управлінь u1, u2, …, um на m кроках розподілу коштів як m точок в k-вимірному просторі.
В якості критерію оцінки якості обраного розподілу коштів, тобто реалізуючих управлінь, взятий сумарний прибуток за m років, який залежить від всієї сукупності управлінь:
W= W (u1, u2, …, um).

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок