- •1.1. Введение.
- •1.2. Оптимизационные задачи в 2.
- •1.4. Понятие о nр-полноте.
- •Условие целочисленности решения задачи лп.
- •Критерий полной унимодулярности.
- •Задача о назначениях.
- •Задача коммивояжера.
- •2. Принятие решений и элементы теории игр.
- •2.1. Задачи многокритериальной оптимизации.
- •2.3. Игры.
- •Дележи.
- •3. Сетевые модели.
- •3.1. Способы задания графов.
- •3.2. Изоморфизм графов.
- •П оиск простейших узких мест графа за o(|e|).
- •3.3. Остовные деревья.
- •Описание алгоритма Прима:
- •Корректность алгоритма Прима.
- •3.4. Кратчайшие пути в графах. Волновой алгоритм построения дкп (Дейкстра)
- •Нахождение кратчайшего пути для ациклического орграфа
- •3.5. Потоковые задачи Задача о максимальном потоке (змп).
- •На входе: матрицы а –пропускных способностей, и c – цен, c ij 0 - стоимость пропуска единицы потока по ребру (I,j), f0 - ограничение на величину потока.
- •3.6. Приближенное решение np-полных задач.
- •Задача о максимальной клике.
- •3.7. Точные методы решения np-полных задач.
- •4. Элементы теории массового обслуживания.
- •4.1. Пуассоновский поток событий
- •4.2. Моделирование простейшего потока.
- •4.3. Процессы гибели и размножения.
- •Классификация систем массового обслуживания:
- •4.4. Открытая система м | м | 1 (один врач).
- •4.5. Замкнутые системы с резервированием. Будем различать горячий и холодный резервы, т.Е. Исправные, но включенные или выключенные приборы.
- •4.6. Задачи проектирования сетей технического обслуживания.
- •3.5. Алгоритм Тарьяна (для планарных графов мод строится за o(n)).
Дележи.
Def. Дележом называется вектор t=(t1,…,tn): 1) ti ({i}) i, 2) ti=(N).
Дележ t доминирует дележ по коалиции S (пишем t≻s ), если:
1) ti>i iS; 2) ti(S).
Пусть E()множество всех дележей, а R()ядро игры, т.е. множество дележей, не доминируемых никакими дележами ни по какой коалиции.
Теорема: Если игра - существенная с постоянной суммой, то R()=.
Def. Множество дележей V E() назовем НМрешением игры, если оно:
внутренне устойчиво, т.е. никакие два дележа из V не доминируют друг друга ни по какой коалиции;
внешне устойчиво, т.е. для V tV и коалиция SN: t≻s.
НМрешение может быть не единственным или пустым при пустом ядре.
Пример К1: (продолжение) V={(1,1,2), (1,2,1), (2,1,1)};
Другое НМрешение: V={(x1,x1a,a)}, x1[2,a], для a[2,1].
Вектор Шепли.
Пусть игра задана в характеристической форме (задана функция ). Относительную силу игроков характеризует вектор Шепли ()=(1(),…,n()):
() E(), т.е. является дележом;
сила каждого игрока не зависит от нумерации, т.е. если в игре номер игрока= i, в игре ' его номер=ki, то ki(')=i();
если игрок участвует одновременно в двух играх и , то можно считать, что игра одна с характеристической функцией + и i(+)=i()+i().
А ксиомы 1)3) однозначно определяют вектор Шепли:
Пример К1(прод): (0)=0=({1,2,3}); ({i})=-2; ({1,2})=({1,3})=({2,3}) =2.
В сумме для 1() будет 4 слагаемых: коалиции {1},{1,2},{1,3},{1,2,3}. 1=(-2-0)/(1*С31)+(-2-(-2))/(2*С32)+(2-(-2))/(2*С32)+(0-)/(3*С33)=0, 2=3=0.
Недостатки вектора Шепли: а) относительная трудоемкость вычислений;
б) вектор Шепли может не принадлежать ядру, даже если ядро не пусто.
Пример К2: Пусть есть акционерное общество из 4-х акционеров. У них 23, 25, 26 и 26% акций соответственно. Выигрыш коалиции равен 1, если она обладает большинством акций; и 0 в противном случае. Найдем вектор Шепли.
Считаем 1. Коалиции, где v(s) - v(s\{1})≠0: {1,2,3},{1,2,4},{1,3,4},{1,2,3,4}
1()=(1-1)/(3*C43)+(1-1)/(3*C43) +(1-1)/(3*C43) +(1-1)/(4*C44)=0.
Игрок 1 является «болваном». Для остальных игроков 2=3=4= 1/3.
Nядро (метод Шмайдлера).
Введем меру близости коалиции S и дележа t: эксцесс . Решая задачу ЛП, найдем дележи . Из них выберем дележи с наименьшим вторым по величине эксцессом и т.д. Решив несколько задач ЛП, получим единственный дележ, называемый Nядром и обладающий свойствами:
1) если игрок i болван, то ti=0; 2) если R(), то NядроR().
Рассмотрим макроигру: два игрока независимо друг от друга выбирают коалицию и дележ, выигрыш = эксцессу. Ищем устойчивое по Нэшу решение: смесь коалиций + N-ядро. Можно решать задачу так: max l(S, t) – верхняя огибающая семейства функций. Исключим tn и разобьем E() в n -1 на области, в которых l(S, t) - линейна решаем ЛП. Ее min на границе.
Окончание примера К1: E() ={(t1,t2,t3): ∑ti =0 & ti v({i})=-2} ~ t1+t2+t3=0 & ti-2
S |
v(S) |
эксцесс |
|
S |
v(S) |
эксцесс |
|
0 |
0 |
|
{1,2,3} |
0 |
0-t1-t2-t3=0 |
{1} |
-2 |
-2-t1 |
|
{2,3} |
2 |
2-t2-t3=2+t1 |
{2} |
-2 |
-2-t2 |
|
{1,3} |
2 |
2-t1-t3=2+t2 |
{3} |
-2 |
-2-t3=-2+t1+t2 |
|
{1,2} |
2 |
2-t1-t2 |
Симметрия по t1,t2 , положим t1=t2=x!!
max{2+x, 2-2x}→ min
2+x = 2-2x 3x = 0 x = 0.
N‑ядро: argmin l̃(t) = (0,0,0).
Пример К3: Одномастка на троих. Позиция - {(9,7,1),(8,4,2),(6,5,3)} с ходом 1-го игрока.
E() ={(t1,t2,t3) | ∑ti = v({1,2,3})=3 & t1 v({1})=1 & t2 v({2})=1 & t3 v({3})=0}.
S |
v(S) |
эксцесс |
|
S |
v(S) |
эксцесс |
{1,2,3} |
3 |
3-t1-t2-t3=0 |
|
|
0 |
0 |
{1,2} |
3 |
3-t1-t2 |
|
{3} |
0 |
0-t3=t1+t2-3 |
{1,3} |
2 |
2-t1-t3=t2-1 |
|
{2} |
1 |
1-t2 |
{2,3} |
2 |
2-t2-t3=t1-1 |
|
{1} |
1 |
1-t1 |
l̃(t)=max{t1-1,t2-1,3-t1-t2}, t1,t21 и t1+t2 3 (симметрия t1,t2, полагаем t1=t2=x)
max{x-1, 3-2x}→ min
x -1= 3-2x 3x = 4 x = 4/3.
N-ядро: argmin l̃(t) = (4/3, 4/3, 1/3).
Можно решать задачу проще: точка пересечения n плоскостей в n есть точка минимума их верхней огибающей. Осталось 3 плоскости. Их пересечение t = (4/3,4/3,1/3).E(). N-ядро совпало с вектором Шепли:
1() = 2() = (1-0)/(1∙C31) + (3-1)/(2∙C32) + (2-0)/(2∙C32) + (3-2)/(3∙C33) = 4/3,
3() = 0/(1∙C31) + (2-1)/(2∙C32) + (2-1)/(2∙C32) + (3-3)/(3∙C33) = 1/3.
???: В игре с постоянной суммой для 3-х игроков N-ядро всегда совпадает с вектором Шепли? Для четырех - не всегда.
Пример К4. На выборах 4 партии набрали 48, 32, 16 и 4 % голосов соответственно.
v-1(0) |
эксцесс |
|
v-1(1) |
эксцесс |
|
0 |
|
1,2,3,4 |
1-t1-t2-t3-t4=0 |
1 |
-t1 |
|
2,3,4 |
1-t2-t3-t4=t1 |
2 |
-t2 |
|
1,3,4 |
1-t1-t3-t4=t2 |
3 |
-t3 |
|
1,2,4 |
1-t1-t2-t4=t3 |
4 |
-t4 |
|
1,2,3 |
1-t1-t2-t3=t4 |
2,3 |
-t2-t3 |
|
1,4 |
1-t1-t4=t2+t3 |
2,4 |
-t2-t4 |
|
1,3 |
1-t1-t3=t2+t4 |
3,4 |
-t3-t4 |
|
1,2 |
1-t1-t2=t3+t4 |
Дележ: t1+t2+t3+t4=1, ti≥0
max S l(S,t)= max{t1, t2+t3, t2+t4, t3+t4}→ min t
Исключим t1 и, используя симметрию по t2,t3,t4 и выпуклость целевой функции, положим t2=t3=t4=x.
max{1-3x, 2x}→ min 1-3x = 2x x = 1/5.
N-ядро =(2/5, 1/5, 1/5, 1/5) не совпадает с вектором Шепли =(1/2, 1/6, 1/6, 1/6)
Постройте вектор Шепли самостоятельно.
v-1(1) |
эксцесс l(S,t) |
|
v-1(0) |
эксцесс |
ЯТЮМС |
1-t1-t2-t3-t4-t5=0 |
|
|
0 |
ЯТЮМ |
1-t1-t2-t3-t4 =t5 |
|
С |
-t5 |
ЯТЮ__С |
1-t1-t2-t3 -t5=t4 |
|
М |
-t4 |
ЯТ__МС |
1-t1-t2 -t4-t5=t3 |
|
Ю |
-t3 |
Я_ЮМС |
1-t1 -t3-t4-t5=t2 |
|
Т |
-t2 |
_ТЮМС |
1 -t2-t3-t4-t5=t1 |
|
Я |
-t1 |
ЯТЮ |
1-t1-t2-t3 =t4+t5 |
|
МС |
-t4-t5 |
ЯТ__М |
1-t1-t2 -t4 =t3+t5 |
|
Ю С |
-t3-t5 |
ЯТ____С |
1-t1-t2 -t5=t3+t4 |
|
ЮМ |
-t3-t4 |
Я_ЮМ |
1-t1 -t3-t4 =t2+t5 |
|
Т С |
-t2-t5 |
Я_Ю__С |
1-t1 -t3 -t5=t2+t4 |
|
Т М |
-t2-t4 |
Я___МС |
1-t1 -t4-t5=t2+t3 |
|
ТЮ |
-t2-t3 |
_ТЮМ |
1 -t2-t3-t4 =t1+t5 |
|
Я С |
-t3-t5 |
_ТЮ__С |
1 -t2-t3 -t5=t1+t4 |
|
Я М |
-t1-t4 |
Я_Ю |
1-t1 -t3 =t2+t4+t5 |
|
Т МС |
-t2-t4-t5 |
ЯТ |
1-t1-t2 =t3+t4+t5 |
|
ЮМС |
-t3-t4-t5 |
Пример К5. Анализ ситуации на Украине после парламентских выборов 2006 года.
В Раду прошли 5 партий, набравшие - 32% (партия регионов, лидер – Янукович), 22% (БЮТ, Тимошенко), 14% (Наша Украина, Ющенко), 5% (СПУ, Мороз) и 4 % голосов (КПУ, Симоненко).
Вопрос: На сколько мест в коалиционном правительстве должна претендовать каждая из партий?
Партии, прошедшие в Раду, набрали 77% голосов. Любаяая коалиция партий, набравшая 39% голосов, может формировать правительство, а не вошедшие в нее партии (антикоалиция) – нет. Число возможных коалиций равно 25. Запишем их в таблицу парами: слева потенциально правящая коалиция, справа – проигравшая антикоалиция.
Дележ: t1+t2+t3+t4+t5=v({ЯТЮМС})=1, ti≥ v({i})=0
Очевидно, что в парах неотрицательные эксцесс имеют коалиции слева. А в левом столбце эксцессы верхних коалиций не превосходят эксцессов нижних пяти коалиций (все их слагаемые как часть входят в эксцессы нижних коалиций). Поэтому
max S l(S,t)= max{t1+t4, t1+t5, t2+t3, t2+t4+t5, t3+t4+t5}
Используем симметрию пар t2,t3 и t4,t5 (t3=t2 и t5=t4), и исключим t1: max S l(S,t)= max{1-2t2-t4, 2t2, t2+2t4}.
Мы ищем точку минимума выпуклой верхней огибающей семейства трех линейных по t2 и t4 функций.
Выделим области Di, в которых огибающая совпадает с i–той функцией.
max=1-2 t2-t4 : 1-2 t2-t4 > 2 t2 t4 < 1-4 t2 , 1-2 t2-t4 > t2+2 t4 3 t4 < 1-3 t2 t4 < 1/3- t2
max=2 t2 : 2 t2 >1-2 t2-t4 t4 > 1-4 t2 , 2 t2 > t2+2 t4 t2 > 2 t4 t4 < t2 / 2
max=t2+2 t4 : t2+2 t4 > 1-2 t2-t4 t4 > 1/3- t2 , t2+2 t4 > 2 t2 t4 > t2 / 2
Ограничения и сами функции – линейны, в каждой области решаем свою задачу ЛП.
функция |
Ограничения области |
min |
1-2 t2-t4 |
t4 < min { 1-4 t2 , 1/3 - t2 } |
4/9 |
2 t2 |
1-4 t2 < t4 < t2 / 2 |
4/9 |
t2+2 t4 |
t4 > max { 1/3- t2 , t2 / 2 } |
4/9 |
1-4 t2 = 1/3 - t2 3 t2 = 2/3
t2 = 2/9 t4 = 1/3 - t2 = 1/9 ,
t1 = 1 - 2 t2 - 2 t4 = 3/9 = 1/3
N-ядро = ( 3/9, 2/9, 2/9, 1/9, 1/9).
Оно не совпадает с вектором Шепли = ( 2/5, 7/30, 7/30, 1/15, 1/15).
1() = 2/(4∙C54) + 6/(3∙C53) + 2/(2∙C52) = 2/20 + 6/30 + 2/20 = 12/30 = 2/5,
2() = 3() = 1/(4∙C54) + 4/(3∙C53) + 1/(2∙C52) = 1/20 + 4/30 + 1/20 = 7/30 ,
4() = 5() = 2/(3∙C53) = 2/30 = 1/15. Заметим, что 12/30 + 7/30 + 7/30 + 2/30 + 2/30 = 1.
Возможности второй и третьей партий по отдельности по созданию правящей коалиции равны возможностям партий 4 и 5, действующим совместно, и N-ядро адекватно отражает силу партий:
|
|
t1 |
t2 |
t3 |
t4 |
t5 |
ЯМС |
p1 |
0 |
1 |
1 |
0 |
0 |
ТЮМ |
p2 |
1 |
0 |
0 |
0 |
1 |
ТЮС |
p3 |
1 |
0 |
0 |
1 |
0 |
ЯЮ |
p4 |
0 |
1 |
0 |
1 |
1 |
ЯТ |
p5 |
0 |
0 |
1 |
1 |
1 |
Можно искать tопт как решение матричной макроигры. Один макроигрок выбирает смешанную коалицию (pi - вероятность прихода коалиции к власти), а другой – дележ. Игра простая ti >0, ti = 1, т.е. дележ t является аналогом смешанной стратегии выбора партии q. Эксцесс l(S,t) – аналог Bi(q). Мы уже знаем tопт. Вектор p можно найти с помощью ТДН. Все tj>0 Aj(p) = 4/9 j.
A4(p) = A5(p) p2 = p3 , A1(p) = 4/9 p2 = 2/9 , A2 = A3 p4 = p5,
A4 = 4/9 p4 = 1/9 , A2 = 4/9 p1 = 3/9 , p = (3/9 , 2/9 , 2/9 , 1/9 , 1/9 ).
Д ля учета взаимоотношений между партиями (например, маловероятна коалиция Януковича и Тимошенко) можно различать выигрыши коалиций. Выигрыш (функция полезности) коалиций конституционного большинства больше среднего, антипрезидентских – меньше. Полученную задачу ЛП небольшой размерности решаем в EXCEL командами Сервис+Поиск решения.
Сведение к ЛП: tопт = argmin w,
при ограничениях дележа
ti > v({i}), ti = v(N)
и эксцесса v(S) - Kt ≤ w
где Kt = {ti | iS} S.
Прямая задача ЛП:
pi ·vi - v(N) ·u → max
при p′ K ≤ u, pi > 0, pi = 1.
ТДН: 1) v(S) - Kt < w pi = 0,
pi > 0 v(S) - Kt = w;
2) ti > v({i}) p′ K = u ,
p′ K < u ti = v({i}).
p′ K - вероятность попадания партий в правительство (сумма
вероятностей pi всех коалиций, содержащих партию), аналог Aj(p).
Для любой партии, не являющейся болваном, вероятность попадания в правительство равна u. По теореме двойственности pi·v(Si) = u∙v(N) + w. Если игра простая, то v(Si) = v(N) = 1 u+w=1.
На какую долю di мест в правительстве может и должна претендовать каждая из партий? ti – это доля мест в правительстве в среднем, т.е. ti = di∙u +0∙(1-u). Отсюда di = ti / u
dЯнукович = (3/9) / (5/9) = 3/5 = 60%; dТимошенко = dЮщенко = (2/9) / (5/9) = 40%; dМороз = dСимоненко = 20%.
Еще раз подчеркнем: решение целиком определяется подбором вектора v выигрыша коалиций!