WWW.DISSERS.RU

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

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


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

3 ОГЛАВЛЕНИЕ 13. ДИСКРЕТНЫЕ КООПЕРАТИВНЫЕ ИГРЫ............. 4 13.1. Основные понятия............................. 4 13.2. Примеры дискретных кооперативных игр........... 6 13.3. С-ядро дискретной кооперативной игры.............10 13.4. Упражнения................................... 21 13.5. Индивидуальные задания........................23 Литература......................................... 24 4 13. ДИСКРЕТНЫЕ КООПЕРАТИВНЫЕ ИГРЫ Кооперативные игры, описанные в методических указаниях [1,2], не могут моделировать экономические ситуации, в которых разыгрываются неделимые виды ресурсов или продукции. Стоимостное выражение этих величин не решает проблему, так как выигрыши должны принимать значения, принадлежащие дискретному множеству. В данной части методических указаний рассматриваются дискретные кооперативные игры, дополняющие теорию классических кооперативных игр.

13.1. Основные понятия Дискретная кооперативная игра < N, >, как и классическая, определяется множеством игроков N ={1, 2,…, n}, n 3, и супераддитивной характеристической функцией ()=0, (ST) (S) + (T), ST=, но функция должна быть целочисленной : 2N Z+, где Z+ - множество неотрицательных целых чисел. Предполагается, что побочные платежи между членами любой коалиции измеряются целыми числами.

Исходом или дележом дискретной игры называется вектор x = ( x1,…, xn), удовлетворяющий условиям x1 + … + xn = (N), xi (i), iN, xi - целые, iN, (N), (i), iN, – целые числа.

Любую дискретную игру можно привести к 0-редуцированной форме, когда (i) = 0, iN;

(S) 0, S N.

Формула перехода к 0-редуцированной игре имеет вид (S) = (S) - (i), S N.

iS Если x = (x1,..., xn ) – дележ игры < N, >, то x = (x1,..., xn ), где xi = xi + (i), iN, является дележом исходной игры < N, >.

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

Для 0-редуцированной дискретной игры множество дележей определяется системой x1 + … + xn = (N), xi 0, iN, xi - целые, iN, (N) – целое число, то есть является множеством целочисленных точек симплекса с вершинами x1= ((N), 0, …, 0), x2= (0, (N), 0, …, 0), …, xn = (0, …, 0, (N)).

Следовательно, множество дележей дискретной кооперативной игры не пусто.

Дискретную кооперативную игру < N, > будем обозначать через ГZ = < N, >, а соответствующую ей недискретную игру (то есть игру с тем же множеством игроков N и той же характеристической функцией, допускающую нецелочисленные дележи) будем обозначать через ГR = < N, > и называть релаксированной к ГZ игрой или просто релаксированной игрой.

Множество дележей дискретной игры ГZ будем обозначать через DZ(), а множество дележей релаксированной игры ГR будем обозначать через DR (). Ясно, что DR () является выпуклой оболочкой точек множества DZ(), то есть DR () = conv DZ().

13.2. Примеры дискретных кооперативных игр Пример 1(Распределение неделимой продукции).

Несколько предприятий, специализирующихся по сборке, поставке комплектующих, закупке сырья и т.п. для дорогостоящей продукции неделимого типа, решили создать кооперативное объединение. Для каждой группы предприятий S ={ i1, …, in } известно максимальное количество готовой продукции a(S), которую они могут произвести, работая совместно в течение данного отрезка времени. Все предприятия заинтересованы производить взаимные расчеты путем перераспределения конечного продукта.

Поскольку каждый участник кооперативного объединения заинтересован в увеличении своей доли прибыли, компромиссное решение вырабатывается в результате переговоров. Базой для переговоров может служить множество альтернатив, полученных с помощью кооперативной игры ГZ с характеристической функцией (S) = a(S) S N.

Положим, например, n = 3, a(1) = 2, a(2) = 1, a(3) = 3, a(1,2) = 4, a(1,3) = 8, a(2,3) = 6, a(1,2,3) = 10.

После перехода к 0-редуцированной форме, получаем дискретную игру с характеристической функцией (i) = 0, i=1,2,3;

(1,2) = 1, (1,3) = 3, (2,3) = 2, (1,2,3) = 4.

