Некоторые применения кластеризации критериального пространства для задач выбора
Рассматриваются некоторые вопросы применения кластеризации критериального пространства многокритериальных задач линейного программирования. Розглянуто деякі питання застосування кластеризації критеріального простору багатокритеріальних задач лінійного програмування і представлено модифікований алгор...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2009 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84557 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Некоторые применения кластеризации критериального пространства для задач выбора / Н.Э. Кондрук, Н.Н. Маляр // Компьютерная математика. — 2009. — № 2. — С. 142-149. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859733698151186432 |
|---|---|
| author | Кондрук, Н.Э. Маляр, Н.Н. |
| author_facet | Кондрук, Н.Э. Маляр, Н.Н. |
| citation_txt | Некоторые применения кластеризации критериального пространства для задач выбора / Н.Э. Кондрук, Н.Н. Маляр // Компьютерная математика. — 2009. — № 2. — С. 142-149. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассматриваются некоторые вопросы применения кластеризации критериального пространства многокритериальных задач линейного программирования.
Розглянуто деякі питання застосування кластеризації критеріального простору багатокритеріальних задач лінійного програмування і представлено модифікований алгоритм адитивної згортки критеріїв ефективності для розв’язування задач такого типу.
Questions of application of clustirization of criterion space of linear programming multicriterional problems are considered. On the basis of it, the modified algorithm of additive package of criterion of efficiency for problem solving of such kind is represented.
|
| first_indexed | 2025-12-01T14:12:25Z |
| format | Article |
| fulltext |
Рассматриваются некоторые во-
просы применения кластериза-
ции критериального простран-
ства многокритериальных задач
линейного программирования.
© Н.Э. Кондрук, Н.Н. Маляр,
2009
ÓÄÊ 519.8
Í.Ý. ÊÎÍÄÐÓÊ, Í.Í. ÌÀËßÐ
ÍÅÊÎÒÎÐÛÅ ÏÐÈÌÅÍÅÍÈß
ÊËÀÑÒÅÐÈÇÀÖÈÈ ÊÐÈÒÅÐÈÀËÜÍÎÃÎ
ÏÐÎÑÒÐÀÍÑÒÂÀ ÄËß ÇÀÄÀ× ÂÛÁÎÐÀ
Введение. Процессы принятия решений ле-
жат в основе любой целенаправленной дея-
тельности. В экономике они предшествуют
созданию промышленных и хозяйственных
организаций, обеспечивают их оптимальное
функционирование и взаимодействие. В на-
учных исследованиях позволяют выделить
важнейшие научные проблемы, найти спосо-
бы их изучения, определяют развитие мате-
риальной базы и теоретического аппарата.
При создании новой техники составляют
важный этап в проектировании машин,
устройств, приборов, комплексов. Оптималь-
ные решения позволяют достигать постав-
ленных целей при минимальных затратах
трудовых и материальных ресурсов.
В наше время многокритериальные задачи
выбора занимают центральное место в тео-
рии принятия решений. Учет многих крите-
риев приближает постановку задачи к реаль-
ной. Однако при решении таких задач возни-
кают проблемы, связанные со сложностью
математических моделей, большим объемом
информации и т.д. Причинами этого могут
быть как большая размерность пространства
альтернатив, так и большая размерность кри-
териального пространства.
Исследования психологов показывают, что
при принятии решений человек (ЛПР, экс-
перт) одновременно может оперировать
(сравнивать) 7 ± 2 объектами (критериями,
альтернативами) [1]. Поэтому задачи, в кото-
рых размерность пространства критериев или
альтернатив превышает 7, целесообразно
считать задачами большой размерности.
142 Компьютерная математика. 2009, № 2
НЕКОТОРЫЕ ПРИМЕНЕНИЯ КЛАСТЕРИЗАЦИИ КРИТЕРИАЛЬНОГО ПРОСТРАНСТВА ...
Примерами задач большой „критериальной” размерности могут быть: задача
оптимизации планирования работы производственной системы, задача автома-
тизации управления современной библиотеки (учитывает 20 критериев), задача
оптимизации организации маневренной работы на железнодорожной станции
(рассматриваются 9 критериев), задача ранжирования художников (учитывает
17 критериев), задача выбора энергетической политики (различных способов про-
изводства электроэнергии) для некоторого региона (включает 11 критериев) и т.д.
Одним из подходов, который можно использовать для решения проблемы
данного типа, является использование специально разработанных подходов для
уменьшения мощности критериального пространства. Например, применение
схем последовательного анализа, отсева и конструирования вариантов крите-
риев для данного класса задач [2] и разбитие множества критериев на под-
множества [3] – [6].
В основе многих человеко-машинных процедур лежит подход, который ис-
пользует разные свертки критериев эффективности [7]. При этом часто нужна
информация от ЛПР об их взвешивающих коэффициентах. Хотя во многих тру-
дах принимается как нормальное явление, что ЛПР может количественно опре-
делить важность критериев, эта задача не простая. Как правило, люди дают за-
вышенные оценки тем критериям, которые сравнительно мало влияют на выбор,
и недооценивают наиболее существенные [7]. Поэтому для анализа взаимосвя-
зей между критериями предлагается провести кластеризацию критериального
пространства, которая позволит выявить и построить подмножества „противо-
речивых” критериев и кластеры „сильно связанных” критериев, что в свою оче-
редь дает дополнительную информацию ЛПР для более обосновательного под-
бора взвешивающих коэффициентов.
Примерами противоречивости критериев в задаче планирования производ-
ства являются максимизация критерия качества продукции и минимизация себе-
стоимости производства продукции и т.п. Примерами „сильно связанных” кри-
териев в этой задаче могут служить критерии минимизации себестоимости про-
дукции и минимизации энергозатрат производства.
Кроме того, целесообразно предложенные подходы относительно решения
вышеприведенных проблем объединить в один обобщающий, комплексный ал-
горитм решения многокритериальных задач выбора.
1. Разные виды кластеризации критериального пространства много-
критериальных задач линейного программирования. Рассмотрим многокри-
териальную задачу линейного программирования в следующей постановке:
∑
=
=→==
n
j
jijii mixcxfy
1
,1max,)( , (1)
, (2) nRXx ⊆∈
где – множество допустимых решений (альтернатив), которое определяется
совокупностью линейных уравнений и неравенств;
X
)(xfy ii = – линейные
Компьютерная математика. 2009, № 2 143
Н.Э. КОНДРУК, Н.Н. МАЛЯР
целевые функции; – коэффициенты. То есть, есть некая совокупность целей,
что отображены критериями ,
ijc
)(xfi mi ,1= , и нужно найти такую точку
, которая в некотором смысле максимизирует все эти критерии. nRXx ⊆∈
Как известно, векторы ( ) , 1,i ic grad f x i m= = указывают на направление
роста функции . Совместим начала этих векторов с началом координат про-
странства и отметим
( )xfi
nR ( )1 2, , ,i i i i ic OC c c c= = … n (рис. 1).
O
y
xC5
C3
C2
C1
C4
РИС. 1. Пример размещения векторов iOC в пространстве 2R
Два критерия будем считать „сильно связанными”, если их оценки являются
близкими на разных альтернативах. Под близкими оценками двух критериев
и будем понимать как близкие значения длин векторов
if
jf ic і jc , так и малый
угол между ними. Если же высокая оценка по одному из критериев сопровожда-
ется низкой оценкой по другому, то такие критерии будем считать „слабо свя-
занными”.
Два критерия назовем „противоречивыми”, если улучшение оценок по од-
ному из них приводит к ухудшению оценок второго.
Алгоритмы разбиения множества критериев на кластеры рассматриваются в
работах [2 – 5]. На основе описанных алгоритмов можно провести кластериза-
цию критериального пространства разными способами. Все алгоритмы, пред-
ставленные в этих работах, можно условно разделить на три группы.
К первой группе можно отнести алгоритмы группирования критериев по-
средством построения гиперплоскости и ортонормированного базиса [3]. Они
разбивают критерии эффективности на множества противоречивых критериев
(рис. 2).
Компьютерная математика. 2009, № 2 144
НЕКОТОРЫЕ ПРИМЕНЕНИЯ КЛАСТЕРИЗАЦИИ КРИТЕРИАЛЬНОГО ПРОСТРАНСТВА ...
x
O
y
C5
C3
C2
C1
C4
РИС. 2. Пример возможной кластеризации критериального пространства алгоритмами
первой группы (пунктирной линией изображена условная линия деления
противоречивых групп критериев)
В частности, алгоритм размытой кластеризации критериев эффективности и
второй алгоритм нахождения сильно связанных кластеров критериев с помощью
нечеткого бинарного отношения можно отнести ко второй группе [5, 6]. В дан-
ном случае проводится группировка критериев на множества их скопления.
Причем, при разбивке учитываются лишь расстояния между точками .
Поэтому такие разбития не исключают попадания в один кластер противоречи-
вых критериев (рис. 3).
iC
O
y
xC5
C3
C2
C1
C4
РИС. 3. Пример кластеризации критериального пространства алгоритмами второй группы
К третьей группе критериев можно отнести первый алгоритм нахождения
сильно связанных кластеров критериев с помощью нечеткого бинарного отно-
шения и алгоритм понижения мощности множества критериев эффективности
[4, 5]. Группировка при этом проводится не только на основании расстояний от
точек , но и с учетом углов между ними. Образованные кластеры не будут
содержать противоречивые критерии (рис. 4).
iC
Компьютерная математика. 2009, № 2 145
Н.Э. КОНДРУК, Н.Н. МАЛЯР
O
C1
y
xC5
C3
C2
C4
РИС. 4. Пример возможной кластеризации критериального пространства
алгоритмами третьей группы
Одним из самых распространенных методов решения многокритериальных
задач линейного программирования является метод аддитивной свертки. С по-
мощью этого метода многокритериальная задача (1), (2) сводится к однокрите-
риальной задаче вида
( ) ( )
1
m
i i
i
F x f
=
= λ∑ x , (3)
nRXx ⊆∈ , (4)
где – взвешивающие коэффициенты критериев эффективности , причем
, ,
iλ ( )xfi
1
1
m
i
i=
λ =∑ 0iλ ≥ mi ,1= [1].
На основании вышеприведенных алгоритмов, как уже отмечалось ранее,
можно проанализировать взаимосвязи критериев, и, кроме того, предлагается
модифицировать метод аддитивной свертки критериев.
2. Свертки кластеров критериев. Пусть любым из алгоритмов второй и
третьей групп проведена кластеризация критериального пространства и образо-
ваны кластеры . В каждом из кластеров , zKKK ,,, 21 … iK zi ,1= предлагается
использовать один из следующих методов свертки кластеров критериев.
1. Среднюю длину векторов, которые принадлежат данному кластеру, обо-
значим j i
j
c K
i
c
K
∈η =
∑
, где iK – мощность множества , а iK jc – длина век-
тора jc . Обозначим
j i
j
c K
c
∈
β = . Свертку кластера обозначим ∑
*
ic .
η⋅β
=
β
Компьютерная математика. 2009, № 2 146
НЕКОТОРЫЕ ПРИМЕНЕНИЯ КЛАСТЕРИЗАЦИИ КРИТЕРИАЛЬНОГО ПРОСТРАНСТВА ...
2. Обозначим { }iji Kcj ∈=Γ і ( )1 2, , , nβ = β β β… ,
где
i
jk
j j
k
i
c
c
K
∈Γ
β =
∑
, nk ,1= . Как и в предыдущем пункте вектор
*
ic η⋅β
=
β
будет обозначать свертку кластера.
3. Пусть каждому из векторов jc кластера ЛПР (лицо, принимающее
решение) может поставить в соответствие весовой коэффициент или,
например, веса можно определить по формуле
iK
jλ
i
j
j
k
k
c
c
∈Γ
λ =
∑
, ij Γ∈∀ , причем
. Координаты вектора 1
i
j
j∈Γ
λ =∑ β определим как i
i
j jk
j
k
l
l
c
∈Γ
∈Γ
λ
β =
λ
∑
∑
.
И, наконец,
*
.ic = β
Каждому вектору **
2
*
1 ,,, zccc … поставим в соответствие критерий ( )xfi
~ ,
zi ,1= – представитель кластера, где ( ) niniii xcxcxcxf ⋅++⋅+⋅= *
2
*
21
*
1
~ … . В даль-
нейшем, рассматривая вместо критериев эффективности новые кри-
терии , можно уменьшить мощность критериального пространства
к числу
nfff ,,, 21 …
zfff
~
,,
~
,
~
21 …
z .
3. Определение весов кластеров критериев. Дальше для каждого из кла-
стеров определим весовой коэффициент zKKK ,,, 21 … 1 2, , , zβ β β… , тем самым
определив их и для . zfff
~
,,
~
,
~
21 …
1. Пусть ЛПР может указать коэффициенты важности 1 2, , , mα α α… соот-
ветственно каждому из критериев ( )xfi , mi ,1= . Весовой коэффициент
кластера можно задать как сумму тех
jβ
jK iα , что отвечают критериям, которые
содержат данный кластер:
{ }
1
s j
i
i s f K
j m
k
k
∈ ∈
=
α
β =
α
∑
∑
, zj ,1= .
Компьютерная математика. 2009, № 2 147
Н.Э. КОНДРУК, Н.Н. МАЛЯР
2. Если нет возможности получить информацию от ЛПР или ЛПР не в со-
стоянии ее предоставить, то весы кластеров определим, как
j
j
K
m
β = , где jK – мощность кластера . jK
3. Если же ЛПР не может определить веса критериев эффективности, но
может попарно сравнить критерии по важности, тогда образуем матрицу B ,
которая имеет строк и столбцов, использовав, например, калибровку z z
1, если важнее ,
0, в противном случае.
i j
ij
K K
b
⎧
= ⎨
⎩
.
Для определения коэффициентов важности 1 2, , , zβ β β… просуммируем
матрицу B по строках и пронормируем найденные величины:
1
j
j z
s
s
c
c
=
β =
∑
, где
1
z
i ij
j
c b
=
= ∑ , 1,=i z .
На основании вышеизложенного задача (1), (2) может быть приведена к од-
нокритериальной с помощью суперкритерия вида
( ) ( , ( ))i iF x S f x= β , (5)
где – некоторая функция свертки, S if
~ – представитель кластера , – весо-
вой коэффициент .
iK iβ
iK
Н.Е. Кондрук, М.М. Маляр
ДЕЯКІ ЗАСТОСУВАННЯ КЛАСТЕРИЗАЦІЇ КРИТЕРІАЛЬНОГО ПРОСТОРУ
ДЛЯ ЗАДАЧ ВИБОРУ
Розглянуто деякі питання застосування кластеризації критеріального простору багатокрите-
ріальних задач лінійного програмування і представлено модифікований алгоритм адитивної
згортки критеріїв ефективності для розв’язування задач такого типу.
N.E. Kondruk, M.M. Malyar
APPLICATIONS OF CLUSTIRIZATION OF CRITERION SPACE FOR
THE CHOICE PROBLEMS
Questions of application of clustirization of criterion space of linear programming multicriterional
problems are considered. On the basis of it, the modified algorithm of additive package of criterion
of efficiency for problem solving of such kind is represented.
Компьютерная математика. 2009, № 2 148
НЕКОТОРЫЕ ПРИМЕНЕНИЯ КЛАСТЕРИЗАЦИИ КРИТЕРИАЛЬНОГО ПРОСТРАНСТВА ...
1. Миллер Г. Магическое число семь плюс или минус два // Инж. психология. – М.: Про-
гресс, 1964.
2. Модели и методы оптимизации надежности сложных систем. / В.Л. Волкович, А.Ф. Во-
лошин, В.А. Заславский, И.А. Ушаков: Под. ред. В.С. Михалевича – Киев: Наук. думка,
1993. – 312 с.
3. Маляр М.М., Цицика Н.Е. Групування критеріїв ефективності // Вісн. СевДТУ. – Севасто-
поль: Вид-во СевДТУ, 2003. – Вип. 47: – С. 75–79.
4. Маляр М.М., Цицика Н.Е. Алгоритм зменшення кількості критеріїв в багатокритеріальній
задачі лінійного програмування // Вісн. Київ. ун-ту. Сер. фіз.-мат. наук. – 2004. – Вип. 2.
– С. 288–292.
5. Кондрук (Цицика) Н.Е., Маляр М.М. Кластеризація критеріїв ефективності у задачах ви-
бору // Там само. – 2005. – Вип. 3. – С. 305–308.
6. Кондрук Н.Е., Маляр М.М. Алгоритм кластеризації критеріального простору для задач
вибору // Там само. – 2006. – Вип. 3. – С. 225–229.
7. Ларичев О.И. Объективные модели и субъективные решения. – М.: Наука, 1987. – 143 с.
Получено 01.11.2007
Îá àâòîðàõ:
Кондрук Наталия Эмериховна,
преподаватель кафедры кибернетики и прикладной математики
математического факультета Ужгородского национального университета,
Маляр Николай Николаевич,
кандидат технических наук, доцент,
заведующий кафедрой кибернетики и прикладной математики,
декан математического факультета Ужгородского национального университета.
e-mail: : cyber@mail.uzhgorod.ua
Компьютерная математика. 2009, № 2 149
Примерами задач большой „критериальной” размерности могут быть: задача оптимизации планирования работы производственной системы, задача автоматизации управления современной библиотеки (учитывает 20 критериев), задача оптимизации организации маневренной работы на железнодорожной станции (рассматриваются 9 критериев), задача ранжирования художников (учитывает 17 критериев), задача выбора энергетической политики (различных способов производства электроэнергии) для некоторого региона (включает 11 критериев) и т.д.
Примерами противоречивости критериев в задаче планирования производства являются максимизация критерия качества продукции и минимизация себестоимости производства продукции и т.п. Примерами „сильно связанных” критериев в этой задаче могут служить критерии минимизации себестоимости продукции и минимизации энергозатрат производства.
, (1)
|
| id | nasplib_isofts_kiev_ua-123456789-84557 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-01T14:12:25Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кондрук, Н.Э. Маляр, Н.Н. 2015-07-10T11:35:59Z 2015-07-10T11:35:59Z 2009 Некоторые применения кластеризации критериального пространства для задач выбора / Н.Э. Кондрук, Н.Н. Маляр // Компьютерная математика. — 2009. — № 2. — С. 142-149. — Бібліогр.: 7 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84557 519.8 Рассматриваются некоторые вопросы применения кластеризации критериального пространства многокритериальных задач линейного программирования. Розглянуто деякі питання застосування кластеризації критеріального простору багатокритеріальних задач лінійного програмування і представлено модифікований алгоритм адитивної згортки критеріїв ефективності для розв’язування задач такого типу. Questions of application of clustirization of criterion space of linear programming multicriterional problems are considered. On the basis of it, the modified algorithm of additive package of criterion of efficiency for problem solving of such kind is represented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Некоторые применения кластеризации критериального пространства для задач выбора Деякі застосування кластеризації критеріального простору для задач вибору Applications of clustirization of criterion space for the choice problems Article published earlier |
| spellingShingle | Некоторые применения кластеризации критериального пространства для задач выбора Кондрук, Н.Э. Маляр, Н.Н. Теория и методы оптимизации |
| title | Некоторые применения кластеризации критериального пространства для задач выбора |
| title_alt | Деякі застосування кластеризації критеріального простору для задач вибору Applications of clustirization of criterion space for the choice problems |
| title_full | Некоторые применения кластеризации критериального пространства для задач выбора |
| title_fullStr | Некоторые применения кластеризации критериального пространства для задач выбора |
| title_full_unstemmed | Некоторые применения кластеризации критериального пространства для задач выбора |
| title_short | Некоторые применения кластеризации критериального пространства для задач выбора |
| title_sort | некоторые применения кластеризации критериального пространства для задач выбора |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84557 |
| work_keys_str_mv | AT kondrukné nekotoryeprimeneniâklasterizaciikriterialʹnogoprostranstvadlâzadačvybora AT malârnn nekotoryeprimeneniâklasterizaciikriterialʹnogoprostranstvadlâzadačvybora AT kondrukné deâkízastosuvannâklasterizacííkriteríalʹnogoprostorudlâzadačviboru AT malârnn deâkízastosuvannâklasterizacííkriteríalʹnogoprostorudlâzadačviboru AT kondrukné applicationsofclustirizationofcriterionspaceforthechoiceproblems AT malârnn applicationsofclustirizationofcriterionspaceforthechoiceproblems |