Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Задача Джонсона Симплекс метод Метод прогонки
Задача замены оборудования Задача распределения инвестиций
Параметры сетевой модели Задача коммивояжера Многоканальные СМО

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

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

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

  1. Задача распределения инвестиций. Распределении инвестиций между предприятиями П1, П2,..., Пn. Инвестируемая сумма E усл. ден. ед.
  2. Задача распределения ресурсов. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0.
  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-й детали на соответствующих машинах. Требуется найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Задача Джонсона