Содержание к диссертации
Введение
Глава 1. Некоторые основополагающие результаты оптимального управления в стохастических полумарковских моделях теории запасов 8
1. Общая характеристика современных научных результатов, связанных с рассматриваемой проблемой 8
2. Некоторые фундаментальные результаты по теории управления полумарковскими процессами с произвольными множествами состояний и управлений 10
3. Некоторые общие результаты, связанные с проблемой оптимального управления в полумарковских моделях теории запасов 17
4. Оптимальное управление запасом в полумарковской модели производства и потребления продукта, основанной на системе обслуживания M|G|1| 21
5. Некоторые специальные полумарковские модели управления запасом 30
6. Оптимальное управление запасом непрерывного продукта в модели регенерации 34
Глава 2. Разработка дискретной полумарковской модели управления запасом непрерывного продукта 40
1. Описание функционирования исследуемой системы и задание её исходных характеристик 40
2. Построение дискретной полумарковской модели управления запасом и общая постановка проблемы оптимального управления 44
3. Аналитические представления для вероятностных и стоимостных характеристик полумарковской модели 46
4. Проблема преобразования интегральных представлений для вероятностных и стоимостных характеристик модели 56
5. Представление основных характеристик полумарковской модели для детерминированных управлений 72
Глава 3. Исследование стационарных показателей качества управления в рассматриваемой модели. Основные результаты 83
1. Экстремальная задача для дробно-линейного функционала 83
2. Результаты о структуре стационарных стоимостных функционалов 85
3. Аналитические представления для функций, задающих дробно-линейные функционалы
Глава 4. Численное решение задачи оптимального управления запасом в дискретной полумарковской модели . 95
1. Описание схемы программы, ее алгоритма и функций 95
2. Описание некоторых стандартных вычислительных функций программы MATLAB 97
3. Унифицированные представления вероятностных и стоимостных характеристик модели 99
4. Задание исходных характеристик полумарковской модели для численного решения задачи оптимального управления запасом 101
5. Представление результатов решения задачи оптимального управления запасом для различного числа параметров управления. 104
Заключение 115
Список литературы. 117
- Некоторые фундаментальные результаты по теории управления полумарковскими процессами с произвольными множествами состояний и управлений
- Построение дискретной полумарковской модели управления запасом и общая постановка проблемы оптимального управления
- Аналитические представления для функций, задающих дробно-линейные функционалы
- Задание исходных характеристик полумарковской модели для численного решения задачи оптимального управления запасом
Введение к работе
Актуальность темы диссертации. Математическая теория управления запасами является одним из важных направлений современной прикладной математики. Стохастические и модели, используемые в теории управления запасами, весьма разнообразны и содержательны. В научной литературе по этому направлению имеется ряд фундаментальных изданий, содержащих обширную информацию об этих моделях и методах. Однако в последние десятилетия в российской научной литературе по прикладной математике отсутствуют издания монографического характера по теории управления запасами. Из современной зарубежной научной литературу упомянем книгу Э. Портеуса (E.L. Porteus) ' , в которой изложены как классические результаты, так и современное состояние стохастической теории управления запасами.
Следует отметить, что стохастические полумарковские модели достаточно редко используются в теории управления запасами. В то же время такие модели могут отражать существенные особенности эволюции рассматриваемых реальных систем. Для анализа этих моделей в общей теории полумарковских процессов разработан мощный и эффективный математический аппарат.
В настоящей работе предлагается и исследуется стохастическая полумарковская модель управления запасом непрерывного продукта, то есть такого, множество значений объема которого является подмножеством множества вещественных чисел. В экономических системах непрерывным продуктом могут являться нефть, бензин, мазут, газ, вода, зерно. Все эти продукты имеют важное значение на внутреннем рынке страны и используются во внешнеторговой деятельности. В реальной экономике имеется много систем (хранилищ или складов), которые предназначены для временного хранения запасов таких продуктов и поставок их непосредственным потребителям.
1 Porteus, Е, L, Foundations of stochastic inventory theory. — California: Stanford Business Books, 2002. — 320 p,
Предлагаемая модель предназначена для описания функционирования таких систем. В работе проводится теоретическое исследование проблемы оптимального управления в предложенной полумарковской стохастической модели. Основываясь на результатах проведенного анализа, можно создать методики вычисления оптимальных значений параметров управления. Таким образом, исследование, проводимое в данной работе, является актуальным, как с точки зрения развития теории стохастических полумарковских моделей, так и с точки зрения его использования для создания научно обоснованных методик расчета оптимальных дисциплин управления реальными экономическими системами.
Общая жарактеристика проведенного исследования. В работе рассматривается система, предназначенная для хранения и поставок потребителю некоторого непрерывного продукта, объем которого ограничен сверху заданной положительной величиной (максимальная вместимость хранилища). Положительные значения объема соответствуют реальному запасу продукта, отрицательное - неудовлетворенному спросу или дефициту. Потребление продукта происходит с постоянной скоростью, параметром управления является время от момента пополнения запаса до момента заказа на следующее пополнение. Пополнение запаса происходит по схеме, в которой учитываются состояния системы до пополнения, а также непосредственно после проведенной операции пополнения. Кроме того, в процедуре пополнения учитываются случайные отклонения от планируемого объема поставки.
Для описания функционирования рассматриваемой системы вводится два случайных процесса. Первый из них непосредственно описывает объем запаса в системе. Второй, условно называемый сопровождающим, представляет собой полумарковский процесс с конечным множеством состояний. Показателем качества управления является стационарный стоимостной функционал средней удельной прибыли (по отношению к единице времени) зависящий от вероятностных характеристик этих процессов. Как известно, он представляет
собой дробно-линейный функционал от вероятностных распределений, определяющих управляющие воздействия. В настоящей работе устанавливается, что оптимальной стратегией управления является детерминированная, которая зависит от состояния полумарковского процесса. Данный результат полностью согласуется с известными теоретическими утверждениями о характере оптимального управления полумарковскими процессами при весьма общих предположениях о структуре множеств состояний и управлений ". В то же время, в настоящей работе доказывается, что набор оптимальных значений параметра управления представляет собой точку глобального экстремума основной функции рассматриваемого дробно-линейного функционала, для которой получено явное представление.
Кроме этого, в работе продемонстрированы возможности использования полученных теоретических результатов с помощью численных методов. Именно, написана программа, позволяющая вычислять значения основной функции соответствующего дробно-линейного функционала и исследовать ее на экстремум.
Цель работы. Цель диссертационной работы заключается в решении проблемы оптимального управления в рассматриваемой стохастической полумарковской модели управления запасом непрерывного продукта и теоретическом обосновании метода нахождения оптимальной стратегии управления.
Научная новизна работы. В работе получены следующие новые научные результаты.
1. Разработана стохастическая модель управления запасом непрерывного продукта в форме управляемого полумарковского процесса с конечным множеством состояний.
Luque-Vasquez, F. Semi-Markov control modeis with average costs / F. Luque-Vasquez, 0, Hemandez-Lerma // Applicationes Mathematicae. - 1999. - v, 26, №3. - P. 315 - 331.
-
Получены явные представления для вероятностных характеристик этой модели, а также для характеристик аддитивного стоимостного функционала, связанного с введенным полумарковским процессом. Такие функционалы по содержанию имеют характер случайных затрат или прибыли, возникающих при эволюции системы.
-
Доказано утверждение о структуре показателя качества управления в поставленной задаче оптимизации. По содержанию данный показатель качества представляет собой стационарный стоимостной функционал средних удельных затрат или средней удельной прибыли. Установлено, что по форме зависимости от вероятностных распределений, задающих управления в каждом состоянии полумарковского процесса, этот показатель представляет собой дробно-линейный функционал. При этом получены явные аналитические представления для подынтегральных функций числителя и знаменателя данного функционала, выраженных через найденные ранее вероятностные и стоимостные характеристики модели.
-
Установлено, что оптимальная стратегия управления в исследуемой стохастической полумарковской модели является детерминированной и определяется точкой абсолютного экстремума основной функции дробно-линейного функционала - показателя качества управления. Основная функция представляет собой отношение подынтегральных функций числителя и знаменателя дробно-линейного функционала и определена в явной форме как функция конечного числа вещественных переменных.
Методы исследования. Для решения поставленной задачи в работе используются следующие математические методы.
1. Общие методы теории вероятностей и теории полумарковских
случайных процессов.
-
Методы функционального анализа и теории функций.
-
Аналитические методы классического математического анализа.
Научная и практическая значимость. Результаты диссертации могут представлять интерес для специалистов, занимающихся приложениями теоретико-вероятностных методов в экономических, технических и других областях. Также эти результаты могут являться теоретической основой для будущих исследований, связанных с различными модификациями данной модели и другими полумарковскими моделями управления запасами.
Кроме того, с целью иллюстрации практической значимости полученных теоретических результатов разработана программа, функционирование которой основано на полученном аналитическом представлении основной функции дробно-линейного функционала. Данная программа позволяет по заданным исходным характеристикам модели вычислять значения основной функции и исследовать её поведение в области возможных значений параметров управления с целью нахождения точки глобального экстремума (оптимального управления). Эта программа может быть интересна специалистам, занимающимся разработкой программных продуктов для анализа систем управления запасами.
Апробация работы. Результаты работы были представлены в форме докладов на следующих научных конференциях, симпозиумах и семинарах:
1. Научно-технические конференции студентов, аспирантов и молодых
ученых МИЭМ и МИЭМ НИУ ВШЭ 2011, 2012, 2013 годов;
2. Всероссийский симпозиум по прикладной и промышленной
математике. Осенняя открытая сессия (Сочи, сентябрь 2011 г.);
3. Всероссийская конференция "Прикладная теория вероятностей и
теоретическая информатика" (Москва, апрель 2012 г.);
-
Международная конференция "Теория вероятностей и ее приложения", посвященная 100-летию со дня рождения Б.В.Гнеденко (Москва, июнь 2012 г.);
-
ХХХЇ International Seminar on Stability Problems for Stochastic Models (Moscow, April 2013);
-
26-th European Conference on Operational Research (Rome, July 2013).
7, Семинар "Теория риска и смежные вопросы" кафедры математической статистики факультета ВМиК МГУ; руководитель семинара - д.ф-м.н., проф. Королев В.Ю. (Москва, март 2014).
Во всех указанных выше научных мероприятиях автор диссертационной работы принял личное участие.
Публикации. Результаты диссертации опубликованы в 6 работах соискателя, список которых приведен в конце автореферата. Научные работы [1], [2] опубликованы в журналах, входящих в утвержденный ВАК перечень ведущих рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени кандидата наук. При этом работы [1], [2] представляют собой развернутые научные статьи, включающие подробное изложение и обоснование полученных результатов. В указанных публикациях содержатся все основные результаты диссертации.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем работы составляет 120 страниц текста, в том числе 29 рисунков. Библиография включает в себя 39 наименований.
Некоторые фундаментальные результаты по теории управления полумарковскими процессами с произвольными множествами состояний и управлений
Проблема оптимального управления запасом в стохастической полумарковской модели является весьма сложной и многоплановой. В первой главе диссертационной работы предпринята попытка исследования связей проблемы управления запасом с общими результатами теории оптимального управления в стохастических полумарковских моделях. Кроме того, описан ряд фундаментальных результатов, относящихся к различным вариантам математических моделей управления запасом непрерывного продукта. Это позволит более точно определить место результатов, полученных в диссертации, среди других, связанных с оптимальным управлением в стохастических полумарковских моделях теории запасов.
Во втором параграфе главы 1 приведено изложение современных результатов теории оптимального управления в стохастических полумарковских моделях при весьма общих предположениях о структуре пространств состояний и управлений [32]. Показателем качества управления является стационарный стоимостной функционал, который по своему содержанию представляет средний удельный доход или прибыль, полученные при длительной эволюции модели. Основной результат исследования заключается в том, что в классе всех возможных марковских рандомизированных стратегий управления оптимальной является стационарная детерминированная стратегия, определяемая некоторой функцией, которая задает значения управления (решения) в каждом состоянии полумарковского процесса. Отметим, что результаты, полученные в данной диссертационной работе для полумарковского процесса с конечным множеством состояний, согласуются с приводимыми общими результатами и дополняют их.
В третьем параграфе главы 1 проводится изложение результатов исследования украинских математиков [7]. В данной работе рассматривается проблема управления запасом в полумарковской модели, множество состояний в которой представляет собой ограниченный интервал во множестве неотрицательных вещественных чисел [ ] . Параметром управления является объем дополнительного заказа (заказа на пополнение). Критерием оптимальности является стационарный стоимостной функционал среднего удельного дохода (прибыли). Доказывается, что среди всех допустимых стратегий пополнения запаса оптимальной является стационарная детерминированная стратегия. При этом среди всех стационарных детерминированных стратегий оптимальной является пороговая, определяемая некоторым пороговым значением запаса [ ]. Если в момент принятия решения состояние системы , то запас не пополняется, если же, то запас пополняется до максимально допустимого уровня. Отметим, что проблема доказательства оптимальности пороговых стратегий управления исследуется и в ряде других работ по теории запасами.
Четвертый параграф главы 1 посвящен изложению исследования, проведенного в работе [35]. В данной работе рассматривается стохастическая полумарковская модель производства и потребления некоторого продукта, объем которого измеряется в дискретных единицах. Основой построенной модели является система обслуживания . Среди работ, посвященных управлению в СМО, отметим монографию [30], в которой проведено подробное исследование задач оптимального управления для различных вариантов таких систем. В работе [35] потребление продукта происходит в моменты событий пуассоновского потока, управлением является решение о производстве дополнительной единицы продукта, принимаемое в определенные моменты времени. Своеобразие проведенного исследования заключается в его формально-технологическом содержании. После постановки основной задачи управления в форме экстремальной проблемы с ограничениями автор переходит к двойственной задаче с другим параметром оптимизации, который интерпретируется как плата за производство одной единицы продукции. Решение новой задачи ищется в классе пороговых стратегий, определяемых разбиением множества возможных значений параметра оптимизации на интервалы. Формулируется несколько понятий оптимальности в классе пороговых стратегий, доказываются утверждения о достаточных условиях оптимальности по отношению к каждому из введенных понятий. На основании полученных теоретических результатов доказываются утверждения о явном представлении оптимальных уровней разбиения множества значений параметра оптимизации для трех видов дисциплин функционирования и принятия решений в исследуемой системе.
В пятом параграфе главы 1 изложены результаты некоторых современных исследований, в которых рассматриваются специальные полумарковские модели управления запасами. В частности, в работе [37] исследуется модель управления запасом скоропортящегося продукта, основанная на использовании системы массового обслуживания с отказами. Поиск оптимального управления авторы осуществляют при помощи численных методов, используя модифицированный итерационный алгоритм. В работе [38] рассматривается проблема оптимального управления в системе, состоящей из складов и торговых точек. Потребление продукта осуществляется из торговых точек, запасы которых пополняются из складов. Запас продукта в каждой торговой точке может пополнятся из заданной подсистемы складов, один из которых является основным. Запас продукта на складе пополняется из внешнего источника согласно заданной стратегии. Параметром управления в системе является векторная величина, компоненты которой представляют собой номер склада, из которого будет произведено пополнение запаса в данной торговой точке. Исследование данной задачи производится численно на основе метода линейного программирования.
Шестой параграф главы 1 посвящен изложению некоторых основных результатов в теории оптимального управления запасом в модели регенерации. Следует отметить, что стохастическая модель регенерации, исследованная в работах [21], [22] и в диссертационной работе Р.В. Мельникова [13], является непосредственной предшественницей полумарковской модели управления запасом непрерывного продукта, исследованной в данной диссертационной работе.
Некоторые фундаментальные результаты по теории управления полумарковскими процессами с произвольными множествами состояний и управлений
Основой данного параграфа является работа [32] посвященная анализу управляемых полумарковских моделей с критериями средних затрат. Целью работы является доказательство существования оптимальной стратегии средних затрат для рассматриваемой модели.
Описание модели.
Пусть задано некоторое полное сепарабельное метрическое пространство X, в котором определена а -алгебра подмножеств В(Х). Такое пространство с заданной а -алгеброй называется борелевским пространством. Если X и Y - борелевские пространства, то стохастическим ядром на X при любом заданном jef называется функция Р(- ) такая, что Р(-у) является вероятностной мерой для любого фиксированного у є Г, а Р(В ) - это измеримая по Борелю функция на Y для каждого ВєВ(Х). Обозначим через N (соответственно N0) множество положительных (соответственно неотрицательных) целочисленных значений, R (соответственно R+) обозначает набор вещественных (соответственно неотрицательных) чисел.
Управляемая полумарковская модель представляет собой набор объектов (X,A,{A(x):xGX\Q,F,D,d).
Приведем описание каждого из указанных объектов. Множество X является пространством состояний, а множество А пространством управлений в данной модели. Эти пространства являются борелевскими.
Построение дискретной полумарковской модели управления запасом и общая постановка проблемы оптимального управления
Для математического описания рассматриваемой системы, кроме основного случайного процесса ( ) , непосредственно описывающего точный уровень запаса в произвольный момент времени, вводится вспомогательный полумарковский случайный процесс с конечным множеством состояний, определяемый при помощивложенной цепи Маркова. Предполагается, что объем запаса ( ) в начальный момент времени является заданной величиной, принадлежащей одному из возможных интервалов разбиения: В частности, возможно, что . Обозначим через номер подмножества состояний, в котором оказался процесс непосредственно после очередного пополнения запаса: В силу того, что в моменты пополнения запаса случайный процесс обладает марковским свойством, последовательность случайных величин образует цепь Маркова. Определим случайный процесс , связанный с последовательностью при помощи соотношения Случайный процесс представляет собой управляемый полумарковский процесс с конечным множеством состояний , траектории которого непрерывны справа. В дальнейшем этот процесс будет называться сопровождающим полумарковским процессом. Последовательность { } является цепью Маркова, вложенной в этот полумарковский процесс. Управление процессом ( ) производится в моменты (после определения значения процесса ( )). Параметр управления представляет собой случайную длительность периода времени от момента после очередного пополнения запаса в системе до момента следующего заказа на пополнение запаса. Именно, если (равенство случайных величин понимается в смысле совпадения функций распределения). Множество допустимых значений параметра управления совпадает с множеством неотрицательных чисел [ ). Задача оптимизации управления запасом в данной стохастической модели заключается в выборе управляющих вероятностных распределений доставляющих экстремум некоторому показателю качества управления Для того, чтобы формально поставить задачу оптимального управления в стохастической модели необходимо задать показатель качества управления или целевой функционал. Предположим, что в рассматриваемой стохастической модели определен некоторый аддитивный стоимостной функционал, связанный с полумарковским процессом ( ). Построение такого функционала описано, например, в работах ([3]; [5], глава 13; [11]). В частности, аддитивными стоимостными функционалами являются случайные величины прибыли и затрат, связанные с эволюцией рассматриваемой системы на интервале времени [ ]. Обозначим через значение аддитивного стоимостного функционала в момент времени , а через обозначим приращение значения данного функционала, образующееся на периоде эволюции ( ], где ( ) - длительность периода эволюции. Через обозначим математическое ожидание значения данного функционала, полученное в результате эволюции полумарковского процесса ( ) на интервале времени [ ].
Из научной литературы ([3], глава 9) известно, что при достаточно общих условиях имеет место следующий результат: где набор [ j представляет собой стационарное распределение цепи Маркова { }, вложенной в полумарковский процесс ( ); [ ] - условное математическое ожидание приращения аддитивного стоимостного функционала на периоде эволюции, определяемое при условии, что на этом периоде процесс ( ) находится в некотором состоянии { }; [Дґп ] - условное математическое ожидание длительности периода эволюции, определяемое при условии, что на этом периоде процесс ( ) находится в некотором состоянии {д По своему прикладному содержанию величина в (2.2.1) может представлять среднюю удельную прибыль или средние удельные затраты, связанные с эволюцией системы в стационарном режиме. Кроме того величина представляет собой функционал от набора вероятностных распределений ( ) { }, определяющих стратегию управления системой. В дальнейшем будем рассматривать стационарный стоимостной функционал ( ( ) ( ) ( )) как показатель качества управления системой и построенным полумарковским процессом ( ).
Таким образом, проблема оптимального управления запасом в рассматриваемой модели может быть сформулирована как экстремальная задача без ограничений: где множество вероятностных распределений, заданных на пространстве допустимых управлений [ ) Для решения поставленной экстремальной задачи будет необходимо установить явную форму зависимости целевого функционала от управляющих вероятностных распределений Для этого в свою очередь необходимо найти явные представления для вероятностных и стоимостных характеристик полумарковской модели, входящих в правую часть равенства (2.2.1). Перейдем к нахождению условных математических ожиданий { }, связанных с сопровождающим полумарковским процессом ( ). 3. Аналитические представления для вероятностных и стоимостных характеристик полумарковской модели В ходе дальнейшего исследования будет существенно использоваться понятие математического ожидания по совместному распределению некоторой случайной величины и случайного события. Приведем точное определение этого понятия. Предположим, что на некотором вероятностном пространстве заданы случайная величина и событие . Обозначим через ( ) ( ), где , совместное распределение случайной величины и события . Математическим ожиданием, определенным по совместному распределению случайной величины и события , будем называть величину: Предположим, что событие не зависит от значения аргумента вероятностного распределения ( ). Тогда имеет место соотношение между математическим ожиданием по совместному распределению и условным математическим ожиданием: Пусть задана система событий { } образующая полную группу несовместных событий. Тогда выполняется следующее соотношение, обычно называемое формулой полного математического ожидания (по аналогии с формулой полной вероятности): Вернемся к исследованию полумарковской модели управления запасом. Для определения вероятностных и стоимостных характеристик модели построим вспомогательную вероятностную конструкцию. Введем систему событий, связанных с состоянием системы в момент заказа на пополнение продукта. Зафиксируем состояние сопровождающего полумарковского процесса ( ) в момент очередного пополнения запаса: Ф) ( }. Будем рассматривать случайные события и характеристики, определяемые при указанном условии ( ) Обозначим через )событие, состоящее в том, что основной случайный процесс ( ), описывающий уровень запаса в системе в момент заказа на интервале [ ), принимает значение из множества , а через - событие, состоящее в том, что указанный процесс в момент заказа на интервале [ ) принимает значение из множества :
Аналитические представления для функций, задающих дробно-линейные функционалы
Применим общие результаты параграфа 2 главы 3 к исследованию рассматриваемой модели управления запасом. Сформулируем утверждение об аналитическом представлении стационарного стоимостного функционала, являющегося критерием качества управления в рассматриваемой задаче управления запасом. Теорема 3.3.1. Стационарный функционал средней удельной прибыли, определяемый равенством (2.2.1), представляет собой дробно-линейный функционал от вероятностных распределений щ) { }. Данный функционал задается аналитически формулой (3.1.1) и подынтегральные функции в дробно-линейном представлении функционала выражаются соотношениями: ((-W-) ) - число инверсий в перестановке N , причем суммирование в правой части формулы, определяющей функцию D {u), производится по всем возможным перестановкам набора чисел ( ), Вероятности перехода вложенной цепи Маркова полумарковского процесса ( ) при фиксированных значениях параметра управления определяются формулой (2.5.21). Представления для стоимостных функций щ) { } и ( ) { } определяются соотношениями (2.5.22) и (2.5.23).
Замечание 5. Входящие в формулы (2.5.21) - (2.5.23) вспомогательные вероятностные и стоимостные характеристики полумарковской модели, а именно функции: определяются с использованием предшествующих аналитических представлений следующими равенствами: (2.5.2) – (2.5.3) и (2.5.5) – (2.5.8) для вспомогательных переходных вероятностей; (2.5.9) – (2.5.14) для вспомогательных величин, связанных со временем пребывания процесса ( ) в различных состояниях; (2.5.15) - (2.5.20) для вспомогательных величин, связанных с математическими ожиданиями дохода, полученного за время пребывания процесса ( ) в различных состояниях.
Доказательство.
Стационарный функционал средней удельной прибыли вида (2.2.1), рассматриваемый в качестве целевого функционала в исследуемой задаче управления запасом, является частным случаем стационарного стоимостного функционала вида (3.2.16). Структура данного функционала, то есть форма его зависимости от управляющих вероятностных распределений, определяется теоремой 3.2.2. Применим эту теорему. Заметим, что основные вероятностные и стоимостные характеристики модели, входящие в выражения для подынтегральных функций числителя и знаменателя дробно-линейного функционала (3.2.16), то есть в правые части равенств (3.2.17), (3.2.18), определены в ходе предшествующего анализа. Именно: где функции ( ) ( ) { },определяются формулами (2.5.22), (2.5.23) с учетом предшествующих соотношений. Условные вероятности перехода , входящие в выражения для вспомогательных функций , определяются формулами (2.5.21) также с учетом предшествующих соотношений. Таким образом, аналитическое представление для подынтегральных функций числителя и знаменателя дробно-линейного функционала (3.1.1) задаются формулами (3.3.1), (3.3.2) с учетом последующих равенств (3.3.3), (3.3.4). Теорема 3.3.1 доказана.
В разделе 3.1 доказано утверждение о представлении показателя качества управления (2.2.1) в виде дробно-линейного функционала. Удалось явно выразить подынтегральные функции числителя и знаменателя (см. формулы (3.3.1), (3.3.2)), то есть найти аналитическое представление для основной функции этого функционала. Согласно утверждениям, приведенным в 1 параграфе главы 3, решение проблемы оптимального управления для рассмотренной задачи определяется точкой глобального экстремума основной функции , определяемой формулой (3.1.2).
Задачу поиска оптимального управления запасом в рассматриваемой модели можно считать завершенной. Нахождение точек, принадлежащих пространству допустимых векторных значений параметров управления ( ), которые доставляют глобальный экстремум функции ( ), представляет собой отдельную задачу. Такая задача может быть решена только численными методами при помощи средств современной вычислительной техники.
Задание исходных характеристик полумарковской модели для численного решения задачи оптимального управления запасом
В данном параграфе в качестве примеров приведены возможные варианты задания исходных характеристик для рассматриваемой полумарковской модели управления запасом. Для иллюстрации работы программы численного решения задачи оптимального управления рассмотрены варианты модели, когда количество параметров управления равняется двум и трем. Выбор размерности для демонстрации работы программы был обусловлен следующими факторами:
удобством графического представления поведения основной функции (3.1.2) в окрестности точки глобального экстремума;
ограниченными ресурсами ПК, которые не позволяют с достаточной точностью вычислять приближенное значение глобального экстремума функции (3.1.2) для случая , то есть при достаточно мелком выборе сетки значений аргументов, на которых строится данная функция.
Итак, зададим исходные характеристики рассматриваемой полумарковской модели для случая, когда число параметров управления равняется трем.
1. Вместимость склада и спрос на продукцию.
1.1. Максимальный объем запаса продукта (у.е.).
1.2. Скорость потребления (у.е./час).
2. Дискретизация модели и определение интервалов разбиения множества возможных значений запаса.
В данном параграфе будут представлены графические результаты численного решения задачи оптимального управления запасом, для значений исходных характеристик модели, заданных в 3. В случае трех параметров управления будут представлены следующие результаты:
графические представления для вероятностных и стоимостных характеристик полумарковской модели;
набор оптимальных параметров управления, а также графическое представление поведения основной функции (3.1.2) во всей области возможных значений параметров управления, а также в некоторой окрестности точки оптимального набора параметров управления (при помощи различных сечений графика функции (3.1.2)).
Представление основной функции (3.1.2) для задачи с 2-мя параметрами управления более удобно для визуального восприятия. В связи с этим для данного варианта модели будут приведены графические представления для функции (3.1.2) на всем множестве возможных значений параметров управления, а также в некоторой окрестности точки глобального экстремума.
Приведем вначале представление для переходных вероятностей ( ) { } вложенной цепи Маркова { } , задаваемых формулой (2.5.21). Общий график для данных функций представлен на рисунке 16. Для более наглядного представления поведения функций ( ), изображенных на рисунке 16, приведем отдельно графики для функций ( ) { } (см. рисунки 17 – 19). Проблема численного нахождения локального и глобального экстремумов функции нескольких вещественных переменных является одной из наиболее важных в теории оптимизации. Теоретические результаты по этой проблеме изложены в ряде фундаментальных научных изданий [4], [9]. На основе теоретических результатов разработан ряд алгоритмов, позволяющих численно решать экстремальные задачи, которые реализованы в различных программных продуктах, в том числе и в программе MatLab. В то же время, не существует универсальных программных продуктов, позволяющих находить глобальный экстремум у функций нескольких вещественных переменных, заданных при помощи массивов своих числовых значений.
Именно к такому случаю относится поиск глобального максимума основной функции ( ), заданной формулой (3.1.2) в данной работе. Заметим, что в основе используемого в пакете метода оптимизации лежат численные и приближенно-аналитические аппроксимации исследуемой целевой функции (3.1.2). Однако в данном случае целевая функция оказалась очень сложной и нерегулярной. Как показали дальнейшие расчеты, ее истинный рельеф является слабо-упорядоченным, имеющим неоднородную форму в разных частях области возможных значений аргументов. В этом варианте метод аппроксимации оказался неэффективен, и мощные средства блока оптимизации MatLab (методы наискорейшего спуска и т.п.) при различных настройках показали неудовлетворительные результаты. При получении данного вывода, в частности, проводилось численное моделирование функции (3.1.2) от двух параметров с последующим поиском экстремума и визуализацией наблюдений самой функции. В дальнейшем анализ поведения основной функции ( ) в случае 2-х и 3-х параметров производился путем численного моделирования и сравнения значений функции на плотной сетке в -мерном кубе. В случае поиск экстремума на ПЭВМ занял около 2-х часов. Учитывая существенно нелинейный рост времени вычисления значения функции (3.1.2) при увеличении размерности , поиск экстремума при займёт много времени. Выходом из данной ситуации является проведение дополнительных исследований по анализу поведения функции ( ) в различных областях и выработке специализированных методов поиска экстремума на всём -мерном кубе или в какой-нибудь его подобласти. Именно, возможен поиск набора локальных экстремумов на разреженной сетке узлов и дальнейшее более точное исследование в окрестностях точек, подозреваемых на глобальный экстремум. 5.2.1. Оптимальное решение для двумерной модели управления запасом. В результате действия программы для данного варианта модели и заданных значений исходных характеристик модели (см. 3) определен следующий набор оптимальных значений параметров управления: ( ) ( ). Отметим, что при построении сетки параметров управления на интервале [ ] был выбран шаг разбиения, равный 0.5, то есть общее количество точек, в которых функция ( ) была вычислена, составляет . График функции ( ) в области допустимых значений параметра управления и ее поведение в окрестности точки глобального экстремума представлены далее на рисунках 22 и 23 соответственно. Результатом действий программы поиска приближенного значения глобального экстремума для варианта трех параметров управления является следующий набор оптимальных значений параметров управления: ( ) ( ). При построении сетки параметров управления на интервале [ ] был выбран шаг разбиения, равный 1, то есть общее количество точек, в которых функция ( ) была вычислена, составляет . Графики сечений функции ( ) в области допустимых значений параметров управления и ее 110 поведение в окрестности точки глобального экстремума представлены далее на рисунках 24 29.
