Багатокритеріальні задачі прийняття рішень в нечітких умовах
Multicriteria problems of decision-making under the uncertainty are considered. For such problems, pareto-optimal solutions and best compromise solutions of level α are introduced. The corresponding theorems determining their interconnections are formulated and proved. The method for solving the con...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2016
|
| Schlagworte: | |
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/88011 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1866301951928434688 |
|---|---|
| author | Zaychenko, Olena Yu. Zaychenko, Yuriy P. |
| author_facet | Zaychenko, Olena Yu. Zaychenko, Yuriy P. |
| author_sort | Zaychenko, Olena Yu. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-03-30T15:25:41Z |
| description | Multicriteria problems of decision-making under the uncertainty are considered. For such problems, pareto-optimal solutions and best compromise solutions of level α are introduced. The corresponding theorems determining their interconnections are formulated and proved. The method for solving the considered problem is suggested based on the search of optimal compromise solutions of level α. The example of solving a multicriteria linear programming problem with fuzzy parameters is presented demonstrating the suggested approach. Also, the comparison of solutions for non-fuzzy and fuzzy problems is performed. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2016.4.08 |
| first_indexed | 2025-07-17T10:22:06Z |
| format | Article |
| fulltext |
Е.Ю. Зайченко, Ю.П. Зайченко, 2016
Системні дослідження та інформаційні технології, 2016, № 4 79
УДК 519.8(075.8)
DOI: 10.20535/SRIT.2308-8893.2016.4.08
МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ
В НЕЧЕТКИХ УСЛОВИЯХ
Е.Ю. ЗАЙЧЕНКО, Ю.П. ЗАЙЧЕНКО
Аннотация. Рассмотрены многокритериальные задачи нечеткого математиче-
ского программирования. Введены понятия парето-оптимального решения и
наилучшего компромиссного решения уровня α МКНП- задачи. Сформулиро-
ваны и доказаны теоремы, устанавливающие взаимосвязи между ними. Пред-
ложен метод решения МКНП-задачи на основе поиска компромиссных реше-
ний уровня α. Приведен пример решения многокритериальной задачи
линейного программирования с нечеткими условиями, иллюстрирующими
предложенный подход и проведено его сравнение с компромиссным решением
этой задачи в четкой постановке.
Ключевые слова: многокритериальные задачи, нечеткое математическое про-
граммирование, парето-оптимальные решения уровня α, наилучшее компро-
миссное решение уровня .
ВВЕДЕНИЕ
Многокритериальные задачи оптимизации составляют широкий класс задач
принятия решений. Для их решения в четких условиях разработано значи-
тельное количество методов и алгоритмов, среди которых подходы, методы
и алгоритмы, изложенные в работах [1–4].Обзор современных методов мно-
гокритериальной оптимизации в четких условиях приведен в учебнике [5].
Однако задача принятия МК-решений существенно усложняется в ус-
ловиях неопределенности, когда ряд параметров и критериев являются не-
четкими. Для таких задач требуется разработка специальных подходов и
методов решения.
Цель работы — исследование многокритериальных задач нелинейного
программирования (МКНП) в нечетких условиях и разработка метода их
решения на основе введения компромиссных решений МКНП-задачи
уровня .
ПОСТАНОВКА МКНП-ЗАДАЧИ В НЕЧЕТКИХ УСЛОВИЯХ И ЕЕ
СВОЙСТВА
Рассмотрим задачу принятия решений с несколькими критериями в нечет-
ких условиях
},1),,({max miCXf ii
при
},1,0),(:{)( KkaXgXAGX kk ,
Е.Ю. Зайченко, Ю.П. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2016, № 4 80
где njxX j ,1],[ ; njcC iji ,1],[ ; RrKkaa krk ,1,,1],[ , ijc — не-
четкие числа (НЧ) с известной функцией принадлежности (ФП) )( ijc ,
][ krk aa — НЧ с ФП )( kra .
Такую задачу назовем многокритериальной задачей нечеткого матема-
тического программирования (МК НМП). Введем в рассмотрение подмно-
жества уровня i :
})(:{},)(:{
krkrkrijijij aaaccC , где )1,0( ,
а также нечеткие матрицы уровня :
},1,,1,)(||:{||},)(||:{|| RrKkaaAccC krkrijij .
По аналогии с четкими задачами введем понятие парето-оптимального
решения уровня [5].
Определение 1. Парето-оптимальным решением уровня α назовем та-
кое решение X* со значениями нечетких параметров AC , , для которого не
существует другого решения X
~
со значениями нечетких параметров ,
~
,
~
AC
такого, что
miCXfCXf ii ,1),,()
~
,
~
( ** (1)
при условиях CCCC
~
,* и хотя бы одно неравенство (1) будет строгим.
Парето-оптимальное решение уровня обладает следующим свой-
ством.
Пусть 21 , а *
1X и *
2X — парето-оптимальные решения уровней
1 и 2 соответственно. Тогда miCXfCXf ii ,1),,(), ( 2
*
21
*
1 .
Поскольку множество парето-оптимальных решений уровня α доста-
точно велико, в общем случае может быть несчетным множеством, то воз-
никает проблема выбора одного из них (в некотором смысле наилучшего).
С этой целью осуществим эквивалентное преобразование критериев и
приведем их к безразмерному виду (нормирование):
minmax
min),(
),(
ii
iii
i
Н
i
ff
fCXf
CXf ,
где iiiiii CCCXffCXff ),,(min),,(max minmax . При этом )(AGX .
Введем веса критериев
m
i
iii www
1
1,0:}{ . Будем искать такой век-
тор 0X , для которого
xi
Н
ii
i
CXfw max),(min . (2)
Условие (2) можно переписать в следующем эквивалентном виде
mikCXfw i
Н
ii ,1,),( max0 . (3)
Многокритериальные задачи принятия решений в нечетких условиях
Системні дослідження та інформаційні технології, 2016, № 4 81
Назовем решение, удовлетворяющее условие (3) при максимальном
значении max0k , наилучшим компромиссным решением (НКР) МК НМП
задачи уровня .
ТЕОРЕМЫ О ВЗАИМОСВЯЗИ ПАРЕТО-ОПТИМАЛЬНЫХ
И КОМПРОМИССНЫХ РЕШЕНИЙ УРОВНЯ
Справедливы следующие теоремы, устанавливающие связь между парето-
оптимальными решениями уровня и НКР.
Теорема 1. Если существует единственное решение *X системы не-
строгих равенств (3), то это решение будет парето-оптимальным решением
уровня МКНМП-задачи.
Таким образом, единственное компромиссное решение уровня будет
обязательно и парето-оптимальным решением.
Если же существует несколько решений системы (3) , то для нахожде-
ния парето-оптимального решения необходимо использовать дополнитель-
ный критерий
m
i
i
Н
ii CXfwCXF
1
1 ),(),(
и найти максимизирующее решение. Оно и будет парето-оптимальным.
Доказательство. Предположим, что единственное решение *X систе-
мы неравенств (3) не является парето-оптимальным уровня , и пусть ре-
шение X
~
является парето-оптимальным со значениями параметров целе-
вой функции C
~
. Тогда
miCXfCXf iiii ,1),,()
~
,
~
( ** .
Следовательно,
miCXfCXf i
Н
ii
Н
i ,1),,()
~
,
~
( **
mikCXfwCXfw i
Н
iii
Н
ii ,1,),()
~
,
~
( max0
** .
Таким образом, X
~
является также решением системы неравенств (3)
при максимальном 0k , что противоречит условиям теоремы 1. Остается
принять, что *x является парето-оптимальным решением уровня МКНП-
задачи.
Теорема 2 (обратная). Пусть *X является парето-оптимальным реше-
нием уровня . Тогда существуют такие веса }{ iw , что X будет наилуч-
шим компромиссным решением МК НМП-задачи уровня .
Доказательство (от противного). Допустим, что *X не является НКР.
И пусть веса }{ iw выбраны так, что выполняется условие
max0
** ),( kCXfw i
Н
ii для всех ji, .
Е.Ю. Зайченко, Ю.П. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2016, № 4 82
Пусть X
~
является НКР задачи МКНП. Тогда max0),( kCXfw i
Н
ii ,
mi ,1 .
Следовательно ),()
~
,
~
( ** i
Н
iii
Н
ii CXfwCXfw для всех mi ,1 и хотя
бы одно неравенство будет строгим. Но тогда ),()
~
,
~
( ** i
Н
iii
Н
i CXfCXf и
соответственно
miCXfCXf iiii ,1),,()
~
,
~
( ** , (4)
и хотя бы одно из неравенств (4) будет строгим.
Тогда решение *X не может быть парето-оптимальным уровня , что
противоречит условиям теоремы 2. Тогда остается принять, что *X являет-
ся НКР уровня МКНП-задачи.
Пример. Пусть задана многокритериальная задача линейного програм-
мирования с нечеткими параметрами:
2221212
2121111
)(max
,)(max
xcxcxF
xcxcxF
при условиях:
,0,0
,24
,10
,4
,7
,
21
252151
242
232131
222121
111212
xx
xaxa
xa
xaxa
xaxa
xaxa
где ijc — НЧ с ФП
2)(1
1
)(c
ijij
ij
cc
; 111 c , 412 c , 321 c , 222 c ;
ija — НЧ с ФП
2
41
1
)(
ij
ijij
ij
a
aa
a ;
6
1
11 a , 1222112 aaa ,
231 a , 142 a , 151 a , 252 a .
Необходимо найти парето-оптимальные решения и наилучшие ком-
промиссные решения уровня α, где 8,0 .
ЧЕТКАЯ МКЛП-ЗАДАЧА
Сначала решаем четкую задачу МКЛП
)23(max)(max
,)4(max)(max
212
211
xxxf
xxxf
при условиях
Многокритериальные задачи принятия решений в нечетких условиях
Системні дослідження та інформаційні технології, 2016, № 4 83
.0,0
,242
,10
,42
,7
,
6
1
21
21
2
21
21
12
xx
xx
x
xx
xx
xx
(5)
Строим область допустимых решений (ОДР), которая определяется ус-
ловиями (5). Ее вид изображен на рис. 1. Находим крайние точки ОДР и их
координаты (1;6)A , (3;10)B , (4;10)C , (18;3)D , (6;1)E .
Решаем задачу графоаналитически, находим 44)(1max1 Cff ; min1f
10)(1 Af ; 48)(2max2 Dff ; 11)(2min2 Bff .
Поскольку 1max f достигается в точке C , а 2max f — в точке D , паре-
то-оптимальные решения четкой МКЛП-задачи находятся на отрезке CD .
Найдем НКР, для этого переходим к безразмерным критериям
34
1041
1044
1041)(
)( 2121
min1max1
min1
1
xxxx
ff
fxf
xf iН ;
59
1123
)( 21
2
xx
xf Н .
Пусть веса таковы:
2
1
21 ww .
Найдем четкое НКР, для чего решаем задачу 0max k при условиях
*
1x ≈ :9,74
С
F
B
E
D
A
Рис. 1. Область допустимых решений и НКР четкой МКЛП задачи
Е.Ю. Зайченко, Ю.П. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2016, № 4 84
011 )( kxfw ;
022 )( kxfw .
Поскольку всего 2 критерия, можно найти НКР из системы уравнений:
..к.т,242
;)()(
21
1111
CDxxx
xfwxfw НН
Решаем систему:
.242
,
59
1123
34
1041
21
2121
xx
xxxx
Решение этой системы: 13,7;74,9 *
2
*
1 xx .
Соответствующая точка F показана на рис. 1.
НЕЧЕТКАЯ МКЛП-ЗАДАЧА
Необходимо найти парето-оптимальные решения и НКР уровня 8,0
МКЛП-задачи. Для этого необходимо сначала найти интервалы принадлеж-
ности уровня α:
ijC и
ija .
Решаем неравенство:
8,0
)(1
1
)(
2
ijij
ij
cc
c .
Отсюда
5,0||25,0)( 2 ijijijij cccc и 5,05,0 ijijij ccc .
Находим соответствующие интервалы для ijc
5,15,0 11 c ; 5,45,3 12 c ;
5,35,2 21 c ; 5,15,2 22 c .
Записываем критерии оптимиста )(xfiU и пессимиста )(xfiL
211 5,45,1)( xxxf U ,
212 5,15,3)( xxxf U ,
211 5,35,0)( xxxf L ,
212 5,25,2)( xxxf L .
Построим ОДР для нечетких ограничений уровня 8,0 . Решаем не-
равенства
25,04
1
1
)(
2
2
ij
ijij
ij
ijij
ij a
aa
a
aa
a
Многокритериальные задачи принятия решений в нечетких условиях
Системні дослідження та інформаційні технології, 2016, № 4 85
или 5,02
ij
ijij
a
aa
, откуда ijijij aaa 25,175,0 .
Находим интервалы для нечетких параметров ija
21,0125,0 11 a ; 25,175,0 12 a ; 25,175,0 21 a ;
25,175,0 22 a ; 5,25,1 31 a ; ; 25,175,0 32 a
25,175,0 42 a ; 25,175,0 51 a ; 51,25,1 52 a .
Построим ОДР уровня α оптимиста (т.е. расширеную). Для этого для
ограничений вида
jjj bxaxa 2211 , где ijUijijL aaa .
Выбираем границы интервалов так:
а) если 01 ja , то min1 ijijLj aaa ,
б) если 01 ja , то max1 ijijUj aaa .
Для ограничений вида
jjj bxaxa 2211 ,
наоборот:
а) если 01 ja , то ijUj aa1 ;
б) если 01 ja , то ijLj aa1 .
В соответствии с этими правилами записываем ограничения, опреде-
ляющие максимальную ОДР уровня .
.0,0
,245,175,0
,1075,0
,475,05,1
,725,125,1
,125,025,1
21
21
2
21
21
12
xx
xx
x
xx
xx
xx
(6)
Находим ОДР уровня 8,0 согласно уравнениям (6). Ее вид изобра-
жен на рис. 2
Находим кратчайшие точки ОДР и их координаты:
5,5
07,0
2
1
x
x
A ;
3
40
4
2
1
x
x
B ;
3
40
3
16
2
1
x
x
A ;
66,2
6,26
2
1
x
x
D ;
51,0
1,5
2
1
x
x
E .
Е.Ю. Зайченко, Ю.П. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2016, № 4 86
Строим вектора нормалей: к целевой функции )(1 xf — вектор 1N и
к )(2 xf — 2N соответственно.
Для нахождения НКР уровня 8,0 находим точки и значения max1f и
min1f графоаналитически:
66)()5,45,1(max),( 121max1 CfxxCXf ;
95,9(E)),( 1min1 fCXf ;
9,89(D))5,15,3(max),( 221max2 fxxCXf ;
94,7(A)),( 2min2 fCXf .
Парето-оптимальное решение уровня 8,0 , как и в частном случае,
находится на отрезке CD, который описывается уравнением 245,175,0 21 xx .
Найдем НКР уровня 8,0 .
Для этого переходим к нормированым критериям
5,56
95,95,45,1
95,966
95,95,45,1
)( 2121
1
xxxx
Xf Н ;
84,97
94,75,15,3
94,79,89
94,75,15,3
)( 2121
2
xxxx
Xf Н .
Далее необходимо найти НКР из условий решения задачи 0max k (5)
при условиях 011 ),( kCXfw Н ; 022 ),( kCXfw Н .
Как и в четком случае, НКР уровня 8,0 лежит на отрезке CD и,
кроме того,
),(),( 2211 CXfwCXfw НН .
Рис. 2. Область допустимых решений и НКР уровня α в нечеткой МКЛП задачи
С
Исходная ОДР
B
D
F
B0
M
A
C0
A0
D0
E0
Расширенная
ОДР
Многокритериальные задачи принятия решений в нечетких условиях
Системні дослідження та інформаційні технології, 2016, № 4 87
Получаем систему
.245,175,0
,
84,97
94,75,15,3
5,56
95,95,45,1
21
2121
xx
xxxx
(7)
oткуда
2
22
1 232
3
696
3
4)5,124(
x
xx
x
.
Решая систему (7) после подстановки 21 232 xx , находим
44,92 x ; 12,13232 21 xx .
Таким образом, НКР уровня 8,0 данной задачи:
44,92 x ; 12,131 x .
Соответствующая точка M показана на рис. 2. Для сравнения на этом
же рисунке приведено ОДР и НКР для четкой задачи ),( F (пятиугольник
00000 FDCBA ).
ВЫВОДЫ
Рассмотрена многокритериальная задача принятия решений в нечетких ус-
ловиях (МКНП). Для ее решения введены понятия парето-оптимального
решения и наилучшего компромиссного решения уровня МКНП-задачи.
Доказаны теоремы, устанавливающие их взаимосвязи.
Предложен метод нахождения НКР уровня МКНП-задачи.
Приведен пример, иллюстрирующий предлагаемый метод для случая
МКЛП-задачи в нечетких условиях.
ЛИТЕРАТУРА
1. Гермейер Ю.Б. Введение в теорию исследования операций. — М.: Наука. —
1971. — 383 с.
2. Волкович В.Л. Проблемы создания интеллектуальных систем поддержки при-
нятия решений. — К., 1990. — 190 c.
3. Подиновский В.В. Оптимизация по последовательно применяемым критериям.
— М.: — 1975. — 360 c.
4. Ларичев О.И. Теория и методы принятия решений / О.И. Ларичев. — М.,
2002. — 302 c.
5. Зайченко Ю.П. Теорія прийняття рішень, підруч. / Ю.П. Зайченко. — К.: НТУУ
«КПІ», 2014. — 412 с.
6. Згуровский М.З. Модели и методы принятия решений в нечетких условиях /
М.З. Згуровский. — К.: Наук. думка, 2011. — 352 с.
Поступила 06.10. 2016
|
| id | journaliasakpiua-article-88011 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:22:06Z |
| publishDate | 2016 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/d1/fe8ae47eb29ce72c49024078406d34d1.pdf |
| spelling | journaliasakpiua-article-880112018-03-30T15:25:41Z Multicriteria decision-making problems under fuzzy conditions Многокритериальные задачи принятия ррешений в нечетких условиях Багатокритеріальні задачі прийняття рішень в нечітких умовах Zaychenko, Olena Yu. Zaychenko, Yuriy P. multicriteria decision-making problems uncertainty Pareto-optimal solutions of level α best compromise solutions of level α многокритериальные задачи нечеткое математическое программирование Парето-оптимальные решения уровня α наилучшее компромиссное решение уровня α багатокритеріальні задачі нечітке математичне програмування Парето-оптимальні розв’язки рівня α найкращий компромісний розв’язок рівня α Multicriteria problems of decision-making under the uncertainty are considered. For such problems, pareto-optimal solutions and best compromise solutions of level α are introduced. The corresponding theorems determining their interconnections are formulated and proved. The method for solving the considered problem is suggested based on the search of optimal compromise solutions of level α. The example of solving a multicriteria linear programming problem with fuzzy parameters is presented demonstrating the suggested approach. Also, the comparison of solutions for non-fuzzy and fuzzy problems is performed. Рассмотрены многокритериальные задачи нечеткого математического программирования. Введены понятия парето-оптимального решения и наилучшего компромиссного решения уровня α МКНП- задачи. Сформулированы и доказаны теоремы, устанавливающие взаимосвязи между ними. Предложен метод решения МКНП-задачи на основе поиска компромиссных решений уровня α. Приведен пример решения многокритериальной задачи линейного программирования с нечеткими условиями, иллюстрирующими предложенный подход и проведено его сравнение с компромиссным решением этой задачи в четкой постановке. Розглянуто багатокритеріальні задачі прийняття рішень в нечітких умовах (БКНП). Уведено поняття парето-оптимального розв’язку та найкращого компромісного розв’язку рівня α БКНП- задачі. Сформульовано та доведено теореми, які встановлюють взаємозв’язки між ними. Запропоновано метод розв’язання БКНП-задачі на основі пошуку компромісних розв’язків рівня α. Наведено приклад ров’язання багатокритеріальної задачі лінійного програмування з нечіткими параметрами, який ілюструє запропонований підхід, та проведено його порівняння з компромісним розв’язком цієї задачі в чіткій постановці. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-11-15 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/88011 10.20535/SRIT.2308-8893.2016.4.08 System research and information technologies; No. 4 (2016); 79-87 Системные исследования и информационные технологии; № 4 (2016); 79-87 Системні дослідження та інформаційні технології; № 4 (2016); 79-87 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/88011/83759 Copyright (c) 2021 System research and information technologies |
| spellingShingle | багатокритеріальні задачі нечітке математичне програмування Парето-оптимальні розв’язки рівня α найкращий компромісний розв’язок рівня α Zaychenko, Olena Yu. Zaychenko, Yuriy P. Багатокритеріальні задачі прийняття рішень в нечітких умовах |
| title | Багатокритеріальні задачі прийняття рішень в нечітких умовах |
| title_alt | Multicriteria decision-making problems under fuzzy conditions Многокритериальные задачи принятия ррешений в нечетких условиях |
| title_full | Багатокритеріальні задачі прийняття рішень в нечітких умовах |
| title_fullStr | Багатокритеріальні задачі прийняття рішень в нечітких умовах |
| title_full_unstemmed | Багатокритеріальні задачі прийняття рішень в нечітких умовах |
| title_short | Багатокритеріальні задачі прийняття рішень в нечітких умовах |
| title_sort | багатокритеріальні задачі прийняття рішень в нечітких умовах |
| topic | багатокритеріальні задачі нечітке математичне програмування Парето-оптимальні розв’язки рівня α найкращий компромісний розв’язок рівня α |
| topic_facet | multicriteria decision-making problems uncertainty Pareto-optimal solutions of level α best compromise solutions of level α многокритериальные задачи нечеткое математическое программирование Парето-оптимальные решения уровня α наилучшее компромиссное решение уровня α багатокритеріальні задачі нечітке математичне програмування Парето-оптимальні розв’язки рівня α найкращий компромісний розв’язок рівня α |
| url | https://journal.iasa.kpi.ua/article/view/88011 |
| work_keys_str_mv | AT zaychenkoolenayu multicriteriadecisionmakingproblemsunderfuzzyconditions AT zaychenkoyuriyp multicriteriadecisionmakingproblemsunderfuzzyconditions AT zaychenkoolenayu mnogokriterialʹnyezadačiprinâtiârrešenijvnečetkihusloviâh AT zaychenkoyuriyp mnogokriterialʹnyezadačiprinâtiârrešenijvnečetkihusloviâh AT zaychenkoolenayu bagatokriteríalʹnízadačíprijnâttâríšenʹvnečítkihumovah AT zaychenkoyuriyp bagatokriteríalʹnízadačíprijnâttâríšenʹvnečítkihumovah |