Інформаційні технології та моделювання бізнес-процесів - Томашевський О.М. - 8.4. Задача про будівництво та експлуатацію підприємств

Припустимо, що фірма планує будівництво и підприємств однакової потужності. Ці підприємства фірма має можливість розмістити в m (m < и) регіонах. Відомі витрати на будівництво та експлуатацію підприємств в кожному регіоні в залежності від їх кількості. Необхідно так розмістити підприємства серед регіонів, щоб сумарні витрати на їх будівництво та експлуатації були мінімальними.

Запишемо математичну модель задачі. Для цього введемо величини:

Тоді математична модель задачі буде такою:

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

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

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

Оптимальний план розміщення и підприємств серед 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 од.

Резюме

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

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

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

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

Ключові слова

Динамічне програмування, прийняття рішень, оптимізація, принцип оптимальності Белмана, керування, стан системи, розподіл ресурсів.

Запитання і завдання для обговорення та самоперевірки:

► Назвіть необхідні умови застосування методу динамічного програмування до розв'язування оптимізаційних задач.

► Поясніть властивість адитивності функції мети.

► Проведіть інтерпретацію процесу отримання водійських прав як багатокрокового.

► Наведіть приклади задач (в загальному вигляді), для розв'язку яких найкраще застосовувати метод динамічного програмування.

► Сформулюйте принцип оптимальності Белмана.