Графическая иллюстрация множества дележей DR() релаксированной игры приведена на рис.1 (заштрихованная область).

Дележами рассматриваемой дискретной игры являются целочисленные точки множества DR ().

Графическая иллюстрация множеств DR () и DZ() для примера Рис. 1.

Пример 2 ( Упаковка в контейнеры).

Каждый из n игроков имеет некоторое количество груза и владеет контейнерами (вагонами, рефрижераторами и т.п.), в которых этот груз перевозится. Предполагается, что игроки могут перевести свои грузы, пользуясь только собственными контейнерами.

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



Характеристическая функция игры имеет вид (S) = k(S) S N, где k(S) – количество контейнеров, необходимых для перевозки грузов коалиции S.

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

Для игры Упаковка в контейнеры получаем (S) = - k(S) S N.

Положим, например, n = 3, k(1) = 3, k(2) = 2, k(3) = 3, k(1,2) = 4, k(1,3) = 5, k(2,3) = 5, k(1,2,3) = 6.

После перехода к 0-редуцированной форме, получаем дискретную кооперативную игру с характеристической функцией (i) = 0, i=1,2,3;

(1,2) = 1, (1,3) = 1, (2,3) = 0, (1,2,3) = 2.

Пример 3 (Игра Мусор).

У каждого из n игроков имеется мешок с мусором, который он должен выбросить во дворе у кого-то другого. Нужно выяснить, сумеют ли игроки достичь соглашения о размещении мусора.

Характеристическая функция игры имеет вид 0, S = 0, (S) = - S, 0 < S < n, n n, S = n.

После перехода от задачи распределения убытков, к задаче дележа прибыли, получаем 0, S = 0, (S) = (n - S ), 0 < S < n, S = n.

- n, В недискретном варианте этой симметричной игры, предложенном Шепли и Шубиком [3], одному мешку с мусором присваивалась полезность, равная (-1), однако, более естественно игру Мусор считать дискретной. Ниже будут рассмотрены различные подходы к ее решению.

13.3. С-ядро дискретной игры Как уже говорилось в предыдущих методических указаниях [1,2], в теории кооперативных игр нет единой концепции решения, но основным считается понятие С-ядра.

Существует два подхода к определению С-ядра классической (недискретной) кооперативной игры.

Подход первый (для ГR ). На множестве всех дележей DR() игры ГR вводится отношение доминирования.

Говорят, что дележ x1=(x1,..., x1 ) доминирует дележ n 2 x2=(x1,..., xn ) (записывается x1 f x2), если существует такая коалиция S N, что 1. xi (S), iS 2. xi > xi2, iS.

Множество всех недоминируемых дележей недискретной кооперативной игры ГR называется ее С -ядром.

Будем обозначать С-ядро игры ГR через СR (), то есть СR () = DR () \ dom DR (), где dom DR () – множество дележей, каждый из которых доминируется некоторым дележом из DR ().

Подход второй (для ГR ). С-ядро определяется, как множество решений линейной системы.

С - ядром недискретной кооперативной игры ГR называется множество векторов x = ( x1,…, xn), удовлетворяющих следующим условиям:

условию индивидуальной рациональности, которое для 0-редуцированных игр становиться условием неотрицательности переменных xi 0, iN, (1) условию оптимальности по Парето xi = (N), (2) iN условию групповой рациональности xi (S), 1 < S < n, S N. (3) iS Неоднозначность определения С-ядра недискретных кооперативных игр не вызывает трудностей, так как эти определения эквивалентны, то есть справедлива следующая теорема.

Теорема 1. Вектор x Rn принадлежит множеству недоминируемых дележей недискретной игры ГR в 0– редуцированной форме тогда и только тогда, когда он удовлетворяет условиям (1), (2) и (3).

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

Подход первый ( для ГZ ). Пусть С*Z () – множество недоминируемых дележей дискретной игры ГZ, то есть С*Z () = DZ() \ dom DZ(), где dom DZ() – множество дележей, каждый из которых доминируется некоторым дележом из DZ().

Рассмотрим два дележа x1 и x2 игры ГZ. Если дележ xдоминирует дележ x2, то есть x1 f x2, то из условий xi > xi2, iS;

