Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи
Запропоновано аналітичний підхід до дослідження багатошвидкісної моделі Ерланга з рандомізованою стратегією доступу. Показано можливість використання отриманих результатів у бездротових мережах обробки потоків мовленнєвих повідомлень і даних для поліпшення якості обслуговування....
Gespeichert in:
| Datum: | 2011 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Schriftenreihe: | Проблемы управления и информатики |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/207282 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи / А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким // Проблемы управления и информатики. — 2011. — № 1. — С. 102–118. — Бібліогр.: 31 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-207282 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2072822025-10-05T00:17:52Z Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи Багатошвидкісна модель Ерланга з рандомізованою стратегією доступу та її застосування в мультисервісних мережах зв’язку Multirate Erlang’s model with randomized access strategy and its application in multiservice communication networks Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон Методы обработки информации Запропоновано аналітичний підхід до дослідження багатошвидкісної моделі Ерланга з рандомізованою стратегією доступу. Показано можливість використання отриманих результатів у бездротових мережах обробки потоків мовленнєвих повідомлень і даних для поліпшення якості обслуговування. An analytical method to investigation of multirate Erlang’s model with randomized access strategy is proposed. An application of this model in wireless integrated voice/data networks is demonstrated. 2011 Article Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи / А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким // Проблемы управления и информатики. — 2011. — № 1. — С. 102–118. — Бібліогр.: 31 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207282 621.394.74:519.872 10.1615/JAutomatInfScien.v43.i2.30 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методы обработки информации Методы обработки информации |
| spellingShingle |
Методы обработки информации Методы обработки информации Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи Проблемы управления и информатики |
| description |
Запропоновано аналітичний підхід до дослідження багатошвидкісної моделі Ерланга з рандомізованою стратегією доступу. Показано можливість використання отриманих результатів у бездротових мережах обробки потоків мовленнєвих повідомлень і даних для поліпшення якості обслуговування. |
| format |
Article |
| author |
Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон |
| author_facet |
Меликов, А.З. Пономаренко, Л.А. Ким, Чи Сон |
| author_sort |
Меликов, А.З. |
| title |
Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи |
| title_short |
Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи |
| title_full |
Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи |
| title_fullStr |
Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи |
| title_full_unstemmed |
Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи |
| title_sort |
многоскоростная модель эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2011 |
| topic_facet |
Методы обработки информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/207282 |
| citation_txt |
Многоскоростная модель Эрланга с рандомизированной стратегией доступа и ее применение в мультисервисных сетях связи / А.З. Меликов, Л.А. Пономаренко, Чи Сон Ким // Проблемы управления и информатики. — 2011. — № 1. — С. 102–118. — Бібліогр.: 31 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT melikovaz mnogoskorostnaâmodelʹérlangasrandomizirovannojstrategiejdostupaieeprimenenievmulʹtiservisnyhsetâhsvâzi AT ponomarenkola mnogoskorostnaâmodelʹérlangasrandomizirovannojstrategiejdostupaieeprimenenievmulʹtiservisnyhsetâhsvâzi AT kimčison mnogoskorostnaâmodelʹérlangasrandomizirovannojstrategiejdostupaieeprimenenievmulʹtiservisnyhsetâhsvâzi AT melikovaz bagatošvidkísnamodelʹerlangazrandomízovanoûstrategíêûdostuputaíízastosuvannâvmulʹtiservísnihmerežahzvâzku AT ponomarenkola bagatošvidkísnamodelʹerlangazrandomízovanoûstrategíêûdostuputaíízastosuvannâvmulʹtiservísnihmerežahzvâzku AT kimčison bagatošvidkísnamodelʹerlangazrandomízovanoûstrategíêûdostuputaíízastosuvannâvmulʹtiservísnihmerežahzvâzku AT melikovaz multirateerlangsmodelwithrandomizedaccessstrategyanditsapplicationinmultiservicecommunicationnetworks AT ponomarenkola multirateerlangsmodelwithrandomizedaccessstrategyanditsapplicationinmultiservicecommunicationnetworks AT kimčison multirateerlangsmodelwithrandomizedaccessstrategyanditsapplicationinmultiservicecommunicationnetworks |
| first_indexed |
2025-10-05T01:10:41Z |
| last_indexed |
2025-10-07T01:06:24Z |
| _version_ |
1845283189735555072 |
| 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
|