Деякi детермінованi моделi задач нечіткого лінійного програмування
We consider deterministic equivalents of various formulations of linear programming prob-lems, in which the coefficients of the objective function, constraints and the boundary values of the variables of the problem and the right-hand side are represented by fuzzy sets. The methods for comparing the...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2016
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/65806 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334264115167232 |
|---|---|
| author | Zack, Y. A. |
| author_facet | Zack, Y. A. |
| author_institution_txt_mv | [
{
"author": "Y. A. Zack",
"institution": null
}
] |
| author_sort | Zack, Y. A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2016-07-25T14:59:53Z |
| description | We consider deterministic equivalents of various formulations of linear programming prob-lems, in which the coefficients of the objective function, constraints and the boundary values of the variables of the problem and the right-hand side are represented by fuzzy sets. The methods for comparing the fuzzy sets and selecting the best ones are proposed. The problem of finding the vec-tor of variables as a vector of real numbers is reduced to solving the one-criterion or multicriteria problem with the significantly large number of constraints. In solving the problem as a vector of Fuzzy-sets, the equivalent problem was determined – a sequence of linear programming problems. The formulated problems can be solved by the simplex method. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2016.1.12 |
| first_indexed | 2025-07-17T10:20:08Z |
| format | Article |
| fulltext |
© Ю.А. Зак, 2016
120 ISSN 1681–6048 System Research & Information Technologies, 2016, № 1
TIДC
МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ,
ПРОБЛЕМИ І ТЕХНОЛОГІЇ ДОСЛІДЖЕННЯ
СКЛАДНИХ СИСТЕМ
УДК 519.85
DOI: 10.20535/SRIT.2308-8893.2016.1.12
НЕКОТОРЫЕ ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ ЗАДАЧ
НЕЧЕТКОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Ю.А. ЗАК
Рассмотрены детерминированные эквиваленты различных постановок задач
линейного программирования, в которых коэффициенты функции цели, огра-
ничений и граничные значения переменных задачи и правых частей нера-
венств представлены нечеткими множествами. Предложены методы сравнения
и определения предпочтения нечетких множеств. Решение задачи при поиске
вектора переменных в виде вектора действительных чисел сводится к реше-
нию однокритериальной или многокритериальной задачи с существенно
большим количеством ограничений. При решении задачи в виде вектора
Fuzzy-множеств детерминировано эквивалент задачи — последовательность
задач линейного программирования. Сформулированные задачи могут быть
решены симплексным методом.
ВВЕДЕНИЕ
В литературе рассматривались различные постановки и математические мо-
дели задач нечеткого линейного программирования, когда коэффициенты
функций цели, ограничений и граничные значения являются не действи-
тельными числами, а некоторыми нечеткими множествами (см., например,
[1–9]), выбор среди множества альтернатив [16], а также анализ различных
приложений [10] и алгоритмов решения этих задач [1, 2, 3, 8, 11]. Решение
задачи можно искать в виде как вектора действительных, целочисленных,
булевых переменных, так и нечетких множеств, функции принадлежности
которых определены с точностью до неизвестных параметров. В зависимо-
сти от интерпретации условий выполнения ограничений, правые части ко-
торых представлены в виде Fuzzy-множеств, и принятых правил предпочте-
ния в этих условиях одного из значений критериев оптимальности перед
другими могут быть предложены и рассматривались в литературе различно-
го вида детерминированные эквиваленты сформулированных задач нечетко-
го линейного программирования.
В отличие от известных публикаций в данной работе строится детер-
минированный эквивалент сформулированной задачи в общем виде: в усло-
виях, когда коэффициенты функции цели и ограничений задачи — нечеткие
множества, наличия двухсторонних ограничений на переменные задачи,
представленных в виде нечетких множеств. Решение задачи ищется в виде
как вектора детерминированных переменных, так и вектора нечетких мно-
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 121
жеств с функциями принадлежности, определенными с точностью до неиз-
вестных параметров (в виде некоторого подмножества значений крайних
точек их функций принадлежности). Показано, что для функций принадле-
жности нечетких множеств треугольного или трапециевидного вида и выб-
ранного математического аппарата сравнения, ранжирования и проверки
выполнения нечетких ограничений (сравнения различных сечений и дискре-
тных α-уровней Fuzzy-множеств) исходная задача сводится к решению ряда
детерминированных задач линейного программирования. В результате
предложенных преобразований количество ограничений увеличивается как
минимум в два раза, но полученную задачу уже можно решить симплекс-
ным методом. Обсуждаются методы решения сформулированных многок-
ритериальных задач. В случае использования в качестве критерия опти-
мальности экстремального значения координаты абсцисс центра тяжести,
полученного в результате решения задачи нечеткого множества, сформули-
рованная задача может быть решена методами нелинейного программиро-
вания. Для задач нечеткого булевого программирования могут быть
предложены эффективные детерминированные эквиваленты и более эффек-
тивные алгоритмы решения [11, 13].
ПОСТАНОВКА ЗАДАЧИ
Детерминированная задача линейного программирования может быть
сформулирована, например, в виде:
,max)(
1
∑
=∈
• =
n
j
jj
GX
xcXf , (1)
,,...,1,;,...,1,| 21
1 ⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
=≤≤=≤== ∑
=
njhxhmibxaXG jjjij
n
j
ijiϕ (2)
где ),...,,....,,( 21 nj xxxxX = — вектор действительных чисел, на каждую
компоненту которого в общем случае накладываются двухсторонние огра-
ничения вида jjj hxh 21 ≤≤ , nj ,...,1= , а jc , ija , nj ,...,1= , mi ,...,1= , —
соответственно коэффициенты линейных функций цели и ограничений.
В частных случаях на все или отдельные компоненты вектора оптими-
зируемых параметров X могут накладываться ограничения целочислен-
ности, или требования принимать только булевы значения.
В условиях размытых данных, т.е. нечеткой постановки задачи, коэф-
фициенты и параметры функции цели )(Xf , функций ограничений )(Xiϕ ,
mi ,...,1= , а также граничные значения 1
jh и 2
jh , nj ,...,1= , могут быть пред-
ставлены не детерминированными величинами, а нечёткими множествами.
Кроме того, вектор оптимизируемых параметров X в соответствии с усло-
виями задачи может быть также представлен в виде некоторого нечёткого
множества, определенного с точностью до неизвестных детерминированных
параметров.
Формы нечеткого описания исходной информации могут быть различ-
ными. Ниже приводятся наиболее часто встречающиеся в литературе поста-
новки и математические формулировки таких задач в условиях размытых
данных. Автору не известны рассматриваемые в литературе задачи Fuzzy-
линейного программирования с двухсторонними ограничениями на пере-
менные.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 122
Задача 1. В задаче (1), (2) параметры функции цели и ограничений,
а также допустимые граничные значения вектора переменных задачи — не-
четкие множества c заданными функциями принадлежности. Решение зада-
чи ищется в виде вектора действительных чисел.
Частным случаем рассматриваемой задачи является задача нечёткого
линейного (Fuzzy-линейного) программирования в виде
,max2211 →⊕⊕⊕⊕⊕ nnjj xCxCxCxC
v
K
v
K
vv
(3)
ininjijiii BxAxAxAxA Re2211 ...... ≤⊕⊕⊕⊕⊕=Ψ , mi ,...,1= , (4)
,2
ReRe
1
jjj HxH ≤≤ .,,1 nj K= (5)
Здесь jC , 21 , jj HH , nj ,...,1= ; iB , mi ,...,1= ; ijA , mi ,...,1= , nj ,...,1= , —
нечёткие множества с заданными функциями принадлежности; jj xC
и jij xA — операции умножения нечётких множеств на действительное
число, результатом выполнения которых является также нечёткое множест-
во; ppjj xCxC ⊕ — операции сложения двух нечётких множеств, результа-
том которой также является нечёткое множество.
Обобщением задачи (3)–(5) является многокритериальная задача нечёт-
кого линейного программирования, в которой не один, а несколько критери-
ев оптимальности
,max......2211 →⊕⊕⊕⊕⊕= npnjpjppp xCxCxCxCF Pp ,...,1= . (6)
Рассмотрим задачу нечёткого линейного программирования вида
(3)–(5) в условиях, когда HX ~
∈ — вектор детерминированных переменных,
на которые наложены двухсторонние ограничения:
},...,1,|{~ 21 njhxhXH jjj
n =≤≤ℜ∈= . (7)
Здесь nj CCCC ,...,,...,, 21 — Fuzzy-числа (нечёткие множества), представ-
ленные LR -интервалами LRjjjj cacmcmca )}(),(),(),({ 2211 , nj ,...,1= ; ijA —
также нечёткие множества, представленные LR -интервалами вида
LRijijijij AaAmAmAaa )}(),(),(),({ 2211 , mi ,...,1= , ;,...,1 nj =
iB — нечёткие множества, представленные LR -интервалами вида
LRiiii BaBmBmBa )}(),(),(),({ 2211 , .,...,1 mi =
Определенный интерес представляет постановка задачи (задача 2),
в которой ija и jc , mi ,...,1= , nj ,...,1= , — действительные числа, а гранич-
ные значения iB , mi ,...,1= , а также 1
jH и 2
jH , nj ,...,1= , и вектор перемен-
ных задачи ),...,,...,,( 21 nj XXXX — нечеткие множества.
Задача 2.
max......2211 →⊕⊕⊕⊕⊕ nnjj XcXcXcXc , (8)
ininjijiii BXaXaXaXa Re2211 ...... ≤⊕⊕⊕⊕⊕=Ψ , mi ,...,1= ; (9)
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 123
2
ReRe
1
jjj HXH
rr
≤≤ , .,...,1 nj =
Функции принадлежности таких нечётких множеств A , представлен-
ных трапециевидными LR -интервалами, вычисляются по формулам, приве-
денным, например, в работе [9].
Условия Re≤ или Re≥ определяют условия доминирования (предпочте-
ния) двух нечётких множеств соответственно в сторону уменьшения или
увеличения их значений. Знаком ⊕ определяется алгебраическая сумма
двух нечётких множеств.
В результате выполнения соответствующих операторов Fuzzy-
арифметики для выражений (8) рассчитываются параметры нечётких мно-
жеств, представленных LR -интервалами LRDDMM },,,{ 0
2
0
1
0
2
0
1 — для целе-
вой функции и LR
iiii DDMM },,,{ 2121 , mi ,...,1= , — для левых частей функций
ограничений.
Если решение задачи ищется в виде детерминированного вектора буле-
вых переменных 10∨=jx , nj ,...,1= , то результаты выполнения соответст-
вующих операторов Fuzzy-арифметики в данном случае могут быть записа-
ны в виде
LR
pjpjj
pjpj
LRpj xBaxAaxBaxAa
xBmxAmxBmxAm
xBxA
⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
±±
±±
=⊕
,])()([;])()([
;])()([;])()([
][
2211
2211
(10)
где jCA = или jAA = , а pCB = или pAB = .
В выражении (10) знак «+» справедлив, если 1=px и коэффициент
pT — число положительное, и знак «–» — если 1=px и pT — отрицатель-
ное число.
ПРАВИЛА СРАВНЕНИЯ, ОПРЕДЕЛЕНИЯ ПРЕДПОЧТЕНИЙ И ПРОВЕРКИ
ВЫПОЛНЕНИЯ ОГРАНИЧЕНИЙ ДЛЯ НЕЧЕТКИХ МНОЖЕСТВ
Правила доминирования для нечётких множеств, представленных LR
Fuzzy-интервалами, основанные на сравнении их сечений, рассматривались
в работах многих авторов (см., например, [5, 12]). Ниже эти методы доведе-
ны до конкретных формульных выражений, а также приведены алгоритмы
сравнения и предпочтения нечетких множеств на основе анализа крайних
точек их функций принадлежности.
Рассмотрим два нечетких множества
LRiiiii amma )}(),(),(),({ 2211 ΨΨΨΨ=Ψ
и
LRjjjjj amma )}(),(),(),({ 2211 ΨΨΨΨ=Ψ
или LRiiii ama )}(),(),({ 21 ΨΨΨ=Ψ и LRjjjj ama )}(),(),({ 21 ΨΨΨ=Ψ .
Правила абсолютного предпочтения. Если для двух Fuzzy-множеств
iΨ и jΨ справедливы неравенства )()( 12 ji aa Ψ≤Ψ , то Fuzzy-множество iΨ
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 124
имеет абсолютное предпочтение перед Fuzzy-множеством jΨ в смысле
ji Ψ<Ψ Re . При выполнении неравенство )()( 21 ji aa Ψ≥Ψ Fuzzy-множество
iΨ имеет абсолютное предпочтение перед Fuzzy-множеством jΨ в смысле
ji Ψ>Ψ Re .
Правила относительного предпочтения. Если для двух Fuzzy-
множеств iΨ и jΨ справедлива система неравенств
)()( 11 ji aa Ψ≤Ψ , )()( 11 ji mm Ψ≤Ψ , )()( 22 ji mm Ψ≤Ψ или )()( ji mm Ψ≤Ψ ,
)()( 22 ji aa Ψ≤Ψ
и хотя бы одно из этих неравенств является строгим, то Fuzzy-множество
iΨ имеет относительное предпочтение перед Fuzzy-множеством jΨ
в смысле ji Ψ≤Ψ Re .
Если для двух Fuzzy-множеств iΨ и jΨ справедлива система неравенств
)()( 11 ji aa Ψ≥Ψ , )()( 11 ji mm Ψ≥Ψ , )()( 22 ji mm Ψ≥Ψ или )()( ji mm Ψ≥Ψ ,
)()( 22 ji aa Ψ≥Ψ
и хотя бы одно из этих неравенств является строгим, то Fuzzy-множество
iΨ имеет относительное предпочтение перед Fuzzy-множеством jΨ
в смысле ji Ψ≥Ψ Re .
Более сильное правило относительного предпочтения может быть по-
строено на основании системы неравенств относительно крайних точек соот-
ветствующих pα сечений, т.е.системы неравенств относительно значений
)(1 iL Ψα , )(2 iL Ψα и )(1 jL Ψα , )(2 jL Ψα , .1,,...,,,0 210 =αααα=α=α PP Ил-
люстрация выбора крайних точек для случая 5 сечений функции принад-
лежности трапециевидного и треугольного типа приведены на рис. 1, 2.
Для функций принадлежности трапециевидного вида значения )(1 iL Ψα ,
)(2 iL Ψα вычисляются по формулам
Рис. 1. Сечения функции принадлежности трапециевидного типа
)()()()( 2211 AAmAmA αα
)(3
1 ALα
)(2
1 ALα
)(1
1 ALα
)(4
2 ALα
)(3
2 ALα
)(2
2 ALα
)(1
2 ALα
α5=1,0
α4
α3
α2
α1
α0=0 x
)(2 Aμ
)(4
1 ALα
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 125
),1()]()([)()( 1111 α−Ψ−Ψ−Ψ=Ψα
iiii ammL
,)1()]()([)()( 2222 α−Ψ−Ψ+Ψ=Ψα
iiii mamL
а для функций принадлежности треугольного вида:
,)1()]()([)()( 11 α−Ψ−Ψ−Ψ=Ψα
iiii ammL
)1()]()([)()( 22 α−Ψ−Ψ+Ψ=Ψα
iiii mamL .
Если справедлива система неравенств
)()( 11 ji LL Ψ≤Ψ αα , )()( 22 ji LL Ψ≤Ψ αα , 1,,...,,,0 210 =αααα=α=α PP ,
то Fuzzy-множество iΨ имеет относительное предпочтение перед Fuzzy-
множеством jΨ в смысле ji Ψ≤Ψ Re .
Если справедлива система неравенств
)()( 11 ji LL Ψ≥Ψ αα , )()( 22 ji LL Ψ≥Ψ αα , 1,,...,,,0 210 =αααα=α=α PP , (11)
то Fuzzy-множество iΨ имеет относительное предпочтение перед Fuzzy-
множеством jΨ в смысле ji Ψ≥Ψ Re .
От выбора значений pα , )1(,...,2,1 −= Pp и количества сечений P
во многом зависит результат решения задач сравнения и ранжирования.
Экспертами могут быть предложены различные варианты такого выбора.
Вычислим значение некоторой функции свертки крайних точек сече-
ний нечетких множеств
∑
=
αα
Ψ+Ψβ=Ψ
P
p
iipi
pp LLf
1
21 ,)]()([
2
1)(
где 10 <β< p , Pp ...,,2,1,0= — некоторые весовые коэффициенты, удовле-
творяющие условиям нормировки 1
1
=β∑
=
P
p
p .
Выбор значений этих коэффициентов осуществляется экспертом или
лицом, принимающем решение. Так, например, могут быть выбраны следу-
ющие значения: 075,00 =β , 125,01 =β , 2,02 =β , 25,02 =β , 35,04 =β .
Рис. 2. Сечения функции принадлежности треугольного типа
)(3
1 ALα
)(2
1 ALα
)(1
1 ALα
)(4
2 ALα
)(3
2 ALα
)(2
2 ALα
)(1
2 ALα
α5=1.0
α4
α3
α2
α1
α0=0
)()()( 211 AAmA αα
x
)(4
1 ALα
)(1 Aμ
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 126
Другое более слабое правило относительного предпочтения может
быть сформулировано следующим образом.
В случае )()( ji ff Ψ<Ψ справедливо утверждение ji Ψ≤Ψ Re .
В случае )()( ji ff Ψ>Ψ справедливо утверждение ji Ψ≥Ψ Re .
ДЕТЕРМИНИРОВАННЫЕ ЭКВИВАЛЕНТЫ ЗАДАЧ НЕЧЕТКОГО
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Различные схемы решения задачи нечеткого линейного программирования
изображены на рис. 3. Пусть задан некоторый детерминированный вектор
переменных ),...,,...,,(,~
21 nj xxxxXHX =∈ , удовлетворяющий системе огра-
ничений на переменные (7). На основе принципа расширения и, пользуясь
операторами Fuzzy-арифметики, можно построить нечёткое множество iΨ
левой части i -го неравенства системы ограничений (4) или (9), функция
принадлежности которого также может быть представлена с помощью
LR -Fuzzy-интервала трапециевидной формы — ),(),(),({ 211 iii mma ΨΨΨ
LRia )}(2 Ψ или треугольной формы — LRiii ama )}(),(),({ 21 ΨΨΨ .
Обозначим )(1 ALα , )(2 ALα — крайние точки α -сечений нечёткого
множества A , где 10 <α< . В качестве множества A могут рассматриваться
нечеткие множества jC , jH1 , jH2 , ijA , nj ,...,1= , а также ii B,Ψ , mi ,...,1= .
Утверждение.
а) Если для двух нечётких множеств iΨ и iB выполняется неравенство
)()( 12 ii Baa ≤Ψ ,
то для детерминированного вектора HX ~
∈ справедливо выражение
ii BRe<Ψ , т.е. условие абсолютного предпочтения.
б) В случае, если выполняется одна из системы неравенств
,)()( 11 ii Baa ≤Ψ ,)()( 11 ii Bmm ≤Ψ ,)()( 22 ii Bmm ≤Ψ ;)()( 22 ii Baa ≤Ψ
,)()( 11 ii BLL αα ≤Ψ ,)()( 22 ii BLL αα ≤Ψ Pααα=α ,...,, 21 ,
то детерминированный вектор переменных HX ~
∈ обеспечивает выполнение
Fuzzy-отношений ii BRe≤Ψ , т.е. условия относительного предпочтения.
Следовательно, как в одном, так и во втором случае обеспечивается
выполнение i -го ограничения из системы ограничений (7) или (9).
Если условия приведенного утверждения выполняются для каждого из
ограничений ( mi ,...,1= ) системы (7) или (9), то детерминированный вектор
HX ~
∈ удовлетворяет всей системе ограничений задачи.
При поиске решения задачи в виде некоторого вектора переменных
в форме Fuzzy-множеств )( jXX = , nj ,...,1= , (правая ветвь схемы решения
показана на рис. 3) в качестве детерминированного эквивалента задачи не-
четкого линейного программирования может рассматриваться последо-
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 127
вательность решения следующих )2(2 +P задач детерминированного
линейного программирования для каждого из значений ,00 =α=α
1,,...,, )1(21 =αααα +PP и значений .2,1=s
Задача 3.
max)(
1
→=∑
=
αα
jj
n
j
ss xCLF , (12)
в условиях ограничений
)()(
1
isjij
n
j
sis BLxAL α
=
αα ≤=ϕ ∑ , mi ,...,1= , (13)
)()( 2211 jjj HLxHL αα ≤≤ , nj ,...,1= . (14)
Здесь, если 00 =α=α , то )()( 11 AaAL =α , )()( 22 AaAL =α , а если
1)1( =α=α +P , то )()( 11 AmAL =α , )()( 22 AmAL =α для функций принадлеж-
ности трапециевидного типа и )()()( 21 AmALAL == αα для функций принад-
лежности треугольного типа.
В результате решения каждой из детерминированных задач (12)–(14)
будет получен детерминированный вектор значения переменных задачи
Построение детерминированных огра-
ничений и критериев оптимальности
для каждого из pα -сечений
Формулировка задач
линейного программирования
для каждого из pα -сечений
Решаем все задачи симплексным
методом. Результат решения каждой
задачи — вектор действительных чисел
),( pX α Pp ,,1,0 K=
Построение функций принадлежности
всех нечетких множеств ,jX ,,,1 nj K=
соединением точек ),( pjx α Pp ,,1,0 K=
Определение весовых коэффициентов
p
wα для каждого из pα -сечений
Формирование локальных и компро-
миссных критериев оптимальности,
ограничений на переменные задачи
и левых частей линейных неравенств
Построение детерминированного
эквивалента в виде задачи
линейного программирования
большого размера
Решение задачи симплексным методом.
Получение решения задачи в виде
вектора действительных чисел
Математическая модель задачи нечеткого
линейного программирования
Ввод pα -сечений, ,,,1,0 Pp K= всех Fuzzy-множеств
Расчет крайних точек сечений `
1
αL и `
2
αL коэффициен-
тов и граничных значений всех Fuzzy-множеств
Решение о виде вектора
действительных переменных
Решение о виде вектора
Fuzzy-множеств
Рис. 3. Общая схема методов построения алгоритмов нечёткого математического
программирования
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 128
),....,,....,,( 21
ααααα = nsjssss xxxxX , представляющий собой граничные точки соо-
тветствующих α -сечений нечёткого множества •X решения сформулиро-
ванной задачи. На основании полученных детерминированных значений
этих векторов соединением этих точек отрезками прямых линий строится
функция принадлежности нечеткого множества каждой переменной вектора
решений задачи, которая может быть отличной от трапециевидного или тре-
угольного вида.
При построении приближенного детерминированного эквивалента ис-
ходной задачи (3), (5) в виде задачи (4) может быть получено решение ее
в виде детерминированного вектора оптимизируемых переменных при су-
щественно меньшем объёме вычислений.
Если обозначить
∑
+
=
ααα +=
1
0
21 ,)]()([5,0)(
P
p
ALALwAM
где 10 ≤≤ αw , },,...,,,{~
)1(210 +ααααα=α=Α PP — весовые коэффициенты,
1
1
0
=∑
+
=
α
P
p
w , то могут быть сформулированы задачи 4 и 5.
Задача 4.
max)(
1
→=Φ ∑
=
jj
n
j
xCM , (15)
)()(
1
ijij
n
j
i BMxAM ≤=φ ∑
=
, mi ,...,1= , (16)
)()( 21 jjj HMxHM ≤≤ , nj ,...,1= . (17)
Задача 5. Найти максимальное значение функции (15) в условиях таких
ограничений:
)()( 1
1
1 ijij
n
j
i BLxAL μ
=
μ ≤=φ ∑ , )()( 2
1
2 ijij
n
j
i BLxAL ρ
=
ρ ≤=φ ∑ , mi ,...,1= , (18)
)( 21 jj HLx ω≤ , )( 22 jj HLx η≤ , nj ,...,1= . (19)
При этом в выражении (18) в качестве μα и ρα выбираются некоторые
подмножества сечений 1
~
Α∈αμ , Α⊆Α
~~
1 ; 2
~
Α∈αρ , Α⊆Α
~~
2 , как и в выра-
жении (19) — 3
~
Α∈αω , Α⊆Α
~~
3 ; 4
~
Α∈αη , Α⊆Α
~~
4 .
Отметим, что как задачи 4 и 5, так и каждая из задач 3 могут быть ре-
шены симплексным методом линейного программирования.
Частные случаи. Рассмотрим случаи, когда в задаче (3), (4) нечеткие
множества nj CCCC ,...,,...,, 21 , ijA , ,,...,1 nj = и iB , mi ,...,1= , представлены
треугольными и трапециевидными функциями принадлежности, крайние
и центральные значения которых равны 1a , 2a и )(am (или 1m и 2m ),
где 0)()( 21 =μ=μ aa AA , 1)()()( 21 =μ=μ=μ mmm AAA . Ограничения (5)
отсутствуют.
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 129
Ограничения (4) и (9) могут рассматриваться как условия строгого
предпочтения для всех рассматриваемых α -сечений Fuzzy-множеств iΨ
и iB и как условия относительного предпочтения. Обозначим соответствен-
но )(1 ia Ψ , )(2 ia Ψ , )( im Ψ и )(1 iBa , )(2 iBa , )( iBm (для трапециевидных
функций принадлежности вместо значений )( im Ψ и )( iBm рассматривают-
ся пары значений )(),( 21 ii mm ΨΨ и )(),( 21 ii BmBm ) — соответственно
крайние и центральные значения α -сечений Fuzzy-множеств iΨ и iB . Тог-
да условия строгого выполнения неравенств (4) и (9) для каждого из α -
сечений могут быть записаны соответственно в виде, аналогичном (11)
)()( 12 ii Baa ≤Ψ
r
, mi ,...,1= . (20)
Условия относительного предпочтения системы нечётких неравенств
(4) и (9) могут быть представлены соответственно в виде
)()( 11 ii Baa ≤Ψ , )()( 22 ii Baa ≤Ψ
r
, mi ,...,1= ,
)()( ii Bmm ≤Ψ , или )()( 11 ii Bmm ≤Ψ и )()( 22 ii Bmm ≤Ψ , mi ,...,1= . (21)
При этом желательно, чтобы одно из неравенств системы (20) и (21)
для пары индексов i и α выполнялось в строгом виде.
Для безусловного выполнения системы нечетких неравенств (20) мож-
но потребовать выполнение следующей системы линейных неравенств:
)(1
1
i
n
j
ijij Bax α
=
≤β∑ , mi ,...,1= . (22)
Здесь αβij — коэффициенты линейных неравенств, )(1 iBaα и )(2 iBaα — соот-
ветственно значения левых и правых точек соответствующих α сечений
функций принадлежности i -го ограничения.
Так как всегда для положительных и отрицательных значений парамет-
ров справедливы неравенства
)()( 21 ijij AaAa αα ≤ и )()( 21 ii BaBa αα ≤ ,
где )(1 ijAaα и )(2 ijAaα — значения левых и правых точек соответствующих
α -сечений функций принадлежности нечеткого множества коэффициента
ijA , то значения этих коэффициентов соответственно равны: )(2 ijij Aaαα =β ,
если знак перед членом jij xA в выражении (4) положительный, =βαij
)(1 ijAaα= , если знак перед членом jij xA ⋅ в выражении (4) отрицательный.
Условия относительного предпочтения при выполнении системы
Fuzzy-логических неравенств представлены в виде
)()( 1
1
1 i
n
j
jij BaxAa α
=
α ≤∑ , )()( 2
1
2 i
n
j
jij BaxAa α
=
α ≤∑ , 1,...,1 mi = ;
)1(210 ,,...,,, +ααααα=α PP , (23)
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 130
и для треугольных и трапециевидных функций принадлежности имеют вид
)()(
1
i
n
j
jij BmxAm ≤∑
=
, (24)
)()( 1
1
1 i
n
j
jij BmxAm ≤∑
=
, )()( 2
1
2 i
n
j
jij BmxAm ≤∑
=
. (25)
Отметим справедливость следующих выражений:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
>
≤
=Ψ
∑ ∑∑
∑ ∑∑
= =
α
=
αα
= =
α
=
αα
α
n
j
n
j
jij
n
j
jijjij
n
j
n
j
jij
n
j
jijjij
i
xAaxAaxAa
xAaxAaxAa
a
1 1
2
1
12
1 1
2
1
11
1
;)()(если,)(
,)()(если,)(
)(
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≤⋅
>⋅
=Ψ
∑ ∑∑
∑ ∑∑
= =
α
=
αα
= =
α
=
αα
α
n
j
n
j
jij
n
j
jijjij
n
j
n
j
jij
n
j
jijjij
i
xAaxAaxAa
xAaxAaxAa
a
1 1
2
1
12
1 1
2
1
11
2
;)()(если,)(
,)()(если,)(
)(
⎪
⎪
⎩
⎪
⎪
⎨
⎧
>
≤
=Ψ
∑ ∑∑
∑ ∑∑
= ==
= ==
n
j
n
j
jij
n
j
jijjij
n
j
n
j
jij
n
j
jijjij
i
AmxAmxAm
xAmxAmxAm
m
1 1
2
1
12
1 1
2
1
11
1
;)()(если,)(
,)()(если,)(
)(
⎪
⎪
⎩
⎪
⎪
⎨
⎧
>⋅
≤
=Ψ
∑ ∑∑
∑ ∑∑
= ==
= ==
n
j
n
j
jij
n
j
jijjij
n
j
n
j
jij
n
j
jijjij
i
xAmxAmxAm
xAmxAmxAm
m
1 1
2
1
11
1 1
2
1
12
2
.)()(если,)(
,)()(если,)(
)(
При задании граничных значений на переменные в форме Fuzzy-
множеств (5) ограничения на переменные задачи могут быть записаны в виде
)( 1
2 jj Hax α≥ , 1
~A∈α ; )( 2
1 jj Hax α≤ , 2
~A∈α , nj ,...,1= , (26)
где AA ~~
1 ⊆ , AA ~~
2 ⊆ — некоторые подмножества всех сечений соответст-
венно Fuzzy-множеств 1
jH и 2
jH .
Так, например, в условиях безусловного выполнения ограничений на
значения переменных
)()( 2
1
1
2 jjj HaxHa ≤≤ , nj ,...,1= . (27)
Более слабые условия выполнения ограничений представлены в форме
)()( 21
jjj HmxHm ≤≤ , nj ,...,1= ; или )()( 2
1
1
2 jjj HmxHm ≤≤ , nj ,...,1= ; (28)
)()( 2
2
1
1 jjj HaxHa ≤≤ , nj ,...,1= . (29)
Целевая функция задачи представлена также в линейной форме
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 131
max)(
1 1
→⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
λ=∑ ∑
= =α
αα
j
n
j
p
jj xCwF . (30)
Здесь αw — вес, придаваемый значению целевой функции в определенном
α -м сечении нечеткого множества коэффициентов целевой функции jC ;
значения )( jj Cαλ для функций принадлежности треугольного и трапецие-
видного вида вычисляются соответственно по формулам:
)1()]()([
2
1)()( 21 α−++α=λ ααα
jjjjj CaCaCmC ,
)1(210 ,,...,,, +ααααα=α PP , nj ,...,1= ; (31)
,)1()]()([
2
1)]()([
2
1)( 2121 α−++α⋅+=λ ααα
jjjjjj CaCaCmCmC
)1(210 ,,...,,, +ααααα=α PP , nj ,...,1= . (32)
Задачи (22) или (23), (24), или (24), (25) с целевой функцией (30), (31)
или (32) являются задачами линейного программирования. При этом долж-
ны также учитываться ограничения на переменные задачи в одной из форм
(26)–(27). Все эти задачи могут быть решены симплексным методом. Реше-
ние этой задачи — вектор действительных значений переменных.
Детерминированные эквиваленты многокритериальных задач нечетко-
го линейного программирования — многокритериальные задачи детерми-
нированного линейного программирования с большим количеством ограни-
чений и локальных критериев оптимальности. Методы решения этих задач
(различные свертки критериев, лексикографическое упорядочение критери-
ев и метод последовательных уступок) рассмотрены в монографии и статьях
автора (см., например [13–15].
Нелинейные критерии оптимальности. Рассмотрим случаи, когда
в качестве критерия оптимальности будет выбрана минимизация значения
координаты абсцисс центра тяжести, полученного в результате решения за-
дачи нечеткого множества функции цели,
∫
∫
μ
μ
=
2
1
2
1
)()]([
)()]([)(
)( a
a
x
a
a
x
x
FdxFx
FdxFxFx
FM .
В этом случае детерминированный эквивалент задачи будет представ-
лен в виде задачи минимизации нелинейного критерия оптимальности в ус-
ловиях линейной системы ограничений. Вид этого критерия оптимальности
для функций принадлежности коэффициентов jC и переменных jX , пред-
ставленных в виде треугольников и трапеций, приведен соответственно
в формулах:
;
)]()([3
)]()([)]([3
)]()([3
)]([)]([)]([4)(
12
21
2
12
3
2
3
1
3
FaFa
FaFaFm
FaFa
FaFaFmFM x −
+−
−
−
++
= (33)
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 132
1
2)(
S
SFM x = , (34)
где +−+
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−
−+
=
∑
=
)]()([
2
1
)()(6
)]([)(3)]([)]([2
12
1
1
1
2
11
3
1
3
1
2 FmFm
FaFm
FmFaFaFmS
n
j
;
)]()([6
)()(3)]([)]([2
22
2
1
22
3
2
3
2
FmFa
FmFaFaFm
n
j
−
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−+
+
∑
= (35)
.)]()()()([
2
1
12121 FaFaFmFmS −+−= (36)
В выражениях (33)–(36) Fuzzy-множество F определяется форму-
лой (6).
ЗАКЛЮЧЕНИЕ
В литературе описаны различные критерии и алгоритмы сравнения и ран-
жирования нечетких множеств. Для каждого из принятых за основу методов
сравнения могут быть сформулированы детерминированные эквиваленты
и методы решения задач Fuzzy-математического программирования. Выбор
определенного вида критерия и метода сравнения зависит от специфики
конкретной прикладной задачи, требований к жесткости выполнения огра-
ничения, надежности получения желаемого результата, а также от предпоч-
тений лица, принимающего решение, и экспертов. В данной работе выбраны
для такого сравнения различные модификации сечений нечетких множеств
и алгоритмы их реализации, а также координаты абсцисс центра тяжести
нечетких множеств, на основе которых построены различные виды детер-
минированных эквивалентов задачи. В отличие от известных публикаций
построение этих эквивалентов рассмотрено в самом общем виде: в услови-
ях, когда коэффициенты функции цели и ограничений задачи — нечеткие
множества, наличие двухсторонних ограничений на переменные задачи,
представленных в виде нечетких множеств. Для функций принадлежности
Fuzzy-множеств в виде треугольников и трапеций рассмотрены различные
условия проверки выполнения системы ограничений и обеспечения опти-
мального значения функции цели, которые приведены в виде детерминиро-
ванных функций от неизвестных параметров. В результате предложенных
преобразований количество ограничений может увеличиваться как минимум
в два раза, но полученные в результате этих преобразований задачи одно-
и многокритериальные задачи линейного программирования можно решить
симплексным методом. Обсуждаются методы решения сформулированных
многокритериальных задач. При использования в качестве критерия опти-
мальности координаты абсцисс центра тяжести нечетких множеств детер-
минированный эквивалент сформулирован в виде задачи нелинейного мате-
матического программирования.
Предложенные в работе подходы находят широкое применение в раз-
личных приложениях, в частности при выборе наиболее эффективного
Некоторые детерминированные модели задач нечеткого линейного программирования
Системні дослідження та інформаційні технології, 2016, № 1 133
портфеля ценных бумаг, минимизации финансовых рисков, решении других
технических и экономических проблем, в которых математические модели
представлены линейными Fuzzy-регрессионными моделями.
ЛИТЕРАТУРА
1. Язенин А.В. Нечеткое математическое программирование / А.В. Язенин. — Ка-
линин: Калин. гос. ун-т, 1986. — 60 с.
2. Згуровский М. Модели и методы принятия решений в нечетких условиях /
М. Згуровский, Ю. Зайченко. — К.: Наук. думка, 2013. — 275 с.
3. Kumar A. A new method for solving fully fuzzy linear programming problems /
A. Kumar, J. Kaur, P. Singh // Applied Mathematical Modelling. — 2011. — 35.
— N 2. — P. 817–823.
4. Kumar A. Fuzzy optimal solution of fully fuzzy linear programming problems with
inequality constraints / A. Kumar, J. Kaur, P. Singh // International Journal of
Applied Mathematics and Computer Sciences. — 2010. — 6. — P. 37–41.
5. Rommelfanger H.J. Entscheiden bei Unschärfe. Fuzzy Decision Support-Systeme /
H.J. Rommelfanger // Springer, Berlin-Heidelberg. — New York, London, To-
kio, 1999. — 304 p.
6. Herrera F. Thtree models of fuzzy integer linear programming / F. Herrera,
J.L. Verdegay // European Journal of Operationel Research. — 1995. — N 83. —
P. 581–593.
7. Allahviranloo F. Solving fully fuzzy linear programming problem by the ranking
functhion / F. Allahviranloo, H. Lotfi, M.K. Kiasary, N.A. Kiani, L. Alizadeh //
Applied Matematical Sciences. — 2008. — 2. — P. 19–32.
8. Maleki R. Linear programming with fuzzy variables / R. Maleki, M. Tata,
M. Mashinchi // Fuzzy Sets and Systems. — 2000. — 109. — P. 21–33.
9. Зак Ю.А. Принятие решений в условиях размытых и нечетких данных /
Ю.А. Зак. — М.: URSS, 2013. — 352 с.
10. Inguichi M. Possibilistic linear programming: a brief review of fuzzy mathematical
programming and a comparison with stochastic programming in portfolio selec-
tion problem / M. Inguichi, J. Ramik // Fuzzy Sets and System. — 2000. — N 11.
— P. 3–28.
11. Barth P. A Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-
Boolean Optimization / P. Barth // Max-Plank-Institut für Informatik, Saar-
brücken, 1995. — 12 p.
12. Зак Ю.А. Критерии и методы сравнения нечётких множеств / Ю.А. Зак // Систем-
ные исследования и информационные технологии. —2013. — № 3. — С. 58–68.
13. Зак Ю.А. Алгоритмы решения задач линейного булевого программирования
в условиях размытых исходных данных / Ю.А. Зак // Программная инжене-
рия. — 2014. — № 4. — С. 28–38.
14. Зак Ю.А. Прикладные задачи многокритериальной оптимизации / Ю.А. Зак //
Экономика. — 2014. — 452 c.
15. Зак Ю.А. Многокритериальные задачи математического программирования
с размытыми ограничениями. Математические модели схем компромисса.
Выбор решений из конечного множества альтернатив / Ю.А. Зак // Кибер-
нетика и системный анализ. — № 5. — 2010. — С. 80–89.
16. Bellman R.E. Decision-Making in Fuzzy Environment / R.E. Bellman, L.A. Zadeh //
Management Science. — 1970. — 17. — N 4. — P.141–160.
Поступила 08.06.2015
|
| id | journaliasakpiua-article-65806 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:20:08Z |
| publishDate | 2016 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/15/e8a346620faeb7cc5556a5635352b415.pdf |
| spelling | journaliasakpiua-article-658062016-07-25T14:59:53Z Some deterministic models of fuzzy linear programming problems Некоторые детерминированные модели задач нечеткого линейного программирования Деякi детермінованi моделi задач нечіткого лінійного програмування Zack, Y. A. We consider deterministic equivalents of various formulations of linear programming prob-lems, in which the coefficients of the objective function, constraints and the boundary values of the variables of the problem and the right-hand side are represented by fuzzy sets. The methods for comparing the fuzzy sets and selecting the best ones are proposed. The problem of finding the vec-tor of variables as a vector of real numbers is reduced to solving the one-criterion or multicriteria problem with the significantly large number of constraints. In solving the problem as a vector of Fuzzy-sets, the equivalent problem was determined – a sequence of linear programming problems. The formulated problems can be solved by the simplex method. Рассмотрены детерминированные эквиваленты различных постановок задач линейного программирования, в которых коэффициенты функции цели, ограничений и граничные значения переменных задачи и правых частей неравенств представлены нечеткими множествами. Предложены методы сравнения и определения предпочтения нечетких множеств. Решение задачи при поиске вектора переменных в виде вектора действительных чисел сводится к решению однокритериальной или многокритериальной задачи с существенно большим количеством ограничений. При решении задачи в виде вектора Fuzzy-множеств детерминировано эквивалент задачи — последовательность задач линейного программирования. Сформулированные задачи могут быть решены симплексным методом. Розглянуто детерміновані еквіваленти різних постановок завдань лінійного програмування, у яких коефіцієнти функції мети, обмежень і граничні значення змінних задачі і правих частин нерівностей подані нечіткими множинами. Запропоновано методи порівняння і визначення переваги нечітких множин. Розв’язання задачі при пошуку вектора змінних у вигляді вектора дійсних чисел зводиться до розв’язання однокритеріальної або багатокритеріальної задачі з істотно більшою кількістю обмежень. При розв’язанні задачі у вигляді вектора Fuzzy-множин детерміновано еквівалент задачі — послідовність задач лінійного програмування. Сформульовані задачі можуть бути розв’язані симплексним методом. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-03-18 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/65806 10.20535/SRIT.2308-8893.2016.1.12 System research and information technologies; No. 1 (2016); 120-133 Системные исследования и информационные технологии; № 1 (2016); 120-133 Системні дослідження та інформаційні технології; № 1 (2016); 120-133 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/65806/61029 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Zack, Y. A. Деякi детермінованi моделi задач нечіткого лінійного програмування |
| title | Деякi детермінованi моделi задач нечіткого лінійного програмування |
| title_alt | Some deterministic models of fuzzy linear programming problems Некоторые детерминированные модели задач нечеткого линейного программирования |
| title_full | Деякi детермінованi моделi задач нечіткого лінійного програмування |
| title_fullStr | Деякi детермінованi моделi задач нечіткого лінійного програмування |
| title_full_unstemmed | Деякi детермінованi моделi задач нечіткого лінійного програмування |
| title_short | Деякi детермінованi моделi задач нечіткого лінійного програмування |
| title_sort | деякi детермінованi моделi задач нечіткого лінійного програмування |
| url | https://journal.iasa.kpi.ua/article/view/65806 |
| work_keys_str_mv | AT zackya somedeterministicmodelsoffuzzylinearprogrammingproblems AT zackya nekotoryedeterminirovannyemodelizadačnečetkogolinejnogoprogrammirovaniâ AT zackya deâkidetermínovanimodelizadačnečítkogolíníjnogoprogramuvannâ |