Содержание к диссертации
Введение
Глава 1 Многокритериальная задача: оптимальность по конусу 20
1 Предпочтение по конусу 20
1.1 Бинарные отношения 20
1.2 Выпуклые конусы 22
1.3 Предпочтение по конусу 24
2 Принципы оптимальности в задачах векторной оптимизации 26
2.1 Оптимальность по Слейтеру 28
2.2 Оптимальность по Парето 30
2.3 Оптимальность по Борвейну 31
2.4 Оптимальность по Джоффриону 33
2.5 А - оптимальность 34
3 Оптимальное по конусу решение многокритериальной задачи 35
4 Необходимые и достаточные условия 38
4.1 Сведения из теории многокритериальных задач 38
4.2 Необходимые и достаточные условия оптимальности по конусу 39
5 Уточнение оптимального по конусу решения 41
Глава 2 Метод анализа иерархии в игровой задаче N лиц с векторными выигрышами 47
6 Бескоалиционная игра N лиц с векторными выигрышами 47
6.1 Математическая постановка задачи 47
6.2 Пример: Биматричная игра с векторными выигрышами 50
6.3 Конусное равновесие Нэша в игровой задаче с векторными выигрышами 54
7 Применение метода анализа иерархии в игровой задаче 55
7.1 Метод анализа иерархий 55
7.2 Игровая задача с векторными выигрышами и иерархией целей 57
7.3 Метод анализа иерархий в игровой задаче с неполной информацией . 62
Глава 3 Многокритериальная динамическая задача при неопределен ности 68
8 Многокритериальная задача при неопределенности 69
8.1 Общая постановка задачи 69
8.2 Векторные гарантии 69
8.3 Гарантированные решения 72
8.4 Гарантированное по конусу решение многокритериальной задачи при неопределенности 74
9 Многокритериальная динамическая задача при неопределенности 77
9.1 Постановка задачи 77
9.2 Векторная С - гарантия 81
10 Применение принципа максимума 83
10.1 Постановка основной задачи оптимального управления 83
10.2 Необходимые условия существования С - гарантированного решения 86
11 Пример: Модель освоения вводимых производственных мощностей 87
11.1 Математическая модель 87
11.2 Нахождение стратегии IIе 90
11.3 Нахождение неопределенности ZQ 92
11.4 Нахождение С - седловой точки 93
12 Позиционная линейно-квадратичная задача 96
12.1 Формализация задачи 96
12.2 Экономическая интерпретация 98
12.3 Сведения из математического программирования 100
12.4 С-гарантированное решение МДЗН 102
Заключение 109
Литература
- Предпочтение по конусу
- Оптимальное по конусу решение многокритериальной задачи
- Пример: Биматричная игра с векторными выигрышами
- Гарантированное по конусу решение многокритериальной задачи при неопределенности
Введение к работе
Проблемы, связанные с выбором оптимальных решений встречаются практически во всех сферах человеческой деятельности. Чтобы принимать решения, которые реализуют поставленные цели в наибольшей степени, приходится учитывать несколько, иногда противоречивых, показателей для оценки каждой из альтернатив. Например, для оптимального функционирования предприятия ставят различные цели: добиться максимально возможных прибыли и выпуска продукции и одновременно с этим выдержать установленные показатели по ассортименту, снизить себестоимость, добиться определенного уровня качества продукции, и т.д. Случаи принятия решений на основании лишь одного критерия качества представляют собой модельные примеры, демонстрирующие применение различных методов оптимизации к социально-экономическим, или другим системам, но не отражают в полной мере изучаемое явление.
Реальные системы являются большими и сложными, и их функционирование всегда является многокритериальным. Математическая модель принятия решений при многих критериях может быть представлена в виде (X,f(x)), где Х- множество возможных исходов принятия решения, то есть множество имеющихся у лица, принимающего решение (ЛПР) альтернатив выбора. Качество каждого исхода х Є X оценивается с помощью векТОрНОГО Критерия f(x) = (fi(x), /2(2:), ..., fm(x)), ГДЄ fi(x)
- оценка исхода х по г'-му критерию. При наличии многих критериев решение зачастую принадлежит области компромисса, когда улучшение решения по одному критерию приводит к ухудшению по другому. Здесь возникает проблема сравнения двух векторов, что является нетривиальной задачей. В настоящее время существует целая область математической теории управления - теория многокритериальной оптимизации, в которой исследуются задачи такого типа. Главные результаты этого направления изложены в [54, 60].
Основной сложностью при анализе задач многокритериальной оптимизации является задача несравнимости двух векторов. Естественное отношение предпочтения на множестве векторов не является линейным порядком. Существуют неравные и несравнимые векторы. Понятие век-
торного оптимума не определено, что представляет собой форму неопределенности - ценностную неопределенность [64, с. 98]. Поэтому, в первую очередь при решении многокритериальных задач необходимо указать принцип оптимальности, объясняющий, в каком смысле одно решение лучше другого. Один из фундаментальных подходов к решению данной проблемы - принцип Парето. Его активное использование относится к началу XX века, после публикации монографии Вильфредо Парето "Руководство по политической экономии".
Парето оптимальный исход, или эффективный исход обладает тем свойством, что он не может быть улучшен ни по одному из критериев без ухудшения по какому-нибудь другому критерию. Если при этом допускается равенство, то исход называют оптимальным по Слейтеру, или слабоэффективным.
Существует ряд недостатков, котрые необходимо учитывать при использовании оптимальных по Слейтеру и Парето решений. Так в [36, с. 158] указаны следующие:
Множество оптимальных по Слейтеру и Парето исходов содержит, как правило, бесконечное множество решений. Для выбора конкретного решения следует привлечь дополнительные соображения, не участвующие в формулировки оптимальности по Парето.
Существуют задачи, где следует выбрать не одно, а несколько наилучших решений или упорядочить их по предпочтительности. А два оптимальных по Парето решения являются несравнимыми.
3)В определении оптимальности по Парето не учитывается, сколько строгих неравенств выполняется при сравнении двух исходов.
Тем не менее, эти понятия играют важную роль в теории многокритериальной оптимизации и в практике их использования. Согласно [64, с.59]: "При любом разумном понимании оптимальности для многокритериальных задач принятия решений оптимальный исход обязательно должен быть Парето оптимальным". Несмотря на то, что в общем слу-
чае, множество эффективных исходов бесконечное, тем не менее, оно значительно "уже"множества всех возможных исходов [36]. На таком "узком"множестве могут выполняться различного рода упрощающие решение факты, которые не имеют место для всего множества возможных альтернатив. Также можно привлечь дополнительную информацию, для обоснования ЛПР выбора единственного решения.
В [64] приведены следующие простейшие способы сужения Парето оптимального множества.
Указание нижних границ критериев. В данном случае привлекается дополнительная информация, в виде набора оценок (71,..., 7т)) гДе 7j - нижняя граница по і- му критерию, fi(x*) > 7*. При увеличении % Парето оптимальное множество сокращается.
Субоптимизация (метод главного критерия) Выделяется один из критериев - главный, а по всем остальным критериям назначаются нижние границы. Оптимальным при этом считается исход, максимизирующий выделенный критерий на множестве исходов, оценки которых по остальным критериям не ниже назначенных. С помощью метода субоптимизации задача многокритериальной оптимизации превращается в скалярную задачу условной оптимизации.
Лексикографическая оптимизация Сначала критерии упорядочивают по относительной важности. Затем на первом шаге отбирают исходы, которые имеют максимальную оценку по важнейшему критерию. Если таких исходов несколько, то среди них отбирают те, которые имеют максимальную оценку по второму по важности критерию, и т.д. При практическом применении данного метода возникают содержательные трудности в установлении полной упорядоченности критериев по их относительной важности. Фактически во внимании принимается только первый - важнейший критерий.
Существуют и другие методы сужения эффективного множества и выбора единственного эффективного решения. Уточнению оптимального
по Парето решения в игровой задаче с векторным выигрышем посвящены работы [51, 101]. Здесь предложено среднеквадратичное равновесие, подход, основанный на нахождении наилучшей, или "идеальной"точки "утопии"в критериальном пространстве. Выявлены свойства такого решения и приведены условия существования и единственности среднекав-дратичного решения в задачах оптимизации.
В [57, с. 161], [60, с.45] приводится метод, где в качестве оптимального исхода предлагается выбрать точку в которой максимальное отклонение оценки f(x) произвольно исхода х от вектора, представляющего собой максимум по каждому критерию минимально
уї - №) . у*і - Ш
max :—і = mm max г— .
1<і<т \у*\ хеХ 1<і<т \у*\
Здесь уї — max/j (я) - вектор максимумов по г-му критерию. Исход х*
всегда слабоэффективный, а если он единственный, то и эффективный.
Другим методом, [57, с. 162] является арбитражная схема, где некоторое исходное решение х подлежит улучшению по некоторому правилу ip(F, f(x0)), где F - множество всех оценок f{x), х Є X. Данное правило должно удовлетворять трем аксиомам:
реализуемости,
индивидуальной рациональности,
независимости от посторонних альтернатив.
Основными методами, с помощью которых можно сузить множество оптимальных решений и, в частности, получить единственное решение, является методы, основанные на скаляризации векторного критерия качества. Таким образом, задача многокритериальной оптимизации сводится к задаче получения сводного показателя, или обобщенного критерия. Для этого необходимо привлечение дополнительной информации о критериях или о свойстве оптимального решения. Принципиальная сложность построения обобщенного критерия заключается в том, что приходится "соотносить"друг с другом критерии, характеризующие объект с разных сторон, например, стоимость и эффективность. Эти критерии имеют различную природу и оценки даются по ним в разных шка-
лах. Также критерии могут быть позитивными, если ЛПР стремится к их увеличению, и негативными, если он стремится к их уменьшению. [64, с.55]. При построении обобщенного критерия необходимо, чтобы все критерии были либо позитивными, либо негативными. Этого можно добиться просто заменой знака. В [71] в примере построения рейтинга коммерческих банков приводится следующий способ нормировки критериев:
max fi(x) - fi(x) Для негативных
fi(x) = —1г- . :——— - (минимизируемых)
^М-^М критериев.
fi{x) - min fi(x) Для позитивных
fr (х) = 1<г<т^ _ (максимизируемых)
i?S/i(")_iS,/i(x) критериев.
После таких преобразований все критерии становятся позитивными, и достигается "сбалансированность"критериев. Наиболее сложную проблему представляет собой случай, когда критерии имеют различную природу и оценки по ним даются в различных шкалах, или критерии имеют качественный характер. В этом случае необходимо произвести арифме-тизацию [71, с.13], что позволяет получить числовые оценки для исходной нечисловой информации. Далее выбирается обобщенный критерий, который позволяет линейно упорядочить все исходы по их обобщенной предпочтительности. Выбор эффективных или слабоэффективных оценок дает целое множество решений, несравнимых друг с другом. Поэтому следует осуществить переход от множества объектов частично упорядоченного, к множеству объектов, ранжировка которых дает линейный порядок, являющийся продолжением исходного частичного порядка. В [71] такой переход осуществляется согласно принципу линеаризации. В качестве синтезирующей функции, в зависимости от характера задачи и используемых частных критериев предлагается использовать:
1) Линейная свертка. Простейший обобщенный критерий , который пользуется наибольшей популярностью.
т т
Q = ^2wifi(x), ^ги* = !,«;< >0 ,г' = l,2,...,m.
г=1 і=\
Здесь Wj - веса, указывающие сравнительную значимость критериев.
В [9] для скаляризации векторного критерия используется система линейных условий предпочтительности групп критериев и вектор приоритетов является центром тяжести множества векторов, удовлетворяющих этой системе. Данный метод применяется к задаче многокритериальной оценке объектов энергетики.
2) Мультипликативная форма синтезирующей функции -
»=i
может быть использована для свертки показателей fi(x),...fm(x), fi(x) Є [0,1]. Мультипликативная синтезирующая функция дает оценку объекта
f(x) = (fi(x),... fm(x)), в целом значение которой не превосходит наихудшей (минимальной) из оценок fi(x),...fm(x), получаемых с точки зрения отдельных критериев.
3) Среднее геометрическое.
л ЦІМ
\ «=1
прибавляет "оптимизма"к мультипликативному критерию, данный обобщенный критерий удовлетворяет неравенствам:
min fi (х)
\
T\fi(x) < max fi(x).
АХ m
»=1
Также можно индуцировать различные обобщенные критерии, применяя различные строго монотонные преобразования у =
тическое Q — ~Ylfi{x)> т0 применение отображения у = ln(/j) дает т t=i
(
m \ m
Y[ fi(x) I , использование же степенной
(
ТП \ m
Yj ft(X) ) ИЗ
этого степенного среднего при Л = 1 получается исходное среднее арифметическое, а при Л —> О - среднее геометрическое. Таким образом, задание параметра Л можно охарактеризовать, как неопределенность способа выбора обобщенного критерия, возникающего вследствие дефицита информации. Все вышеуказанное легко переносится на случай линейной свертки. Таким образом, для построения обобщенного критерия необходимо указать дополнительную информацию о критериях, которая определяет обобщенный критерий с точностью до эквивалентности [64, с.78], либо применить принцип рандомизации [71], позволяющий моделировать дефицит информации. В [28] дефицит информации о значимости показателей моделируется с помощью случайного вектора весовых коэффициентов, равномерно распределенного на дискретном подмножестве.
Для случая двухкритериальной задачи в [64] обобщенный критерий с точностью до эквивалентности определяется с помощью карты безразличии . Соответственно чтобы построить карту безразличии требуется следующая дополнительная информация: чему равна уступка по одному критерию, которая компенсируется прибавкой единицы по другому. Если задана карта безразличии, то из множества Парето-оптимальных оценок, выбирается оценка, принадлежащая более высокой кривой безразличия. Данное отношение предпочтения является отношением линейного квазипорядка [64, с.90], и следовательно, определяет обобщенный критерий. Этот метод применен к задаче исследования потребительских предпочтений. [64, с.93]
Согласно [71, с. 12] при построении обобщенного критерия можно выделить три этапа:
задание отдельных показателей (частных критериев);
выбор синтезирующей функции;
определение весовых коэффициентов.
Для выбора весовых коэффициентов необходимо привлекать дополнительную информацию об относительной важности критериев и об отношении предпочтения ЛПР. Общий подход к решению многокритериальных задач при наличии количественной информации об относительной важности критериев разработан в [54]. Данная информация используется для сужения множества Парето.
Многие из существенных подходов к решению многокритериальных задач используют именно информацию в виде коэффициентов относительной важности. В зависимости от типа, характера и объема имеющейся в наличии дополнительной информации используют тот или иной метод принятия решений или их комбинацию. К настоящему времени таких методов, схем и подходов поиска компромисса насчитывается не один десяток.
Один из известных методов - метод анализа иерархий (МАИ), разработанный американским ученым Томасом Саати [65]. Данный метод предполагает декомпозицию сложной проблемы на серию более простых задач, каждая из которых допускает попарное сравнение. В результате метод позволяет определить приоритеты для каждой цели и выбрать лучшее решение, которое учитывает как количественные, так и качественные критерии на основе линейной свертки. В соответствии с МАИ экспертами формируется матрица парных сравнений, а весовой вектор вычисляется как собственный вектор этой матрицы, отвечающий максимальному собственному значению. Использование МАИ позволяет выявить причины, влияющие на выбор, имеет теоретическое обоснование и получившее мировое признание программное обеспечение. Применение этого метода для игровых задач с векторным выигрышем продемонстрировано в [12, 13, 14, 15, 20, 87, 88].
Недостатки МАИ указаны в [55], в частности, матрица парных сравнений может оказаться несовместной. Кроме того, применение линейной свертки критериев требует ограничительных предположений. В связи с этим предлагается использовать нелинейную свертку в виде функции минимума, участвующую в теореме Ю.Б. Гермейера [29].
В большинстве методов, использующих информацию об относительной важности критериев, коэффициенты должны назначаться эксперта-
ми. В МАИ эксперты производят попарные сравнения. В вышеупомянутом методе из [9], использующем линейную свертку, предпочтительность для групп критериев тоже устанавливается экспертами.
Однако, как правило, эксперт вообще не имеет никакого представления о том методе, в котором будут использоваться назначенные ими коэффициенты. Таким образом, как отмечается в [54, 11], одни специалисты назначают коэффициенты относительной важности критериев, затем другие специалисты применяют тот или иной метод, а ЛПР, несущее ответственность за принятое решение, является некой третьей стороной.
Существуют различные примеры приложения теории многокритериальных задач. Например, рассматриваются такие задачи, как выбор места работы [64, с.62], оптимизация производственнорго процесса [64, с.67], исследование потребительских предпочтений [64, с.93]. В [57, с. 164] исследуется задача развития экологически замкнутого региона. Пример построения рейтингов коммерческих банков рассматривается в [71]. Математические модели конкуренции для двух однотипных экономик, как динамическая многокритериальная задача исследуется в [36]. В рамках данных моделей каждому принимаемому решению отвечает единственное значение каждого векторного критерия. Однако в реальных условиях это требование часто не выполняется.
Вторая особенность задачи принятия решений - это наличие неопределенности. Социально-экономические системы являются открытыми и на них оказывают воздействия возмущения со стороны внешней среды. Таким образом, в задаче присутствуют неконтролируемые факторы, влияющие на ее исход, которыми ЛПР не распоряжается. Очевидно, что ЛПР важно иметь некоторую информацию о значениях неконтролируемых факторов. Исходя из различных причин появления неопределенностей, их можно условно разделить на следующие типы [34, с. 73]:
неопределенности, появившиеся за счет действия со стороны лиц, имеющих свои цели, но не являющимися ЛПР;
неопределенности, отражающие нечеткость знания ЛПР своих целей;
неопределенности, появляющиеся из-за недостаточной изученности процессов или величин;
неопределенности, возникающие в процессе сбора, переработки и передачи информации;
особые виды неопределенностей, возникающие при управлении механическими системами.
Такая ситуация встречается в подавляющем большинстве областей техники, экономики, экологии и социальных науках. При этом наличие неопределенности приводит к тому, что нельзя однозначно определить понятие решения многокритериальной задачи, а можно лишь указать "разумные"решения согласно выбранного принципа оптимальности.
Появление основ теории принятия решений при неопределенности можно отнести к началу второй половины прошлого века. В это время были предложены принцип максиминной полезности (принцип Вальда)[97], принцип минмаксного сожаления (принцип Сэвиджа) [90], принцип пессимизма - оптимизма (принцип Гурвица)[83], принцип недостаточного основания [72]. Каждый из этих признаков формирует критерий, использование которого приводит к однозначному ответу. Например, в [10, 11] принцип гарантированного результата (максиминной полезности) применяется к задаче выбора проекта в условиях неопределенности. Однако, все эти методы созданы для однокритериальных задач. Исследование многокритериальных задач ведется в рамках различных модификаций принципа гарантированного результата. Исследования статического варианта таких задач ведутся в Италии [78, 79], Японии [93, 94, 95] и США [76, 86]. Динамические многокритериальные задачи в позиционных стратегиях исследуются в России В.И.Жуковским [32, 33, 34, 36, 101], В.А. Матвеевым [45, 50], В.С.Молоствовым [35], Г.И.Житомирским [31]. Результаты исследования динамических многокритериальных задач с программными управлениями и неопределенностями, а также, соответствующих им многошаговых задач представлены в [66, 67].
Задача принятия решений в условиях неопределенности связана с теорией игр. Теория игр - это раздел математики, в котором исследу-
ются математические модели принятия решений в условиях конфликта, т.е. в условиях столкновения сторон, каждая из которых стремится воздействовать на развитие ситуации в своих собственных интересах. Так в [52] двухуровневая игра применяется для выбора оптимального набора инструментов торговой политики в модели третьего рынка.
Сознательная деятельность других лиц, отстаивающих свои интересы является источником неопределенности. Поэтому, задачу принятия решений в условиях неопределенности можно трактовать как конфликтную ситуацию для двух игроков, одним из которых является ЛПР, а в качестве второго игрока выступает гипотетический индивид, формирующий неопределенность. При этом, если придерживаться принципа гарантированного результата, то следует считать, что второй игрок действует так, чтобы максимально препятствовать ЛПР в достижении его целей. Изложение основных результатов теории игр можно найти в [25, 26, 47, 58, 59, 77, 80, 82].
Целью работы является разработка теоретических основ принципа оптимальности по конусу, применение полученных результатов к исследованию многокритериальных задач, гарантированных решений в динамических многокритериальных задачах с программными и позиционными управлениями и неопределенностями, причем полагается, что о неопределенностях известна лишь область возможных значений.
Объектом исследования являются динамические многокритериальные задачи принятия решений в условиях неопределенности и сед-ловые точки в игровых задачах с векторными выигрышами.
Предметом исследования - принятие решений в динамических многокритериальных задачах при неопределенности на основе принципа оптимальности по конусу, равновесия в игровых задачах с векторным выигрышем для различных принципов оптимальности.
Проблема заключается в способе формализации и исследовании свойств решений динамической многокритериальной задачи при
неопределенности и в поиске методов построения седловых точек, реализующих такие решения, определении векторной седловои точки относительно выбранного принципа оптимальности
В основу исследования положена следующая гипотеза: основываясь на результатах из теории многокритериальных задач, теории игр и оптимального управления, для динамических задач при неопределенности можно определить понятие оптимального решения согласно принципа оптимальности по конусу, предложить способ его нахождения и получить условия его существования.
Для реализации поставленной цели и проверки сформулированной гипотезы потребовалось решить следующие задачи:
выявить свойства оптимальных по конусу решений многокритериальной задачи, установить их связь с известными принципами оптимальности;
получить достаточные условия существования таких решений;
предложить способ уточнения оптимального по многогранному конусу решения многокритериальной задачи;
рассмотреть применение метода анализа иерархий в игровой задаче с векторными выигрышами;
формализовать понятия гарантированных по конусу решений для динамической многокритериальной задачи при неопределенности с программными управлениями и неопределенностями;
найти методы построения гарантированных по конусу решений, используя аппарат принципа максимума Понтрягина;
рассмотреть приложения к конкретным задачам.
Методологическую основу работы составляют методы и подходы теории многокритериальных задач, теории игр, выпуклого анализа, теории матриц, теории дифференциальных уравнений и теории оптимального управления.
Научная новизна. В работе рассмотрен новый подход к исследованию динамических многокритериальных задач при неопределенности и выявлены его свойства. Для многокритериальной задачи при неопределенности определена оптимальность по произвольному выпуклому конусу. Для оптимального по многогранному конусу решения предложен способ уточнения решения. Рассмотрено применение метода анализа иерархий к игровой задаче с векторными выигрышами и определено понятие конусного равновесия.
Основные положения, выносимые на защиту:
исследованы свойства оптимального по конусу решения многокритериальной задачи, выявлены условия существования, получены достаточные условия оптимальности по конусу;
предложен способ уточнения максимального по конусу решения многокритериальной задачи;
для игровой задачи с векторными выигрышами формализовано понятие равновесия с применением метода анализа иерархий, сформулированы условия существования таких равновесий.
формализовано гарантированное по конусу решение динамической многокритериальной задачи при неопределенности;
найдены условия существования гарантированного по конусу решения динамических многокритериальных задач при неопределенности;
сформулированы необходимые условия существования С- седловых точек в форме принципа максимума Понтрягина;
найдены коэффициентные условия существования и явный вид гарантированного по конусу решения динамической многокритериальной позиционной задачи при неопределенности.
Апробация. Результаты диссертации докладывались на научно - методических семинарах кафедры высшей математики Псковского политехнического института и кафедры математики и информатики Псковского Вольного института, на XIV и XIX международной научно-методической конференции "Математика в ВУЗе"(Великие Луки, 2002, Псков,2006),на X международной конференции "Математика, компьютер, образование"(Пущино, 2003), на II научно-практической конференции "Потенциал развития Псковской области в экономике, управлении и решении социальных проблем"(Псков 2004), на международной конференции, посвященной 75 - летию со дня рождения В.И. Зубова "Устойчивость и процессы управления"(Санкт-Петербург 2005).
Перейдем к краткому изложению содержания диссертации. Диссертация состоит из трех глав, разбитых на 12 параграфов.
В первой главе ( 1-5) сформулировано понятие оптимального по конусу решения для многокритериальной задачи. Именно, в 1
рассматриваются бинарные отношения и вводится отношение предпочтения по конусу, как отношение порядка. Рассматриваются свойства и типы бинарных отношений и связь отношения конусного предпочтения с другими отношениями порядка. В 2 рассматривается многокритериальная задача и известные принципы оптимальности для выбора решения -оптимальность по Слейтеру, по Парето, по Борвейну, по Джоффриону и Л-оптимальность. В 3 формулируется понятие оптимального по конусу решения, рассматриваются свойства и частные случаи данного решения, его связь с известными принципами оптимальности. Рассматривается пример нахождения максимального по конусу решения для трехкрите-риальной задачи. Необходимым и достаточным условиям существования оптимального по конусу решения посвящен 4. Утверждения из 4 используются в следующем параграфе. В 5 приводится способ уточнения максимального по многогранному конусу решения.
Содержание второй главы (6-7) составляет рассмотрение игровой задачи с векторными выигрышами и применение метода анализа иерархии для нахождения равновесия в этой задаче. В 6 приводится поста-
новка задачи, определение равновесия, и алгоритм его нахождения. Приводится пример нахождения ситуации равновесия в игровой задачи двух лиц с трехкомпонентными функциями выигрыша. Применению метода анализа иерархии посвящен 7. Сначала представлено описание МАИ, потом определяется понятие игры с векторным выигрышем и иерархией целей. Далее приводится решение в такой игре. Показывается связь равновесия в игре с векторными выигрышами и иерархией целей с равновесием Нэша-Парето, приводится пример нахождения такого решения. Наличие у каждого игрока "своей"иерархии целей интерпретируется, как неопределенность и формулируется игровая задача с векторными выигрышами, иерархией целей и неполной информацией, которая сводится к статической игре с неполной информацией. Рассматривается модельный пример.
Третья глава посвящена многокритериальным задачам при неопределенности. В 8 рассматривается статический вариант задачи, и определяется понятие гарантированного решения. Рассматриваются различные виды векторных гарантий, определенных на основе понятий минимумов по Слейтеру, Парето, Борвейну, Джоффриону и А-минимума, определения которых приводятся в 2. Затем они обобщаются на случай доминирования по выпуклому конусу. Здесь формализуется гарантированное по конусу решение многокритериальной задачи при неопределенности и С - седловые точки, реализующие эти решения. Эти результаты используются в 9, для определения решения непрерывной динамической многокритериальной задачи при неопределенности с программными управлениями и программными неопределенностями. В 10 предложен способ нахождения С-седловых точек, основанный на применении аппарата принципа максимума Понтрягина. Утверждения и алгоритмы этого параграфа применяются для нахождения седловых точек в конкретных задачах. Именно, в 11 рассмотрена модель освоения вводимых производственных мощностей. В следующем 12 рассмотрен более общий случай - динамическая многокритериальная позиционная задачи при неопределенности Для нее определяются основные составляющие элементы задачи, описывается процесс принятия решения и приводится экономическая интерпретация. Для этой задачи, используя метод динамического
программирования, найдены коэффициентные условия существования и явный вид гарантированного по конусу решения динамической многокритериальной позиционной задачи при неопределенности.
Предпочтение по конусу
Рассмотрим многокритериальную задачу: (X, f(x)). (2.1) где ICR"- множество решений х Є X. Считаем, что решение отождествляется с точкой х из множества всех допустимых решений X. Выбранное решение оценивается набором из TV функций f(x) = (fi(x)J2{x),...,fN(x)) или векторным критерием. Вектор-функция f(x): X —у HN представляет собой набор локальных критериев ЛПР. Множество всех значений векторного выигрыша для ЛПР когда х "пробегает"все множество X называется область достижимости многокритериальной задачи (2.1) и обозначается F(X) = {yeRN:y = f(x),xeX}.
На содержательном уровне, цель ЛПР состоит в выборе такого х Є X, который доставляет возможно большие значения компонентам, соответствующим максимизируемым локальным критериям, и возможно меньшие значения для минимизируемых критериев вектор-функции f(x). Обычно задачу преобразовывают к такому виду, чтобы все локальные критерии либо максимизировались, либо минимизировались.
При принятии решений о выборе наилучшей альтернативы прежде всего необходимо выбрать принцип оптимальности, указывающий, в каком смысле выбранное ЛПР решение, лучше остальных. Таким образом, предпочтения ЛПР, оказывающие влияние на процесс выбора, выражены с помощью векторного критерия и отношения предпочтения. Если из двух решений х , х" Є X ЛПР отдает предпочтение первому из них, то пишут х УХ х".
Знак Ух обозначает отношение предпочтения на множестве всевозможных решений. Это отношение естественным образом индуцирует отношение предпочтения на области достижимости F(X): f(x )yFf(x") & х Ухх".
Не из всякой пары решений ЛПР может сделать окончательный выбор. Могут существовать такие пары, что ЛПР не в состоянии отдать предпочтения выбор не одного, а целого множества возможных решений на X - множества выбираемых решений X Є X [54, с. 15]. Наряду с выбираемым решением удобно ввести множество выбираемых оценок
Т = F(X) = {уЄ F(X): у = /(я), х Є X].
Для задач многокритериального выбора предъявляются требования, которые можно сформулировать с помощью следующих аксиом.
Аксиома 1 [54, с.24](исключение доминируемых векторов) Если для некоторой пары векторов f(x ) и f(x") Є F(X) выполнено отношение f(x ) yF f(x"), mo f(x") І Т.
Аксиома 2 [54, с.27] (продолжение отношения предпочтения) Существует продолжение У на все критериальное пространство RN отношения Ур, причем это продолжение У является иррефлексивным и транзитивным отношением.
Аксиома 3 [54, с.28] (согласование критериев с отношением предпочтения) Каждый из критериев /1,/2,---,/ согласован с отношением предпочтения У.
Аксиома 4 [54, с.42] (инвариантность отношения предпочтения) Отношение предпочтения У является инвариантным относительно линейного положительного преобразования.
Рассмотрим следующие известные принципы оптимальности [60], [32]. Определение 2.1 Решение задачи (2.1) xs Є X называется максимальным по Слейтеру [60, с.32], если не существует такого решения х Є X, что fi{x) fi{xs), і є N.
В векторной записи несовместность данной системы неравенств обозначается f(x) fS{x) или, согласно (1.1) f(x) 5 fS(x) для Va: Є X. Значение векторного критерия f(xs) = (f\(xs),..., /JV(xS)) называется максимальным по Слейтеру или слабоэффективным.
Через Xs обозначим множество всех максимальных по Слейтеру решений в задаче (2.1 ). Введем множество F(XS) = (J /(х) xeXs - множество максимальных по Слейтеру оценок. Приведем геометрическую интерпретацию максимального по Слейтеру решения для двухкри-териальной задачи. Обозначим: Ri {/ = (/1,/2) І/І 0,t = 1,2, },
Согласно определению 2.1, ни одна из точек множества F(X) не должна попасть внутрь угла М.; угол М представляет собой сдвиг положительного ортранта R на вектор f(xs), то есть М f(xs) + R . Векторный критерий f(xs) = (/1(2: ),/2( 5)) является оптимальным по Слейтеру. В случае оптимальности по Слейтеру отдельные точки множества F(X) могут находится на сторонах угла М. (например, точка В\ на рис. 3), но внутри угла оказаться не могут.
Оптимальное по конусу решение многокритериальной задачи
Приведем свойства максимальных и минимальных по Слейтеру решений в многокритериальной задаче [60].
Утверждение 4.1 (достаточные условия существования максимального по Слейтеру решения [60, с.71]) Пусть х Є X доставляет, максимум N N функции 2 &ifi{x), причем постоянные Х{ 0, і — 1,..., N, аг- = 1. Тогда решение х является максимальным по Слейтеру в задаче (2.1). Если решение х Є X такое, что N N У2 PifiM = min V А/і W, i=l і=1 N где постоянные / 0, і = 1,2,..., N, YlA 1- Тогда решение x i=i является минимальным по Слейтеру в задаче (2.1).
Утверждение 4.2 (необходимое и достаточное условие максимальности по Слейтеру [60, с. 105] ) Пусть в задаче (2.1) множество X выпукло, а функции fi(x), г Є N вогнуты по х на этом множестве. Тогда для того, чтобы решение х Є X было максимальным по Слейтеру, необходимо и достаточно, чтобы существовал набор чисел с г- 0, г = N 1,2,..., iV, ]П ( = 1, такой, что i=i ;./( ) = тах]Г / (а;). г=і х t=i
Для того, чтобы решение х Є X ,было минимальным по Слейтеру, необходимо и достаточно, чтобы множество X было выпуклым, функции /І(я), г Є N, выпуклы по ж на множестве X, а решение ж Є X такое, что N N y\fcfi{x ) = min У] (3ifi(x), і=1 »=1 где постоянные / 0, г = 1, 2,..., АГ, ][) / = 1. i=i
Пусть задан многогранный конус К = {/: Л/ 0}, где А - матрица размерности т х N с положительными элементами ац 0, f — (/ь І2, /N)- Конус К - это множество векторов, образующих острые углы с векторами, координаты которых - строки матрицы А. Конус К , образующие вектора которого - строки матрицы А является полярным конусом для конуса К [8, с.52]. Рассмотрим матрицу А с элементами а\; — - -—, строки которой, нормализованные строки матрицы А. L aij Рассмотрим их линейную комбинацию ак f = «! (4-1) г=1 m где ot.{ О, і = 1,2,..., m, такие, что 0 = 1, а- = (а , а-2,..., а ш) - г-я строка матрицы А . Вектор ак = af, о; а]у - вектор такой, что J2 af — 1) принадлежащий конусу /С . i=i Лемма 4.1 (достаточные условия максимального по многогранному ко N нусу решения) Пусть х Є X доставляет максимум функции affj(x), i-i где а определены в (4.1). Гог а решение х является максимальным по конусу К в задаче (3.1).
Доказательство. Согласно определению оптимальности по конусу, решение х будет оптимальным по конусу К если не существует решения х такого, что f{x) — f{x ) Є К. Так как конус К = {/: Af 0}, то это равносильно тому, что несовместна система неравенств: A(f(x) — f(x )) 0 или Af (х) Af(x ). Покомпонентно это означает, что N N Y Q ijfj(x) ]Г a,ijfj(x ). Из последнего условия следует, что решение 3=1 3=1 х максимально по Слейтеру в задаче с векторным критерием Af{x) или А - максимально. Таким образом, достаточные условия существования ііГ-максимального решения, эквивалентны достаточным условиям существования максимального по Слейтеру решения в задаче с векторным критерием Af (х). То есть если решение х доставляет максимум функ т N т ции ] Ylaiaijf{x)i аг — О, Y1 аг — 1 тогда оно является макси-мальным по Слейтеру в задаче с векторным критерием Af(x). Если мы РОССМчОКЛН ГОСУЛА .- .".:І-:!,::ІАЯ нормализуем строки матрицы А, то получим тот же конус К, и свертку векторного критерия /(ж) с коэффициентами, определенными в (4.1). Замечание 4.1 Этот результат можно обобщить на случай произ N вольного выпуклого конуса С Є R : Пусть х = argmax affj(x), где хЄХ ._! J oR - компоненты вектора cf — (af,..., aN) Є С , и С .- полярный конус для конуса С. Тогда решение х является оптимальным по конусу С в задаче (3.1). Утверждение 4.3 (необходимое и достаточное условие максимальности по к(жусу)Пусть в задаче (2.1) множество X выпукло, а функции fi(x), і Є N вогнуты по х на этом множестве. Конус доминирования С - выпуклый, острый и С D R . Тогда для того, чтобы решение х Є X было максимальным по конусу С, необходимо и достаточно, N чтобы существовал вектор а Є С , ]Г а = 1 такой, что
Пример: Биматричная игра с векторными выигрышами
В этой игре два игрока (N = 2). Первый игрок выбирает строки (первая, вторая строка), а второй игрок - столбцы (первый, второй столбец). Каждая клетка таблицы соответствует ситуации игры. В клетках представлены векторы выигрышей: в верхнем левом углу выигрыш первого игрока, в нижнем правом углу - второго игрока. Векторы выигрышей (hi Є {1)2}) имеет размерность 1\ и bli(i,j {1,2}) имеет размерность /2- Смешанные стратегии - это векторы, составляющие фундаментальный симплекс в евклидовом пространстве R2. Множество смешанных стратегий первого (второго) игрока будем обозначать X = {х = (а, 1 - а) 10 а 1} CR2. (6.3) (У = {у = (/М-0)О 0 1}) CR2.
Отметим, что множество смешанных стратегий первого (второго) игрока является однопараметрическим. Стандартным образом определяются выигрыши игроков при использовании смешанных стратегий, как математическое ожидание, вычисленное для каждой компоненты векторного выигрыша отдельно. По аналогии с [25, с. 176],[58] обозначим такую игру Г(А,В), где А(В) - матрица векторных выигрышей первого (второго) игрока. Приведем метод нахождения всех равновесных по Нэшу-Парето ситуаций в игре Г (А, В). Предлагаемый метод обобщает способ нахождения равновесия по Нэшу в биматричной игре, представленный в [25, с.179-181]; [26, с.145-147]; [59, с.78-89]. Этот метод основан на нахождении многозначной функции наилучшей стратегии - реакции игрока на смешанную стратегию другого игрока. Тогда пересечение этих многозначных функций для первого и второго игроков (бинарных отношений на пространстве параметров) образует все ситуации векторного равновесия. В данном случае наилучший ответ понимается относительно паретовского отношения предпочтения.
Пример 6.1 На рис. 9 представлено пространство параметров игры Г (А, В), где векторная функция выигрыша является трехкомпонентной (її — І2 = 3). Каждая точка (а,/3) квадрата [0,1] х [0,1] соответствует ситуации в 2 х 2 биматричной игре с векторными выигрышами. Это ситуация (ж, у) — ((а; 1 — а); (/?; 1 — /3)). Отметим, что такое представление биективно.
Учитывая обозначения стратегий игроков (6.3), обозначим многозначную функцию наилучшей реакции первого игрока а = а(/3) относительно паретовского предпочтения. Область определения и область значения этой функции есть отрезок [0,1]. Эта функция принимает значения is а(Р) если ((3(ап - а12) + аи) (Р(а21 - а22) + а22); если (/3(а21 - а22) + а22) (/3(ап - а12) + а12); [0,1], если векторы (/?(ап - а12) + а12) и (/?(а21 - а22) + а22) несравнимы. (6.4) Так в данном примере эта функция [0;1], если /З Е [0; 1/3] ; 0, если $ Е [1/3; 1].
Эта многозначная функция представлена на рисунке 10а) . Аналогично определяется многозначная функция наилучшей реакции второго игрока относительно паретовского предпочтения (3 = /3(a). Область определения и область значения этой функции также отрезок [0,1]. Эта функция принимает значения /3(a) = 1, если (а(Ьп - Ьп) + Ъ12) (а(Ь21-Ь22) + Ь22); 0, если (а(Ь21 - Ь22) + Ъ22) (a(bn-bi2) + b12); [0,1], если векторы (а(Ъп - Ъи) + Ь12)и (а(Ь21 - Ь22) + Ь22) несравнимы. (6.5) Так в примере 6.1 /%) [0; 1], если а Е [0; 1/3) ; 0, если а Е [1/3; 1].
Многозначные функции, представленные в (6.4) и (6.5), порождают многозначное отображение множества всех ситуаций игры в себя по правилу (а, /3) = (а(/3);/3(а;)). Неподвижные точки этого отображения и только они являются равновесием Нэша - Парето в игре Т(А, В). Найдем значения параметров а [0; 1] и (З Є [0; 1], соответствующие ситуациям такого равновесия. Множество всех пар таких параметров совпадает с пересечением многозначных отображений (бинарных отношений) из (6.4) и (6.5). Учитывая их обозначения, получаем Р = {( т-,Р) Є [0;l]2}f{(«;/5W) Є [0;1]2}. Графически это соответствует пересечению графиков, представленных на рис. 10а) и 106). Итак, все пары параметров, соответствующие равновесию Нэша - Парето в игре Г (А, В) приведены на рис.Юв). Отметим, что пары параметров "северной"и "восточной"границы квадрата не представляют равновесия Нэша
Р = {(а; № = [0; 1/3)2 U (0 х [0; 1]) U ([0; 1] х 0).
Итак, на рис.Юв), представлены в параметрической форме все равновесные по Нэшу-Парето ситуации в рассмотренной игре. В задаче векторной оптимизации, как правило, существует бесконечное множество максимальных по Парето решений. Это отрицательное свойство векторных онтимумов наследует и игровая задача с векторными выигрышами. Так в приведенном выше примере множество паретовских равновесных ситуаций бесконечно. Для сокращения этого множества или даже выбора единственного решения требуется привлечение дополнительной информации. Для задачи векторной оптимизации один из возможных подходов состоит в создании иерархии целей и последовательном решении серии более простых задач. Рассмотрим аналогичный подход к игровой задаче с векторными выигрышами.
Гарантированное по конусу решение многокритериальной задачи при неопределенности
Используя в определении 8.2 индексы К = S,P,B,G,A2nL = S, Р, В, G, А\ , получим 25 различных KL - седловых точек, реализующих эти решения. Эти случаи можно объединить, используя понятие оптимальности по конусу, аналогично задаче (3.1). Рассмотрим многокритериальную задачу ТсиС1 = {ХЛЦх,г\СъС2). (8.4)
Здесь X, Z, /(ж, z) - определены аналогично задаче Г (8.1), а Сі, С2 - выпуклые конусы. Качество выбранной альтернативы х Є X при конкретном значении неопределенности z Є Z оценивается с помощью конуса С\ как это определено 3.1. Аналогично задаче Г для задачи TQ рассмотрим две вспомогательные задачи: TCl(z = zt) = (XJ(x1zt)1Ci)1 (8.5) TC2(x = x ) = (ZJ(x\z),C2). (8.6) которые получаем из задачи Гсьс2 ПРИ фиксированных z = z Є Z и x — x Є X соответственно. Определим понятия максимального по конусу решения, минимальной по конусу неопределенности и векторной гарантии по конусу согласно замечаниям 3.1 и 3.2.
Определение 8.3 Альтернативах01 называется максимальной по конусу С\ в задаче Tc\(z = z ) если для конуса С\ D R и при любых хЄХ / )-/( , ) 1 Последнее условие согласно (1.7)можно записать: fi{x,z ) id f{xC\z ). Определение 8.4 Неопределенность ZQ2 называется минимальной по конусу Сі в задаче Тс2(х — х ) если для конуса Ci D R и для любых zeZ fi(x\z)-f{x\zC2)iC,. Последнее условие согласно (1.6)можно записать: f{x ,z) с2 f(x\zCi).
Аналогично задаче Г определим понятие гарантированного решения для задачи Тсис2- Будем считать, что Ci, ( - выпуклые конусы, с непустой топологической внутренностью, причем такие, что Сі Э В, С2 Э R?. (8.7) Тогда,
Определение 8.5 Пару (а 1,/ ) Є X х R назовем Сі- решением, гарантированным по Сі для задачи Гс1гс2 г е С\,Сі удовлетворяют условию (8.7), и, если существует такая неопределенность zc2 Є 2, что 1 альтернатива xCl является максимальной по конусу С] в задаче TCl{z = zC2), 2 неопределенность ZQ2 является минимальной по конусу Сі для задачи TQ2 (х — xCl), 3 fd = f(xc\zc2)= {h(xc\zCi),h(xc\ZC2),...JN(XC\ZC2)).
Пару {xc\ zc2) Є X x Z реализующую Су решение, гарантированное по Сі для задачи Vcx{z = zc2), назовем C\Ci - седловой точкой в задче vCl{z = zC2).
Замечание 8.2 Можно рассмотреть более общий случай, когда в определении 8.5 конусы С\,Сч не обязательно удовлетворяют условию (8.7). Тогда в определении 8.5 в 1 альтернатива xCl должна является оптимальной по конусу С\, а в 2 неопределенность ZQ2 является оптимальной по конусу Сі Обозначим (XC\FQ ) - множество всех С\ - решений, гарантированных по Сг, a (XCl,Zc2) - множество C\Ci - седловых точек в задаче Tcx(z = zc2). Пусть Cl, Cf, Сі, СІ - выпуклые конусы, такие что С\ С Ci, С2 С (72
Тогда связь между Су решениями задачи Tcx(z — zc2), гарантированными по Сі и всеми С\Сі - седловыми точками можно представить следующими схемами: Под многокритериальной непрерывной динамической задачей при неопределенности понимается упорядоченная система Г = W, Z, {Ji{U,Z)}ieNiCh C2),N = {1,2,..., JV}. (9.1)
Основные обозначения из [32]. Здесь функционирование управляемой динамической системой рассматривается на отрезке времени [to,tf], где О to $ - фиксированные моменты начала и и окончания процесса. Текущее состояние системы Е в каждый момент времени t характеризуется фазовым вектором х = (хі,...хп) Є Rn. Задано начальное состояние системы Е, именно a:(to) = XQ. Изменение фазового вектора описывается векторным дифференциальным уравнением х = (t,,u,z) (9.2) с начальными условиями x(t0) = XQ. (9.3)
Вектор-функция ip(t,x,u,z) описывает внутреннее устройство системы S и определена для любых значений векторных переменных х — (жі,...жп) Є Rn, и Є Р С Rr, z G Q С R1, где множества P и Q - заданы априори, компакты в Rr и R1 соответственно.
Для каждого конкретного момента времени t Є [to, $], ЛПР выбирает некоторое управляющее воздействие u(t) - точку из множества Р, которое называется областью управления. Одновременно, независимо от действия ЛПР, реализуется неопределенный фактор - точка из множества Q - области значений неопределенности.
Управление U, которым распоряжается ЛПР будем отождествлять с функцией u(t), определенной на интервале t Є [to,$] и со значениями в множестве Р С Rr. Этот факт обозначаем U -i- u(t). Множество всех управлений обозначим U.
