Contribution to International Economy

  • РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНОГО ОБЕСПЕЧЕ-
СОДЕРЖАНИЕ
стр.
Введение 3
1. Концептуальные проблемы решения многокритериаль-
ных задач принятия решений 5
1.1. Наличие противоречий между некоторыми частными критериями 5
1.2. Разнородность частных критериев 7
1.3. Сложность установления приоритетов разнородных частных критериев 7
2. Применение метода формирования векторов предпочтений как один из подходов к решению проблем, связанных с решением многокритериальных задач принятия решений 8
2.1. Необходимость использования экспертных знаний для идентификации весовых коэффициентов 8
2.2. Декомпозиция вектора предпочтений и методы сравнения альтернатив по отдельным свойствам 10
2.3. Формирование векторов предпочтений и уточнение весовых коэффициентов частных критериев оптимальности для сравнение альтернатив в целом 11
3. Алгоритм формирования векторов предпочтений для идентификации весовых коэффициентов частных критериев оптимальности 16
4. Программное обеспечение для решения задач идентификации весовых коэффициентов частных критериев оптимальности методом формирования векторов предпочтений 18
Заключение 23
Литература 24

Введение
Задача идентификации формулируется следующим образом: по результатам наблюдений над входными и выходными переменными системы должна быть построена оптимальная в некотором смысле модель, т.е. формализованное представление этой системы, используемое затем для исследования, проектирования и непосредственного управления.
Идентификация весовых коэффициентов частных критериев оптимальности является важнейшей составляющей процесса решения многокритериальных оптимизационных задач.
Формализованное представление любой задачи, в том числе и многокритериальной задачи принятия решений, является необходимым этапом для ее решения на ЭВМ. Среди огромного класса многокритериальных задач принятия решений существует значительное число задач, для которых существуют трудности концептуального характера при их формализации.
Если для задач принятия решений в условиях детерминированной определенности с численным оцениванием исходов по одному показателю цель адекватна максимизации (или минимизации) целевой функции, и для этих задач имеется фактически единственная концепция оптимальности решения: оптимальным будет решение, доставляющее целевой функции наибольшее (или наименьшее) значение. То совершенно другая картина имеет место, когда исходы оцениваются по нескольким показателям.
Для таких задач принятия решений между некоторыми частными показателями возникают противоречия. Суть этого противоречия состоит в том, что стремление улучшить какой либо частный показатель ведет, как правило, к ухудшению некоторого другого.
Некоторые классы задач векторной оптимизации отличаются тем, что частные показатели имеют различную физическую природу и поэтому различную размерность. Это обстоятельство значительно осложняет решение задач векторной оптимизации. Возникает проблема нормирования показателей, под которой понимается приведение показателей к единому безразмерному виду.
Возможен случай, когда количественные показатели оценивания альтернатив объективно не могут быть введены и использованы в процедуре сравнения процедур. В этой ситуации применяется некоторое отношение сравнения, определенное на множестве сопоставляемых альтернатив (выбор по отношению предпочтения).
Рассмотренные выше проблемы решения многокритериальных задач принятия решений, а также зачастую наличие существующей неопределённости в задачах выбора не могут быть сняты только на основе использования результатов расчетов с помощью объективных моделей. В таких ситуациях только привлечение экспертов оказывается единственным источником информации, позволяющим оценить варианты решений и выбрать из них наилучший. Использование знаний экспертов, их системы предпочтений становится принципиальным моментом в процессе формирования решений. В этом случае субъективная информация представляется как единственно возможная основа объединения параметров рассматриваемой проблемы в единую модель, позволяющую оценить варианты решений.
Применение метода формирования векторов предпочтений позволяет снять ряд проблем, связанных с решением многокритериальных задач принятия решений, а именно на основе знаний экспертов позволяет установить значения весовых коэффициентов частных критериев таким образом, что позволит выбрать одно единственно верное решение при сравнении разных альтернатив.
Цель работы: в соответствии с принципами метода формирования векторов предпочтений разработать алгоритмы и программное обеспечение для решения задач идентификации весовых коэффициентов частных критериев оптимальности.


