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

Вернемся к задаче о выборе графика поставок при учете эффекта концентрации и платы за хранение, но теперь откажемся от гипотезы о равномерности спроса. Эта модель разработана Г. Вагнером и Т. Уайтином и в литературе фигурирует всегда как модель Вагнера — Уайтина[1].

Пусть имеется однопродуктовый склад неограниченной емкости. Предъявляемый потребительский спрос удовлетворяется за счет запаса продукта па складе, пополнение запаса осуществляется с помощью заказываемых поставок. Предполагаем, что склад функционирует в течение N этапов планируемого периода. Обозначим через х„ уровень запаса на складе к началу и-го этапа; цп — объем поставок, приходящих в начале п-го этапа; гп — объем спроса за п-й этап, предъявляемый в начале этапа (последовательность гх,..., образует график спроса и предполагается заданной). При этих обозначениях процесс пополнения запаса на складе описывается уравнением

Для определенности будем предполагать, что х1 = 0. Таким образом, состояние системы (склада) характеризуется уровнем запаса, управляющими переменными являются qn.

Требуется найти политику (последовательность qu ..., qN), гарантирующую удовлетворение спроса и минимизирующую суммарные издержки, которые складываются из издержек хранения лежащего на складе продукта и издержек, связанных с поставкой. При предположении, что поставка qn и предъявление спроса гп производятся сразу после момента и, на этапе п хранится объем х„+1.

Будем предполагать, что зависимость издержек от уровня запаса на складе и объема поставки имеет следующий вид:

где h, С и К, предполагаемые одинаковыми для всех этапов, имеют смысл, уже указанный ранее;

Таким образом, суммарные издержки, связанные с функционированием склада, имеют вид

Первое слагаемое, очевидно, не зависит от графика поставок, поскольку

N

Y^q„ есть суммарный объем поставок, а таковой, при требовании полного

п=1

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

и задача минимизации суммарных издержек приобретает вид

при условиях {qn,xn+1}ne[l N) е D, где

D {{cjn у Хп+у }«е{1,..., N) I ^п+1 Яп ~~ бг ’ %п+ — 0, CJn ^ 0, 71 Е {1,N}} Ху — 0}.

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

Смысл этого свойства прост: если продукт есть в наличии, то в поставках нет необходимости. Проведение простых рассуждений показывает, что в оптимальном решении объемы поставок должны совпадать с суммарным объемом спроса за ряд последовательных этапов. Иными словами, длительность отрезка времени между поставками совпадает с суммарной длительностью ряда идущих последовательно этапов, а объем поставки должен совпадать с совокупным объемом спроса за этот отрезок.

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

Для организации перебора удобно использовать динамическое программирование. Введем следующие обозначения: — переменная часть издержек за время использования одной поставки, поступившей на этапе i и покрывающей спрос вплоть до этапа j - 1 включительно; — минимальное значение переменных издержек за j начальных этапов, вычисленное при условии, что к концу этапа j запас полностью исчерпан (х/+1 = 0).

Очевидно, что справедливы рекуррентные соотношения

(перебор ведется по различным вариантам длительности последнего «бес- поставочного» отрезка, примыкающего к моменту j + 1, в предположении, что до него политика была оптимальной).

Можно показать, что если

то

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

Для демонстрации хода вычислений приведем пример.

Пример 6.1

Пусть N = 12 (планирование на 12 месяцев), К = 400, h = 3. Объем спроса, заданный помесячно, приведен в табл. 6.1, где приведены и результаты вычислений.

Таблица в. 1

Объем спроса и результаты вычислений

п

1

2

3

4

5

6

7

8

9

10

И

12

гп

70

100

110

90

50

50

110

120

130

100

40

110

В„

400

700

1100

1370

1650

1920

2320

2680

3080

3380

3600

4000

ч

1

1

3

3

4

5

7

7

9

9

10

12

Опишем подробнее первые расчеты. Имеем

и Т.Д.

Оптимальный график поставок определяется «обратной прогонкой» с учетом найденных моментов itl.

Для всего 12-месячного отрезка планирования последняя поставка должна осуществляться в начале этапа п = 12, поскольку /12 = 12. Это означает, что х12 = 0, и период в 11 месяцев можно рассматривать самостоятельно. Последняя поставка за этот период должна приходить в начале 10-го этапа (/и = 10), после чего рассматривается 9-месячный отрезок, поскольку дг10 = 0, и т.д. После того как моменты прихода поставок определены, объемы поставок элементарно рассчитываются из условий покрытия спроса за период до следующей поставки. На рис. 6.4 изображены оптимальные моменты прихода поставок и значения объема поставок.

График прихода поставок

Рис. 6.4. График прихода поставок

  • [1] Букет Дж., Кенигсберг Э. Научное управление запасами. М.: Наука ; Физматгиз, 1967.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >