Методы параметризации и аппроксимации значения кратного векторного минимакса

• Автор: Семовская, Анна Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 113 с.

Глава 1. Определение значения кратного векторного минимакса.... 26 §1.1. Задача поэтапного принятия решений в условиях

неопределенности. Постановка задачи

§1.2. Необходимые сведения о векторной отимизации

§1.3. Задачи векторной оптимизации с неопределенностью

§1.4. Задачи многоэтапного принятия решений в условиях

неопределенности

§1.5. Определение значения кратного векторного минимакса

Глава 2. Параметризация значения кратного векторного

минимакса

§2.1. Обратная логическая свертка и ее свойства

§2.2. Обратная логическая свертка в задаче на кратный векторный минимакс

Глава 3. Аппроксимационные свойства свертки в задаче на
кратный векторный минимакс
§3.1. Регулярный случай
§3.2. Нерегулярный случай
§3.3. Редуцированное пространство
§3.4. Реализации оптимумов
Заключение
Список литературы

В работе исследуется задача поэтапного принятия решений и условиях неопределенности при наличии векторного критерия. Задачи, в которых интерес управляющей стороны не может быть описан одним критерием, являются хорошо известными в исследовании операций. Многокритериальность может иметь смысл многогранности человеческих предпочтений или выражать необходимость обеспечения потребностей нескольких пользователей или процессов (так, например, в сетевых задачах возникает необходимость обеспечения линиями связи одновременно нескольких тяготеющих пар в сети). Задача принятия решений в случае, когда некоторые параметры системы не известны либо зависят от внешних факторов, является актуальной!. Рассмотрим задачу, в которой оперирующая сторона вынуждена принимать решение в условиях неопределенности и выделим случай, когда условия задачи не ограничивают оперирующую сторону необходимостью единократного принятия решения, но включают в себя возможность при реализации какой-либо серии неопределенных факторов применить так называемое корректирующее управление, которое можно выбрать с учетом реализации неопределенности на данный момент. Таким образом можно сформулировать задачу поэтапного принятия решений в условиях неопределенности с наличием векторного критерия.
Для формализации задачи введем необходимые обозначения: обозначим через ги1 переменные, относящиеся к неопределенности, через и1 управления оперирующей стороны и будем считать, что при выборе каждого и1 уже станут известны значения го1 го4, а значения го4+1 определятся позже. Здесь й - индекс этапа (время). Векторный критерий обозначим за Ф(н;го).
Заметим, что традиционно в исследовании операций для решения задач с неопределенностью применяется принцип гарантированного результата ([13]), иначе говоря, неопределенность представляется в виде действий некоторого противника и нсследу-

ется случай наихудшего для оперирующей стороны варианта реализации стратегий этого противника. Таким образом, для раскрытия неопределенности используется минимаксный, или пессимистический критерий. В случае задачи многоэтапного принятия решений с одним критерием приходим к задаче на кратный минимакс.
Формально распространяя данный подход на многоэтапную многокритериальную задачу, запишем:
Ф* =f Min Мах Min Мах ... Min Мах Ф(и;ю). (1)
ш'еип u>€tf1(“'1)«'selV2(u»)u?€UJ(“'J) wT€VT(uT-l)uTeUT{wT)
Приведем пример интерпретации задачи (1) с Т — 2 в терминах многопродуктовых потоковых сетей, служащих структурной моделью ряда многопользовательских сетевых систем (см. в частности [41]). Рассмотрим задачу учета неопределенности при синтезе многопродуктовых сетей.
Качество функционирования многопользовательской сетевой системы определяется мультипотоком — вектором одновременно пропускаемых по сети потоков заявок пользователей (видов продуктов) / = (/i,-.-,/q). Для сети с заданной пропускной способностью ребер ставится, задача векторной максимизации /. При исследовании живучести сетевой системы учитывается, что в процессе се работы исходный вектор пропускной способности может изменяться — уменьшаться по некоторым компонентам. Обозначим соответствующие неопределенные факторы через иг1, ги2 и укажем, что ги1, w2 могут иметь смысл отказов и износа оборудования либо еще какого-либо ухудшения функционирования сети.
Пусть у оперирующей стороны между "ударами" иг1, и>2 есть возможность применить корректирующее управление гг1, ограничения на которое в общем случае зависят от реализации w1. Здесь гг1 имеет смысл вложения в восстановление сети после удара некоторого ресурса.
Тогда гарантированная оценка качества функционирования сети дается гаранти-

где eph X — ПЭ-оболочка X (см. определение 1.5), т.е.
eph X =г {£| Бх 6 А" : £ < х}. (31)
Далее будем под значением (29) понимать (30).
Рассуждая сходным образом для задачи минимизации, придем к формуле
Min Л'(u) ‘= IR+ Р) Min (J {х| Бх е X(v) : х > *}• (32)
VeV v£V
Если объединить (30) и (32), используя пересечение с IR+ лишь один раз (в последний момент), то построим обобщение значения (27) векторного мшшмакса для постановок, в которых целевой функцией является точечно-множественное отображение
A4-,-), Л>,и)сК?.
А именно, убрав в (30) пересечение с IR^ и записав формально
Min Мах X(u,v) Min Мах II eph Л'(ы, и),
vtVuemv) veV u^{v)
выведем нз (32) равенство
Min Мах X(u,v) = IR+HMin И {у| Бх 6 Мах И ephA”(u, и) : х > х)
vev u€U(v) 'т., Ат,
4 ' v€V u€U{v)
= IR+ P| Min (J Max p epii X (u, v), (33)
v£V ueU(v)
что рекуррентпо приводит к следующему распространению (27) для (10):
Ф* =fIR+ПMin (J Мах У ... Min У Мах У {ф < Ф(и;w)}.
w'eiv1 ul6U'(wl) wTeVT(ur-i) uTeUT(u>T)
(34)
(Равенство (33), а также сокращение промежуточных eph и IIУ в (34) получается из определений eph (31), Мах и Min.)
Обобщение формулы (2G) на векторный мшпшакс точечно-множественных отображений проводится с других содержательных позиций. При каждом фиксированном v для описания полуэффективных оценок критерия X(u,v) С IR+ получаем задачу