Модели и алгоритмы многоцелевого линейного программирования

Досліджено окремий випадок постановки задачі векторної оптимізації — задачу багатоцільового лінійного програмування (ЛП), наведено її постановку, а також два найбільш поширені підходи до її розв’язання. Автор, використовуючи свої результати в області знаходження компромісних розв’язків для одного кл...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
1. Verfasser:	Павлов, А.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы оптимизации и оптимальное управление
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/208789
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:	Модели и алгоритмы многоцелевого линейного программирования / А.А. Павлов // Проблемы управления и информатики. — 2020. — № 6. — С. 5-15. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208789
record_format	dspace
spelling	irk-123456789-2087892025-11-06T13:51:45Z Модели и алгоритмы многоцелевого линейного программирования Моделі та алгоритми багатоцільового лінійного програмування Models and algorithms of multipurpose linear programming Павлов, А.А. Методы оптимизации и оптимальное управление Досліджено окремий випадок постановки задачі векторної оптимізації — задачу багатоцільового лінійного програмування (ЛП), наведено її постановку, а також два найбільш поширені підходи до її розв’язання. Автор, використовуючи свої результати в області знаходження компромісних розв’язків для одного класу задач комбінаторної оптимізації за умов невизначеності, модифікував їх для розв’язання задачі багатоцільового ЛП, обмеження якої задаються у вигляді опуклого компакту. В результаті цієї модифікації доведено два твердження, які дозволили отримати наступні результати: (а) для задачі багатоцільового ЛП в детермінованій постановці: знайдено нову властивість компромісного критерію, який є лінійною зваженою згорткою лінійних критеріїв; наведено п’ять нових критеріїв отримання компромісного розв’язку. Для кожного з наведених компромісних критеріїв сформульовано задачі ЛП, розв’язки яких є оптимальним компромісним розв’язком за відповідним критерієм; (б) сформульовано задачі багатоцільового ЛП в умовах невизначеності (при цьому невизначеність формалізується як в термінах теорії ймовірностей шляхом введення багатовимірних дискретних випадкових величин, так і в термінах теорії нечітких множин шляхом введення відповідних функцій приналежності нечітких дискретних множин). Наведено компромісні критерії та алгоритми отримання компромісних розв’язків як розв’язки відповідних задач ЛП для невизначеності обох типів; (в) наведено також змішані моделі багатоцільового ЛП для випадку, коли частина лінійних критеріїв детермінована, а решта задана в умовах невизначеності. У розглянутих критеріях використовуються експертні ваги, які запропоновано знаходити за емпіричною матрицею парних порівнянь за допомогою моделей оптимізації та відповідних критеріїв знаходження найкращого рішення, розроблених автором та його учнями. This paper examines a special case of the vector optimization problem formulation, the multipurpose linear programming (LP) problem. Its formulation is provided, as well as two most common approaches to its solution. The author uses his results in the field of finding compromise solutions for one class of combinatorial optimization problems under uncertainty. He has modified the results to solve the multipurpose LP problem with the constraints given in the form of a convex compact. As a result of this modification, two statements were proved, which made it possible to obtain the following results: (a) for the multipurpose LP problem in a deterministic formulation: a new property was found of the compromise criterion which is a linear weighted convolution of linear criteria; five new criteria for obtaining a compromise solution are provided; for each of the given compromise criteria, the LP problems are formulated, their solution is the optimal compromise solution for the corresponding criterion; (b) the problems of a multipurpose LP under uncertainty are formulated (the uncertainty is formalized both in terms of probability theory by introducing multidimensional discrete random variables, and in terms of fuzzy sets theory by introducing the corresponding membership functions of fuzzy discrete sets); compromise criteria and algorithms for obtaining compromise solutions by solving the corresponding LP problems for both types of uncertainty are presented; (c) mixed models of multipurpose LP are also given for the case when some of the linear criteria are deterministic, and the rest are specified uncertainly. The proposed criteria use expert weights, which are proposed to be found by the empirical matrix of paired comparisons using optimization models and the corresponding criteria for finding the best solution developed by the author and his students. 2020 Article Модели и алгоритмы многоцелевого линейного программирования / А.А. Павлов // Проблемы управления и информатики. — 2020. — № 6. — С. 5-15. — Бібліогр.: 6 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208789 519.854.2 10.1615/JAutomatInfScien.v52.i11.40 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление
spellingShingle	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление Павлов, А.А. Модели и алгоритмы многоцелевого линейного программирования Проблемы управления и информатики
description	Досліджено окремий випадок постановки задачі векторної оптимізації — задачу багатоцільового лінійного програмування (ЛП), наведено її постановку, а також два найбільш поширені підходи до її розв’язання. Автор, використовуючи свої результати в області знаходження компромісних розв’язків для одного класу задач комбінаторної оптимізації за умов невизначеності, модифікував їх для розв’язання задачі багатоцільового ЛП, обмеження якої задаються у вигляді опуклого компакту. В результаті цієї модифікації доведено два твердження, які дозволили отримати наступні результати: (а) для задачі багатоцільового ЛП в детермінованій постановці: знайдено нову властивість компромісного критерію, який є лінійною зваженою згорткою лінійних критеріїв; наведено п’ять нових критеріїв отримання компромісного розв’язку. Для кожного з наведених компромісних критеріїв сформульовано задачі ЛП, розв’язки яких є оптимальним компромісним розв’язком за відповідним критерієм; (б) сформульовано задачі багатоцільового ЛП в умовах невизначеності (при цьому невизначеність формалізується як в термінах теорії ймовірностей шляхом введення багатовимірних дискретних випадкових величин, так і в термінах теорії нечітких множин шляхом введення відповідних функцій приналежності нечітких дискретних множин). Наведено компромісні критерії та алгоритми отримання компромісних розв’язків як розв’язки відповідних задач ЛП для невизначеності обох типів; (в) наведено також змішані моделі багатоцільового ЛП для випадку, коли частина лінійних критеріїв детермінована, а решта задана в умовах невизначеності. У розглянутих критеріях використовуються експертні ваги, які запропоновано знаходити за емпіричною матрицею парних порівнянь за допомогою моделей оптимізації та відповідних критеріїв знаходження найкращого рішення, розроблених автором та його учнями.
format	Article
author	Павлов, А.А.
author_facet	Павлов, А.А.
author_sort	Павлов, А.А.
title	Модели и алгоритмы многоцелевого линейного программирования
title_short	Модели и алгоритмы многоцелевого линейного программирования
title_full	Модели и алгоритмы многоцелевого линейного программирования
title_fullStr	Модели и алгоритмы многоцелевого линейного программирования
title_full_unstemmed	Модели и алгоритмы многоцелевого линейного программирования
title_sort	модели и алгоритмы многоцелевого линейного программирования
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2020
topic_facet	Методы оптимизации и оптимальное управление
url	https://nasplib.isofts.kiev.ua/handle/123456789/208789
citation_txt	Модели и алгоритмы многоцелевого линейного программирования / А.А. Павлов // Проблемы управления и информатики. — 2020. — № 6. — С. 5-15. — Бібліогр.: 6 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT pavlovaa modeliialgoritmymnogocelevogolinejnogoprogrammirovaniâ AT pavlovaa modelítaalgoritmibagatocílʹovogolíníjnogoprogramuvannâ AT pavlovaa modelsandalgorithmsofmultipurposelinearprogramming
first_indexed	2025-11-07T02:35:37Z
last_indexed	2025-11-07T02:35:37Z
_version_	1848097308753788928
fulltext	© А.А. ПАВЛОВ, 2020 Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 6 5 МЕТОДЫ ОПТИМИЗАЦИИ И ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ УДК 519.854.2 А.А. Павлов МОДЕЛИ И АЛГОРИТМЫ МНОГОЦЕЛЕВОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Ключевые слова: многоцелевое линейное программирование, неопределен- ность, компромиссные критерии, компромиссные решения, вероятность, нечет- кое множество, эмпирическая матрица парных сравнений. Введение В [1, 2] для класса задач комбинаторной оптимизации вида  =   s i iik 1 )( max min , (1) где i — положительные весовые коэффициенты, )(ik — произвольная число- вая характеристика допустимого решения , — области допустимых ре- шений, численные значения коэффициентов sii ,1, = , могут принимать одно из возможных значений },1,{ sil i = , Ll ,1= . Для такой постановки задачи приве- дены компромиссные критерии и соответствующие им эффективные алгоритмы получения оптимальных компромиссных решений. В [3] рассмотрен прикладной пример решения такой задачи. В [4, 5] использованы и модифицированы компро- миссные критерии для решения однопродуктивных и многопродуктивных транс- портных задач в условиях неопределенности. В данной статье показано, что полу- ченные в [1, 2, 4, 5] результаты могут использоваться для нахождения новых свойств известных критериев, введения новых критериев и соответствующих им алгоритмов в задаче многоцелевого линейного программирования (ЛП) [6], а так- же позволяют сформулировать новую постановку задачи линейного целевого про- граммирования в условиях неопределенности и предложить новые компромисс- ные критерии и соответствующие им эффективные алгоритмы нахождения опти- мальных компромиссных решений. Постановка задачи многоцелевого ЛП заключается в следующем [6]. Имеют- ся линейные ограничения, которые для удобства дальнейшего изложения пред- ставим в стандартной форме njxbAx j ,1,0, == , (2) где njmiaA ij ,1,,1),( === , T 1 )...,,( mbbb = , iij ba , — известные действитель- ные числа. jx , nj ,1= — переменные. Задано k линейных функционалов Llxcl x ,1,min T = , )...,,( 1 T lnll ccc = , lic — заданные действительные числа. 6 ISSN 0572-2691 Примечание 1. Некоторые числа lic могут тождественно равняться нулю, ес- ли они соответствуют неотрицательным переменным, превращающим неравен- ства в равенства. В классической постановке задачи многоцелевого ЛП требуется сформулировать критерии и соответствующие им алгоритмы нахождения ком- промиссного вектора x , которому соответствует оптимальное значение выбран- ного компромиссного критерия. Примечание 2. Некоторые из функционалов могут иметь вид xcl x Tmax . Это не сужает сформулированную задачу, так как )(minmax TT xcxc l x l x −= . Рассмотрим наиболее распространенные подходы к решению этой задачи: 1) вводятся положительные весовые коэффициенты 0l важности крите- рия Llxcl x ,1,min T = , и решается задача njxbAxxc j L l ll x ,1,0,,min 1 T == = ; 2) пусть Llll  21 , решается задача ,min T 1 xc l x ,bAx = ,0jx nj ,1= . Пусть оптимальное значение ее функционала равно 1 optf . Решается вторая задача ЛП: njxfxcbAxxc jll x ,1,0,,,min 1 opt TT 12 === . Описанная процедура продолжается. Последней задачей ЛП является njxLifxcbAxxc j i ll x iL ,1,0,1,1,,,min opt TT =−=== . Покажем, что для случая, когда njxbAx j ,1,0, == , выпуклым компактом является модификация результатов, приведенных в [1, 2, 4, 5]. Во-первых, это позволяет конкретизировать свойства компромиссного решения, полученного при использовании описанного выше первого подхода; во-вторых, ввести новые компро- миссные критерии и соответствующие им оптимальные компромиссные решения. Примечание 3. Условие, что ,,1,0, njxbAx j == — выпуклый компакт, не ограничивает область практического применения изложенных ниже результатов, поскольку ни в одной практической задаче реализуемый вектор решения не со- держит не ограниченных по модулю компонент. Компромиссные критерии для задачи многоцелевого линейного программи- рования в детерминированной постановке Введем следующие компромиссные критерии. Критерий 1. Найти вектор opt 1x , которому соответствует njxbAxfxc j L l l ll x ,1,0,,)(min 1 opt T ==− = , (3) где ,,1,0 Lll = — известные экспертные коэффициенты, а njxbAxxcf jl x l ,1,0,,min T opt === . Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 6 7 Примечание 1. Далее будет показано, что решение задачи (3) является опти- мальным компромиссным решением, реализующим описанный во введении из- вестный первый подход. Примечание 2. Для критерия 1 условие, что njxbAx j ,1,0, == , — выпуклый компакт, не является обязательным. Критерий 2. Пусть 1,,1, 1 llLlll = . Найти вектор opt 2x , удовлетво- ряющий следующим условиям: 1 opt T 2 arg{min , , 0, 1, }jl x x c x Ax b x j n= =  = , (4) 1 1 opt T opt2 { } 1, arg min ( ) l L l l x x l l l x c x f  =  = − , (5) где 1 }{ lx — множество оптимальных решений задачи ЛП (4). Примечание. Аналогично задаются множества оптимальных решений Llx l ,1,}{ = . Критерий 3 (обобщение критерия 2). Найти вектор opt 3x , удовлетворяющий следующим условиям: 1 opt T opt3 1 arg min ( ), , 0, 1,j j j k t t jt x j x c x f Ax b x j n =    =  − =  =      , (6) 2 1 opt T opt3 { } 1 arg min ( )l l l k k p p p x x l x c x f  =    =  −      , где Lkkklpkjt lj =+=== 2121 },{},1,{},1,{  ; 1 }{ kx — множество оптималь- ных решений задачи ЛП (6); Lll ,1,0 = , — экспертные коэффициенты, за- данные выше. Примечание 1. Ограничения задачи ЛП (6) могут иметь вид T opt ˆ, 0, 1, , , 0, 1, p j p n p p n pAx b x j n c x f x l x p L+ +=  = − + =   = , где 0ˆ pl — экспертные ограничения. Примечание 2. Наиболее практичным является следующий частный случай критерия 3: opt T opt3 1 arg min ( ), , 0, 1,j j j k l l jl x j x c x f Ax b x j n =    =  − =  =      , (7) opt T opt3 { } 1 arg min ( )j j j k L l l l x x j k x c x f  = +    =  −      , (8) где kx}{ — множество оптимальных решений задачи ЛП (7); Ljj ,1, = , удо- влетворяют неравенствам Llll  21 . 8 ISSN 0572-2691 Критерий 4. Для заданных экспертных чисел Ljl j ,1,0ˆ = , найти век- тор opt 4x , удовлетворяющий условиям         ==−=  = njxbAxlx jrr L r r x ,1,0,),ˆ,0max(minarg 1 1opt 4 , (9) где Lrfxc r rr ,1,opt T =−= ; Lrr ,1,01 = , — экспертные коэффициенты важ- ности нарушения r -го ограничения; r r r lfxc ˆ opt T − . Критерий 5. Для заданных экспертных чисел 1,1,0 kj jt = , 2,1,0ˆ kll lp = , найти вектор opt 5x , удовлетворяющий условиям 1 opt T T 2opt opt5 1 ˆarg min ( ), , 0, 1, , , 1,j l j lj l k t p t j pt p x j x c x f Ax b x j n c x f l l k =    =  − =  = −  =      . Критерий 6. Для заданных экспертных чисел 1,1,0 kj jt = , 2 1 ,1,0ˆ,0 kll ll pp = , найти вектор opt 6x , удовлетворяющий условиям 1 2 opt T 1 opt5 1 1 ˆarg min ( ) max(0, ) ,j j l lj l k k t t p pt p x j l x c x f l = =    =  − +   −           == njxbAx j ,1,0, , (10) где T 2opt , 1,l l l p p p c x f l k = − = . Построение оптимальных алгоритмов, реализующих компромиссные крите- рии 1–6, непосредственно вытекает из следующих двух утверждений. Утверждение 1. Рассмотрим многоцелевую задачу ЛП (2). Тогда для ,0 la Ll ,1= , имеет место равенство opt 1 1 1 1 arg min ( ) arg min j j L n n L l l l j l l j x xl j j l a c x f a c x  = = = =      − =            , (11) где  — произвольное выпуклое множество относительно переменных ,jx nj ,1= , вектора x , xcf l x l T opt min  = . Примечание. Так как при построении оптимальных алгоритмов, реализую- щих компромиссные критерии 1–6, линейные ограничения используемых задач ЛП могут иметь различный вид, в утверждении 1 задается произвольное выпуклое множество  . Доказательство. 0,, opt T − l l fxcxl . Таким образом, левая часть равенства (11) определяет вектор x , которому соответствует минимум суммы неотрицательных слагаемых. Следовательно, 0min)(min opt 11 11 opt 1 −                 =         −   == === l L l l n j j L l ll x n j l jl L l l x faxcafxca jj , (12) откуда очевидным образом следует справедливость утверждения 1. Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 6 9 Примечание. Утверждение 1 является частным случаем утверждения 5 [1]. Действительно, в данном примере ns = , а nixk ii ,1,)( == . Утверждение 2. Рассмотрим задачу комбинаторной оптимизации  = − L l l ll x fxca 1 opt T )(min , (13) где 0la ,  — произвольный выпуклый компакт, образованный конечным чис- лом линейных ограничений. Пусть коэффициенты jl llLla = ,,1, , фиксирован- ные. Тогда существует такое конечное положительное число 0*  jla , что для всех * jj ll aa  для произвольного оптимального решения optx задачи комбинаторной оптимизации (13) выполняется 0optopt T =− j j l l fxc . Доказательство. Множество вершин выпуклого компакта  конечно (обо- значим его  ). Для произвольного вектора c существует не менее одной вершины  ( — выпуклый компакт), на которой достигается xc x Tmin  . В силу утверждения 1   = ==         =− n j j L l ll x l l L l l x xcafxca j 1 1 opt T 1 minarg)(minarg . (14) Пусть jlx}ˆ{ — множество всех вершин  , каждая из которых является оптимальным решением задачи ЛП j j l l x fxc opt Tmin =  . (15) Тогда 0)(max opt T 1}ˆ{ − = l l L l l xx fxca jl — конечное число, которое от значения коэф- фициента 0 jla не зависит. Следовательно, всегда существует такое положи- тельное число jla , что для всех * jj ll aa  , при фиксированных конечных значени- ях jl llLla = ,,1,0 , выполняется неравенство jlxx }ˆ{  == −− L l l ll xx l l L l l fxcafxca jl 1 opt T }ˆ{\ opt T 1 )(min)( * . Утверждение 2 доказано. Примечание. * jj ll aa  , при фиксированных значениях коэффициентов jl llLla = ,,1, , jj l n j j L l ll x xxca }{minarg 1 1            = = . (16) Тогда на произвольном оптимальном решении (16) в силу равенства (14) достигается )(min opt T 1}{ l l L ll l l xx fxca j jl −  = . (17) 10 ISSN 0572-2691 Построение оптимальных компромиссных решений, соответствующих критериям 1–6 Критерий 1. Оптимальное компромиссное решение по критерию 1 в силу утверждения 1 является решением следующей задачи ЛП:         ===  = njxbAxxcx j L l ll x ,1,0,,minarg 1 Topt 1 . Критерий 2. Необходимо подобрать такое достаточно большое положитель- ное число 0 1 la , которое в силу утверждения 2 всегда существует, при этом оп- тимальное решение задачи ЛП 1 }{,1,0,,minarg 1 1 l n j jj L l ll x xnjxbAxxca j          ==           = = . Это решение и является оптимальным компромиссным вектором opt 2x в силу примечания к утверждению 2 (равенство (5) выполняется автоматически). Критерий 3. Сначала решаем следующую задачу ЛП:   = = ==          n i ji k j itt x njxbAxxc jj 1 1 , ,1,0,,min 1 . (18) Затем подбираем такое достаточно большое положительное число 0 1 ka , которое в силу утверждения 2 всегда существует, при этом оптимальное ре- шение задачи ЛП         ==         +           == njxbAxxcca j k l pp k j ttk x lljj ,1,0,,minarg 21 1 1 T 1 T является оптимальным решением задачи ЛП (18). Полученное решение — опти- мальный компромиссный вектор opt 3x в силу примечания к утверждению 2. Критерий 4. Сначала находим числа lfopt — оптимальные значения функци- оналов следующих задач ЛП: njxbAxfxc j l l x ,1,0,,min opt T === . Оптимальное компромиссное решение opt 4x по критерию 4 является решени- ем следующей задачи ЛП: LrzlfzxcnjxbAxz rr r rrj L r rr x ,1,0,ˆ;,1,0,,min opt T 1 1 =+−== = . (19) Критерий 5. Сначала решаются 2k задач ЛП 2opt T ,1,,1,0,,min klnjxbAxfxc j p p x l l ==== . В силу утверждения 1 вектор opt 5x — решение следующей задачи ЛП: 2opt T 1 T ,1,ˆ;,1,0,,min 1 kllfxcnjxbAxxc l l ljj p p pj k r tt x =−== = . (20) Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 6 11 Критерий 6. Сначала решаются 2k задач ЛП: 2opt T ,1,,1,0,,min klnjxbAxfxc j p p x l l ==== . Вектор opt 6x — решение следующей задачи ЛП: ;,1,0,,min 21 2 1 1 1 T ,1 , njxbAxzxc j k l pp k j tt kl zx lljj lp ==         +  == = 2opt T ,1,0,ˆ klzlfzxc ll l ll pp p pp =+− . (21) Действительно, в силу очевидной модификации утверждения 1 ( ,0 lpz 01  lp выражение 02 1 1  = k l pp ll z ) решение задачи ЛП (21) является компро- миссным решением по критерию 6. Многоцелевое линейное программирование в условиях неопределенности Постановка задачи. Как было показано выше, задача многоцелевого ЛП в детерминированной постановке имеет следующий вид: имеются линейные огра- ничения, заданные в стандартной форме задачи ЛП njxbAx j ,1,0, == , кото- рые являются выпуклым компактом, и L линейных функционалов Llxcl x ,1,min T = (функционал )(minmax TT xcxc l x l x −= ). Постановка этой задачи в условиях неопределенности заключается в том, что значения коэффициентов векторов lc (числа Llnjclj ,1,,1, == ) не определены. Эта неопределенность в данной работе формализуется в терминах теории вероят- ностей либо в терминах теории нечетких множеств. Задаются случайные величины LlfxcF l n j jlj x l ,1,ˆˆmin opt 1 T =−=  = , (22) где 1+n -мерные дискретные случайные величины Llfcc l lnl ,1,ˆ,ˆ,,ˆ opt1 = , за- даются таблицами вида lT m m l m l lm opt m ln m l TmLl PP fcc l ,1,,1, 1,0 ,,, 1 1 ==             =  =  , (23) где .,1,0,,min 1 opt njxbAxxcf j n j j m lj x lm ===  = (24) Задаются нечеткие дискретные множества llmm ln m l m l lmm ln m l TmLl fcc fcc ,1,,1, 1),,,(0 ,,, opt1 opt1 ==            , (25) где m l lmm ln m l m l fcc = ),,,( opt1  — степень достоверности (значение функции при- надлежности нечеткого множества) того, что коэффициенты l -го функционала 12 ISSN 0572-2691 примут значения m ln m l cc ,,1  , а lmfopt — оптимальное значение функционала задачи ЛП (24), соответствующего этим значениям. Для такой постановки задачи многоцелевого ЛП в условиях неопределенности вводим следующие компромиссные критерии (всюду Ljj ,1,0 = , — извест- ные экспертные коэффициенты). Критерий 1a. Найти вектор opt 1ax , удовлетворяющий условиям         ===  = njxbAxMFx j l L l l x a ,1,0,,minarg 1 opt 1 , где ])[( opt T 1 lmm l T m m l l fxcPMF l −= = — математическое ожидание случайной вели- чины LlF l ,1, = . Критерий 1b. Найти вектор opt 1bx , удовлетворяющий условиям         ==−=  == njxbAxfxcx j lmm l T m m l L l l x b l ,1,0,],)[(minarg opt T 11 opt 1 . В дальнейшем для сокращения записи будем обозначать символом )( fuz l нечеткий аналог lMF : Llfxc lmm l T m m l fuz l l ,1],)[()( opt T 1 =−=  = . Пусть 021  Llll  . Критерий 2a. Найти вектор opt 2ax , удовлетворяющий условиям },1,0,,minarg{ 1 2 njxbAxMFx j l x opt a === , (26)         =  = l L lllxx a MFx Fl 1 )(1 ,1}{ opt 2 minarg , где )(1 }{ Flx — множество оптимальных решений задачи ЛП (26). Критерий 2b. Найти вектор opt 2bx , удовлетворяющий условиям },1,0,),(minarg{ 12 njxbAxx j fuz l x opt b === , (27)         =  =  )(minarg 1)(1 ,1}{ opt 2 fuz l L lllxx b fuzl x , где )(1 }{ fuzl x  — множество оптимальных решений задачи ЛП (27). Критерий 3a. Найти вектор opt 3ax , удовлетворяющий условиям         ===  = njxbAxMFx j k j t t x a j j ,1,0,,minarg 1 1 opt 3 , (28)         =  = 2 )(1 1}{ opt 3 minarg k l p p xx a l l Fk MFx , Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 6 13 где )(1 }{ Fkx — множество оптимальных решений задачи ЛП (28); === },1,{},1,{ 21 klpkjt lj  Lkk =+ 21},{ . Критерий 3b. Найти вектор opt 3bx , удовлетворяющий условиям         ===  = njxbAxx j fuz t k j t x b jj ,1,0,),(minarg 1 1 opt 3 , (29)         =  =  )(minarg 2 )(1 1}{ opt 3 fuz p k l p xx b ll fuzk x , где )(1 }{ fuzk x  — множество оптимальных решений задачи ЛП (29); === },1,{},1,{ 21 klpkjt lj  Lkk =+ 21},{ . Многоцелевое линейное программирование в условиях неопределенности. Смешанные модели Постановка задачи. Рассматривается следующая модификация условий (23), (25). Условия (23), (25) относятся только к критериям с номерами 1,1, kjt j = . Множество критериев с номерами 2,1, klpl = , }{},1,{},1,{ 21 === klpkjt lj  , Lkk =+ 21 , соответствуют детерминированной постановке задачи многоцелевого ЛП. Такая ситуация возможна, когда множество критериев },1,{ 1kjt j = опреде- ляет эффективность в отдаленной перспективе. Для такой постановки задачи модификация критерия 4 (детерминированная постановка) теряет смысл. Критерий 5a. Для заданных экспертных чисел 2,1,0ˆ kll lp = , найти вектор opt 5ax , удовлетворяющий условиям         =−===  = 2 T 1 opt 5 ,1,ˆ,,1,0,,minarg 1 kllfxcnjxbAxMFx l l l j j p p optpj k j t t x a . Критерий 5b. Для заданных экспертных чисел 2,1,0ˆ kll lp = , найти вектор opt 5b x , удовлетворяющий условиям         =−===  = 2opt T 1 opt 5 ,1,ˆ,,1,0,,)(minarg 1 kllfxcnjxbAxx l l ljj p p pj k j fuz tt x b . Критерий 6a. Для заданных экспертных чисел 1,1,0 kj jt = , 2 1 ,1,0ˆ,0 kll ll pp = , найти вектор opt 6ax , удовлетворяющий условиям:         ==         −+=  == njxbAxlMFx jpp k l p k j t t x a lll j j ,1,0,,)ˆ,0max(minarg 21 1 1 1 opt 6 , где 2opt T ,1, klfxc l ll p pp =−= . 14 ISSN 0572-2691 Критерий 6b. Найти вектор opt 6bx , удовлетворяющий условиям:         ==         −+=  == njxbAxlx jpp k l p k j fuz tt x b llljj ,1,0,,)ˆ,0max()(minarg 21 1 1 1 opt 6 . В силу утверждений 1, 2 алгоритмы построения оптимальных компромисс- ных решений по критериям 1a–3a, 5a, 6a, 1b–3b, 5b, 6b являются очевидной моди- фикацией алгоритмов построения оптимальных компромиссных решений для критериев с номерами 1, 2, 3, 5, 6. В заключение отметим, что предложенные линейные модели содержат экс- пертные веса. В [2] автор систематизировал полученные им и его учениками ре- зультаты для нахождения экспертных весов по эмпирической матрице парных сравнений. В [2] приведены статистически подтвержденные эффективные модели оптимизации для нахождения оценок экспертных весов, обоснованный критерий выбора наилучших оценок, а также критерий оценки достоверности полученных результирующих оценок экспертных весов. Эффективность предложенных моде- лей, критериев и методов существенно не зависят от размерности эмпирической матрицы парных сравнений и возможной ее неполной заполненности (значения ее некоторых элементов могут отсутствовать). Заключение На основе теоретических результатов, ранее полученных автором при иссле- довании одного класса задач комбинаторной оптимизации в условиях неопреде- ленности, получены новые критерии и соответствующие им алгоритмы опти- мальных компромиссных решений для следующих задач: 1) многоцелевого ЛП в детерминированной постановке; 2) многоцелевого ЛП в условиях неопределенности; 3) многоцелевого ЛП в смешанной постановке. Формальные модели многоцелевого ЛП в условиях неопределенности приве- дены как в терминах теории вероятностей, так и в терминах нечетких множеств. ABSTRACTS О.А. Павлов МОДЕЛІ ТА АЛГОРИТМИ БАГАТОЦІЛЬОВОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ Досліджено окремий випадок постановки задачі векторної оптимізації — задачу багатоцільового лінійного програмування (ЛП), наведено її постановку, а також два найбільш поширені підходи до її розв’язання. Автор, використовуючи свої результати в області знаходження компромісних розв’язків для одного класу задач комбінаторної оптимізації за умов невизначеності, модифікував їх для розв’язання задачі багатоцільового ЛП, обмеження якої задаються у вигляді опуклого компакту. В результаті цієї модифікації доведено два твердження, які дозволили отримати наступні результати: (а) для задачі багатоцільового ЛП в детермінованій постановці: знайдено нову властивість компромісного критерію, який є лінійною зваженою згорткою лінійних критеріїв; наведено п’ять нових критеріїв отримання компромісного розв’язку. Для кожного з наведених компромісних критеріїв сформульовано задачі ЛП, розв’язки яких є оптимальним компромісним розв’язком за відповідним критерієм; (б) сформульовано задачі багатоцільового ЛП в умовах невизначеності (при цьому невизначеність формалізується як в термінах теорії ймовірностей шляхом введення багатовимірних дискретних випадкових величин, так і в термінах теорії нечітких множин шляхом введення відповідних функцій приналежності нечітких дискретних множин). Наведено компромісні критерії та алгоритми отримання компромісних розв’язків як розв’язки відповідних задач ЛП для невизначеності обох типів; (в) наведено також змішані моделі багатоцільового ЛП для випадку, коли частина лінійних критеріїв детермінована, а решта задана в умовах невизначеності. Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 6 15 У розглянутих критеріях використовуються експертні ваги, які запропоновано знаходити за емпіричною матрицею парних порівнянь за допомогою моделей оптимізації та відповідних критеріїв знаходження найкращого рішення, розробле- них автором та його учнями. Ключові слова: багатоцільове лінійне програмування, невизначеність, комп- ромісні критерії, компромісні розв’язки, ймовірність, нечітка множина, емпі- рична матриця парних порівнянь. A.A. Pavlov MODELS AND ALGORITHMS OF MULTIPURPOSE LINEAR PROGRAMMING This paper examines a special case of the vector optimization problem formulation, the multipurpose linear programming (LP) problem. Its formulation is provided, as well as two most common approaches to its solution. The author uses his results in the field of finding compromise solutions for one class of combinatorial optimization problems under uncertainty. He has modified the results to solve the multipurpose LP problem with the constraints given in the form of a convex compact. As a result of this modification, two statements were proved, which made it possible to obtain the following results: (a) for the multipurpose LP problem in a deterministic formulation: a new property was found of the compromise criterion which is a linear weighted convolution of linear criteria; five new criteria for obtaining a compromise solution are provided; for each of the given compromise criteria, the LP problems are formulated, their solution is the optimal compromise solution for the corresponding criterion; (b) the problems of a multipurpose LP under uncertainty are formulated (the uncertainty is formalized both in terms of probability theory by introducing multidimensional discrete random variables, and in terms of fuzzy sets theory by introducing the corresponding membership functions of fuzzy discrete sets); compromise criteria and algorithms for obtaining compromise solutions by solving the corresponding LP problems for both types of uncertainty are presented; (c) mixed models of multipurpose LP are also given for the case when some of the linear criteria are deterministic, and the rest are specified uncertainly. The proposed criteria use expert weights, which are proposed to be found by the empirical matrix of paired comparisons using optimization models and the corresponding criteria for finding the best solution developed by the author and his students. Keywords: multipurpose linear programming, uncertainty, compromise criteria, compro- mise solutions, probability, fuzzy set, empirical matrix of pairwise comparisons. REFERENCES 1. Pavlov A.A. Optimization for one class of combinatorial problems under uncertainty. Адаптивні системи автоматичного управління. 2019. 1. N 34. С. 81–89. DOI: 10.20535/1560- 8956.1.2019.178233. 2. Pavlov A.A. Combinatorial optimization under uncertainty and formal models of expert estima- tion. Вісник Національного технічного університету «ХПІ». Серія: Системний аналіз, уп- равління та інформаційні технології. 2019. № 1. С. 3–7. DOI: 10.20998/2079- 0023.2019.01.01. 3. Pavlov A.A. Long-term operational planning of a small-series production under uncertainty (theory and practice). The Third International Conference on Computer Science, Engineering and Education Applications (ICCSEEA 2020). 2021. P. 167–180. DOI: 10.1007/978-3-030-55506-1_15. 4. Павлов А.А., Жданова Е.Г. Транспортная задача в условиях неопределенности. Междуна- родный научно-технический журнал «Проблемы управления и информатики». 2020. № 2. С. 34–45. [Pavlov A.A., Zhdanova E.G. The Transportation Problem under Uncertainty. Journal of Automation and Information Sciences. 2020. 52, N 4. P. 1–13. DOI: 10.1615/JAutomatInfScien.v52.i4.10.] 5. Pavlov A.A., Zhdanova E.G. Finding a compromise solution to the transportation problem under uncertainty. Адаптивні системи автоматичного управління. 2020. 1. № 36. С. 60–72. DOI: 10.20535/1560-8956.36.2020.209764. 6. Таха Х.А. Введение в исследование операций. М. : Вильямс, 2005. 912 с. Получено 21.09.2020

Модели и алгоритмы многоцелевого линейного программирования

Institution

Ähnliche Einträge