WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Министерство образования Российской Федерации Ростовский ордена Трудового Красного Знамени государственный университет С.В.Гусаков, Л.Н.Землянухина, А.Б.Зинченко, Л.И.Сантылова МЕТОДИЧЕСКИЕ УКАЗАНИЯ по курсу "Методы оптимизации" для студентов механико-математического факультета дневного и вечернего отделения ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И СМЕЖНЫЕ ВОПРОСЫ Часть 7 Ростов-на-Дону 2001 2 Методические указания рекомендованы к печати заседанием кафедры исследования операций механикоматематического факультета РГУ протокол № 1 от 1 февраля 2001 г.

3 ОГЛАВЛЕНИЕ 10. ЭЛЕМЕНТЫ ТЕОРИИ КООПЕРАТИВНЫХ ИГР (продолжение)............................................. 4 10.5 Параметрическое представление С-ядра................. 4 10.6. Значения игр (цена Шепли, N-ядро).................... 8 10.7. Методы вычисления N –ядра.........................15 10.8. Выпуклые игры.....................................18 10.9. Упражнения........................................22 Индивидуальные задания.................................23 Литература............................................. 25 Приложение (метод нахождения всех вершин многогранника).. 26 4 10. ЭЛЕМЕНТЫ ТЕОРИИ КООПЕРАТИВНЫХ ИГР (продолжение) В части 5 методических указаний была описана основная концепция решения кооперативной игры – ее С-ядро. В данной части изложен способ нахождения всех вершин С-ядра, рассмотрены другие понятия решения, описан специальный класс игр, часто возникающих при моделировании экономических процессов.

10.5. Параметрическое представление С-ядра Для исчерпывающего описания непустого С-ядра нужно перейти от аналитического его задания xi (S), SN ; xi = ( N ) (1) iS iN к параметрической форме c C() = i xi, i=c где x1,…, xc – вершины С-ядра, 1,…,c – параметры, i = 1.

i = Параметрическая форма представления С-ядра позволяет определить диапазоны изменения выигрышей игроков xi = xij, x = xij, i = 1, n, i min max 1 j c 1 j c c c а также центр С-ядра (( x1j ) / n,...,( xnj ) / n), который можно j=1 j=выбрать в качестве компромиссного дележа прибыли.

Существует два основных подхода к нахождению всех вершин многогранника: симплициальный (использующий симплекс-таблицы) и метод свертки систем линейных неравенств. При симплициальном подходе перебираются все допустимые базисы (их количество может быть намного больше количества вершин), поэтому в приложении рассмотрен второй метод, позволяющий также выделить избыточные ограничения и найти направляющие векторы неограниченных ребер для неограниченных многогранных множеств. Этот метод может быть полезен и для других приложений, например, для поиска всех оптимальных опорных решений задачи линейного программирования, при многокритериальной оптимизации и т.д.

Пример 1 ("Озеро" [1]). Вокруг озера расположено n предприятий. Обработка стоков перед их сбросом в озеро стоит каждому предприятию В (денежных единиц), а очистка воды для собственных нужд стоит µ А, где µ - число предприятий, не обрабатывающих свои отходы. Считая, что А <В < nА, s =S, получаем -snA, s B / A, (S) = (2) -sB - s(n - s) A, s > B / A.

В этой игре нужно узнать, смогут ли предприятии договориться об обработке отходов.

Положим n=3, А =10, В =25. Тогда (1)= (2) = (3) = -30, (12) = (13) = (2,3)= -60, (12,3)= -75.

,,, С-ядро задается условиями x1 -30, x2 -30, x3 -30, x1+ x2 -60, x1+ x3 -60, x2 + x3 -60, x1+ x2 + x3= -75, после преобразования которых получаем систему -30 x1 -15, -30 x2 -15, -60 x1+ x2 -45, множеством решений которой является заштрихованный треугольник (рис. 1) с вершинами x1=(-30, -30, -15), x2 =(-30, -15, -30), x3=(-15, -30, -30).