xi, xi2 - целые, iS следует, что 1 xi xi2+ 1, iS, xi2 + S xi (S) iS iS xi2 (S) - S.

iS Так как левая и правая части последнего неравенства целочисленны, то получаем, что доминироваться могут только дележи, удовлетворяющие условию xi2 < (S) - S + 1.

iS Следовательно, условие недоминируемости дележа задается системой xi (S) - S + 1, S N.

iS Это условие является также и необходимым условием недоминируемости дележа, то есть справедлива следующая теорема.

Теорема 2. Вектор x Rn принадлежит множеству недоминируемых дележей дискретной игры ГZ в 0-редуцированной форме тогда и только тогда, когда он удовлетворяет условиям xi (S) - S +1, 1 < S < n, S N, (4) iS xi = (N), (5) iN xi 0, iN, (6) xi - целые, iN, (7) (S) - целое число, S N.

Подход второй ( для ГZ ). Так как множество дележей дискретной игры есть подмножество целых точек множества дележей релаксированной игры, то естественно определить С-ядро дискретной игры как подмножество целых точек С-ядра релаксированной игры, то есть как множество решений системы xi (S), 1 < S < n, S N. (8) iS xi = (N), (9) iN xi 0, iN, (10) xi - целые, iN, (11) (S) - целое число, S N.

Множество решений системы (8) - (11) обозначим через СZ ().

Сравнив системы (4) – (7) и (8) – (11), определяющие множества С*Z () и СZ (), получаем, что СZ () С*Z ().

Найдем множества С*Z () и СZ () для конкретных дискретных игр.

1. Игра Распределение неделимой продукции (см. пример 1, стр. 6 -7 ).

0-редуцированная характеристической функции имеет вид (i) = 0, i=1,2,3;

(1,2)=1, (1,3)=3, (2,3)=2, (1,2,3)=4.

Множество С*Z () определяется системой x1 + x2 0, x1 + x3 2, x2 + x3 1, x1 + x2 + x3 = 4, x1, x2, x3 0, x1, x2, x3 - целые.





После исключения переменной x3 получаем x1 + x2 4, x1 3, x2 2, x1, x2 0, x1, x2 - целые.

Из рисунка 2 видно, что множество С*Z () состоит из 11 точек С*Z () = {(0,0,4), (1,0,3), (2,0,2), (3,0,1), (0,1,3), (1,1,2), (2,1,1), (3,1,0), (0,2,2), (1,2,1), (2,2,0)}.

Графическая иллюстрация множества С*Z () для примера Рис.2.

Множество СZ () определяется системой x1 + x2 1, x1 + x3 3, x2 + x3 2, x1 + x2 + x3 = 4, x1, x2, x3 0, x1, x2, x3 - целые.

После исключения переменной x3 получаем 1 x1 + x2 4, x1 2, x2 1, x1, x2 0, x1, x2 - целые.

Из рисунка 3 видно, что множество СZ () состоит из 5 точек СZ () = { (1,0,3), (2,0,2), (0,1,3), (1,1,2), (2,1,1) }.

Графическая иллюстрация множества СZ () для примера Рис.3.

В данном примере С*Z () СZ ().

Для исходной (не 0-редуцированной игры) с характеристической функцией имеем С*Z () = {(2, 1, 7), (3, 1, 6), (4, 1, 5), (5, 1, 4), (3, 2, 5), (4, 2, 4), (5, 2, 3), (5, 2,3), (2, 3, 5), (3, 3, 4), (4, 3, 3)}.

СZ () = { (3, 2, 6), (4, 1, 5), (2, 2, 6), (3, 2, 5), (4, 2, 4) }.

Рассмотрим точки, принадлежащие разности множеств С*Z () \ СZ ():

x1= (20,10,70), x2= (50,10,40), x3 = (50,20,30), x4 = (20,30,50), x5= (30,30,40), x6 = (40,30,30).

j Любой из дележей x, j =1,…,6, хотя и не доминируется другими дележами из DZ(), является дискриминирующим по крайней мере для одной из коалиций, приписывая ей доход, меньший, чем ее собственные коалиционные возможности. Например, xi = 3 < (1,2) = 4, xi2 = 5 < (2,3) = 6 и т. д.

