Применение принципа гарантированного результата для учета качественной информации о предпочтениях при комплексной оценке качества функционирования телекоммуникационных сетей

Размещено на http://www.allbest.ru/

Применение принципа гарантированного результата для учета качественной информации о предпочтениях при комплексной оценке качества функционирования телекоммуникационных сетей

Д.Е. Шапошников

Нижегородский государственный университет им. Н.И. Лобачевского

Аннотация: В статье рассматривается способ решения задач многокритериального выбора и ранжирования на основе автоматического вычисления весовых коэффициентов важности частных критериев по принципу гарантированного результата с использованием обобщенного логического критерия максимальной осторожности. Данный способ позволяет учитывать дополнительную качественную информацию лица, принимающего решение, в виде графа предпочтений с уточняющими коэффициентами. Полученные на основе принципа гарантированного результата значения весовых коэффициентов обладают свойством равномерности. Решения оптимизационных задач приводятся в виде конечных алгоритмов и аналитических выражений с учетом введенной дополнительной информации. Описан анализ данной информации и способы её представления.

Ключевые слова: Принятие решений, многокритериальный выбор, область эффективных решений, качественная информация о предпочтениях, принцип гарантированного результата.

При решении задач планирования и развития телекоммуникационных сетей, а также при оценке деятельности подразделений телекоммуникационного оператора (разделенных по географическому и/или функциональному признаку) возникает проблема комплексной многопараметрической оценки варианта конфигурации телекоммуникационной сети. Многокритериальной оценке вариантов при выборе или ранжировании вариантов посвящено значительное число усилий ученых и это широко описано в литературе [1-5]. При этом под задачей выбора понимается ситуация ранжирования вариантов по итоговой оценке качества и, в дальнейшем, необходимости выбора наилучшего в некотором смысле варианта из множества рассматриваемых. В дальнейшем будем говорить о задачах выбора и ранжирования как эквивалентных.

В задачах выбора и оценивания, в большинстве случаев имеющиеся альтернативы оцениваются сразу по нескольким критериям [6 _ 8], то есть, являются многокритериальными. В случае многокритериального выбора и речь идет о компромиссном решении - решении, которое не может быть улучшено ни по одному из критериев без ухудшения по другим критериям [9]. В случае многокритериальной оценки речь идет о компромиссном варианте ранжирования.

Существуют подходы к задачам многокритериального выбора и ранжирования (МКВР), учитывающие качественную информацию о предпочтениях ЛПР [3]. Основным недостатком этих методов является требование к ЛПР о вводе достаточно большого объема дополнительных параметров, отсутствие (хотя бы, частичное) которых ставит под вопрос применимость этих методов. Описанная методика предполагает использование ровно того количества информации, которое ЛПР готово предоставить (в частном случае, вообще отсутствие такой информации).

Одним из самых известных и распространенных способов решения задач МКВР является применение обобщенного критерия оптимальности с весовыми коэффициентами важности , отражающими мнение лица, принимающего решение (ЛПР) об относительной предпочтительности частных критериев оптимальности, и решение однокритериальной задачи оптимизации (выбора) следующего вида (при выборе направления минимизации):

. (1)

В дальнейшем, для краткости, через будем обозначать вектор численных оценок частных критериев при определенном в контексте . Кроме того, предположим, что численные значения оценок приведены к безразмерному виду и некоторому интервалу , причем (например, к интервалу ).

В задаче (1) важность критериев понимается в смысле аксиоматической теории важности [11], что позволяет считать: если известна дополнительная информация вида "-й критерий не менее важен, чем j-й критерий (), то для весовых коэффициентов и справедливо соотношение:

. (2)

гарантированный результат учет информация

Весовые коэффициенты могут быть назначены ЛПР различными способами [10, 13, 14]. При использовании (или неиспользовании) одного из них, но при возможности назначить точные численные значения весовых коэффициентов со стороны ЛПР, получаем возможность решить задачу подходящим методом оптимизации. Однако все известные методы назначения весовых коэффициентов важности в задаче (1) требуют полноты вводимой информации с точно определенными числовыми оценками в соответствии с алгоритмом метода.

В ряде работ [10, 12] был предложен и развит подход, при котором весовые коэффициенты важности частных критериев являются неконтролируемыми факторами, их значения могут быть различными для различных вариантов выбора, отражать зависимость от них. При этом численные значения весовых коэффициентов могут быть вычислены по принципу гарантированного результата:

.

При этом область допустимых значений весовых коэффициентов важности определяется следующим образом:

. (3)

В дальнейшем будем считать, что в общем случае (при отсутствии качественной информации о предпочтениях частных критериев) весовые коэффициенты , нормированы относительно положительного параметра .

Величина необходима для исключения ситуации, при которой значение весового коэффициента частного критерия в результате решения некоторой оптимизационной задачи может стать равной нулю. Фактически это будет означать «выключение» данного частного критерия из дальнейшего рассмотрения и, следовательно, по сути, решение другой задачи многокритериального выбора. Кроме того, как известно [9] нулевое значение весового коэффициента может привести к выбору слабо-эффективного решения в качестве оптимального.

В качестве обобщенного критерия оптимальности могут быть использованы различные функции [9]. Особое место среди них занимает обобщенный логический критерий минимизации, который можно назвать «обобщенным критерием максимальной осторожности» (или принципом гарантированного результата) при расчете весовых коэффициентов:

. (4)

Таким образом, исходная задача (2) при использовании данного обобщенного логического критерия формулируется так:

. (5)

При этом область допустимых значений весовых коэффициентов важности в задаче (5) определяется как (2).

Использование дополнительной качественной информации об относительной предпочтительности частных критериев заключается в том, что от ЛПР может быть получена дополнительная качественная информация, устанавливающая для некоторых L пар частных критериев (необязательно для всех возможных пар) предпочтение i-го критерия над j-м критерием на всем множестве D допустимых вариантов:

. (6)

Информация (6) является качественной, так как из нее следует, что i-й критерий важнее j-го критерия, но нельзя сказать, во сколько раз. Тогда качественная информация (6) в соответствии с соотношением (2) позволяет уточнить определение области допустимых значений (3) весовых коэффициентов следующим образом:

.

Данный подход позволяет ЛПР предоставить информацию о своих предпочтениях в виде некоторого (в общем случае - неполного) множества пар сравнения частных критериев.

В некоторых случаях ЛПР имеет возможность уточнить информацию о взаимной предпочтительности частных критериев и соответствующих весовых коэффициентах и связанных отношением с помощью параметра :

. (8)

Будем считать, что дополнительная качественная информация (6) является непротиворечивой, если область непуста.

Представим качественную информацию от ЛПР в виде графа , где - множество вершин, соответствующих частным критериям, - множество ребер, соединяющих -ю вершину с -й тогда и только тогда, когда выполняется соотношение .

Разобьем все вершины графа на слои (ярусы) следующим образом:

- к последнему слою отнесем те вершины, из которых не выходит ни одна дуга;

- к предпоследнему слою - те и только те вершины, исходящие дуги которых входят в вершины последнего слоя;

- к третьему нижнему слою - те и только те вершины, исходящие дуги которых входят в вершины последнего и предпоследнего слоев, и т. д.;

- к первому слою отнесем оставшиеся вершины, то есть, те и только те, исходящие дуги которых входят в вершины остальных слоев;

- перенумеровываем слои графа таким образом, чтобы первый слой имел первый номер , а самый нижний слой - номер .

В качестве иллюстрации приведем пример графа предпочтений (рис. 1). В данном примере используются семь частных критериев и введенная ЛПР информация.

Размещено на http://www.allbest.ru/

Рисунок 1. - Граф предпочтений с коэффициентами и разделение по слоям (ярусам) с

Отметим, что расположение вершин графа, соответствующих частным критериям, на одном слое не означает эквивалентности по важности частных критериев. Их расположение на одном слое можно условно назвать случайным, поскольку ЛПР никак их между собой никак по важности (предпочтительности) не сравнил.

В частном случае отсутствия качественной информации (6) граф не будет иметь ни одной дуги, и будет представлять собой совокупность из точек (рис. 2).

Размещено на http://www.allbest.ru/

Рисунок 2. - Граф предпочтений при отсутствии качественной информации

Можно рассмотреть также частный случай линейной упорядоченности частных критериев по важности:

.

В данном случае (рис. 3) граф будет иметь число слоев, равное числу вершин .

Размещено на http://www.allbest.ru/

Рисунок 3. - Граф предпочтений при линейной упорядоченности критериев по важности

Введем дополнительные обозначения:

, - множество вершин графа , из которых имеется путь в вершину , включая ее саму;

- мощность множества ;