Параметрическая форма С-ядра имеет вид С( )= -30 (1 + 2 + 3 / 2, 1 + 2 / 2 + 3, 1 / 2 + 2 + 3), где 1,2,30, 1+2 +3=1.

Центром С-ядра является точка (-25, -25, -25) (см. рис.1) равномерного распределения величины (12,3)= -75.

, Рис.1. С-ядро игры " Озеро".

Пример 2. П редставим в параметрической форме С-ядро следующей игры пяти лиц: N = { 1, …, 5 } ; v(N)=12;

v(1,2,3)=v(3,5)=3; v(1,3,4)=v(2,4,5)=v(1,2,4,5)=9;

v(S)=3 для собственных коалиций, содержащих { 1,2,3} или {3,5};

v(S)=9 для собственных коалиций, содержащих { 1,3,4} или { 2,4,5} ;

v(S)=0 для остальных коалиций.

Неравенства системы (1), соответствующие v(S), где S N и S{ 1,2,3} или S{3,5} или S{ 1,3,4} или S{ 2,4,5}, а также v(S)=0, S>1, являются следствием остальных ограничений. Их исключаем из рассмотрения. Остальные неравенства системы (1) умножаем на (-1). Уравнение xi = ( N ) заменяем двумя неравенства iN ми xi v( N ), - xi -v( N ).

iN iN Получаем систему - x1- x2 - x3 -3, - x3- x5 -3, - x1- x3- x4 -9, - x2 - x4- x5 -9, - x1- x2 - x3- x4- x5 -12, x1+ x2 + x3+ x4+ x5 12; xi 0, i = 15.

, Применив описанный в приложении метод, находим вершины С-ядра x1=(0, 3/2, 3/2, 15/2, 3/2), x2 =(3, 0, 0, 6, 3), x3=(0, 3, 3, 6, 0), x4 =(0, 0, 3, 6, 3), x5=(0, 0, 3, 9, 0), границы изменения выигрышей игроков xi =0, i = 15; x = x = x = x =3, x =9,, 1 2 3 5 а также центр (0.6, 0.9, 2.1, 6.9, 1.5) С-ядра.

Параметрическое представление С-ядра данной игры имеет вид C() = (32, 31 / 2 + 33, 31 / 2 + 3(3 + 4 + 5), 151 / 2 + 6(2 + 3 + 4 ) + 95, 31 / 2 + 3(2 + 4 )), где 1,…,50, 1+…+5=1.



10.6. Значения игр (цена Шепли, N -ядро) С-ядро игры может быть очень большим, например, совпадать с множеством всех дележей, а может быть и пустым. Пустота С-ядра наблюдается в том случае, когда промежуточные коалиции слишком сильны, но из этого не следует невозможность кооперации всех игроков. Если кооперативное равновесие не может быть достигнуто только с помощью простых коалиционных угроз (принцип С-ядра), то необходимы другие принципы, например, тактика угроз и контругроз [3].

В идеальном случае анализ кооперативной игры должен был бы приводить к отбору единственного дележа, который и следовало бы принять за решение.

Правило, ставящее в соответствие каждой кооперативной игре единственное распределение x =( x1,…, xn ) совместной прибыли (N), удовлетворяющее некоторому принципу оптимальности, называется оператором значения, а само распределение x - значением игры. Наиболее популярными значениями, показавшими свою применимость к широкому кругу экономических моделей, являются: цена Шепли ( значение Шепли или вектор Шепли) и N-ядро (nucleolus).

Эти понятия отражают два основных условия, необходимых для устойчивости кооперативного соглашения [2]:

- каждый участник договора должен получить "справедливую" долю прибыли (внутренняя устойчивость);

- прибыль от кооперации не должна быть слишком мала по сравнению ситуацией без кооперации (внешняя устойчивость).

