Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 35
Текст из файла (страница 35)
Часть Iствует, если K и Ф i – выпуклые ограниченные множества и функции соответственно.Свойство 5.5. Так как вектор Шепли – делёж, то по утверждению 5.4вектор Шепли либо находится на Парето-границе П–Н-множества компромиссных решений игры N лиц, либо проектируется на Паретомножество в виде предпосылки дележа и даёт оценку эффективности i-гообъекта – игрока на множестве возможных коалиций с другими объектамиММС (в утверждении 5.10 это показано для любой ν ).5.3.3.Вычисление вектора ШеплиРассмотрим способ компактного вычисления вектора Шепли.
Для этогофиксируем K⊂N и вводим обозначение s = |K|, где |K| – «мощность» множества K (число элементов).{}Пусть Ω = π | K ππ(i ) = K . Заменим в соотношении (5.17) K ππ(i ) на K, асумму по всем перестановкам соответственно на сумму по всем K ⊂ N. Тогда получим1(5.22)=Фi ( ν)∑ | Ω | [ν( K ) − ν( K \ (i ))], i ∈ K ,N ! K⊂Nгде суммирование ведётся по всем K, содержащим i-го игрока. Пусть перестановка π∈Q. Представим её как 1,..., s − 1, s, s + 1,..., N .В соотношении (5.22) надо вычислить |Ω|. Это число всевозможных перестановок π, таких чтоπ(i )= s и K ππ(i )= K , где K ππ(i )= {k ∈ N | π( k ) ≤ π(i )} .Очевидно, что для множества K ππ(i ) \(i) имеем (s – 1)! перестановок, гдеs – число элементов множества K, а для множества N \ K ππ(i ) находим(N – s)! всевозможных перестановок, гдеK ππ(i ) \(i) = (1,…,s – 1), N\ K ππ(i ) = (s+1,…,N),cледовательно |Ω| = (s – 1)!(N – s)!.Подставляя это выражение в формулу (5.22), получаем формулу, удобную для вычисления вектора Шепли:( s − 1)!( N − s )!(5.23)=Фi ( ν) ∑| [ ν( K ) − ν( K \ (i ))] , i ∈ K ,N!K⊂Nгде суммирование происходит по всем коалициям K, содержащим i-го игрока.
Приведём несколько вариантов решения в зависимости от N.При N = 2Глава 5. Оценка эффективности кооперативного компромисса1831!0!1!0!1[ ν(1, 2) − ν(2)] + [ ν(1) − ν(0)=] [ ν(1, 2) + ν(1) − ν(2)] ;2!2!2(5.24)1!0!1!0!1Ф2 ( ν=)[ ν(1, 2) − ν(1)] + [ ν(2) − ν(0)=] [ ν(1, 2) + ν(2) − ν(1)].2!2!2При N = 3 возможные коалиции K с игроком ii = 1: (1,2,3);(1,2);(1,3);(1),i = 2: (1,2,3);(1,2);(2,3);(2),i = 3: (1,2,3);(1,3);(3,2);(3).Поэтому, например (сравнить с (5.18а)),2!0!Ф1=( ν)[ ν(1, 2, 3) − ν(2, 3)] +3!(5.25)1!1!1!1!0!2!+[ ν(1, 2) − ν(2)] +[ ν(1, 3) − ν(3)] +[ ν(1) − ν(0)].3!3!3!Утверждение 5.8.
Численные значения компонент {Ф i , i∈N} векторадележа Шепли являются линейными комбинациями показателей конечного числа R-задач Парето- и Нэш-оптимизации, причём R удовлетворяетследующему соотношению:R N+1 = 2R N , при R 2 = 2.В конечном наборе R N при каждом фиксированном N имеет местоN – 1 задача Нэш-оптимизации. Доказательство следует из анализа выражений (5.18а), (5.23) – (5.25).Утверждение 5.9. При N = 2 в игре с постоянной суммой с характеристической функцией (5.3) вектор Шепли – обобщение максиминной цены.До к аз ат е льс тво . Имеем J 1 +J 2 = 0;n(1) =−(min max J1 ) ,max min J1 , n(2) =max min J 2 =max min( − J1 ) =Ф1 ( ν=)12212121ν (1,2) = max[J 1 +J 2 ] = max[0] = 0.При наличии равновесия=n(1) max min =J1 , n(2) min max J1 , поэтому ν (2) = – ν (1).1221Тогда из (5.24) имеем11Ф=[0 + ν(1) + ν(1)] , Ф=[0 + ν(2) + ν(2)] .1222Следовательно, вектор Шепли есть обобщение максиминной цены.
Если равновесие отсутствует, то11Ф1=[ ν(1) − ν(2)],Ф2=[ ν(2) − ν(1)]= −Ф1 .22Следовательно, вектор Шепли соответствует гарантирующей игре снулевой суммой Ф 1 +Ф 2 = 0.Утверждение 5.10. Вектор Шепли при общих свойствах Паретомножества и при любой характеристической функции обеспечивает на Па-184Стабильные эффективные решения и компромиссы.
Часть Iрето-границе ПНОК (Парето–Нэш-области компромиссов) сильную предпосылку дележа игры из условий:для задачи максимизации∑ Фi ( ν) =ν( N ) =max ∑ J i , i(5.26а)Фi ≥ ν(i ),i =1, N ;для задачи минимизации∑ Фi ( n) =n( N ) =min ∑ J i , i(5.26б)Фi ≤ n(i ),i =1, N .Рассмотрим метод вычисления вектора Шепли. Общая формула вычисления вектора Шепли имеет вид (5.23). Без ограничения общностирассуждений рассмотрим вариант (5.26б) для случая N = 2. Тогда формула вычисления вектора Шепли принимают вид (5.24), где ν (1,2) == min(J 1 +J 2 ) = J1′ + J 2′ – точка принадлежит Парето-множеству; ν (1),ν (2) – значение любой характеристической функции, например точкиНэша.Решим систему уравнений:1Ф1= 2 [ ν(1, 2) + ν(1) − ν(2)],Ф = 1 [ ν(1, 2) + ν(2) − ν(1)]. 2 2При замене ν (1,2) = J1′ + J 2′ тогда имеют место равенства(5.27)2Ф 1 = J1′ + J 2′ + ν (1) – ν (2),(5.28)2Ф 2 = J1′ + J 2′ + ν (2) – ν (1).Вычтем из уравнения (5.28) уравнение (5.27):2(Ф 2 – Ф 1 ) = 2( ν (2) – ν (1)),(5.29)Ф 2 – Ф 1 = ν (2) – ν (1),ν (2) – Ф 2 = ν (1) – Ф 1 ;Ф 2 и Ф 1 – координаты точки Шепли, ν (2) и ν (1) – координаты точкиНэша.Из (5.29) следует, что точка Шепли и точка Нэша являются диагонально противоположными вершинами квадрата.
Точка Шепли всегда лежитна линии, проведённой из точки Нэша под углом 45° к оси 0J 1 (линия снаклоном +1; J 2 = J 1 +b; b = const). Эту линию назовем линией равных выигрышей (см. рис. 5.1).Сложим уравнения (5.27) и (5.28):2(Ф 2 + Ф 1 ) = 2( ν (2) + ν (1)),Ф 2 + Ф 1 = ν (2) + ν (1),(5.30)Глава 5.
Оценка эффективности кооперативного компромисса185J 2′ – Ф 2 = Ф 1 – J1′ ;Ф 2 и Ф 1 – координаты точки Шепли, J 2′ и J1′ – координаты точки Парето.Из (5.30) следует, что точка Шепли и точка min( J1 + J 2 ) являются диагонально противоположными вершинами квадрата. Точка Шепли всегдалежит на линии, проведённой из точки min( J1 + J 2 ) под углом 135° к оси0J 1 , (линия с наклоном – 1; J 2 = – J 1 +b; b = const) (рис. 5.1).
Процедура независит от типа характеристической функции V.Точка Шепли лежит на пересечении линии, проведённой из точкиНэша с наклоном +1 (угол 45° к оси 0J 1 ) (линия равных выигрышей) с линией, проведённой из точки min( J1 + J 2 ) с наклоном – 1 (угол 135° к оси0J 1 ). Эти линии пересекаются под прямым углом. (рис. 5.1). Процедура независит от типа характеристической функции ν .Так как точка min( J1 + J 2 ) является точкой Парето-множества, то извышеприведённого доказательства следует, что точка Шепли в общем случае не принадлежит Парето-границе, а лежит «за ней», т.е. является недостижимой («утопической») точкой, так как лежит за областью допустимых значений показателей.В частном случае точка Шепли может принадлежать Паретомножеству в трёх случаях:• точка min( J1 + J 2 ) принадлежит линии равных выигрышей; тогда точкаmin( J1 + J 2 ) и точка Шепли совпадают, и точка Шепли принадлежитПарето-границе;• Парето-граница представляет собой прямую линию, составляющую сосью 0J 1 угол 1350, т.е.
с наклоном –1; тогда вся Парето-границасостоит из точек min( J1 + J 2 ) и перпендикулярна линии равныхвыйгрышей. Точка Шепли будет являться точкой min( J1 + J 2 ) ипринадлежать Парето-границе;• Парето-граница имеет такую форму, что имеется несколько точекmin( J1 + J 2 ), одна из которой является точкой Шепли.Во всех рассмотренных трёх случаях, если точка Шепли является точкой min( J1 + J 2 ), то тогда она (точка Шепли) принадлежит Паретогранице.Стабильные эффективные решения и компромиссы. Часть I186J2Парето-областьH ( nn(1) ; ( 2 ) )ПНОКmin(J1 +J 2 ) = n(1,2)Ш0Линия равныхвыиграшейпредпосылкаJ1Рис.
5.1. Геометрическая интерпретация получения точки Шепли при N = 2В общем случае имеем следующие соотношения:точка Нэша – равновесная точка, которая обладает свойствами устойчивости (стабильности);точка min( J1 + J 2 ) – точка Парето-множества, имеющая минимальныесуммарные равноприоритетные потери (максимальный суммарный выигрыш) систем, объединившихся в коалицию;точка Шепли – «априорно ожидаемое значение» – значение выигрышакаждого игрока, усреднённое по всем перестановкам, по всем возможнымкоалициям.Точка Шепли является способом оценки полезности возможноговступления в коалиционные связи.Утверждение 5.10 может быть обобщено на случай N ≥ 3.5.4.
ФОРМИРОВАНИЕ ДВУХЭТАПНОГО МЕТОДА ОПТИМИЗАЦИИ РЕШЕНИЙВ ММС НА ОСНОВЕ ВЕКТОРА ДЕЛЕЖА ШЕПЛИПолучение значений вектора Шепли позволяет сделать вывод о полезности кооперативного компромисса для объектов ММС.Следующей задачей становится выбор способа объединения объектов вкооперацию, реализующую выявленную дополнительную эффективность.Глава 5.
Оценка эффективности кооперативного компромисса187В общем случае основным является подход, связанный с объединениемресурсов, перестройкой оптимизационной структуры управления ММС,созданием новых технических средств поддержки и др.Ориентировкой реализации управляющих функций и параметров ММСв этом общем случае и вариантом реализации кооперативного компромисса при наличии практической полезной и мало меняющейся «при входе» вкооперацию математической модели ММС может служить выбор управлений и параметров состояний ММС, которые обеспечивают близость показателей цели ММС к полученным значениям вектора Шепли.В таком случае может быть сформирован алгоритм оптимизации решений, состоящий из следующих двух этапов.Эт а п 1.
Определение значений вектора дележа Шепли {Ф i , i∈N} наоснове выражений (5.23), которые для N = 2,3 приведены в (5.24), (5.25).Если при решении задачи этапа 1 применяются (5.1), (5.3), то данныйнабор задач может быть решён с помощью ПС «MOMДИС» (см. гл. 9), всоставе которой реализованы модули Парето- и Нэш- оптимизации.При неединственности вектора Шепли, вызванной возможной неединственностью решения задач Парето–Нэш-оптимизации, в качестве дополнительного подэтапа возникает задача определения дополнительного компромисса на основе групповой неудовлетворённости (см. гл.6 – частныйслучай СТЭК-14 (6.53)).Теперь Ф*∈{Ф} выбирается из условия(5.31)min ∑ [Фi − J i* ]2 → Ф * ,Фгде J* = {J i∗ ;i∈N},J* – идеальная точка векторной оптимизации [246].188Стабильные эффективные решения и компромиссы.
Часть IДвухэтапный метод параметрической оптимизации управления ММСна основе вектора дележа Шепли1 этап: определение значений вектора дележа Шепли на основеПарето–Нэш-оптимизацииАлгоритм Парето-оптимизации (глава 3) –модуль ПС МОМДИСЛП-поиск (вычисление вектора параметров q)Вычисление значений целевого вектора JПарето-оптимизация значений целевого вектора JВычисление min ∑ J iВычисление Нэш-равновесия (глава 2) – модуль ПСМОМДИСВычисление значений вектора дележа Шепли Ф –модуль ПС МОМДИС2 этап: векторная оптимизация управления коалициями для минимизацииотклонения от точки Шепли на основе Ω-оптимизации (глава 3) –модуль ПС МОМДИСРис. 5.2.
Структурная схема двухэтапного метода параметрической оптимизацииуправления ММС на основе вектора дележа ШеплиЭт а п 2. Целью данного этапа является решение относительно управлений системы функциональных уравнений J i=( u) Фi∗ , i ∈ N ;(5.32)x f ( x, u, t ), u ∈ U , x(t0=) x0 .=Данная система может быть приведена к обычной форме задачи оптимизации. С учётом параметризации ПКЗУ и параметрическим уточнениемкооперативной структуры ММС задача оптимизации принимает видГлава 5. Оценка эффективности кооперативного компромисса189min ∑ [ J i − Фi∗∗]2 или J i =[ J i − Фi ], i =1, N , → min;qqxi∈N()x, q, u ( q, x, t ) , t , x(t0 ) x 0 ;f=(5.33)q ∈ Q; q ∈ Q; u ∈ U .Для решения задачи определения параметризованного программногоуправления и ПКЗУ применяется модуль Ω-оптимизации ПС «МОМДИС».На рис. 5.2 дана структурная схема двухэтапного алгоритма Шеплиоптимизации ММС.5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