i{1,2} i{2,3} Эти коалиции будут возражать против соответствующих исходов игры, так как существуют пять дележей из множества СZ(), удовлетворяющих минимальным требованиям всех коалиций.

2. Игра Упаковка в контейнеры (см. пример 2, стр. 8-9).

0-редуцированная характеристической функции имеет вид (i) = 0, i=1,2,3;

(1,2)=1, (1,3)=1, (2,3)=0, (1,2,3)=2.

Графическая иллюстрация множества СZ () для примера Рис.4.

Множество С*Z () определяется системой x1 + x2 0, x1 + x3 0, x2 + x3 -1, x1 + x2 + x3 = 2, x1, x2, x3 0, x1, x2, x3 - целые.

После исключения переменной x3 получаем x1 + x2 2, x1, x2 0, x1, x2 - целые.

В данном примере множество С*Z () совпадает с множеством всех дележей DZ() и состоит из 6 точек С*Z () ={ (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1) }.

Множество СZ () определяется системой x1 + x2 1, x1 + x3 1, x2 + x3 0, x1 + x2 + x3 = 2, x1, x2, x3 0, x1, x2, x3 - целые.

После исключения переменной x3 получаем 1 x1 + x2 2, x2 1, x1, x2 0, x1, x2 - целые.

Из рисунка 4 видно, что множество СZ () состоит из 4 дележей СZ () ={ (2,0,0), (1,1,0), (1,0,1), (0,1,1) }.

Возвращаясь к исходной игре с характеристической функцией, получаем С*Z () = { (1,2,3), (3,0,3), (3,2,1), (2,1,3), (2,2,2), (3,1,2) }, СZ () = { (1,2,3), (2,1,3), (2,2,2), (3,1,2) }, С*Z () \ СZ () = { (3,0,3), (3,2,1) }.

Рассмотрим, например, дележ (3,0,3) С*Z () \ СZ ().

Согласно этому исходу игры, коалиция {1,3} должна выделить контейнеров, хотя свой груз она может упаковать в 5 контейнеров.

Следовательно, коалиция {1,3} будет возражать против дележа (3,0,3).

3. Игра Мусор (см. пример 3, стр. 9).

Положим n=3, тогда характеристической функции игры будет иметь вид (1) = (2) = (3) = 2, (1,2) = (1,3)= (2,3) = 1, (1,2,3) = 3.

После перехода от игры с распределением убытков к 0-редуцированной форме игры с дележом прибыли, получаем (i) = 0, i=1,2,3;

(1,2) = (1,3) = (2,3) = 3, (1,2,3)= 3.

Множество С*Z () определяется системой x1 + x2 2, x1 + x3 2, x2 + x3 2, x1 + x2 + x3 = 3, x1, x2, x3 0, x1, x2, x3 - целые.

После исключения переменной x3 получаем 2 x1 + x2 3, x1 1, x2 1, x1, x2 0, x1, x2 - целые.

В данной игре С*Z () = С*Z () = { (1,1,1) }, СZ () = СZ () =.

Было доказано (методические указания [2], стр. 17), что С-ядро релаксированной игры тоже не существует СR () =.

Поскольку в игре Мусор (для трех игроков), множество недоминируемых дележей С*Z () состоит из единственного дележа { (1,1,1) }, а множество СZ () пустое, то, скорее всего, такой исход игры будет одобрен всеми коалициями.

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

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

Находить все недоминируемые дележи С*Z () имеет смысл только в случае пустоты С-ядра СZ ().

13.4. Упражнения Упражнение 1. Каким условиям должна удовлетворять характеристическая функции дискретной кооперативной игры с распределением убытков.

Упражнение 2. Привести пример дележа из множества С*Z (), доминирующего дележ (6, 1, 3) для игры Распределение неделимой продукции (см. стр.6-7, 14-17).

Упражнение 3. Получить формулы перехода от дележей из множеств С*Z (), СZ () к соответствующим дележам множеств С*Z (), СZ () для игры Упаковка в контейнеры (см. пример 2, стр.8-9, 17-19).

Упражнение 4. Получить формулы перехода от дележей из множества С*Z () к соответствующим дележам множества С*Z () для игры Мусор (см. пример 3, стр. 9, 19, 20).

Pages:     || 2 |










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

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