-- произвольный путь в графе :,

где -- дуга, входящая в путь, -- число дуг в пути ;

- множество всех путей из вершины в вершину ;

для всех (9)

где _ уточняющий коэффициент для соответствующей дуги графа предпочтений ;

. (10)

В таблице ниже (табл. 1) приведен пример расчета величин и для приведенного примера.

Таблица №1

Вычисление величин и для графа на рис. 1

	Величины при
1		1.728
2		1.69
3		1.44
4		1.3
5		1.2
6	_	1
7	_	1

Для данной задачи (5) и приведенной области допустимых значений весовых коэффициентов (8) могут быть получены методы вычисления весовых коэффициентов важности по принципу гарантированного результата при помощи конечных алгоритмов.

Рассмотрим решение задачи вычисления весовых коэффициентов важности по принципу гарантированного результата (то есть, при использовании обобщенного логического критерия «максимальной осторожности»):

, (11)

. (12)

Для решения этой задачи (нахождения значений весовых коэффициентов важности ) с нулевым значением параметра может быть применен следующий алгоритм.

Алгоритм вычисления весовых коэффициентов (алгоритм 1).

1. Граф отношений предпочтения разбивается на слои .

2. Каждой вершине графа приписываем начальное значение:

.

3. В качестве первого слоя рассматриваем нижний слой ().

4. Для каждой вершины -го слоя полагаем:

.

5. Проводим корректировку значений для вершин более высоких слоев:

,

где - множество вершин, в которые есть путь из вершины .

6. Полагаем . Если (то есть, рассмотрены все слои), то переходим к п.7, в противном случае повторяем вычисления с п.4.

7. Вычисляем итоговые значения весовых коэффициентов важности:

.

Конец алгоритма. Для обоснования корректности данного алгоритма (алгоритма 1) необходима следующая лемма.

Лемма 2.1. Вектор весовых коэффициентов , построенный с помощью алгоритма 1, обладает следующим свойством: для любой вершины , принадлежащей -му слою и такой, что

,

всегда найдется вершина , принадлежащая нижнему по отношению к -му слою , такая, что и , то есть, для которой .

Доказательство.

Пусть вектор построен по алгоритму 1. Тогда, для всех вершин самого нижнего -го слоя, согласно пунктам 4 и 7, получим для всех .

Рассмотрим произвольную вершину такую, что . Построим путь из вершины в вершину следующим образом (построение такого пути всегда возможно в силу определения слоя).

Среди всех вершин множества найдем такую вершину , что

.

Если не принадлежит , то выбираем следующую вершину такую, что

,

и так до тех пор, пока не найдем вершину , принадлежащую нижнему -му слою:

,

.

Согласно построению весового коэффициента по алгоритму 1 возможны два случая.

Случай 1. Для всех имеем . Тогда из построения алгоритма 1 следует, что

.

То есть требуемая по лемме -я вершина нижнего слоя определена - ею является вершина .

Случай 2. Найдется такая вершина , что и для всех .

Тогда из алгоритма 1 следует, что , то есть, искомой (-й вершиной нижнего слоя) будет вершина . Что и требовалось доказать.

Лемма 1 позволяет доказать следующую теорему.

Теорема 1. Вектор весовых коэффициентов , построенный с помощью алгоритма 1, является оптимальным решением экстремальной задачи (11)-(12) при нулевом значении параметра .

Доказательство.

Пусть вектор построен по алгоритму 1. Тогда

.

При этом для и для .

Предположим от противного, что имеется вектор , который является оптимальным решением задачи (11)-(12):

.

Так как , то

для всех . (13)

Покажем, что в этом случае будет иметь место и система неравенств:

для всех . (14)

Действительно, предположим, что найдутся такие , что . Так как , то согласно лемме 1 найдется вершина , такая, что

и .

Просуммировав по от 1 до значения и , и, учитывая неравенства (13) и (14), получим, что

. (15)

Так как вектора и принадлежат области , то их сумма равняется величине . Тогда из неравенства (15) следует, что . Полученное противоречие говорит о том, что сделанное предположение неверно и, следовательно, вектор , построенный с помощью алгоритма 1, является оптимальным решением экстремальной задачи (11)-(12). Что и требовалось доказать.

Сущность данного подхода и принцип минимакса при вычислении весовых коэффициентов практически гарантируют, что получаемые значения весовых коэффициентов будут иметь ненулевые значения. Поэтому, наличием жесткого параметра при расчетах можно пренебречь при условии достаточно малого его значения.

