Занятие 6. Решение задач ДП: Задача оптимальный план производства

Постановка задачи

Описание:
Фабрика производит стулья, столы и шкафы. Известно, что прибыль с каждого стула равняется 2 единицам прибыли, стола — 3 единицам прибыли и шкафа 5.

Потребляемые ресурсы:
1 единица древесины на стул и т.д. (см. таблица).

Ограничение:
на один день можно истратить только <=11 древесины.

Цель:
Необходимо разработать оптимальный план производства при заданных ограничениях.

Необходимо решить, сколько стульев, столов и шкафов надо произвести, чтобы получить оптимальную прибыль при указанном ограничении.

Введем обозначения:

• x1 — кол-во стульев, которое мы произведем;
• x2 — кол-во столов;
• x3 — кол-во шкафов.

max <- 2*x1 + 3*x2 + 5*x3

1. затраты древесины:

1*x1 + 2*x2 + 3*x3 <= 11

2. нельзя произвести отрицательное количество объектов:

xi>=0   i = 1, 2, 3

3. нельзя произвести половину объекта (полстула, например):

xi ∈ целое число   i = 1, 2, 3

Эту задачу нельзя решить методами линейного программирования (например, Симплекс методом), потому что у нас есть ограничение, что xi должен быть натуральным числом, включая ноль. Поэтому эта задача является задачей дискретного программирования.

Наивное решение

Наивным решением будет решение задачи методом перебора.

Рассматриваются всевозможные планы производства:

• когда мы производим одни стулья,
• когда мы производим одни столы,
• когда мы производим одни шкафы,
• производим 1 стул, 1 шкаф и 1 стол,
• производим 1 стул, 1 шкаф и 2 стола
• … и т.п.

То есть необходимо перебрать все возможные варианты планов производства. Но в результате получится неэффективное экспоненциальное решение.

Решение методом динамического программирования

Воспользуемся динамическим программированием.

Итак, мы определили общую целевую функцию:
max <- 2*x1 + 3*x2 + 5*x3

Решим задачу, как будто есть только производство стульев (F1), потом — только производство стульев и столов (F2), и — есть производство стульев, столов и шкафов (F3) — рис. 6.1.

Определим отдельно целевые функции для каждого этапа решения:

• F1(n) — максимальная прибыль, которую можно получить, производя лишь стулья, имея на складе n единиц древесины
• F2(n)— максимальная прибыль, которую можно получить, производя стулья и столы, имея на складе n единиц древесины
• F3(11)— максимальная прибыль, которую можно получить, производя стулья, столы и шкафы, и, имея на складе 11 единиц древесины

Цель: вычислить F3(11)

F3(11) <- F2(n) <- F1(n), где n = 0 … 11

• Найдем F1(n) для всех n от 0 до 11
• Учитывая найденное решение, найдем F2(n) для всех n от 0 до 11
• Учитывая найденное решение, найдем F3(11)
• В скобках будем записывать функцию argmax — максимальную прибыль

Расшифруем:

1 стул = 1 единица древесины, прибыль = 2: F1(1) = 2
2 стула = 2 единицы древесины, прибыль = 4: F1(2) = 4
…
n стульев = n единиц древесины, прибыль = 2 * n: F1(n) = 2 * n

Вычисление функции F2(n)

Рассмотрим пример:

Если у нас 5 единиц древесины, то мы можем произвести столов:
F2(5) =

• 0 столов: то все 5 единиц переходят на производство стульев (функция уже вычислена) = F1(5) = 10, т.е. F2(5) = 10
• 1 стол: прибыль = 3, 3 единицы древесины переходят на производство стульев F1(3) = 6, т.е. F2(5) = 3 + 6 = 9
• 2 стола: прибыль = 6, 1 единица древесины переходят на производство стульев F1(1) = 2, т.е. F2(5) = 6 + 2 = 8

Получим функцию для 5 единиц древесины:

F2(5) = max[0: F1(5) (прибыль 10);1: 3 + F1(3) (прибыль 9);2: 6 + F1(1) (прибыль 8)] = 10

Рассчитаем по аналогии, например, F2(2):

F2(2) = max[(i = 0 или 1 стол) F1(2) (= 4);3 + F1(0) (= 0)] = 4

Запишем формулу в общем виде:
F2(n) = max[3 * i + F1(n — 2 * i)]
где i — количество производимых столов, и i = 0, 1, … n/2

В итоге получаем, что столы вообще не выгодно производить. Т.е. выгодно производить 0 столов, и тогда функция maxarg производитсва столов всегда равна функции maxarg производства стульев.

Вычисление функции F3(11)
F3(11) =

• 0 шкафов: остальную древесину на стулья и столы, т.е. F2(11) (= 22)
• 1 шкаф: остальную на стулья и столы, т.е. 5 + F2(8) (= 21)
• 2 шкафа: остальную на стулья и столы, т.е. 10 + F2(5) (= 20)
• 3 шкафа: остальную на стулья и столы, т.е. 15 + F2(2) (= 17)

F3(11) = max[0 + F2(11)(= 22);5 + F2(8) (= 21);10 + F2(5) (= 20);15 + F2(2) (= 17)] = 22 — надо производить 0 шкафов.
при i = 0, 1, 2, 3

Теперь восстановим оптимальный план производства:

оптимальный план производства начинается с 22 единиц прибыли и надо начать с производства 0 шкафов, 0 столов и 11 стульев.

Можно решать задачу в любом порядке: например, только шкафы, потом шкафы и столы, потом шкафы, столы и стулья.