Динамическое Программирование Примеры Решения Задач

Ноябрь 12, 2016 – 07:28

Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же и первое, и второе одновременно характеризуются нелинейными зависимостями.

Данный раздел представлен следующими калькуляторами:

Задача распределения инвестиций. Распределении инвестиций между предприятиями П1, П2..., Пn. Инвестируемая сумма E усл. ден. ед.
Складская задача: составить оптимальную программу выпуска продукции X, которая минимизирует суммарные издержки предприятия.

Задача распределения инвестиций

В задачах данного типа заданы сумма инвестиций (или сумма для распределения) и таблица планируемой прибыли. Если сумма для распределения явно не задана, то ее можно найти из таблицы - она равна максимальному значению xi (последняя строчка таблицы).

Таблицы могут иметь разный вид.
Таблица 1 - Первый вариант таблицы исходных данных

	1()	2()	3()
6.3
5.2
4.3	4.6	7.8
*		8.2

* - здесь значение 5 - максимальное значение (сумма для распределения).

Таблица 2 - Второй вариант таблицы исходных данных

10	20	30	40

Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.

При вводе данных первую нулевую строку можно не заполнять.

Метод прогонки

Данная задача соответствует задаче распределения инвестиций. Разница состоит в оформлении результатов полученного решения и применения метода прямой прогонки.

Задача замены оборудования

Цель решения - определить на каких шагах алгоритма (в какие годы) необходимо заменить оборудование. Для этого вводятся Период эксплуатации (в годах) и Стоимость нового оборудования. После этого необходимо заполнить таблицу дохода r(t) и остаточной стоимости S(t).
Задача замены оборудования

Source: math.semestr.ru

Похожие публикации