Загальна математична модель

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

Нехай задана загальна кількість ресурсів , яку треба розподілити між п відтинками часу протягом заданого періоду часу. Міра використання ресурсів кожним -м відтинком часу задана функціями ефективності кожного окремого кроку. Треба знайти варіант розподілу ресурсів протягом заданого періоду часу так, щоб загальна цільова функція використання ресурсів досягла екстремального значення.

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

.

Цільова функція цього процесу складається з мір використання ресурсів на всіх п відтинках часу:

де – функція ефективності використання ресурсів на -му кроці; ця функція може бути будь-якого виду (лінійна, цілочислова, неформалізована тощо), крім того, на різних кроках оптимізації її можна задавати по-різному.

Загальний вид математичної моделі дискретної задачі розподілу ресурсів у термінах динамічного програмування такий:

знайти цільову функцію

при обмеженнях

де всі – дискретні величини або змінюються із заданим кроком.

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

1. Етап умовної оптимізації, на якому знаходяться всі допустимі стани об’єкта на кожному кроці оптимізації; після проходження усіх кроків оптимізації і повного розподілу заданих ресурсів складається таблиця оптимальних розв’язків;

2. Етап безумовної оптимізації, на

якому за таблицею оптимальних

розв’язків знаходяться значення

усіх змінних та цільової функції

оптимального варіанта розв’язку.

Геометричне розв’язування за-

Рис.6.2 дачі методом динамічного програ-

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

Процес розв’язування задачі методом динамічного програмування ілюструє рис. 6.2.