Цена Шепли учитывает дополнительные прибыли (S{i}) - (S) ( iS, SN ) от присоединения фиксированного участника к каждой коалиции, т.е. обеспечивает внутреннюю устойчивость.

N-ядро, по возможности, максимизирует суммарный доход каждой коалиции, т.е. гарантирует внешнюю устойчивость, игнорируя устойчивость внутреннюю.

Цена Шепли = (1,..., n ) приписывает каждому игроку его средний вклад во все коалиции и вычисляется по формуле s!(n - s - 1)! i = [(S {i}) - (S)], i = 1,n, n! S N \i где s = S.

Например, в игре трех лиц (n=3) цена Шепли имеет вид 1 = (1) / 3 + [(1,2) - (2) + (1,3) - (3)] / 6 + [(1,2,3) - (2,3)] / 3, 2 = (2) / 3 + [(12) - (1) + (2,3) - (3)] / 6 + [(12,3) - (13)] / 3,,,, 3 = (3) / 3 + [(2,3) - (2) + (1,3) - (1)] / 6 + [(1,2,3) - (1,2)] / 3.

Для простой игры n лиц общая формула цены Шепли упрощается и принимает вид s!(n - s - 1)! i = (s) =, i = 1,n, n! Si S i где i – множество таких проигрывающих коалиций S, не содержащих игрока i, что коалиция S {i } является выигрывающей.

По этой формуле легко вычисляется цена Шепли взвешенных мажоритарных игр.

Пример 3. Четыре акционера обладают следующим количеством акций: 40, 30, 20, 10. Любое решение утверждается акционерами, имеющими простое большинство акций. Это взвешенная мажоритарная игра (51; 40, 30, 20, 10), в которой выигрывают коалиции {1,2}, {1,3}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.

Определяем 1={{2}, {3}, {2,3}, {2,4}, {3,4}}, 2 ={{1}, {1,4}, {3,4}}, 1!(4 - 1 - 1)! 3={{1}, {1,4}, {2,4}}, 4 ={2,3}. Так как (1) = = и 4! i 2!(4 - 2 - 1)!,, (2) = =, то i =, i = 12,34. Окончательно 4! 12 5 3 3 получаем =(,,, ).

12 12 12 Цена Шепли не совпадает с "вектором голосования" 4 3 2 (,,, ), в котором выигрыш игрока пропорционален его доле 10 10 10 акций. В отношении цены Шепли, игроки 2 и 3 обладают одинаковой силой (несмотря на разное количество акций они имеют одинаковые возможности для образования коалиций). Сила игрока 1 больше доли его акций, а сила игрока 4, наоборот, меньше доли акций.

Предположим теперь, что игрок 3 приобрел еще 10 акций, т.е. рас1 1 смотрим игру (55; 40, 30, 30, 10). Ее цена Шепли =(,,, 0 ) 3 3 4 3 3 также не совпадает с "вектором голосования" (,,, ) и пока11 11 11 зывает, что дополнительные акции игрока 3 не дают ему преимуществ, а акции игрока 4 обесцениваются (он не может войти ни в одну коалицию, т.е. становится "болваном").

Цена Шепли обладает следующими свойствами.

1. i = (i), i = 1,n, где ((1),...,(n)) – перестановка N, т.е. цена любого игрока не зависит от его номера (аксиома анонимности).

2. Если игрок i ничего не добавляет к каждой коалиции, т.е.

(S {i}) = (S) для любого S N ( такой игрок называется "болваном"), то его цена равна нулю i = 0 (аксиома болвана).

3. Цена Шепли является коалиционно монотонной, т.е. если прибыль (S) некоторой коалиции S увеличить, а прибыли всех остальных коалиций оставить без изменения, то цена i каждого игрока коалиции S не уменьшиться.

4. В симметричной игре цена Шепли делит (N) на n равных частей = (( N ) / n,..., ( N ) / n).

5. Цена Шепли может не принадлежать непустому С-ядру.

