Линейное программирование и смежные вопросы. Часть 11. Методические указания по курсу ''Методы оптимизации'' для студентов механико-математического факультета

1

Министерство образования Российской Федерации РОСТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

С.В.Гусаков, Л.Н.Землянухина, А.Б.Зинченко, Л.И.Сантылова

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по курсу "Методы оптимизации" для студентов механико-математического факультета дневного и вечернего отделения

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И СМЕЖНЫЕ ВОПРОСЫ Часть 11

Ростов-на-Дону 2004

2

Методические заседанием кафедры

указания

рекомендованы к печати

исследования

операций механико-

математического факультета РГУ протокол № 5 от 27 января 2004 г.

3

ОГЛАВЛЕНИЕ 13. ДИСКРЕТНЫЕ КООПЕРАТИВНЫЕ ИГРЫ (продолжение) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 13.6.

Свойства С-ядра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

13.6.1.

Игра трех лиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

13.6.2.

Игра четырех лиц . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

13.6.3.

Игра n лиц. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

13.7.

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

13.8.

Индивидуальные задания . . . . . . . . . . . . . . . . . . . . . . . 22 Литература . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4

13. ДИСКРЕТНЫЕ КООПЕРАТИВНЫЕ ИГРЫ (продолжение) В части 10 методических указаний было дано определение дискретной кооперативной игры и ее С-ядра, найдены ядра конкретных игр. В данной части методических указаний исследуются свойства С-ядра дискретной игры, приводятся условия существования С-ядра и методы нахождения дележей, принадлежащих С-ядру. 13.6. Свойства С-ядра дискретной игры Согласно данному выше определению, С-ядро СZ(ν) дискретной игры ГZ есть множество целочисленных точек С-ядра СR(ν) релаксированной игры ГR , то есть множество целочисленных решений линейной системы, имеющей специальную структуру. Исследуем свойства С-ядра для дискретных игр трех и четырех лиц, затем рассмотрим общий случай. 13.6.1. Игра трех лиц Запишем условия, определяющее С-ядро дискретной игры трех лиц с 0-редуцированной характеристической функцией

x1 + x2

≥ ν(1,2 ) ,

x1

≥ ν(1,3) ,

+ x3

x2 + x3 ≥ ν( 2,3) , x1 + x2 + x3 = ν(1,2,3) ,

5

x1 , x2 , x3 ≥ 0, x1 , x2 , x3 - целые, ν (S ) - целое число, S ⊆ N. После преобразования получаем систему

x1 + x2 + x3 = ν(1,2,3) , ≤ ν(1,2,3) - ν( 2,3) , x1 ≤ ν(1,2,3) - ν(1,3) , x2 x3 ≤ ν(1,2,3) - ν(1,2 ) , - x1 ≤ 0, - x2 ≤ 0, - x3 ≤ 0, x1 , x2 , x3 - целые,

(1)

в которую явно включены условия неотрицательности переменных.

ГZ

У т в е р ж д е н и е 1 . С-ядро дискретной кооперативной игры трех лиц не пусто тогда и только тогда, выполняется условие ν(1,2 ) + ν(1,3) + ν( 2,3) ≤ 2 ν(1,2,3) .

(2)

Д о к а з а т е л ь с т в о . Условие (2) является необходимым и достаточным условием непустоты С-ядра СR (ν) релаксированной игры ГR. Поэтому достаточно показать, что при выполнении (2), множество СR (ν) содержит по крайней мере одну целочисленную точку. Известна теорема [1]: решение x системы n

∑ aij x j ≤ bi ,

i = 1, m1 ,

∑ aij x j = bi ,

i = m1 + 1, m ,

j =1 n

j =1

6

является вершиной выпуклого многогранного множества, определенного этой системой, тогда и только тогда, когда среди ограничений найдутся n линейно независимых условий, которым эта точка удовлетворяет как равенствам. Рассмотрим матрицу системы (1)

