Розробка економіко-математичної моделі оптимального розподілу коштів методом динамічного програмування

3.1 Розробка економіко-математичної моделі оптимального розподілу коштів методом динамічного програмування

Динамічне програмування – це область математичного програмування, що включає сукупність прийомів і засобів для знаходження оптимального рішення, а також оптимізації кожного кроку в системі і виробленні стратегії керування, тобто процес керування можна представити як багатокроковий процес. Динамічне програмування, використовуючи поетапне планування, дозволяє не тільки спростити рішення задачі, але і вирішити ті з них, до яких не можна застосувати методи математичного аналізу. Спрощення рішення досягається за рахунок значного зменшення кількості досліджуваних варіантів, тому що замість того, щоб один раз вирішувати складну різноманітну задачу, метод поетапного планування припускає багаторазове рішення щодо простих задач. Плануючи поетапний процес, виходять з інтересів усього процесу в цілому, тобто при ухваленні рішення на окремому етапі завжди необхідно мати на увазі кінцеву мету [9].

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

На практиці зустрічаються такі задачі планування, у яких помітну роль грають випадкові фактори, що впливають як на стан системи, так і на виграш. Існує різниця між детермінованою і стохастичною задачами динамічного програмування. У детермінованій задачі оптимальне керування є єдиним і вказується заздалегідь як тверда програма дій. У стохастичній задачі оптимальне керування є випадковим і вибирається в ході самого процесу в залежності від випадково сформованої ситуації. У детермінованій схемі, проходячи процес по етапах від кінця до початку, теж знаходиться на кожнім етапі цілий ряд умовних оптимальних керувань, але з усіх цих керувань, у кінцевому рахунку здійснювалося тільки одне. У стохастичній схемі це не так. Кожне з умовних оптимальних керувань може виявитися фактично здійсненим, якщо попередній хід випадкового процесу приведе систему у відповідне стан [9].

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

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

Розглянемо застосування методу динамічного програмування на прикладі розподілу коштів між шістьма об’єктами реконструкції МКВП "Дніпроводоканалу":

1.                 Кайдакська насосно-фільтрувальна станція;

2.                 Ломовська насосно-фільтрувальна станція;

3.                 Водопровідні насосні станції перекачки "Правий берег";

4.                 Центральна станція аерації;

5.                 Лівобережна станція аерації;

6.                 Південна станція аерації.

Загальна сума коштів, що надана на розвиток складає не більш 195 тисяч гривень. На основі техніко-економічних розрахунків установлено, що в результаті реконструкції у залежності від кількості витрачених коштів об’єкти будуть мати продуктивність, приведену у таблиці 3.1. Необхідно визначити оптимальний розподіл коштів між об’єктами реконструкції МКВП "Дніпроводоканалу", що забезпечить максимальне збільшення продуктивності цих об’єктів. Таким чином, у цій задачі використовується критерій оптимізації - сумарна продуктивність підприємств об’єктів реконструкції МКВП "Дніпроводоканалу".

Нехай х1, х2, х3, х4, х5, х6 ¾ кошти, які вкладаються в розвиток відповідно першого, другого, третього, четвертого, п’ятого та шостого об’єкта, 0£ хi £195, i = 1,6. Позначимо f1(x), f2(x), f3(x), f4(x), f5(x), f6(x) - функції зміни продуктивності першого, другого, третього, четвертого, п’ятого та шостого об’єкта при вкладенні в їхній розвиток х тис. грн. Цим функціям відповідають рядки 1, 2, 3, 4, 5, 6 у таблиці 3.1.

Визначимо максимум функції цілі:

F (х1, х2, х3, х4, х5, х6) = f1(x) + f2(x) + f3(x) + f4(x) + f5(x) + f6(x).

При цьому на кошти х1, х2, х3, х4, х5, х6 накладено обмеження:

х1 + х2 + х3 + х4 + х5 + х6 = А,

 тис. грн.

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

Таблиця 3.1 - Вихідні дані про продуктивність об’єктів реконструкції МКВП "Дніпроводоканалу"

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

Виділимо в нашій задачі 5 кроків:

1.                А тис. грн. вкладаються в перший та другий об’єкти одночасно;

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

3.                А тис. грн. вкладаються в чотири об’єкти одночасно;

4.                А тис. грн. вкладаються в п’ять об’єктів одночасно;

5.                А тис. грн. вкладаються в шість об’єктів одночасно.

Позначимо F1,2 (А), F1,2,3 (А), F1,2,3,4 (А), F1,2,3,4,5 (А), F1,2,3,4,5,6 (А) відповідно умовно оптимальні розподіли коштів для першого, другого, третього, четвертого та п’ятого кроків. Алгоритм методу динамічного програмування складається з двох етапів. На першому етапі виконується умовна оптимізація, що полягає в тому, що для кожного з п’яти кроків знаходять умовний оптимальний виграш F1,2 (А), F1,2,3 (А), F1,2,3,4 (А), F1,2,3,4,5 (А), F1,2,3,4,5,6 (А). На другому етапі виконується безумовна оптимізація. Використовуючи результати першого етапу, знаходять величини інвестицій у розвиток об’єктів х1, х2, х3, х4, х5, х6 що забезпечують максимальну продуктивність групи об’єктів. Перший етап включає такі кроки: 1) Обчислення максимуму критерію оптимізації для різноманітних значень коштів х = 0, 15, 30, 45, 60, 75, ..., 195, що використовуються тільки для об’єктів 1 і 2. Розрахунок ведеться за формулою:

F1,2 (А) = max [ f1(x) + f2 (A - x) ];