11

Лекция № 12. Проблема размерности в динамическом программировании.

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

Увеличение количества переменных состояния вызывает рост числа возможных вариантов решения, ассоциированных с каждым из этапов. Это может привести к так называемой проблеме «проклятие размерности», которая является серьезным препятствием при решении задач динамического программирования средней и большой размерности.

В качестве примера рассмотрим задачу о загрузке рюкзака, но уже при двух ограничениях (например, ограничение по весу и по объему):

(1)

где ,. Поскольку в задаче имеется два вида ресурсов, то необходимо ввести два параметра состоянияи. Обозначим,,. Тогда ограничения (1) можно привести к виду:

(2)

где . В рекуррентных уравнениях метода динамического программирования для задачи о «ранце» с двумя ограничениями (1):

каждая из функций ,является функцией двух переменных. Если каждая из переменных,может принимать 10²значений, то функциюприходится табулировать в 10⁴точках. В случае трех параметровпри тех же предположениях требуется вычислять 10⁸степени значений функций.

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

Задача управления запасами.

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

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

Эти затраты включают в себя:

1. Затраты на приобретение, которые становятся особо важным фактором, когда цена единицы выражается в виде оптовых скидок в тех случаях, когда цена единицы продукции убывает с возрастанием размера заказа.

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

3. Затраты на хранение запаса, которые представляют собой расходы на содержание запаса на складе (процент на инвестированный капитал, амортизационные расходы и эксплуатационные расходы), обычно возрастают с увеличением уровня запасов.

4. Потери от дефицита, обусловленные отсутствием запаса необходимой продукции. Обычно они связаны с экономическими санкциями со стороны потребителей, потенциальными потерями прибыли. На рис.1 иллюстрируется зависимость рассмотренных видов затрат от уровня запаса продукции. На практике какую-либо компоненту затрат можно не учитывать, если она не составляет существенную часть общих затрат. Это приводит к упрощению моделей управления запасами.