1. Концептуальные проблемы решения многокритериальных задач принятия решений
Весьма важным классификационным признаком для задач принятия решений является количество показателей оценивания, по которым сравниваются исходы (альтернативы). По этому признаку задачи делятся на скалярные и векторные. В первом случае решения сравниваются по единственному числовому показателю, представленной в виде скалярной функции, заданной на множестве возможных решений. Во втором случае каждое решения оценивается набором частных показателей, каждый из которых в ряде случаев представляется скалярной функцией, определенной на множестве решений.
В случае, когда исход характеризуется несколькими частными показателями оценивания, выбор наилучшего решения обосновывают с помощью теории векторной оптимизации.
Задачей векторной оптимизации называется задача, решаемая с учетом нескольких скалярных показателей оценивания, т. е. на основе векторного показателя, компонентами которого являются эти скалярные показатели.
1.1. Наличие противоречий между некоторыми частными критериями
Задачи векторной оптимизации принципиально отличаются от задач с оцениванием исходов по одному скалярному показателю. Это отличие обусловлено тем, что в математике отношение порядка для векторов не установлено.
В задачах с одним показателем полная информация о предпочтениях исходов обычно состоит в указании направления предпочтительного изменения значений скалярного показателя, принадлежащих области действительных чисел. Это объясняется тем, что в большинстве прикладных задач в качестве показателя выбирается такая функция, для которой либо большее значение всегда предпочтительнее меньшего, либо наоборот, меньшее значение предпочтительнее большего.
Так как для задач принятия решений в условиях детерминированной определенности с численным оцениванием исходов по одному показателю цель адекватна максимизации (или минимизации) целевой функции, то для этих задач имеется фактически единственная концепция оптимальности решения: оптимальным будет решение, доставляющее целевой функции наибольшее (или наименьшее) значение. Совершенно другая картина имеет место, когда исходы оцениваются по нескольким показателям.
Для таких задач принятия решений между некоторыми частными показателями возникают противоречия. Суть этого противоречия состоит в том, что стремление улучшить какой либо частный показатель ведет, как правило, к ухудшению некоторого другого. Например, повышение надежности технической системы и снижение её стоимости, как правило, противоречивы. Данная ситуация относится к проблеме «эффект-затраты», когда целевой и экономический эффекты находятся в противоречии (улучшение одного из них влечет за собой ухудшение другого). Действительно, только в исключительных случаях экстремумы нескольких независимых друг от друга функций достигаются в одной точке. Типичным же является случай, когда экстремумы имеют место в различных точках и не ясно, какую точку (решение) следует считать наилучшей (оптимальной).
В данном случае при поиске решения сталкиваются с трудностью концептуального характера связанной с тем, что следует понимать под оптимальным решением, в отличие от задачи принятия решения в условиях детерминированной определённости с одним оптимизируемым показателем, когда принцип оптимальности очевиден (оптимально то решение, которое максимизирует (минимизирует) значение показателя) и возникают только трудности технического (вычислительного) характера, связанные с поиском оптимального решения.
При выборе решения в задаче с несколькими показателями оценивания надо ограничиться теми решениями, для которых невозможно одновременное улучшение всех показателей. Такие решения называются эффективными, или оптимальными по Парето. В качестве синонимов этого названия используются также наименования: недоминируемые, нехудшие, неподчиненные решения. Следовательно, выбор решений следует производить из множества эффективных решений. Однако остается неясным, какое именно эффективное решение следует признать в качестве оптимального. Использование информации об альтернативах, содержащейся только в значениях компонентов векторного показателя, не позволяет, как правило, выбрать единственную альтернативу. Необходима дополнительная информация, чтобы установить принцип оптимальности, основанный на некотором компромиссе, и в соответствии с ним выбрать единственное компромиссно-оптимальное решение.
1.2. Разнородность частных критериев
Некоторые классы задач векторной оптимизации отличаются тем, что частные показатели имеют различную физическую природу и поэтому различную размерность. Это обстоятельство значительно осложняет решение задач векторной оптимизации. Возникает проблема нормирования показателей, под которой понимается приведение показателей к единому безразмерному виду. К настоящему времени разработано большое количество различных схем нормирования.
Возможен случай, когда количественные показатели оценивания альтернатив объективно не могут быть введены и использованы в процедуре сравнения процедур. В этой ситуации применяется некоторое отношение сравнения, определенное на множестве сопоставляемых альтернатив (выбор по отношению предпочтения). В теории решений используются два различных (по смыслу и употреблению) основных отношения: отношение строгого предпочтения и отношение нестрогого предпочтения.
1.3. Сложность установления приоритетов разнородных частных
критериев
В ряде случаев частные показатели имеют различную степень важности. Это следует учитывать при выборе оптимального решения, отдавая известное предпочтение более важным показателям.
2. Применение метода формирования векторов предпочтений как один из подходов к решению многокритериальных задач принятия решений
2.1. Необходимость использования экспертных знаний для идентификации весовых коэффициентов
Одним из возможных вариантов решения многокритериальной задачи принятия решений является сведение задачи векторной оптимизации к эквивалентной (в смысле принятого принципа оптимальности) задаче скалярной оптимизации, которая затем решается на основе очевидного принципа предпочтительности: большему (меньшему) значению скалярного показателя оценивания предпочтительности, полученного скаляризацией векторного показателя исходной задачи, соответствует более предпочтительное решение. Вследствие этого проблему выбора схемы компромисса и соответствующего ей принципа оптимальности называют проблемой скаляризаци. Примером скаляризации является свертывание векторного показателя
F=(F1, …Fm) (2.3)
в скалярный показатель
F= 1F1+2F2+…+mFm, (2.4)
где I ,i=1…m, - весовые коэффициенты частных критериев оптимальности.
Число возможных схем компромисса практически неограниченно. Наиболее часто применяются принципы компромиссов, такие как принцип выделения главного показателя, принцип обобщенного показателя, принцип максимина и принцип последовательной уступки.
Обобщенный скалярный показатель:
(2.5)
может быть использован для свертывания векторного показателя F=(F1, …Fm), если о его компонентах F1, …Fm известна следующая информация:
частные показатели количественно соизмеримы по важности, т.е. каждому из них можно поставить в соответствие некоторое число I >=0 ( ), которое численно характеризует его относительную важность по отношению к другим показателям;
частные показатели являются однородными, т.е. допускают количественное сравнение в одной размерности.
Недостатком средневзвешенного арифметического показателя является то, что эффективное решение, выбранное в качестве оптимально-компромиссного решения может оказаться неудовлетворительным по некоторым частным показателям Fk(x) , т.е. при обеспечении максимума функции:

(2.6)
может оказаться, что один частный показатель качества компенсируется за счет других, которые могут оказаться недопустимо малыми.
Обобщенный скалярный показатель в виде средневзвешенного показателя представляет собой искусственную форму обобщения. Определение весовых коэффициентов обычно осуществляется экспертными методами, что дает возможность как то решить перечисленные выше проблемы решения многокритериальных задач принятия решений используя специальные методы, основанные на знаниях и опыте экспертов по рассматриваемой проблеме, а также их системы предпочтений.
Рассмотренные выше проблемы скаляризации и другие приведенные в первом разделе, проблемы решения многокритериальных задач принятия решений, а также зачастую наличие существующей неопределённости в задачах выбора не могут быть сняты только на основе использования результатов расчетов с помощью объективных моделей. В таких ситуациях только привлечение экспертов оказывается единственным источником информации, позволяющим оценить варианты решений и выбрать из них наилучший. Использование знаний экспертов, их системы предпочтений становится принципиальным моментом в процессе формирования решений. В этом случае субъективная информация представляется как единственно возможная основа объединения параметров рассматриваемой проблемы в единую модель, позволяющую оценить варианты решений. Для повышения качества решений при наличии субъективных факторов используют так называемые системы поддержки принятия решений − человеко-машинные системы, имеющие базы знаний. База знаний может содержать в себе как фактические, объективные данные о той или иной предметной области, так и правила принятия решений опытных лиц принимающих решения. Основная задача таких систем состоит в сопоставлении каждой предметной ситуации рекомендуемых вариантов решений.
2.2. Декомпозиция вектора предпочтений и методы сравнения альтернатив по отдельным свойствам
Одним из принципов данного метода, который облегчает принятие решения, является переход от сравнения альтернатив в целом к сравнению их отдельных свойств. Основная идея такого подхода состоит в том, что в отношении отдельного свойства существенно легче сказать, какая из альтернатив предпочтительней.
Выделение свойств альтернатив является не чем иным, как декомпозицией. Свойства первого иерархического уровня могут делиться на следующие наборы свойств и т.д. Глубина такого деления определяется стремлением дойти до тех свойств, которые удобно сравнивать друг с другом. После сравнения альтернатив по отдельным свойствам должен быть осуществлен обратный переход к требуемому сравнению альтернатив в целом.
Наиболее аргументированным способом выбора представляется сравнение альтернатив на основе сопоставления им числа. Здесь необходима лишь уверенность в том, что выполненное сопоставление объективно. Как правило, это имеет место, если показатель свойства обладает физическим смыслом и, следовательно, объективно обусловлен. В задаче принятия решений следует стремиться довести декомпозицию до уровней, для которых возможны численные оценки свойств. Получение набора объективно обусловленных количественных показателей свойств альтернатив является одной из важных целей декомпозиции. К подходу, связанному с получением набора показателей свойств прибегают и тогда, когда естественные числовые характеристики отсутствуют. В последнем случае вводят искусственные оценки типа бальных оценок, формируемых экспертами.
2.3. Формирование векторов предпочтений и уточнение весовых коэффициентов частных критериев оптимальности для сравнение альтернатив в целом
После того как экспертным путем уточнены частные критерии и их важность (с помощью предварительного определения значения весовых коэффициентов частных критериев оптимальности) в соответствии с методом формирования векторов предпочтений проводится сравнение альтернатив по каждому свойству.
Сравнение альтернатив по отдельным свойствам может быть выполнено одним из трех способов:
на основе попарного сравнения альтернатив по данному свойству;
на основе введения естественных объективно обусловленных количественных показателей степени проявления свойств;
на основе введения искусственных объективно обусловленных числовых показателей свойств.
При попарном сравнении считается, что для двух альтернатив Х1 и Х2 из множества Ω каким то образом можно произвести выбор наиболее предпочтительной по данному свойству. Способ выбора в общем случае не конкретизируется.
С формальной точки зрения для двух альтернатив Х1 и Х2 из Ω вводится бинарная операция сравнения по свойству (бинарное отношение) r . Запись Х1 r Х2 означает, что альтернатива Х1 предпочтительнее (или в несколько измененной трактовки “не хуже”) альтернативы Х2 по свойству r. Для операции сравнения r естественной является аксиома транзитивности: из Х1 r Х2 и Х2 r Х3 следует Х1 r Х3. Дополнительно могут быть введены аксиомы антисимметричности и антирефлексивности. При выполнении аксиомы антисимметричности из Х1 r Х2 и Х2 r Х1 верно лишь одно, а при аксиоме антирефлексивности из Х1 r Х2 следует несовпадение альтернатив Х1 и Х2. Естественное отношение предпочтения антисимметрично и антирефлексивно. Естественное отношение “не хуже” этими свойствами не обладает. Для обозначения операции сравнения вместо записи Х1 r Х2 используется также запись Х1 > Х2 (предпочтение) и Х1 ≥ Х2 “не хуже”.
Итак, для всех свойств альтернатив рассматривается отношение сравнения. Пусть любая из альтернатив имеет m свойств, по каждому из которых может быть задана операция сравнения вида Хk ri Хl , I = 1…m. Будем считать что, отношения r1, r2 ,… rm транзитивны и антирефлексивны. Допустим пока, что по любому отношению ri , i = 1...m , сравнимы две любые альтернативы из Ω. Тогда по каждому свойству может быть выполнено полное ранжирование альтернатив. Результатом операции полного ранжирования альтернатив будет набор перестановок из альтернатив, который можно записать в виде матрицы из m столбцов (по числу свойств) и n (по числу альтернатив).
Например, пусть имеется задача с четырьмя альтернативами и двумя свойствами. На основании бинарного сравнения может быть выполнена специальная операция ранжирования (упорядочения). В результате ее выполнения альтернативы в зависимости от свойства r располагаются в определенном порядке: от наиболее до наименее предпочтительной.
Ранжирование альтернатив по свойствам дало следующий результат: по первому свойству (первому частному критерию) первая альтернатива предпочтительнее четвертой, а четвертая в свою очередь предпочтительнее третьей, третья предпочтительнее второй.
По второму свойству (второму частному критерию) четвертая альтернатива предпочтительнее третьей, а третья в свою очередь предпочтительнее второй, вторая предпочтительнее первой.
Х1 r1 Х4 , Х4 r1 Х3 , Х3 r1 Х2 , (2.7)
Х4 r2 Х3 , Х3 r2 Х2 , Х2 r2 Х1
Матрица ранжирования имеет вид
1 4
4 3 (2.8)
3 2
2 1
В ней первая вектор-строка (вектор приоритетов) содержит наиболее предпочтительные альтернативы по первому (Х1) и второму (Х2) свойствам. То есть по первому частному критерию предпочтительнее всех первый вариант решения, по второму частному критерию предпочтительнее всех четвертый вариант решения.
Одним из способов работы с такой матрицей является введение условного пространства свойств. В нем в проекции на ось ri альтернативы будут располагаться в соответствии с ранжированием по операции ri. Эквивалент записей (2.7) и (2.8) приведен на рис. 2.1. Здесь неулучшаемыми альтернативами будут альтернативы (Х1) и (Х4).
Дальнейший выбор среди неулучшаемых альтернатив в основном производится также методом экспертизы. Однако следует отметить, что эксперты всегда могут перед окончательным вариантом выбора поварьировать значениями весовых коэффициентов частных критериев оптимальности, чтобы убедиться в правильности своего выбора.
Х4
4
3
2
1 Х1
1 2 3 4
Рис. 2.1. Неулучшаемые альтернативы на условном пространстве
свойств
Например, в данном случае видно, что первая альтернатива предпочтительнее всех других по первому показателю оптимальности, но в тоже время первая альтернатива хуже всех по второму показателю оптимальности. В тоже время четвертая альтернатива предпочтительнее всех остальных по второму показателю оптимальности, и в тоже время четвертая альтернатива находится по второму показателю оптимальности уступает только первой. Далее, если значение весового коэффициента первого частного критерия, установленного экспертами до начала попарного сравнения не намного отличается от значения весового коэффициента второго частного критерия (где то по 0,4-0,5), то экспертами может быть изменены веса этих частных критериев в сторону увеличения весового коэффициента второго частного критерия.
Таким образом решается задача идентификации весовых коэффициентов частных критериев оптимальности путем формирования векторов предпочтений. Построена оптимальная в некотором смысле модель выбора решений из имеющихся альтернатив и уточнены значения весовых коэффициентов частных критериев оптимальности, т.е. получено формализованное представление этой системы. В дальнейшем установленные частные критерии оптимальности с соответственно своими весовыми коэффициентами применяются для исследования, проектирования и непосредственного управления. В случае управления быстротечными процессами правильность выбранного решения непосредственно подскажет практика. В ином случае имеется возможность смоделировать реальную действительность и проверить результативность функционирования системы выбора решений.
3. Алгоритм формирования векторов предпочтений для идентификации весовых коэффициентов частных критериев оптимальности


