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

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

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

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

Типы моделей управления запасами.

Большое разнообразие моделей управления запасами определяется характером спроса на продукцию, который может быть детерминированным или вероятностным. На рис.2 приведена схема классификации спроса, принимаемая в моделях управления запасами.

Рис.2

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

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

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

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

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

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

Характер спроса является одним из основных факторов при построении модели управления запасами, но имеются и другие факторы, влияющие на выбор типа модели.

1. Запаздывание поставок. После размещения заказа он может быть поставлен немедленно или потребуется некоторое время на его выполнение. Интервал времени между моментом размещения заказа и его поставкой называется запаздыванием поставки. Эта величина может быть детерминированной или случайной.

2. Пополнение запаса. Процесс пополнения запасов может осуществляться мгновенно или равномерно во времени.

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

4. Число пунктов накопления запасов. В систему управления запасами может входить несколько пунктов хранения запаса. В некоторых случаях эти пункты организованы таким образом, что один выступает в качестве поставщика для другого. Эта схема иногда реализуется на различных уровнях так, что пункт – потребитель одного уровня может стать пунктом – поставщиком на другом. В этом случае имеется система управления с разветвлённой структурой.

5. Число видов продукции. В системе управления запасами может фигурировать более одного вида продукции. Этот фактор учитывается при условии наличия некоторой зависимости между видами продукции. Так, для различных изделий может использоваться одно и тоже складское помещение или же их производство может осуществляться при ограничениях на общие производственные фонды.

Детерминированные модели управления запасами.

1.Детерминированная обобщённая модель определения оптимального размера партии продукции при допущении дефицита.

Рассматривается система управления запасами, когда продукция поступает на склад непосредственно с производственной линии с постоянной интенсивностью единиц продукции в единицу времени. При достижении некоторого уровня объёма запаса Q производство продукции прекращается. Возобновление производства и поставки продукции на склад осуществляется в момент, когда неудовлетворённый спрос достигнет некоторого значения G. Расходование запаса осуществляется с интенсивностью . Известны значения следующих параметров: - стоимость хранения единицы товара на складе в единицу времени; -стоимость организации заказа (одной партии продукции); - убытки от неудовлетворенного спроса (штраф). Требуется найти оптимальный объём партии продукции и интервал времени между точками возобновления поставки по критерию минимума общих затрат от функционирования системы управления запасами.

Графически условия задачи показаны на рис.3.

Из рисунка видно, что пополнение и расходование запаса осуществляются одновременно в течение интервала каждого цикла. Накопленный запас Q полностью расходуется в течение интервала . В течение интервала спрос не удовлетворяется, а накапливается. Неудовлетворённый спрос G покрывается в интервале .

Величина называется полным циклом управления запасом. - предельный запас продукции, G – предельный дефицит продукции.

Очевидно текущий уровень запаса продукции определяется по формуле:

Из треугольника OAB следует:

или . (1)

Аналогично можно определить , и (2)

Из подобия треугольников OAC и CEF можно записать Из равенства следует, что (3)

Выражение (3) с учётом (1) перепишется:

(4)

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

Если привести затраты в единицу времени, то выражение для удельных затрат будет иметь вид:

Таким образом, есть функция двух аргументов Q и T, оптимальные значения которых определяются как решение задачи:

Для того, чтобы найти минимум функции двух аргументов, необходимо и достаточно решить систему уравнений:

(5)

Это следует из факта, что функция является вогнутой функцией относительно своих аргументов. Решение системы уравнений (5) даёт следующие неотрицательные корни:

(6)

(7)

Минимум общих затрат в единицу времени составит:

(8)

Можно рассмотреть частные случаи.

1. Дефицит продукции не допускается. Решение задачи в этом случае получается из формулы (6)-(8), если положить штраф Тогда С₁/С₃=0 и оптимальные значения искомых величин будут:

Этому случаю соответствует график изменения уровня запаса во времени:

2. Пополнение запаса осуществляется мгновенно. В этом случае полагается и соответственно

График изменения уровня запаса имеет вид:

3. Дефицит не допускается, запасы пополняются мгновенно, т.е. . Тогда следует:

Эти формулы называются формулами Уилсона, а величина - экономическим размером партии.

График изменение уровня запаса имеет вид:

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

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

В случае, если рассматривается функционирование системы за n периодов, причем спрос непостоянен, приходят к динамическим моделям управления запасами. Эти задачи, как правило, не поддаются аналитическому решению, однако оптимальные уровни запасов на каждый период можно вычислить, применив метод динамического программирования.

Рассматривается задача управления запасами, когда спрос за j-ый период (j=1,n) определяется величиной . Пусть – уровень запаса в начале j-го периода, а - объем пополнения запаса в этом периоде. Пополнение запасов осуществляется мгновенно в начале периода, дефицит продукции не разрешается. Графически условия задачи показаны на рис.1.

Рис.1.

Пусть - общие затраты на хранение и пополнение на j-том периоде. Значение задано, а , т.к. в конце функционирования систем запас не нужен.

Требуется определить оптимальные объемы заказов в каждом периоде по критерию минимума суммарных затрат.

Математическая модель задачи будет иметь вид

здесь необходимо определить , которые удовлетворяли бы ограничениям (2)-(6) и минимизировали целевую функцию (1).

В этой модели целевая функция сепарабельная, ограничения (2) имеют рекуррентный вид. И эта особенность модели наталкивает на мысль о возможности применения для ее решения метода динамического программирования. Модель (1)-(6) отличается от стандартной модели динамического программирования наличием условия это условие можно преобразовать следующим образом. Из (2) и (3) следует, что , или можно записать

Тогда из (7) с учетом (4) определяется область возможных значений : или окончательно:

Таким образом, условие (3)-(4) заменяется условием (8), и модель (1),(2),(5)-(6),(8) имеет стандартный вид для метода динамического программирования.

В соответствии с методом динамического программирования решение этой задачи состоит из следующих этапов:

1. Решается задача минимизации затрат на последнем участке, т.е. отыскивается значение

если желаемый уровень запаса в конце планового периода задан, то решение рассматриваемой задачи есть

т.к. в этом случае существует лишь единственный объем производства , обеспечивающий желаемое значение при спросе и фиксированном значении . В противном случае минимизация осуществляется в области (8).

Решаются задачи для k=n-1, n-2….1:

задача (10) решается для любого допустимого фиксированного значения . В результате находятся две функции и. При k=1 задача (10) решается только для одного заданного значения .

После этого проводится обратное движение, и находятся оптимальные значения:

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

Наряду с задачей (1)-(6) рассмотрим аналогичную задачу, соответствующую первым K участкам:

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

Область определения переменной следует из ограничения (12)-(14).

Выражение (17) определяет рекуррентное уравнение Беллмана. Оно справедливо при k=.

Для k=1 соотношение Беллмана имеет вид

Так как , то каждому фиксированному значению при заданном значении соответствуют единственное значение , которое и является точкой минимума.

Алгоритм метода динамического программирования в этом случае состоит из следующих этапов:

Решается задача (18) и находятся и . Далее решается задача (17) и находятся и (j=2,n).

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

Дата добавления: 2014-01-14