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

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

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

Таблица 6.1
Прибыль Дерево
стулья 2 1
столы 3 2
шкафы 5 3

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

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

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

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

Сформируем математическое определение задачи:

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

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

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

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

Найдем все ограничения:
  1. затраты древесины:
  2. 1*x1 + 2*x2 + 3*x3 <= 11

  3. нельзя произвести отрицательное количество объектов:
  4. xi>=0   i = 1, 2, 3

  5. нельзя произвести половину объекта (полстула, например):
  6. xi ∈ целое число   i = 1, 2, 3

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

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

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

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

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

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

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

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

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

Определение порядка решения:

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

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

Рис. 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 — максимальную прибыль
Таблица 6.2. Поиск решения для F1(n)
F1(n) F2(n) F3(n)
0 0
1 2
2 4
3 6
4 8
5 10
6 12
7 14
8 16
9 18
10 20
11 22

Расшифруем:

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 производства стульев.

Таблица 6.3. Поиск решения для F2(n)
F1(n) F2(n) F3(n)
0 0 0(0)
1 2 2(0)
2 4 4(0)
3 6 6(0)
4 8 8(0)
5 10 10(0)
6 12 12(0)
7 14 14(0)
8 16 16(0)
9 18 18(0)
10 20 20(0)
11 22 22(0)

Вычисление функции 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

Таблица 6.4. Поиск решения для F3(11)
F1(n) F2(n) F3(n)
0 0 0(0)
1 2 2(0)
2 4 4(0)
3 6 6(0)
4 8 8(0)
5 10 10(0)
6 12 12(0)
7 14 14(0)
8 16 16(0)
9 18 18(0)
10 20 20(0)
11 22 22(0) 22(0)

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

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

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

Задание: необходимо рассчитать оптимальный план производства при следующих исходных данных:

Прибыль Дерево
стулья 2 1
столы 5 2
шкафы 6 3

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

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить