Задачи математического программирования
Решения задачи обеими методами дали одинаковый результат.
Лабораторная работа №5 (задача динамического программирования об оптимальном распределении инвестиций)
Задача
Имеются четыре предприятия, между которыми необходимо распределить 100 тыс. усл.ед. средств. Значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств X представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
Таблица 14
| X | g1 | g2 | g3 | g4 |
| 0 | 0 | 0 | 0 | 0 |
| 20 | 14 | 17 | 22 | 20 |
| 40 | 26 | 20 | 21 | 33 |
| 60 | 35 | 32 | 37 | 46 |
| 80 | 52 | 61 | 67 | 30 |
| 100 | 61 | 72 | 58 | 42 |
Решение
Этап I. Условная оптимизация.
Шаг 1. k = 4. Предполагаем, что все средства 100 ден.ед. переданы на инвестирование четвертого предприятия. В этом случае максимальная прибыль составит F4(C4)= 46, данные представлены в таблице 15.
Таблица 15.
| C4 | x4 | F4(C4) | X* | |||||
| 0 | 20 | 40 | 60 | 80 | 100 | |||
| 0 | 0 | - | - | - | - | - | 0 | 0 |
| 20 | - | 20 | - | - | - | - | 20 | 20 |
| 40 | - | - | 33 | - | - | - | 33 | 40 |
| 60 | - | - | - | 46 | - | - | 46 | 60 |
| 80 | - | - | - | - | 30 | - | 30 | 80 |
| 100 | - | - | - | - | - | 42 | 42 | 100 |
Шаг 2. k = 3. Определяем оптимальную стратегию инвестирования в третье и четвертое предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:
.
На его основании рассчитываются данные таблицы 16
Таблица 16.
| C3 | X3 | F3(C3) | X* | |||||
| 0 | 20 | 40 | 60 | 80 | 100 | |||
| 0 | 0+0 | - | - | - | - | - | 0 | 0 |
| 20 | 0+20 | 22+0 | - | - | - | - | 22 | 20 |
| 40 | ||||||||