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 - Вихідні дані про продуктивність об’єктів реконструкції МКВП "Дніпроводоканалу"
Порядковий номер об’єкта | Обсяг коштів, наданих на розвиток об’єктів (тис. грн.) | |||||||||||||
0 | 15 | 30 | 45 | 60 | 75 | 90 | 105 | 120 | 135 | 150 | 165 | 180 | 195 | |
Продуктивність об’єктів в результаті розвитку (тис. м3) | ||||||||||||||
1 | 250 | 300 | 320 | 330 | 340 | 350 | 360 | 400 | 430 | 440 | 450 | 460 | 470 | 490 |
2 | 100 | 200 | 300 | 350 | 400 | 500 | 700 | 900 | 1100 | 1440 | 1450 | 1500 | 1600 | 1610 |
3 | 330 | 450 | 460 | 470 | 520 | 530 | 540 | 550 | 560 | 570 | 580 | 600 | 620 | 630 |
4 | 160 | 260 | 310 | 360 | 370 | 410 | 430 | 440 | 460 | 480 | 500 | 510 | 570 | 610 |
5 | 850 | 1230 | 2010 | 2090 | 3170 | 3750 | 4000 | 4010 | 5000 | 5050 | 5100 | 5200 | 5300 | 5400 |
6 | 45 | 57 | 69 | 81 | 93 | 105 | 117 | 129 | 141 | 153 | 165 | 177 | 189 | 201 |
Відповідно до цього принципу, обравши деякий початковий розподіл ресурсів, виконуємо багатокрокову оптимізацію, причому на найближчому кроці вибираємо такий розподіл ресурсів, щоб він у сукупності з оптимальним розподілом на всіх наступних кроках призводив до максимального виграшу на всіх кроках, що залишилися, включаючи даний.
Виділимо в нашій задачі 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) ];
0 £ x £ 195;
0 £ A £ 195.
Результати розрахунку наведені у таблиці 3.2.
Таблиця 3.2 - Обчислення максимуму критерію оптимізації для першого та другого об’єктів
х2 = А - х | |||||||||||||||
0 | 15 | 30 | 45 | 60 | 75 | 90 | 105 | 120 | 135 | 150 | 165 | 180 | 195 | ||
f2 (А - x) | |||||||||||||||
А | f1 (x) | 100 | 200 | 300 | 350 | 400 | 500 | 700 | 900 | 1100 | 1440 | 1450 | 1500 | 1600 | 1610 |
0 | 250 | 350 | 450 | 550 | 600 | 650 | 750 | 950 | 1150 | 1350 | 1690 | 1700 | 1750 | 1850 | 1860 |
15 | 300 | 400 | 500 | 600 | 650 | 700 | 800 | 1000 | 1200 | 1400 | 1740 | 1750 | 1800 | 1900 | |
30 | 320 | 420 | 520 | 620 | 670 | 720 | 820 | 1020 | 1220 | 1420 | 1760 | 1770 | 1820 | ||
45 | 330 | 430 | 530 | 630 | 680 | 730 | 830 | 1030 | 1230 | 1430 | 1770 | 1780 | |||
60 | 340 | 440 | 540 | 640 | 690 | 740 | 840 | 1040 | 1240 | 1440 | 1780 | ||||
75 | 350 | 450 | 550 | 650 | 700 | 750 | 850 | 1050 | 1250 | 1450 | |||||
90 | 360 | 460 | 560 | 660 | 710 | 760 | 860 | 1060 | 1260 | ||||||
105 | 400 | 500 | 600 | 700 | 750 | 800 | 900 | 1100 | |||||||
120 | 430 | 530 | 630 | 730 | 780 | 830 | 930 | ||||||||
135 | 440 | 540 | 640 | 740 | 790 | 840 | |||||||||
150 | 450 | 550 | 650 | 750 | 800 | ||||||||||
165 | 460 | 560 | 660 | 760 | |||||||||||
180 | 470 | 570 | 670 | ||||||||||||
195 | 490 | 590 |
Найбільше з отриманих значень буде F1,2 (195). Інші F1,2 (х) одержуються як найбільше значення кожної діагоналі в таблиці (ці значення в таблиці виділені):
F1,2 (0) = 350;