Жадные алгоритмы

Задача о замене оборудования

Перекрывающиеся подзадачи

Оптимальность для подзадач

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

Укажем два признака, характерных для задач, решаемых методом динамического программирования.

При решении оптимизационной задачи с помощью динамического программирования необходимо сначала описать структуру оптимального решения. Будем говорить, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальные решения её подзадач. Если задача обладает этим свойством, то динамическое программирование может оказаться полезным для её решения (а возможно, применим и жадный алгоритм).

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

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

Второе свойство задач, существенное при использовании динамического программирования, — небольшое число различных подзадач. Благодаря этому при рекурсивном решении задачи мы многократно выходим на одни и те же подзадачи. В таком случае говорят, что у оптимизационной задачи имеются перекрывающиеся подзадачи. В типичных случаях количество подзадач полиномиально зависит от размера исходных данных.

Пусть нужно определить оптимальные сроки замены оборудования. В качестве критерия оптимальности используется получаемая прибыль или суммарные затраты. При заданном объеме выпуска продукции эти два критерия эквивалентны.

Динамическое программирование дает единый подход к решению задачи о замене оборудования.

Математическая постановка задачи следующая. Плановый период разбит на этапов, на каждом из которых можно заменить оборудование (парк оборудования заменяется весь целиком и только в начале этапа). Начальная стоимость оборудования . Стоимость производства на оборудовании возраста составляет . Ежегодные затраты на обслуживание оборудования возраста составляет . Ликвидационная стоимость (выручка от продажи) оборудования возраста составляет .

Будем считать, что возраст оборудования в начале планового периода (и, соответственно, в начале первого этапа) есть . Возраст оборудования будем отображать целым числом. Если парк не заменяется, и в начале -го этапа оборудование имеет возраст , то его возраст равен весь -ый этап, равен весь -ый этап и т.д. Если же в начале -го этапа оборудование имело возраст , но было заменено, то его возраст равен 0 весь остаток -го этапа, равен 1 весь -ый этап и т.д.

На каждом из этапов возможны два варианта управления:

- - сохранить оборудование, тогда этап принесет прибыль , где - возраст оборудования;

- - заменить оборудование, тогда этап принесет прибыль , где - возраст оборудования на начало этапа.

Введем величину - максимальную прибыль в конце -го этапа (), если возраст оборудования в конце этапа составляет . Минимальное значение равно (если в начале -го этапа выполнили замену оборудования), а максимальное составляет (если оборудование ни разу не заменялось с начала планового периода по конец -го этапа).

При значение два возможных управления дают и . Ситуации с недопустимы, поэтому положим .

Проанализируем случаи при .

Значение при можно рассчитать следующим образом. Поскольку , то замены в начале -го этапа не было, поэтому в конце предыдущего этапа (т.е. ()-го) возраст оборудования составлял . В течение -го этапа была получена прибыль (применили управление ). Следовательно, максимальная прибыль в конце -го этапа есть сумма величины и максимальной прибыли в конце ()-го этапа: .

Если , то в начале -го этапа была произведена замена парка оборудования. Если конце предыдущего этапа возраст оборудования составлял , то в течение -го этапа была получена прибыль (применили управление ), и максимальная прибыль в конце -го этапа составит . может принимать значения от 0 до включительно, следовательно,

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

Для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. Многие задачи можно решать с помощью т.н. жадных алгоритмов. Такой алгоритм делает на каждом шаге локально оптимальный выбор, — в надежде, что итоговое решение также окажется оптимальным. Это не всегда так — но для многих задач такие алгоритмы действительно дают оптимум.