Рис.3.1. Алгоритм попарного сравнения предпочтений
Данный алгоритм представляет собой последовательность действий, приводящих к искомому результату. В чем заключается результат? Результат заключается в том, что в результате выполнения операций, описанные в блоках данного алгоритма альтернативы ранжируются по убыванию.
4. Программное обеспечение для решения задач идентификации весовых коэффициентов частных критериев оптимальности методом формирования векторов предпочтений
Программное обеспечение, реализующее задачу идентификации весовых коэффициентов частных критериев оптимальности методом формирования векторов предпочтений разработано на языке программирования высокого уровня С++ Builder.
Интегрированная среда разработки приложений представлена на рис. 4.1.


Рис. 4.1. Интегрированная среда разработки приложений
Текст программы представлен ниже:
/---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
int n =4;
int vk [4]; // вес коэф вектора
vk[1]=5;
vk[2]=3;
vk[3]=6;
vk[4]=4;
Edit1->Text= vk[1];
Edit2->Text= vk[2];
Edit3->Text= vk[3];
Edit4->Text= vk[4];
int i;
int p;
i=1;
for(i=1;i<(n-1);i++)
{
if (vk[i]<vk[i+1])
{
p= vk[i];
vk[i]=vk[i+1];
vk[i+1]=p;
}
}
Edit5->Text= vk[1];
Edit6->Text= vk[2];
Edit7->Text= vk[3];
Edit8->Text= vk[4];
}
//---------------------------------------------------------------------------

Рис. 4.2. Результат ранжирования весовых коэффициентлв
Заключение
Идентификация весовых коэффициентов частных критериев оптимальности является важнейшей составляющей процесса решения многокритериальных оптимизационных задач.
Формализованное представление любой задачи, в том числе и многокритериальной задачи принятия решений, является необходимым этапом для ее решения на ЭВМ. Среди огромного класса многокритериальных задач принятия решений существует значительное число задач, для которых существуют трудности концептуального характера при их формализации.
Для таких задач принятия решений между некоторыми частными показателями возникают противоречия. Суть этого противоречия состоит в том, что стремление улучшить какой либо частный показатель ведет, как правило, к ухудшению некоторого другого.
Некоторые классы задач векторной оптимизации отличаются тем, что частные показатели имеют различную физическую природу и поэтому различную размерность. Это обстоятельство значительно осложняет решение задач векторной оптимизации. Возникает проблема нормирования показателей, под которой понимается приведение показателей к единому безразмерному виду.
Некоторые классы задач векторной оптимизации отличаются тем, что частные показатели имеют различную физическую природу и поэтому различную размерность. Это обстоятельство значительно осложняет решение задач векторной оптимизации. Возникает проблема нормирования показателей, под которой понимается приведение показателей к единому безразмерному виду.
Применение метода формирования векторов предпочтений позволяет снять ряд проблем, связанных с решением многокритериальных задач принятия решений, а именно на основе знаний экспертов позволяет установить значения весовых коэффициентов частных критериев таким образом, что позволит выбрать одно единственно верное решение при сравнении разных альтернатив.
Литература
1. Вилкас Э.Й., Маиминас Е.З. Решения: теория, информация, моделирование.&#8722;Радио и связь, 1981&#8722; 328 с.
2. Экспертные системы. Принципы работы и примеры. Пер. с англ./
А.Брукинг, П.Джонс, Ф. Кокс и др. Под ред.Р. Форсайта.
3. Культин Н. С++ Builder в задачах и примерах.- СПб.:БХВ-Петербург. 2005.-336 с.
4. Осуга С. Обработка знаний. Пер. с япон.- М.:Мир.1989.-293 с.
5. Логическое программирование. Пер. с англ. и фр.-М.1988.


Другие работы по теме: