UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЗадачі динамічного програмування (реферат)
АвторPetya
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось5185
Скачало662
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

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

 

План.

 

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 , розприділяються між

підприємствами. Одночасно з цим між підприємствами розподіляється

отриманий ними за минулий рік прибуток. Таким чином, на початок кожного

-----> Page:

0 [1] [2] [3] [4]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