автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Динамические модели систем управления запасами с интервальной неопределенностью в данных

Введение

1 Элементы интервального анализа

1.1 Классическая интервальная арифметика

1.2 Полная интервальная арифметика Каухера.

2 Интервальные модели размера партии с непрерывным контролем

2.1 Модель управления запасами с интервально заданными ин-тенсивностями спроса и поставок и возможностью дефицита: пороговая стратегия.

2.2 Частные случаи

2.2.1 Модель с интервально заданными интенсивностями спроса и поставок при отсутствии дефицита

2.2.2 Модель с интервально заданной интенсивностью спроса, мгновенными поставками и возможностью дефицита.

2.2.3 Модель с интервально заданной интенсивностью спроса, мгновенными поставками при отсутствии дефицита.

2.3 Модель управления запасами с интервально заданными интенсивностями спроса и поставок и возможностью дефицита: периодическая стратегия.

2.4 Анализ результатов и численная реализация.

2.5 Выводы.

3 Интервальные модели размера партии с периодическим контролем

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

3.2 Условия существования оптимального решения.

3.3 Определение оптимальной стратегии.

3.4 Пример.

3.5 Нестационарная неопределенность спроса.

3.6 Выводы.

4 Динамические сетевые модели управления запасами с интервально заданным стационарным спросом

4.1 Описание модели и постановка задачи.

4.2 Определение оптимального допустимого уровня запаса в сети

4.3 Определение оптимальной допустимой стратегии управления

4.4 Численная реализация.

4.5 Модель с устареванием запаса в узлах сети.

4.6 Модель с задержками поставок.

4.7 Выводы.

5 Динамические сетевые модели управления запасами с интервально заданным нестационарным спросом

5.1 Описание модели и постановка задачи.

5.2 Определение оптимального допустимого уровня запаса в сети.

5.3 Определение оптимальной допустимой стратегии управления

5.4 Численная реализация.

5.5 Модель с устареванием запаса в узлах сети.

5.6 Выводы.

Проблема управления запасами (inventory control problem) является одной из наиболее важных в организационном управлении. Запасы разного рода материальных ценностей возникают почти во всех звеньях системы производства - распределения - потребления. Под запасом подразумевается не только наличие некоторого товара или продукции на складе [14], но и производственные, транспортные, трудовые, информационные, водные ресурсы, финансовый капитал и т.д. Поэтому модели управления запасами описывают широкий круг задач оптимального планирования производственных, транспортных, информационных, финансовых, водохозяйственных, энергетических и других систем.

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

Возникновение теории управления запасами принято связывать с появившимися в конце XIX - начале XX века работами Ф. Эджуорта, Ф. Харриса и Р. Уилсона, в которых исследовалась простая оптимизационная модель для определения экономичного размера партии поставки (the economic lot size models) для складской системы с детерминированным стационарным спросом. Из ранних работ в этой области следует отметить книги Ю.И. Рыжикова [49], Г. Вагнера [8], Дж. Букана и Э. Кенигсберга, [7], Дж. Хедли и Т. Уайтина [52], Ф. Хэнссменна [54].

В них описаны подходы и методы оптимального управления запасами, которые приобрели характер классических результатов: формулы Уил-сона для детерминированных моделей размера партии и их обобщения; управление запасами при случайном спросе с непрерывном и периодическим контролем уровня запасов; принцип оптимальности Р. Беллмана [6] в динамических моделях управления запасами; управление запасами при случайной задержке поставок и т.д.

В наиболее общем виде объектом исследования теории управления запасами можно считать изображенную на Рисунке 1 складскую систему [37], где штриховыми линиями обозначены информационные, а сплошными - материальные потоки. поставка потребление поставщик складская система потребители w запас заказ ---------- спрос

Рисунок 1: Структура системы управления запасами

Системы управления запасами можно классифицировать по многим признакам:

• вид запасов (сырье, полуфабрикаты, готовая продукция);

