Содержание к диссертации
Введение
Глава 1. Определение значения кратного векторного минимакса .. 26
1.1. Задача поэтапного принятия решений в условиях неопределенности. Постановка задачи 26
1.2. Необходимые сведения о векторной отимизации 28
1.3. Задачи векторной оптимизации с неопределенностью 36
1.4. Задачи многоэтапного принятия решений в условиях неопределенности 45
1.5. Определение значения кратного векторного минимакса 48
Глава 2. Параметризация значения кратного векторного минимакса 55
2.1. Обратная логическая свертка и ее свойства 55
2.2. Обратная логическая свертка в задаче на кратный векторный минимакс 66
Глава 3. Аппроксимационные свойства свертки в задаче на кратный векторный минимакс 79
3.1. Регулярный случай 79
3.2. Нерегулярный случай 91
3.3. Редуцированное пространство 96
3.4. Реализации оптимумов 102
Заключение 105
Список литературы 106
- Необходимые сведения о векторной отимизации
- Задачи многоэтапного принятия решений в условиях неопределенности
- Обратная логическая свертка в задаче на кратный векторный минимакс
- Редуцированное пространство
Введение к работе
В работе исследуется задача поэтапного принятия решений в условиях неопределенности при наличии векторного критерия. Задачи, в которых интерес управляющей стороны не может быть описан одним критерием, являются хорошо известными в исследовании операции. Многокрптерпальность может иметь смысл многогранности человеческих предпочтений нлн выражать.необходимость обеспечения потребностей нескольких пользователей или процессов (так, например, в сетевых задачах возникает необходимость обеспечения линиями связи одновременно нескольких тяготеющих пар в сети). Задача принятия реніснніі и случае, когда некоторые параметры системы не известны либо зависят от внешних факторов, является актуальной. Рассмотрим задачу, в которой оперирующая сторона вынуждена принимать решение в условиях неопределенности и выделим случай, когда условия задачи не ограничивают оперирующую сторону необходимостью едшюкратного принятия решения, но включают в себя возможность при реализации какой-либо серии неопределенных факторов применить так называемое корректирующее управление, которое можно выбрать с учетом реализации неопределенности на данный момент. Таким образом можно сформулировать задачу поэтапного принятия решений в условиях неопределенности с наличием векторного критерия.
Для формализации задачи введем необходимые обозначения: обозначим через wl переменные, относящиеся к неопределенности, через и1 управления оперирующей стороны и будем считать, что при выборе каждого ц* уже станут известны значения it;1,,..,«/, а значении wt+l определятся позже. Здесь t - индекс этапа (время). Векторный критерий обозначим за Ф(щга).
Заметим, что традиционно в исследовании операций для решения задач с неопределенностью применяется принцип гарантированного результата ([13]), иначе говоря, неопределенность представляется в виде действий некоторого противника и нсследу- ется случаи наихудшего для оперирующей стороны варианта реализации стратегии этого противника. Таким образом, для раскрытия неопределенности используется минимаксный, или пессимистический критерии. В случае задачи многоэтапного принятия решений с одним критерием приходим к задаче на кратный мишшакс.
Формально распространяя данный подход на многоэтапную многокритериальную задачу, запишем:
Ф* = Min Max Min Max ... Min Мах Ф(щ w). (1)
Приведем пример интерпретации задачи (1) с Т = 2 в терминах мпогопродукто-кых потоковых сетей, служащих структурной моделью ряда многопользовательских сетевых систем (см. в частности [41]). Рассмотрим задачу учета неопределе и пости при синтезе много продуктовых сетей.
Качество функционирования многопользовательской сетевой системы определяется ыультипотоком — вектором одновременно пропускаемых по сети потоков заявок пользователей (видов продуктов) / — (/ъ >/(?) Для сети с заданной пропускной способностью ребер ставится задача векторной максимизации /. При исследовании живучести сетевой системы учитывается, что в процессе се работы исходный вектор пропускной способности может изменяться — уменьшаться по некоторым компонентам. Обозначим соответствующие неопределенные факторы через го1, w2 и укажем, что ги1, w2 могут иметь смысл отказов н износа оборудования либо еще какого-либо ухудшения функционирования сети.
Пусть у оперирующей стороны между "ударами" и;1, w2 есть возможность применить корректирующее управление г*1, ограничения на которое в общем случае зависят от реализации w1. Здесь и1 имеет смысл вложения в восстановление сети после удара некоторого ресурса.
Тогда гарантированная оценка качества функционирования сети дается гарантн- рованным значением кратного векторного мнпимакса типа (1)
Мій Max Min Мах /. (2)
Целевая функция в (2) для сетевых систем линейна (по крайней мере во внутренней задаче максимизации), причем целевая функция зависит лишь от последнего управления и2 = f. Рассматривая общий случай, приходим к задаче (1). Допустима также зависимость ограничений U1, \\п п от всей предыстории w1 = (w1,... ,wl), ut_I = (к1,..., u*_I), і = 1, 2,... , T, по для упрощения изложения ограничимся данной постановкой, поскольку обобщение проводится автоматически (требует лишь более громоздких обозначений). В дальнейшем для иллюстративных целей будем рассматривать случай линейных ограничений в данной задаче.
Рассмотрим следующий иллюстративный пример: пусть дана сеть ЛВС с двумя ребрами ЛВ, АС. В данной сети заданы тяготеющие пары АВ, АС, ВС. Для сети заданы пропускные способности липни связи р^в н рве- По сети дважды наносятся удары W1, ги2, причем известна их мощность А1, А2. Здесь А1, А2, рлв, Рлс ~ некоторые константы. Между этими ударами у ЛПР есть возможность применить корректирующее управление и, то есть вложить некоторый ресурс в ремонт, на увеличение пропускной способности ребер. Поток обозначим, по тяготеющим парам, /ав-, /лс,
Таким образом, приходим к задаче:
Ф*= Min Max Min МахФ(и;ш), при этом Ф(«;ш) = {/ав,/лс,/вс}-
На удары естественно вводится следующая система ограничений: WAB + w\c = Х\ WAB > 0. WAC > 0.
АВ + ЛС - *?> WAB ^ 0» WAC i> 0-
Введем следующие ограничения на и. Предположим, что па текущий ремонт выделяется некоторая фиксированная сумма, однако в случае существенно большего повреждения одного из ребер эта сумма может быть увеличена (на устранение последствий катастрофы выделяется резервная сумма}. Прнходнм^в простейшем случае к следующей системе ограничении, где 5 - константа;
Из свойств сети вытекают следующие ограничения на вектор мультипотока; ІАВ + І ВС < РЛБ - 11'ЛП + UAB - W2AB, ІАС + he < РЛС - w\c + UAC - W2ACi ІАВ > С ІАС > 0, he > 0.
В качестве примера для рисунков рассмотрен случаи, Л1 — 2, А2 = 3, 5 = 1, рдн = 6, Рас — 7. Дли наглядности і! иллюстративном примере рассмотрен дискретный случай, в котором стратегии выбираются из конечного множества векторов.
Формализация значения кратного векторного минимакса (1) не очевидна. В данной работе предложено использовать определение, являющееся обобщением определения векторного минимакса из [59]. Для удобства описания решений предлагается также использовать множество исулучшаемых оценок. А именно предлагается принять за основное определение кратного векторного минимакса следующее:
Ф'^Мах П U П U {^>0| ^<Ф(«;ш)}. (3)
Отметим, что данное множество оказывается заданным неявно, так что возникает необходимость в его параметризации. В данной работе для параметризации и аппроксимации значения кратного векторного минимакса предложено использовать обратную логическую свертку (ОЛС). Исследованы свойства ОЛС и данной задаче, предложен и обоснован метод аппроксимации значения кратного векторного мпин-макса па основе ОЛС.
Поскольку задача, которой посвящено данное исследование, возникает "па стыке" нескольких тем - многокритериальной оптимизации, теории игр и динамических систем, проведем обзор основных идеи и направлений по этим темам.
Исследование операций и, в частности, теория принятия решений являются сравнительно .молодыми науками, а следовательно, предоставляют большой простор для разработки новых понятий и нового математического аппарата. В связи с развитием вычислительной техники, а, следовательно, широкої! применимостью и востребованностью математических моделей задачи оптимизации являются популярной темой в современной пауке. Многокритериальная оптимизация и динамические задачи не являются исключением. Оба этих направления представлены в большом количестве работ.
Многокритериальная отиимизация.
Проблемы формализации принятия решений человеком не являются еще полностью разработанной теорией ([83]). В качестве одной из основных концепций следует рассматривать задачи принятия решения при нескольких критериях.
Смысл многокритериальной постановки заключается в том, что зачастую лицо, принимающее решение (ЛПР) не в состоянии описать спои предпочтения при помощи одной функции, поскольку это противоречит многогранности, "нелинейности" его интересов. Практически в любой реальной задаче принятия решения, в любой рассматриваемой области, будь то распределение финансирования научных проектов либо проблема покупки нового телевизора, для ныяспеиия предпочтений недостаточно одного критерия (см. [20}, [52], [36], [4]).
Традиционно задача принятия решения при нескольких критериях делится па две стадии или подзадачи. Первой стадией является задача многокритериальной опти- мнзации, под которой под разу меняется построение некоторого эффективного множества, то есть множества решений, каждое из которых в определенном смысле "пе хуже" других. Второй стадиен является задача, которую иногда называют задачей многокритериального выбора, то есть сужения эффективного множества до нескольких точек, а в идеале и до одной точки.
Построение эффективного лтожества. Одним из классических определений "эффективного" множества является определение эффективности по Парето. Эффективное множество (или векторный максимум) по Парето - это множество всех педо-минируемых (максимальных по отношению >) векторов.
Множества Парето является, пожалуй, самым распространенным, хотя и пе единственным определением векторного максимума. Достоинств у использования множества Парето достаточно много. Так, это определение в достаточной степени наглядно, ясно н хорошо известно, а следовательно, исследователь операций не вызовет особого удивления, если представит его для рассмотрения ЛПР.
Однако множество Парето неудобно для аппроксимации, а потому вместо множества Парето часто рассматривается некоторое его расширение - множество Слейтера. Множество Слейтера (или максимум по Слейтсру) - множество всех максимальных по отношению > векторов. Подробно о множествах Парето и Слейтера см. 1.3. Также точки максимума по Слейтсру часто называют полуэффективными. Множество Слейтера в общем случае обладает лучшей структурой, чем множество Парето, потому в данной работе рассматривается почти исключительно именно это определение оптимальности вектора критериев.
Необходимым условиям эффективности по Слейтсру посвящена, например, работа [G2]. Здесь при определенных условиях регулярности задачи векторной оптимизации приведены необходимые п достаточные условия эффективности решения по Слейтсру. Подробнее о численных методах аппроксимации векторного максимума см. ниже.
Как уже отмечалось, построение множеств Парето или Слсіітера - не единственный подход к многокритериальной оптимизации. В большом количестве работ вместо или наряду с множеством Парето используется ранжирование критериев, вводится лексикографическое упорядочивание критериев, функции предпочтении либо весовые коэффициенты для множества критериев. Так, например исследование [11] посвящено многокритериальному ранжированию объектов. Здесь предлагается не рассматривать множество Парето как решение задачи, но применить алгоритмы, основанные на использовании экспертиз, позволяющие экспертам упорядочить критерии по важности. В частности, предлагается использовать схему голосования для ранжирования критериев. В данной работе рассматривается также два варианта свертки критериев и указывается связь видов свертки с методами ранжирования критериев. Ранжирование критериев порой может иметь достаточно сложную структуру. Так, в [16] для облегчения целенаправленного выбора предлагается выделять дерево критериев.
Подробно о различных подходах к построению эффективного множества, а также о вопросах топологических свойств, параметризации и устойчивости множества Парето можно прочесть в монографии [57].
Приведем примеры работ, в которых разрабатываются различные подходы к многокритериальным задачам.
Прежде всего несколько слов об областях человеческой деятельности, в которых успешно применяется многокритериальный подход:
Экология. Одна из моделей, рассматриваемых в [37] - экологическая модель, описывающая функционирование предприятия, загрязняющего окружающую среду. Предполагается, что для минимизации загрязнения предприятие имеет возможность установить очистные сооружения либо иными способами уменьшить загрязнение. Управлениями в подобной модели являются технологические параметры пропзвод- ства, а в качестве независимых критериев логично рассмотреть уменьшение объема загрязнения и сумму средств, затраченных па установку очистных сооружений. Здесь же отметим работу [7-1], посвященную проблеме охраны окружающей среды и водных ресурсов, с применением к решению данной задачи многокритериальных моделей.
Производство. В работе [69] рассматривается интересная многокритериальная модель, описывающая проблемы производства вполне реального устройства - одноступенчатого редуктора. При исследовании данного устройства выяснилось, что у редуктора имеется 14 характеристик, связанных с виброактивностыо. Каждая из этих характеристик может рассматриваться как критерий, который необходимо уменьшить, поэтому задача оптимизации производства редуктора естественно сводится к многокритериальной.
Распределение финансирования. Одной из наиболее распространенных экономических моделей является задача распределения ресурсов между производственными подсистемами (отраслями, регионами, проектами и т.д), а также некоторое ее расширение - задача распределения ресурсов с общественными благами (см. например, [57]). В частности, работа [12] посвящена рассмотрению многокритериальной модели распределения бюджетных средств между научными организациями в условиях недостаточного финансирования. Здесь управлением является распределение средств между проектами, а критериями - степень выполнения проектов. Легко понять, что степень выполнения проекта зависит от его финансирования. В этой работе предлагается не строить множество Парето, но "свертывать" его, пользуясь одной трех стратегии -линейным (пли экономическим) свертыванием, стратегией "подтягивание отстающих" п стратегией "развитие успешных". Интерес модели заключается еще и в том, что процесс финансирования научных проектов рассматривается во времени. Доказано, что при применении всех трех вариантов свертки критериев задача финансирования может быть сведена к задаче линейного программирования, которую можно решать стандартными методами.
Нефтяная промышленность, В работе [15] предложена многокритериальная модель с неопределенностью для планирования геолого-техппчеекпх мероприятий в пефтяноіі промышленности. Здесь для разрешения многокрнтерналышети предлагается использовать ранжирование критериев, а для работы с неопределенностью - теорию нечетких множеств. В данной работе представляется также экспертная система, помогающая ЛПР принимать решения планирования гсолого-техпиче-ских мероприятий.
Менеджмент. Отмстим отдельно сборник |81], в котором приведено большое количество иллюстраций к применению многокритериального подхода в задачах финансового управления.
Развитие города. Наконец, работа [63] представляет многокритериальную задачу планированию функционирования города. В этой монографии обосновывается многокритериальный подход к планированию жизнедеятельности города, рассмотрены диалоговые процедуры принятия решении. В данной работе поднимается и вопрос о многокритериальной оптимизации в условиях неопределенности, в качестве решения предлагается предварительно воспользоваться экономическим свертыванием критериев, а затем использовать мипимакс, который в таком случае получается скалярным.
Аппроксимация. Связь аппроксимации функций и векторной оптимизации см., например в [80].
См. также сборник [82], посвященный вопросам многокритериальной оптимизации в науке и технике.
Построение эффективного лтоэ/сесгпва:
Численные методы аппроксимации множеств Парето и Слсйтера предлагаются в большом числе работ.
Подробный обзор методов аппроксимации множества Парето можно найти в работе [G7], а здесь приведем только краткий обзор основных пдеіі. Отмстим вначале, что методы аппроксимации множества Парето делятся на три основные группы:
Методы симплексного типа для линейных задач рассматриваются в большом количестве работ, однако все они имеют общий недостаток - недостаточно точное представление множества Парето. Этот недостаток имеет две основные причины. Во-первых, симплексные методы строят только эффективные вершины, в то время как множество Парето может даже и в линейном случае оказаться невыпуклым, а значит, набор вершин не дает полного представления о его структуре. И второе, из-за большого количества псрппш-рсшешШ пли же из-за возможного зацикливания симплексных методов представление множества Парето может получиться неточным.
Метод сеток состоит в выборе некоторой сети на множестве решении и отбрасыванию доминируемых по значению критериев точек этой сетки. Недостатком этой группы методов является трудоемкость при больших размерностях пространства решений.
Методы свертки - подмножество методов скаляризацпн. Суть всех методов свертки состоит в том, что задача аппроксимации множества Парето заменяется на задачу оптимизации параметрического семейства скалярных функций, что позволяет ввести сетку по параметрам свертки н получить аппроксимацию множества Парето с необходимой точностью. Видов свертки уже разработано достаточно много, см. [13J. Видимо, наиболее известной и часто применяемой является линейная свертка критериев. Так, например, в работе [26] для линейной модели экономического взаимодействия регионов предложено использовать линейную свертку для параметризации множества Парето. Аналогичное применение линейной свертки см., например, в [03].
Логическая свертка, введенная в [13], а также модифицированная логическая свертка, позволяющая получить множество Парсто, а не Слсйтера, также хорошо изучена и применяется для выпуклых задач.
Обоснованию предпочтительности использования нелинейной свертки по сравнению с линейной посвящена работа [54].
Отметим также ассортиментные свертки (см. [78]) и популярный в экономических работах метод идеальной тонки {см., например [76]).
Общей проблемой методов свертки является необходимость решать большое количество скалярных задач. Из-за этого актуальными являются вопросы уменьшения числа задач оптимизации свертки. Так, в [67] проведено исследование возможностей уменьшения количества скалярных задач для обратной логической свертки.
Существуют и иные методы аппроксимации множества Парсто, например, в работе [79] предлагаются вычислительные методы поиска компромиссных решений, основанные на методе "центра тяжести".
Читателю, желающему получить подробное представление о постановках и методах решения многокритериальных задач можно рекомендовать книгу [77]. В этой работе подробно и иллюстративно обсуждаются вопросы построения эффективных точек, рассматривается применение в многокритериальной оптимизации целевого программирования, метода метрик Чебышева, методов наискорейшего подъема и Фрэпка-Вулфа и т.д. Также в этой работе рассматриваются такие частные случаи задач многокритериальной оптимизации как дробно-линейные многокритериальные задачи, задачи с непогнутой функцией полезности и т.д.
Многокритериальные задачи.оптимального управления рассматриваются, в частности, в работе [39]. В данной работе рассматриваются и игровые задачи с векторными доходами, решать которые предлагается при помощи А-свсрткн.
В центре нашего внимания в данном исследовании будет обратная логическая свертка критериев (см. 2.1).
Многокритериальный выбор
Напомним, что кроме задачи многокритериальной оптимизации мы упоминали и задачу многокритериального выбора.
Итак, предположим, что множество Парето пли множество Слсйтера построено аналитически или получена его аппроксимация. Далее паре ЛПР - исследователь операций необходимо определиться н сузить построенное множество до одной ТОЧКИ, чтобы принять решение о применении топ или иной стратегии.
Основным подходом к многокритериальному выбору до некоторого времени была следующая концепция: считалось, что па задаче оптимизации исследователь операций закончил свою работу и задача выбора переходит к ЛПР. Напомним, что множество Парето даже в "простом" случае (например, для векторных критериев, задаваемых линейными функциями) может иметь достаточно сложный ннд п выбор из этого множества не является очевидной задачей. На вопрос "как именно ЛПР сделать свой выбор" рекомендация обычно следовала следующая: призвать экспертов, которые выяснят, какие именно критерии для ЛПР важнее н помогут принять решение на основе построенного множества Парето.
Разработано большое количество методов подбора экспертной группы и правил голосования внутри нес. Так, правила формирования группы экспертов и методы ее работы подробно описаны в работе [CJ.
На данный момент роль экспертов в окончательном выборе не считается исключительной. В процесс многокритериального выбора в современных моделях вовлечены как эксперты, так и исследователь операций и ЛПР. Видимо, наиболее популярным подходом, связанным с развитием экспертных систем, является следующий: дальнейшее сужение множества Парето поручается экспертам, экспертной системе пли исследователю операций, причем они вступают в диалог с ЛПР, при помощи голосования или при помощи интерактивной процедуры. В процессе этого диалога п ныяс- няются истинные предпочтения ЛПР. Большое внимание здесь уделяется развитию алгоритмов визуализации и построения интерактивной процедуры.
Так, в [78] приводится обоснование и пример диалоговой схемы принятия решений. В работе [28] для формирования проекта пятилетнего плана машиностроительного предприятия предложено использовать имитациоииую модель, на основе которой ЛПР принимает решения, и ирипедспы принципы построения подобной модели с использованием как лексикографического упорядочивания, так и свертки критериев.
В качестве примера интерактивной экспертной системы многокритериального выбора можно отметить Yandex Гуру ( - популярный онлайп-сервпе, помогающий принять решение о выборе той или иной модели в данной группе товаров).
В монографии [1] обоснованы методы теории выбора, основанные на применении функций выбора, в частности, применение механизмов турнирного выбора для разрешения мпогокритерпалыюстп.
В работе [52] критикуется подход привлечения экспертов и предлагается допустить паличне у ЛПР некоторого отношения предпочтения на множестве решений. Доказано, что при "разумности" ЛПР все итоговые решения будут являться Парето-оптнмальпыми. Под "разумностью" понимается соответствие отношения предпочтения некоторым достаточно логичным аксиомам, как то принципу исключения доминируемых решений, существованию пррефлекспвиого и транзитивного продолжения критерия па все критериальное пространство и, наконец, согласованности отношения предпочтения с критериями выбора. Показано, что при "неразумности" ЛПР итоговое решение может и не оказаться Парсто-оптпмальпым. Однако и от имеющейся информации об относительной важности критериев отказываться не предлагается. В данной работе предложены методы сужения множества Парето на основе имеющегося ранжирования критериев по важности.
Далее приведен метод последовательного сужения множества Парето на основании количественной информации об относительной важности критериев. Изложение основывается в том числе и на психологических аспектах принятия решений человеком. А именно рассматриваются и иллюстрируются стратегия компенсации и стратегия отсечения, которыми в реальных задачах выбора пользуется ЛПР.
Проблеме относительной важности критериев посвящены и работы [55], [53]. О нормализации критериев см. также [42].
Проблема количественной оценки важности критериев является актуальной. Так, отметим продолжающую данную тему статью [75].
Работа [37] также во многом посвящена тому, как из множества Парето выбрать точку или подмножество. В данной работе рассматривается случай, в котором ЛПР должен выбрать из имеющегося множества Парето итоговую точку, либо несколько игроков должны найти компромисс на итоговом Паретовском множестве. В качестве иллюстрации па примере экологической модели рассматривается противостояние заводов (муниципальных служб) и жителей (экологов), из которых первые заинтересованы в минимизации затрат, а вторые - в минимизации загрязнения. Для поиска оптимальных решении и для визуализации и удобства этого поиска в работе пропагандируется метод достижимых целей.
В работе [18] также исследуются проблемы визуализации многокритериальных задач для помощи ЛПР в принятии решений. Исследуется функция полезности ЛПР и предлагаются методы аппроксимации данной функции при помощи квазпвогнутых функции и Чсбышевскнх функций.
Отметим также уже упоминавшуюся работу [15], в которой представляется экспертная система для принятия решений о разработке и разведке нефтяных месторождений.
Динамические задачи и задачи с пеопределенпостгт
Задачи оценки последствий действий противника или природы, задачи учета влияния случайных сбоев и помех на работу оборудования или сетей связи и многие другие являются типичными случаями возможности применения теоретико-игровых и минимаксных моделей. Приведем ссылки на некоторые работы, посвященные этой теме.
В работе [3| проведено исследование методологии принятия решения в условиях неопределенности, дана классификация видов неопределенности и формулируются различные подходы к принятию решений при неопределенности. Для выбора решения при неопределенности возможно использование следующих критериев: средних затрат, критерии минимаксных затрат, критерии минимаксного риска (критерий Сэ-внджа), критерии пессимизма-оптимизма (критерий Гурвнца), обобщенный критерий. У каждого из этих критериев есть как достоинства, так и недостатки. Так, критерий средних затрат предполагает равновероятность всех исходов неопределенности, что пе всегда соответствует действительности. Критерий Гурвица и обобщенный критерий опираются на субъективные показатели. Недостаток критерия минимаксных затрат и критерия Сэвиджа заключаются в ориентации на самые худшие из осуществимых условий, однако именно они предохраняют ЛПР от наибольших потерь. Таким образом, минимаксный критерий часто используется в математических моделях.
Например, в [19] рассматриваются задачи распределения ресурсов па транспорт-пых сетях при наличии неопределенных факторов, задачи минимизации времени либо стоимости выполнения работ при наличии неопределенных факторов.
В [34] рассматривается минимаксный подход к решению задач выделения полезного сигнала при наличии шумов и помех. Здесь рассмотрены в динамике как задача фильтрации (т.е. задачи в реальном масштабе времени при наличии только информации, поступившей к текущему моменту), так и задача интерполяции (восстановление сигнала при наличии записи).
В [3] рассматривается задача потребления электроэнергии и, в частности, применение макснмшшого критерия її задаче вычисления тарифов электроэнергии.
Вопросам байесовского (вероятностного) подхода к динамическим задачам посвящена, например, работа [61]. В этой работе, в частности, исследован случай динамики при непрерывном времени п показано, что в случае непрерывного времени возникают эффекты, отсутствующие в дискретном случае.
Любопытная динамическая модель рассматривается в работах [44], [45]. Приведена многошаговая пли бесконечная игра, связанная с процессами.перебора и пополнения. Суть игры в следующем: в исходный момент имеется некоторая не более чем счетная совокупность перебираемых предметов. Стратегия минимизирующего игрока - забирать не более чем счетное количество предметов из набора. Стратегия максимизирующего игрока состоит в добавлении не более чем счетного набора предметов. Цель игрока, отвечающего за перебор - мшшмизнронать, а цель игрока, отвечающего за пополнение, максимизировать количество предметов, которые останутся незабраппымн при самом неблагоприятном поведении другой стороны. Характерной чертой этой игры является зависимость результата от полноты информации о предыдущих состояниях игры. Показана связь такой модели с дифференциальными играми, а также описано применение модели перебора-пополнения для задачи сортировки деталей.
Вопросы принятия решений при неопределенности обсуждаются н в работе [29j. В данной монографии рассматриваются игровые модели с субъективной неопределенностью, в частности с учетом возможной неполной информации о неопределенных факторах и их влиянии па систему, а также о целях противника.
Один из основных источников динамических и теоретико-игровых задач с наличием противника - модели военных действий. Так, в работе [73] приведена модель минирования, легко распространяемая на случай кратного векторного мпнпмакса. Игра заключается в следующем: защищающаяся сторона размещает мины п проливе. Нападающая сторона использует минный тральщик для того, чтобы обезвредить мины. Однако на случай прохода тральщика каждая мина имеет устройство, называемое счетчиком судов. Счетчик судов предотвращает взрыв мины до того момента, пока мимо нее не пройдет заданное заранее количество судов. Итак, управлениями "минирующей" стороны являются количество мин и значения, выставляемые па счетчиках судов, управлениями "прорывающейся" стороны будет количество тральщиков, направляемых по минируемому фарватеру, Критериями в данной задаче могут являться как количество прорвавшихся судов, так п стоимость минирования и протиномшшых работ.
Аналитические и численные методы поиска мииимакса
Поиск максимина и мииимакса не является простой задачей. Задача па распадающийся макснмнн и миннмакс является более изученной, а задача поиска мииимакса (максимина) со связанными переменными представляет немалую трудность как с точки зрения аналитического решения, так и с точки зрения численных методов.
В работе [43] проведены исследования транспортных задач с минимаксным критерием. Рассматриваются транспортные задачи с нетрадиционным критерием. В классических моделях транспортная задача ставится как задача максимизации или минимизации, в зависимости от постановки (подробно о транспортных задачах см., например, [-18], [30]). В работе [43] критерий рассматривается как миннмакс, разработан алгоритм нахождения минимаксного значения и соответствующей ему минимаксной транспортной матрицы, проведен анализ и для случая целочисленных переменных.
Численным методам максимина и, в частности, кратного максимина, посвящена работа |72]. В этой работе обосновывается трудоемкость метода штрафов для вычисления кратного максимина и мииимакса и предлагаются некоторые рекомендации по упрощению вычислении. В данной работе делается также предположение о возможности использования для численных решении кратного макспмина и мшшмакса стохастических методой.
В работе |24] предложено построение стохастических аналогов детерминированных итерационных методов для решения минимаксных задач. Так, для решения минимаксных задач обоснован стохастический метод градиентного спуска, названный комбинированным методом штрафов и стохастического градиента.
В работе [25] рассмотрена задача поиска мшшмакса со связанными переменными. В основе исследования лежит идея сведении задачи па связанный максимин к предельной задаче математического программирования при помощи метода штрафов. Установлена связь между градиентами штрафных функций и множеством стационарных точек задачи и на основе этой связи предложен стохастический градиентный алгоритм для поиска стационарных точек задачи на связанный максимин.
Дифференциальные игры. Отдельной строкой стоит упомянуть активно развивающееся направление на стыке теории игр и оптимального управления, а именно дифференциальные игры. Отметим здесь такие работы как [21], [22], [23], в которых предложена концепции векторного мшшмакса и макеимпна (подробнее см. 1-3) а также [47], [2], [71] в которых проведены исследования некоторых динамических минимаксных задач на основе аппарата дифференциальных игр. Обратим также внимание на статью [70], is котороіі рассматриваются дифференциальные игры днух коалиций в условиях неопределенности. В этой работе рассматривается случай, когда каждая коалиция состоит из диух игроков, отношения между которыми считаются доброжелательными и строятся на основе максимума по Парсто.
Динамическая многокритериальная задача с неопределенностью.
Заметим, что динамическая многокритериальная задача с неопределенностью, являясь естественным продолжением вышеперечисленных тем, уже рассматривалась в литературе.
Отметим, например, статью [35[, в которой, в частности, поднимаются вопросы о многокритериальных динамических задачах и предложено решение такой задачи на основе теории управления в условиях неопределенности.
В работе [47] в рамках концепции из [21] для формализации многокритериальной динамической задачи принятия решений при неопределенности рассматриваются методы решения обратных задач динамики и задач сближения объекта с заданными точками. В качестве оптимального решения многокритериальной позиционной задачи при неопределенности предложена седловая точка по Парсто, доставляющая гарантированный результат векторному критерию (см [22]). Устанавливается динамическая устойчивость данного решения, выясняется его структура. Рассматриваются свойства максимипа по Парсто в позиционных дифференциальных играх и играх сближения.
В работе [17] задача многокритериальной оптимизации при неопределенности рассматривается в случае, если известна информация о неопределенных факторах, в частности, случай, если неопределенные факторы описываются случайной величиной с известным распределением.
Данная работа продолжает исследования, начатые к работах |7, 9, 10, 40, 58, 59, 60]. Здесь отметим, что в этих работах разрабатывалась формализация векторных макспмпна, мипнмакса и макспмшшмакса, с использованием понятия о гарантированных оценках. В этих работах также рассматривались вопросы аппроксимации векторных максимипа, мипнмакса и макспмшшмакса. Подробнее о данном подходе см. в 1.3.
Структура диссертации.
В первой главе рассматривается вопрос определения значения кратного векторного мипнмакса. Для формализации задачи динамического принятия решения с неопределенностью используются классические определсиия векторного максимума по Парето пли Слеіітеру и определения векторных мшшмакса и макснмпна, предложенные в [9, 10, 59].
Параграф 1.1 посвящен постановке задачи на кратный векторный мнппмакс.
В параграфе 1.2 изложены основные сведения о задачах и подходах векторной оптимизации, которые будут необходимы для обоснования определения кратного векторного мшшмакса. Здесь приводятся основные определения векторного минимума и максимума, понятия о множествах Парето и Слсйтера, о П-Э оболочке, вводится понятие оптимизации в оценках.
Параграф 1.3 посвящен обзору задач векторной оптимизации с неопределенностью. В применении к этим задачам обсуждаются различные определения кратного векторного мшшмакса и максимина, различия и связь между этими определениями. В работах [9, 10, 59] проведен подробный анализ различных подходов к определению векторного мипимакса и доказано, что все имеющиеся определения для векторного мшшмакса и максимина за максимизирующего игрока для задачи с неопределенностью сводятся всего к двум различным подходам:
МіпМахФ(а:,у) = F< = Мах П U {Ф\Ф < Щх,у)}, (4)
МахМіпФ(о:,у)=/<=Мах \J f) {ф\ф < Ф(х, у)}. (5)
Здесь черта сверху означает интерес оперирующей стороны, т.е. определения выше приведены для случая, в котором исследователь операций представляет максимизирующую сторону. Данные определения не могут быть сведены одно к другому заменой игроков. Различие между ними показывает информированность или пепн-формироваппость максимизирующего игрока, за которого проводится исследование.
Параграф 1.4 дает представление о задаче поэтапного принятия решении в условиях неопределенности. Здесь приводится определение векторного макспмпннмакса. Векторный макснмшшмакс исследуется в [49, 60]. В этих работах обосновано следующее определение:
Мах Мій Мах Ф(г,ш,ы) =Мах 1 I П U {Ф еШР\ф < Ф(г,ги,и)\. (G)
В параграфе 1.5 вводится формализация кратного векторного мипимакса. В работе [50] рассматриваются следующие обобщения определения мипимакса (4):
Ф* = ЇЇІ?ПМІП U Мах U Мін [J Max J {ф<Ф(щги)}. wlWl «ЧУ1!»1) wflVT(uT-i) ит UT (wT)
Ф* = Мах f] [J ... f] [J {ф>0\ір<Ф(щи))}. (8)
Доказано, что определения (7) и (8) в слейтеровском случае совпадают.
Вторая глава посвящена параметризации неулучптаемых оценок вектора критериев в задаче динамического принятия решении в условиях неопределенности, а именно использованию в данной задаче обратной логической свертки.
Параграф 2.1 вводит понятие обратной логической свертки, которая далее будет использоваться для аппроксимации значения кратного векторного мипимакса. В данном разделе обсуждаются свойства обратной логической свертки п задаче аппроксимации множества Парето.
Эта свертка предполагает замену вектора Ф = (^ь- , Применение ОЛС для параметризации максимума Парето и Слейтера было изучено в работах [66, 65, G7]. Параграф 2.2 посвящен параметризации значений кратного векторного мшгпмак-са при помощи обратной логической свертки. Параметризация значения кратного векторного миннмакса рассмотрена автором в работах ]50, 51, 64]. На основе ОЛС сведена функция свертки 0\и] = min max ... min шах тій ц~1<лЛи\ w) Vu M. шЧи'1 цієї/Чи;1) wT\Vr{uT-^)uTUT(wT)iZl{li) Основным результатом второй главы является теорема 2.1, в которой доказано, что при предположениях регулярности задачи Ф = ~П U П U {Ф>0\ф<<Цщю)} (9) для слейтсровекпх значений максимума справедливо представление * = U *№ Таким образом, обосновано применение обратной логической свертки для параметризации оценок векторного критерия. Третья глава посвящена вопросам аппрокспмациоппых свойств ОЛС в задачах на кратный векторный мипнмакс. В параграфе 3.1 проведено исследование аппрокспмациоппых свойств свертки для регулярной задачи. Доказано, что в предположен и ях регулярности (9) функция свертки непрерывна па рассматриваемом множестве. На основе нспрерыппостн обоснован алгоритм построения 5-сети, позволяющей аппроксимировать значення кратного векторного миннмакса да я регулярного случая. В параграфе 3.2 рассмотрены свойства функции свертки в случае, если условие регулярності! (9) не выполнено. В частности, доказана ограниченность функции сверт- ки. Предложен и обоснован способ построения непрерывного продолжения функции свертки, как предела 0[j.i] = lim 9\ji], доказана корректность построения непре- ,1 -> Ч, II > п рывпого продолжения п рассмотрены свойства функции 0\р\. Показано применение непрерывного продолжения для аппроксимации значения кратного векторного мипимакса. Параграф 3.3 описывает ашірокспмациоиньїе свойства ОЛС в случае, если условие регулярности (9) выполнено не па всем пространстве критериев, но на некотором его подпрострапствс, Показано, что и при редуцированном условии регулярности возможно построение 6-сети, только па более узком множестве. В этом параграфе обосновано также построение усиленной 5-сстн. Параграф 3.4 описывает свойства реализаций кратного векторного мипимакса. Показано, что экстремальные стратегии в задаче поиска кратного векторного мипимакса следует искать среди реализаций кратного мипимакса свертки при различных значениях /( параметра свертки. Основным результатом главы является доказательство правомерности использования ОЛС для аппроксимации кратного векторного мипимакса как в регулярной, так и в нерегулярной задаче. В заключении приведены основные результаты диссертации. Поскольку задача, которой посвящено данное исследование, возникает "па стыке" нескольких тем - многокритериальной оптимизации, теории игр и динамических систем, проведем обзор основных идеи и направлений по этим темам. Исследование операций и, в частности, теория принятия решений являются сравнительно .молодыми науками, а следовательно, предоставляют большой простор для разработки новых понятий и нового математического аппарата. В связи с развитием вычислительной техники, а, следовательно, широкої! применимостью и востребованностью математических моделей задачи оптимизации являются популярной темой в современной пауке. Многокритериальная оптимизация и динамические задачи не являются исключением. Оба этих направления представлены в большом количестве работ. Проблемы формализации принятия решений человеком не являются еще полностью разработанной теорией ([83]). В качестве одной из основных концепций следует рассматривать задачи принятия решения при нескольких критериях. Смысл многокритериальной постановки заключается в том, что зачастую лицо, принимающее решение (ЛПР) не в состоянии описать спои предпочтения при помощи одной функции, поскольку это противоречит многогранности, "нелинейности" его интересов. Практически в любой реальной задаче принятия решения, в любой рассматриваемой области, будь то распределение финансирования научных проектов либо проблема покупки нового телевизора, для ныяспеиия предпочтений недостаточно одного критерия (см. [20}, [52], [36], [4]). Традиционно задача принятия решения при нескольких критериях делится па две стадии или подзадачи. Первой стадией является задача многокритериальной оптимнзации, под которой под разу меняется построение некоторого эффективного множества, то есть множества решений, каждое из которых в определенном смысле "пе хуже" других. Второй стадиен является задача, которую иногда называют задачей многокритериального выбора, то есть сужения эффективного множества до нескольких точек, а в идеале и до одной точки. Построение эффективного лтожества. Одним из классических определений "эффективного" множества является определение эффективности по Парето. Эффективное множество (или векторный максимум) по Парето - это множество всех педо-минируемых (максимальных по отношению ) векторов. Множества Парето является, пожалуй, самым распространенным, хотя и пе единственным определением векторного максимума. Достоинств у использования множества Парето достаточно много. Так, это определение в достаточной степени наглядно, ясно н хорошо известно, а следовательно, исследователь операций не вызовет особого удивления, если представит его для рассмотрения ЛПР. Однако множество Парето неудобно для аппроксимации, а потому вместо множества Парето часто рассматривается некоторое его расширение - множество Слейтера. Множество Слейтера (или максимум по Слейтсру) - множество всех максимальных по отношению векторов. Подробно о множествах Парето и Слейтера см. 1.3. Также точки максимума по Слейтсру часто называют полуэффективными. Множество Слейтера в общем случае обладает лучшей структурой, чем множество Парето, потому в данной работе рассматривается почти исключительно именно это определение оптимальности вектора критериев. Необходимым условиям эффективности по Слейтсру посвящена, например, работа [G2]. Здесь при определенных условиях регулярности задачи векторной оптимизации приведены необходимые п достаточные условия эффективности решения по Слейтсру. Подробнее о численных методах аппроксимации векторного максимума см. ниже. Как уже отмечалось, построение множеств Парето или Слсіітера - не единственный подход к многокритериальной оптимизации. В большом количестве работ вместо или наряду с множеством Парето используется ранжирование критериев, вводится лексикографическое упорядочивание критериев, функции предпочтении либо весовые коэффициенты для множества критериев. Так, например исследование [11] посвящено многокритериальному ранжированию объектов. Здесь предлагается не рассматривать множество Парето как решение задачи, но применить алгоритмы, основанные на использовании экспертиз, позволяющие экспертам упорядочить критерии по важности. В частности, предлагается использовать схему голосования для ранжирования критериев. В данной работе рассматривается также два варианта свертки критериев и указывается связь видов свертки с методами ранжирования критериев. Ранжирование критериев порой может иметь достаточно сложную структуру. Так, в [16] для облегчения целенаправленного выбора предлагается выделять дерево критериев. Подробно о различных подходах к построению эффективного множества, а также о вопросах топологических свойств, параметризации и устойчивости множества Парето можно прочесть в монографии [57]. Приведем примеры работ, в которых разрабатываются различные подходы к многокритериальным задачам. Прежде всего несколько слов об областях человеческой деятельности, в которых успешно применяется многокритериальный подход: В выпуклом случае 0(/х) будет лииппщсвой и без предположения о строгой положительности Фі{и). Утверждение 2.5. Пусть U — выпуклое множество, Ф»(и) — вогнуты на U (г = 1,..., т). Тогда в ((.і) удовлетворяет условию Липишца с копстантоіі В этом параграфе задача построения множества Парето будет сведена к параметрической задаче однокрнтерпалыюп оптимизации. Множество Парето будет строиться к виде объединения множеств максимумов ОЛС. Следующие два результата аналогичны приведенным в [14] для "традиционной"логической свертки. Утверждение 2.6. р.ЄМ ftcM 2) Р(Ф) С [J { (« (/ ))} С 5(Ф), где и (/() — произвольная точка из У (/І). Как следует из утверждения 2.6, точки максимума свертки А являются, вообще говоря, лишь слейтеровскими. Для выделения парстовскпх точек будем максимизировать сумму критериев на множестве U (fi) (см., например [56], [77]). 2)Р(Ф) = [J (Ф(ІІЦ(/І))}, где tij5(/i) — произвольная точка пз Щ{(і). Отметим, что для определения «о0і) "УЖ"0 решить двухэтаппую лексикографи-ческую задачу. Известно, что в нелинейном случае такого рода задачи обычно обладают худшими свойствами, нежели обычная одпокрптерпальная задача. Упростить аппроксимацию мы можем, введя следующее требование регулярности (см. 31]): Определение 2.1 Оценку ф Є Р(Ф) будем называть регулярной с константой регулярности с 0, если для любого ф Є Ф справедливо неравенство Множество Парсто Р(Ф) будем называть равномерно регулярным с константой е 0, если каждая оценка ф Є -Р(Ф) регулярна с константой с. Таким образом, регулярные оценки характеризуются тем, что нельзя увеличить ни один частный критерий за счет потерь более высокого порядка малости по остальным. Замечание. Рассмотрим вместо функций Ф;(и) функции Ф((и) = Ф{(и) + а , где а — набор произвольных констант. Обозначим Фа = Ф(/). Очевидно, что Р(Фа) = Р(Ф) + {а}, а Рф(и) = РФ(ЇУ). Легко заметить, что если множество Р(Ф) равномерно регулярно с константой регулярности с 0, то и множество Р(Ф,г) также будет равномерно регулярным с той же самой константой с. Иначе говоря, как сам факт регулярности множества Парето, так и константа регулярности не зашісят от сдвигов частных критериев. Отметим, что равномерно регулярное множество Парето — достаточно распространенный случай в многокритериальной оптимизации. Достаточным условием регулярности, например, является линейность критериев либо их дискретность (см., например [5G]). Можно считать, что нерегулярные оценки не представляют интереса для ЛПР, поскольку подобное нерегулярное решение можно сильно улучшить по одному из критериев, не теряя в остальных, а значит, строго говори, задача не является многокритериальной либо критерии не были правильным образом нормализованы. В регулярном случае множество Щ (/.і) (решении лексикографической задачи максимизации) может быть заменено множеством Аналогично утверждению 2.2 и следствию из этого утверждения можно показать, что функция 0a(}.i) непрерывна на А/, а отображение Ф(/Ґ (д)) полунепрерывно сверху на Л/ и непрерывно в тех точках ft0, в которых множество Ф(с7 (//)) состоит из одного элемента. В регулярном случае вместо /0 (/і) для параметризации множества Парето могут быть использованы множества U (/.i) при достаточно малом а 0. Утверждение 2.8. Пусть множество Р(Ф) равномерно регулярно с константоіі с 0. Тогда для любого а Є (0, с) справедливо гДе иа(м) произвольная точка из U (/t). Отметим, что ограничение па а в утверждении 2.8 инвариантно относительно сдвигов функций ФІ(Х) па любые константы а,-, сохраняющих неотрицательность получаемых функций ФІ(ГС). Выше было показано, что решая задачу максимизации ОЛС для всех значении параметра jt Є М, можно найти все множество Парето. На практике приходится, как правило, ограничиваться лишь конечным числом точек из некоторой 5-сетн М$ С М Определение 2.2. Конечной 6-сетью во множестве М называется конечное число точек ЛЛ& с М таких, что V/i Є М найдется вектор \і6 Є М&, для которого \\HLS\\ 5. Сложность в непосредственном использовании определении (36) для построения множества Ф н])нводит к задаче параметризации множеств Парето и Слсйтсра. Согласно утверждению 2.9, при выполнении условия регулярности (4G) для значения Мах по Слеіітеру в (36) справедливо представление (43). Таким образом, перебирая все значения параметра /І Є М и находя соответствующие 0[ц], можно получить все множество Слейтера. Однако па практике подобный перебор возможен только при аналитическом решении задачи, поэтому возникает вопрос об аппроксимации (43) с помощью конечного множества точек из М. Для изучения аппроксимацнопных свойств ОЛС в задаче (10) исследуем непрерывность функции 8[}і]. Утверждение 2.9 дает параметризацию слейтсровского значения (36). Для того, чтобы обосновать аппроксимацпонпые свойства представления (43) па базе ОЛС, докажем следующее Утверждение 3.1. Пусть при всех w, uT_1, удовлетворяющих ограничениям задачи (10), выполнено условие регулярности из [65, 67, С8] для внутренней задачи векторной максимизации, т.е. Тогда функция в[-] (42) непрерывна Уд Є М. Доказательство. Согласно утверждению 2.2 в рассматриваемом случае внутренний макспмин является непрерывной функцией /і па М. Далее рекуррентно пользуемся непрерывной зависимостью от параметра ц функций максимума и минимума (см. задачу 4.4 из [46)). Таким образом, и условиях (46),(50) представление (43) позволяет аппроксимировать слейтсровское значение (3G) с любой наперед заданной точностью. Исследуем соотношение этих условий. Утверждение 3.2. В сделанных предположениях относительно задачи (10) из условий утверждения 3.1 следует и регулярность в смысле (45),(46). Доказательство, По лемме 2.1 правам часть (50) раина а левая — замыканию пересечения этого множества с положительным ортаитом. Теперь заметим, что где Л/ = {/і Є М\ ji 0, 0 [//](uT l, wT) 0}. Кроме того, если для некоторого /і0 0 выполнено 0 r[/i](uT-1,wT) = 0, то \/ит Ur(wT) Зі Є I: pi(u;w) = 0, так 4TOHV// 0 r[/j](uT-1IwT) =- 0. Тем самым, если 3)i 0: б Ч/і0] -1, wT) 0, то п V/i 0 0/r[/f](iiT 1,wT) 0. Следовательно, условие 0/r[/i](uT-1,wT) 0 V/A 0 (а, значит, и V/i 0 по определению 0 ) является отрицанием того, что множество в левой части (50) пусто, и таким образом оказывается необходимым для выполнения равенства (50) VUJ, UT-1. НО при этом и 6[/i\ 0 \/{І Є М (см, определение (42)). В результате и условиях утверждения 3.1 получаем Обозначим через Ед множество под чертой. Из свойств операции замыкания можем записать ЄМ ЄЛ/О /ІЄЛ/ /іЛ/ //ЄЛ/ ЄЛ( Отсюда по определению Е для левой части (45) выводим Докажем, что последнее множество равно правой части (45). Дсііствнтельпо, множество Е(і задано линейными ограничениями неравенствами, у которых лишь правая часть зависит от /j. В силу утверждения 3.1 эта зависимость непрерывна, что обусловливает непрерывность по Хаусдорфу отображения fi — Е для \і Є М [?, ]. В рассматриваемом случае Л/ = {/І Є М\ ц 0}, т.е. М является замыканием Л/. Поэтому V// Є Л/ \ -Л/0 Зд 0: / - , к -» со, и Н -J- 5 в смысле метрики Хаусдорфа, а значит, Из непрерывности функции 9[fi] ф 0 следует #[д] 0. Действительно, пусть имеется д, такое, что 0[д] = 0. Тогда ОЩр = 0. Значит для всех д 0 выполняется 9[fi] = 0, так как иначе Эд 0, при котором #[д ]д 0 и #[д ]д 0[д]д, а это невозможно, поскольку оба этих вектора максимальны по СлеИтеру в множестве Ф. Предположим теперь, что Зд , такое, что 0[ft ] ф 0. Из непрерывности заключаем, что для любого є 0 35 0, такое, что Уд : д - д У выполнено 0[д ] - 0[ц}\ є, Рассмотрим е = —— и зафиксируем S 0 таким образом, чтобы Уд, таких что д — д [ (Ї, было справедливо 0[д ] — 0[д] є . Выберем St 0, Si min(5, min дг ). Обозначим /(д ) через JV и построим д : Д; = д — — при і Є І {(і ), / . — — — при і ф /(/t ). Рассмотрим 6т 0. Из-за сходимости к 77 последовательности {ftk} l и условия \рк] — 9 в этой последовательности имеется /А " , при котором \\f.t m — р,\\ 5т/2 fcm] - Щ є/А. По определению функции 0[ц] в 5т/2-окрестиости вектора Jiknx имеется / (т) 0, при котором \0Щкт] - % m ] є/4. Раскрыв неравенства, получаем: для любого 8Ш из последовательности {6к}=1 отыщется ц(} 0, удовлетворяющее условиям JI/7 — / т 5т н J6[/J. ri ]— д\ Е/2. Итак, существует последовательность {// " } =и ( 0» um 11 — ЇЇ» причем Vm %tm ] -0 г/2. Переходя к пределу, получим lim 9{ \ 0\ Е/2, следовательно, lim 0[и } ф V, но но определению 0 = 0[ji} = lini_ 0\j.t]. Данное противоречие доказывает лемму. Следствие 3.3. Функция 0[р] равномерно непрерывна па Д/. Действительно, по функции 0\р\ однозначно можно определить функцию $[іі] па М, которая непрерывна на М, а значит, равномерно непрерывна на М, и, кроме того, %] = 0[/i] Уд 0. Таким образом, функцию 6[(.t] можно использовать для аппроксимации кратного векторного мнннмакса в нерегулярном случае, в частности, для построения й—сети. Ситуацию, в которой не выполняются условия регулярности, в частности, когда 0о)! = О (т-с- Ь1] О V/i 0) нельзя считать экзотической. Так, для сетевой задачи (2) = 0 означает, что пет априорных гарантий обеспечения связи всем пользователям (при любом допустимом варианте синтеза не исключены разрушения, приводящие к потере связности графа сети). Исследование возможностей сетевой системы в подобных случаях, без сомнения, важно, ибо часть пользователей сети, как правило, не настолько затронута разрушением, чтобы совсем лишиться связи, и некоторый ненулевой поток для них достижим, Однако формальное определение слейтеровского решении задачи (10),(36) дает при в[{= 0 слишком широкое множество Ф — всех гарантированных оценок векторов потоков. А именно, Ф , равное МахФ, совпадает со всем множеством Ф, т.е. оптимизация просто отсутствует (не учитывается стремление к максимизации потока). Представление множества Ф в виде (43) является более адекватным, поскольку правая часть (43), вообще говоря, уже множества Ф, по при этом, согласно (48), содержит все паретовекие векторы из Ф. Кроме того, в ситуации, когда по некоторым компонентам вектора критериев нельзя гарантированно обеспечить ненулевые оценки, формула 1J 0[/i]fi\ {0} в силу леммы 2.4 описывает слентероиское множество в задаче на кратный минимакс вектора из остальных компонент. В ряде случаев невыполнения (4G) справедливо аналогичное условие регулярности, но только по ненулевым компонентам вектора критериев. А именно, обозначим через /І г-н орт и введем J = {і Є І\ #[/іг] 0}. Очевидно, если раскрыть определения, то 0[fi] = 0 при всех /І Є М, таких что 1(ц) \ J ф 0, и в[[і] 0 при тех //, для которых /(/І) С J, А кроме того Ф = {О/у} х Ф./, где О/у — вектор из пулевых компонент і Є I\J, Здесь и далее для любого вектора Є К и любого индексного множества / С / символ /) означает вектор, составленный из компонент j, г Є / . Предположим, что условие регулярности типа (46) выполняется в каком-либо подпространстве критериев размерности \J\ Q, т.е. для замыкания в Rj справедливо Л U П U № о\ъ ч №М v j} = «о. (51) Будем называть (51) редуцированным условием регулярности и введем следующие обозначения: В редуцированном пространстве Rj справедливы все результаты, доказанные для полноразмерного пространства, а именно для значения Мах по Слсіітеру и прострапствс Rj выполнено Махе ФІ 2 Ф}і а Для значення Мах по Парсто в пространстве Махс j 2 } Э Махп j. Справедливы также сформулированные ниже утверждения. Утверждение 3.4. В сделанных обозначениях, если J -ф- 0 и для множества Ф выполнено условие регулярности (51), т.е. то рассматривая максимум по Слейтеру, будем иметь Доказательство. Применив утверждение 2.9 к задаче (10) с критерием ФІ5 получим, что левая часть равна U %]Д Отсюда выводим требуемое равенство с учетом 0[/.i] — 0 при 1(ц) 2 J. Утверждение 3.5. В сделанных обозначениях, если при всех w, ит 1, удовлетворяющих ограничениям задачи (10), выполнено то функция 0j[-\ непрерывна V/xj Є Mj и Доказательство следует из утверждений 3.1, 3.2, примененных к Ф/. Таким образом, в условиях утверждения 3.G можно пользоваться представлением (52) для аппроксимации множества {Од,/} х МахФ . Последнее даст более адекватное, чем Ф — Ф (см. выше), описание решения задачи (10),(30) в отсутствие регулярности. Теорема 3.2. Редуцированное условие регулярности (51) выполнено тогда и только тогда, когда для Мах по Слейтеру имеет место представлениеНеобходимые сведения о векторной отимизации
Задачи многоэтапного принятия решений в условиях неопределенности
Обратная логическая свертка в задаче на кратный векторный минимакс
Редуцированное пространство
Похожие диссертации на Методы параметризации и аппроксимации значения кратного векторного минимакса
