Crowdly

w_i - вага одного предмету вантажу і

Нехай

f_i(x_i)

– максимальний

сумарний прибуток від етапів

i ,

i+1 , …

n при заданому стані,

-го

типу,

r_i - прибуток, який приносить один завантажений предмет вантажу i -го типу,

m_i - невідома кількість предметів вантажу і-го типу, яку потрібно завантажити.

Тоді рекурентне рівняння методу зворотної прогонки визначається так:

$f_i(x_i)={max}\limits_{m_i,x_i}\{w_im_i+f_{i+1}(x_i-r_i m_i)\}$ f_i(x_i)={max}\limits_{m_i,x_i}\{w_im_i+f_{i+1}(x_i-r_i m_i)\} , $i=\overline{1,n}$ i=\overline{1,n}

$f_i(x_i)={min}\limits_{m_i,x_i}\{r_im_i+f_{i+1}(x_i-w_i m_i)\}$ f_i(x_i)={min}\limits_{m_i,x_i}\{r_im_i+f_{i+1}(x_i-w_i m_i)\} , $i=\overline{1,n}$ i=\overline{1,n}

$f_i(x_i)={max}\limits_{m_i,x_i}\{r_im_i+f_{i+1}(x_i-w_i m_i)\}$ f_i(x_i)={max}\limits_{m_i,x_i}\{r_im_i+f_{i+1}(x_i-w_i m_i)\} , $i=\overline{1,n}$ i=\overline{1,n}

$f_i(x_i)={max}\limits_{m_i,x_i}\{r_im_i+f_{i+1}(w_ix_i - m_i)\}$ f_i(x_i)={max}\limits_{m_i,x_i}\{r_im_i+f_{i+1}(w_ix_i - m_i)\} , $i=\overline{1,n}$ i=\overline{1,n}

13%

$f_i(x_i)={max}\limits_{r_i,x_i}\{r_im_i+f_{i+1}(x_i-w_i m_i)\}$ f_i(x_i)={max}\limits_{r_i,x_i}\{r_im_i+f_{i+1}(x_i-w_i m_i)\} , $i=\overline{1,n}$ i=\overline{1,n}

i -го типу, які потрібно завантажити

Визначити елементи моделі задачі про завантаження.

Стан x_i на i -

му етапі виражає сумарну вагу

предметів, рішення про завантаження яких прийнято на етапах

i ,

i+1

…

Альтернативи розв’язку на i

-му

етапі описуються кількістю

предметів

Етап i відповідає предмету n-i -го типу ( $i=\overline{1,n}$ i=\overline{1,n} )

Стан x_i на i -му етапі виражає сумарну вагу предметів, рішення про завантаження яких прийнято на етапах 1 , 2 , … i

Альтернативи розв’язку на i -му етапі описуються кількістю предметів i -го типу, які не потрібно завантажувати

Етап i відповідає предмету i -го типу ( $i=\overline{1,n}$ i=\overline{1,n}

)

Типовими

задачами, що розв’язуються методами динамічного програмування є:

задачі про раціональне завантаження літака, вантажного автомобіля.

задача про призначення.

задача

планування виробництва.

складання календарних планів.

11%

транспортна

задача.

задача вибору оптимального маршруту.

11%

задача

складання раціону.

задача розподілу ресурсів.

задача про заміну обладнання.

Задачі, які

можна розв’язувати методами динамічного програмування повинні мати такі

властивості:

задача не повинна передбачати багатокрокову структуру

функція мети не повинна володіти властивістю адитивності

функція мети повинна володіти властивістю адитивності

подальші пошуки оптимального розв’язку ведуться відносно стану об’єкта,

якого він досяг на кінці даного кроку оптимізації і не залежить від того,

яким чином цей об’єкт потрапив у цей самий стан

задача повинна передбачати багатокрокову структуру

подальші пошуки оптимального розв’язку ведуться відносно стану об’єкта,

якого він досяг на початку даного кроку оптимізації і залежить від того,

яким чином цей об’єкт потрапив у цей самий стан

подальші пошуки оптимального розв’язку ведуться відносно стану об’єкта,

якого він досяг на початку даного кроку оптимізації і не залежить від того,

яким чином цей об’єкт потрапив у цей самий стан

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

обчислювальна процедура методу не дозволяє проводити аналіз знайденого

розв’язку по етапах і тим самим переглядати динаміку поведінки об’єкта

визначення глобального екстремуму не залежить від кількості локальних

екстремумів

використання методу залежить від характеру функції мети

метод не дозволяє вводити до моделі будь-які види обмежень, причому чим меньше їх буде тим скоріше знаходиться оптимальний варіант, якщо існує область

допустимих розв’язків

обчислювальна процедура методу дозволяє проводити аналіз знайденого

розв’язку по етапах, тим самим переглядаючи динаміку поведінки об’єкта

метод дозволяє вводити до моделі будь-які види обмежень, причому чим

більше їх буде тим скоріше знаходиться оптимальний варіант, якщо існує область

допустимих розв’язків

використання методу не залежить від характеру функції мети, вона може

бути недиференційована, таблична, у вигляді графіку чи діаграми

визначення глобального екстремуму залежить від кількості локальних

екстремумів

Недоліки методу динамічного програмування:

метод має універсальний алгоритм

формулювання задачі у термінах динамічного програмування досить простий етап і від того, як вибрані кроки оптимізації не залежить якість

розв’язування задачі

метод немає універсального алгоритму

найбільш простий момент у процесі розв’язування задачі динамічного програмування – складання функціонального рівняння, що передбачає принцип оптимальності

формулювання задачі у термінах динамічного програмування досить

трудомісткий етап і від того, як вибрані кроки оптимізації залежить якість

розв’язування задачі

найбільш складний момент у процесі розв’язування задачі динамічного програмування – складання

функціонального рівняння, що передбачає принцип оптимальності