Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 1
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. В кінці 18-го ст. французький математик Рене де Монмор розглянув наступну ситуацію. Для того, щоб зробити подарунок своєму синові, батько пропонує: "Я візьму зколоту монету в праву або ліву руку, а ти назвеш одну з них. Якщо монета в мене в правій руці і твоя здогадка правильна, то ти отримуєш одну золоту монету. Якщо ж монета у лівій руці і твоя здогадка правильна, то ти отримуєш дві монети; в протилежному випадку ти нічого не отримуєш".Скласти матрицю гри.
Завдання 3. Для гри з пункту 5 знайти нижню чисту ціну, верхню чисту ціну гри,визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
-4 -4 3
3 6 5
0 4 -2
2 -4 1
-3 2 -4
Завдання 5. Маємо дві карти - старша і молодша. Гравець 1 з рівною ймовірністю витягає одну з них, причому робить це в таємниці від гравця 2.Потім він вирішує: чи дати долар другому гравцеві, чи грати далі. В останньому випадку гравець 2 приймає рішення:або спасувати, і тоді він дає долар гравцеві 1, або грати дальше. В останньому випадку карта гравця 1 відкривається і гравець 2 платить 4 долари гравцю 1, якщо це виявилась старша карта, в протилежному випадку гравець 1 платить 5 доларів гравцю 2.
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 80y8 - 5xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І.М. Дронюк Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 2
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо матриця А має вигляд:
a b
c d
a d
c b
де a,b,c,d- довільні числа.
Завдання 2. Два гравці незалежно один від одного вибирають одне із чисел 1,2 або 3.Якщо обидва вибирають одне і тке ж число, то перший гравець платить другому суму в розмірі вибраного числа. В протилежному випадку перший гравець отримує від другого суму, рівну числу вибраному другим. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити скідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
-3 -4 -5
-5 -4 -3
-6 -4 -2
-1 -3 -6
0 -3 -6
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали. Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник пам"ятає комерсанта.
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 16y6 - 3xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 3
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2. Два партнери вибирають незалежно один від одного одне із значень -1 або 1. Позначимо значення, вибране першим гравцем через s, а другим - через t. Сума яку другий гравець виплачує першому, рівна (t-s)+t(t+s). Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4.Звести гру до задачі лінійного програмування
1 2 3
3 1 2
0 4 1
2 3 1
1 5 0
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець 1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали. Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник не пам"ятає комерсанта.
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 80y8 - 5xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 4
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. Гравці вибирають одне з цілих чисел від 1 до k. Якщо перший вибрав i, а другий j, то перший отримує i-j одиниць виграшу, якщо i > j, та платить i+j одиниць виграшу, якщо i < j. Скласти матрицю гри.
Завдання 3. Для гри з пункту 5 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
6 0 -6
2 -1 -4
-6 -3 0
-10 -4 2
3 -4 1
Завдання 5. Перший гравець вибирає одне з трьох чисел 1,2,3. Другий намагається вгадати вибране число.При кожній здогадці другого гравця перший відповідає "багато", "мало" або "правильно". Гра продовжується до того часу, поки другий гравець не вгадає правильно. Платіж першому гравцеві - число здогадок, яке потрібне другому гравцеві, щоб отримати відповідь "правильно".
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Знайти хоча б один роз"язок матричної гри з матрицею A=(a_{ij}), i=1,m; j=1,m), якщо кожна стрічка і кожний стовпчик матриці A містять всі цілі числа від k+1 до k+m.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 5
Завдання 1 Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Кожен з двох гравців вибирає одне з цілих чисел від 1 до 9. Якщо число вибране одним з гравців, на одиницю більше, ніж число, вибране другим, то перший гравець програє дві одиниці виграшу. Якщо вибір одного з гравців більший хоча б на дві одиниці, перший гравець виграє одну одиницю виграшу. В тому випадку, коли вибори гравців співпадають, гра закінчується внічию. Складіть матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
3 4
0 1
1 4
6 0
5 0
Завдання 4. Звести гру до задачі лінійного програмування
3 7 10
7 3 2
2 6 11
0 4 12
-1 6 12
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець І вибирає число х з множини (1,2).
Хід 2. Вибирається число y з множини (1,2) при допомозі випадкового механізму, такого, що ймовірність вибору 1 рівна 1/2, а 2 рівна 1/2.
Хід 3. Гравець ІІ, знаючи y, але не знаючи х, вибирає число z з множини (1,2),якщо y =1, і з множини {1,2,3}, коли y=2.
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(-A)=-v(A^T), де A^T- матриця транспонована до A.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 6
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2. Перший гравець називає одне з чисел 1 або 2, а другий одне з чисел 1, 2, 3. При цьому кожен з партнерів намагається вгадати, яке з чисел назве суперник. Якщо обидва партнери вгадали або помилились одночасно, то гра закінчується внічию; коли ж один з них вгадав, то він отримує виграш, рівний числу,яке назвав суперник. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
-1 0 -1
-1 -1 2
1 1 -2
1 1 -3
-1 4 0
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець 1 вибирає число х з множини (1,2).
Хід 2. Вибирається число y з множини (1,2) при допомозі випадкового механізму такого, що ймовірність вибору 1 рівна 1/2, а 2 рівна 1/2.
Хід 3. Якщо на другому ходу вибрано 1, то то гравець 2, знаючи значення х і у, вибирає число z з множини (1,2), якщо ж на другому ходу було вибрано 2, то гравець 1, знаючи значення х і у, вибирає число z з множини (1,2).
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(A+B)=v(A)+b та множина оптимальних стратегій в іграх з матрицями A i A+B співпадають, якщо всі елементи матриці B рівні b.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 7
Завдання 1. Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Два гравці одночасно кидають кожний по одній гральній кості. Перший гравець отримує виграш рівний різниці значень між числом, що випало у нього та числом, що випало у противника. Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
19 0
15 20
17 15
5
Завдання 4. Звести гру до задачі лінійного програмування
1 2 3
0 2 4
2 2 2
4 2 0
3 1 2
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Випадковий механізм з ймовірностями відповідно 1/3 і 2/3 вибирає х з множини (1,2).
Хід 2. Якщо х = 1, то гравець І, знаючи х, вибирає у з множини (1,2,3). Якщо х =2, то гравець ІІ, знаючи х, вибирає у з множини (1,2,3).
Хід 3. Якщо у = 1, то гравець ІІ, знаючи у, але не знаючи х вибирає z з множини (1,2). Якщо у не рівний 1, то гравець І, знаючи х і знаючи, чи було вибрано у=1 чи у не рівне 1, вибирає z з множини (1,2).
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Знайти хоча б один роз"язок матричної гри з матрицею A=(a_{ij}), i=1,m; j=1,m), якщо кожна стрічка і кожний стовпчик матриці A містять всі цілі числа від k+1 до k+m.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 8
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. Два гравці одночасно кидають кожний по одній гральній кості.Якщо сума чисел ,щo випали парна, то виграш, рівний цій сумі, отримує перший гравець, якщо непарна - то другий. Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
1 1
2 1
3 3
4 3
2 0
Завдання 4. Звести гру до задачі лінійного програмування
-1 0 5
-2 1 4
1 7 8
6 5 4
2 8 1
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець І вибирає число х з множини (1,2,3,4).
Хід 2. Гравець ІІ, знаючи парне х або непарне х, вибирає у з множини (1,2).
Хід 3. Якщо у =2, то гравець ІІ вибирає число z з множини (1,2), якщо у =1, то гравець І, знаючи x і у, вибирає число z з множини (1,2).
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Довести, що матрична гра з матрицею A=( (aij), i=1,m;j=1,n) має розв'язок в чистих стратегіях і знайти цей розв'язок, якщо матриця А має вигляд:
a e a e a e a e
b f b f f b f b
c g g c c g g c
де a,b,c,d,f,e,g- довільні числа.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 9
Завдання 1. Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Два гравці одночасно кидають кожний по одній гральній кості. Якщо сума чисел, що випала більша або рівна 9, то виграш, рівний цій сумі, отримує перший гравець, у протилежному випадку - другий. Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
24 0
0 8
4 5
-1 3
7
Завдання 4. Звести гру до задачі лінійного програмування
3 6 9
9 6 3
1 1 1
3 7 0
0 3 7
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець І вибирає число х з множини (1,2).
Хід 2. Гравець ІІ, не знаючи х, вибирає у з множини (1,2,4).
Хід 3. Гравець І,знаючи парна чи не парна сума х+y вибирає число z з множини (1,2) .
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 80y8 - 5xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 10
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо матриця А має вигляд:
a b
c d
a d
c b
де a,b,c,d- довільні числа.
Завдання 2. Розглянемо наступну гру з двома гравцями. Кожний гравець показує від одного до п'яти пальців, і загальне число показаних пальців ділиться на 3. Якщо сума ділиться на 3 без залишку, то ніяких виплат не проводиться. Якщо залишок рівний 1, то гравець А виграє суму, рівну загальному числу показаних пальців, а якщо залишок рівний 2, то гравець В виграє суму, рівну загальному числу показаних пальців.Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
3 5 3
4 -3 2
3 2 6
Завдання 4. Звести гру до задачі лінійного програмування
6 21
5 52
4 63
1 62
7 81
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали.
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник пам"ятає комерсанта.
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 16y6 - 3xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 11
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2. Кожен з двох гравців вибирає одне з цілих чисел від 1 до 3. Якщо число вибране одним з гравців, на одиницю більше, ніж число, вибране другим, то перший гравець програє дві одиниці виграшу. Якщо вибір одного з гравців більший хоча б на дві одиниці, перший гравець виграє одну одиницю виграшу. В тому випадку, коли вибори гравців співпадають, гра закінчується внічию. Складіть матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
5 6 7
7 3 2
1 5 9
9 5 4
1 7 6
Завдання 5. Маємо дві карти - старша і молодша. Гравець 1 з рівною ймовірністю витягає одну з них, причому робить це в таємниці від гравця 2.Потім він вирішує: чи дати долар другому гравцеві, чи грати далі. В останньому випадку гравець 2 приймає рішення: або пасувати, і тоді він дає долар гравцеві 1, або грати дальше. В останньому випадку карта гравця 1 відкривається і гравець 2 платить 4 долари гравцю 1, якщо це виявилась старша карта, в ротилежному випадку гравець 1 платить 5 доларів гравцю 2. Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Знайти хоча б один роз"язок матричної гри з матрицею A=(a_{ij}), i=1,m; j=1,m), якщо кожна стрічка і кожний стовпчик матриці A містять всі цілі числа від k+1 до k+m.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 12
Завдання 1. Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Два гравці одночасно кидають кожний по одній гральній кості. Якщо сума чисел, що випала більша або рівна 9, то виграш, рівний цій сумі, отримує перший гравець, у протилежному випадку - другий. Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
2 0 1 4
1 2 5 3
4 1 3 2
3 0 1 1
1 0 1 4
Завдання 4. Звести гру до задачі лінійного програмування
1 8 9 5
5 4 10 3
9 4 5 5
2 9 3 2
10 3 4 4
Завдання 5. Перший гравець вибирає одне з трьох чисел 1,2,3. Другий намагається вгадати вибране число.При кожній здогадці другого гравця перший відповідає "багато", "мало" або "правильно". Гра продовжується до того часу, поки другий гравець не вгадає правильно. Платіж першому гравцеві - число здогадок, яке потрібне другому гравцеві, щоб отримати відповідь "правильно".
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(-A)=-v(A^T), де A^T- матриця транспонована до A.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 13
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. Два гравці незалежно один від одного вибирають одне із чисел 1,2 або3. Якщо обидва вибирають одне і те ж число, то перший гравець платить другому суму в розмірі вибраного числа. В протилежному випадку перший гравець отримує від другого суму, рівну cумі чисел, що ними вибрані. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
2 3 4 5
5 2 3 4
6 2 3 4
5 4 3 2
1 5 6 7
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали.
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник пам"ятає комерсанта.
Завдання 6. Знайти хоча б один роз"язок матричної гри з матрицею A=(a_{ij}), i=1,m; j=1,m), якщо кожна стрічка і кожний стовпчик матриці A містять всі цілі числа від k+1 до k+m.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 14
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо матриця А має вигляд:
a b
c d
a d
c b
де a,b,c,d- довільні числа.
Завдання 2. Два гравці одночасно кидають кожний по одній гральній кості. Якщо сума чисел, що випали більша або рівна 9, то виграш, рівний цій сумі, отримує другий гравець, у протилежному випадку - перший. Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
0 1 -1 2
-1 0 2 -2
1 -2 0 1
-2 2 -1 0
Завдання 4. Звести гру до задачі лінійного програмування
1 1 9 9
8 1 2 3
1 2 8 9
2 2 8 8
3 3 7 8
Завдання 5. Маємо дві карти - старша і молодша. Гравець 1 з рівною ймовірністю витягає одну з них, причому робить це в таємниці від гравця 2.Потім він вирішує: чи дати долар другому гравцеві, чи грати далі. В останньому випадку гравець 2 приймає рішення: або спасувати, і тоді він дає долар гравцеві 1, або грати дальше. В останньому випадку карта гравця 1 відкривається і гравець 2 платить 4 долари гравцю 1, якщо це виявилась старша карта, в протилежному випадку гравець 1 платить 5 доларів гравцю 2. Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(A+B)=v(A)+b та множина оптимальних стратегій в іграх з матрицями A i A+B співпадають, якщо всі елементи матриці B рівні b.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 15
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2. Два гравці домовились грати в наступну гру. Перший гравець буде показувати 1,2 або 4 пальці. Одночасно другий гравець буде показувати 2, 3 або 5 пальців. Якщо загальне число показаних пальців рівне 3, 5 або 9, то перший гравець отримує таку ж суму. В протилежному випадку не проводиться ніякої виплати. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
2 4 6 8
8 6 4 2
4 5 6 8
6 8 2 4
8 6 4 2
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець І вибирає число х з множини (1,2).
Хід 2. Вибирається число y з множини (1,2) при допомозі випадкового механізму, такого, що ймовірність вибору 1 рівна 1/2, а 2 рівна 1/2.
Хід 3. Гравець ІІ, знаючи y, але не знаючи х, вибирає число z з множини (1,2),якщо y =1, і з множини {1,2,3}, коли y=2.
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Всі елементи матриці A невід"ємні, причому кожний стовпчик містить хоча б один додатній елемент. Довести, що ціна гри з матрицею А додатня.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 16
Завдання 1. Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Два гравці домовились грати в наступну гру. Перший гравець буде показувати 1, 2 або 4 пальці. Одночасно другий гравець буде показувати 2, 3 або 5 пальців. Якщо загальне число показаних пальців рівне 3, 5 або 9, то перший гравець отримує таку ж суму. В протилежному випадку другий гравець отримує виплату, рівну сумі показаних пальців. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
2 3 7 8
7 3 8 1
3 4 9 8
2 5 7 9
1 9 2 4
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець 1 вибирає число х з множини (1,2).
Хід 2. Вибирається число y з множини (1,2) при допомозі випадкового механізму такого, що ймовірність вибору 1 рівна 1/2, а 2 рівна 1/2.
Хід 3. Якщо на другому ходу вибрано 1, то то гравець 2, знаючи значення х і у, вибирає число z з множини (1,2), якщо ж на другому ходу було вибрано 2, то гравець 1, знаючи значення х і у, вибирає число z з множини (1,2).
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 3) =-2, H (2, 2, 3) = 3
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(-A)=-v(A^T), де A^T- матриця транспонована до A.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк
Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 17
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. Два гравці домовились грати в наступну гру. Перший гравець буде показувати 1,3 або 4 пальці. Одночасно другий гравець буде показувати 2, 4 або 5 пальців. Якщо загальне число показаних пальців ділиться на 3, то перший гравець отримує виплату рівну сумі показаних пальців. В протилежному випадку не проводиться ніякої виплати. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
9 8 7 2
8 7 4 2
2 5 10 1
3 8 9 1
2 9 2 3
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Випадковий механізм з ймовірностями відповідно 1/2 і 1/2 вибирає х з множини (1,2).
Хід 2. Якщо х = 1, то гравець І, знаючи х, вибирає у з множини (1,2,3). Якщо х =2, то гравець ІІ, знаючи х, вибирає у з множини (1,2).
Хід 3. Якщо у = 1, то гравець ІІ, знаючи у, але не знаючи х вибирає z з множини (1,2). Якщо у не рівний 1, то гравець І, знаючи х і знаючи, чи було вибрано у=1 чи у не рівне 1, вибирає z з множини (1,2).
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,z,y) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 3, 1) =-2,
H (1, 3, 2) =-3,
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(A+B)=v(A)+b та множина оптимальних стратегій в іграх з матрицями A i A+B співпадають, якщо всі елементи матриці B рівні b.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 18
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо матриця А має вигляд:
a b
c d
a d
c b
де a,b,c,d- довільні числа.
Завдання 2. Два гравці одночасно і незалежно один від одного показують 1,2 або 3 пальці. Нехай k-загальне число показаних пальців. Якщо k-парне, то перший платить другому k карбованців. Якщо k- непарне, то другий платить k карбованців першому.Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
1 3 5 7
7 3 5 7
7 5 3 1
3 5 7 1
5 7 1 3
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець І вибирає число х з множини (1,2,3,4).
Хід 2. Гравець ІІ, знаючи парне х або непарне х, вибирає у з множини (1,2).
Хід 3. Якщо у =2, то гравець ІІ вибирає число z з множини (1,2), Якщо у =1, то гравець І, знаючи x і у, вибирає число z з множини (1,2).
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0 H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1 H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (3, 1, 1) = 3, H (4, 1, 1) = 1 H (3, 1, 2) =-3, H (4, 1, 2) = 6
H (3, 2, 1) = 2, H (4, 2, 1) =-2 H (3, 2, 2) = 1, H (4, 2, 2) =-4
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 80y8 - 5xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 19
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2. Обидва гравці називають одну з чотирьох букв: a, b, c, d. Гравець, що назвав букву, яка стоїть раніше в ряду, отримує одиницю виграшу. Якщо обидва називають однакову букву, гра закінчується внічию. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
3 4 7 8
10 3 4 8
7 8 2 4
2 7 8 8
4 5 8 7
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець І вибирає число х з множини (1,2).
Хід 2. Гравець ІІ, не знаючи х, вибирає у з множини (1,2,4).
Хід 3. Гравець І,знаючи парна чи не парна сума х+y вибирає число z з множини (1,2) .
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,z,y) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
H (1, 2, 4) =-2, H (2, 2, 4) = 3
Завдання 6. Довести, що матрична гра з матрицею A=( (aij), i=1,m;j=1,n) має розв'язок в чистих стратегіях і знайти цей розв'язок, якщо матриця А має вигляд:
a e a e a e a e
b f b f f b f b
c g g c c g g c
де a,b,c,d,f,e,g- довільні числа.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 20
Завдання 1. Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Полководець, що обороняє місто, має 4 дивізії, а його суперник - 3 дивізії. Відомо, що місто буде здане тільки в тому випадку, коли на одній з двох застав дивізії, що наступають, будуть у більшості.Перемога полководця, що обороняє місто, оцінюється 2 бали, його суперника - 1 бал, нічия - 0 балів. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
2 3 5 9
10 1 1 1
2 9 2 2
5 2 1 10
9 1 1 2
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали.
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник пам"ятає комерсанта.
Завдання 6. Знайти хоча б один роз"язок матричної гри з матрицею A=(a_{ij}), i=1,m; j=1,m), якщо кожна стрічка і кожний стовпчик матриці A містять всі цілі числа від k+1 до k+m.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 21
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. Два гравці одночасно і незалежно один від одного показують 1,2 або 3 пальці. Нехай k-загальне число показаних пальців. Якщо k-непарне,то перший платить другому k+1 карбованців. Якщо k- парне, то другий платить k-1 карбованців першому.Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нкижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
1 1 9 9
9 1 3 4
1 9 1 1
2 9 3 4
3 4 5 9
Завдання 5. Перший гравець вибирає одне з трьох чисел 1,2,3. Другий намагається вгадати вибране число.При кожній здогадці другого гравця перший відповідає "багато", "мало" або "правильно". Гра продовжується до того часу, поки другий гравець не вгадає правильно. Платіж першому гравцеві - число здогадок, яке потрібне другому гравцеві, щоб отримати відповідь "правильно".
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Довести, що матрична гра з матрицею A=( (aij), i=1,m;j=1,n) має розв'язок в чистих стратегіях і знайти цей розв'язок, якщо матриця А має вигляд:
a e a e a e a e
b f b f f b f b
c g g c c g g c
де a,b,c,d,f,e,g- довільні числа.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 22
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо aij = f(i)+g(j).
Завдання 2. Полководець, що обороняє місто, має 3 дивізії, а його суперник - 2 дивізії. Відомо, що місто буде здане тільки в тому випадку, коли на одній з двох застав дивізії, що наступають, будуть у більшості. Перемога полководця, що обороняє місто, оцінюється 2 бали, його суперника - 1 бал, нічия - 0 балів. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
3 4 5 6
7 3 4 5
8 2 2 2
6 8 2 1
1 9 2 3
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець 1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали.
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник не пам"ятає комерсанта.
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 16y6 - 3xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 23
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2. Перший гравець називає одне з чисел 1 або 2, а другий одне з чисел 1, 2, 3, 4. При цьому кожен з партнерів намагається вгадати, яке з чисел назве суперник. Якщо обидва партнери вгадали або помилились одночасно, то гра закінчується внічию; коли ж один з них вгадав, то він отримує виграш, рівний числу,яке назвав суперник. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
2 1 0 5
0 3 5 1
2 7 2 4
9 0 2 3
5 0 2 9
Завдання 5. Гра "митний огляд". Маємо два гравці - митник (гравець1) і комерсант (гравець 2). Комерсант може з'явитися на митниці три рази. Кожний раз він думає - брати з собою контрабандний товар чи ні (йому треба пронести цей товар рівно один раз). Митник при кожній появі комерсанта може провести огляд. Гра закінчується, якщо була спроба пронести контрабандний товар незалежно від того, вдала вона чи ні.Виграш комерсанта при вдалому провозі товару складає 2 бали, при холостому ході він втрачає 1 бал,якщо не було контролю і 0 балів, якщо контроль відбувся. Якщо митник знаходить контрабандний товар, то він отримує 3 бали.
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми, при умові що митник пам"ятає комерсанта.
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 80y8 - 5xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 24
Завдання 1. Довести, що матрична гра з матрицею A = ((aij), i = 1,m; j = 1,n) має розв’язок в чистих стратегіях і знайти цей розв’язок, якщо матриця А має вигляд:
a b
c d
a d
c b
де a,b,c,d- довільні числа.
Завдання 2. Перший гравець називає одне з чисел 1 або 2, а другий одне з чисел 1, 2, 3. При цьому кожен з партнерів намагається вгадати, яке з чисел назве суперник. Якщо обидва партнери вгадали або помилились одночасно, то гра закінчується внічию; коли ж один з них вгадав, то він отримує виграш, рівний cумі чисел, названих суперниками. Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
3 6 9 0
6 0 2 5
8 2 5 2
4 5 9 0
2 4 9 0
Завдання 5. Перший гравець вибирає одне з трьох чисел 1,2,3. Другий намагається вгадати вибране число.При кожній здогадці другого гравця перший відповідає "багато", "мало" або "правильно". Гра продовжується до того часу, поки другий гравець не вгадає правильно. Платіж першому гравцеві - число здогадок, яке потрібне другому гравцеві, щоб отримати відповідь "правильно".
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Знайти хоча б один роз"язок матричної гри з матрицею A=((aij)), i=1,m;j=1,n), якщо кожна стрічка і кожний стовпчик матриці A містять всі цілі числа від k+1 до k+m.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 25
Завдання 1. Знайти хоча б один розв’язок гри з матрицею A = ((aij), i = 1,m; j = 1,n), якщо
1 коли i ( j
aij =
0 коли i = j
Завдання 2.Два гравці одночасно і незалежно один від одного показують 1,2 або 3 пальці. Нехай k-загальне число показаних пальців. Якщо k>3,то перший платить другому 2k карбованців. В протилежному випадку другий платить k карбованців першому.Скласти матрицю гри.
Завдання 3. Для гри з пункту 2 знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують, або розв'язати гру в змішаних стратегіях.
Завдання 4. Звести гру до задачі лінійного програмування
3 6 7 8
8 4 0 1
8 2 0 5
3 5 9 0
7 9 0 2
Завдання 5. Перший гравець вибирає одне з трьох чисел 1,2,3. Другий намагається вгадати вибране число.При кожній здогадці другого гравця перший відповідає "багато", "мало" або "правильно". Гра продовжується до того часу, поки другий гравець не вгадає правильно. Платіж першому гравцеві - число здогадок, яке потрібне другому гравцеві, щоб отримати відповідь "правильно".
Побудувати дерево гри, вказати на ньому інформаційні множини та привести гру до нормальної форми.
Завдання 6. Позначимо через v(A) ціну гри з матрицею А. Довести, що v(-A)=-v(A^T), де A^T- матриця транспонована до A.
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк

Національний університет “Львівська політехніка”
Кафедра Автоматизовані системи управління
Дисципліна “Методи оптимізації і дослідження операцій”
Семестр 4
Розрахункова №2
Варіант 26
Завдання 1. Довести, що ціна гри, матриця якої складається з раціональних чисел, також раціональне число.
Завдання 2. Перший гравець називає одне з чисел 1, 2 або 3, а другий одне з чисел 4, 5, 6. При цьому кожен з партнерів намагається вгадати, яке з чисел назве суперник. Якщо обидва партнери вгадали або помилились одночасно, то гра закінчується внічию; коли ж один з них вгадав, то він отримує виграш, рівний сумі чисел,які назвали суперник. Скласти матрицю гри.
Завдання 3. Знайти нижню чисту ціну, верхню чисту ціну гри, визначити сідлові точки, оптимальні чисті стратегії та чисту ціну гри, якщо вони існують або розв'язати гру в змішаних стратегіях:
0 4 -3 1
-4 0 2 -1
3 -2 0 3
-1 1 -3 0
Завдання 4. Звести гру до задачі лінійного програмування
3 5 7 9
9 7 5 2
9 0 8 7
1 9 0 2
6 8 2 5
Завдання 5. Дати графічне зображення і привести до нормальної форми наступну гру:
Хід 1. Гравець 1 вибирає число х з множини (1,2).
Хід 2. Вибирається число y з множини (1,2) при допомозі випадкового механізму такого, що ймовірність вибору 1 рівна 1/2, а 2 рівна 1/2.
Хід 3. Якщо на другому ходу вибрано 1, то то гравець 2, знаючи значення х і у, вибирає число z з множини (1,2), якщо ж на другому ходу було вибрано 2, то гравець 1, знаючи значення х і у, вибирає число z з множини (1,2).
Побудувати дерево гри і вказати інформаційні множини.
Функція виграшу H(x,y,z) визначена наступним чином:
H (1, 1, 1) = 2, H (2, 1, 1) = 0
H (1, 1, 2) =-2, H (2, 1, 2) = 5
H (1, 2, 1) = 1, H (2, 2, 1) =-1
H (1, 2, 2) = 0, H (2, 2, 2) =-3
Завдання 6. Знайти розв’язок нескінченної антагоністичної гри на одиничному квадраті з функцією виграшу
H(x,y) = 80y8 - 5xy + x2
Питання
1
2
3
4
5
6
Сума

Бали
0
1
1
1
2
0
5


Затверджено на засідання кафедри АСУ протокол № 1-11/12 від 22.08.2011 .
Зав.каф. М.Медиковський
Викладач І. М. Дронюк