Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин
The deterministic equivalents of the tasks of fuzzy linear programming with two-sided constraints on the deterministic values of variables that can take both positive and negative values are proposed, and the coefficients of the goal function and the linear constraint functions, as well as the left...
Saved in:
| Date: | 2018 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/139961 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302240935903232 |
|---|---|
| author | Zack, Yuriy A. |
| author_facet | Zack, Yuriy A. |
| author_sort | Zack, Yuriy A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-01-17T13:29:35Z |
| description | The deterministic equivalents of the tasks of fuzzy linear programming with two-sided constraints on the deterministic values of variables that can take both positive and negative values are proposed, and the coefficients of the goal function and the linear constraint functions, as well as the left and right boundary values on their values, are fuzzy sets, represented by fuzzy-intervals with membership functions with LR-representation of the most general kind. Based on the rules of ranking and estimating the dominance of fuzzy sets considered in the work, conditions for unconditional (strict) and conditional (non-strict) fulfillment of restrictions are established. The different kinds of deterministic equivalents of the problem in which the execution of fuzzy constraints with different degrees of severity is required, involve solving not one but several sets of linear programming problems. The best possible solution is chosen. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2018.2.11 |
| first_indexed | 2025-07-17T10:24:05Z |
| format | Article |
| fulltext |
Ю.А. Зак, 2018
Системні дослідження та інформаційні технології, 2018, № 2 111
TIДC
МЕТОДИ АНАЛІЗУ ТА УПРАВЛІННЯ
СИСТЕМАМИ В УМОВАХ РИЗИКУ
І НЕВИЗНАЧЕНОСТІ
УДК 519.85
DOI: 10.20535/SRIT.2308-8893.2018.2.11
ЗАДАЧИ НЕЧЕТКОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
С ДВУХСТОРОННИМИ ОГРАНИЧЕНИЯМИ
И ПАРАМЕТРАМИ ЦЕЛЕВЫХ ФУНКЦИЙ И ОГРАНИЧЕНИЙ
В ВИДЕ НЕЧЕТКИХ МНОЖЕСТВ
Ю.А. ЗАК
Аннотация. Предложены детерминированные эквиваленты задач нечеткого
линейного программирования c двухсторонними ограничениями на детерми-
нированные значения переменных, которые могут принимать как положитель-
ные, так и отрицательные значения, а коэффициенты функции цели и линей-
ные функции ограничений, а также левые и правые граничные их значения —
нечеткие множества, преставленные fuzzy-интервалами с LR -представлением
функций принадлежности общего вида. На основе рассмотренных в работе
правил ранжирования и оценки доминирования нечетких множеств установле-
ны условия безусловного (строгого) и условного (нестрогого) выполнения ог-
раничений. Различного вида детерминированные эквиваленты задачи, в кото-
рых требуется выполнение fuzzy-ограничений с различной степенью строгости,
предусматривают решения не одной, а некоторого множества задач линейного
программирования. Выбирается наилучшее из допустимых решений.
Ключевые слова: нечеткое линейное программирование, fuzzy-интервалы
с LR -представлением функций принадлежности, условия доминирования не-
четких множеств, двухсторонние интервальные ограничения, детерминиро-
ванный эквивалент.
ВВЕДЕНИЕ
Постановкам, математическим моделям и методам решения задач линей-
ного программирования, в которых такие параметры, как граничные зна-
чения, а также коэффициеты целевых функций и ограничений могут быть
выражены нечеткими множествами, уделялось значительное внимание в
монографиях и периодической литературе (см., например, [1–10]). Такие
задачи возникают в практических приложениях вследствие как нечеткости
математического описания решаемой проблемы, так и некоторой размыто-
сти требований к выполнению установленных ограничений.
Поскольку формы нечеткого математического описания решаемой про-
блемы бывают различными, существуют разные классы задач нечеткого ма-
тематического программирования:
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 112
оптимизация как некоторой детерминированной функции, так и
функции принадлежности некоторого нечеткого множества на заданном не-
четком множестве допустимых альтернатив. Для решения этой задачи при-
менялся подход Беллмана–Заде [11, 12] — поиск решения, максимизирую-
щего минимальное из значений превышения функцией цели некоторого
заданного уровня и уровня выполнения каждого из ограничений; нечеткая
цель описывается функцией принадлежности. Решить данную задачу озна-
чает достигнуть заданного уровня цели и обеспечить выполнение каждого
уровня из системы ограничений с заданным уровнем надежности;
задачи линейного ограничения с размытыми ограничениями, в кото-
рых отклонениям приписываются различные степени допустимости и до-
пускается нечеткое выполнение некоторых неравенств [2, 13, 17]. Исходная
задача оказывается сформулированной в форме задачи достижения нечеткой
цели, и к ней также можно применить подход Беллмана–Заде;
рассматриваемый в данной работе класс задач, в которых коэффици-
енты функций цели и ограничений, а также левые и правые граничные зна-
чения – нечеткие множества, а переменные задачи — действительные числа,
на которые (в отличие от рассматриваемых ранее подходов) могут быть на-
ложены двухсторонние ограничения и некоторые из этих действительных
чисел могут иметь отрицательные значения. Все рассматриваемые в литера-
туре задачи предусматривали лишь положительные значения всех действи-
тельных переменных [11, 12]. Если все переменные задачи не могут быть
отрицательными числами, в качестве одного из подходов при выборе в ка-
честве решения одной из возможных альтернатив исходная задача может
быть сформулирована в форме задачи достижения нечеткой цели и к ней
можно также применить подход Беллмана–Заде (см., например, [1–4, 10,
17]). Общая схема решения задач в рассматриваемой в данной работе поста-
новке заключается в следующем:
вводим некоторые дискретные уровни на основе k , Kk ,...,1,0 ,
сечений значений функций принадлежности нечетких множеств (подмноже-
ства уровня λ) как фунций ограничений, так и их граничных значений. Каж-
дый из этих уровней определяет интервалы возможных значений этих пара-
метров и устанавливает возможности их сравнения;
в зависимости от требований бузусловного или допустимости не-
строго выполнения системы ограничений, а также субъективных представ-
лений лица, принимающего решение (ЛПР), устанавливаем ограничения на
соотношения границ этих интервалов в каждом из этих сечений. Ограниче-
ния принимают интервальный вид и размерность системы ограничений су-
щественно увеличивается;
вводим подмножества уровня k , Kk ,...,1,0 , и для целевой функ-
ции задачи потребуем оптимизацию для каждой из функций, коэффициен-
тами которых являются все граничные значения образованных интервалов.
Получим задачу многокритериальной оптимизации, которая, например, вве-
дением аддитивной свертки этих критериев с различными весовыми коэф-
фициентами, сводится к решению однокритериальной задачи;
в результате выполненных преобразований получаем детерминиро-
ванный эквивалент исходной задачи нечеткого линейного программирова-
ния в виде задачи линейного программирования, которая может быть реше-
на симплексным методом.
Задачи нечеткого линейного программирования с двухсторонними ограничениями …
Системні дослідження та інформаційні технології, 2018, № 2 113
В случае, если некоторые переменные задачи могут принимать как по-
ложительные, так и отрицательные значения, правила fuzzy-арифметики не
позволяют ограничиваться только одним видом детерминированной мате-
матической модели задачи, и в этом случае приходится решать не одну, а
несколько детерминированных задач линейного программирования, что су-
щественно усложняет процесс решения. Среди допустимых решений сфор-
мулированных детерминированных задач выбирается решение с наилучшим
значением целевой функции.
В данной работе предлагаются методы сравнения и определения безус-
ловных и условных предпочтений нечетких множеств, на основе которых
формулируются различного вида правила выполнения ограничений для не-
четких множеств представления критерия оптимальности в виде одной или
нескольких детерминированных функций переменных задачи. Для рассмат-
риваемого класса задач нечеткого линейного программирования предложе-
ны детерминированные эквиваленты, обеспечивающие решение задачи при
различных требованиях к строгости выполнения системы ограничений для
нечетких множеств. Обсуждаются алгоритмы решения сформулированной
задачи [14, 15].
МЕТОДЫ СРАВНЕНИЯ И ОПРЕДЕЛЕНИЯ ПРЕДПОЧТЕНИЙ НЕЧЕТКИХ
МНОЖЕСТВ И УСЛОВИЯ ВЫПОЛНЕНИЯ FUZZY-ОГРАНИЧЕНИЙ
Нечеткое множество A с функцией принадлежности произвольного вида
аппроксимируем некоторой ломанной линией, соединяющей точки мини-
мальных 111
1
1
0 ,...,,...,, Kk aaaa и максимальных значений координат абсцисс
222
1
2
0 ,...,,...,, Kk aaaa некоторого множества сечений, т.е. подмножеств уровней
Kk ,...,,...,, 10 , и представляем их многоугольником ...,,...,,( 11
1
1
0 kaaa
),...,,...,,,,... 2
0
22
1
21 aaaaa kKKK . Такая аппроксимация поясняется рис. 1, на ко-
тором выбрано 5 сечений: 543210 ,,,,, и исходное множество пред-
ставлено многоугольником ),,,,,,,,,,( 2
0
2
1
2
2
2
3
2
4
2
5
1
5
1
4
1
3
1
2
1
1
1
0 aaaaaaaaaaaa .
Рис. 1. Аппроксимация функции принадлежности нечеткого множества самого
общего вида
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 114
Рассматриваются нормализованные нечеткие множества с LR-пред-
ставлением функции принадлежности, т.е. функции, значения которых
)(AA , начиная с некоторого значения абсцисс )(Aax , 0)]([ AaA и до
значения )(1 Amx , 0,1)]([ 1 AmA , на некотором отрезке )](),([ 21 AmAmx
(в частном случае только в одной точке — )]()()([ 21 AmAmAmx )
имеют постоянное значение 0,1)]([)]([ 21 AmAm AA , а на отрезке
)](),([ 2 AbAmx убывают до значения 0)]([ AbA .
Среди достаточно большого количества функций этого класса наи-
больший интерес представляют нечеткие множества с функцией принад-
лежности прямоугольного, треугольного и трапецевидного типов.
Обозначим координаты абсцисс крайних точек каждого из этих сече-
ний соответственно )]([1
kk Aa и )]([2
kk Aa , Kk ,...,1,0 . Обозначим коорди-
наты абсцисс крайних точек функций принадлежности соответствующих
нечетких множеств при 00 K через )(1 AR и )(2 AR , а крайних точек
функций принадлежности соответствующих нечетких множеств при 0,1s ,
где
2
1
K
s , соответственно )(1 AT и )(2 AT . Здесь, если )()( 21 ATAT ,
т.е. )(AA , имеет только одну координату абсцисс, для которой 0,1)( AA ,
то K — четное число.
Координаты абсцисс соответствующих сечений функций принадлеж-
ности определяются по формулам:
)]()([)()]([ 1111 ARATARAa kkk ;
)]()([)()]([ 2222 ATARARAa kkk , Kk ,...,1,0 .
В результате умножения нечеткого множества на некоторое действи-
тельное число b координаты абсцисс соответствующих сечений функций
принадлежности нечетких множества D вычисляются по формулам:
;0)]},()([)({
,0)]},()([)({
)]([)]([
222
111
11
bifATARARb
bifARATARb
AabDa
k
k
kkkk
.0)]},()([)({
,0)]},()([)({
)]([)]([
111
222
22
bifARATARb
bifATARARb
AabDa
k
k
kkkk
В результате сложения нечетких множеств координаты соответствую-
щих сечений вычисляются по формулам:
n
i
iik
n
i
i
n
i
kikkk ARATARAaPa
1
11
1
1
1
11 )]()([)()]([)]([ ;
n
i
iik
n
i
i
n
i
kikkk ATARARAaPa
1
22
1
2
1
22 )]()([)()]([)]([ .
Рассматривается задача нечеткого линейного программирования с
двухсторонними ограничениями вида
Задачи нечеткого линейного программирования с двухсторонними ограничениями …
Системні дослідження та інформаційні технології, 2018, № 2 115
m
j
jj
HHX
xCF
1],[ 21
min
в условиях ограничений
2
1
1
i
m
j
jijii bxAyb
, ni ,...,1 ,
или
2
1
1
i
m
j
jijii BxAyB
, ni ,...,1 ;
21
jjj hxh , mj ,...,1 . (1)
Здесь jC , ijA и граничные значения 1
iB , 2
iB , ni ,...,1 ; mj ,...,1 , а сле-
довательно и значения F и iY , ni ,...,1 , — нечеткие множества с функций
принадлежности LR-представления произвольного вида, а переменные зада-
чи jx и граничные значения 21 , jj hh и 21, ii bb — действительные числа, кото-
рые могут принимать как положительные, так и отрицательные значения.
Так как нечеткое множество определяет некоторый диапазон возмож-
ных значений критерия оптимальности и выходных переменных, определим
сформулированные в данной задаче условия выполнения ограничений зада-
чи и понятие оптимальности функции цели задачи.
Здесь и в дальнейшем для простоты изложения наряду с обозначения-
ми )(F , )(iY , )(1 iB , )(2 iB могут также использоваться обозначения со-
ответствущих нечетких множеств )(F , )(iY , )(1 iB , )(2 iB .
Обозначим )]([1 Fd , )]([2 Fd и )]([1 iYd , а также )]([2 iYd , )](11 iBd ,
)](12 iBd ; )]([ 21 iBd , )]([ 22 iBd , ni ,...,1 — соответственно левые и правые
крайние координаты абсцисс различных сечений функций принадлежности
соответствующих сечений рассматриваемых нечетких множеств. Пусть
00 , 0,1K , 1 kk , )1(,...,1,0 Kk .
Определение 1. Из условий
)]([)]([ 111 ii BdYd и )]([)]([ 122 ii BdYd , Kk ,...,,...,1,0 ,
и )]([)]([ 211 ii BdYd и )]([)]([ 222 ii BdYd , Kk,...,,...,1,0 ,
или )]([)]([ 121 ii BdYd и )]([)]([ 212 ii BdYd , Kk ,...,,...,1,0 ,
следует безусловное выполнение ограничений 1
ii BY и 2
ii BY , ni ,...,1 .
Определение 2. Выполнение неравенств
)]([)]([ 111 ii BdYd и )]([)]([ 222 ii BdYd , Kk ,...,,...,1,0 ,
свидетельствует о нестрогом выполнении i -го ограничения (выполнение в
слабом смысле).
Определение 3. Если для некоторого подмножества сечений
},...,,{ 110
1
1 g
K одно из неравенств )]([)]([ 121 ii BdYd или )]([2
iYd
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 116
)]([ 11 iBd может не выполняться, или для некоторого подмножества сече-
ний },...,,{ 210
2
1 g
K может не выполняться одно из неравенств
)]([)]([ 221 ii BdYd или )]([)]([ 212 ii BdYd , а для каждого из подмноже-
ства уровня λ },...,,{
21
1
2 11 Kgg
K
или },...,,{
21
2
2 22 Kgg
K
с боль-
шими значениями выполняются одновременно два из этих неравенств, то
это означает, что соответствующие ограничения выполняются в слабом
смысле.
Если 1
iB и 2
iB не являются нечеткими множествами, а некоторые дей-
ствительные числа — 1
iB и 2
iB , то безусловное выполнение ограничений
1
ii BY и 2
ii BY равносильно выполнению пары неравенств 1
0
1 )]0([ ii BYd
и 22 )]0([ iKi BYd , а выполнение этой пары ограничений в слабом смыс-
ле — выполнение одной из пары условий
11 )]0([ iki BYd , Kggk ,...,1, 11 ; 22 )]0([ iKi BYd ;
1
0
1 )]0([ ii BYd ; 22 )]([ iki BYd , 2,...,1, gppk ,
где p — сечение с координатами абсцисс )()( 21 iii YmYmY .
Обозначим:
)]}([)]([{5,0)]([ 21 iii YdYdYd , )]}([)]([{5,0)]([ 12111 iii BdBdBd ;
)]}([)]([{5,0)]([ 22212 iii BdBdBd , Kk,...,,...,1,0 .
Определение 4. В случае, если все условия определения 1 не выполня-
ются, а справедлива система неравенств
)]([)]([)]([ 21 iii BdYdBd , Kk,...,,...,1,0 ,
следует заключить, что i -е ограничение выполняется в слабом смысле.
Определение 5. Выполнение условий F
HHX ],[ 21
min
эквивалентно выпол-
нению ряда условий минимизации множества критериев
)]([min 1
],[ 21
Fd
HHX
, )]([min 2
],[ 21
Fd
HHX
, Kk,...,,...,1,0 . (2)
Другим детерминированным эквивалентом критерия оптимальности является
минимизация координаты абсцисс центра тяжести этого нечеткого множества
)(
)(
)(
~
)(
)(
)(
)(
Fb
Fa
F
Fa
F
dFF
dFFF
FG
Fb
, (3)
где )(Fa и )(Fb — граничные значения (абсциссы крайних левой и правой
точек) нечеткого множества критерия оптимальности.
Задачи нечеткого линейного программирования с двухсторонними ограничениями …
Системні дослідження та інформаційні технології, 2018, № 2 117
Обозначим соответственно через )( iYC и )( 1
iBC , )( 2
iBC координаты
абсцисс центров тяжести соответствующих подмножеств.
Определение 6. В случае, если все условия определения 1 не выполня-
ются, а справедлива система неравенств )()()( 21
iii BCYCBC , следует, что
i -е ограничение выполняется в слабом смысле.
Различные условия выполнения интервальных ограничений представ-
лены на рис. 2.
Строгое (безусловное) выполнение интервальных ограничений иллю-
стрирует рис. 2, a, их нестрогое выполнение — рис. 2, г, а на рис. 2, д – е —
ситуации, в которых одно из двухсторонних ограничений нарушено. Си-
туация, когда оба из интервальных ограничений нарушены, показана на
рис. 2, и.
ДЕТЕРМИНИРОВАННЫЕ ЭКВИВАЛЕНТЫ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ С НЕЧЕТКИМИ ПАРАМЕТРАМИ
В качестве детерминированного эквивалента задачи линейного программи-
рования с двухсторонними ограничениями, в которой переменные задачи —
действительные числа, а коэффициенты целевой функции, функций ограни-
Рис. 2. Различные случаи выполнения и нарушения интервальных ограничений
][ 11
iBd
][ 12
iBd ][ 21
iBd ][ 22
iBd
][1
iYd ][2
iYd
][ 11
iBd ][ 12
iBd ][ 21
iBd ][ 22
iBd
][1
iYd ][2
iYd
][ 11
iBd
][ 12
iBd ][ 21
iBd ][ 22
iBd
][1
iYd
][2
iYd
][ 11
iBd ][ 12
iBd
][ 21
iBd ][ 22
iBd
][1
iYd ][2
iYd
][ 11
iBd ][ 12
iBd ][ 21
iBd ][ 22
iBd
][ 11
iYd
][ 12
iYd
][ 11
iBd ][ 12
iBd
][ 21
iBd ][ 22
iBd
][1
iYd
][2
iYd
][ 11
iBd
][ 12
iBd ][ 21
iBd ][ 22
iBd
][1
iYd ][2
iYd
][ 11
iBd
][ 12
iBd ][ 21
iBd ][ 22
iBd
][1
iYd ][2
iYd
][ 11
iBd
][ 12
iBd ][ 21
iBd ][ 22
iBd
][1
iYd ][2
iYd
а
б
в
ж
г
д
е
з
и
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 118
чений, а также их граничных значений представлены нечеткими множест-
вами, могут рассматриваться следующие модели. В результате решения за-
дачи значения функций ограничений и критерия оптимальности будут пред-
ставлены нечеткими множествами. В данных условиях ограничения задачи
могут быть сформулированы в форме принадлежности интервала расчетных
значений абсцисс нечетких множеств выходных переменных заданным ин-
тервалам допустимых значений, а критерий оптимальности — в виде много-
критериальной задачи оптимизации значений сумм координат абсцисс
функций принадлежности правых и левых частей установленных сечений
нечеткого множества критерия оптимальности.
Граничные значения на переменные задачи, т.е. значения 1
jh и 2
jh , мо-
гут быть как отрицательными, так и положительными значениями. Обозна-
чим 1~
J — подмножество переменных задачи, для которых 01 jh и следова-
тельно 02 jh , т.е. }0,0|
~
{
~ 211 jj hhJjJ , а также ,0|
~
{
~ 12 jhJjJ
}02 jh и }0,0|
~
{
~ 213 jj hhJjJ .
Поскольку значения коэффициентов функции цели и функций ограни-
чений задачи в зависимости от знака переменной вычисляются по различ-
ным формулам,
;0if],[
,0if],[
][ 2
1
1
jj
jj
j
xCd
xCd
CD
;0if],[
,0if],[
][ 1
2
2
jj
jj
j
xCd
xCd
CD
;0if],[
,0if],[
2
1
1
jij
jij
ij
xAd
xAd
AD
,0if],[
,0if],[
][ 1
2
2
jij
jij
ij
xAd
xAd
AD (4)
то детерминированный эквивалент задачи нечеткого линейного программи-
рования должен быть представлен не одной задачей, а последовательностью
решения некоторого множества задач линейного программирования с раз-
личными математическими моделями, учитывающими все возможные ком-
бинации знаков переменных задачи. Если количество переменных подмно-
жества 1~
J равно 1m , подмножества 2~
J — 2m и подмножества 3~
J — 3m
(где mmmm 321 ), то необходимо решить 22
m различных задач этого
типа. Так, например, в случае 31 m , 22 m и 13 m необходимо решить
422 таких задач. Комбинации знаков переменных и коэффициентов этих
задач:
1) (+ + + – – –), 2) (+ + + – + –), 3) (+ + + + – –), 4) (+ + + + + –).
Как видно из формул (3) и (4), в каждой из математических моделей
этих задач все коэффициенты )]([1 jCD , )]([2 jCD , а также )]([1 ijAD ,
)]([2 ijAD при переменных подмножества 1~
J рассчитываются по различ-
ным формулам как для положительных значений переменных, так и для
подмножества 3~
J — для отрицательных значений, а для переменных под-
Задачи нечеткого линейного программирования с двухсторонними ограничениями …
Системні дослідження та інформаційні технології, 2018, № 2 119
множества 2~
J — в зависимости от знака этой переменной, выбранной
в данной конкретной комбинации. Среди всех допустимых решений этих
задач выбирается решение с лучшим значением критерия оптимальности:
;))](([min
1
1
],[
1
21
n
j
kjj
hhX
k CDxF
,,...,1,0,))](([min
1
2
],[
2
21
KkCDxF
n
j
kjj
hhX
k
либо
)(min
1],[
3
21
n
j
jj
hhX
CGxF
(5)
в условиях ограничений на переменные (1), а также различных требований
выполнения системы ограничений
;,...,1,0)),(((ˆ))](((ˆ[))((ˆ 2
1
1 KkBdAdxBd ki
n
j
kijjki
ni ,...,1 .
Здесь )(ˆ d — значения )(1 d или )(2 d в зависимости от различных требова-
ний выполнения ограничений предусматривают их безусловное или услов-
ное (менее строгое) их выполнение.
Множество критериев (4) представим аддитивной сверткой критериев
,))](([))](([min
0 1
22
1
11
],[ 21
K
k
n
j
kjjk
n
j
kjjk
hhX
CDxCDx (6)
где 01 k , 02 k — весовые коэффициенты, удовлетворяющие условиям
1)(
0
21
K
k
kk .
Рассмотрим различные виды детерминированных эквивалентов рас-
сматриваемых в работе задач нечеткого линейного программирования.
Задачи 1, 2, 3 (безусловное выполнение системы ограничений). Не-
обходимо решить 22m задач линейного программирования, в каждой из ко-
торых требуется минимизировать критерий оптимальности (5) или (6), либо
критерий
,)]([min
0 1],[ 21
K
k
n
j
kjjk
hhX
CDx (7)
где )]}([)]([{5,0)]([ 21
kjkjkj CDCDCD , Kk ,...,1,0 , в условиях сис-
темы ограничений для Kk ,...,1,0 ;
)]([)]([)]([ 21
1
12
ki
m
j
jkij
p
ki BdxADBd
, 2,1p , ni ,...,1 . (8)
Если в задаче используются коэффициенты )]([1
kjCD и )]([1
kijAD ,
2,...,1 mj , ni ,...,1 , то ограничения на детерминированные значения пе-
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 120
ременных должны быть в виде 20 jj hx . Коэффициенты )]([2
kjCD и
)]([2
kijAD , ni ,...,1 , используются для подмножества переменных 3~
J , т.е.
mmj ,...,12 , а также подмножества переменных 2~
J при условии, что на
все эти переменные будут наложены ограничения 01 jj xh , 2,...,1 mj .
Среди всех допустимых решений этих задач находим решение с наи-
меньшим значением целевой функции. Данное решение и принимается
в качестве решения сформулированной задачи нечеткого линейного про-
граммирования. В большинстве практических приложений все переменные
задачи — положительные действительные числа, т.е. 02 m и 12 2 m , мо-
дель детерминированного эквивалента задачи нечеткого линейного про-
граммирования однозначна, и необходимо решать только одну из рассмат-
риваемых задач.
Если ни одна из сформулированных 22m детерминированных задач не
имеет допустимых решений, то решений исходной задачи в условиях безус-
ловного выполнения всей системы ограничений не существует. В этом слу-
чае могут быть рассмотрены различные постановки задач, предусматри-
вающие выполнение системы ограничений в слабом смысле.
Задачи 4, 5, 6 (условное выполнение системы ограничений). Необ-
ходимо решить 22m задач линейного программирования, в каждой из кото-
рых требуется минимизировать критерий оптимальности (5) или (6), либо
(7) в условиях системы ограничений
)]([)]([)]([ 22
1
11
ki
m
j
jkijki BdxADBd
, Kk ,...,1,0 , 2,1p , ni ,...,1 , (9)
)]}([)]([{5,0)]([ 21
kijkijkij ADADAD , а значения )]([1
kijAD и
)]([2
kijAD вычисляются по формулам
;0if,)]([
,0if,)]([
)]([ 2
1
1
jkij
jkij
kij xAd
xAd
AD
.0if,)]([
,0if,)]([
)]([ 1
2
2
jkij
jkij
kij xAd
xAd
AD
При этом ограничения на переменные jx , mj ,...,1 , устанавливаются ана-
логично описанным в задачах 1–3.
Кроме того, могут рассматриваться более слабые, чем в задачах 1–3,
условия, которые определяют менее строгое выполнение системы ограниче-
ний:
)]([)]()]([[)]([ 22
1
11
ki
m
j
jkijkij
p
ki BdxADBd
, 2,1p , ni ,...,1 .
Задачи 7, 8, 9 (выполнение системы ограничений в слабом смысле).
Необходимо решить 22m задач линейного программирования, в каждой из
которых требуется минимизировать критерий оптимальности (5) или (6),
либо (7) в условиях системы ограничений
)()()( 2
1
1
i
m
j
jiji BGxAGBG
, ni ,...,1 .
Задачи нечеткого линейного программирования с двухсторонними ограничениями …
Системні дослідження та інформаційні технології, 2018, № 2 121
Задачи 10, 11, 12 (выполнение системы ограничений в слабом смыс-
ле). Необходимо решить 22m задач линейного программирования, в каждой
из которых требуется минимизировать критерий оптимальности (5) или (6),
либо (7) в условиях системы ограничений (9) для значений ,01 kk
Kk ,...,11 , а для значений )1(,...,2,1,0 1 kk — выполнение только одной
из пары ограничений
m
j
jkij
p
ki xADBd
1
11 )]([)]([ ,
либо
)]([)]([ 22
1
ki
m
j
jkij
p BdxAD
, )1(,...,2,1,0 1 kk , ni ,...,1 .
То есть для сечений с малым значением функций принадлежности не
требуется строгого выполнения двухсторонних ограничений, а ставится
требование выполнения только одного из них, а в некоторых случаях допус-
кается, что не будет выполнено ни одно из них. Выбор значений 1kk , а
также степени важности одного из пары ограничений является субъектив-
ным, зависит от специфики прикладной задачи и решения ЛПР.
Как и в задачах 1–3, во всех задачах 4–12, предусматривающих выпол-
нение всей системы ограничений в слабом смысле, в случае получения до-
пустимого решения некоторых из сформулированных задач в качестве ре-
шения задачи нечеткого линейного программирования в условиях условного
выполнения системы ограничений принимается допустимое решение детер-
минированной задачи с наилучшим значением критерия оптимальности. Ес-
ли ни одна из сформулированных задач не имеет допустимого решения, то
в сформулированной постановке решения исходной задачи нечеткого ли-
нейного программирования не существует.
Следует отметить, что для большинства практических приложений
значения переменных задачи могут быть только положительными действи-
тельными числами, т.е. 012 jj hh , mj ,...,1 . В этом случае 02 m и необ-
ходимо решать только одну из каждого вида детерминированных за-
дач 1–12.
Обозначим соответственно 0
~
и l
~ , Ll ,...,1 , множества значений пе-
ременных задачи, удовлетворяющих системе неравенств, обеспечивающих
безусловное и различного вида нестрогое (условное) выполнение ограниче-
ний для нечетких множеств сформулированной задачи; 3
0F , 0 и 3
lF , l ,
Ll ,...,1 , — соответственно минимальные значения критериев оптимально-
сти в решении этих задач.
Утверждение. 1. Так как l
~~
0 , то 0l , 3
0
3 FFl , Ll ,...,1 .
2. Если l
~~ , то l , 33
FFl , Ll ,...,1, .
Предлагается следующий процесс решения сформулированной про-
блемы. Формулируется детерминированный эквивалент, предусматриваю-
щий безусловное выполнение всех ограничений задачи в виде задач 1–3 при
условии выполнения системы неравенств в виде (8). Если какая-то из сфор-
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 122
мулированных 22m задач имеет допустимое решение, то на этом процесс
поиска решений завершается. В противном случае формулируем различные
виды детерминированных эквивалентов, предусматривающих нестрогое
(условное) выполнение всех ограничний в виде задач 1–3 при условии вы-
полнения системы неравенств в виде (9), либо в форме задач 4–12. При этом
в соответствии с решением экспертного совета и ЛПР на каждом из после-
дующих этапов определяется и увеличивается то подмножество неравенств
и (или) сечений, для которых могут быть ослаблены требования выполнения
ограничений. Этот процесс продолжается до тех пор, пока на некотором
этапе не будет получено допустимое решение одной из сформулированных
задач.
ЗАКЛЮЧЕНИЕ
Сформулирована задача нечеткого линейного программирования c двух-
сторонними ограничениями детерминированных значений переменных и
линейными функциями, в которой левые и правые граничные значения
линейных функций, коэффициенты ограничений и критерия оптимальности
суть нечеткие множества, преставленные fuzzy-интервалами с LR -функциями
принадлежности общего вида.
Предложены правила ранжирования и оценки доминирования для не-
четких множеств, установлены условия безусловного (строгого) и условного
(нестрогого) выполнения ограничений для нечетких множеств с функциями
принадлежности, представленных LR fuzzy-интервалами.
Предложены различные детерминированные эквиваленты сформулиро-
ванных задач нечеткого линейного программирования в условиях, когда пе-
ременные задачи могут принимать как положительные, так и отрицательные
значения в виде решения 22m детерминированных задач линейного про-
граммирования, предусматривающие различные требования к строгости вы-
полнения всей системы ограничений. Каждая из этих 22m задач содержит
существенно большее количество ограничений, но может быть решена сим-
плексным методом линейного программирования. Если переменные задачи
могут принимать только неотрицательные значения, то каждый детермини-
рованный эквивалент представлен только одной задачей.
В случае отсутствия решения задачи, обеспечивающего безусловное
выполнение всей системы fuzzy-ограничений, последовательное ослабление
требований к выполнению отдельных неравенств и формулирование раз-
личного вида детерминированных эквивалентов, обеспечивающих нестро-
гое выполнение ограничений для нечетких множеств (fuzzy-множеств), про-
исходит на основе субъективных соображений ЛПР в соответствии со
спецификой решаемой задачи.
В подавляющем большинстве практических задач принятия решений
все действительные значения переменных задачи могут принимать только
положительные значения. Следовательно, 02 m и 12 2 m , и в зависимо-
сти от требования к строгости выполнения ограничений необходимо решать
не несколько, а только одну задачу каждого класса. Однако для некоторых
задач управления промышленными объектами возможны и отрицательные
Задачи нечеткого линейного программирования с двухсторонними ограничениями …
Системні дослідження та інформаційні технології, 2018, № 2 123
значения управляющих переменных (например, если они заданы в отклоне-
ниях от стандартной величины), для которых предлагаемые математические
модели и алгоритмы найдут приктические приложения.
ЛИТЕРАТУРА
1. Шаталова А.Ю. Нечеткое линейное программирование в задачах оптимально-
го финансирования инвестиционных проектов, максимизирующей полу-
чаемый предприятием доход / А.Ю. Шаталова, К.А. Лебедев // Междуна-
родный журнал прикладных и фундаментальных исследований. — 2015. —
№ 9–1. — С. 35–38;
2. Шведов А.С. Нечеткое математическое программирование: краткий обзор /
А.С. Шведов // Проблемы управления. — М., № 3, 2017. — С. 2–10.
3. Zimmermann H-J. Fuzzy programming and linear programming with several objec-
tive functions / H-J. Zimmermann // Fuzzy Sets and Systems. — 1978. — Vol. 1.
— P. 45–57.
4. Rommelfanger H.J. Fuzzy-Optimierungsmodelle in praktischen Anwendungen //
Multi-Criteria und Fuzzy-Systeme in Theorie und Praxis. — Deutscher Univer-
sitäts-Verlag, Wiesbaden 2003. — P. 95–113.
5. Rommelfanger H.J. Entscheiden bei Unschärfe. Fuzzy Decision Support System /
H.J. Rommelfanger. — Springer Verlag, Berlin-Heidelberg, Second edition 1994.
6. Зайченко Ю.П. Нечеткие модели и методы в интеллектуальных системах /
Ю.П. Зайченко. — К.: Слово, 2008. — 344 с.
7. Sakawa M. Fuzzy Sets and multiobjektive optimization / M. Sakawa. — N-Y: Ple-
num Press, 1993. — 380 p.
8. Maleki H.R. Linear programming with fuzzy variables / H.R. Maleki, M. Tata,
M. Mashinchi // Fuzzy Sets and Systems. — 2000. — Vol. 109. — P. 21–33.
9. Mahdavi-Amiri N. Duality in fuzzy number linear programming by use of a certain
linear ranking function / N. Mahdavi-Amiri, S.H. Nasseri // Applied Mathematics
and Computation. — 2006. — Vol. 180. — P. 206–216.
10. Delgado M. A general model for fuzzy linear programming / M. Delgado, J.L. Ver-
degay, M.A. Vila // Fuzzy sets and System. — Vol. 29. — 1989. — P. 21–29.
11. Bellman R.E. Decision-Making in Fuzzy Environment / R.E. Bellman, L.A. Zadeh //
Management Science. — 1970. —Vol. 17. — N 4. — P.141–160.
12. Беллман Р. Принятие решений в расплывчатых условиях / Р. Беллман, Л. Заде //
Вопросы анализа и процедуры принятия решений. — М.: Мир, 1976. —
С. 172–215.
13. Орловский С.А. Проблемы принятия решений при нечеткой исходной инфор-
мации / С.А. Орловский // М.: Радио и связь, 1981. — 286 с.
14. Згуровский М.З. Модели принятия решений в нечетких условиях /
М.З. Згуровский, Ю.П. Зайченко. — К.: Наук. думка. — 211 с.
15. Зак Ю.А. Принятие решений в условиях размытых и нечетких данных /
Ю.А. Зак. — М.: URSS, 2013. — 352 c.
16. Зак Ю.А. Четкий эквивалент задачи Fuzzy-линейного пограммирования /
Ю.А. Зак // Проблемы управления и информатики. — К., 2011. — № 1. —
С. 87–101.
17. Зак Ю.А. Многокритериальные задачи математического программирования
с размытыми ограничениями. Математические модели схем компромисса.
Выбор решений из конечного множества альтернатив // Кибернетика и сис-
темный анализ. — К., 2010. — № 5. — С. 80–89.
Поступила 01.09.2017
|
| id | journaliasakpiua-article-139961 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:24:05Z |
| publishDate | 2018 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/95/8ddd83f2ea4fe2f23445f18a552b6095.pdf |
| spelling | journaliasakpiua-article-1399612019-01-17T13:29:35Z Problems of fuzzy-linear programming with two-sided constraints and parameters of objective functions and constraints in the form of fuzzy sets Задачи нечеткого линейного программирования с двухсторонними ограниченииями и параметрами целевых функций и ограничений в виде нечетких множеств Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин Zack, Yuriy A. fuzzy-linear programming fuzzy-intervals with LR-representation of membership functions conditions for dominance of fuzzy sets two-way interval constraints deterministic equivalent нечеткое линейное программирование fuzzy-интервалы с -пред-ставлением функций принадлежности условия доминирования нечетких множеств двухсторонние интервальные ограничения детерминированный эквивалент fuzzy-лінійне програмування fuzzy-інтервали з LR-подан- ням функцій приналежності умови домінування нечітких множин двосторонні інтервальні обмеження детермінований еквівалент The deterministic equivalents of the tasks of fuzzy linear programming with two-sided constraints on the deterministic values of variables that can take both positive and negative values are proposed, and the coefficients of the goal function and the linear constraint functions, as well as the left and right boundary values on their values, are fuzzy sets, represented by fuzzy-intervals with membership functions with LR-representation of the most general kind. Based on the rules of ranking and estimating the dominance of fuzzy sets considered in the work, conditions for unconditional (strict) and conditional (non-strict) fulfillment of restrictions are established. The different kinds of deterministic equivalents of the problem in which the execution of fuzzy constraints with different degrees of severity is required, involve solving not one but several sets of linear programming problems. The best possible solution is chosen. Предложены детерминированные эквиваленты задач нечеткого линейного программирования c двухсторонними ограничениями на детерминированные значения переменных, которые могут принимать как положительные, так и отрицательные значения, а коэффициенты функции цели и линейные функции ограничений, а также левые и правые граничные их значения — нечеткие множества, преставленные fuzzy-интервалами с LR-представлением функций принадлежности общего вида. На основе рассмотренных в работе правил ранжирования и оценки доминирования нечетких множеств установлены условия безусловного (строгого) и условного (нестрогого) выполнения ограничений. Различного вида детерминированные эквиваленты задачи, в которых требуется выполнение fuzzy-ограничений с различной степенью строгости, предусматривают решения не одной, а некоторого множества задач линейного программирования. Выбирается наилучшее из допустимых решений. Запропоновано детерміновані еквіваленти задач нечіткого лінійного програмування з двосторонніми обмеженнями на детерміновані значення змінних, які можуть набувати як додатних, так і від’ємних значень, а коефіцієнти функції мети і лінійні функції обмежень, а також ліві та праві граничні їх значення — нечіткі множини, подані fuzzy-інтервалами із LR-поданням функції належності загального вигляду. На підставі розглянутих в роботі правил ранжирування і оцінки домінування нечітких множин установлено умови безумовного (строгого) і умовного (нестрогого) виконання обмежень. Різного виду детерміновані еквіваленти задачі, у яких слід дотримуватися fuzzy-обмежень з різним ступенем строгості, передбачають розв’язання не однієї, а деякої множини задач лінійного програмування. Вибирається найкращий з допустимих розв’язків. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-06-20 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/139961 10.20535/SRIT.2308-8893.2018.2.11 System research and information technologies; No. 2 (2018); 111-123 Системные исследования и информационные технологии; № 2 (2018); 111-123 Системні дослідження та інформаційні технології; № 2 (2018); 111-123 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/139961/137016 Copyright (c) 2021 System research and information technologies |
| spellingShingle | fuzzy-лінійне програмування fuzzy-інтервали з LR-подан- ням функцій приналежності умови домінування нечітких множин двосторонні інтервальні обмеження детермінований еквівалент Zack, Yuriy A. Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| title | Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| title_alt | Problems of fuzzy-linear programming with two-sided constraints and parameters of objective functions and constraints in the form of fuzzy sets Задачи нечеткого линейного программирования с двухсторонними ограниченииями и параметрами целевых функций и ограничений в виде нечетких множеств |
| title_full | Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| title_fullStr | Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| title_full_unstemmed | Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| title_short | Задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| title_sort | задачі нечіткого лінійного програмування з двосторонніми обмеженнями і параметрами цільових функцій та обмежень у вигляді нечітких множин |
| topic | fuzzy-лінійне програмування fuzzy-інтервали з LR-подан- ням функцій приналежності умови домінування нечітких множин двосторонні інтервальні обмеження детермінований еквівалент |
| topic_facet | fuzzy-linear programming fuzzy-intervals with LR-representation of membership functions conditions for dominance of fuzzy sets two-way interval constraints deterministic equivalent нечеткое линейное программирование fuzzy-интервалы с -пред-ставлением функций принадлежности условия доминирования нечетких множеств двухсторонние интервальные ограничения детерминированный эквивалент fuzzy-лінійне програмування fuzzy-інтервали з LR-подан- ням функцій приналежності умови домінування нечітких множин двосторонні інтервальні обмеження детермінований еквівалент |
| url | https://journal.iasa.kpi.ua/article/view/139961 |
| work_keys_str_mv | AT zackyuriya problemsoffuzzylinearprogrammingwithtwosidedconstraintsandparametersofobjectivefunctionsandconstraintsintheformoffuzzysets AT zackyuriya zadačinečetkogolinejnogoprogrammirovaniâsdvuhstoronnimiograničeniiâmiiparametramicelevyhfunkcijiograničenijvvidenečetkihmnožestv AT zackyuriya zadačínečítkogolíníjnogoprogramuvannâzdvostoronnímiobmežennâmiíparametramicílʹovihfunkcíjtaobmeženʹuviglâdínečítkihmnožin |