Стохастические модели теории запасов тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

факультет вычислительной математики и кибернетики

------

_ На правах рукописи

1 ц ДЕК

БУЛИНСКАЯ ЕКАТЕРИНА ВАДИМОВНА

СТОХАСТИЧЕСКИЕ МОДЕЛИ ТЕОРИИ ЗАПАСОВ

специальность 01.01.05 тэория вероятностей и математическая статистика

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Москва 1998

РАБОТА ВЫПОЛНЕНА НА КАФЕДРЕ ТЕОРИИ ВЕРОЯТНОСТЕЙ • МЕХАНИКО-МАТЕМАТИЧЕСКОГО ФАКУЛЬТЕТА МОСКОВСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА имени М.В.ЛОМОНОСОВ

Официальные оппоненты:

академик Российской Академии Наук, доктор физико-математических наук, профессор Ю.В.ПРОХОРОВ

доктор физико-математических наук, профессор С.А.АЙВАЗЯН

доктор физико-математических наук, профессор А.В.ПЕЧИНКИН

Ведущая организация - Московский Государственный Институт Электроники и Математики (Технический Университет)

Защита диссертации состоится 4.) Ср г. в 11 час. на

заседании Диссертационного Совета Д U53.05.38 при Московском Государственном Университете имени М.В.Ломоносова по адресу: 119899 Москва, Воробьевы горы, МГУ, факультет ВМиК, аудитория 685.

I I

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

/

Автореферат разослан /о ОцмлЛ^ 199

Ученый секретарь Диссертационного Совета профессор

Н.П.ТРИФОНОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Математическая теория запасов возникла менее 50 лет назад благодаря работам K.J.Arrow, T.Harris, T.Marschak, A.Dvoretzky, J.Kiefer, J.Wolfowitz. Тогда же сложилась традиция широкого использования в теории терминологии, идущей от приложений. До 50-х годов нашего века велись отдельные исследования некоторых детерминированных моделей. Согласно обзору T.Whitin'a до 1953г. насчитывалось 180 таких работ. Среди ранних результатов отметим известную формулу Wil-sorfa (которую связывают также с именами K.Andler, B.Marganinsky, К.Steffanic-Allmayer, F.Harris), описывающую оптимальный размер заказа как определенную функцию от размера потребления. Единственной и весьма простой стохастической моделью, возникшей в годы Второй мировой войны, была модель "продавца газет" Ph.Morse и G-KimbelFa. вошедшая ныне в большинство учебников по исследованию операций.

С 50-х годов до настоящего времени теория запасов прошла в своем развитии несколько важных периодов. Исследования таких авторов как R.Bellman, J.Glicksberg, О.Gross привели к созданию динамического про-грамирования, послужившего основой решения большинства задач в рамках так называемого "стоимостного подхода", связанного с минимизацией средних издержек. Большой вклад в развитие этого направления внесли S.Karlin, Н.Scarf, A.Clark, J.H.Girlich, H.Klemm. R.Grubström, E.Silver, S.Axäter и многие другие ученые.

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

поставки (приток воды) случайны, иначе говоря, описываются некоторым случайным процессом. Существенный вклад в создание и развитие этого направления внесли P.A.P.Moran, J.Gani, N.U.Prabhu.

С середины 60-х годов возникает новый "надежностный подход" в теории запасов. Пионерской работой в этой области была статья А.Ргёкора 1964г. Данный подход ориентирован на те ситуации (прорыв плотины, другие катастрофы), когда в качестве целевой функции не следует выбирать лишь возникающие издержки. Перспективность такого подхода обеспечивалась глубокими результатами, полученными в математической теории надежности Б.В.Гнеденко, А.Д.Соловьевым, И.Н.Коваленко, В.А.Каштановым, Ю.К.Беляевым, их коллегами и учениками. Важно подчеркнуть, что с начала 70-х годов разворачиваются исследования в области теории водохранилищ, связанные с введением управлений.

После нефтяного кризиса 1973г. во всем мире усиливается интерес к детерминированным моделям, связанным с централизованным планированием производственных процессов, запасов сырья и полуфабрикатов. В 1975г. выходит монография J.A.Orlicky "Material Require-raent Planning", посвященная этим проблемам. Ведущие японские компании вкладывают средства в теоретические исследования нового направления в теории запасов, получившего название синхронизации поставок и потребления. Основы этого направления заложены T.Ohno(1982-1986), K.Suzaki (1985), S.Shingo (1985-90). Цель этого подхода - по возможности сократить уровень запасов (в том числе до нуля) и тем самым уменьшить издержки. В 80-е годы идеи этого направления начинают распространяться на США и Западную Европу. К началу 90-х годов появилось уже более 1000 работ в журналах, а также книг по системам с синхронизацией ("just-m-time'1). Среди них - исследования R.W.Hall, Y.Monden, S.Jordan, W.E.Deming. T.P.Ryan, R.J.Schönberger. M.J.Schniederjans. H.Groenvelt, U.S.Karmarkar, S.Kerkre и др. Однако до настоящего времени имеется очень мало работ (J.A.Buzacott, D.Mitra, I.Mitrani, P.H.Zipkin), в которых делаются попытки учесть в подобной ситуации возможность случайных возмущений детерминированных процессов (задержки в доставке, брак производства, выход из строя оборудования и др.). Дестабилизирующее воздействие на экономические процессы жестких систем планирования без буферов в виде запасов ярко проявилось во время землетрясения 1995г. в Кобе, когда производство

остановилось из-за отсутствия запасов и невозможности поставок вследствие разрушения коммуникаций.

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

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

Цель работы - решение следующих взаимосвязанных проблем современной математической теории запасов.

1) Создание теории устойчивости случайно возмущенных систем с синхронизацией поставок и потребления.

2) Разработка нового подхода к определению асимптотически оптимальных политик управления запасами в условиях неизвестного распределения спроса.

3) Анализ асимптотического поведения моделей с дискретным временем на основе диффузионных приближений.

Методы исследования. Основные результаты диссертации получены с помощью сочетания методов преобразований Лапласа, факторизации Винера-Хопфа и сходимости мер в функциональных пространствах. Использован также аппарат теории случайных процессов (про-

цессов восстановления, регенерирующих и марковских).

Научная новизна работы состоит в следующем.

1. Впервые исследована устойчивость случайно возмущенных систем с синхронизацией поставок и потребления. Установлена неустойчивость к малым случайным возмущениям широко применяемых на практике систем типа "just-in-time". Доказано, что введение многоуровневых управлений приводит к стабилизации неустойчивых систем. Введена новая целевая функция, характеризующая функционирование системы и найден вид оптимального управления. Таким образом, построена законченная теория устойчивости случайно возмущенных систем с синхронизацией поставок и потребления.

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

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

4. Обобщены управляемые модели с непрерыным временем (M.J.Faddy. F.A.Attia, P.J.Brockwell, D.Zuckerman и др.), показано, что процессы, описывающие введенные автором модели, являются предельными для соответствующим образом нормированных процессов с дискретным временем.

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

вероятностей.

Апробация работы. Результаты диссертации докладывались на многих конференциях в нашей стране и за рубежом, в том числе на Международном конгрессе математиков в Москве (1966 г.), на I, III, IV, V, VI Международных Вильнюсских конференциях по теории вероятностей и математической статистике (1973, 1981, 1985, 1989, 1993гг.), на I Всемирном конгрессе общества Бернулли (Ташкент, 1986г.), на двенадцати Международных семинарах по проблемам устойчивости стохастических моделей в период 1979-1998 гг., на всех десяти Международных симпозиумах по теории запасов в Будапеште (1980-1998 гг.), на Международном симпозиуме по исследованию операций в Пассау (1995г.), на 21-27 Всепольских конференциях по приложениям математики в 1992-98 гг. и др. Неоднократно делались доклады на Ломоносовских чтениях в МГУ, научно-исследовательских семинарах механико-математического факультета и факультета вычислительной математики и кибернетики МГУ, ДЭМИ РАН.

По теме диссертации были прочитаны лекции и доклады в университетах Бухареста (1973г.), Берлина (1974г., 1990г.), Дрездена (1974г.), Лейпцига (1974г., 1989г.), Будапешта (1985г.), Софии (1986г.), Ульма (1990г.), Магдебурга (1995г.), Лондона (1998г.).

В 1998г. решением Исполкома Международного общества по исследованию запасов (КЗШ.) Е.В.Булинской присуждена медаль "За выдающийся вклад в развитие математической теории запасов".