Пример 4 ("Рынок перчаток" [2]).

Случай 1. Два игрока (1 и 2) имеют по одной правой перчатке, а два остальных игрока (3 и 4) имеют по одной левой перчатке. Рыночная цена одной перчатки равна нулю, а цена одной пары (с одной правой и одной левой) равна единице.

Эта ситуация описывается игрой , где N={1,2,3,4}, (1,3)= (1,4)=(2,3)= (2,4)=(1,2,3)= (1,2,4)=(1,3,4)=(2,3,4)=1, (1,2,3,4)=2, (S) =0 для остальных S.

С-ядро (без учета избыточных ограничений) задается системой x1+ x31, x1+ x4 1, x2 + x31, x2 + x4 1, x1+ x2 + x3+ x4 =2, x 0.

Оно имеет две вершины x1=(1, 1, 0, 0) и x2 =(0, 0, 1, 1), т.е. является отрезком.

Игра симметрична, поэтому цена Шепли =(1/2, 1/2, 1/2, 1/2) совпадает с равномерным распределением прибыли, - центр С-ядра.





Случай 2. Предположим теперь, что игрок 1 имеет две правые перчатки, в то время как остальные игроки располагают прежними запасами. Тогда (1,3)= (1,4)=(2,3)= (2,4)=(1,2,3)= (1,2,4) =(2,3,4)=1, (1,3,4)=(1,2,3,4)=2, (S) =0 для остальных S, т.е. собственная прибыль коалиции {1,3,4} увеличилась на единицу.

С-ядро игры задается системой x1+ x31, x1+ x41, x2+ x31, x2+ x41,, x1+ x3+ x42, x1+ x2+ x3+ x4=2, x 0.

Оно состоит из единственного дележа x0= (0, 0, 1, 1), при котором всю прибыль делят владельцы левых перчаток.

Цена Шепли =(7/12, 3/12, 7/12, 7/12) увеличивает долю первого, третьего и четвертого игроков, чьи коалиционные возможности возросли, уменьшая долю второго игрока. В данном случае цена Шепли не принадлежит С-ядру. Заметим, что рассмотренный пример иллюстрирует также немонотонность С-ядра.

В отличие от цены Шепли, N-ядро = (1,..., ) всегда принадn лежит непустому С-ядру. Оно занимает центральное место внутри Сядра.

Для определения N –ядра вводится понятие эксцесса e(x,S) = xi - (S), iS который является "мерой неудовлетворенности" коалиции S дележом x.

Положительный (отрицательный) эксцесс e(x,S) есть дополнительная прибыль (убыток) коалиции S по сравнению с ее собственной возможностью (S). Для каждой коалиции S желательно, чтобы значение эксцесса e(x,S) было как можно больше.

Каждому дележу x ставиться в соответствие вектор эксцессов e(x) =(e(x, S1),e(x, S2),...,e(x, Sm)), компонентами которого являются упорядоченные по неубыванию эксцессы собственных коалиций e(x, S1) e(x, S2 )... e(x, Sm ), m = 2n - 2 ; Si 2N \ N \, i = 1, m.

Ясно, что дележ x принадлежит С-ядру тогда и только тогда, когда его вектор эксцессов неотрицателен.

Вычислим, например, вектор эксцессов для цены Шепли =(7/12, 3/12, 7/12, 7/12) игры "Рынок перчаток" (случай 2). Определяем вначале эксцессы собственных коалиций e(,{1})=e(,{3}) =e(,{4}) =7/12, e(,{2}) =3/12, e(,{12})=10/12,, e(,{13})=e(,{14})=2/12, e(,{2,3}) =e(,{24}) = -2/12,,,, e(,{34}) =14/12, e(,{12,3})=e(,{12,4})=5/12,,,, e(,{134})= -3/12, e(,{2,3,4}) =5/12.

