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

The problem of construction of mathematical models of controlled supply chains under the condition of an uncertain external demand with the presence of restrictions on the state and control, as well as transport delays, is considered. Using the model of the discrete delay a discrete model of supply...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автори:	Dorofieiev, Yu. I., Nikulchenko, A. A.
Формат:	Стаття
Мова:	Російська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/55895
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334253526646785
author	Dorofieiev, Yu. I. Nikulchenko, A. A.
author_facet	Dorofieiev, Yu. I. Nikulchenko, A. A.
author_institution_txt_mv	[ { "author": "Yu. I. Dorofieiev", "institution": null }, { "author": "A. A. Nikulchenko", "institution": null } ]
author_sort	Dorofieiev, Yu. I.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-03-30T15:12:23Z
description	The problem of construction of mathematical models of controlled supply chains under the condition of an uncertain external demand with the presence of restrictions on the state and control, as well as transport delays, is considered. Using the model of the discrete delay a discrete model of supply chains with the controlled flows delays is received. On the basis of that model the "expanded" model without delays and a "moment" model, where the delay is equal to zero, are built. The proposed approach makes it possible to formulate the task of checking the conditions of existence and the task of forming the strategy of the inventory control in the supply chain, which guarantees the full and timely satisfaction of the external demand as a linear programming task. The first of them is solved in off-line mode before starting the process of control, and the second one is solved in on-line mode for each discrete instant of time. As an example, a problem of the analysis and synthesis of strategy of supplies control is consider for a three-tier supply chain, containing five knots.
first_indexed	2025-07-17T10:19:40Z
format	Article
fulltext	© Ю.И. Дорофеев, А.А. Никульченко, 2013 16 ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 УДК 519.95 ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ УПРАВЛЯЕМЫХ СЕТЕЙ ПОСТАВОК С УЧЕТОМ ЗАПАЗДЫВАНИЙ ПОТОКОВ Ю.И. ДОРОФЕЕВ, А.А. НИКУЛЬЧЕНКО Рассмотрена задача построения математических моделей управляемых сетей поставок в условиях неопределенного внешнего спроса при наличии ограни- чений на состояния и управления, а также транспортных запаздываний. С по- мощью модели дискретной задержки получена дискретная модель сети поста- вок с запаздываниями управляемых потоков, на основе которой построена «расширенная» модель без запаздываний и «мгновенная» модель, у которой запаздывания равны нулю. Предложенный подход позволяет сформулировать задачу проверки условия существования и задачу формирования стратегии управления запасами в сетях поставок, которая гарантирует полное и своевре- менное удовлетворение внешнего спроса, как задачи линейного программиро- вания. Первая из них решается в режиме off-line до начала процесса управле- ния, а вторая — в режиме on-line для каждого дискретного момента времени. В качестве примера рассмотрена задача анализа и синтеза стратегии управле- ния запасами для трехуровневой сети поставок, содержащей пять узлов. ВВЕДЕНИЕ Объектом исследования является система, которая представляет собой сово- купность взаимосвязанных объектов, осуществляющих добычу сырья, про- изводство, хранение, транспортировку и распространение некоторого набо- ра продукции. Предполагая производительности производственных узлов системы ненулевыми и учитывая, что уровни запаса ресурсов в узлах хране- ния изменяются с течением времени под воздействием внешнего спроса, получаем динамическую сетевую модель, которая имеет множество практи- ческих приложений, включая производственные системы, коммуникацион- ные сети, системы распределения ресурсов (воды, электроэнергии и т.п.), транспортно-складские системы и т.д. Одной из важнейших задач для систем рассматриваемого класса яв- ляется построение системы управления запасами. Создание запасов необхо- димо для полного и своевременного удовлетворения спроса со стороны внешних потребителей, но связано с издержками вследствие необходимости создания складов и наличия затрат на хранение ресурсов. В результате возни- кает необходимость в разработке методов математического моделирования управляемых систем производства-хранения-распределения ресурсов с целью их анализа и построения оптимальных стратегий управления запасами. Существуют различные типы топологии рассматриваемых систем, ко- торые определяются спецификой и размещением потребителей и складов. Если некоторые виды сырья или полуфабрикатов используются в несколь- ких процессах, проходящих одновременно, то система приобретает эшело- нированную структуру, и, поскольку отношения местоположения отдельных Построение математических моделей управляемых сетей поставок с учетом … Системні дослідження та інформаційні технології, 2013, № 1 17 узлов играют существенную роль с точки зрения анализа динамики всей системы, подобные системы называют распределенными сетями поставок. Предполагается, что каждый узел сети поставок в реальном времени принимает заказы от узлов, являющихся потребителями его продукции, и формирует заказы узлам, которые являются для него поставщиками ресур- сов. Узлы-продавцы конечной продукции принимают заказы непосредст- венно от внешних потребителей. В случае невозможности мгновенного вы- полнения заказа (то есть наличия дефицита) заказ считается отложенным и выполняется, как только это станет возможным. За отложенные заказы предусмотрены штрафы. Для анализа сетей поставок используется понятие «потока». Формаль- но, поток представляет деятельность, которая в единицу времени потребляет объемы ресурсов, пропорциональные ,,1, nii =µ полученные из n храни- лищ (возможно перерабатывая их) и поставляет объемы продукции, про- порциональные mjj ,1, =ν , в m хранилищ. Стоит подчеркнуть, что никакие предположения не вводятся относи- тельно природы деятельности, которая описывается потоком, безотноси- тельно ее технологической или организационной сущности. Другими сло- вами, поток обеспечивает представление в виде «черного ящика» любой производственной деятельности, и не требуют описания, каким образом та- кая деятельность выполняется. При этом «производственная деятельность» понимается в наиболее общем смысле, включая любой вид активности. Как частный случай, потоки могут представлять операции транспортировки, пе- ремещающие ресурсы между различными узлами сети без изменения их фи- зических свойств. В состав модели могут также входить потоки, которые поступают от (или направлены к) внешней среды и представляют внешний спрос либо поставки конечной продукции заказчикам. При этом потоки могут быть двух типов: часть из них являются управляемыми, а часть зависит от внеш- них факторов и являются неуправляемыми. Например, спрос на готовую продукцию обычно зависит от внешних факторов, в то время как производ- ственными и транспортными операциями можно управлять. По этой причи- не все потоки сети разделяются на два вектора: управляющие воздействия и внешний спрос. При этом единый термин «спрос» используется для обо- значения любых видов деятельности, порождаемых внешней средой, — как фактических значений спроса на конечную продукцию, так и происходящих вследствие этого поставок и закупок. Для графического представления сетей поставок используется ориен- тированный граф, вершины которого соответствуют узлам сети и предпола- гаются однономенклатурными. Дуги графа описывают управляемые и не- управляемые потоки в сети. Граф может быть разделен на уровни в зависимости от стадий переработки сырья и полуфабрикатов: первый уровень содержит узлы сети, которые являются продавцами конечной про- дукции, а любой уровень графа l содержит узлы, производящие либо со- храняющие ресурсы, которые используются для производства продук- ции уровнями строго меньше ,l но не менее одного вида продукции уровня .)1( −l Ю.И. Дорофеев, А.А. Никульченко ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 18 Цель работы — построение математических моделей управляемых се- тей поставок в условиях неопределенного внешнего спроса при наличии ограничений на состояния и управления, а также транспортных запаздыва- ний, что является важнейшим этапом решения задачи их анализа и построе- ния стратегии управления запасами, которая гарантирует полное и своевре- менное удовлетворение спроса со стороны внешних потребителей. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СЕТЕЙ ПОСТАВОК С ЗАПАЗДЫВАНИЯМИ Для математического описания сетей поставок применяются различные подходы [1]. В данной работе предлагается подход, использующий «дис- кретно-событийные модели». Дискретность возникает вследствие того, что получение информации о спросе, а также подача управляющих воздействий на объект происходит в дискретные моменты времени, обычно кратные не- которому периоду. Поэтому при построении модели используются следую- щие предположения: • выбирается период дискретизации по времени t∆ и все временные интервалы считаются кратными выбранному периоду; • время увеличивается пошагово, текущий момент времени обозна- чается ...,2,1,0=k , в конце каждого периода времени состояние системы вычисляется с помощью уравнений модели; • состояние системы характеризуется уровнем запасов каждого вида продукции в течение данного периода. Несмотря на то, что в состав сети поставок входят узлы различного ти- па, все они могут рассматриваться как производственные узлы, которые вы- полняют какие-либо операции из следующего перечня: формирование зака- зов на поставку ресурсов, переработка полученных ресурсов, хранение готовой продукции, отправка продукции заказчикам. Для описания узлов введем следующие обозначения: N — количество узлов сети поставок; }{ ijП π= , Nji ,1, = — производственная матрица, значение ),( ji -го элемента которой равно количеству продукции i , измеренному в единицах, которое требуется для производства единицы продукции ;j ijT , — целочисленная переменная, значение которой кратно периоду дискретизации t∆ , обозначающая время транспортировки продукции из уз- ла j в узел ;i iLT — целочисленная переменная, значение которой кратно периоду дискретизации t∆ , обозначающая время выполнения заказа в узле ;i iCost — стоимость производства единицы продукции ,i измеряемая в у.е.; ih — стоимость хранения единицы продукции i в течение периода времени t∆ , измеряемая в у.е.; iWar — максимально допустимая вместимость склада узла ,i измеряе- мая в единицах; iCap — максимальная производительность узла i в течение периода времени ,t∆ измеряемая в единицах. Построение математических моделей управляемых сетей поставок с учетом … Системні дослідження та інформаційні технології, 2013, № 1 19 Пополнение запасов всегда происходит с некоторым запаздыванием относительно момента выдачи требования. Запаздывания возникают вслед- ствие затрат времени на транспортировку ресурсов между узлами сети, наличия технологических ограничений системы коммуникаций, затрат вре- мени на обработку сырья и полуфабрикатов в узлах сети, наличия человече- ского фактора. Возможны следующие варианты моделей сетей поставок [2]: • модель с мгновенными поставками; • задержка поставок на фиксированный срок (кратный величине пе- риода дискретизации t∆ ); • случайная задержка с известным распределением длительности. В настоящей работе предлагается использовать модель дискретной за- держки, в которой величина запаздывания считается константой. Тогда для построения модели сети поставок вначале необходимо определить значения периодов запаздывания материальных потоков между каждой парой связан- ных узлов сети по формуле: .,, iijij LTTΛ += (1) Предполагается, что значения временных интервалов известны и не меняются в процессе функционирования сети. Затем вычисляется макси- мальный период запаздывания для каждого узла сети ,max iΛ Ni ,1= , после чего определяется максимальное значение периода запаздывания для всей сети maxΛ : .,1,,max,max max max, max NjiΛΛΛΛ i i ij j i === (2) Тогда динамика сети поставок с запаздываниями управляемых потоков описывается следующим рекуррентным соотношением: ,)()()()1( max 0 ∑ = +−+=+ Λ t t kEdtkuBkxkx (3) где Nkx R∈)( — вектор состояний системы, компонентами которого явля- ются уровни запаса ресурсов ,)(kxi имеющихся в наличии в момент време- ни ,k то есть такие, переработка которых к моменту времени k завершена и которые помещены в хранилища соответствующих узлов сети; mku R∈)( — вектор управляющих воздействий, компонентами которого являются объемы заявок на поставку ресурсов )(ku , которые формируются узлами сети в момент времени ;k qkd R∈)( — вектор внешних возмуще- ний, компонентами которого являются размеры внешнего спроса на конеч- ную продукцию, которые поступают в момент k на узлы первого уровня сети поставок; структура сети определяется структурой матриц влияния управляющих воздействий ,qN tB ×∈ R maxΛt ,0= и матрицы влияния внеш- них возмущений .mNE ×∈R Поясним на примере принцип формирования матриц tB и .E Пусть управляемый поток nu представляет процесс транспортировки и сборки, Ю.И. Дорофеев, А.А. Никульченко ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 20 в результате которого из 10 единиц продукции i , время транспортировки которой равно 2, =niT и 5 единиц продукции ,j время транспортировки равно ,1, =njT получают 1 единицу продукции n , время выполнения заказа равно .1=nLT Тогда в соответствии с выражением (1), определяется макси- мальное значение периода запаздывания для узла n : == nin ΛΛ , max {max .3}2,3 ,,, ==+==+ nnjnjnni LTTΛLTT На графе, изображающем модель сети, этот поток представляется гипер- дугой, соединяющей узлы сети i и j с узлом n (рис. 1). Значение времени транспортировки и количество единиц продукции, которое требуется в соот- ветствии с технологическим процес- сом, указаны в круглых и квадратных скобках, соответственно. Возле узла n в круглых скобках указано значение времени выполнения заказа .nLT Тогда в матрицах управляющих воздействий 3,0, =tBt управляемый поток nu будет представлен следующими ненулевыми элементами: =inB ][ 0 10−= , 5][ 0 −=jnB , .1][ 3 =nnB Аналогично, неуправляемый поток ,pd представляющий внешний спрос на продукцию узла ,r формирует столбец p матрицы внешних воз- мущений ,E который содержит один ненулевой элемент .1][ −=rpE Учитывая физический смысл введенных переменных, должны выпол- няться следующие ограничения: • переменные, описывающие уровни запаса ресурсов в узлах сети, а так- же управляемые и неуправляемые потоки должны быть неотрицательными; • уровни запаса, имеющиеся в наличии, не должны превышать вмести- мость соответствующих складов; • размеры заказов не должны превышать максимально возможные объемы транспортировок. Указанные ограничения могут быть представлены в виде выпуклых многогранников в пространствах соответствующей размерности: },0{)( +≤≤∈=∈ xxxXkx NR },0{)( +≤≤∈=∈ uuuUku mR (4) где векторы +x и +u считаются заданными. Предположение о том, что нижние границы значений x и u равны ну- лю, не является ограничением общности. Действительно, если нижняя гра- ница 0≠−x , то достаточно сдвинуть переменные состояний следующим i n j (2)[10] un (1)[5] (1) Рис. 1. Графическое представление потока Построение математических моделей управляемых сетей поставок с учетом … Системні дослідження та інформаційні технології, 2013, № 1 21 образом −−= xxx̂ , чтобы получить .ˆ0 −+ −≤≤ xxx Если 0≠− ju для неко- торых ,j то необходимо установить jjj uuu ˆ+= − , где −+ −≤≤ jjj uuû0 . Тогда компоненты − ju могут рассматриваться как дополнительные неуправляемые потоки с фиксированными значениями − + = jq ukd )(1 , для которых выпол- няется + + − + = 11 qq dd . Для определения оптимальной стратегии управления запасами необхо- димо точное задание характеристик внешнего спроса — интенсивности спроса в детерминированных моделях и вероятностных характеристик в стохастических моделях. Однако, при решении практических задач эти ха- рактеристики точно не известны. Поэтому используется подход, предло- женный в работе [3], согласно которому предполагается, что сеть поставок функционирует в условиях неизвестного, но ограниченного спроса, который характеризуется интервальной неопределенностью. Это означает, что каж- дая компонента спроса принадлежит некоторому интервалу, границы кото- рого определяются на основании изучения статистики продаж. Тогда к рас- смотренным ограничениям добавляется следующее: },{)( +− ≤≤∈=∈ ddddDkd qR (5) где векторы −d и +d определяют граничные значения спроса. Таким образом, ограничения (4) и (5) выглядят похоже, хотя интерпре- тируются по-разному. Ограничения на состояния и управляемые потоки оп- ределяются физическими возможностями системы, а на неуправляемые по- токи — неопределенностью внешнего спроса. ПОСТРОЕНИЕ «РАСШИРЕННОЙ» И «МГНОВЕННОЙ» МОДЕЛЕЙ СЕТЕЙ ПОСТАВОК Для построения модели сети поставок без запаздываний применяется техни- ка расширения пространства состояний. В результате получим «расширен- ную» модель, уравнение динамики которой примет вид: ),()()()1( kGdkFukAξkξ ++=+ (6) где вектор состояний строится следующим образом: ,])(,...,)2(,)1(,)([)( TTTTT maxΛkukukukxkξ −−−= (7) а матрицы модели имеют соответствующую блочную структуру: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = ××××× ××××× ××××× ××××× −× mmmmmmmmNm mmmmmmmmNm mmmmmmmmNm mmmmmmmmNm ΛΛNN BBBB A ]0[...]0[]0[]0[ .................. ]0[]0[...]0[]0[ ]0[]0[...]0[]0[ ]0[]0[...]0[]0[]0[ ... maxmax 121 I I I I , Ю.И. Дорофеев, А.А. Никульченко ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 22 ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = × × × × mm mm mm mm B F ]0[ ... ]0[ ]0[ 0 I , ⎟⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = × × × × qm qm qm qm E G ]0[ ... ]0[ ]0[ ]0[ . Использовать расширенную модель для анализа сложно из-за очень больших размерностей. Однако с помощью замены базиса ее можно свести к модели, вектор состояний которой имеет вид: ,])(,...,)2(,)1(,)([)(ˆ TTTTT maxΛkukukukzk −−−=ξ (8) где переменные )(kz называют фиктивными уровнями запаса и определяют как сумму уровня запаса ресурсов, находящихся в хранилищах, и ресурсов, которые находятся в процессе транспортировки между узлами сети: .,1,ˆгде),(ˆ)()( max 1 maxmax ΛiBBtkuBkxkz Λ it ti Λ t t ==−+= ∑∑ == (9) Полученная система с вектором состояний )(ˆ kξ допускает декомпози- цию на две подсистемы. Первая представляет собой «мгновенную» модель сети, у которой все запаздывания равны нулю, и описывается уравнением: .где),()()()1( max 0 ∑ = =++=+ Λ t tBBkEdkBukzkz (10) Переменными состояния второй подсистемы являются управляющие воздействия с запаздываниями расширенной модели сети ),( tku − max,1 Λt = . При этом вторая подсистема является асимптотически устойчи- вой, поскольку ее матрица динамики является нильпотентной. Поэтому для анализа и синтеза стратегии управления запасами используется «мгновен- ная» модель распределенной сети поставок (10). СИНТЕЗ СТРАТЕГИИ УПРАВЛЕНИЯ ЗАПАСАМИ Задача синтеза системы управления запасами состоит в синтезе стратегии управления, которая определяет управляемые потоки сети в соответствии с поставленной целью управления и с учетом ограничений (4), (5). Множество допустимых начальных условий определяется выражением: }.0:{)}:({0 +++− ≤≤∩−−≤≤−= xxxBUxxxX δδ (11) При этом границы множества X допустимых значений вектора со- стояний трансформируются с учетом векторов −δ и +δ , которые вычисля- ются следующим образом: ,max,min dEδdEδ i Dd ii Dd i ∈ + ∈ − == (12) где iE обозначает i–ю строку матрицы .E Построение математических моделей управляемых сетей поставок с учетом … Системні дослідження та інформаційні технології, 2013, № 1 23 Одним из главных вопросов, на которые необходимо дать ответ в про- цессе анализа, является следующий: существует ли для построенной модели сети поставок допустимая стратегия управления запасами, которая обеспе- чивает полное и своевременное удовлетворение внешнего спроса при задан- ных ограничениях. В работе [3] доказана теорема, которая определяет необходимые и дос- таточные условия существования допустимой стратегии управления для систем рассматриваемого класса. Согласно этой теореме, допустимая стра- тегия управления существует, если и только если выполняется условие: .BUED −⊂ (13) Условие (13) допускает следующую геометрическую интерпретацию: выпуклый многогранник, описывающий влияние внешнего спроса, должен находиться строго внутри выпуклого многогранника, описывающего влия- ние управляющих воздействий. Условие (13) выполняется, если существует 0>ε такое, что ,BUΩED −⊂+ ε где )}.(0:{ −++ −−≤≤= δδxxxΩ Множество ΩED ε+ представляет собой множество векторов, которые могут быть представлены в виде ⎥⎦ ⎤ ⎢⎣ ⎡= εω dEx ][ I , где ,Dd ∈ Ω∈ω . Тогда множество ΩED ε+ со- держится в ,BU− если и только если условие BUdIEx j iij −∈⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = εω ][ выполняется для каждого }{Dd i vert∈ и ,}{Ω∈ vertjω где }{Avert обоз- начает множество вершин многогранника .A Значение ε может быть най- дено с помощью следующего алгоритма: • Установить .∞+=ε • Для каждого }{Dd i vert∈ и }{Ω∈ vertjω решить следующую за- дачу линейного программирования (ЛП): ,max εµ =ij ,BuEd ji −=+ εω .0,0 ≥≤≤ + εuu (14) Если хотя бы для одного из наборов jid ω, задача (14) не имеет реше- ния, значит для построенной модели сети поставок условие (13) не выпол- няется. В противном случае установить }.,{min , ijji µεε = • Если полученное минимальное значение равно нулю ,0min =ε то выполняется условие BUED −⊆ , тогда сходимость последовательности )(kx ..,.2,1,0=k к некоторому оптимальному уровню запасов не может быть гарантирована. • Если полученное минимальное значение больше нуля ,0min >ε зна- чит условие (13) выполняется. Несмотря на то, что задача проверки условия существования допусти- мой стратегии управления (13) является NP -полной, она может быть реше- на до начала процесса управления в режиме off-line [4]. Если условие (13) выполняется, то выбор допустимой стратегии управ- ления для мгновенной модели сети (10) определяется следующими сообра- Ю.И. Дорофеев, А.А. Никульченко ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 24 жениями. Определяются конструктивные ограничения сети поставок для переменных, определяющих фиктивные уровни запаса: }.{)( +− ≤≤∈=∈ zzzzZkz NR (15) Значение вектора нижней границы −z должно обеспечивать неотрица- тельность значений вектора наличного уровня запаса )(kx . Тогда из выра- жения (9) следует, что «наименьшее» значение вектора нижней границы оп- ределяется выражением: .ˆ max 1 ∑ = +− = Λ i iuBz (16) Полученный результат кажется парадоксальным. Чтобы обеспечить ,0)( >kx накладывается ограничение (16), согласно которому, чем выше мощность потока, которая определяется максимальным размером перевози- мых ресурсов, тем выше должна быть нижняя граница. Чтобы объяснить это, на первый взгляд, абсурдное заключение, напомним, что, чем большими являются мощности управляемых потоков, тем большими могут быть мгно- венные объемы отгрузки ресурсов, которые невозможно сразу компенсиро- вать из-за наличия запаздываний. Это требует наличия больших страховых уровней запаса, чтобы избежать опустошения складов. Чтобы решить эту проблему, необходимо минимизировать стоимость величины в правой части выражения (16), используя вектор стоимостей производства единицы продукции .,1},0{ NiCostC i =>= Тогда необходи- мо найти вектор +u~ такой, что ++ ≤≤ uu~0 , который минимизирует соот- ветствующую стоимость при выполнении условия ,~UBED −⊂ где }~0:{~ +≤≤= uuuU . Это означает, что если управляемые потоки сети никогда не используются в полную силу, то можно заменить +u на ,~ +u чтобы свес- ти к минимуму затраты. Значения вектора +u~ определяется путем решения следующей ЛП-задачи: ,~ˆmin max 1 + = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∑ uBC Λ i i .~,~0 UBEDuu −⊂≤≤ ++ (17) Тогда векторы, определяющие оптимальную нижнюю и верхнюю гра- ницы фиктивного уровня запаса вычисляются следующим образом: .~ˆ,~ˆ~ 11 ∑∑ = +++ = +− +== maxmax Λ i i Λ i i uBxzuBz (18) Для существования допустимой стратегии управления, формируемой в виде обратной связи по состоянию ))(()( kzΦku = с учетом ограничений (15), кроме выполнения условия (13), необходимо, чтобы выполнялось ус- ловие .)(~ +−+− ≤−+ zz δδ Поэтому на каждом шаге k для определения допустимой стратегии управления, гарантирующей полное удовлетворение внешнего спроса Dkd ∈)( , необходимо решить следующую ЛП-задачу [3]: Построение математических моделей управляемых сетей поставок с учетом … Системні дослідження та інформаційні технології, 2013, № 1 25 ,minarg))(()( 0 λ λ≥ == kzΦku ,~)(,)()( UkuzkBukzz ∈+≤+≤ λθ (19) где ,~ −− −= δzz ).(~ −+−+ −−−= δδθ zz ЧИСЛЕННЫЙ ПРИМЕР В качестве примера рассмотрим сеть поставок, которая изучалась в рабо- те [5]. Граф, представляющий модель сети, можно описать следующим об- разом )})2,3(),1,3(),3,4(),3,5(),2,5(),1,5{(},5,4,3,2,1{( === EVG . Сеть содержит 5=N узлов, которые разделены на три уровня: узлы 1 и 2, образующие первый уровень сети поставок, перерабатывают продук- цию узлов 3 и 5, и имеют склады, которые хранят, соответственно, про- дукцию типа 1 и продукцию типа 2. Узел 3 перерабатывает продукцию уз- лов 4 и 5, хранит продукцию типа 3, и составляет второй уровень сети поставок. Узлы 4 и 5 являются поставщиками сырья соответствующего типа и составляют третий уровень сети поставок. Представим управляемые потоки в виде гипер-дуг, изображенных не- прерывными линиями, добавив два потока, которые представляют поставки сырья извне, и пронумеруем, как показано на рис. 2. Дуги 21, dd , изобра- женные пунктирными линиями, представляют внешний спрос. Значение времени транспортировки jiT , и количество единиц продукции ijπ , которое требуется в соответствии с технологическим процессом, указаны в круглых и квадратных скобках, соответственно. Возле каждого узла в круглых скоб- ках указаны значения времени выполнения заказа iLT . В соответствии с технологическим описанием производственных про- цессов составлена производственная матрица П . Матрица влияния управ- ляющих воздействий B и матрица влияния внешних возмущений E равны: ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 00221 00300 00022 00000 00000 П , ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ −−− − −−= 10221 01300 00122 00010 00001 B , ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − = 00 00 00 10 01 E . 1 1u ]1)[0( 2u 3u 2d 2 1d 3 4 5 )1( )2( )1( )1( )2( ]1)[1( ]2)[1( ]2)[1( ]2)[1( ]3)[1( ]2)[1( 5u 4u ]1)[0( Рис. 2. Графическое представление модели сети поставок Ю.И. Дорофеев, А.А. Никульченко ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 26 Пусть заданы ограничения по максимальные производительности узлов сети за период ,]7608402806080[ T=Cap максимальные вместимости складов [ ] ,50050030015080 T=+x максимальные объемы транспорти- ровки ,]4004002505050[ T=+u граничные значения внешнего спроса T]2515[=−d и ,]3625[ T=+d а также стоимости производства и транспор- тировки единицы продукции: T]30305090100[=Cost и .]11145[ T=h Остальные нижние границы возможных значений переменных равны нулю. В соответствии с (12) вычислим векторы T]0003625[ −−=+δ и .]0002515[ T−−=−δ Для построенной модели сети поставок необходимо проверить выпол- нение условия существования допустимой стратегии управления (13), ис- пользуя приведенный выше алгоритм. Для рассматриваемого примера раз- мерности множеств вершин многогранников равны ,4}{dim =Dvert 32}{dim =Ωvert . В результате получили, что для всех 128324 =× вариан- тов задача (14) имеет решение, и минимальное значение 0885,0min =ε от- лично от нуля. Таким образом, оптимальная допустимая стратегия управле- ния для построенной модели сети существует, и гарантируется сходимость последовательности векторов состояний к некоторому оптимальному уров- ню запасов. Кроме того, в результате решения задачи (17) были определены мини- мальные значения элементов вектора ,]3353601203624[~ Tu =+ опреде- ляющего верхние границы размеров заказа ресурсов, при которых га- рантируется полное удовлетворение спроса. Тогда в соответствии с выражениями (18) границы вектора фиктивного уровня запаса равны: ,]33572024010848[~ Tz =− .]8351220540268128[ Tz =+ Предположим, что в начальный момент времени значения вектора фик- тивных уровней запаса ресурсов совпадают с максимальными объемами вместимости складов Warz =)0( , а векторы )(ku и )(kd равны нулю для .0<k Стратегия управления ))(()( kzΦku = определяется на каждом шаге k путем решения ЛП-задачи (19), которая для рассматриваемого примера может быть представлена в виде: .335,360,120,36,24 ,0,,,,,0 ,50035022335 ,5007203720 ,30013422240 ,140240143 ,716363 min 54321 54321 53215 434 3213 22 11 ≤≤≤≤≤ ≥≥ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ⋅+≤+−−−≤ ⋅+≤+−≤ ⋅+≤+−−≤ ⋅+≤+≤ ⋅+≤+≤ uuuuu uuuuu uuuuz uuz uuuz uz uz λ λ λ λ λ λ λ (20) Построение математических моделей управляемых сетей поставок с учетом … Системні дослідження та інформаційні технології, 2013, № 1 27 Анализ результатов моделирования изменения фиктивных уровней за- паса )(kz и объемов производства ),(ku полученных с использованием «мгновенной» модели сети, позволяет сделать следующие выводы: • полученная стратегия управления запасами обеспечивает полное и своевременное удовлетворение как внешнего, так и внутреннего спроса; • сходимость последовательности векторов состояний ),(kz ...,1,0=k к некоторому оптимальному уровню запасов достигнута за 6 шагов. ВЫВОДЫ Предложенный подход к построению математических моделей распреде- ленных сетей поставок с запаздываниями управляемых потоков и интер- вальной неопределенностью внешнего спроса позволяет сформулировать задачу проверки условия существования и задачу формирования допусти- мой стратегии управления запасами как ЛП-задачи. Первая из них решается в режиме off-line до начала процесса управления, а вторая — в режиме on- line в каждый момент времени k . Построена программная реализация алго- ритмов с помощью пакета MATLAB. Результаты численного моделирова- ния подтверждают эффективность предложенного подхода. ЛИТЕРАТУРА 1. Лотоцкий В.А., Мандель А.С. Модели и методы управления запасами. — М.: Наука, 1991. — 189 с. 2. Рыжиков Ю.И. Теория очередей и управление запасами. — СПб.: Питер, 2001. — 384 с. 3. Blanchini F., Rinaldi F., Ukovich W. Least inventory control of multistorage systems with non-stochastic unknown inputs // IEEE Transaction on robotics and automa- tion. — 1997. — 13. — P. 633–645. 4. Дорофеев Ю.И., Дорофеев Д.Ю., Никульченко А.А. Применение MATLAB для анализа и синтеза систем управления запасами в распределенных сетях поcтавок // Проектирование инженерных и научных приложений в среде MATLAB: материалы V Международной научной конференции (г. Харь- ков, 11 – 13 мая 2011 г.) — Харьков: БЭТ, 2011. — С. 220–230. 5. Hennet J.-C. A bimodal scheme for multi-stage production and inventory control // Automatica. — 2003. — 39. — P. 793–805. Поступила 31.05.2011
id	journaliasakpiua-article-55895
institution	System research and information technologies
keywords_txt_mv	keywords
language	Russian
last_indexed	2025-07-17T10:19:40Z
publishDate	2013
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/ce/a52d5d303e83ac4250f5a74711f358ce.pdf
spelling	journaliasakpiua-article-558952018-03-30T15:12:23Z Construction of mathematical models of controlled supply chains considering flows delays Построение математических моделей управляемых сетей поставок с учетом запаздываний потоков Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків Dorofieiev, Yu. I. Nikulchenko, A. A. The problem of construction of mathematical models of controlled supply chains under the condition of an uncertain external demand with the presence of restrictions on the state and control, as well as transport delays, is considered. Using the model of the discrete delay a discrete model of supply chains with the controlled flows delays is received. On the basis of that model the "expanded" model without delays and a "moment" model, where the delay is equal to zero, are built. The proposed approach makes it possible to formulate the task of checking the conditions of existence and the task of forming the strategy of the inventory control in the supply chain, which guarantees the full and timely satisfaction of the external demand as a linear programming task. The first of them is solved in off-line mode before starting the process of control, and the second one is solved in on-line mode for each discrete instant of time. As an example, a problem of the analysis and synthesis of strategy of supplies control is consider for a three-tier supply chain, containing five knots. Рассмотрена задача построения математических моделей управляемых сетей поставок в условиях неопределенного внешнего спроса при наличии ограничений на состояния и управления, а также транспортных запаздываний. С помощью модели дискретной задержки получена дискретная модель сети поставок с запаздываниями управляемых потоков, на основе которой построена "расширенная" модель без запаздываний и "мгновенная" модель, у которой запаздывания равны нулю. Предложенный подход позволяет сформулировать задачу проверки условия существования и задачу формирования стратегии управления запасами в сетях поставок, которая гарантирует полное и своевременное удовлетворение внешнего спроса, как задачи линейного программирования. Первая из них решается в режиме off-line до начала процесса управления, а вторая — в режиме on-line для каждого дискретного момента времени. В качестве примера рассмотрена задача анализа и синтеза стратегии управления запасами для трехуровневой сети поставок, содержащей пять узлов. Розглянуто задачу побудови математичних моделей керованих мереж поставок в умовах невизначеного зовнішнього попиту за наявності обмежень на стани і управління, а також транспортних запізнювань. За допомогою моделі дискретної затримки одержано дискретну модель мережі поставок із запізнюваннями керованих потоків, на основі якої побудовано "розширену" модель без запізнювань і "миттєву" модель, в якій запізнювання дорівнюють нулю. Запропонований підхід дозволяє сформулювати задачу перевірки умови існування та задачу формування стратегії управління запасами в мережах поставок, яка гарантує повне і своєчасне задоволення зовнішнього попиту, як задачі лінійного програмування. Перша з них вирішується в режимі off-line до початку процесу управління, а друга — у режимі on-line для кожного дискретного момента часу. Як приклад розглянуто задачу аналізу та синтезу стратегії управління запасами для трирівневої мережі поставок, що містить п’ять вузлів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013-03-19 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/55895 System research and information technologies; No. 1 (2013); 16-27 Системные исследования и информационные технологии; № 1 (2013); 16-27 Системні дослідження та інформаційні технології; № 1 (2013); 16-27 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/55895/52056 Copyright (c) 2021 System research and information technologies
spellingShingle	Dorofieiev, Yu. I. Nikulchenko, A. A. Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
title	Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
title_alt	Construction of mathematical models of controlled supply chains considering flows delays Построение математических моделей управляемых сетей поставок с учетом запаздываний потоков
title_full	Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
title_fullStr	Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
title_full_unstemmed	Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
title_short	Побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
title_sort	побудова математичних моделей керованих мереж поставок із врахуванням запізнювань потоків
url	https://journal.iasa.kpi.ua/article/view/55895
work_keys_str_mv	AT dorofieievyui constructionofmathematicalmodelsofcontrolledsupplychainsconsideringflowsdelays AT nikulchenkoaa constructionofmathematicalmodelsofcontrolledsupplychainsconsideringflowsdelays AT dorofieievyui postroeniematematičeskihmodelejupravlâemyhsetejpostavoksučetomzapazdyvanijpotokov AT nikulchenkoaa postroeniematematičeskihmodelejupravlâemyhsetejpostavoksučetomzapazdyvanijpotokov AT dorofieievyui pobudovamatematičnihmodelejkerovanihmerežpostavokízvrahuvannâmzapíznûvanʹpotokív AT nikulchenkoaa pobudovamatematičnihmodelejkerovanihmerežpostavokízvrahuvannâmzapíznûvanʹpotokív

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

Репозитарії

Схожі ресурси