Задачи динамического программирования
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же и первое, и второе одновременно характеризуются нелинейными зависимостями.Данный раздел представлен следующими калькуляторами:
- Задача распределения инвестиций. Распределении инвестиций между предприятиями П1, П2,..., Пn. Инвестируемая сумма E усл. ден. ед.
- Задача распределения ресурсов. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0.
- Метод прогонки.
- Задача замены оборудования.
- Складская задача: составить оптимальную программу выпуска продукции X, которая минимизирует суммарные издержки предприятия.
- Задача Джонсона.
- Задача о рюкзаке (решение задачи о загрузке транспортного средства).
- Динамическая оптимизация в планировании работ
В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.Объекты / Стадии №1 №2 №3 №4 A1 2 5 4 3 A2 1 4 2 6 A3 3 4 3 4
- Задача о кратчайшем пути (алгоритм Беллмана-Форда)
Задача распределения инвестиций
В задачах данного типа заданы сумма инвестиций (или сумма для распределения) и таблица планируемой прибыли. Если сумма для распределения явно не задана, то ее можно найти из таблицы - она равна максимальному значению xi (последняя строчка таблицы).Таблицы могут иметь разный вид.
Таблица 1 - Первый вариант таблицы исходных данных
| x | f1(x) | f2(x) | f3(x) |
| 1 | 6.3 | 4 | 5 |
| 2 | 5.2 | 6 | 7 |
| 3 | 4.3 | 4.6 | 7.8 |
| 4 | 5 | 6 | 3 |
| 5* | 7 | 6.3 | 8.2 |
Таблица 2 - Второй вариант таблицы исходных данных
| x | 0 | 10 | 20 | 30 | 40 |
| f1(x) | 0 | 4 | 5 | 7 | 8 |
| f2(x) | 0 | 3 | 3 | 4 | 6 |
| f3(x) | 0 | 4 | 4 | 5 | 6 |
Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.
При вводе данных первую нулевую строку можно не заполнять.
В сервисе Задача распределения инвестиций используется метод обратной прогонки.
Метод прогонки
Данная задача соответствует задаче распределения инвестиций. Разница состоит в оформлении результатов полученного решения и применения метода прямой прогонки.В сервисе Метод прогонки необходимо также выбрать метод решения: процедура прямой или обратной прогонки.
Задача замены оборудования
Цель решения - определить на каких шагах алгоритма (в какие годы) необходимо заменить оборудование. Для этого вводятся Период эксплуатации (в годах) и Стоимость нового оборудования. После этого необходимо заполнить таблицу дохода r(t) и остаточной стоимости S(t).Задача замены оборудования
Планирование производственной линии
Задача последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i-й детали на соответствующих машинах. Требуется найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.Задача Джонсона