Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования
Розв’язання задачі fuzzy-лінійного програмування зведено до розв’язання деякої детермінованої нелінійної екстремальної задачі. Запропоновано правила ранжування та оцінки домінування для fuzzy-множин, заданих LR fuzzy-інтервалами. Встановлено властивості монотонності fuzzy-множин, лівих частин обмеже...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207281 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования / Ю.А. Зак // Проблемы управления и информатики. — 2011. — № 1. — С. 87–101. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859929653856174080 |
|---|---|
| author | Зак, Ю.А. |
| author_facet | Зак, Ю.А. |
| citation_txt | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования / Ю.А. Зак // Проблемы управления и информатики. — 2011. — № 1. — С. 87–101. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розв’язання задачі fuzzy-лінійного програмування зведено до розв’язання деякої детермінованої нелінійної екстремальної задачі. Запропоновано правила ранжування та оцінки домінування для fuzzy-множин, заданих LR fuzzy-інтервалами. Встановлено властивості монотонності fuzzy-множин, лівих частин обмежень і критерію оптимальності задачі щодо вектора детермінованих змінних. Розроблено алгоритми розв’язання задачі на основі модифікованого методу «гілок і границь».
The solution of problem of fuzzy-linear programming is reduced to solution of a determinate nonlinear extremal problem. The rules of ranking and domination estimate for fuzzy sets represented by LR fuzzy intervals are proposed. The properties of fuzzy sets monotonicity, left-hand parts of bounds and optimality criterion of the problem relative to the vector of determined variables are defined. The algorithms of problem solving on the basis of modified branch-and-bound method are developed.
|
| first_indexed | 2025-12-07T16:08:16Z |
| format | Article |
| fulltext |
© Ю.А. ЗАК, 2011
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 87
УДК 519.8
Ю.А. Зак
ДЕТЕРМИНИРОВАННЫЙ ЭКВИВАЛЕНТ
И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ
FUZZY-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Введение
Классические стратегические проблемы принятия решений на перспективу
зачастую используют постановки задачи, формулировки и оценки, связанные с
неопределенностью и лингвистическими понятиями, что существенно осложняет
построение их адекватных математических моделей, основанных на количествен-
ных данных. Используемые в таких математических моделях количественные па-
раметры (особенно те, которые описывают поведение системы в будущем) могут
быть заданы только их оценочными или качественными значениями. Это может
привести к тому, что детерминированные математические модели будут доста-
точно грубо описывать реально решаемую проблему. Попытки построения веро-
ятностных моделей в этих ситуациях в ряде случаев недостаточно эффективны,
так как часто связаны с серьезными трудностями из-за отсутствия достаточных
объемов статистических данных, невозможностью адекватно предсказать поведе-
ние системы в будущем на основе исторических данных, а также возникающими
дополнительными сложностями решения стохастических проблем.
Использование в математических моделях вместо не точно известных ко-
личественных данных их средних значений и моментов более высоких порядков
при недостаточных объемах статистических данных может привести к решению
нереальной проблемы и получению недопустимого для реальной ситуации ре-
шения. В настоящее время широкое распространение находят подходы, основан-
ные на использовании нечеткой логики и fuzzy-интервалов (см., например, [1–8]).
Как следует из многих публикаций и практических приложений, использование
fuzzy-технологий в принятии решений позволяет представить более адекватную
картину реальной проблемы и получить допустимое и более эффективное решение.
Постановкам, математическим формулировкам и методам решения задач ма-
тематического программирования, в которых параметры математических моде-
лей, правые части ограничений и коэффициенты целевых функций могут быть
выражены fuzzy-логическими множествами, уделялось значительное внимание
(в монографиях и периодической литературе).
В отличие от предлагаемых прямых методов решения задачи fuzzy-линей-
ного программирования, использующих методы абсолютного и относительного
предпочтения fuzzy-множеств, в настоящей работе предлагается детерминирован-
ный эквивалент сформулированной задачи, исследуются его математические
свойства, на основе которых предложены методы решения этой задачи. Подходы
и методы решения этой задачи могут использоваться как для решения непрерыв-
ных, так и дискретных задач fuzzy-линейного программирования и определенного
класса задач fuzzy-нелинейного программирования. Кроме того, на их основе мо-
гут разрабатываться алгоритмы решения некоторого класса задач стохастического
математического программирования.
1. Постановка и математическая формулировка задачи
Рассматривается задача fuzzy-линейного программирования вида
max2211 nnjj xCxCxCxC (1)
88 ISSN 0572-2691
при ограничениях
,HX },...,,1,{ 21 njhxhXH jjj
n (2)
,Re2211 ininjijiii bxaxaxaxaXA .,,1 Ki (3)
Здесь HX — вектор детерминированных переменных, на которые условия-
ми (2) наложены двухсторонние ограничения; nj CCCC ,,,,, 21 — fuzzy-чис-
ла (множества), представленные LR-интервалами
,)}(),(),(),({ 2121 LRjjjj cdcdcmcm ;,,1 nj
ija — fuzzy-числа (множества), представленные LR-интервалами
,)}(),(),(),({ 2121 LRijijijij adadamam ,,,1 Ki ;,,1 nj
ib — fuzzy-числа (множества), представленные LR-интервалами
,)}(),(),(),({ 2121 LRiiii bdbdbmbm .,,1 Ki
Условия Re или Re определяют условия доминирования (предпочтения) двух
fuzzy-множеств соответственно в сторону уменьшения или увеличения их зна-
чений, — алгебраическая сумма двух fuzzy-множеств.
Функции принадлежности таких fuzzy-чисел ,A представленных трапеце-
видными LR-интервалами, вычисляются по формулам
).()()(если,
)(
)()(
),()(если,1
),()()(если,
)(
)()(
,)()(или)()(если,0
)(
222
2
22
21
111
1
11
2211
AdAmxAm
Ad
xAdAm
AmxAm
AmxAdAm
Ad
AdAmx
xAdAmxAdAm
x
A (4)
Если ),()()( 21 AmAmAm то функции принадлежности (4) вырождается
в центральный треугольник вида
).()()(если,
)(
)()(
),()()(если,
)(
)()(
,)()(или)()(если,0
)(
2
2
2
1
1
1
21
AdAmxAm
Ad
xAdAm
AmxAdAm
Ad
AdAmx
xAdAmxAdAm
x
A
(5)
Отметим, что если в формуле (4) LR-интервала ,0)(1 Ad то функции при-
надлежности вырождаются в правостороннюю трапецию. Виды этих функций
представлены на рис. 1, 2.
Если в функции принадлежности вида (4) ,0)(2 Ad то она вырождается в ле-
востороннюю трапецию. Если )()()( 21 AmAmAm и ,0)(1 Ad то (5) преобразу-
ется в правосторонний треугольник, а в случае )()()( 21 AmAmAm и 0)(2 Ad —
в левосторонний.
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 89
1.0
)(xA
x
)(1 Ad )(1 Am )(2 Ad )(2 Am
Рис. 1
1.0
)(xA
x
)(1 Ad )(2 Ad )(Am
Рис. 2
Результатом выполнения соответствующих операторов fuzzy-арифметики (1)
и (2) являются некоторые fuzzy-множества, представленные LR-интервалами
LRDDMM },,,{ 0
2
0
1
0
2
0
1 — для целевой функции и ,},,,{ 2121 LR
iiii DDMM ,,,1 Ki —
для ограничений.
2. Правила доминирования для fuzzy-множеств,
представленных LR fuzzy-интервалами
Рассмотрим два fuzzy-множества: ,A представленное LR fuzzy-интервалом
LRAdAdAmAm )}(),(),(),({ 2121 , и ,B представленное LR fuzzy-интервалом
LRBdBdBmBm )}(),(),(),({ 2121 . Fuzzy-множество A предпочтительнее множества
B )( BA в смысле fuzzy-отношения ,Re BA если справедливы неравенства
P
p
pp AdAdAmAm
1
1221 )}()({
2
1
)}()({
2
1
,)}()({
2
1
)}()({
2
1
1
1221
P
p
pp BdBdBmBm (6)
т.е. если средневзвешенная сумма середины интервалов P сечений функции при-
надлежности множества A больше соответствующей средневзвешенной суммы
середины интервалов этих же P сечений функции принадлежности множества .B
В выражении (6), например, может быть принято: 1) ,3P ,3,01 ,6,02
;9,03 2) ,5P ,2,01 ,4,02 ,7,03 ,85,04 .0,15
Количество сечений может быть увеличено. Как частный случай (6) рассмотрим
выражение, в котором значения середин интервалов в каждом из сечений учитывают-
ся с одинаковым весом, предложенное в [1]
P
p
p AdAdAmAm
1
1221 )}()({
2
1
)}()({
2
1
.)}()({
2
1
)}()({
2
1
1
1221
P
p
p BdBdBmBm (7)
90 ISSN 0572-2691
На рис. 3 показано, что fuzzy-множество .Re BA Поэтому середины интерва-
лов всех сечений fuzzy-множества A (трапеция 4321 AAAA , изображенная сплош-
ными линиями, а середины всех ее -сечений лежат на прямой, соединяющей точки
L1(A) и L2(A)) расположены правее середин интервалов всех сечений fuzzy-
множества B (трапеция 4321 BBBB изображена пунктирными линиями, а середины
всех ее -сечений лежат на прямой, соединяющей точки L1(В) и L2(В)), т.е. имеют
бóльшие значения координаты x. Следовательно, выполняется как условие (6), так
и условие (7).
x
y
1,0
0,25
0,5
0,75
0,9
1A
L
2
(B
)
L
2
(A
)
L
1
(B
)
L
1
(A
)
2A 3A
4A 1B
2B
4B
3B
Рис. 3
Определим некоторые свойства доминирования fuzzy-множеств, заданных LR
fuzzy-интервалами.
Отношения доминирования двух fuzzy-множеств на основе параметров их
-сечений формулирует следующее утверждение.
Утверждение 1. Если справедливы неравенства
dALALAL )0,1()]()([
2
1
)( 121
1
0
dBLBLBL )0,1()]()([
2
1
)( 121
1
0
(8)
или в дискретном случае
)0,1()]()([
2
1
)( 121
1
p
P
p
p ALALAL
,)0,1()]()([
2
1
)( 121
1
p
P
p
p BLBLBL (9)
где ,10 p ,,,1 Pp ,1 pp то для рассматриваемых fuzzy-множеств
A и B справедливы fuzzy-отношения доминирования BA в смысле .Re BA
Если для двух fuzzy-множеств A и B справедливо хотя бы одно из системы
неравенств
),()( 11 BmAm ),()( 22 BmAm ),()( 11 BdAd );()( 22 BdAd (10)
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 91
),()( 11 BmAm ),()( 22 BmAm ),()( 11 BdAd );()( 22 BdAd (11)
),()( 11 BmAm ),()( 22 BmAm ),()( 11 BdAd );()( 22 BdAd (12)
),()( 11 BmAm ),()( 22 BmAm ),()( 11 BdAd ),()( 22 BdAd (13)
то ,Re BA т.е. .BA
Вычислим значения
)],()([
2
1
)( 211 AmAmAL )];()()()([
2
1
)( 22112 AdAmAdAmAL (14)
)],()([
2
1
)( 211 BmBmBL .)]()()()([
2
1
)( 22112 BdBmBdBmBL (15)
Если рассматривать fuzzy-числа типа , введенные в [2], то переменная x
определяется по формуле
,)(если,0
,)(если,
x
xx
x
A
A
(16)
а вместо )(2 AP и )(2 BP могут быть введены точки
),),(()( 33 ALAP ),),(()( 33 BLBP (17)
где
,)]1)(()()1)(()([
2
1
)( 22113 AdAmAdAmAL (18)
.)]1)(()()1)(()([
2
1
)( 22113 BdBmBdBmBL (19)
При использовании в дальнейшем fuzzy-чисел этого )( -го типа приме-
няются все приведенные ниже формульные выражения, только вместо точек
)(2 AP и )(2 BP подставляются )(3 AP и ).(3 BP
Определим в декартовой системе координат ),( yx четыре точки с коорди-
натами
),0,1),(()( 11 ALAP );0,0),(()( 22 ALAP
),0,1),(()( 11 BLBP ).0,0),(()( 22 BLBP
Запишем уравнения двух прямых, проходящих соответственно через точки
)(1 AP и ),(2 AP а также через точки )(1 BP и )(2 BP и середины всех -сечений
fuzzy-множеств A и :B
,0
)()(
)(
)()(
1
21
2
21
ALAL
AL
x
ALAL
y (20)
.0
)()(
)(
)()(
1
21
2
21
BLBL
BL
x
BLBL
y (21)
Утверждение 2. Если справедливы два неравенства:
)()( 11 BLAL и ),()( 22 BLAL (22)
то ,Re BA т.е. .BA
92 ISSN 0572-2691
Если выполняются условия утверждения 2, то прямые (20) и (21) либо совсем
не пересекаются, либо пересекаются в точке )()( 11 BPAP или ).()( 22 BPAP
Если условия утверждения 1 не выполняются, найдем точку пересечения прямых
(20) и (21), т.е. точку O с координатами
,
)()()()(
)]()()[()]()()[(
2112
122122
BLBLALAL
BLBLALALALBL
xO
(23)
.
)()()()(
)]()()[()]()()[(
)()(
)(
2112
122122
12
2
BLBLALAL
BLBLALALALBL
ALAL
AL
yO
(24)
Рассмотрим два треугольника: 11OBA и .22OBA Их вершины имеют следую-
щие координаты: 1A — ],0,1),([ 2 AL O — ],,[ 00 yx 1B — ];0,1),([ 2 BL 2A —
],0,0),([ 1 AL O — ],,[ 00 yx 2B — ].0,0),([ 1 BL
Вычислим площади этих треугольником по формуле Симпсона:
,))()(( cpbpappS
где )(
2
1
cbap — периметр треугольника, cba ,, — соответственно длины
его сторон. При этом:
длина стороны OA1 равна ;]0,1[])([ 22
21 OO yxALa
длина стороны 1OB — ;]0,1[)]([ 22
21 OoO yBLxb
длина стороны 11BA —
);()(если),()(
),()(если),()(
)]()([
2222
22222
221
BLALALBL
BLALBLAL
BLALc
длина стороны OA2 — ;])([ 22
22 OO yxALa
длина стороны 2OB — ;)]([ 22
22 OO yBLxb
длина стороны 22BA —
).()(если),()(
),()(если),()(
)]()([
1111
11112
112
BLALALBL
BLALBLAL
BLALc
Обозначим площадь первого треугольника ,1S а второго — .2S
Утверждение 3. Если справедливо неравенство
,
22
0,1
21 S
y
S
y OO
(25)
либо в случае, когда значения середин интервалов в каждом из сечений учитыва-
ются с одинаковым весом в соответствии с выражением (7), справедливо неравен-
ство ,21 SS то ,Re BA т.е. .BA
Выполнение условий утверждения 2 иллюстрирует рис. 3, а условий утвер-
ждения 3 — рис 4. На рис. 4 fuzzy-множество ,A представленное трапецией
4321 AAAA (сплошные линии), доминирует над множеством ,B представленным
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 93
трапецией 4321 BBBB (пунктирные линии), т.е. ,Re BA на основании правил до-
минирования (7), так как площадь 1S треугольника 11OBA меньше площади 2S
треугольника ,22OBA т.е. 21 SS и выполняются условия утверждения 2.
x
y
1,0
A2 B2
B1 A1
1A
2A
3A
4A 1B
2B
4B
3B
Рис. 4
Другой, более простой способ вычисления площади этих треугольников можно
использовать, если вычислить их высоты (значения 1 и ).2 Так как треугольники
11OBA и 22OBA подобны, то справедливы соотношения
)()(
)()(
22
11
2
1
BLAL
BLAL
или для fuzzy-чисел этого )( -го типа
)()(
)()(
33
11
2
1
BLAL
BLAL
,
)()()()(
)()(
1122
11
1
BLALBLAL
BLAL
,1 12 (26)
или fuzzy-чисел этого )( -го типа
,
)()()()(
)()(
)1(
1122
11
1
BLALBLAL
BLAL
.1 12 (27)
Здесь || — абсолютное значение соответствующей величины.
Если вычислены значения высот 1 и ,2 то площади треугольников могут
быть определены по более простым формулам:
,)()(
2
1
1111 BLALS .)()(
2
1
2222 BLALS )()( 22 BLAL . (28)
Утверждение 4. Если ),()( 11 BLAL )()( 22 BLAL и при этом
)],()([)]()([ 2211 ALBLBLAL (29)
и значения середин интервалов в каждом из сечений учитываются с одинаковым
весом, то справедливо неравенство ,21 SS следовательно, ,Re BA т.е. .BA
Доказательство утверждения получаем из цепочки неравенств ,21 по-
этому в соответствии с выражением (28) .21 SS
Если используются правила доминирования fuzzy-множеств (8), в которых
значения середин интервалов в каждом из сечений учитываются с различными ве-
сами, то справедлива следующая оценка условий доминирования.
94 ISSN 0572-2691
Утверждение 5. Если ),()( 11 BLAL )()( 22 BLAL и при этом
,
2
)()(
2
1
2
2
)()(
2
1 2
1122
1
1111
BLALSBLALS (30)
где в частном случае ,0 то
,Re BA т.е. .BA
3. Четкий детерминированный эквивалент fuzzy-оптимизационной задачи
3.1. Четкий детерминированный эквивалент проверки выполнения
ограничений. Пусть задан некоторый детерминированный вектор переменных
,HX ),,,,,,( 21 nj xxxxX удовлетворяющий системе ограничений (2). На
основе принципа расширения и c помощью операторов fuzzy-арифметики можно по-
строить fuzzy-множество iG левой части i-го неравенства системы ограничений (3),
функция принадлежности которого трапецеидальной формы также может быть пред-
ставлена с помощью LR-fuzzy-интервала .)}(),(),(),({ 2121 LRiiii GdGdGmGm
Утверждение 6. Если для fuzzy-множеств iG и iB справедливо хотя бы одно
из следующих двух неравенств:
),()( 11 ii GLBL ),()( 22 ii GLBL (31)
либо неравенства (28), (29) или (30), если значения середин интервалов учитыва-
ются с различными весами, где fuzzy-множество A соответствует множеству ,iB
а B — fuzzy-множеству ,iG то детерминированный вектор переменных HX
обеспечивает выполнение fuzzy-отношений ii BG Re и, следовательно, выполне-
ние i-го ограничения из системы (3).
Если условия утверждения 3 выполняются для каждого из ограничений
,,,1 Ki то детерминированный вектор HX удовлетворяет всей системе
ограничений задачи (3).
3.2. Четкий детерминированный эквивалент оптимальности целевой функ-
ции. Обозначим )(XF fuzzy-множество (fuzzy-число), определяющее значение целе-
вой функции для некоторого детерминированного вектора переменных .HX
Функция принадлежности fuzzy-множества )(XF — )]([)( XfXF также представ-
лена LR-fuzzy-интервалом вида .)]}([)],([)],([)],([{ 2121 LRXFdXFdXFmXFm
Пусть для данного fuzzy-множества )(XF по формулам, аналогичным (14), вычис-
лены значения )]([1 XFL и )]([2 XFL , а в соответствии с формулами (8) или (9) —
значения
dXFLXFLXFLXFW
1
0
121 )])([)]([)([0,1(
2
1
)]([)]([ (32)
или в дискретном выражении
.))([)]([()0,1(
2
1
)]([)]([
1
121
P
p
pp XFLXFLXFLXFW (33)
Утверждение 7. Если для двух значений вектора переменных задачи 1X и 2X
справедливо неравенство
)],([)]([ 21 XFWXFW (34)
либо эквивалентные ему неравенства (28), (29) или (30) при учете весов середин ин-
тервалов -сечений, где )( 1XF соответствует fuzzy-множеству ,A а )( 2XF — fuz-
zy-множеству ,B то fuzzy-множество )()( 21 XFXF в смысле ).()( 2
Re
1 XFXF
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 95
Следовательно, четкий детерминированный эквивалент задачи fuzzy-линей-
ного программирования формулируется следующим образом. Требуется найти
детерминированный вектор ,* HX удовлетворяющий ограничениям (2), а также
системе ограничений
),()( *
Re
* XBXG ii ,,,1 mi (35)
и обеспечивающий выполнение условий доминирования критерия оптимальности
среди всех удовлетворяющих системе ограничений векторов, т.е.
},,)]([)]([{ ** XXXFWXFW (36)
где
},...,1),()({ Re miXBXGHX ii . (37)
При этом для проверки выполнения отдельных ограничений задачи и проверки
доминирования значения критерия для различных векторов переменных HX
могут использоватьcя выражения (28) или неравенства (29), либо условия (30).
4. Определение граничных значений параметров
LR-интервалов fuzzy-множеств
Пусть LRXAdXAdXAmXAm )]}([)],([)],([)],([{ 2121 — LR-fuzzy-интервал
fuzzy-множества
nnjj xaxaxaxaXA 2211)( (38)
для некоторого значения вектора детерминированных переменных .sHX
Пусть
},,1,{ 2
21 j
s
j
s
j
s
j
s hxhnjxHX (39)
— некоторое подмножество значений вектора HX ( ,01 s
jh ,12
s
j
s
j hh ,,,1 nj
).,,1 Ss
Введем обозначения: )]},([{ 1
, XAms )]}([{ 1
, XAms — соответственно
нижняя и верхняя границы параметра )]([1 XAm для s-го подмножества возможных
значений детерминированного вектора переменных ;sHX )]},([{ 2
, XAms
)]}([{ 2
, XAms — соответственно нижняя и верхняя границы параметра )];([2 XAm
)]},([{ 1
, XAds )]}([{ 1
, XAds — нижняя и верхняя границы параметра
)]([1 XAd соответственно; )]},([{ 2
, XAds )]}([{ 2
, XAds — нижняя и верхняя
границы параметра )]([2 XAd соответственно.
Введем обозначения выполнения пар условий, используемых в последующих
выражениях: &0)(1 jam — величина )(1 jam не больше 0 и в выражении (38)
перед коэффициентом ja стоит знак ; &0)(1 jam — величина )(1 jam
больше 0 и в выражении (38) перед коэффициентом ja стоит знак . (Аналогич-
ным образом следует понимать и другие пары условий.)
Вычислим граничные значения )]([1 XAm , )]([2 XAm и )],([1 XAd :)]([2 XAd
,)()()]}([{
1
1
,
11
,
n
j
s
jj
s mqamXAm ,)()()]}([{
1
1
,
11
,
n
j
s
jj
s mqamXAm (40)
где
,&0)(или&0)(если,
,&0)(или&0)(если,
)(
111
112
1
,
jj
s
j
jj
s
js
j
amamh
amamh
mq (41)
96 ISSN 0572-2691
;&0)(или&0)(если,
,&0)(или&0)(если,
)(
111
112
1
,
jj
s
j
jj
s
js
j
amamh
amamh
mq (42)
,)()()]}([{
1
2
,
22
,
n
j
s
jj
s mqamXAm .)()()]}([{
1
2
,
22
,
n
j
s
jj
s mqamXAm (43)
Здесь
),()( 1
,
2
, mqmq s
j
s
j
),()( 1
,
2
, mqmq s
j
s
j
если ,0)()( 21 jj amam
),()( 1
,
2
, mqmq s
j
s
j
),()( 1
,
2
, mqmq s
j
s
j
если ;0)()( 21 jj amam
,)()()]}([{
1
1
,
11
,
n
j
s
jj
s dqadXAd ,)()()]}([{
1
1
,
11
,
n
j
s
jj
s dqadXAd (44)
где
),()( 1
,
1
, mqdq s
j
s
j
),()( 1
,
1
, mqdq s
j
s
j
если ,0)(1 jam
),()( 1
,
1
, mqdq s
j
s
j
),()( 1
,
1
, mqdq s
j
s
j
если ;0)(1 jam
,)()()]}([{
1
2
,
22
,
n
j
s
jj
s dqadXAd .)()()]}([{
1
2
,
22
,
n
j
s
jj
s dqadXAd (45)
В выражении (45) значения )( 2
, dqs
j
и )( 2
, dqs
j
вычисляются по формулам
),()( 1
,
2
, mqdq s
j
s
j
),()( 1
,
2
, mqdq s
j
s
j
если ,0)(1 jam
),()( 1
,
2
, mqdq s
j
s
j
),()( 1
,
2
, mqdq s
j
s
j
если .0)(1 jam
Утверждение 8. Если для подмножества детерминированных векторов sHX
в соответствии с (40)–(45) построено fuzzy-множество ,sD которое представлено
LR-fuzzy-интервалом ,)}(),(),(),({ 2
,
1
,
2
,
1
,
LR
ssss ddmm и справедливо соот-
ношение fuzzy-логическое неравенство вида
LRLR
ssss bdbdbmbmddmm )}(),(),(),({)}(),(),(),({ 2121Re2
,
1
,
2
,
1
,
, (46)
то в этом подмножестве не существует никакого такого вектора ,ss HX чтобы
fuzzy-множество s
nn
s
jj
sss xaxaxaxaXA 2211)( удовлетворяло
fuzzy-логическому неравенству .)( Re BXA s
Если же справедливо fuzzy-логическое неравенство вида
,)}(),(),(),({)}(),(),(),({ 2121Re2
,
1
,
2
,
1
,
LRLR
ssss bdbdbmbmddmm
(47)
то в подмножестве детерминированных переменных sHX не существует ника-
кого такого детерминированного вектора ,ss HX чтобы fuzzy-множество (29)
удовлетворяло fuzzy-логическому неравенству .)( Re BXA s
Для каждого подмножества детерминированных значений вектора ss HX
может быть определено некоторое граничное fuzzy-множество )],([ sXF выра-
женное LR-fuzzy-интервалом ,)}(),(),(),({ 2
,
1
,
2
,
1
,
LR
ssss ddmm где
,)()]}([{)(
1
,,,
j
n
j
s
j
sss xgXF
где ,,,, 2121 ddmm (48)
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 97
а соответствующие значения )( 1
, mg s
j
и )( 1
, dg s
j
вычисляются по формулам
,&0)([или&0)(если,
,&0)(или&0)(если,
)(
111
112
1
,
jj
s
j
jj
s
js
j
cmcmh
cmcmh
mg (49)
.&0)(или&0)(если,
,&0)(или&0)(если,
)(
11
1
2
111
1
,
jjj
jj
s
js
j
cdcdh
cdcdh
dg (50)
Значения )( 2
, mg s
j
и )( 2
, dg s
j
вычисляются по формулам, аналогичным
(49), (50), только вместо значений )(1 jcm подставляются соответственно значе-
ния )(2 jcm и ).(2 jcd
Для некоторого вектора ss HX на основе принципа расширения, используя
операции fuzzy-арифметики, можно построить в соответствии с выражением (1)
fuzzy-множество ),( sXF также определяемое LR-fuzzy-интервалом
.)]}([)],([)],([)],([{:)( 2121 LR
sssss XFdXFdXFmXFmXF
Утверждение 9. В подмножестве детерминированных векторов ss HX не
существует ни одного вектора, для которого справедливо fuzzy-логическое нера-
венство вида
Re2121 )]}([)],([)],([)],([{ LR
ssss XFdXFdXFmXFm
.)}(),(),(),({ 2
,
1
,
2
,
1
,
Re LR
ssss ddmm (51)
Следовательно, fuzzy-множество )],([ sXF параметры LR-fuzzy-интервала
которого определены в соответствии с формулами (48)–(50), является нижней
границей fuzzy-оптимального решения среди подмножества детерминированных
векторов .ss HX
5. Алгоритмы решения задачи
5.1. Общее описание метода. Решение сформулированного «четкого эквива-
лента» задачи fuzzy-линейного программирования может быть получено на осно-
ве модифицированного метода «ветвей и границ» (см. [9]).
На каждом шаге итеративного процесса область изменения какой-либо одной
из детерминированных переменных }{ 21 s
jj
s
j
s
j hxhH разобьем на две под-
области:
},,{ 211 s
j
s
j
s
jj
s
j
s
j hggxhH }.{ 22 s
jj
s
j
s
j hxgH (52)
Определим каждое из альтернативных подмножеств следующим образом:
s
n
s
j
s
j
s
j
sss HHHHHHH 1
1
121)1( , (53)
s
n
s
j
s
j
s
j
sss HHHHHHH 1
2
121)2( . (54)
Для каждого из этих подмножеств могут быть выполнены описанные ниже
итеративные процедуры исключения областей изменения переменных, не содер-
жащих допустимых планов. Кроме того, могут быть вычислены по приведенным
выше формулам оценки верхней границы оптимальных решений в подмножествах
98 ISSN 0572-2691
)1(sH и ).2(sH Обозначим эти оценки соответственно )]1([ sH и )]2([ sH .
Кроме того, )1(ˆ sH и )2(ˆ sH — соответственно подобласти в подмножествах
)1(sH и ),2(sH не содержащие допустимых планов. Пусть
,2,1
)},(
~
)(
~
)(
~
)(
~
{)(
~
),(ˆ/)()(
~ 222
2
2
1
l
lHlHlHlHlHlHlHlH nj
ssss
(55)
},)({)(
~ 212 s
jlj
s
jl
s
jj xlHxlH (56)
где ,11 s
jl
s
jlh ,22 s
jl
s
jlh ,,,1 nj .2,1l
Для полученных подмножеств ),(
~
lH s ,2,1l также могут быть вычислены
оценки верхней границы оптимальных решений — )],(
~
[ lH s причем )](
~
[ lH s
)],([ lH
s
.2,1l Заметим, что выполнение итераций по исключению обла-
стей, не содержащих допустимых решений, на каком-то шаге вычислений может
не производиться. В дальнейшем последующему ветвлению подвергается область
детерминированных переменных с наибольшим значением верхней границы.
Такой процесс продолжаем до тех пор, пока на некотором S-м шаге итерации не
будет получено подмножество ),(
~
lH s
включающее только одно значение вектора
детерминированных переменных, удовлетворяющее всем ограничениям «четкого
эквивалента» задачи fuzzy-линейного программирования и обеспечивающего зна-
чение показателей -сечений fuzzy-множества целевой функции задачи, не хуже
чем верхние оценки всех остальных fuzzy-множества для допустимых подмно-
жеств значений вектора детерминированных переменных.
Как на первом, так и на последующих шагах алгоритма, исходная область
},...,1,{
21 njhxhH
s
jj
s
j
s может быть разбита на большее количество под-
областей: на четыре, если область двух переменных 1j и 2j разбивается на две
подобласти, на 8 и т.д., либо область изменения одной переменной может быть
разбита на 3, 4, 5, ... подобластей.
Некоторые расширения метода ветвей и границ (branch-and-bound) заключа-
ются в следующем.
1. Возможность исключить из каждого подмножества области, не содержа-
щие допустимых решений, и использовать две оценки:
)].([)](
~
[ lHlH ss
Причем выполнение итеративного процесса по исключению областей, не содер-
жащих допустимых решений, и вычисление )](
~
[ lH s для некоторого l-го под-
множества целесообразно лишь в том случае, если )](
~
[ lH s больше верхней гра-
ницы для любого из остальных рассматриваемых подмножеств.
2. Пусть на каком-то шаге ветвления получена )](
~
[ lH s (или )])([ lH s —
наилучшая оценка среди всех L подлежащих рассмотрению непересекающихся
подмножеств, т.е.
)],([)](
~
[)](
~
[ sss HHlH ,,,1 L .l (57)
Находим методами случайного поиска одно или несколько допустимых реше-
ний ),(
~
)( lHlX s
v а также соответствующие этим детерминированным векторам
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 99
fuzzy-множества целевых функций )]},([),({)(
)( vXFvv XfXfXF
v
,,,1 Vv
которые удовлетворяют соотношениям вида
).(..)()()( ReReReRe 21
* Vvvv
XFXFXFXF (58)
Тогда для каждого из подмножеств ,,,1 L ,l к системе ограничений мо-
гут быть добавлены дополнительные ограничения:
),()]([ *Re v
s XFH ),()](
~
[ *Re v
s XFH (59)
которые заменяются соответствующим четким детерминированным эквивалентом.
Если для подмножества )(sH или )(
~
sH ограничения не выполняются, то
они исключаются из дальнейшего рассмотрения как неперспективные.
5.2. Итеративные процессы исключения областей изменения детермини-
рованных переменных, не содержащих допустимых решений. Для каждого из
ограничений (3) определим ),( jI ),( jI },,,1{)()( KjIjI ,,,1 nj —
подмножества ограничений, у которых при увеличении значений переменной j
значения параметров )(1 ijam и )(2 ijam соответственно возрастают и не возрас-
тают. Обозначим
;,,1,,,1
),()()]}([{]}/)([{ 1
,1,
1
1,
1
,1,
1
,
Kinj
mqamXAmxXAm ts
jij
ts
i
s
j
ts
i
s
(60)
.,,1,,,1
),()()]}([{]}/)([{ 2
,1,
2
1,
2
,1,
2
,
Kinj
mqamXAmxXAm ts
jij
ts
i
s
j
ts
i
s
(61)
Здесь
,,,1},{
},,,,,{
2
0,
21
0,
1
0,0,
0,0,0,
1
0,
njhhxhhxHHx
xxxX
s
j
s
jj
s
j
s
jj
s
j
s
j
s
j
s
n
s
j
ss
(62)
)()( 2
,1,
1
,1, mgmg ts
j
ts
j
.,,1
],&0)([или],&0)([если,
],&0)([или],&0)([если,
11
1,
1
11
1,
2
nj
cmcmh
cmcmh
jj
ts
j
jj
ts
j
(63)
При ограничениях (52)–(54) выполним итеративный процесс, на каждом шаге
которого ,,,1 Tt найдем
,
]}/)([{)(
,
]}/)([{)(
min
1
2
,
2
1
1
,
1,
ij
j
t
i
s
i
ij
j
t
i
s
its
ij
a
xXAmbm
a
xXAmbm
(64)
,max ,
)(
,
2
ts
ij
jIi
ts
j
,max ,
)(
,
1
ts
ij
jIi
ts
j
(65)
,,
1
1,
1
,
1
ts
j
ts
j
ts
j hy .,
2
1,
2
,
2
ts
j
ts
j
ts
j hy (66)
Положив
,,,,1),()(),()(
,,
2
,1,
2
,,
1
,1,
1
,,
1,
2
,
2
1,
1
,
1
jknkmgmgmgmg
hhhh
ts
k
ts
k
ts
k
ts
k
ts
k
ts
k
ts
k
ts
k
(67)
,,
1
,
1
ts
j
ts
j yh ,,
2
,
2
ts
j
ts
j yh (68)
100 ISSN 0572-2691
рассмотрим )1( j -ю переменную и перейдем к )1( t -му шагу итеративного про-
цесса. Если ,nj то на следующем )1( t -м шаге процесса выбираем перемен-
ную .1j
Описанный выше итеративный процесс продолжаем выполнять до тех пор,
пока на некотором 1t -м шаге процесса не получим одно из условий:
,
1,
1
,
1
11
ts
j
ts
j hh ,
1,
2
,
2
11
ts
j
ts
j hh ,,,1 nj (69)
либо для некоторого индекса 1j справедливо .1
1
1
1
,
2
,
1
ts
j
ts
j
hh
Утверждение 10. Если на некотором t-м шаге итеративного процесса полу-
чим условия ,,
2
,
1
ts
j
ts
j hh то ,)(
~
lH s подобласть детерминированных перемен-
ных )(lHX
ss не содержит допустимых решений и может быть отброшена из
рассмотрения как неперспективная.
В результате выполнения итеративного процесса (64)–(68) будут отброшены
области, не содержащие допустимых решений, и n-мерный параллелепипед sH пре-
образуется в параллелепипед меньшего размера ,
~ ss HH ,{
~
11 ,
2
,
1
ts
jj
ts
j
s hxhH
}.,,1 nj
Отметим, что остановка итеративного процесса вследствие выполнения усло-
вия (69) является только необходимым условием выполнения ограничений задачи.
Не все ограничения, удовлетворяющие этим условиям, являются совместными.
5.3. Обсуждение алгоритмов решения задачи. Следует отметить, что пред-
лагамый алгоритм решения задачи может успешно использоваться, если некото-
рые или все детерминированные переменные задачи HX могут принимать
только целочисленные значения.
Аналогичным образом могут быть построены детерминированные эквивален-
ты и разработаны алгоритмы решения для достаточно широкого класса задач нели-
нейного fuzzy-программирования, в которых в выражениях критериев оптимально-
сти и левых частей ограничений содержатся суммы умноженных на fuzzy-числа
произведений детерминированных переменных при условии, что каждая из таких
переменных может принимать только положительные значения. Отличие в методах
решения такого класса задач будет заключаться только в формулах построения ре-
зультирующих функций принадлежности левых частей ограничений и критерия оп-
тимальности, используя соответствующие правила fuzzy-арифметики.
Заключение
Сформулирована задача fuzzy-линейного программирования, в которой ко-
эффициенты левых частей ограничений и критерия оптимальности, а также пра-
вые части ограничений — суть fuzzy-множества, представленные LR fuzzy-ин-
тервалами.
Предложены правила ранжирования и оценки доминирования для fuzzy-мно-
жеств, представленных LR fuzzy-интервалами.
Показано, что решение задачи fuzzy-линейного программирования может
быть сведено к решению некоторой детерминированной нелинейной задачи, об-
ладающей некоторыми специфическими свойствами. Особенностью этой задачи
является то, что левая часть ограничений задачи и критерия оптимальности не яв-
ляются явными функциями переменных задачи. Для проверки выполнения огра-
ничений и вычисления критерия оптимальности этой детерминированной задачи
необходимо выполнить определенный объем вычислений.
Исследованы и установлены свойства слабой монотонности fuzzy-множеств
левых частей ограничений и критерия оптимальности задачи относительно векто-
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 101
ра детерминированных переменных. На основе установленных свойств предло-
жены итеративные процессы отсечения областей, не содержащих допустимых и
оптимальных решений.
Разработаны алгоритмы решения задачи на основе модифицированного ме-
тода «ветвей и границ», использующего установленные свойства задачи и итера-
тивные процессы отсева неперспективных продолжений.
Предложенные подходы могут применяться для решения некоторого класса
задач fuzzy-нелинейного программирования.
Ю.О. Зак
ДЕТЕРМІНОВАНИЙ ЕКВІВАЛЕНТ
І АЛГОРИТМИ РОЗВ’ЯЗАННЯ ЗАДАЧІ
FUZZY-ЛІНІЙНОГО ПРОГРАМУВАННЯ
Розв’язання задачі fuzzy-лінійного програмування зведено до розв’язання де-
якої детермінованої нелінійної екстремальної задачі. Запропоновано правила
ранжування та оцінки домінування для fuzzy-множин, заданих LR fuzzy-інтер-
валами. Встановлено властивості монотонності fuzzy-множин, лівих частин
обмежень і критерію оптимальності задачі щодо вектора детермінованих змін-
них. Розроблено алгоритми розв’язання задачі на основі модифікованого мето-
ду «гілок і границь».
Yu.A. Zасk
DETERMINATE EQUIVALENT
AND ALGORITHMS OF SOLVING
FUZZY-LINEAR PROGRAMMING PROBLEM
The solution of problem of fuzzy-linear programming is reduced to solution of a de-
terminate nonlinear extremal problem. The rules of ranking and domination estimate
for fuzzy sets represented by LR fuzzy intervals are proposed. The properties of
fuzzy sets monotonicity, left-hand parts of bounds and optimality criterion of the
problem relative to the vector of determined variables are defined. The algorithms of
problem solving on the basis of modified branch-and-bound method are developed.
1. Rommelfanger H. Fuzzy-Optimierungsmodelle in praktischen Anwendungen // Multi-Criteria und
Fuzzy-Systeme in Theorie und Praxis / W. Habenicht, B. Scheubrein, R. Scheubrein (Hrsg.),
Wiesbaden : Deutscher Universitäts-Verlag, 2003, — S. 95–113.
2. Rommelfanger H. Entscheiden bei Unschärfe // Fuzzy Decision Support-Systeme. — Berlin; Hei-
delberg : Springer-Verlag, 1994, Second Edition.
3. Rommelfanger H. FULPAL 2.0 — An interactive algorithm for solving multicriteria fuzzy linear
programs controlled by aspiration levels // Methods of Multickriteria Decision Theory / Ed. by
D. Schegert. — Pfalzakademie Lamprecht, 1995. — S. 21–34.
4. Rommelfanger H., Keresztfalfi T. Multicriteria fuzzy operation based on Yager’s parametrized
T-norm // Found. of Comput. and Decision Sci. — 1991 — 16. — P. 99–110.
5. Rommelfanger H., Slowinski R. Fuzzy linear programming with single or multiple objective func-
tions // Fuzzy Sets in Decision Analisys, Operations Research and Statistics / Ed. by R.
Slowinski. — Norwell, Massachusetts : Kluwer Academ. Publ., 1998. — P. 179–213.
6. Zimmermann H.-J. Unscharfe entscheidungen und multi-criteria analyse // Proc. Oper. Res. —
1979. — 6. — P. 99–109.
7. Yager R.R. On a general class of fuzzy connectives // Fuzzy Sets and Systems. — 1980. — 3. —
P. 235–242.
8. Miettinen K.M. Nonlinear multiobjective optimization. — Boston; London; Dordrecht : Kluwer
Academ. Publ., 2004. — 298 p.
9. Зак Ю.А. Вычислительные схемы последовательных алгоритмов оптимизации // Автомати-
ка и вычисл. техника. — 1980. — № 2. — С. 46–55.
Получено10.12.2009
После доработки 05.05.2010
|
| id | nasplib_isofts_kiev_ua-123456789-207281 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T16:08:16Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Зак, Ю.А. 2025-10-04T18:43:39Z 2011 Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования / Ю.А. Зак // Проблемы управления и информатики. — 2011. — № 1. — С. 87–101. — Бібліогр.: 9 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207281 519.8 10.1615/JAutomatInfScien.v43.i2.20 Розв’язання задачі fuzzy-лінійного програмування зведено до розв’язання деякої детермінованої нелінійної екстремальної задачі. Запропоновано правила ранжування та оцінки домінування для fuzzy-множин, заданих LR fuzzy-інтервалами. Встановлено властивості монотонності fuzzy-множин, лівих частин обмежень і критерію оптимальності задачі щодо вектора детермінованих змінних. Розроблено алгоритми розв’язання задачі на основі модифікованого методу «гілок і границь». The solution of problem of fuzzy-linear programming is reduced to solution of a determinate nonlinear extremal problem. The rules of ranking and domination estimate for fuzzy sets represented by LR fuzzy intervals are proposed. The properties of fuzzy sets monotonicity, left-hand parts of bounds and optimality criterion of the problem relative to the vector of determined variables are defined. The algorithms of problem solving on the basis of modified branch-and-bound method are developed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования Детермінований еквівалент і алгоритми розв’язання задачі fuzzy-лінійного програмування Determinate equivalent and algorithms of solving fuzzy-linear programming problem Article published earlier |
| spellingShingle | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования Зак, Ю.А. Методы обработки информации |
| title | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования |
| title_alt | Детермінований еквівалент і алгоритми розв’язання задачі fuzzy-лінійного програмування Determinate equivalent and algorithms of solving fuzzy-linear programming problem |
| title_full | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования |
| title_fullStr | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования |
| title_full_unstemmed | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования |
| title_short | Детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования |
| title_sort | детерминированный эквивалент и алгоритмы решения задачи fuzzy-линейного программирования |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207281 |
| work_keys_str_mv | AT zakûa determinirovannyiékvivalentialgoritmyrešeniâzadačifuzzylineinogoprogrammirovaniâ AT zakûa determínovaniiekvívalentíalgoritmirozvâzannâzadačífuzzylíníinogoprogramuvannâ AT zakûa determinateequivalentandalgorithmsofsolvingfuzzylinearprogrammingproblem |