Оптимальное планирование поставок

Рассмотрим задачу планирования поставок (закупок) какого-либо оборудования для развития производства в течение ряда лет. Период планирования и его этапы заданы. Принципиального значения не имеют количество этапов и их длительность. Это могут быть годы, кварталы или месяцы. Для определённости будем говорить о годах и считать, что период составляет Т лет. Не имеет принципиального значения и вид поставок. Для определённости будем считать, что это оборудование для развивающегося производства, и обозначим как rt его минимально необходимое количество в начале года t, (t=l,...,T). Реальное количество оборудования в начале года t обозначим it (it>rt). В начальный момент времени (начало первого года) имеющееся количество оборудования известно ii= А>п. Количество поставляемого оборудования в год t обозначим xt>0. Затраты на приобретение оборудования ct(xt) зависят от его количества, причём в различные годы эти зависимости (или их параметры) могут быть разными. Количество оборудования на начало t+1-го года it+i=it+xt>rt+i. Будем считать, что поставки относятся к концу года. Затраты на эксплуатацию (хранение) оборудования также зависят от его количества и в различные годы эти зависимости (или их параметры) могут быть разными, так что в году t эти затраты есть функция mt(it). Требуется разработать такой план поставок, то есть последовательность xt >0 (t=l,2,...,T-l), при котором суммарные затраты на поставки и экплуатацию (хранение) за все годы минимальны. В последний год поставок нет.

Простейшее решение состоит в том, чтобы в каждый год поставлять минимально необходимое количество, то есть принять xt+i = rt+i- rt, но это может оказаться не оптимальным решением, если функции mt(it) нелинейны и закупить и установить сразу большое количество много дороже, чем по частям, или в последние годы поставки дороже, чем в первые.

Данная задача легко решается методом динамического программирования, так как, если считать состоянием системы на шаге t количество it, а оценкой

этого состояния суммарные затраты за все предшествующие годы (1,2,___,t-l),

то очевидно отсутствие влияния предыстории. Действительно, можно строить план поставок на все оставшиеся годы из любого состояния на шаге t независимо от того «как система попала в это состояние», то есть от поставок в предшествующие годы, важно только, что в год t мы имеем it.

Построение оптимального плана (траектории)

Рис. 3.11. Построение оптимального плана (траектории)

Если следовать обычным рекомендациям [6,12], то нужно ввести дискрет 5, например, 8=1, определить состояния системы на каждом шаге t как it=rt, rt +8,rt+28,..., гг и, начиная процесс с последнего шага из состояния гг, строить оптимальную траекторию (рис. 3.11).

При этом необходимо последовательно определять и запоминать суммарные затраты на переход в состояние гт из всех состояний сначала шага Т-1, затем из всех состояний гг-2 шага Т-2 и так до шага 2, так что из всех возможных переходов из состояния it шага t в состояние it+i шага t+1 запоминается только тот, для которого суммарные затраты на весь путь до состояния гт минимальны (пунктир на рис. 3.11). На первом шаге состояние ii=A единственное и в каждом из состояний 2 будут известны затраты на весь путь в состояние гт, что даёт возможность вычислить затраты на переход из состояния А в каждое из состояний 2 и затем найти минимальные суммарные затраты на весь путь и обратным разворотом определить оптимальную траекторию. Для реализации такого алгоритма необходимо вычислить оценки всех состояний на всех шагах.

Покажем, как при линейных функциях ct(xt) =ktxt и mt(xt)= Vtit решение по методу динамического программирования может быть получено «аналитически», в том смысле, что можно построить алгоритм поиска оптимального решения, не требующий анализа всех состояний на каждом шаге и вычисления оценки каждого из них, то есть суммарных затрат на достижение этого состояния по оптимальному пути.

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

Будем строить оптимальную траекторию из начальной точки в конечную.

Затраты первого года zi= kixi+viА, а затраты второго года Z2= k2X2+V2i2. Первое слагаемое -это затраты на поставку оборудования в соответствующем году, а второе слагаемое - это затраты на его эксплуатацию (хранение). Здесь i2=A+xi>r2; i3-i2+X2. Отсюда для любого заданного допустимого состояния Ь получим оптимальный путь, приводящий в данное состояние, то есть найдём такое 2, при котором затраты первых двух лет (zi + Z2) минимальны (xi>0 и Х2>0). Все остальные пути, приводящие в состояние i3, в соответствии с принципом оптимальности можно исключить из рассмотрения вместе со всеми их продолжениями. Z2- z + Z2= kiXi+viA +k2X2+V2i2. Подставляя вместо xi и хг их выражения через 12 и i3, получим