• место хранения (производитель, потребитель, база снабжения);

• структура системы (изолированный склад, последовательная или иерархическая система складов, разомкнутая или замкнутая по спросу система);

• способ контроля уровня запасов (непрерывный, периодический);

• цели системы (стоимостные и надежностные критерии, многокри-териальность);

• структура запасов (одно- или многономенклатурные запасы, взаимозаменяемость и дополняемость, изменения количества и качества запасов при хранении);

• характеристики спроса и поставок (стационарность, коррелиро-ванность, управляемость, устойчивость, случайность поставок);

• ограничения (на объем и номенклатуру запасов, на размеры партий поставок, пропускную способность склада, на надежность и экономические характеристики процесса снабжения);

• информационные характеристики (периодичность сбора данных, наблюдаемость спроса, полнота знаний о (стоимостных) коэффициентах потерь) и т.д.

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

Модели управления запасами подразделяют на статические и динамические, одно- и многономенклатурные, с периодическим и непрерывным контролем уровня запасов, конечным и бесконечным периодом планирования, детерминированные и стохастические, стационарные и нестационарные, замкнутые и разомкнутые по спросу, со случайными поставками и временем поставок и другие [50].

Широкий класс систем управления запасами описывается динамическими сетевыми моделями. В качестве примера можно привести системы снабжения, производства-распределения, транспортные, информационные, водохозяйственные и энергетические системы, системы управления инвестициями и денежными потоками и т.д. Узлы сети задают виды и размеры управляемых запасов, а дуги - управляемые и неуправляемые потоки в сети. Управляемые потоки перераспределяют ресурсы между узлами сети, возможно перерабатывая их, и планируют поставки извне. Неуправляемые потоки описывают спрос на ресурсы в узлах сети, который формируется как со стороны других узлов, так и внешнего окружения. Проблеме оптимизации динамических потоков в сети посвящено большое количество работ (см., к примеру, [35,88] и обширную библиографию к этим статьям).

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

• преимущественное развитие стохастических моделей и статистических методов управления запасами [17,18,37,46,47,70,72,83];

• распространение адаптивного подхода и методов управления по неполным данным [12,37,71,98-100];

• исследование игровых постановок задач управления запасами [117,121];

• исследование многономенклатурных систем управления запасами с коррелированным спросом [36-38,85,87,116];

• исследование систем управления запасами с частично наблюдаемым спросом и замкнутых по спросу систем [37],

• исследование иерархических систем управления запасами [82,90, 91,102,118,120].

Ю.И. Рыжиков в книге [48] отмечает, что "управление запасами, с одной стороны, имеет наибольшие возможности для практического применения и с другой - наиболее развитую теорию". Наряду с вероятностными методами и методами линейного программирования теория управления запасами активно использует аппарат теории автоматического управления [37,42,43]. Предлагаются алгоритмы управления запасами, разработанные на основе современных методов теории адаптации, идентификации, стохастической оптимизации, принципа максимума, динамического программирования, марковских процессов с доходами и т.д. Различные математические модели и методы теории управления запасами рассматриваются также в [41,44,92,101,112,113].

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

Интересный подход для динамических сетевых моделей, основанный на концепции "неизвестных, но ограниченных" воздействий [107] (unknown-but-bounded inputs), предлагается в работах Ф. Вланчини, Ф. Ринальди и В. Уковича [73-78]. В них рассматриваются динамические сетевые модели систем управления запасами в предположении, что неизвестный спрос принадлежит заданному множеству. Такой подход приводит к минимаксным игровым постановкам и решениям, обеспечивающим некоторый гарантированный результат в смысле заданного критерия. Авторы [73-78] используют аппарат теории множеств. Однако, теоретико-множественное представление результатов приводит к трудностям при проверке условий существования оптимальных стратегий управления и вычисления их параметров. Кроме того, предложенные в данных работах модели не учитывают возможное устаревание запаса в узлах сети (порча, естественная убыль, моральный износ и т.д.) и нестационарность спроса во времени, например, когда спрос имеет сезонный характер.

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

1) построение и исследование моделей размера партии систем с непрерывным контролем в условиях нестохастической неопределенности спроса и поставок;

2) построение и исследование моделей размера партии систем с периодическим контролем в условиях нестохастической неопределенности спроса;

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

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

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

Исторически интервальный анализ возник как средство учета ошибок вычислений и задач чувствительности. Среди работ в направлении доказательных, надежных вычислений (reliable, validated computing) можно назвать книги Р.Е. Мура [103], Г. Алефельда и Ю. Херцбергера [1], С.А. Калмыкова, Ю.И. Шокина и З.Х. Юлдашева [25] и другие. Однако идеи, положенные в основу интервального анализа, оказались гораздо шире. Выяснилось, что интервальный анализ позволяет эффективно решать задачи с интервальными неопределенностями в данных. В тех случаях, когда относительно факторов неопределенности неизвестно ничего, кроме их свойства быть ограниченными, интервальные подходы и модели более полно отражают характер неопределенности и отвечают широкому классу задач теории автоматического управления, исследования операций, теории принятия решений, теории идентификации и оценивания параметров и ряда смежных дисциплин.

Большой устойчивый спрос на решение подобных задач со стороны практиков привел к интенсивному развитию, как самой теории интервального анализа, так и ее приложений к прикладным практическим задачам. Ю.И. Шокин в книге [68] пишет, что "в последнее время наметились пути использования интервальных методов в задачах управления и экономики". А.П. Вощинин и Г.Р. Сотиров [11] отмечают, что интервальное представление факторов неопределенности "привлекает все большее внимание практиков". В этом же смысле высказываются и другие авторы [13,27].

Современное состояние теории интервального анализа можно оценить по работам С.П. Шарого [60-64,67,108,111], А.В Лакеева [28,29,97], Е. Ка-ухера [93], А. Ноймайера [104], и другим [26,32-34,40,45,59,84,95,96,114]. Предлагаемые интервальные подходы и методы нашли применение в области слежения, управления и стабилизации систем [15,22,24,51,53,65, 66,69,109], транспортных задачах [5,23] и финансовом анализе [2-4,16], эконометрике [106] и других [30,31,39].

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

Методы исследования

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

Основные результаты, полученные в данной работе, следующие.

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

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

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

4) Результаты обобщены на случаи динамических сетевых моделей с интервально заданным стационарным спросом при устаревании запаса в узлах сети и задержках в поставках.

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

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

Теоретическая и практическая ценность

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

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

Результаты диссертационной работы внедрены ООО "Международный центр технологии и торговли" и используются в учебном процессе на факультете прикладной математики и кибернетики Томского государственного университета (акты о внедрении прилагаются).

Структура и объем работы

Настоящая диссертационная работа состоит из введения, основного текста, заключения и списка литературы. Основной текст разбит на 5 глав и содержит 3 таблицы и 15 рисунков. Список литературы включает 121 наименование. Общий объем работы - 147 страниц.

5.6 Выводы

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

1) В терминах полной интервальной арифметики Каухера получены необходимые и достаточные условия существования допустимого управления с обратной связью по состоянию (теорема 5.1);

2) Доказана теорема о виде оптимального допустимого уровня запаса в сети (теорема (5.2));

3) Получены достаточные условия существования оптимальной допустимой стратегии управления запасами с обратной связью (теорема 5.3);

4) Найдена оценка скорости сходимости системы к оптимальному допустимому уровню запаса (формула (5.17));

5) Предложен алгоритм определения оптимальной допустимой стратегии управления (формула (5.27));

6) Показано, что учет нестационарности спроса позволяет существенно уменьшить уровень запаса в системе и, как следствие, затраты на его хранение;

7) Рассмотрена модель, учитывающая устаревание запаса в узлах сети (модель (5.29));

8) Приведены результаты численных расчетов (рисунки 5.2, 5.3).