Тем не менее, рассмотрим частный случай задачи (11)-(12) при совместно с обобщением на случай ненулевого значения минимального порога , где

, (16)

. (17)

Для вычисления значений весовых коэффициентов важности используется следующий алгоритм.

Алгоритм вычисления весовых коэффициентов (алгоритм 2).

1. Полагаем .

2. Для графа предпочтений с помощью алгоритма 1 с параметром находим значение .

3. Если для всех выполняется условие , то полагаем и задача решена; в противном случае переходим к п.4.

4. Для каждой вершины , для которой выполняется условие , осуществляем следующие действия:

а) полагаем

б) исключаем вершину из рассмотрения, для этого полагаем и из множества исключаем дуги, инцидентные вершине (если они есть).

После выполнения указанных действий для всех вершин, в которых выполнилось условие , повторяем вычисления с п.2.

Конец алгоритма.

Корректность данного алгоритма обосновывают теорема 2 и вспомогательная лемма 2. Их доказательства приведены в [3]. Лемма показывает, что исключение вершины из графа предпочтений не изменяет отношение предпочтения, введенное ЛПР, для остальных вершин.

Лемма 2. Операция исключения вершины из графа на шаге 4 алгоритма 2 не изменяет частичное попарное отношение предпочтения на множестве .

Теорема 2 обосновывает применение приведенного алгоритма.

Теорема 2. Вектор весовых коэффициентов , построенный с помощью алгоритма 2, является оптимальным решением задачи (16)-(17).

При получаем однократное применение алгоритма 1, что соответствует теореме 2.

Следствие 1 теоремы 2. В случае отсутствия дополнительной качественной информации (6) решением задачи (16), где

,

и при условии перенумерации критериев таким образом, чтобы выполнялось условие , является вектор , компоненты которого определяются по формуле

(18)

где - наибольший индекс , при котором выполняется условие:

(19).

Доказательство данного утверждения приведено в [3].

При и выражения (18)-(19) аналогичны результату, полученному в [7]:

.

Рассмотрим пример.

Пусть существуют три допустимых варианта решения, оцениваемые по четырем частным критериям. Оценки частных критериев для всех вариантов приведены в таблице (табл. 2). Оценки приведены к безразмерному виду и нормированы к единичному интервалу .

Таблица №2

Пример таблицы многокритериального выбора для трех вариантов и четырех критериев

	Оценки вариантов по критериям
Вариант
1	1	2	1.5	1.3
2	2	1.1	1.2	1.8
3	2	1.8	1.7	1

Граф предпочтений и соответствующие уточняющие коэффициенты показаны на рис. 4.

Размещено на http://www.allbest.ru/

Рисунок 4. - Граф предпочтений с коэффициентами
и разделение по слоям (ярусам) для иллюстративного примера

В таблице (табл. 3) приведен расчет величин и для данного примера.

Таблица №3

Вычисление величин и для графа на рис. 4

	Величины при
1		1.68
2		1.2
3		1.4
4	_	1

Приведем ход работы алгоритма (алгоритм 1) для первого варианта (в соответствии с нумерацией шагов алгоритма 1).

Шаг 2. Полагаем .

Шаг 3. Рассматриваем нижний слой: .

Шаг 4. Полагаем .

Шаг 5. Корректируем весовые коэффициенты у вершин на вышележащих слоях:

;

;

.

Шаг 6. Переходим к следующему слою (полагаем ) и возвращаемся к шагу 4.

Шаг 4.

Для вершины 2 находим значение: .

Для вершины 3 находим значение:.

Шаг 5. Корректируем значение коэффициента для вершины 1:

.

Шаг 6. Переходим к первому слою (полагаем ) и возвращаемся к шагу 4.

Шаг 4. Для вершины 1 находим значение: .

Шаг 5. Корректировка не требуется, так как вышележащие слои графа предпочтений отсутствуют.

Шаг 6. Все слои пройдены - переходим к шагу 7.

Шаг 7. Вычисляем итоговые значения весовых коэффициентов:

.

Для второго и третьего варианта весовые коэффициенты важности рассчитываются аналогично.

Результаты расчетов с итоговыми данными приведены в таблице (табл. 4). Оптимальным вариантом является третий вариант, затем по ранжированию следуют первый и второй.

