Задачи динамического программирования

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

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

  1. Задача распределения инвестиций. Распределении инвестиций между предприятиями П1, П2,..., Пn. Инвестируемая сумма E усл. ден. ед.
  2. Задача распределения ресурсов.
  3. Метод прогонки.
  4. Задача замены оборудования.
  5. Складская задача: составить оптимальную программу выпуска продукции X, которая минимизирует суммарные издержки предприятия.
  6. Задача Джонсона.
  7. Задача о рюкзаке (решение задачи о загрузке транспортного средства).

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

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


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


Таблица 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-й детали на соответствующих машинах. Требуется найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Задача Джонсона
загрузка...