Структура и объем работы. Диссертация состоит из введения, четырехглав, списка литературы (219 наименований) и списка публикаций автора по теме диссертации (64 наименования). Объем работы 271 страница.

Данная работа основана на результатах исследований, проводившихся автором в течение многих лет на кафедре теории вероятностей механико-математического факультета МГУ. Автор пользуется возможностью выразить искреннюю признательность всем сотрудникам этой кафедры, возглавлявшейся Андреем Николаевичем Колмогоровым, Борисом Владимировичем Гнеденко, а ныне - Альбертом Николаевичем Ширяевым, за творческую, доброжелательную атмосферу и постоянную поддержку.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Основным объектом исследования в диссертации являются стохастические модели теории запасов.

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

Глава 1 "Случайно возмущенные системы с синхронизацией поставок и потребления" разделена на 8 параграфов, в первом из которых дается описание исходной модели и устанавливаются некоторые вспомогательные результаты. Данная глава посвящена изучению влияния случайных возмущений на качество функционирования системы, ее устойчивость и надежность, а также выбору оптимальных параметров в стационарном режиме. Здесь главную роль играет исследование случайных блужданий в полосе. Изучены все возможные комбинации граничных условий. Важным показателем качества функционирования системы, предложенным автором, являются времена поглощения (определяемые ниже), поэтому много внимания уделяется их изучению.

Для систем производства-хранения характерны потребление и поставки партиями фиксированного размера. Без ограничения общности размер партии может быть принят за единицу, тем более, что согласно результатам К.,1.8с11опЬе^ег'а и МЛ.8сЬгиес1едап5'а при достаточно широких предположениях единичный размер партии является оптимальным. При этом естественно полагать, что ширина полосы, соответствующая объему хранилища, равна целому числу п. Начальный уровень запасов а' также считается целым, а размер экстренной поставки равен 1. Сделанные предположения приводят к тому, что чистое пополнение Л"; за ¿-й период принимает три значения -1, 0 и 1. В разделах 1.2-1.5 проводится исчерпывающее исследование неуправляемых систем, в которых случайные величины А',- предполагаются независимыми и одинаково распределенными. Обозначим

Р(Х,- = 1)=р, Р(^ = -1)=9, ВД = 0) = г, (1)

р > 0, 5 > 0, г > 0, р + д + г = 1.

В разделах 1.2-1.4 исследуется асимптотическое поведение времен достижения т/М,, г = 0,1,2, при п -> оо. Величина т][°1 определяется соот-

ношением

= min{fc > 0 : s£0) = п или Sf] = 0}, (2)

где Sq0' = х, a = £ A'¡. Для определения i = 1,2, используется ¿—i '

соотношение, аналогичное (2), где сохраняется лишь требование ' = п, а определены должным образом в модели с индексом (г).

Найден явный вид предельного распределения случайных величин нормированных своим средним, что позволяет сделать вывод об устойчивости модели по отношению к флуктуациям параметра г. Природа этого явления допускает объяснение с помощью широко известных результатов Б.В.Гнеденко, В.М.Круглова, В.Ю.Королева, так как i = 0,1, могут быть представлены в виде сумм случайного числа случайных слагаемых. Однако методы упомянутых авторов не позволяют установить характер предельных законов. Подчеркнем, что выбор Е//[!]г в качестве нормировки позволил не только обобщить результаты W.Stadje, R.A.Khan, М.Хаджара, относившиеся к частному случаю (г = 0, задерживающий экран в нуле, другая нормировка), но и глубже понять природу изучаемых систем. Отметим также, что процесс с г = 0 не подходит для описания случайно возмущенных систем just-in-time даже в простейшем предположении, что поставки и потребление представляют собой две независимые последовательности бернуллиевских случайных величин. Поэтому нами проведен детальный анализ случаев, когда г > 0.

Область возможных изменений начальных состояний (0,п) разбивается на две части, которые молено назвать областью устойчивости и областью неустойчивости по отношению к начальному состоянию х. При р ф q предельное распределение не зависит от начального состояния х в довольно широкой области его изменения, а именно, когда i со и п — £ оо при п —> со (иначе говоря, когда начальное состояние достаточно удалено от поглощающих границ). Напротив, при фиксированном к и х = к, х = п — к в модели (0), а также при х — п — к в моделях (1) и (2) с верхней поглощающей границей, предельное распределение зависит от к. При нулевом сносе (р — q) даже в центральной части полосы (0, п) наблюдается сильная зависимость предельного распределения от начального состояния, что доказывает

Теорема 1.4. Пусть а — 1 и при п —> оо начальное состояние ме-

нлется таким образом, что хп 1 -4 с, с £ (0,1), тогда -4 тс, где неотрицательная случайная величина тс обладает плотностью

оо

1с{у) = (2тгс(1 - с)у3)~1/2 £ (—1)*(е + к) ехр{—(с + &)2/2с(1 — с)у}

к--оо

при у > 0.

Здесь и далее обозначается а — д/р, т^'1 = 1^П/Е))[!'„, а шапочка над символом г напоминает о том, что речь идет о случае а — 1.

Асимптотическое поведение т^ разительно отличается от предельного поведения т.^ при а ф 1. В самом деле, согласно теореме 1.3, при предельное распределение вырождено, точнее, г]0^ А- 1 при п —> оо, если также х —> оо, п — х —со.

Наличие в нуле задерживающего (модель (1)) или отражающего (модель (2)) экрана меняет характер предельного поведения г = 1,2 в центральной полосе по сравнению с что демонстрируют теоремы 1.5 и 1.7. Приведем формулировку первой из них.

Теорема 1.5. Если р > q,a х фиксировано или растет с ростом п так, что п — х —>• со при п оо, то т^ -4- 1.

Если р < д, в тех же предположениях о начальном состоянии х\ имеем -4 т, где т распределена показательно с параметром 1.

Если р — 5 и хп~1 —»■ с 6 [0,1) при п оо, то т^1] -4 тс, где неотрицательная случайная, величина тс обладает плотностью

дс(у) = (2тг(1-с2)у3Г1/2 Е (—1)т+1(2то+с—1) ехр{-(2т+с—1)2/2^(1-с2)}

т=—со

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

Эти результаты были получены с помощью техники преобразований Лапласа, что позволило также исследовать характер поведения для х, лежащих в приграничной полосе. Как установлено в теоремах 1.6 и 1.8, при р < q существует предельное распределение являюще-

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

В разделе 1.4 демонстрируется, что при р ф q результаты, касающиеся области устойчивости по отношению к начальному состоянию, могут быть получены и с помощью метода моментов.

В разделе 1.5, в отличие от предыдущих, изучается асимптотическое поведение всех трех ранее рассмотренных систем в предположении, что случайное возмущение убывает. Это означает, что г —> 1 (или, что то же самое, р —»■ 0, q -> 0), в то время как ширина полосы п и начальное состояние х остаются фиксированными.

Полученные в следствии 1.9 явные выражения для вероятностей г — 0,1,2, выйти на поглощающую границу прежде, чем произойдет возвращение в начальное состояние, показывают, что q^ —> 0, если р —> 0, g —> 0 так, что а — qp~l остается фиксированным. Иначе говоря, достижение поглощающей границы на периоде регенерации является "редким событием". Однако из следствий 1.10 и 1.11 (из раздела 1.5) вытекает, что условия известной теоремы Соловьева об асимптотической показательности времени до наступления редкого события не выполняются. И хотя эти условия не являются необходимыми для показательности предельного распределения, удается доказать, что и в самом деле характер предельного поведения существенным образом зависит не только от х н п, но и от конкретного значения а. Справедлива, например, следующая теорема.

Теорема 1.9. Пусть р —> 0 таким образом, что а = qp"1 остается фиксированным, т.огда

1) при произвольном а имеем г}®] т, где т распределена показательно с параметром 1,

2) при п = 3, х — 1,2 аналогичное утвержедние справедливо лишь

для а — 1, т.е. -4 г,

3) при п. = 3 и а ф 1 предельное распределение имеет плотность /j°,j(f) = 0 при t < 0, а для t > 0 она зависит от а:

/u(í) = {cosh[ív^(2+a')/(l+a+a2)]+o3/2sinh[fv^(2+a)/(l + Q + ü2)]}x

х[(2 + а)/{ 1 + а + а2)] ехр{-<(2 + За + а-2)/(1 + а + а2)}, Í2°¡{t) = {acosh[ív^(l+2a)/(l+a+a2)]+a~1/2sinh[¿v/a(l+2a)/(l+Q+Q;2)]}x х[(1 + 2a)/(í + а-f a2)]exp{-í(l +3а + 2а2)/(1 + а + а2)}.

Существование плотности у предельного распределения при любых х, п и а устанавливает

Теорема 1.10. Для любых п > 4, х = 1,п — 1, предельное распределение (при р —» 0 и фиксированном а) обладает плотностью /^(О (зависящей от а). В частности, при т > 1, £ > О

= [(1 + а2т)/с'°'(2т, 2т+1)] П ~ х

<? Э'фд

х ехр{-*(1 + а + )/с'0'(2т, 2т+1)}, (3)

где с^(2т,2"1+1) задается следствием 1.12. Б (3) Л4Ы суммируем по всевозможным наборам а — (сгь..., ат) длины т с а, = О, I, г = 1, гп? и

= (-1)^(2 + (—1)СТ2(2 + (-1)^(2 + ... +(-1)^-+ (-1)^"Л/2)1/2 - --)1/2)1/2)1/2-

Далее,

(индекс ~ означает, что поменяли местами р и д. иными словами, подставили аГ1 вместо а).

Отметим, что для явного описания плотностей полезно замечание 1.7, согласно которому предельные распределения т^ и г^х п совпадают. При а ф 1 совпадают предельные распределения т^ и г^0^,,, значок показывает, что речь идет об обратном случайном блуждании.

Аналогичные результаты получены и для моделей с дефицитом и с экстренными поставками. При этом особенно интересными представляются просто формулируемые утверждения теорем 1.12 и 1.13, устанавливающие связь между поведением систем с различными граничными условиями:

/Й1(0 - для п>2,

и

/¿^(0 = /]+1.п+1(*) для п>1, х<п.

Таким образом, в результате проведенных исследований становится ясным, что системы с синхронизацией поставок и потребления неустойчивы по отношению к малым случайным возмущениям. А сравнение

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

Однако до этого в разделе 1.6 рассматриваются дважды стохастические системы, которые описываются случайными блужданиями в случайной среде. Наглядно это означает, что вероятности (p,q) в (1) заменяются на независимые одинаково распределенные случайные векторы (Р^-

Следующий результат не только представляет самостоятельный интерес, но и позволяет уточнить теоремы 1.5, 1.7, как показывает приведенное далее следствие 1.19.

Теорема 1.16. Если а\ < 1, Ь\ < ос, а х таково, что п — х оо при п оо, то Т^ДЕТ^,)-1 -> 1 почти наверное при i — 1,2

Здесь обозначено: а! = Ма, = М/5, случайные величины а и ft определяются аналогично неслучайным а и ft с помощью равенств а = qp-1, ft = p~l, a M означает их математическое ожидание (в отличие от Е, которое предполагает двойное усреднение). Через обозначено время до выхода на уровень п процессом, начинающимся в точке х.

Следствие 1.19. При а < 1 имеет место сходимость rj'l к 1 не

только по вероятности, но и с вероятностью 1.

Дальнейшее уточнение теоремы 1.16, проведенное в разделе 1.7, позволяет получить экспоненциальное убывание хвостов распределения максимального размера дефицита (теорема 1.19). А это в свою очередь полезно для расмотренного в данном разделе надежностного подхода к системам с синхронизацией (JIT).

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

Последний раздел 1.8 главы 1, посвященный оптимизации системы в стационарном режиме, отличается от предыдущих тем, что распределение случайных величин А',- предполагается нерешетчатым, а объем хранилища R произвольным неотрицательным числом. Как и в разделе 1.7, изучается процесс с двумя задерживающими границами и сначала исследуется асимптотическое поведение его стационарного распределения при Ft —> оо. Как показывают теорема 1.27 и следствие 1.11, это асим-

птотическое поведение при нулевом снссе оказывается одинаковым для решетчатых и нерешетчатых распределений скачков. Найденный вид стационарного распределения позволяет решить задачи о выборе оптимального объема хранилища при фиксированных издержках и исследовать его асимптотическое поведение, когда штраф за дефицит или за переполнение неограниченно возрастает, т.е. по сути дела рассматривается переход от стоимостного критерия к надежностному (теоремы 1.22, 1.23, 1.28 и следствие 1.23).

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

A.А.Боровкова, В.С.Королкжа и Ю.В.Боровских, Н.Прабху, Л.Такача.

B.Федлера, а также работы С.А.Айвазяна, Л.Г.Афанасьевой, В.М.Золотарева, В.И.Лотова, А.А.Могульского, С.А.Молчанова, А.В.Печинкина и многие другие). Подчеркнем, что в диссертационной работе изучаются те аспекты случайных блужданий, которые представляют интерес для теории запасов и которые ранее не рассматривались.

Глава 2 "Управляемые системы и оптимизация" состоит из 5 параграфов. В данной главе продолжается исследование случайных блужданий в полосе, но без предположений о независимости и одинаковой распределенности скачков Х*.

Раздел 2.1 дает определение управляемой системы и описывает класс допустимых управлений. Как указано в предыдущей главе, неуправляемые процессы с вероятностью 1 достигают одной из границ. Поскольку в приложениях желательно как можно дольше отсрочить остановку процесса, связанную с выходом на поглощающую границу, естественно вводить управления, создающие защитные зоны вблизи таких границ.

Вместо (1) теперь предполагается,что для любого у 6 (0, п)

Р(А',+1 = 1 ¡в^ = у) = р(у), Р(ХШ = -1/5,- = у) = д(у),

Р(Х;+1 = 0/5; = у) = г (у), р(у) + д{у) + г(у) = 1 1 ;

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

Применение многоуровневого управления с I переключающими уровнями п,-, 0 — п0 < п\ < ... < щ < 1 = п, означает, что в (4)

Р(у) = Р<- Ч{У) = Чи Лу) = г, (5)

для у 6 [?гьпг+1), £ = 0,При £ = 0 значение у = 0 в соответствующую полосу не включается. Для модели (0) с двумя поглощающими экранами р{у) — ?(2/) = О1 г(у) = 1 при у = 0, п. В модели (1) с задерживающим экраном в нуле р(0) = ро, д(0) = 0, г(0) = 1 — ро. Модель (2) с отражением в нуле отличается от предыдущей тем, что р(0) = 1, д(0) = г(0) = 1.

Сначала в разделе 2.2 рассматривается модель с экстренными поставками при наличии одно- или двухуровеневого управления. Это значит, что имеются два уровня щ и щ (щ < п2) такие, что

!1~1П( Ь;, г = 1,2. при п -4 оо (6)

и выполняются соотношения

р{х) =р0. я(£) = Чо, г(х) = 0 и ро > 90 при я-е[1, П!); р{х)= р2, д(х) = 52, ф:) = 0 и ^ < © при г€[п2, «)-

Что касается средней полосы [п),«^ то здесь = р], д(х) = г/ь

г(а-) = Оказывается, что не только величина п, но и направление сноса в этой области не влияет на характер асимптотического поведения. А именно, во всех трех случаях (р\ > р\ = дъ р\ < 51) величины т]2] асимптотически показательны в достаточно широком диапазоне значений х (теорема 2.2).

Доказательство этого утверждения, разбитого на ряд теорем и лемм, требует рассмотрения вспомогательных случайных блужданий и занимает 16 стр. Исследование проводится с использованием свойств регенерирующих процессов. Условия (7) означают, что при пересечении уровней щ и п-2 происходит "переключение", т.е. меняется размер сноса, а возможно, и его направление. Иначе говоря, двухуровневая политика может пониматься следующим образом: когда уровень запасов попадает в область [О, П1), частота поставок увеличивается, а в области [»2,п) она уменьшается. Другая возможность - соответственно увеличивать или уменьшать частоту отказов потребителям.

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

(7) ослаблены следующим образом: вместо г(х) —- 0 при х £ [l,«i) и х 6 [п2,п) предполагается, что г(х) > 0 при всех х € (0,п).

Наличие управления существенным образом меняет характер асимптотического поведения т^. В то время как для неуправляемой системы прир ф q предельное распределение т^ было сосредоточено в одной или в двух точках, нормированное время до поглощения в управляемой системе является асимптотически показательным не только для состояний х, лежащих в центральной полосе [ni,ri2), но и в тех частях подполос [l,ni) и К п), которые достаточно удалены от поглощающих границ (теорема 2.7). В этой области устойчивости относительно начального состояния управляемая модель устойчива и по отношению к параметрам Г{, i — 0,1,2. Доказательство данного результата потребовало детального анализа определенных рекуррентных уравнений. Использование преобразований Лапласа позволяет также изучить и область неустойчивости по отношению к начальному состоянию х, где предельное распределение зависит от х, хотя и не меняется с изменением pi, qi и ri, как утверждает

Теорема 2.8. Для любого ai при фиксированном к и п ос имеет место соотношение -4 т*, где распределение т- это смесь (с весами 1 — и а{) показательного распределения с параметром и вырожденного, сосредоточенного в нуле. При тех же предположениях Гп-кп Тк, где распределение f- это смесь (с весами 1 — ajj"* и а%к) показательного распределения с параметром 1 — ayk и вырожденного, сосредоточенного в нуле.

При рассмотрении в раздаче 2.4 более широкого класса допустимых управлений ситуация оказывается еще более сложной, поэтому и там отдается предпочтение исследованию производящих функций и преобразований Лапласа. В дополнение к (4) и (5) предполагается, что pt > qt, t = 0, к — 1, pt — qt, t =■ k. m — 1, pt < qt, t = m,l, для некоторых к и т, I < к < то < Z, т.е. требование о наличнн '"защитных зон1' у поглощающих границ сохраняется. Исследование асимптотического поведения управляемой системы проводится при дополнительном условии о зависимости переключающих уровней щ, г = 1,1 от ширины полосы (объема хранилища) п при п —> оо. А именно, пусть существуют а, > 0,

г — 0, п, такие, что i

di = 1 и (rii+1 — П{)п~1 -4 a,i при п —> оо. (8)

¡=0

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

Доказательство основного результата данного раздела (теорема 2.9) разбито на б лемм. При этом за счет введения должных вспомогательных функций удается провести анализ очень громоздких выражений. Так, согласно лемме 2.24, если х £ [n(,ni+i), то при t = к производящая функция R(x) = EzVt'" записывается в виде R(x) = Л^Д-1, где

Л* = Ьк1<рш{х) + Ьмщ-1(х),

Л = Е Е {~1)1-^тк(пш + j, щ + ■«■*+!,i-л t=—1 j=—i

и

R(x) ~ [R(iit+i)ist-i(x-) + btlmt(nt+u х)]^"!1^^^) для t = 0, к - 1,

R(r) = [R(nt - l)<pt+i(x) + bi2mt{x,nt - l)]^^ - 1) для t = к + 1,1.

Однако при этом функции vt(x), t — —1,к — 1, и <Pt(x), t = к + 1,1 + 1, а также t = 0,к — 1, i — —1,0 и е1Лt = к+ 1,1, j = —1,0

определяются для целых к, 0 < к < I, и j, 0 < х < п, с помощью следующих рекуррентных соотношений

Е {-l)l~'mt+1(x,nt+i + i)dt^i, »= —1

üLu_; = -(1 + г), dt^i = Vt-i{nt+l - 1 - i),

Vt(x) = E (-l)_-,mi_i(R(+ j.x)e(, j=-i

= 1 + j, ei,l-j = Vi+l("i ~ 1 ~ j)-

Кроме того,

boi = 1, = 'п т,-(п,-+1,п,-+1 - 1), i = 1, fc,

!=0

Ь/2 = 1, 6(2 = П mi(ni,ni-l), t-k,l- 1. !=t+l

и для t = 0,1 и неотрицательных целых чисел 1\ и обозначено пц{1\, Щ = Х[\Х% - А'ДЛ'г, где = ;/ = 1,2 имеют вид

Ау = (г^я)-1!! - + - Пг)2 - 4№2]1/2} .

Теорема 2.9 устанавливает, что при любом числе переключающих уровней I предельное распределение оказывается показательным с параметром 1, если х —>• оо при п оо так, что п — х -> оо. Таким образом, введение указанных управлений стабилизирует систему.

Управление вводится для того, чтобы как можно дольше не произошел выход на границу. Поскольку предельное распределение при любом многоуровневом управлении одно и то же, представляется естественным найти среди них оптимальное. Ключевую роль в задачах оптимизации играет выбор целевой функции. В разделе 2.5 автором предложена в качестве целевой функции скорость роста среднего времени до поглощения. Ранее такая целевая функция в теории запасов не использовалась, впервые она появилась в работах автора 1996-98 гг. Так как осуществление управления влечет за собой издержки, рассматривается также оптимизация при дополнительных ограничениях. В результате приходится решать задачи линейного программирования и нелинейной оптимизации.

Если возникающие издержки не учитываются, то оптимально использовать управление с одним переключающим уровнем, как показывает

Теорема 2.12. Пусть управление осуществляется бесплатно ( или сумма, выделенная на его осуществление, неограничена). Если величины а,- — 5,-р,-1; I — 0,1, фиксированы и 0 < «о < сц < • ■ • < ¿и-1 < 1 < а^ < ... < а; < со, то оптимально иметь лишь один переключающий уровень щ = [п(1п а;)/(1па;ао')], при этом а(у) = а0 при у < щ, в то время как а (у) = а/ при у > щ; здесь квадратные скобки означают взятие целой части.

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

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

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

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

В первом разделе 3.1 дается постановка задачи и вводятся понятия асимптотически оптимальной и стационарной политик. В разделах 3.2, 3.5 и 3.6 рассматриваются новые модели управления запасами с периодической проверкой уровня запасов, обобщающие предложенные автором в работах 1967г. и 1981 г., а также работы B.Lakdere, B.T.Zaid, E.Ignall, A.Veiriott-, H.Kaspi, D.Perry и проводится анализ устойчивости оптимального поведения. А именно, исследуется оптимальное поведение в моделях с несколькими поставщиками, со случайной доставкой заказов, модели со скоропортящимися продуктами и с взаимозаменяемыми продуктами.

Например, в модели с двумя поставщиками, если начальный уровень запасов равен х, то минимальные средние издержки fn{x) за тг периодов удовлетворяют рекуррентному соотношению

fn(x) = -CiX+ min Gn(u,v), (9)

u>v>x

где

Gn{u,v) = c2{u) + ci{v) - C2(v) + I(u) + E/n_i(ti - fr),

L(v) = E[A(u-fr)++p(fr-u)+], a+ = max(o,0), (10)

функции ci, c-2, hup описывают учитываемые издержки, fr - случайный размер спроса за первый период (с функцией распределения F). Значения и и V, на которых достигается минимум в правой части (9), задают оптимальное поведение на первом шаге n-шагового процесса следующим образом: размер заказа у первого поставщик zi(x,n) равен v — x, размер заказа у второго zz{x,n) равен и — v. Обозначим через Нп и Кп частные производные функции Gn(u,v) соответственно по и и v. Как видно из (10), Нп и Л'„ это функции одной переменной и Кп не зависит от п. Положим Tn(t) = Hn(t) -f K„(t) и ß = p/{p + h). Далее, пусть а = cj — c^,

Рк* это ¿-кратная свертка а Ъ удовлетворяет уравнению Кп(ь) — 0. В предположении о линейности С1(-) и с-^(-) (платы за заказы) имеет место следующий результат.

Теорема 3.1. Оптимальная политика имеет вид:

A. Если а < 0, (/ - 1 )р < С[ < 1р, I > 1, то

гх(х, п) = п) — О при п < I,

21 (я, га) = (£п — з;)+, г2(х,п) = 0 при п>1. (11)

Параметры 1п, однозначно определяемые соотношениями Тп(<п) = 0, п > I, образуют ограниченную неубывающую последовательность. Ее предел ? удовлетворяет условию = ¡3.

B. Если 0 < а < р, {I - 1)р < С] < 1р, I > 1, тс? < (т - 1)сь т > 2, (тем самым т > I и и„ > V при п > т), то

г\(х, п) = 22(х,п) при п < I,

¿\{х,п) = (у — а-)4. г%(х,п) = тт{(и„ - й),(и„ - х)+} при п > т.

(12)

Параметры ип, однозначно определяемые соотношениями II п (и„) = 0. п > т, образуют ограниченную неубывающую последовательность. Ее предел й - единственное решение уравнения Ь(и) = 0, где

Ци) =-а + (а-р)Г(и - V) + {р+Н) / Г(и - б)сЩб),

о

При I < п <т оптимальное поведение может иметь вид (11) или (12). но если при некотором щ оно имеет вид (11), то же самое верно при I <п < щ.

C. Если а > р, (к - 2)р < Сч < (к - 1)р, к > 2, то

z^(x,n) = ¿2{х,п) при п<к\

г\(х,п) = 0, 22{х,п) = (и„ - х)+ при п > к.

Параметры ип, однозначно определяемые соотношениями Н„(и„) = 0. образуют ограниченную неубывающую последовательность. Ее предел й удовлетворяет условию Р2*(й) = /?.

Характерной особенностью полученного оптимального поведения является его пороговый характер.

Если рассматривать будущие издержки со скидкой, то уравнение для минимальных средних издержек /£(х):

№) = min [С1(у - х) +с2(и -у) + L(y) + * F{u)}. (13)

Справедливо следующее утверждение.

Теорема 3.14. 1. Пусть р > с\(0) > с2( 1 + а)/а, с'1оо > р + с2, тогда при любом п оптимальное значение у®(х) равно уп(х), определенному в теореме 3.12.

При п = 1 имеем иЦх) = ?/?(£)•

При п > 2 существуют такие постоянные йп, образующие возрастающую последовательность, что

Существует Jim^w® = иа, являющийся решением уравнения Da(u) — О, где

Если р + с2 > ci(0) > тах(р,с2(1 + а)/а), с'1оо > р + с2, то и? (я) = = х, при п > 2 оптимальное поведение такое же. как указано

выше.

2. Для любого 0 < а < 1, если выполнены условия п. 1, существует.

и>у>х

и°(х) = пра х' < и,", и„(х) = :г при х >

,а и'

О

Ci{y(x) - a:) + с2(йа - у(х)) + L{y{x)) fa(x) = с2(йа - i} + L(i) + аЛ'о, L{x) + afa*F(x),

+ аЛ'а х < х,

X < х < йа, X > йа,

с2 J s(p(s) ds + j L(ua — s)(p(sds)+

ос- ос

+ / Цу{йа -з))у{з)(18+ / С1(у(йа-5)- (йа- *))<р{8)<18+

йа—х йа—х

й"-х )

Сходимость равномерна на полупрямой х < М.

Как показано в теоремах 3.12-3.14, предположение о выпуклости платы за заказ у первого поставщика приводит к существенному изменению оптимального поведения. Размер производимого у него заказа определяется уже не одним, а двумя параметрами, причем, когда уровень запасов меньше нижнего порога х, производится заказ фиксированного размера, при х > х не заказывается ничего, а для ж, лежащих в промежутке (х, х), размер заказа монотонно убывает с ростом х. Таким образом, получившийся результат также отличается от всесторонне изученной классической (§, 5)-политики, где заказ размера 5 — х делается при х < 5, а при х > 8 не заказывается ничего.

Наибольший интерес в этой главе представляют разделы 3.3 и 3.4. В первом из них устанавливается асимптотическая оптимальность стационарной двухпараметрической (й,г))-политики (теорема 3.2). Важная особенность стационарной политики заключается в том, что нет необходимости, во-первых, производить трудоемкие, даже при малом горизонте планирования, вычисления по рекуррентному определению параметров оптимальной политики, а, во-вторых, заранее фиксировать горизонт планирования. Асимптотическая оптимальность политики означает, что ^ш^п^/Л-1') = п1ип п_1/„(х), где /„(х) - средние издержки за п периодов при использовании (й, г>)-политики, а /„(х) - минимальные средние издержки за тот же срок.

В разделе 3.4 демонстрируется предложенный автором метод построения асимптотически оптимальных политик при неизвестном распределении спроса. Преимущество этих политик, основанных на эмпирических функциях распределения и их непрерывных аналогах, состоит в том. что они стационарны, т.е. при продлении срока функционирования системы, а значит, и появлении новых наблюдений, значения параметров лишь уточняются. Доказательство основной теоремы 3.4 разделено на 7 лемм. Исследовано также предельное поведение случайных издержек, а не только их средних, при использовании введенных политик.

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

Глава 4 "Модели с непрерывным временем" разделена на 5 параграфов. Первые два изучают управляемые модели водохранилища с одно-и двухуровневым управлением. Раздел 4.1 исследует предельное при t —> оо поведение модели, предложенной M.J.Faddy. В разделе 4.2 содержится разработанное автором обобщение изучавшихся ранее моделей (M.J.Faddy, F.A.Attia, R.J.Brockwell, D.Zuckerman и др.). Следует отметить тот факт, что рассматриваемые процессы Z(t) не являются марковскими. Однако наличие управления делает их регенерирующими процессами с запаздыванием. Это позволяет найти явный вид предельного распределения.

Теорема 4.2. У процесса Z(t) существует предельное распределе ние Р(В) следующий вид

lim Рt{B), обладающее плотностью р(х), которая имеет

t—>оо

р{ х) =

где

для 0 < х < с,

для с < х < Ь, для Ь < х < а, (14)

5 = Е(02-75) + Е(Г2-01)

и для I > 2

т - ъ) =

о

М-ц

Е(г, - 0,_х) =

2 (М - (if Ь-с

Ц 2/Х2

случайные величины 9i, ц, I > 1, задаются следующим образом

<?0 = 0, ц = inf{i > : 2T(f) = 6}, = inf{i > г; : Z(t) = с}.

(15)

(16)

(Формулы (14)-(16) выписаны в предположении ц ф О, М — ц ф О, в противном случае очевидные изменения получаются предельным переходом.)

При доказательстве основной теоремы 4.2 о существовании стационарного распределения рассматриваемого управляемого случайного процесса Z(t) используется известная теорема Смита, утверждающая, что для апериодического регенерирующего процесса с запаздыванием су-

оо

ществует limP(Z(i) е В) = (E(0j - fy-i)) f Ф.в(<) dt, если функции

Я>в(1) = Р(Z(9i + t) 6 В,в{ — 0i-\ > t) непосредственно интегрируема по Риману и P(#i < оо) = 1, здесь 0/, I > 1, - точки регенерации. Для проверки выполнения ее предположений и нахождения явного вида предельного распределения широко используется тот факт, что период регенерации состоит из двух частей, на первой из которых процесс совпадает с марковским процессом Z\(t), а на второй соответственно с Z%(t), с одной отражающей и одной поглощающей границей. Благодаря этому

со оо 2

удается установить, что можно записать J i>s(t)dt= f £ В) dt.

о о i=l

где Pi(x,t, В) - переходная функция процесса Zi(t) . Здесь xi = с, = 6 (О < с < b < а) - это параметры используемого управления, а - объем водохранилища.

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

Следствие 4.3. Для любого п > 1 существует такал константа с„, что V(Pt,P) < cnt~n, где V - это расстояние по вариации между распределениями Pt и Р.

Как показано в разделе 4.3, изученные в предыдущих разделах процессы с непрерывным временем являются предельными для соответствующим образом нормированных процессов с дискретным временем, изучавшихся в предыдущих главах (теоремы 4.5 и 4.6). Более точно, в данном разделе доказываются функциональные предельные теоремы, следуя подходу, заложенному в классической работе Ю.В.Прохорова 1956 г. В данном случае удобно работать со ступенчатыми функциями, т.е. дей-

ствовать в пространстве Скорохода D[0,oo).

Чтобы сформулировать один из полученных результатов, предположим, что и Две серии случайных величин, а

Znk = тт(ау/п, (Z„,fc-i + Х„к)+), ¿„о = О,

где

X = I ДЛЯ - к < '

" \ для Тп, <к< вп1

и

0no = O, t„i = inf{Jc > : Znk = ау^г},

= inf{/c > г„, : ¿„t = 0}, I > 1.

С точки зрения теории запасов - чистое пополнение запасов в к-й период в н-й системе, а^/п - ее емкость, характер пополнения (или потребления) меняется при опустошении и переполнении.

Теорема 4.4. Пусть {А^'}*•>! и {Х$}к>i - две последовательности независимых одинаково распределенных случайных величин с ЕА^ = ЕЛ'$ = (ц - М)п~1!2, DA',',2 = о2, i = 1,2. Пусть, далее, для каждой из серий i = 1,2, выполняется условие Линдеберга, то-

гда Zn => Z при п —> оо. Здесь Zn(t) = n~l^Zn{nt), a Zn(t) = для k < t < k + 1, k > Q. Предельный процесс Z(t) - это процесс, рассмотренный в теореме 4.2, г/ которого положено Ь = о, с = 0.

В разделе 4.4 изучаются системы производства-хранения в условиях большой нагрузки. Понятие большой нагрузки (heavy traffic) появилось впервые в теории массового обслуживания. Применив общие теоремы об инвариантности предельного распределения функционалов от случайных ломаных при диффузионном характере предельного процесса, в 1963г. Ю.В.Прохоров исследовал предельное поведение распределения длительности ожидания n-го требования при р 1 и п 4 оо - нагрузка), тем самым заложив основы диффузионной аппроксимации. Среди появившихся в 60-е годы работ, исследовавших системы массового обслуживания в условиях большой нагрузки, интересно отметить работы D.Iglehart'a и N.U.Prabhu, которые, как и J.Kingman, в тот же период активно занимались и теорией запасов. Однако в теории запасов в то время доминировал стоимостной подход либо вероятностный

анализ поведения системы при заданном управлении, а интерес к диффузионной аппроксимации появился позднее (см., напр., работы автора 1986-91 гг.).

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

Сформулируем наиболее простой результат для гибкой системы. Пусть потребители г-го класса прибывают в соответствии с пуассоновским потоком интенсивности А- , а времена их обслуживания распределены показательно с параметром г = 1,2, номер системы п соответствует числу обслуживающих приборов. Предположим, что /4™' — ц,, а А-"' = пц{р\"\ Условия большой нагрузки имеют следующий вид

р\п] = - а^-1'2, ¿ = 1,2, Р1 + Р2 = 1, (17)

где р{ и а,- положительны.

Рассмотрим нормированный двумерный марковский процесс =

(Л), Л)), где Л) = (^(0 ~пр!п))п-1/2> »" = 1,2, а - число

клиентов класса г в гг-й системе в момент t.

Теорема 4.8. В предположениях (17) нормированные процессы сходятся по распределению к диффузионному процессу т?(<) с инфините-зималъным оператором

в = - + рт-щ - т П1ш(х2, ах + а2 - х»)^.

Диффузионные приближения для многопродуктовых систем получены как в предположении о фиксированной, так и гибкой структуре (теоремы 4.9-4.11).

В разделе 4.5 производится анализ динамики развития системы произво ства-хранения в предположении, что ее функционирование описывается

стохастическим дифференциальным уравнением вида

dX(t) = a(t.)X(t)dt + <r(t)X(t)dW{t), (18)

где X(t) = X(t,oj) - уровень запасов в момент t и W(t) = W{t,u>) - это стандартный винеровский процесс на [0, оо) х Эта модель естественным образом возникает, если считать, что коэффициент а(-) обыкновенного дифференциального уравнения dX(t)fdt — a(i)X(t), являющегося отправным пунктом исследования во многих экономических моделях . возмущается белым шумом. Формализация, основанная на переходе к стохастическому уравнению Ито представляется желательной, так как позволяет исследовать весьма хаотические флуктуации изучаемых процессов. При этом решаются задачи, связаные с достижением процессом критического уровня. Предположим, что имеется некоторая "критическая" неслучайная кривая Xc(t), которую, в зависимости от постановки задачи, в идеале, должен или не должен достигнуть процесс X(t) на отрезке [О,Г]. Например, если X(t) это вложение в запасы, то необходимо оставаться в рамках выделенных ассигнований. С другой стороны, если X(t) - это уровень запасов при заданном управлении, то желательно избежать опустошения или переполнения и/или максимизировать некоторый функционал, характеризующий эффективность функционирования системы (например, долю времени, проведенную над или под кривой Л'с(£) и др.).

Основное внимание уделяется исследованию устойчивости стохастически возмущенной модели. В частности, подсчет вероятности выхода за время от 0 до Т на кривую Xc{t) позволяет установить допустимые колебания коэффициента а2{-) в уравнении (18), приводящие к выходу за время Т на уровень АХ(0) с вероятностью не меньшей 1-е.

Обозначим

rc = mi{t:X(t) = Xc(t)}. (19)

Удобно записать Xc{t) = А(£)Х(0), где А(-) > 1 - некоторая функция, выбираемая из экономических соображений с учетом общего распределения приоритетов вложений и ожидаемого эффекта. Обратимся к той модельной ситуации, когда удается найти точные, а не приближенные формулы. Пусть коэффициенты уравнения постоянны a(t) = ад, a(t) = оо, a Xc(t) = АоХ(О). Так как щ и Ао обычно определяются экономическими соображеиями, необходимо установить для любого б € (0,1)

область изменения сто, чтобы выполнялось следующее соотношение

Р(ге <Т)> 1-е, (20)

где тс было определено (19). Соотношение (20) очевидным образом означает, что с вероятностью Р(<т$,Т) = Р(гс < Т), большей или равной 1-е, процесс Х(1) достигает критического уровня Хс(1) на отрезке [0,Т].

Теорема 4.13. 1) При Т = оо и ао > 0 соотношение (20) верно для всехс7о > 0, если е € [1—Лд1,1]. Если жее < 1—Ад"1, то (20) справедливо лишь при 0 < а0 < >Дао(1 + (Ц1 - е))/(1п Ао))~1/2.

2) При Т = оо и ао < 0 имеем Р(сто, оо) < Ад1 для всехоо > 0. Еслие £ [1 — АЗ"1,1], то (20) выполнено для <т0 > \Л-2ао((1п(1-е))/(1п Ад 1)-1)~1/2.

Поскольку скорость сходимости Р(о"о-. Т) к Рао,оо) при Г —> оо высока, для больших Т качественная картина возможных колебаний параметра од, обеспечивающих выполнение (20), будет похожа на то, что происходит при Т — оо. Точные границы области, задаваемой соотношением (20) дает следствие 4.7.

Список основных публикаций по теме диссертации

[1] Е.В.Булинская. Оптимальный контроль и устойчивость некоторых систем// Теория вероятн. и ее примен. - 1997. - т.42, в.2. - с.386-387.

[2] Е.В.Булинская. Предельные теоремы для моментов остановки случайных блужданий в полосе// Фундаментальная и прикладная математика- 1996.- т.2, N 4.-С.977-997.

[3] Е.В.Булинская. О пересечении высокого уровня некоторым классом случайных процессов с дискретным временем// Фундаментальная и прикладная математика.- 1995.-т.1,М 1.-С.81-107.

[4] Е.В.Булинская. Предельные теоремы для больших систем производства-хранения// Теория вероятн. и ее примен. - 1991. - т.36, в.4. - с.779-780.

[5] Е.В.Булинская. О построении асимптотически оптимальных политик/ в сб.: Проблемы устойчивости стохастических моделей. Труды семинара. М.:ВНИИСИ - 1989. - с.10-19.

[6] Е.В.Булинская. Об одной модели теории водохранилищ// в сб.: Проблемы устойчивости стохастических моделей. Труды семинара. М.:ВНИИСИ. - 1984, с.34-39.

[7] Е.В.Булинская. Проблемы непрерывности в теории запасов// Теория вероятн. и ее примен. - 1983. - т.29, в.4. - с.807-808.

[8] Е.В.Булинская. Многопродуктовые модели с взаимозаменяемыми продуктами./в сб. Теория массового обслуживания. Труды семинара,- М.:ВНИИСИ, 1981, с.122-127.

[9] Е.В.Булинская. Теория запасов/ в сб.: Труды школы-семинара по массовому обслуживанию, Пущино, 1974. М.:Изд.МГУ, 1976, с.17-41.

10] Е.В.Булинская Оптимальное управление запасами в случае выпуклой платы за заказ// Теория вероятн. и ее примен. - 1967. -т.12, в.1. - с.11-23.

11] E.V.Bulinskaya Systems stability and optimal control// J.Math.Sci. -1998. - v.92,N2. - p.12-28.

12] E.V.Bulinskaya. Multi-level control and asymptotic behaviour of some inventory systems// Int.J.Prod.Economics. - 1998. - v.57 - p.248-256.

13] E.V.Bulinskaya. Stability problems in inventory theory// Int.J. Prod. Economics. - 1996. - v.45 - p.353-359.

14] E.V.Bulinskaya. Inventory models with random supply. Asymptotic-analysis and optimization/ in: Operations Research Proceedings 1995, P.Kleinschmidt et al. (eds.)Springer, Berlin, Heidelberg, 1996, p.451-456.

[15] E.V.Bulinskaya.Reliability of some inventory-production systems// Int. J. Prod. Economics. - 1994. - v.35. - p.245-251.

116] E.V.Bulinskaya. Heavy-traffic inventory-production systems//Int.J. Prod.Economics.-1992.-v.26.-p.283-291.

[17] E.V.Bulinskaya. Inventory control in case of unknown demand distribution// Engineering Costs and Prod. Economics.-1990.-v.l9.-p.301-306.

[18] E.Bulinskaja. Lagerhaltung bei unbekannter Nachfrageverteilung./ in: H.J.Girlich (ed.), Sitzungsbericht 1989, Konferenz Lagerhaltung Systeme und Logistik, 26-29 Juni, S.75-89.

[19] E.V.Bulinskaya. Functional limit theorems for some inventory models/ in: A.Chikan (ed.) Progress in inventory research.-Akademiai Kiado, Budapest, Hungary, 1989. - p.323-328.

[20] E.V.Bulinskaya Limit theorems for stochastic inventory models/ in: Probab. Theory and Math. Stat., Yu.V.Prohorov et al. (eds.) 1986. VNU Science Press, v.l, p.291-306.

[21] E.Bulinszkaja. Egyes keszletgazdlkodasi rendszerek aszimptotikus viselkedesi tulajdonasi/ in: A.Chikan (ed.) Keszletek az elmeletben es a gyakorlatban, Budapest, 1985, p.3l-57.

[22] E.Bulinskaja. Methoden der Bedienungstheorie in der Lagerhaltungstheorie/ in: H.Girlich (ed.) IG Lagerhaltungsmodelle, 1984, S.9-15.



московский государственный университет

имени М.В. ЛОМОНОСОВА

резид;;ум ВАК, Росс^ш' 1

(решение от » ¿Г " сМЛ г ^

присудил учеьук, степей ДОКТОМ

I На правах рукописи УДК 519.21

Начальник упштм

ра»лени* ВАК Р#сс*Г

/1 /О,

? (

булинская екатерина вадимовна

СТОХАСТИЧЕСКИЕ МОДЕЛИ ТЕОРИИ ЗАПАСОВ

специальность 01.01.05 теория вероятностей и математическая статистика

диссертация

на соискание ученой степени доктора физико-математических наук

Москва 1998

Оглавление

введение 3

1 СЛУЧАЙНО ВОЗМУЩЕННЫЕ СИСТЕМЫ С СИНХРОНИЗАЦИЕЙ ПОСТАВОК И ПОТРЕБЛЕНИЯ 34

1.1 Описание основной модели и некоторые вспомогательные результаты........................................................34

1.2 Асимптотическое поведение момента остановки процесса, описывающего возмущенную систему..........................44

1.3 Модель с дефицитом ............................................50

1.4 Модель с экстренными поставками............................56

1.5 Проблема неустойчивости исходной модели..................59

1.6 Дважды стохастические системы..............................73

1.7 Надежность системы и выбор оптимальных параметров . . 80

1.8 Оптимизация системы в стационарном режиме..............85

2 УПРАВЛЯЕМЫЕ СИСТЕМЫ И ОПТИМИЗАЦИЯ 113

2.1 Определение управляемой системы..............113

2.2 Двухуровневое управление в модели с экстренными поставками ................................116

2.3 Двухуровневое управление в модели с остановкой......132

2.4 Многоуровневые управления и устойчивость системы . . . 143

2.5 Оптимальное управление....................159

3 МОДЕЛИ СО СЛУЧАЙНЫМ СПРОСОМ (ДИСКРЕТ-

НОЕ ВРЕМЯ) 167

3.1 Постановка задачи .......................167

3.2 Оптимальное управление при известном распределении спроса170

3.3 Устойчивость стационарной (й, ¿^-политики.........173

3.4 Асимптотически оптимальные политики при неизвестном распределении спроса......................177

3.5 Анализ устойчивости оптимального управления.......182

3.6 Модели с взаимозаменяемыми продуктами..........195

4 МОДЕЛИ С НЕПРЕРЫВНЫМ ВРЕМЕНЕМ 203

4.1 Управляемая модель с одним переключением ........203

4.2 Управляемая модель с двумя переключениями........211

4.3 Приближение процессов с дискретным временем процессами с непрерывным.......................216

4.4 Системы производства-хранения в условиях большой нагрузки ...............................222

4.5 Анализ динамики развития системы производства-хранения 237

ЛИТЕРАТУРА 247

СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ 265

ВВЕДЕНИЕ

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

Возникновение современной теории запасов обычно связывается с появлением в 1951г. работы Arrow, Harris, Marschak [68], а затем в 195253гг. трех работ Dvoretzky, Kiefer, Wolfowitz [102, 103]. В них были четко сформулированы основные математические проблемы, описаны важные модели, указаны факторы, влияющие на принятие решений, и предложены подходы к учету неопределенности спроса. Точнее говоря, в них были заложены основы стоимостного подхода в теории запасов.

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

Интересно отметить, что впервые задача управления запасами (применительно к определению резервных денежных фондов) была математически сформулирована в 1888г. в работе Edgeworth [106].

Первым обзором по теории запасов была книга Raymond [180], вышедшая в 1931г. Однако она не содержала никаких теоретических разработок, касавшихся характера оптимальных политик управления запасами, а давала некоторые практические указания по поводу применения EOQ-

формулы (наиболее экономичного размера заказа). В англоязычной литературе соответствующая модель носит название формулы Wilson'a, который ввел ее в 1934г. [212], независимо от своих предшественников. Аналогичный результат получил в 1915г. Harris [118]. А в немецкой литературе первенство в ее открытии приписывается работам Andler [67] 1929г., Marganinsky [154] 1933г. или Steffanic-Allmayer [202] 1927г.

Формула Wilson'a для своего вывода требует элементарных знаний из области математического анализа, однако содержит результат, который часто далеко не очевиден практикам. Пусть известен размер спроса в единицу времени, равный S. Дефицит не допускается, доставка пополнения немедленная, стоимость доставки заказанной партии равна К. Расходование запасов идет с постоянной скоростью, а плата за хранение единицы продукта единицу времени равна h. Необходимо выбрать размер доставляемой партии Q (или, что то же самое, частоту поставок), чтобы минимизировать суммарные издержки в предположении, что стоимость заказываемого продукта с течением времени не меняется. Оптимальным оказывается значение

Q* = V2KShrl. (0.1)

Эта простая широко известная модель послужила основой для многих исследований и, что самое интересное, продолжает изучаться и обобщаться и до сих пор (см., напр., [169, 182, 94, 207]).

Другая простая модель, уже стохастическая, появилась в годы второй мировой войны в работах Morse и Kimbel по исследованию операций и стала доступна широкой научной общественности лишь в 1951г. [162]. Она носит название модели продавца газет, или продавца рождественских елок, и интерес к ней также не пропал до сих пор [170]. И хотя она всегда традиционно приводится как пример принятия решения в условиях неопределенности и относится к исследованию операций, но по своей природе это типичная статическая модель теории запасов.

Здесь предполагается, что спрос на запасаемый продукт - это случайная величина £ с известным распределением. Известна также цена покупки В и продажи V, неиспользованный продукт пропадает. В качестве функционала, который надо максимизировать, рассматривается полученный средний доход УЕ min((2, £) — BQ, если приобретена заранее партия размера Q. Эта модель является первым шагом при рассмотрении динамических моделей, которые стали интенсивно развиваться

после выхода в 1955г. работы Bellman, Glicksberg, Gross [75], а также последующих работ Беллмана и особенно благодаря созданному им динамическому программированию [9]. Особое внимание в этот период уделяется поиску условий, при которых оптимальна политика, зависящая лишь от одного критического параметра х (если уровень запасов становится ниже ж, то происходит пополнение до этого уровня, превышение х влечет отсутствие заказов).

Работы по теории запасов (inventory theory) регулярно печатаются в таких журналах, как Management Science, Journal of Applied Probability, Opérations Research, Journal of Industrial Engineering, SIAM Journal, Unternehmensforschung, Revue Française de la Recherche Opérationnelle, Spectrum, Econometrica, Harvard Business Review, International Journal of Production Economies и многих других.

Глубокий математический анализ задач управления запасами был проведен в сборниках статей, изданных Стэнфордским университетом в 1958 и 1962 гг. под редакцией Arrow, Karlin, Scarf [69, 70]. Здесь содержались также и работы, касающиеся регулирования запасов воды в гидроэнергетике. Это направление, получившее в англоязычной литературе название storage theory или dam theory (которое на русский язык переводится как теория хранения или теория водохранилищ), также интенсивно развивается в 50-е годы в работах Могап [161], Gani [109], Prabhu [46, 45] и др. (см., напр. [132]). Для исследований этого направления характерно изучение переходного и установившегося режима в системах, где приток воды случаен, а выпуск производится по некоторому заданному правилу. Этим они отличаются от работ первого направления, связанного с производством, где случаен спрос, а поставки надо производить так, чтобы минимизировать возникающие средние издержки. Первые оптимизационные работы в теории водохранилищ появились в 70-е годы и принадлежат Faddy, Zuckerman, Attia, Brockwell, и другим (см., напр., [107, 219, 72, 214, 218]).

В нашей стране первыми математическими работами по теории запасов были статьи автора диссертации, опубликованные в журнале "Теория вероятностей и ее применения" в 1964г., и кандидатская диссертация "Некоторые задачи оптимального управления запасами" (МГУ, 1965г.), развивавшие далее стоимостной подход. В 1969г. появилась книга Ры-жикова [52], далее книги Рубальского [51], Первозванского [40], Петра-

кова, Ротаря [41] и др., многие статьи отечественных авторов, а также переводы на русский язык монографий Buchan, Koenigsberg [15], Hanss-man [62], Wight [57] и ряда других. В 1970 и 1972гг. ЦЭМИ АН СССР проводит Всесоюзные конференции по теории запасов. В Германии в конце 60-х годов появляются книги Klemm, Mikut [145], Girlich [112], Hochstädter [120] и Popp [174], с тех пор в этой области активно работают исследователи школы Girlich'a.

С появлением в 1964г. работы Ргёкора [178], а затем Zirmann, Horvath [121] связано возникновение и развитие надежностного подхода в теории запасов. В то время как стоимостной подход стремится свести к минимуму издержки, существуют ситуации, когда такой подход неприменим. Например, недостаток топлива у самолета или крови для переливания больному может привести к гибели людей, а это не следует оценивать лишь с помощью возникающих издержек. Здесь необходим другой критерий качества функционирования системы - ее надежность. Этот подход оказался очень плодотворным в связи с фундаментальными результатами, полученными в работах Гнеденко, Соловьева, Коваленко, Каштанова, Беляева, их коллег и учеников (см., напр., [20]).

В 70-е годы снова усиливается интерес к детерминированным моделям теории запасов, при этом центр тяжести перемещается в область централизованного планирования производственных процессов и запасов сырья или полуфабрикатов. Если раньше речь шла о наиболее рациональном выборе уровня запасов, то теперь доминирует желание иметь их как можно меньше, а лучше всего не иметь вообще. В 1975г. выходит книга Orlicky "Material Requirement Planning" [167], посвященная этим проблемам. Еще раньше, в 50-е годы, вопросами организации производства стали заниматься в Японии. Сначала соответствующий подход был разработан компанией Toyota, а затем он широко распространился и на другие компании, в особенности после нефтяного кризиса 1973г. В этой связи можно отметить работы Ohno [165] , 1982г., Suzaki [204], 1985г., а также Shingo [195], 1989г.

Их исследования заложили основу нового подхода - синхронизации процессов поставки и потребления, который по-английски называется just-in-time ( или сокращенно JIT). Как уже было сказано, цель этого подхода - сократить уровень запасов (или в идеале вообще избежать хранения), тем самым значительно уменьшив издержки.

Разработанная в Японии система получила название Kanban. Это также планирование производства, но менее централизованное. С конца 70-х годов идеи уменьшения запасов начинают распространяться на США и Западную Европу. Среди таких компаний, которые начали использовать подход JIT, можно указать General Electric, Hewlett Packard, IBM, Xerox и др., о чем написано, например, в статьях Schönberger, Ansari [188], Schönberger, Schniederjans [190], Sepehri, Walleigh [193].

К 80-м годам относится появление более 1000 работ в журналах, а также первых книг и обзоров по системам JIT, среди них Hall [117], Monden [160], Jordan [134], Deming [97], Ryan [179], Schönberger [187], Groen-velt, Karmarkar [115]. Происходит изучение различных аспектов систем JIT (к которым относятся MRP и Kanban [76, 84, 213, 155]), начиная с отчетов об успешной организации работы на отдельных предприятиях или в цехах и моделирования с помощью компьютеров [105, 110, 122, 191], кончая статьями об оптимизации параметров рассматриваемых производственных систем [108, 131, 168, 150, 216]. В 1989г. Buzacott сравнивает между собой системы Kanban и MRP, моделируя их как сети массового обслуживания [86]. Однако в подавляющем большинстве этих работ все процессы считаются детерминированными и внимание сосредоточено на улучшении организации труда и создании заинтересованности персонала в конечном результате [95, 136, 137, 203, 211], контроле качества [205, 206, 179, 193] и многих других интересных и важных сторонах рассматриваемого подхода (см. [82, 83, 77, 71, 79, 80, 81, 85, 90, 91, 92, 98, 129, 155, 156, 189, 198]).

В частности, снова проводится исследование модели EOQ. Традиционно в учебниках по теории запасов (см., напр., Нах, Candea [119]) указывалось, что как оптимальный размер заказа Q*, задаваемый формулой (0.1), так и минимальные издержки С* = л/2KhS, нечувствительны к малым изменениям параметров К и h. Поэтому в применениях величина К постоянных издержек на организацию производства партии размера Q (или ее доставку) считалась фиксированной. Однако Porteus в [175] рассматривает возможность инвестиций в сокращение издержек К и производит одновременную оптимизацию К и Q. Zangwill [215] рассмотрел инвестиции в сокращение фиксированных издержек в динамической модели EOQ, предложенной в 1958г. Wagner, Whitin [209]. В работе Schönberger, Schniederjans [190] доказано, что при "правиль-

ной организации" доставки и хранения оптимальное Q* равно единице. Имеется лишь небольшое количество работ, где содержится критика систем JIT или делаются попытки учесть случайные возмущения. К ним относятся, например, работы Mitra, Mitrani [157, 158], Buzacott [86] и др. [110, 111]. В статье 1991г. Zipkin [217] пишет, что не следует идеализировать системы JIT, поскольку для реального сокращения запасов потребуются огромные капиталовложения на реорганизацию производства, а без этого сокращение запасов нанесет лишь вред. Об опасности слепого копирования японских систем JIT говорит и Moyes [163], который считает, что отсутствие буферов в виде запасов способствует дестабилизации экономики. Эти опасения частично подтвердились во время землетрясения 1995г. в Кобе, когда, вследствие разрушения коммуникаций и невозможности поставок, производство остановилось из-за отсутствия запасов.

Подводя итоги краткого исторического обзора, можно отметить, что до середины 60-х годов основную роль при выборе политики регулирования запасов играл стоимостной подход. Он означает, что при фиксированном горизонте планирования Т для оценки качества функционирования системы рассматриваются средние суммарные издержки Ст-Если горизонт планирования неограничен, то в качестве целевой функции рассматриваются дисконтированные ожидаемые издержки или же средние издержки в единицу времени при длительном функционировании системы (более точно, рассматривается lim (1 /Т)£у, подробнее см.,

Т-> оо

например, [44]).

При надежностном подходе в качестве целевой функции выступают вероятности опустошения и/или переполнения, средний размер дефицита и другие характеристики системы. В то время как при стоимостном подходе часто оказывалось возможным находить оптимальную политику, обеспечивающую достижение экстремума целевой функции, добиться "полной надежности", скажем, бездефицитной работы, практически никогда не удается. В результате возникает понятие е-оптимальной политики, которая обеспечивает отклонение целевой функции от ее экстремума не более чем на е. Это направление в теории запасов было инициировано работами автора диссертации, выполненными в 1976г.

Широкое распространение в 80-е годы систем JIT означало новый взгляд на роль запасов в производстве, при этом упор делался на плани-

рование и организацию производства и снабжения, а "целью" становилась ликвидация запасов.

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

Стохастические процессы с дискретным временем, предложенные автором в работах 1990-98гг. для описания случайно возмущенных систем с синхронизацией поставок и потребления, позволили глубоко проникнуть в природу таких систем. В современной теории вероятностей большой интерес представляют проблемы, связанные с устойчивостью тех или иных моделей. Даже классическая теорема Пуассона излагается в книге Ширяева [64] с оценкой по вариации отклонения распределения сумм независимых слагаемых (со значениями 0 и 1) от соответствующего пуассоновского закона.

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

Разработан новый для теории запасов подход к выбору оптимального управления. Здесь в качестве функционала, характеризующего систему, выбирается средняя длительность ее бесперебойной р