ЗАКЛЮЧЕНИЕ 131 сти системы к оптимальному допустимому уровню запаса. Вычислительный алгоритм определения оптимальной допустимой стратегии управления.

5) Обобщение динамической сетевой модели с интервально заданным стационарным спросом при устаревании запаса на случай задержек в поставках.

6) Необходимые и достаточные условия существования допустимого управления для динамической сетевой модели управления запасами с интервально заданным нестационарным спросом. Достаточные условия существования оптимальной допустимой стратегии управления. Оценка скорости сходимости системы к оптимальному допустимому уровню запаса. Вычислительный алгоритм определения оптимальной допустимой стратегии.

7) Необходимые и достаточные условия существования допустимого управления для динамической сетевой модели управления запасами с интервально заданным нестационарным спросом при устаревании запаса. Достаточные условия существования оптимальной допустимой стратегии управления. Оценка скорости сходимости системы к оптимальному допустимому уровню запаса. Вычислительный алгоритм определения оптимальной допустимой стратегии управления.

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. - М.: Мир, 1987.

2. Авдеенко С.Н., Домбровский В.В. Анализ инвестиционных проектов в условиях интервальной неопределенности // Вестник Томского государственного университета. 2000. -№ 271. - С. 125-126.

3. Авдеенко С.Н. , Домбровский В.В. Расчет индивидуального пенсионного фонда в условиях интервальной неопределенности // Вычислительные технологии. 2001. - Т. 6, Ч. 2 (спец.выпуск, CD).

4. Авдеенко С.Н., Домбровский В.В. Применение обобщенной интервальной арифметики для анализа финансовых операций // Вычислительные Технологии. 2002. - Т. 7, № 1. - С. 3-14.

5. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях: монография. Тюмень: Издательство Тюменского государственного университета, 2000 (http://www.plink.ru/tnm).

6. Беллман P. Динамическое программирование. М.: ИЛ, I960.

7. Букан Дж., Кенигсберг Э. Научное управление запасами. -М.: Наука, 1967.

8. Вагнер Г. Основы исследования операций. М.: Мир, 1973.

9. Вербицкий В.И., Горбань А.Н., Утюбаев Г.Ш., Шокин

10. Ю.И. Эффект Мура в интервальных пространствах // Доклады АН СССР. 1989. - Т. 304, № 1. - С. 17-22.

11. Вощинин А.П. Метод оптимизации объектов по интервальным моделям целевой функции. М.: МЭИ, 1987.

12. И. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. М.: Изд-во МЭИ; Техника, 1989.

13. Гордиенко Е.И. Адаптивное управление запасами при неизвестном распределении спроса // Известия АН СССР. Техн. кибернетика. 1982. - № 1. - С. 56-60.

14. Грановский В.Г., Сирая Т.Н. Методы обработки экспериментальных данных при измерениях. Ленинград: Энергоатомиздат, 1990.

15. Громенко В.М. Применение методов теории управления запасами в экономических задачах. М.: Московский институт управления, 1981.

16. Домбровский В.В. Интервальные методы в управлении финансами // Труды международной конференции по проблемам управления. Москва: ИПУ РАН, 1999. - Т. 1. - С. 202-209.

17. Домбровский В.В., Чаусова Е.В. Математическая модель управления запасами при случайном сезонном спросе и ненадежных поставщиках // Вестник Томского государственного университета. 2000. - Т. 271. - С. 141-146.

18. Домбровский В.В., Чаусова Е.В. Управление запасами при случайном сезонном спросе и ненадежных поставщиках // Дискретный анализ и исследование операций: Материалы международной конференции. Новосибирск: Издательство института математики, 2000. С. 209.

19. Домбровский В.В., Чаусова Е.В. Применение интервальных методов в управлении запасами // Вычислительные Технологии. -2002. Т. 7, № 2. - С. 50-58.

20. Домбровский В.В., Чаусова Е.В. Динамическая сетевая модель управления запасами с интервальной неопределенностью спроса // Вычислительные Технологии. 2001. - Т. 6, Ч. 2. -С. 271-274 (спец. выпуск, CD).

21. Домбровский В.В., Чаусова Е.В. Управление запасами в условиях интервальной неопределенности // Труды XV конференции по интервальной математике. Новосибирск: ИВТ СО РАН, 2000 (http://www.ict.nsc.ru/ws/showabstract.dhtml! ru+8+418).

22. Захаров A.B., Шокин Ю.И. Синтез систем управления при интервальной неопределенности параметров их математических моделей // Доклады АН СССР. 1988. - Т. 299, № 2. - С. 292-295.

23. Ивлев Р.С., Соколова С.П. Построение векторного управления многомерным интервально заданным объектом // Вычислительные Технологии. 1999. - Т. 4, № 4. - С. 3-13.

24. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, 1986.

25. Карлюк А.Ю. Численный метод нахождения алгебраического решения ИСЛАУ основанный на треугольном расщеплении // Вычислительные Технологии. 1999. - Т. 4, № 4. - С. 14-23.

26. Куржанский А.Б. Задача идентификации теория гарантированных оценок // Автоматика и Телемеханика. - 1991. - № 4. -С. 3-26.

27. Лакеев А.В. Существование и единственность алгебраических решений интервальных линейных систем в полной арифметике Каухера // Вычислительные Технологии. 1999. - Т. 4, Я2 4. - С. 33-44.

28. Лакеев А.В., Носков С.И. О множестве решений линейного уравнения с интервально заданным оператором и правой частью // Доклады РАН. 1993. - Т. 330, № 4. - С. 430-433.

29. Литвинов Г.Л., Маслов В.П., Соболевский А.Н. Идемпотент-ная математика и интервальный анализ // Вычислительные Технологии. 2001. - Т. 6, № 6. - С. 47-70.

30. Литвинов Г.Л., Соболевский А.Н. Точные интервальные решения дискретного уравнения Беллмана и сложность задач интервальной линейной алгебры // Доклады РАН. 2002. - Т. 374, № 3.- С. 304-306.

31. Ловецкий С.Е., Меламед И.И. Динамические потоки в сетях // Автоматика и Телемеханика. 1987. - № 11. - С. 7-29.

32. Лотоцкий В.А. Модели управления запасами при зависимом случайном спросе // Экономика и мат. методы. 1975. - Т. 11, № 4. -С. 789-792.

33. Лотоцкий В.А., Мандель А.С. Модели и методы управления запасами. М.: Наука, 1991.

34. Лотоцкий В.А., Мандель А.С. Модели и методы управления многономенклатурными запасами // Автоматика и Телемеханика.- 1979. № 6. - С. 134-144.

35. Манусов В.З., Моисеев С.М., Перков С.Д. Интервальный анализ в задачах расчета токов короткого замыкания // Техническая Электродинамика. 1987. - № 5. - С. 13-18.

36. Мартынов А.П., Салимоненко Е.А., Федорова Н.И. Интервальная устойчивость оптимального решения задачи линейного программирования при параметрическом анализе // Вычислительные Технологии. 1999. - Т. 4, № 4. - С. 45-50.

37. Микитьянц С.Р., Голдобина Н.Н. Применение математических методов в управлении запасами. Л.: ЛФЭИ, 1982.

38. Первозванская Т.Н., Первозванский А.А. Элементы теории управления запасами. Л.: Изд-во ЛГУ, 1983.

39. Первозванский А.А. Математические модели в управлении производством. М.: Наука, 1975.

40. Плоткин Б.К. Экономико-математические методы и модели в управлении материальными ресурсами: учеб. пособие. СПб.: Университет экономики и финансов, 1992.

41. Рогалев А.Н., Шокин Ю.И. Исследование и оценка решений обыкновенных дифференциальных уравнений интервально-символьными методами // Вычислительные Технологии. 1999. -Т. 4, № 4. - С. 51-75.46