Здесь i3 задано, а по 12 нужен минимум. Если ki- кг+ V2>0, то минимум достигается при минимальном i2*-r2 независимо от величины i3. При этом затраты за первые два года равны

Соответственно

Если же к]- кг+ V2<0, то минимум достигается при максимальном 12, который из условия Х2>0 и i3=i2+X2 равен i2*=i3 и Х2*=0. Зная 'ц*, находим хГ= i2*-A и

При ki- кг+ V2=0 можно взять любое 12 в пределах Г2 < 1 г < h. В любом случае суммарные затраты за два года записываются как i3, а для констант А.2 и рз получаем другие выражения соответственно.

Далее найдём при заданном и состояние i3* из условия минимума суммарных затрат Z3 за три года.

Снова получили линейную функцию теперь от i3, минимум которой может достигаться только в крайних точках интервала поиска. При рг+ V3- кз>0 минимум достигается при i3*= гз и Z3*= А,з+ рз U,

где и рз= кз. Если же

Если за все t-1 лет затраты равны Zt-i*=A,t-i + pt-iit, то за t лет суммарные затраты так как it+i= it +xt.

Если а при pt-i +Vr-kt<0 имеем it*= it+i и xt*=0.

Соответственно в выражении Zt*= A.t + pt it+i для констант A.t и pt в первом случае получаем а во втором

В первом случае из всех допустимых переходов в рассматриваемое состояние it+i выбираем переход из состояния it*= rt, а во втором случае из it*= it+i.

При pt-i +vt-kt=0 можно взять любую пару полученных констант.

В итоге получаем простое правило вычисления (пересчёта) констант А* и pt линейной зависимости Zt*=A,t + pt it+i суммарных затрат на оптимальный переход из начального состояния в заданное произвольное состояние it+i (за t лет):

- если и оптимальный переход в

состояние it+i на последнем шаге происходит из состояния it*=rt.

- если же и оптимальный переход в состояние it+i на последнем шаге происходит из состояния it*=it+i.

Применяем полученное правило пересчёта констант A.t и pt последовательно и запоминаем только последние из вычисленных констант (для перехода на следующий шаг), а также на каждом шаге признаки перехода (1 при it*=rt и 0 при it*=it+i).

На последнем шаге Константы А.т-2 и рт-2

вычислены, iT-iT-i+XT-i и Е=гт по смыслу задачи.

Получаем

Если и

иначе

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

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

Восстановление оптимальной траектории

Рис. 3.12. Восстановление оптимальной траектории

Конкретно эта траектория (оптимальный план) определяется параметрами kt и vt функций Для её построения нет необходимости анализировать все отмеченные на рис. 3.12 траектории. Необходимо только последовательно пересчитать константы X.t и pt, начиная с h и pi, и, дойдя до последнего шага, выявить последний переход, а далее траектория определяется обратным движением из конца в начало, так как известны признаки перехода (подъём или площадка см. пунктир на рис. 3.12). Поскольку период планирования и соответственно число этапов незначительны, получается крайне малый объём вычислений для определения оптимального плана поставок.

Изложенный алгоритм производит одни и те же действия независимо от числа состояний на каждом шаге, а при численной реализации метода динамического программирования число состояний на каждом шаге существенно влияет на требуемую память и время вычислений. К сожалению, для более сложных исходных зависимостей с(х) и m(i) получить такие «аналитические» решения далеко не всегда возможно. Так, при определении оптимального состояния 12*

как функции заданного состояния i3 приходится искать минимум по ii функции Z2=mi (A)+ci (i2-A)+m2(i2)+ C2(i3-i2).

Точка минимума, найденная из условия равенства нулю производной Z2 по 2, при некоторых i3 может оказаться за пределами интервала поиска, а при других i3 внутри интервала, что существенно затрудняет дальнейший анализ. Поэтому при более сложных функциях с(х) и m(i) приходится применять классическую схему динамического программирования: разбить регулярную сетку состояний и организовать по-шаговый процесс поиска оптимальных переходов от конечной точки к начальной или от начальной к конечной.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >