Розділ «8. Прийняття рішень у системах управління. Динамічне програмування»

де С виражає сумарні витрати на будівництво та експлуатацію підприємств.

Покажемо, як, використовуючи метод динамічного програмування, можна розв'язати сформульовану задачу. Нехай:

Процес розв'язування задачі розіб'ємо на т кроків. На першому кроці визначаємо мінімальні витрати при розміщенні в першому регіоні

Оптимальний план розміщення и підприємств серед m регіонів визначається так. Нехай

Приклад 8.3. Припустимо, що фірма планує будівництво п'яти промислових підприємств однакової потужності в трьох регіонах.

Нехай gi (xj) (i = 1,2,3)- витрати на будівництво та експлуатацію xj = j (j = 0,1,…,5) підприємств, розміщених в i -му регіоні. Треба так розподілити будівництво підприємств між трьома регіонами, щоб забезпечити мінімум витрат на їх будівництво та експлуатацію. Задачу розв'язати на основі даних таблиці 8.5.

Таблиця 8.5. Витрати на будівництво та експлуатацію підприємств

Процес розв'язання даної задачі розіб'ємо на три кроки. На першому кроці визначимо мінімальні витрати при розміщенні в першому регіоні

регіонах. І, нарешті, на третьому кроці визначимо мінімальні витрати при розміщенні п'ятьох підприємств в трьох регіонах. На першому кроці

Таблиця 8.6. Витрати на будівництво та експлуатацію підприємств

Із табл.8.6. бачимо, що F2* (0) = 0, F2* (1) = 15, F2* (2) = 20 , F2* (3) = 25, F2* (4) = 40 , F2* (5) = 55 .

Далі достатньо обчислити F3(5). Одержимо таблицю 8.7.

Таблиця 8.7. Витрати F3(5)

Із табл.8.7 бачимо, що F3* (5) = 50 .

Оптимальний план розміщення п'ятьох підприємств між трьома регіонами визначається так.

Оскільки F3* (5) = 50 і досягається для k = 1, то в третій регіон треба розмістити одне підприємство. Далі розподіляємо чотири підприємства між першими двома регіонами. Із табл.8.6 при хj = 4 маємо F2* (4) = 40 і досягається для k = 3 . Це означає, що три підприємства треба розмістити в другому регіоні. Тому в першому регіоні треба розмістити одне підприємство.

Мінімум витрат на будівництво та експлуатацію п'ятьох підприємств становить F3* (5) = 50 од.

Резюме

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

Щоб для розв'язування задачі можна було застосовувати метод динамічного програмування, повинні виконуватись дві вимоги: стан системи на окремому кроці повинен залежати тільки від попереднього стану і керування на цьому кроці (відсутність післядії); функція мети повинна бути адитивною. Сформульовані вимоги лежать в основі принципу оптимальності Белмана.