⎛ 1 1 1 ⎞ ⎜ ⎟ 1 0 0 ⎜ ⎟ ⎜ 0 1 0⎟ ⎜ ⎟ A =⎜ 0 0 1 ⎟ ⎜−1 0 0 ⎟ ⎜ ⎟ 0 − 1 0 ⎜ ⎟ ⎜ ⎟ ⎝ 0 0 − 1⎠ ⎛ 2⎞ Количество ее допустимых базисов не больше ⎜ ⎟ = 15. ⎝6⎠ Допустимые базисы матрицы A имеют вид:

⎛ 1 1 1 ⎞ ⎜ ⎟ B 3 = ⎜ b213 b223 b233 ⎟ , ⎜ 3 3 3 ⎟ ⎝ b31 b32 b33 ⎠

где элементы bij3 равны 0, 1 или -1, причем вторая и третья строки содержат только один ненулевой элемент. Разлагая определитель базиса B 3 последовательно по второй и третьей строке, получаем, что ⏐det B 3 ⏐= 1. Так как определители всех базисов матрицы системы (1) равны 1 или –1, а правые части ограничений целочисленны, то С-ядро СR(ν) релаксированной игры является целочисленным многогранником. Целочисленные вершины многогранника СR(ν)

7

принадлежат С-ядру СZ(ν) дискретной игры, следовательно, для игры трех лиц СZ (ν)≠∅. 13.6.2. Игра четырех лиц Запишем условия, определяющие С-ядро дискретной кооперативной игры четырех лиц в 0–редуцированной форме x1 + x2 x1 + x3 x1 + x4 x2 + x3 x2

+ x4

≥ ν(1,2 ) , ≥ ν(1,3) , ≥ ν (1,4) , ≥ ν( 2,3) , ≥ ν (2,4) ,

x3 + x 4 ≥ ν (3,4) , x1 + x2 + x3 ≥ ν(1,2,3) , x1 + x2 + x 4 ≥ ν (1,2,4) , x1 + x3 + x 4 ≥ ν (1,3,4) , x2 + x3 + x 4 ≥ ν (2,3,4) , x1 + x2 + x3 + x 4 = ν (1,2,3,4) , x1 , x2 , x3 , x 4 ≥ 0, x1 , x2 , x3 , x 4 - целые, ν (S ) - целое число, S ⊆ N. После преобразования получаем линейную систему с целочисленными правыми частями ≤ ν (1,2,3,4) - ν (3,4) ,

x1 + x2 x1

+ x3

≤ ν (1,2,3,4) -ν (2,4) , + x 4 ≤ ν (1,2,3,4) - ν(2,3) ,

x1 x2 + x3

≤ ν (1,2,3,4) - ν (1,4) ,

8

x2

+ x4

≤ ν (1,2,3,4) - ν(1,3) ,

x3 + x 4 ≤ ν (1,2,3,4) - ν(1,2 ) , x1 + x2 + x3 + x 4 = ν (1,2,3,4) , ≤ ν (1,2,3,4) - ν (2,3,4) ,

x1

≤ ν (1,2,3,4) - ν (1,3,4) ,

x2

≤ ν (1,2,3,4) - ν (1,2,4) ,

x3 x4

≤ ν (1,2,3,4) - ν(1,2,3) , ≤ 0,

- x1

≤ 0,

- x2 - x3

≤ 0, - x 4 ≤ 0,

x1 , x2 , x3 , x 4 - целые.

У т в е р ж д е н и е 2 . Если дискретная кооперативная игра ГZ четырех лиц имеет непустое С-ядро, то ее характеристическая функция удовлетворяет условиям ν(1,2 ) + ν(1,3) + ν (1,4) + 2ν (2,3,4) ≤ 3ν (1,2,3,4) ,

(3)

ν(1,2,3) + ν (1,2,4) + ν (3,4) ≤ 2ν (1,2,3,4) ,

(4)

ν(1,2,3) + ν (1,2,4) + ν (1,3,4) + ν (2,3,4) ≤ 3ν (1,2,3,4)

(5)

и аналогичным (3), (4) неравенствам, с учетом перестановок игроков. Д о к а з а т е л ь с т в о . Пусть Ω=2N \ N \ ∅ - множество собственных коалиций. Рассмотрим релаксированную игру ГR четырех лиц. Как было показано в части 5 методических указаний ([2], стр.

9

35), игра ГR имеет непустое С-ядро тогда и только тогда, когда для коэффициентов (λ(S))S∈Ω любого минимального сбалансированного покрытия выполняется условие

∑ λ ( S )ν ( S ) ≤ ν (N ) .

(6)

S ∈Ω

Все типы минимальных сбалансированных покрытий [2] (для игры четырех лиц) и их коэффициенты приведены в таблице 1. Остальные минимальные сбалансированные покрытия получаются перестановкой игроков. Таблица 1 №

Минимальное сбалансированное покрытие

Кол-во анало- Коэффициенты гичных по- покрытия крытий

1 {{1},{2},{3},{4}}

0

(1,1,1,1)

2 {{1,2},{3},{4}}

5

(1,1,1)

3 {{1,2},{3,4}}

0

(1,1)

4 {{1,2,3},{4}}

3

(1,1)

5 {{1,2},{1,3},{2,3},{4}}

3

(1/2, 1/2, 1/2, 1)

6 {{1,2},{1,3},{2,3,4},{4}}

3

(1/2, 1/2, 1/2, 1/2)

7 {{1,2},{1,3},{1,4},{2,3,4}}

3

(1/3, 1/3, 1/3, 2/3)

8 {{1,2,3},{1,2,4},{3,4}} 9 {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

5

(1/2, 1/2, 1/2)

0

(1/3, 1/3, 1/3, 1/3)

Покрытия 1-6 типов можно не рассматривать, так как соответствующие им неравенства (6) являются следствиями других неравенств и условий супераддитивности характеристической функции

10

(см. упражнение 1). Покрытия 7-9 типов определяют неравенства (3), (4), (5) соответственно. Утверждение доказано, так как необходимое и достаточное условие непустоты С-ядра релаксированной игры ГR является необходимым условием существования С-ядра дискретную игры ГZ.

П р и м е р 1 . Рассмотрим дискретную кооперативную игру четырех лиц с 0-редуцированной характеристической функцией

ν (1) =ν (2) =ν (3) =ν (4) =0; ν(1,2 ) = ν(1,3) =ν (1,4) =2;

ν (2,3) =ν (2,4) =ν (3,4) =1;

ν(1,2,3) =ν (1,2,4) =ν (1,3,4) =3;

ν (2,3,4) =4;

ν (1,2,3,4) =4. Подставив харатеристическую функцию игры в условия (3)(5), получаем, что она не удовлетворяет неравенству

ν (1,3,4) + ν (2,3,4) + ν (1,2) ≤ 2ν (1,2,3,4) , так как 3 + 4 + 2 > 8. Следовательно, С-ядро данной дискретной игры является пустым.

У т в е р ж д е н и е 3 . С-ядро релаксированной игры ГR четырех лиц в общем случае не является целочисленным многогранником. Непустое С-ядро релаксированной игры четырех лиц может не содержать ни одной целочисленной точки. Д о к а з а т е л ь с т в о . Рассмотрим дискретную игру ГZ четырех лиц в 0-редуцированной форме с характеристической функцией

ν (1) =ν (2) =ν (3) =ν (4) =0;

11

ν(1,2 ) = ν(1,3) =ν (1,4) =2;

ν(2,3) =ν (2,4) =ν (3,4) =3;

ν(1,2,3) =ν (1,2,4) =ν (1,3,4) =3;

ν (2,3,4) =4;

ν (1,2,3,4) =5. Преобразованная система, определяющая С-ядро релаксированной игры ГR, имеет вид ≤ 2, x1 + x2 + x3 ≤ 2, x1 + x 4 ≤ 2, x1 ≤ 3, x2 + x3 + x 4 ≤ 3, x2 x3 + x4 ≤ 3, x1 + x2 + x3 + x 4 = 5, x1 ≤ 1, x2 ≤ 2, ≤ 2,

x3 x4

≤ 2,

x1 , x2 , x3 , x 4 ≥ 0. Исключив переменную x 4 из уравнения x1 + x2 + x3 + x 4 = 5 иподставив ее в остальные ограничения получаем систему

x1 + x2 + x3 x1 x2 + x3 x1 x2 x3 x1 + x2 + x3 x1 , x2 , x3 ≥ 0,

=2, =2, = 3, ≤ 1, ≤ 2, ≤ 2, ≥ 3,

12

единственное решение которой имеет вид

x = (0.5, 1.5, 1.5, 1.5). Таким образом, СR(ν)≠∅ - нецелочисленный многогранник и СZ(ν)=∅. У т в е р ж д е н и е 4 . Нецелочисленными вершинами непустого С-ядра релаксированной игры ГR четырех лиц могут быть только векторы x1 = ( x11 ,..., x1n ) и x 2 = ( x12 ,..., xn2 ) , имеющие следующие координаты

x11 = x12 = x31 =

x14 =

2ν (1,2,3,4) − ν ( 2,3) − ν ( 2,4) − ν (3,4) , 2

ν ( 2,3) + ν ( 2,4) − ν (3,4) 2

ν ( 2,3) − ν ( 2,4) + ν (3,4) 2

, ,

− ν ( 2,3) + ν ( 2,4) + ν (3,4) , 2

x12 = x22 = x32 = x42 =

ν (1,2,3,4) + ν (1,4) − ν ( 2,4) − ν (3,4) 2

ν (1,2,3,4) − ν (1,4) + ν ( 2,4) − ν (3,4) 2

ν (1,2,3,4) − ν (1,4) − ν ( 2,4) + ν (3,4) 2

, , ,

− ν (1,2,3,4) + ν (1,4) + ν ( 2,4) + ν (3,4) . 2

13

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

⎛1 ⎜ 1 A = ⎜⎜ 0 ⎜⎜ ⎝0

T

1 1 0 0 0 1 1 0 0 0 − 1 0 0 0⎞ ⎟ 0 0 1 1 0 1 0 1 0 0 0 −1 0 0⎟ . 1 0 1 0 1 1 0 0 1 0 0 0 −1 0⎟ ⎟⎟ 0 1 0 1 1 1 0 0 0 1 0 0 0 − 1⎠

Количество допустимых базисов этой матрицы не больше ⎛3 ⎞ ⎜ ⎟ =364. Допустимые базисы, с точностью до перестановки строк ⎝14 ⎠ и столбцов, имеют вид 4 ⎛ b11 ⎜ 4 ⎜ b21 4 B =⎜ 4 ⎜ b31 ⎜ 1 ⎝

4 4 4 ⎞ b12 b13 b14 ⎟ 4 4 4 ⎟ b22 b23 b24 ⎟, 4 4 4 b32 b33 b34 ⎟ 1 1 1 ⎟⎠

где элементы bij4 равны 0, 1 или -1, причем каждая строка, кроме последней, содержит не менее одного и не более двух неравных нулю элементов. Возможны следующие случаи. 1. Все строки базиса B 4 , кроме последней, содержат один неравный нулю элемент. Разлагая определитель базиса B 4 последовательно по первой, второй и третьей строкам, получаем, что | det B 4 | =1.

14

2. Только одна из первых трех строк (например, строка 3) базиса B 4 содержит два ненулевых элемента, а 1-я и 2-я строки – по одному отличному от нуля элементу. Тогда 2 2 ⎞ ⎛ b11 b12 ⎟⎟ ⇒ | det B | = | det B | , где B = ⎜⎜ ⎝1 1 ⎠ 2

4

⇒

2

2 2 | det B 4 | = | b11 - b12 |.

Поскольку элементы bij2 равны 1, -1 или 0, то 2 2 = - b12 ≠ 0. | det B 4 | ≠ 1 ⇔ b11

Но из структуры матрицы A вытекает, что 2 2 ≠ 0, b12 ≠0 ⇒ b11

2 2 = b12 = 1, b11

следовательно | det B 4 | =1. 3. Две из первых трех строк (например, строки 2 и 3) базиса B 4 содержат два отличных от нуля элемента, а 1-я строка – один ненулевой элемент. Тогда 3 3 3 ⎞ ⎛ b11 b12 b13 ⎟ ⎜ 3 3 3 3 4 3 ⏐det B ⏐ = ⏐det B ⏐, где B = ⎜ b21 b22 b23 ⎟ . ⎟ ⎜ ⎜1 1 1 ⎟ ⎠ ⎝

Как и в предыдущем случае, нетрудно показать, что ⏐det B 4 ⏐=1 (см. упражнение 2). 4. Все строки базиса B 4 , кроме последней, содержат два ненулевых элемента, равных 1. Тогда, с точностью до перестановки строк и столбцов, базисы B 4 имеют вид

15

⎛1 ⎜ 1 B14 = ⎜ ⎜1 ⎜⎜ ⎝1

1 0 0 1

0 1 0 1

0⎞ ⎟ 0⎟ 1⎟ ⎟ 1 ⎟⎠

или

⎛1 1 0 ⎜ 1 0 1 B24 = ⎜ ⎜0 1 1 ⎜⎜ ⎝1 1 1

0⎞ ⎟ 0⎟ . 0⎟ ⎟ 1 ⎟⎠

Вычислив эти определители (см. упражнение 3), получаем, что | det B 4 | =2. Найдем координаты вершин С-ядра релаксированной игры, соответствующие базисам B14 и B24 . Матрица B14 определяет систему = ν (1,2,3,4) - ν (3,4) ,

x1 + x2 x1 x1

+ x3

= ν (1,2,3,4) - ν (2,4) , + x 4 = ν (1,2,3,4) - ν(2,3) ,

x1 + x2 + x3 + x 4 = ν (1,2,3,4) , единственным решением которой является дележ x 1 , вид которого приведен в условии доказываемого утверждения. Матрица B24 определяет систему x1 + x2 = ν (1,2,3,4) - ν (3,4) , x1 + x3 = ν (1,2,3,4) -ν (2,4) ,

x2 + x3 = ν (1,2,3,4) - ν (1,4) , x1 + x2 + x3 + x 4 = ν (1,2,3,4) , единственным решением которой является дележ x 2 .

У т в е р ж д е н и е 5 . Если С-ядро СR(ν) релаксированной игры четырех лиц удовлетворяет условию ⏐СR(ν)⏐>1, то С-ядро СZ(ν) соответствующей дискретной игры не пусто.

16

Д о к а з а т е л ь с т в о . Пусть y 1 ,…, y k – вершины многогранника СR(ν). По предположению, k ≥ 2. Если по крайней мере одна из вершин y j , j = 1, k , целочисленна, то она принадлежит С-ядру дискретной игры, то есть СZ(ν)≠∅. Пусть все векторы y j , j = 1, k , нецелочисленны, тогда они определяются формулами из утверждения 4. В этом случае любое ребро многогранника СR(ν) содержит целочисленную точку, следовательно, СZ(ν)≠∅. П р и м е р 2 . Рассмотрим дискретную кооперативную игру четырех лиц с 0-редуцированной характеристической функцией

ν (1) =ν (2) =ν (3) =ν (4) =0; ν(1,2 ) = ν(1,3) =3, ν (1,4) =ν (2,4) =ν (3,4) =2, ν(1,2,3) =ν (1,2,4) =ν (1,3,4) =3;

ν(2,3) =1;

ν (2,3,4) =2;

ν (1,2,3,4) =5. Подставив данную характеристическую функцию в формулы, приведенные в утверждении 4, получаем

x11 =

10 − 1 − 2 − 2 1+ 2 − 2 = 2.5 , x12 = = 0 .5 , 2 2

x31 =

1− 2 + 2 = 0 .5 , 2

x14 =

−1+ 2 + 2 = 1.5 , 2 5−2+ 2−2 = 1 .5 , 2

x12 =

5+ 2−2−2 = 1 .5 , 2

x22 =

x32 =

5−2−2+ 2 = 1 .5 , 2

x42 =

−5+ 2+ 2+ 2 = 0 .5 . 2

17

Так как С-ядро релаксированной игры имеет две нецелочисленные вершины

x 1 =(2.5, 0.5, 0.5, 1.5)

и

x 2 =(1.5, 1.5, 1.5, 0.5),

то ⏐СR(ν)⏐>1. Из утверждения 5 вытекает, что С-ядро СZ(ν) дискретной игры не пусто. Найдем один из дележей множества СZ(ν). Направление отрезка от x 1 к x 2 параллельно вектору (-1, 1, 1, -1), поэтому ближайшая к x 1 по этому направлению целочисленная точка x * определяется формулами

x1* = x11 - 0.5,

x2* = x12 + 0.5,

x3* = x31 + 0.5,

x4* = x14 - 0.5.

Получаем дележ x * =(2, 1, 1, 1) ∈ СZ(ν).

13.6.3. Игра n лиц Рассмотрим систему, определяющую С-ядро дискретной кооперативной игры n лиц в 0–редуцированной форме

∑ xi ≤ ν ( N ) − ν ( N \ S ),

i ∈S

1 < S < n − 1, S ⊂ N ,

∑ xi = ν ( N ),

(8)

i∈N

0 ≤ xi ≤ ν ( N ) − ν ( N \ i ),

(7)

i ∈ N,

i∈N. xi - целые, ν (S ) - целое число для любого S ⊆ N.

(9) (10)

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

18

Лэнд и Дойг [3,4], разработанного для решения задач целочисленного линейного программирования АЛГОРИТМ 1. Положить k = 1, f = 0. Через M 1 обозначить многогранник, определенный системой (7) - (9). 2. Если k = 0, то перейти к шагу 7. 3. Проверить условие M k = ∅. Если оно выполняется, то положить k = k – 1 и перейти к шагу 2. 4. Найти произвольную вершину x k многогранника M k . 5. Если x k - целочисленный вектор, то положить f = 1 и перейти к шагу 7. 6. Выбрать нецелочисленную компоненту x kj вектора x k (например, первую по порядку). Определить два новых многогранника M k +1 = { x ∈ M k : x j ≥ [ x kj ] + 1},

M k = { x ∈ M k : x j ≤ [ x kj ]}, где [ x kj ] – целая часть числа x kj . Положить k = k + 1 и перейти к шагу 3. 7. Если f = 0, то СZ(ν) = ∅, в противном случае x k – дележ, принадлежащий С-ядру СZ(ν) дискретной игры ГZ. 8. Конец. П р и м е р 3 . Используя описанный выше алгоритм, найдем дележ из С-ядра дискретной игры с характеристической функцией

ν (1) =ν (2) =ν (3) =ν (4) =0;

19

ν(1,2 ) =3,

ν(1,3) =ν (1,4) = ν(2,3) =ν ( 2,4) =2, ν (3,4) =3;

ν(1,2,3) =ν (1,2,4) =ν (1,3,4) =ν (2,3,4) =3;

ν (1,2,3,4) =6. Положим k = 1. Многогранник M 1 определяется системой x1 + x2 ≤ 3, x1 + x3 ≤ 4, x1 + x 4 ≤ 4, x2 + x3 ≤ 4, x2 + x 4 ≤ 4,

(11)

x3 + x 4 ≤ 3,

(16)

x1 + x2 + x3 + x 4 = 6, x1 , x2 , x3 , x 4 ≥ 0,

(17)

(12) (13) (14) (15)

(18)

из которой удалены зависимые неравенства.

M 1 ≠∅, так как система (11)-(18) совместна. Одна из вершин многогранника M 1 имеет вид x1 = (1.5, 1.5, 2.5, 0.5). Вектор x1 нецелочисленный, поэтому определяем множества M 2 = { x ∈ M 1 : x1 ≥ 2 }, M 1 = { x ∈ M 1 : x1 ≤ 1}, то есть многогранник M 1 теперь определяется системой (11) - (18) и дополнительным условием (19) x1 ≤ 1, а многогранник M 2 определяется системой (11) - (18) и дополнительным условием (20) x1 ≥ 2.

20

Положим k = 2. M 2 ≠∅, так как система (11)-(18),(20) совместна. Одна из вершин многогранника M 2 имеет вид

x 2 = (2.5, 0.5, 1.5, 1.5). Вектор x 2 нецелочисленный, поэтому определяем множества

M 3 = { x ∈ M 2 : x1 ≥ 3 }, M 2 = { x ∈ M 2 : x1 ≤ 2}, то есть многогранник M 2 теперь определяется системой (11)-(18), (20) и дополнительным условием (21) x1 ≤ 2, а многогранник M 3 определяется системой (11) - (18), (20) и дополнительным условием (22) x1 ≥ 3. Положим k = 3. Рассмотрим систему (11) - (18), (20), (22), определяющую многогранник M 3 . Из условий (11),(22) получаем, что x1 = 3, x2 = 0. Подставив эти значения в остальные условия, получаем несовместную систему

x3 ≤ 1,

x4 ≤ 1,

x3 + x4 = 3,

x3 , x4 ≥ 0.

Следовательно, M 3 =∅. Положим k = 2. Рассмотрим систему (11) - (18), (20), (21), определяющую многогранник M 2 . Из условий (20),(21) вытекает, что x1 = 2. Подставив это значение в остальные условия, получаем систему x2 ≤ 1,

x3 ≤ 2,

x 4 ≤ 2, x3 + x 4 ≤ 3, x2 + x3 + x 4 = 4, x2 , x3 , x 4 ≥ 0, одно из опорных решений которой имеет вид x 2 = (2, 1, 1, 2). Получили целочисленный вектор x 2 = (2, 1, 1, 2) принадлежащий С-ядру данной дискретной игры. Вычисления закончены.

21

13.9. Упражнения.

У п р а ж н е н и е 1 . Доказать, что неравенства (6), соответствующие минимальным сбалансированным покрытиям 1-6 типа (см. таблицу 2), являются следствием неравенств (6), соответствующих минимальным сбалпнсированным покрытиям 7-9 типов и условий супераддитивности характеристической функции. Упражнение имеющих вид

2 . Доказать, что определители базисов, 3 3 3 ⎞ ⎛ b11 b12 b13 ⎟ ⎜ 3 3 3 3 B = ⎜ b21 b22 b23 ⎟ . ⎟ ⎜ ⎜1 1 1 ⎟ ⎠ ⎝

равны 1 или –1.

У п р а ж н е н и е 3 . Показать модули определителей базисов

⎛1 ⎜ ⎜1 ⎜1 ⎜⎜ ⎝1

1 0 0⎞ ⎟ 0 1 0⎟ , 0 0 1⎟ ⎟ 1 1 1 ⎟⎠

⎛1 1 0 ⎜ ⎜1 0 1 ⎜0 1 1 ⎜⎜ ⎝1 1 1

0⎞ ⎟ 0⎟ 0⎟ ⎟ 1 ⎟⎠

равны двум.

У п р а ж н е н и е 4 . Могут ли векторы x1 и x 2 , приведенные в утверждении 4, иметь часть целочисленных компонент, а часть – нецелочисленных? У п р а ж н е н и е 5 . Составить программу вычисления вершин многогранника СR(ν) по формулам, приведенным в утверждении 4, и аналогичным формулам, получающимся перестановкой игроков.

22

Таблица 2 №

1

2

3

4

5

6

7

8

9

10 11 12

ν(1,2 )

2

1

3

2

2

1

3

3

3

4

2

2

ν(1,3)

2

2

2

1

2

2

2

2

2

2

3

3

ν (1,4) ν (2,3) ν (2,4) ν (3,4)

2

1

3

1

2

3

3

1

2

2

2

2

2

2

2

2

3

2

1

3

3

3

3

4

2

1

2

1

3

3

3

3

3

3

3

1

2

2

2

2

3

3

2

2

1

1

1

3

ν(1,2,3)

3

4

4

3

3

3

3

5

4

5

3

4

ν (1,2,4) ν (1,3,4) ν (2,3,4) ν (1,2,3,4)

4

4

3

4

4

5

4

4

4

4

5

5

3

4

3

4

4

4

5

3

3

4

4

4

4

4

4

3

3

3

3

3

5

5

5

4

4

5

5

4

5

5

5

5

5

6

6

6

13.9. Индивидуальные задания.

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

23

Таблица 3 №

1

2

3

4

5

6

7

8

9

10 11 12

ν(1,2 )

3

5

2

2

2

3

5

5

5

4

4

3

ν(1,3)

4

4

3

3

2

2

6

6

6

5

4

3

ν (1,4) ν (2,3) ν (2,4) ν (3,4)

5

3

4

3

3

3

5

5

4

3

3

2

4

6

4

4

3

2

4

4

4

4

3

3

5

5

5

4

4

3

3

3

2

2

2

2

6

4

6

5

4

2

4

4

3

3

2

2

ν(1,2,3)

5

7

4

4

3

3

6

7

7

6

5

4

ν (1,2,4) ν (1,3,4) ν (2,3,4) ν (1,2,3,4)

6

5

5

4

4

4

6

5

5

4

4

3

7

5

6

5

4

3

7

6

6

5

4

3

6

6

7

6

5

3

5

5

4

4

3

3

9

9

8

7

6

5

9

9

8

7

6

5

Таблица 4 №

1

2

3

4

5

6

7

8

9

10 11 12

ν(1,2 )

3

4

8

3

2

9

5

9

3

3

3

5

ν(1,3)

3

5

8

9

2

9

4

8

2

2

3

3

ν (1,4) ν (2,3) ν (2,4) ν (3,4)

3

4

9

6

2

6

4

8

2

2

3

3

3

4

9

9

1

3

4

8

2

4

3

3

5

5

8

6

3

6

4

8

4

2

3

3

3

4

9

6

3

6

5

9

3

3

3

3

ν(1,2,3)

4

6

9

9

2

9

6

9

3

4

4

5

ν (1,2,4) ν (1,3,4) ν (2,3,4) ν (1,2,3,4)

5

6

9

6

3

9

6

9

4

3

4

5

4

6

9

9

3

9

6

9

3

3

4

4

5

6

9

9

3

6

6

9

4

4

4

4

8

10 18 15

5

15 10 18 6

6

8

8

24

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

Литература 1. Юдин Д.Б, Гольштейн Е.Г. Линейное программирование. М., 1963. С.71-73. 2. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.,1969. С.219-224. 3. Таха Х. Введение в исследование операций. Т.1. М.,1985. С.357-363. 4. Мулен Э. Кооперативное принятие решений: аксиомы и модели. М., 1991. С.139-141.