Таблица №4

Вычисление величин и для графа на рис. 4

Вариант					Значение критерия
1	1	2	1.5	1.3	0.246212
	0.318182	0.227273	0.265152	0.189394
2	2	1.1	1.2	1.8	0.303216
	0.303216	0.275651	0.252680	0.168453
3	2	1.8	1.7	1	0.189394
	0.318182	0.227273	0.265152	0.189394

Данный иллюстративный пример показывает, что данная методика применима для широкого класса задач многокритериального выбора. Кроме того, приведенные соотношения легко обобщаются на общий случай решения задач многокритериального математического программирования.

Литература

1. Батищев Д.И. Поисковые методы оптимального проектирования. - М.: Советское радио, 1975. 286 с.

2. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984. 248 с.

3. Батищев Д.И., Шапошников Д.Е. Многокритериальный выбор с учетом индивидуальных предпочтений. ИПФ РАН. Нижний Новгород, 1994. 92 с.

4. Batishchev D.I., Anuchin V.F., Shaposhnikov D.E. The Use of the Qualitative Information on the Importance of Particular Criteria for the Computation of Weighting Coefficients. // Multiobjective Problems of Mathematical Programming / Lecture Notes in Economic and Mathematical Systems, v.35. Springer-Verlag, 1991. P. 2-7

5. Касимова (Костина) И.В., Шапошников Д.Е. Использование обобщенного критерия максимального риска для вычисления весовых коэффициентов важности при решении многокритериальных задач // Материалы XVIII международной научно-технической конференции «Информационные системы и технологии ИСТ-2012». Нижний Новгород, изд-во Нижегородского государственного технического университета, 2012

6. Бронштейн Е.М. Аппроксимация выпуклых множеств многогранниками // Современная математика. Фундаментальные направления. Т22, 2007. С. 5-37.

7. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. 384 с.

8. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

9. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 с.

10. Многокритериальная оптимизация: Математические аспекты / Березовский Б.А., Барышников Ю.М., Борзенко В.И., Кемпнер Л.М. М.: Наука, 1989. 128 с.

11. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений // Многокритериальные задачи принятия решений. М.: Машиностроение, 1978. С. 48-92

12. Березкин В.Е, Каменев Г.К., Лотов А.В. Гибридные адаптивные методы аппроксимации невыпуклой многомерной границы Парето // Журнал вычислительной математики и математической физики, 2006, т. 46, №11

13. Лоскутов А.Б., Солнцев Е.Б., Петрицкий С.А., Терентьев П.В. Методика интегральной оценки уровня энергоэффективности непромышленных объектов // Инженерный вестник Дона, 2014, №3. URL: ivdon.ru/ru/magazine/archive/n3y2014/2477.

14. Каменев Г.К., Лотов А.В., Рябиков А.И. Использование параллельных вычислений при аппроксимации многомерной границы Парето в задачах многокритериальной оптимизации // Доклады Пятой Международной конференции «Параллельные вычисления и задачи управления». М.: ИПУ РАН, 2010. С. 241-264.

15. Климова О.Н., Ногин В.Д. Учет взаимно зависимой информации об относительной важности критериев в процессе принятия решений // Журнал вычислительной математики и математической физики, т. 46, №12. СПб., 2006. С. 2179-2191

16. Земцов А.Н., Болгов Н.В., Божко С.Н. Многокритериальный выбор оптимальной системы управления базы данных с помощью метода анализа иерархий // Инженерный вестник Дона, 2014, №2. URL: ivdon.ru/ru/magazine/archive/n2y2014/2360

17. Лотов В.А., Поспелова И.И. Многокритериальные задачи принятия решений: учебное пособие. М: МАКС Пресс, 2008. 197 с.

18. Nelyubin A.., Podinovskiy V. Algorithmic decision rule using ordinal criteria importance coefficients with a first ordinal metric scale // Comput. Math. Math. Phys. 2012. № 1. P. 43-59.

19. Podinovskiy V. Using interval information on relative criteria tradeoffs in analyzing multicriterial decision making problems // Autom. Remote Control. 2010. Т. 71. № 8. P. 1648-1660.

20. Лазарев Е.А., Мисевич П.В., Шапошников Д.Е. Бикритериальная модель сети передачи данных // Системы Управления И Информационные Технологии. 2011. № 3.2 (45). С. 255-258.

Размещено на Allbest.ru

...