5.8. Динамическое программирование

Динамическое программирование — один из методов решения задач оптимизации. Слово “программирование” здесь не имеет того значения, которое свойственно ему в информатике: в данном случае оно является производным от термина programme mathematique, обозначающего систему неравенств, которые нужно решить. Основная идея динамического программирования состоит в том, что неизвестные соответствующей системы рассматриваются как переменные решения, значения, для которых надо выбирать последовательно. Если при этом два различных набора решений приводят к одной и той же ситуации, сохраняется только наилучший из них. Все подходящие значения каждой переменной изучаются параллельно. Следовательно, данный процесс относится к типу предварительного неявного перебора “в ширину”.

Пример 1. Директор фабрики должен за три ближайшие месяца выполнить заказ на четыре комплекта одинаковой мебели.

Учитывая стоимость наладки станков, зарплату сотрудников и стоимость хранения изделий, он подсчитывает суммарную стоимость комплектов мебели в течение месяца для всех возможных пар Таким образом, он составляет следующую таблицу:

Он старается сделать сумму стоимостей за три месяца минимальной, добиваясь при этом выполнения заказа, т. е. при условии

По сравнению с полным перебором поиск получается более эффективным благодаря пошаговому изучению (т. е. изучению месяц за месяцем): в конце первого месяца стоимость четырех возможных ситуаций (0, 1, 2 и 3 сделанных комплекта) может быть вычислена непосредственно из первой строки таблицы. Аналогично сумма стоимостей в двух первых строках показывает стоимость каждой из пяти возможных в конце второго месяца ситуаций. При этом очевидно, что независимо от решений, которые будут приняты в дальнейшем, для каждой из них нужно рассматривать только минимальную стоимость. Итак, стоимость комплектов, сделанных в конце второго месяца, составляет

Таким образом, до конца второго месяца мы получаем

Рис. 5.19. Граф решений в динамическом программировании.

Чтобы общее решение было оптимальным, нужно, чтобы любое подмножество решений было оптимальным. Это утверждение, которое мы только что использовали, мы уточним в дальнейшем.

Поскольку общее количество сделанной к концу трех месяцев мебели является заранее заданным, решение получается за счет добавления полученных значений к каждой из четырех единиц:

Следовательно, оптимальная общая стоимость четырех комплектов мебели равна 40. Соответствующие ей переменные решения могут быть найдены, если мы вернемся по уже сделанным расчетам к началу: по формуле (6), (т. е. в конце второго месяца затем по формуле (4) мы получаем , наконец, Схема решения данной задачи приводится на рис. 5.19 в виде “графа решений”.