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%

задача

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

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

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

Задачі, які

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

екстремумів

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

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

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

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

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

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

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

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

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

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