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

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

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2019
Hauptverfasser: Белых, Т.В., Журбенко, Н.Г., Шулинок, И.Э.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:Теорія оптимальних рішень
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/161675
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Динамические производственно-распределительные задачи / Т.В. Белых, Н.Г. Журбенко, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 61-66. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-161675
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1616752025-02-23T20:13:21Z Динамические производственно-распределительные задачи Динамічні виробничо-розподільні задачі Dynamic industrial-distributive problems Белых, Т.В. Журбенко, Н.Г. Шулинок, И.Э. Приводится математическая модель динамических распределительных задач. Алгоритм решения задач большой размерности основан на использовании методов негладкой оптимизации. Наводиться математична модель динамічних розподільних задач. Алгоритм розв'язання задач великої розмірності заснований на використанні методів негладкої оптимізації. A mathematical model of dynamic distribution problems is given. The algorithm for solving large-scale problems is based on the use of nonsmooth optimization methods. 2019 Article Динамические производственно-распределительные задачи / Т.В. Белых, Н.Г. Журбенко, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 61-66. — Бібліогр.: 4 назв. — рос. 2616-5619 https://nasplib.isofts.kiev.ua/handle/123456789/161675 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Приводится математическая модель динамических распределительных задач. Алгоритм решения задач большой размерности основан на использовании методов негладкой оптимизации.
format Article
author Белых, Т.В.
Журбенко, Н.Г.
Шулинок, И.Э.
spellingShingle Белых, Т.В.
Журбенко, Н.Г.
Шулинок, И.Э.
Динамические производственно-распределительные задачи
Теорія оптимальних рішень
author_facet Белых, Т.В.
Журбенко, Н.Г.
Шулинок, И.Э.
author_sort Белых, Т.В.
title Динамические производственно-распределительные задачи
title_short Динамические производственно-распределительные задачи
title_full Динамические производственно-распределительные задачи
title_fullStr Динамические производственно-распределительные задачи
title_full_unstemmed Динамические производственно-распределительные задачи
title_sort динамические производственно-распределительные задачи
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2019
url https://nasplib.isofts.kiev.ua/handle/123456789/161675
citation_txt Динамические производственно-распределительные задачи / Т.В. Белых, Н.Г. Журбенко, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 61-66. — Бібліогр.: 4 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT belyhtv dinamičeskieproizvodstvennoraspredelitelʹnyezadači
AT žurbenkong dinamičeskieproizvodstvennoraspredelitelʹnyezadači
AT šulinokié dinamičeskieproizvodstvennoraspredelitelʹnyezadači
AT belyhtv dinamíčnívirobničorozpodílʹnízadačí
AT žurbenkong dinamíčnívirobničorozpodílʹnízadačí
AT šulinokié dinamíčnívirobničorozpodílʹnízadačí
AT belyhtv dynamicindustrialdistributiveproblems
AT žurbenkong dynamicindustrialdistributiveproblems
AT šulinokié dynamicindustrialdistributiveproblems
first_indexed 2025-11-25T00:00:41Z
last_indexed 2025-11-25T00:00:41Z
_version_ 1849718306285551616
fulltext ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 61 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Приводится математическая мо- дель динамических распредели- тельных задач. Алгоритм реше- ния задач большой размерности основан на использовании мето- дов негладкой оптимизации.  Т.В. Белых, Н.Г. Журбенко, И.Э. Шулинок, 2019 УДК 519.8 Т.В. БЕЛЫХ, Н.Г. ЖУРБЕНКО, И.Э. ШУЛИНОК ДИНАМИЧЕСКИЕ ПРОИЗВОДСТВЕННО- РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ Введение. В работе приводится математиче- ская модель одного класса динамических распределительных задач. Математическая модель имеет приложения при решении практических задач оптимального матери- ально-технического снабжения. Математиче- ская модель задачи – переработанный вари- ант модели [1, 2]. Математическая модель динамических распределительных задач отражает требова- ние возможно наиболее полного удовлетво- рения спроса потребителей высокого прио- ритета в отдельные интервалы планируемого периода. Условие баланса общих объемов производимой и требуемой продукции для отдельных интервалов и всего планового периода может не выполняться. Математическая модель. Имеется m по- ставщиков (предприятий) и n потребителей (строек). Планируемый период разбит на T временных интервалов. Для краткости интервал планирования будем называть кварталом. Заданы величины: ita – максимально возможный объем про- дукции, производимый поставщиком i за квартал t , 1,t T ; 0ita  ; jtb – объем спроса на продукцию потреби- теля j в квартале t , 1  ,t T ; 0jtb  ; ijc – стоимость перевозки единицы объема продукции от поставщика i к потребителю j ; транспортные издержки не зависят от вре- менного интервала доставки. Т.В. БЕЛЫХ, Н.Г. ЖУРБЕНКО, И.Э. ШУЛИНОК 62 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 Введем обозначения: jt – объем спроса потребителя j за первые t кварталов; 1 , t jt jb     1, ;t T it – максимально возможный объем продукции предприятия i за первые t кварталов: 1 , 1, ; t it ia t T     ijtx – объем продукции, поставляемый предприятием i потребителю j за первые t кварталов, 1,t T ; величины ijtx подлежат определению в результате решения задачи. Заданы величины: jtR – величина штрафа за недопоставку единицы продукции j -му потреби- телю в конце квартала t , 1,t T ; jtR задаются в cоответствии с приоритетом потребителя j . it – величина штрафа за наличие единицы нераспределенной продукции у i -го поставщика в конце квартала t ; 1, .t T Обозначим it – объем нераспределенной продукции поставщика i в конце квартала t . При построении математической модели существенна следующая целевая установка: потребители в течение всего планируемого периода должны по возможности получать продукцию лишь от одного поставщика. Это требование соответствует условию стабильности логистических связей между поставщиками и потребителями. В модели условие стабильности логистических связей учитывается следующим образом. Пусть все 0jt  . Это ограничение, как будет видно из дальнейшего, не является существенным и введено лишь для простоты изложения. Окончательные результаты справедливы для общего случая 0jt  . Величину /( )ijt jtx  назовем степенью обеспеченности потребителя j поставщиком i за первые t кварталов, 1,t T . В математической модели вводится условие не убывания степени обеспеченности потребителя (любым) поставщиком по интервалам планового периода: 1 1, 2, , 1, ,/ 1, ./ijt jt ijt jtx x t T j n i m       (1) Математическая модель поставленной задачи представляется следующей задачей, линейного программирования: ДИНАМИЧЕСКИЕ ПРОИЗВОДСТВЕННО-РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 63 , , , , 1 , 1 1 , 1 min . n m n T m Tm ij ijT jt jt ijt it it j i j t i i t c x R x                      (2) 1 1, 1, , 1, , 2, ,jt ijt jt ijtx x i m j n t T       (3) 1 , 1, , 1, , n ijt it it j x i m t T       (4) 1 , 1, , 1, , m ijt jt i x j n t T      (5) 0, 1, , 1, , 1, ,ijtx i m j n t T    (6) 0, 1, , 1, ,it i m t T    (7) Замечания. 1. Ограничения (3), имеющие смысл и для 0jt  , соответствуют выше- приведенному условию (1): степень обеспеченности потребителя любым поставщиком i ( 1, )i m не убывает со временем. Условие неубывания степени обеспеченности (3) запрещает прерывать обслуживание потребителя данным поставщиком в следующие периоды времени, если потребитель получал продукцию от этого поставщика в предыдущие периоды планируемого периода и его спрос не был полностью удовлетворен. Поэтому условие (3) отражает требование стабильности логистических связей между поставщиками и потреби- телями. Более строгая формулировка такого условия привела бы к задаче частично целочисленного программирования, но решение таких задач при большой размерности проблематично. 2. Хотя естественное условие 1ijt ijtx x  ( 1,i m , 1, ,j n   1, 1)t T  не введено формально в список ограничений задачи, однако, это условие является следствием ограничений (3) и очевидных неравенств 1 .0jt jt   3. Ограничения (4) соответствуют балансу объемов производимой и постав- ляемой продукции для поставщиков. 4. Ограничения (5) отражают условие: потребители не получают излишка продукции (преждевременно произведенная поставщиком продукция хранится на его складах – величины it уравнения (3)). Введем переменные :ijy  1 , 1, , 1, , 1, . t ijt jt ijx y j n i m t T       (8) Тогда задача (2) – (7) компактно представляется в следующем виде: , , , , , 1 1 , 1 , 1 , 1 min 1 , n m n T m t m TT ij jT ij jt jt ij it it j i j t i i t c y R y                           (9) Т.В. БЕЛЫХ, Н.Г. ЖУРБЕНКО, И.Э. ШУЛИНОК 64 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 1 1 1, 1, , m T ij i y j n     (10) 1 1 , 1, , 1, , n t jt ij it it j y i m t T          (11) 1 0,ijty  1, , 1, , 1, ,i m j n t T   (12) 0,it it   1, , 1, .i m t T  (13) Нетрудно показать справедливость следующего утверждения. Предложение 1. Задачи (2) – (7), (9) – (13) эквиваленты. В силу простоты утверждения, его детальное доказательство не приводится. Достаточно следующих пояснений. Представление переменных ijtx в форме (8) обеспечивает выполнение ограничений (3). Из ограничений (10), (12) получаем (5): 1 1 1 1 1 m m tT ij ij i i y y         и, следовательно, ограничения (5). Метод решения. Прикладные задачи рассматриваемого класса могут иметь достаточно большую размерность: 1000,n  100,m  12.T  Формально число переменных такой задачи 1000000. Использовать стандартные солверы задач линейного программирования для решения таких задач без учета их специ- фической структуры не рационально. Предлагаемый метод решения основан на применении алгоритмов негладкой оптимизации в сочетании со схемой декомпозиции по связывающим ограничениям задачи [2]. Пусть itu – двойственные переменные относительно ограничений (11). Тогда двойственная задача будет состоять в следующем: max ( ), u u (14) где ( ) min ( , ), z D u L z u    (15) ( , )L z u – функция Лагранжа относительно ограничений (11); z – совокупность переменных ( , )ij ity   ; u – совокупность двойственных переменных itu ; D – множество, определенное системой ограничений (10), (12), (13). Нетрудно видеть, что решение задачи минимизации (15) представляется в следующем виде: , 1 1 1 , 1 ( ) ( ) ( ) , m Tn T n jt jt j it it j t j i t u R u u u               (16) , , 1 ( ) min ( ) , m T j ji ij i u c u y      ( 1, ),j n (17) ДИНАМИЧЕСКИЕ ПРОИЗВОДСТВЕННО-РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 65 , , 1 1, 0, m T ij ij i y y     , , 1 ( }) min{ ( ) : 0 . m T it it it it i t u u         (18) Коэффициенты ( )jic u и ( )i u определяются формулами: ) .(ji ij jT j T j t T i j t c c R uu             ( ) .it it itu u  Решение задачи минимизации (17) ( )ijy u , как легко видеть, задается формулой: * * * * 1, ( )) ( ( )) ( , ( ) 0, ( )) ( ( ( ) 0) ( ( ))) 0)( ( , ji ij ji i i j j c y u i i j j c u u                    (19) где *( )i j , *( )j какая-нибудь (она может быть не единственной) пара индексов, при которых достигается минимум в выражении * * , { ( ), ( )} min ( ).ji i i j j arc c u    (20) Решение задач минимизации (18) определяется, очевидно, формулой , ( ) 0 ( ) . 0, ( ) 0 it it it it u u u       Обобщенные градиенты функции ( )u определяются формулами 1 1 ( ) ( ) ( ) . it n t u jt ij it it j u y u u          Таким образом, решение двойственной задачи сводится к задаче безуслов- ной максимизации кусочно-линейной вогнутой функции ( ).u Отметим малую трудоемкость приведенных алгоритмов вычисления значений и обобщенных градиентов функции ( ).u Решение задачи состоит из двух этапов. На первом этапе на основе исполь- зования ( )r  -алгоритма [3] решается двойственная задача (14). ( )r  -алгоритм – это модификация r -алгоритма [4] с программным управлением значениями коэффициентов растяжения пространства. Обозначим 1J множество потребителей, для которых минимум в (20) дости- гается только для одной пары индексов (при полученных оптимальных значени- ях двойственных переменных). Для таких потребителей оптимальные поставки определяются непосредственно в результате решения двойственной задачи согласно (8). Т.В. БЕЛЫХ, Н.Г. ЖУРБЕНКО, И.Э. ШУЛИНОК 66 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 На втором этапе решается задача для остальных потребителей 2.J Обозна- чим 2n – число потребителей из 2J . Если исходная задача (2) – (7) имеет един- ственное решение, то для числа потребителей 2n справедлива оценка 2n mT (единственность решения обеспечивается малыми случайными возмущениями констант тарифов перевозки ijc ). Таким образом задача второго этапа имеет сравнительно небольшую размерность. Для ее решения можно использовать стандартные пакеты линейного программирования или алгоритмы восстановле- ния решения исходной задачи на основе решения ей двойственной [1, 2] (алго- ритм усреднения субградиентов, квадратичное возмущение задачи). Работа выполнена при частичной поддержке Volkswagen Foundation (грант No 90 306 – Н. Г. Журбенко). Т.В. Бєлих, М.Г. Журбенко, І.Е. Шулінок ДИНАМІЧНІ ВИРОБНИЧО-РОЗПОДІЛЬНІ ЗАДАЧІ Наводиться математична модель динамічних розподільних задач. Алгоритм розв'язання задач великої розмірності заснований на використанні методів негладкої оптимізації. T.V. Belykh, N.G. Zhurbenko, I.E. Shulinok DYNAMIC INDUSTRIAL-DISTRIBUTIVE PROBLEMS A mathematical model of dynamic distribution problems is given. The algorithm for solving large- scale problems is based on the use of nonsmooth optimization methods. Список литературы 1. Беляева Л.В., Журбенко Н.Г., Шор Н.З. О методе решения одного класса динамических распределительных задач. Экономика и математические методы. 1978. Т. ХIY. вып. 1. 2. Шор Н.З. Методы минимизации недифференцируемых функций и их применение. Киев: Наук. думка, 1979. 200 с. 3. Журбенко Н.Г. Численная эффективность одной модификации r-алгоритма. Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2017. С. 33 – 38. 4. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяже- ния пространства в направлении разности двух последовательных градиентов. Ки- бернетика. 1971. № 3. С. 51 – 59. Получено 04.03.2019

Ähnliche Einträge