Інформаційні технології та моделювання бізнес-процесів - Томашевський О. М. - 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 од.
Резюме
На відміну від задач лінійного та нелінійного програмування, розв'язок яких одержується за один крок, задачі динамічного програмування є багатокроковими - процес пошуку розв'язку складається з низки кроків, на кожному з яких відшукується розв'язок деякої часткової задачі, породженої початковою.
Щоб для розв'язування задачі можна було застосовувати метод динамічного програмування, повинні виконуватись дві вимоги: стан системи на окремому кроці повинен залежати тільки від попереднього стану і керування на цьому кроці (відсутність післядії); функція мети повинна бути адитивною. Сформульовані вимоги лежать в основі принципу оптимальності Белмана.
Початкове керування при розв'язуванні задачі методом динамічного програмування завжди вибирається так, щоб забезпечити максимальну ефективність не першого кроку, а процесу в цілому.
Плануючи багатокроковий процес, вибирають керування на кожному кроці, крім останнього, з врахуванням його майбутніх наслідків на наступних кроках. Останній крок можна планувати так, щоб керування на цьому кроці принесло найбільшу вигоду.
Ключові слова
Динамічне програмування, прийняття рішень, оптимізація, принцип оптимальності Белмана, керування, стан системи, розподіл ресурсів.
Запитання і завдання для обговорення та самоперевірки:
► Назвіть необхідні умови застосування методу динамічного програмування до розв'язування оптимізаційних задач.
► Поясніть властивість адитивності функції мети.
► Проведіть інтерпретацію процесу отримання водійських прав як багатокрокового.
► Наведіть приклади задач (в загальному вигляді), для розв'язку яких найкраще застосовувати метод динамічного програмування.
► Сформулюйте принцип оптимальності Белмана.
Схожі статті
-
8.1. Задачі динамічного програмування Розглянемо так звані задачі динамічного програмування і метод їх розв'язування (метод динамічного програмування)....
-
8.1. Задачі динамічного програмування Розглянемо так звані задачі динамічного програмування і метод їх розв'язування (метод динамічного програмування)....
-
7.1. Роль інформаційних технологій в системі організаційного управління Система (від грецького systema - ціле, складене з частин, з'єднання) - це...
-
Запишемо принцип оптимальності у формалізованій формі. Для цього позначимо через Fn (So) максимальний виграш, який одержується за n кроків при переході...
-
Запишемо принцип оптимальності у формалізованій формі. Для цього позначимо через Fn (So) максимальний виграш, який одержується за n кроків при переході...
-
7.1. Роль інформаційних технологій в системі організаційного управління Система (від грецького systema - ціле, складене з частин, з'єднання) - це...
-
На сьогоднішній день штучний інтелект (Artifical Intelligence, AI) залишається одним із найбільш перспективних і нерозкритих напрямків розвитку...
-
Інформаційні технології та моделювання бізнес-процесів - Томашевський О. М. - 6.4. Експертні системи
Експертною системою (EC) називають систему підтримки прийняття рішень, яка містить знання з певної вузької предметної області, а також може пропонувати...
-
Data Mining (добування знань, даних) - технологія аналізу сховищ даних, що грунтується на методах штучного інтелекту та інструментах підтримки прийняття...
-
Штучний інтелект є одним з напрямів інформатики, завданням якого є розробка апаратно-програмних засобів, які дозволяють користувачу формулювати і...
-
4.1. Принципи функціонування автоматичних засобів видобування знань Для аналізу і розв'язання задач різного характеру, в тому числі і економічних,...
-
Окрім вибору системи шифрування, яка оптимально відповідає характеру інформації, що обробляється, зберігається та передається в інформаційній системі,...
-
4.1. Принципи функціонування автоматичних засобів видобування знань Для аналізу і розв'язання задач різного характеру, в тому числі і економічних,...
-
Self Organizing Maps - SOM, або мапи Кохонена, що самоорганізуються, є різновидом нейронної мережі і використовуються для вирішення задач кластеризації і...
-
Дані представляють собою спосіб представлення, збереження та елементарних операцій обробки інформації. Дані - це основа інформації. Поняття "дані" -...
-
1.1. Визначення поняття технології Словник іншомовних слів визначає технологію як сукупність способів переробки матеріалів, виготовлення виробів і...
-
Життєвий цикл (ЖЦ) фіксує найбільш істотні, характерні для певного об'єкту стани, визначає їх основні характеристики та значення в даних станах, а також...
-
Системи підтримки прийняття рішень, які містять базу знань і розробляються з використанням методів штучного інтелекту, називаються системами підтримки...
-
3.1. Етапи розвитку інформаційних технологій Інформаційні технології посідають чільне місце в нашому житті, тому це поняття є багатофункціональним та...
-
Кодування представляє собою процес присвоєння коду об'єкту класифікації. Кодування забезпечує унікальну ідентифікацію об'єктів, яка в сукупності з...
-
Під терміном ERP (Enterprise Resource Planning) розуміють спеціалізоване програмне забезпечення, яке виконує функції автоматизації певних напрямів...
-
Для забезпечення повноцінного і ефективного обміну інформацією як всередині ІС, так і між різними ІС, автоматизації роботи з даними різних типів,...
-
Обов'язковим реквізитом електронного документа є електронний підпис. Його визначення вказано у Законі України "Про електронний цифровий підпис": Це вид...
-
1.1. Визначення поняття технології Словник іншомовних слів визначає технологію як сукупність способів переробки матеріалів, виготовлення виробів і...
-
Практика використання інформаційних технологій для моделювання та автоматизації підтримки прийняття рішень в управлінні соціально-економічними процесами...
-
Комплексна автоматизація інформаційних потоків підприємства, організації, відомства, галузі вимагає створення єдиного інформаційного простору для...
-
Основною метою систем чи підсистем, що розробляються, є необхідність отримання бажаного результату в межах деякого інтервалу часу. В інформаційних...
-
Різноманітність сфер і форм застосування сучасних інформаційних технологій породжує різноманітність способів їх класифікації. За масштабністю...
-
3.1. Етапи розвитку інформаційних технологій Інформаційні технології посідають чільне місце в нашому житті, тому це поняття є багатофункціональним та...
-
5.1. Структура сховища даних та оптимізація його обсягів Методи інтелектуального аналізу інформації часто розглядають як природний розвиток концепції...
Інформаційні технології та моделювання бізнес-процесів - Томашевський О. М. - 8.4. Задача про будівництво та експлуатацію підприємств