,, Упорядочивая эти величины по неубыванию получаем e() =(e(,{134}),e(,{23}),e(,{24}),e(,{13}),e(,{14}),,,,,,, e(,{2}),e(,{12,3}),e(,{12,4}),e(,{2,3,4}),e(,{1}),e(,{3}),,, e(,{4}),e(,{12}),e(,{34}) )=,, =(-3/12, -2/12, -2/12, 2/12, 2/12, 3/12, 5 /12, 5/12, 5/12, 7/12, 7/12, 7/12, 10/12, 14/12).

Вектор эксцессов единственной точки x0=(0, 0, 1, 1) С-ядра этой же игры имеет вид e(x0 ) = (e(x0,{1}), e(x0,{2}), e(x0,{12}), e(x0,{13}), e(x0,{14}),,,, e(x0,{23}), e(x0,{24}), e(x0,{12,3}), e(x0,{12,4}), e(x0,{134}),,,,,,, e(x0,{3}), e(x0,{4}), e(x0,{34}))=(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2).

, На множестве E = {e(x): x D()} векторов эксцессов дележей игры Г вводится лексикографическое упорядочение p.

Говорят, что вектор e(x) предшествует e( y) (или e( y) предпочтительнее e(x) в смысле лексикографического порядка) e(x) p e( y), если существует такая коалиция Sk, что k e(x, Si ) =e( y, Si ), i = 1, k - 1, e(x, S ) < e( y, Sk ).

Так, например, для вычисленных выше векторов эксцессов e() и e(x0 ) имеем e() p e(x0 ).

Доказано, что существует единственный дележ, вектор эксцессов e( ) которого предпочтительнее всех остальных векторов из E e( ) =lexmax e(x). (3) e( x)E Это и есть N-ядро.

Как и цена Шепли, N-ядро удовлетворяет аксиомам анонимности и болвана, но не является коалиционно монотонным. Поэтому возможен случай, когда увеличение величины (N) при сохранении прибылей (S) всех остальных коалиций S N, приводит к уменьшению доли прибыли некоторых игроков. Это очень непривлекательное свойство, т.к. если какие-либо игроки страдают в результате улучшений, то они могут отказаться от участия и тем самым сделать невозможным улучшение ситуации.

Однако, для n5 не существует такого значения кооперативной игры, которое одновременно принадлежит С-ядру и является коалиционно монотонным (теорема Янга [2]).

10.7. Методы вычисления N -ядра Если известны вершины x1,…, xc С-ядра, то N-ядро вычисляется по формуле c i = ( xij ) / c, i = 1, n, j=т.е. является средним арифметическим вершин.

В примере "Рынок перчаток" (случай 1) имеем =( x1+ x2)/2=(1/2, 1/2, 1/2, 1/2), т.е. N-ядро совпадает с ценой Шепли. В примере "Рынок перчаток" (случай 2) С-ядро состоит из единственной точки, которая является также и N-ядром =(0, 0, 1, 1).

Если вершины С-ядра вычислить сложно или С-ядро пустое, то Nядро можно определить с помощью серии задач линейного программирования.

Из соотношения (3) вытекает, что вначале нужно определить min e(, S) = max [ min e(x, S)], S N xD() S N т.е. максимизировать минимальную коалиционную прибыль. После введения дополнительной переменной z получаем задачу max z, (4) z xi - (S), S N, (5) iS xi = ( N ). (6) iN Если задача (4)-(6) имеет единственное решение, то соответствующий дележ есть N-ядро. В противном случае, нужно выбрать произвольное оптимальное решение (z *, x *) и определить множество коалиций ={S1,..., Sl }, для которых неравенства (5) выполняются как равенства при z= z *, x = x *.

Новая задача имеет вид max z, z xi - (S), S N, S, iS z * xi - (S ), j = 1, l, j iS j xi = ( N ), iN т.е. максимизируется вторая по минимальности коалиционная прибыль.

Через конечное число шагов получается задача линейного программирования, имеющая N-ядро в качестве единственного решения.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.