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

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

Данная задача легко решается методом динамического программирования, так как, если считать состоянием системы на шаге t количество it; а оценкой этого состояния суммарные затраты за все предшествующие годы (1,2, ..., t — 1), то очевидно отсутствие влияния «предыстории». Действительно, можно строить план поставок на все оставшиеся годы из состояния t независимо от того «как система попала в состояние t», то есть от поставок в предшествующие годы, важно только, что в год t мы имеем it. Если следовать обычным рекомендациям, то нужно ввести дискрет 8(например, 8=1), определить состояния системы на каждом шаге t как (it = rt, rt + 8, rt +28, ..., Гу) и, начиная процесс с последнего шага из состояния rj, строить «оптимальную траекторию» (рис. 2.11), то есть последовательно определять и запоминать суммарные затраты на переход в состояние rj из всех состояний сначала шага Т — 1, затем из всех состояний iy_2 шага Т — 2 и так до шага 2, так что из всех возможных переходов из состояния it шага t в состояние it+i шага t + 1 запоминается только тот, для которого суммарные затраты на весь путь до состояния Гу минимальны (пунктир на рис. 2.11). На первом шаге состояние ц = А единственное и в каждом из состояний i2 будут известны затраты на весь путь в состояние rj что дает возможность вычислить затраты на переход из состояния А в каждое из состояний i2 и затем найти минимальные суммарные затраты на весь путь и обратным разворотом определить оптимальную траекторию. Для реализации такого алгоритма необходимо вычислить оценки всех состояний на всех шагах.

Отметим, что при линейных функциях ct(xt) = ktxt и mt(it) = vtit решение по методу динамического программирования может быть получено аналитически, в том смысле, что можно построить ал го-

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

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

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

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

Будем строить оптимальную траекторию из начальной точки в конечную. Затраты первого года z = kX + vjA и затраты второго года Z2 = k^X2 + V2h- Здесь 2 = А + х > Г2; 13 = 12 + х2- Отсюда для любого заданного допустимого состояния i3 получим оптимальный путь, приводящий в данное состояние, то есть найдем такое 12, при котором затраты первых двух лет (z + Z2) минимальны (xi > 0 и Х2> 0). Все остальные пути, приводящие в состояние i3, в соответствии с принципом динамического программирования можно исключить из рассмотрения вместе со всеми их продолжениями. Z2 = zj + Z2 = (vi — kj)A + i2(k] — кз + V2) + кг i3. Здесь i3 задано, a no 12 нужен минимум. Если к) — кг + v2 > 0, то минимум достигается при минимальном 2 = гг независимо от величины i3. При этом затраты за первые два года равны

где

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

Если же ki — кг + V2 < 0, то минимум достигается при максимальном 2, который из условия хг> 0 равен [2 i3- Зная 2, находим ХГ = i2* А и хг* = 0 и 2г*0з) = (vi — k])A + i3(k) + V2). Интересно, что при к] — кг + V2 = 0 можно взять любое гг < 12 ^ 1з- В любом случае суммарные затраты за два года записываются как Z2*(is) = А,2 +Ц2к^ а Для констант Х2 и ц2 получаем другие выражения А,2 = (Vj - k,)A, ц2 = k, + v2.

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

Снова получили линейную функцию, минимум которой может достигаться только в крайних точках. При р2 + V3 — кз > 0 минимум достигается при i3* = Г3 и Z3* = Х3 + р3 [4, где = ?i2 + (р2 + + v3 - к3) г3 и ц3 = к3. Если же р2 + v3 - к3 < 0, то i3* = ц и ^3 =^2>ЙЗ =р2 + v3.

Если обозначить Xl = (vj — кДА и р, = ki, то получаем простое правило вычисления новых констант X, и р, зависимости суммарных затрат на оптимальный переход из начального состояния в заданное произвольное состояние it+i (за t лет) от состояния it+i. Zt* = Xt + pt it+j. Если pt_i + vt — kt > 0, to A,t = ?it-i + (M-t-i + vt

  • — kt) rt, pt = kt и оптимальный переход в состояние it+i на последнем шаге происходит из состояния it* = rt. Если же pt_i + vt
  • — kt < 0, то Xt = Xt-i, pt = pt-i + vt и оптимальный переход в состояние it+i на последнем шаге происходит из состояния it* = it+]. Это правило легко доказывается по индукции.

Если за все t-1 лет затраты равны Zt_i* = Xt_ + pt_i it, то за t лет суммарные затраты Zt = ?it_i + it + ktxt + vtit = ?it_i + (pt_i + + vt-kt) it + kt it+i, так как it+i = it + xt. Далее повторяем точно те же рассуждения, что и при анализе Z3 — затрат за три года.

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

На последнем шаге Zj. = Xj.2 + рт-2 Им + kj-ixT-i + ут-йт-1- Константы и рт_2 вычислены, ij = i-p-1 + xj-i и ij = rj по смыслу задачи.

Получаем Zj. = Xj.2 + (йт-2 + vt-i кдм) ij-1 + кт.^т. Если РТ-2 VT-1 кх-1 >0, ТО Zj_j* = A.j_2 + (РТ-2 VT-1 kj_i) ГТ_! + + кт_]Гт и ij.i* = rj_i, иначе Zj_* = ^т-2 (Цт-2 vt-i) Иг и ij.j* =

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

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

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

Получается так, что для линейных функций оптимальная траектория имеет отличительные свойства: на участках подъема нижняя точка обязательно соответствует минимальному значению rt для соответствующего шага, а верхняя одному из минимальных значений на последующих шагах. Все промежуточные состояния, кроме заданных минимальных, в формировании траектории не участвуют вообще. Конкретно траектория (оптимальный план) определяется параметрами kt и vt заданных функций ct(xt) = ktxt и mt(xt) = vtit (t = 1, 2, ..., Т — 1) и для ее определения нет необходимости анализировать все отмеченные на рис. 2.12 траектории. Необходимо только последовательно пересчитать константы A,t и рь начиная с и и дойдя до последнего шага выявить последний переход, а далее траектория определяется обратным движением из конца в начало, так как известны признаки перехода (подъем или площадка см. пунктир на рис. 2.12). Поскольку период планирования и соответственно число этапов незначительно, получается крайне малый объем вычислений для определения оптимального плана (траектории).

Изложенный алгоритм производит одни и те же действия независимо от числа состояний на каждом шаге, а при численной реализации метода динамического программирования число состояний на каждом шаге существенно влияет на требуемую память и время вычислений. К сожалению, для более сложных исходных зависимостей с(х) и m(i) получить такие «аналитические» решения далеко не всегда возможно. Так, при определении оптимального состояния i2* как функции заданного состояния i3 приходится искать минимум Z2 = mi(A) + С1О2 — А) + т^Ог) + С2О3 — i2) по i2.

Точка минимума, найденная из условия равенства нулю производной Z2 по 12, при некоторых i3 может оказаться за пределами интервала поиска, а при других i3 внутри интервала, что существенно затрудняет дальнейший анализ.

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