Розрахунок резервів часу робіт та їх використання 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Розрахунок резервів часу робіт та їх використання



 

Коментарі до резервів часу робіт.

Повний резерв.

1) робота 3-6 має повний резерв часу у 8 годин. Його можна використовувати без перевищення критичного шляху на роботі 3-6 чи на інших роботах її максимального некритичного шляху: 1-3, 6-9 чи 9-11, оскільки жодна з цих робіт не належить іншим шляхам більшої довжини.

2) робота 2-6 має повний резерв часу у 16 годин. Його можна повністю використовувати для неї, без перевищення довжини критичного шляху. Інші ж роботи 6-9 та 9-11 належать не тільки максимальному шляху роботи 2-6, а й іншому шляху більшої довжини, тому мають не 16, а 8 годин повного резерву. Таким чином, резерв часу роботи 2-6 можна використовувати на роботах 6-9 та 9-11 її максимального шляху не повністю, а тільки у межах повного резерву часу цих робіт.

 

 


 
 

 

 

Резерви часу робіт

Код роботи i – j Тривалість tij Ранні терміни Пізні терміни Резерви часу
початку закінчення початку закінчення повний частинний вільний незалежний
0-1                  
0-5                  
1-2                  
1-3                  
1-4                  
1-5                  
2-6                 -8
3-6                 -8
3-7                  
4-7                  
4-10                  
5-8                 -26
5-10                  
6-9                 -8
7-10                  
7-11                  
8-12                  
9-11                  
10-11                  
10-12                  
11-12                  

 

Частинний резерв.

1) роботи 3-6 та 3-7 мають загальну початкову подію 3. Максимальний шлях роботи 3-6 проходить через події 0-1-2-6-9-11-12 та має тривалість 50 годин. Робота 3-7 належить максимальному шляху 0-1-3-7-10-11-12 довжиною 40 годин. Таким чином, роботи 3-6 частинного резерву не має, а у роботи 3-7 цей резерв дорівнює різниці між довжинами зазначених шляхів, тобто 50-40=10 годин.

2) робота 1-3 має повний резерв часу у 8 годин, її максимальний шлях від початкової події 1 перетинається з найбільшим з шляхів цієї події 1-4-10-11 (довжина 40 годин) у події 11. Максимальний шлях роботи 1-3 проходить через події 1-3-6-9-11 та має довжину у 32 години. Різниця у довжині цих шляхів становить частинний резерв часу роботи 1-3, тобто 40-32 = 8. Цей частинний резерв може бути використаний для роботи 1-3 чи робіт 3-6, 6-9, 9-11.

3) роботи 3-7 має повний резерв часу у 18 годин, у складі якого частинний резерв дорівнює 10 годинам. Інші 8 годин є повним резервом часу передуючої роботи 1-3. Збереження повного резерву часу у передуючої роботи 1-3 у розмірі 8 годин не призведе до зменшенню резерву часу у шляху більшої довжини 0-1-4-7, з яким перетинається шлях роботи 3-7 у події 7. Таким чином, частинний резерв часу роботи 3-7, що дорівнює 10 годинам, не обов’язково використовувати на ділянці її шляху до перетину з іншим шляхом більшої довжини, тобто для самої роботи 3-7. Певну його частину, що не перевищує резерву часу шляху більшої довжини можна зберегти для останнього з тим, щоб він не опинився критичним.

У нашому випадку шлях більшої довжини, з яким перетинається максимальний шлях роботи 3-7 у події 7, має резерв часу у 4 години. Якщо частинний резерв часу роботи 3-7 повністю використати для неї, то у події 7 резерву часу не залишиться, тобто подія 7 відбудеться у найбільш пізній термін. Тоді відповідно і наступна робота 7-10, що належить максимальному шляху події 7, стане критичною.

Щоб не допустити такого випадку, слід використати тільки частину частинного резерву роботи 3-7, але не більш ніж 4 години, тобто не більше ніж резерв часу події 7.

 

Вільний резерв.

1) вільний резерв часу роботи 3-7 дорівнює 14 годинам та може бути повністю використаний для неї. При цьому не порушиться ранній термін її кінцевої події 7, а відповідно, ранні терміни всіх наступних за нею робіт та не зменшаться їх резерви часу. Однак, це можливе тільки за умови, що робота 1-3, що передує роботі 3-7 буде виконана не пізніше раннього терміну її кінцевої події 3. У випадку порушення цієї вимоги, будуть порушені ранні терміни початку та зменшаться (чи навіть анулюються) повні резерви часу робіт 3-6, 6-9 та вільний резерв часу роботи 9-11.

2) Використання вільного резерву часу роботи 9-11 у повному обсязі для неї самої не порушить раннього терміну початку роботи 11-12, не змінить ранніх термінів початку та не зменшить повних і вільних резервів часу у всіх інших робіт графіку, за винятком робіт, що лежать на передуючих шляхах події 9-11.

Якщо для роботи 9-11 використати повністю її вільний резерв часу та запланувати для неї не 5, а 13 годин, то при збереженні термінів раннього початку у всіх робіт графіку зміняться пізні терміни початкової події роботи 9-11 та всіх некритичних подій її передуючих шляхів, що призведе до зменшення повних резервів у з’єднаних з ним робіт.

3) робота 9-11 має вільний резерв часу 8 годин. Найближчою передуючою подією, з якої виходять інші шляхи, є подія 3. За умови відбування події 3 у ранній термін, вільний резерв часу роботи 9-11 можна розподілити між роботами 3-6, 6-9, 9-11, в результаті чого зміняться терміни початку та перерозподіляться резерви часу тільки у цих робіт без зміни їх у всіх інших робіт.

ТЕМА 15. Оптимізація сіткових графіків

 

15.1. Оптимізація сіткового графіку за критерієм часу виконання комплексу робіт

15.2. Оптимізація сіткового графіку за критерієм використання ресурсів

 

15.1. Оптимізація сіткового графіку за критерієм часу виконання комплексу робіт

Під оптимізацією сіткового графіка розуміють внесення до його первісного варіанту можливих змін з метою досягнення найбільш вигідних результатів та доведення розрахункових параметрів, на які планується комплекс робіт, до заданих показників.

Оптимізація критичного шляху полягає в поліпшенні його відповідно до прийнятого критерію. В принципі, цими критеріями можуть бути: час, вартість, людські і матеріальні ресурси й ін. У даний час оптимізація сіткових графіків виконується в більшості випадків тільки за критерієм часу.

Оптимізація може виконуватися з різними цілями:

1. Якщо критичний шлях з тривалістю перевищує задані терміни , то оптимізація за часом полягає в скороченні критичного шляху.

2. Якщо , то мається відомий резерв часу , тому роботи можна розтягнути у часі з метою економії витрачених ресурсів.

Розглянемо дані задачі окремо.

Задача 1.

Відомий критичний шлях , причому

,

де – поширюється тільки на критичні роботи;

– заданий (директивний) термін виконання робіт.

Для скорочення критичного шляху, дійсно, є сенс форсувати критичні роботи. Їх можна прискорити, наприклад:

а) за рахунок додаткових сил і засобів;

б) за рахунок перекидання сил і засобів з некритичних робіт на критичні.

Якщо використовується пункт (а), то виникає типова задача дослідження операцій: які додаткові засоби та у які критичні роботи потрібно вкласти, щоб критичний шлях , а витрати додаткових засобів були мінімальними.

Допустимо, що при вкладенні додаткових засобів у роботу , скорочує час виконання цієї роботи до часу

 

.

 

Таким чином, потрібно визначити невід’ємні значення змінних (додаткові вкладення) при яких би виконувалася умова:

,

де – поширюється по всіх критичних роботах нового критичного шляху (після розподілу засобів);

і щоб при цьому загальна сума додаткових засобів

,

була мінімальною.

У загальному вигляді обмеження задачі є нелінійними, тому що вкладення якихось засобів у роботу не обов'язково призводить до лінійного зменшення часу, затрачуваного на цю роботу. Тому поставлена задача відноситься до класу задач нелінійного програмування. Однак, при невеликих змінах плану, коли обмеження є лінійними, поставлена задача оптимізації критичного шляху вирішується методом лінійного програмування.

Якщо використовується пункт (б), тобто для оптимізації критичного шляху перекидаються наявні засоби з некритичних робіт на критичні, знову відомий критичний шлях (1) і крім того мається певний запас пересувних засобів , що розподілений між роботами в кількостях .

Позначимо: – кількість пересувних засобів, що перекидаються з роботи ( береться від’ємним, якщо з роботи перекидаються засоби на інші роботи).

Зрозуміло, що сума засобів, що знімаються з якихось робіт, повинна бути дорівнює сумі засобів, що додаються іншим роботам, тобто

.

Величини повинні задовольняти обмеженням:

чи .

Відомо:

– якщо кількість засобів знімається з роботи , то час її виконання зростає:

;

– якщо кількість засобів вкладається в роботи , то час її виконання зменшується:

.

При таких позначеннях загальний термін виконання всіх робіт (новий критичний шлях) складе:

,

де перша містить у собі всі роботи з яких переносяться засоби, а друга – всі роботи, в які вкладаються засоби, якщо вони входять до критичного шляху.

Здавалося б, що перенос засобів має сенс робити тільки з некритичних робіт на критичні. Однак, у процесі таких переносів може вийти, що некритичні роботи можуть переходити в критичні і навпаки. Тому в рівнянні для цільової функції, у загальному випадку, присутній перший доданок . Отже, задача ставиться таким чином: знайти такі значення змінних , при яких би задовольнялися обмеження, а загальний термін виконання робіт обертався б у мінімум. Це також задача нелінійного програмування, тому що цільова функція є завжди нелінійною.

 

Задача 2. Відомий критичний шлях

.

Передбачається збільшити час виконання деяких критичних робіт, так, щоб і одержати максимальну економію засобів. Якщо збільшимо час виконання критичної роботи на величину , то звільняється деяка кількість засобів на цій роботі :

.

Потрібно вибрати такі значення невід’ємних змінних , щоб загальна сума критичних часів

,

при який сума засобів, що звільнилися

,

досягала максимуму.

Ця задача так само відноситься до задач нелінійного програмування. У випадках, коли збільшення терміну робіт невелике, вдається звести цю задачу до задачі лінійного програмування.

 

15.2. Оптимізація сіткового графіку за критерієм використання ресурсів

 

Основні типи ресурсів.

Ресурси, що витрачаються у транспортно-технологічних процесах, є виключно різноманітними. Всі види ресурсів прийнято розділяти на два типи:

а) не поновлювані ресурси (ресурси разового використання);

б) поновлювані ресурси (ресурси багаторазового використання).

До не поновлюваних ресурсів (будемо називати їх ресурсами першої групи) відносяться всі види паливно-мастильних матеріалів, грошові засоби, одноразові засоби пакетування. Особливість таких ресурсів полягає в тому, що вони можуть накопичуватися та використовуються при виконанні тієї чи іншої роботи тільки один раз. Вони, як правило, є статичними, та у процесі виконання робіт на них діють людські ресурси з використанням різноманітних механізмів, інструментів. Потреба у ресурсах такого виду у плановому періоді може бути визначена підсумовуванням відомих потреб у них за окремими роботами та термінам їх виконання.

До поновлюваних ресурсів (будемо називати їх ресурсами другої групи) відносяться людські ресурси (водії, вантажники), машини, механізми, транспортні засоби. Особливість такого виду ресурсів полягає в тому, що вони є динамічними, не можуть накопичуватись та повинні використовуватись безперервно. Невикористання таких ресурсів в умовах транспортно-технологічних процесів призводить до їх простою та фактичної втрати.

Задачі по найбільш оптимальному використанню ресурсів при їх обмеженій кількості можуть розглядатися по одному чи декількох видах ресурсів чи групах робіт, у визначені відрізки часу чи за весь період виконання комплексу робіт.

Для нескладних сіткових графіків при оптимізації ресурсів використовують лінійні діаграми, на якій по кожній роботі показують вільні та повні резерви часу, резерви часу подій, з використанням яких можливе пересування термінів початку та закінчення робіт та регулювання використання ресурсів.

Розглянемо ці можливості на прикладі роботи (3-7) нашого сіткового графіка. У первісному розрахунку сіткового графіка тривалість роботи прийнята у 8 годин за умови безперервної роботи та щогодинного споживання ресурсів у кількості 15 одиниць. Таким чином, для виконання роботи в загальному випадку необхідно 15*8 = 120 одиниць ресурсу.

Дійсно, що зменшення інтенсивності, тобто використання ресурсу у одиницю часу, коли ми розглядаємо тільки одну роботу, можливе тільки за рахунок збільшення її тривалості.

У даному випадку подовжити тривалість роботи та зменшити інтенсивність використання ресурсів можливе за наступними варіантами.

Варіант 1.

Якщо виконання роботи буде заплановано у ранній термін у первісною розрахунковою тривалістю у 8 годин, то витрати ресурсу у одиницю часу будуть максимальні, тобто 15 одиниць на годину. При цьому після виконання роботи 3-7 у неї залишиться вільний час до відбування раннього терміну її кінцевої події, який не може бути використаний (вільний резерв у 14 годин). У той же час, планування початку роботи 3-7 у ранній термін передбачає анулювання повного резерву часу у попередньої роботи 1-3, що є у даній ситуації навряд чи є розумним рішенням.

 

 

Варіант 2.

Робота 3-7 має, як видно з розрахунку, незалежний резерв часу у 6 годин. Якщо збільшити тривалість роботи 3-7 на величину її незалежного резерву та запланувати початок виконання роботи и пізній термін її початкової події, то буде досягнуте зменшення інтенсивності використання ресурсу з 15 до 9 одиниць на годину. При цьому не будуть порушені ранні терміни початку наступних робіт та не будуть зменшені резерви часу ані у попередніх ані у наступних робіт.

 

 

Варіант 3.

Подальше зменшення інтенсивності споживання ресурсів роботою 3-7 може бути досягнуте шляхом використання для неї її вільного резерву часу. У даному випадку робота повинна бути розпочата та закінчена у ранні терміни відбування її початкової та кінцевої події. При цьому анулюються резерви часу у попередньої роботи 1-3 та не зменшуються резерви часу у всіх наступних робіт.

Варіант 4.

У необхідних випадках зменшення інтенсивності споживання ресурсу може бути досягнуте за рахунок збільшення тривалості роботи на величину її повного резерву часу. У цьому випадку анулюються резерви часу у всіх робіт, що лежать на максимальному шляху даної роботи.

 

 

 

Аналогічним чином, можлива мінімізація, вирівнювання чи створення неперервності використання однорідних ресурсів по групі робіт чи по всім роботам сіткового графіка. При цьому слід пам’ятати, що для групи одночасно виконуваних робіт зменшення інтенсивності використання ресурсу можуть бути вирішені без збільшення тривалості окремих робіт шляхом пересування термінів їх виконання у межах вільних та повних резервів часу.

Наприклад, нехай роботи 2-6, 3-7 та 5-10 виконуються одним видом ресурсу. Інтенсивність споживання ресурсу для всіх робіт є однаковою та складає 8 одиниць на годину. При цьому одночасне споживання ресурсу обмежене також 8 одиницями ресурсу з умови забезпечення безперервності у роботі.

 

 

Якщо роботи 2-6, 3-7 та 5-10 будуть розпочаті у ранні терміни, максимальна потреба у ресурсах припаде на період часу 15-20 годин та складе 24 одиниці замість лімітованих 8 одиниць. Кожна з робіт має вільний резерв часу. Пересування термінів початку та закінчення робіт 2-6 та 5-10 у межах їх вільних резервів часу забезпечує неперервне виконання робіт до ранніх термінів їх кінцевих подій та максимальну потребу у ресурсах 8 одиниць, що не перевищує ліміту.

У випадку, коли роботи не мають вільного резерву часу, зменшення інтенсивності споживання ресурсів може бути досягнуте за рахунок збільшення тривалості чи пересування термінів виконання робіт з використанням для цього повного резерву часу.

Наприклад, роботи 3-6, 6-9 та 9-11 підлягають виконанню однорідним ресурсом. Максимальна потреба ресурсу припадає на період виконання роботи 3-6 у ранній термін та складає 12 одиниць. Ліміт на використання ресурсу складає 8 одиниць.

 

 

 

 

За рахунок збільшення тривалості роботи 3-6 на всю величину її повного резерву та переносу початків робіт 6-9 та 9-11 досягається виконання обмежень на наявні ресурси. При цьому всі наступні роботи можуть бути розпочаті у пізній термін.

 


ТЕМА 16. Теорія ігор.

 

16.1. Основні поняття та визначення. Класифікація ігор.

16.2. Матричні парні антагоністичні ігри з нульовою сумою.

16.2.1 Платіжна матриця гри.

16.2.2 Рішення гри в чистих стратегіях. Ціна гри. Сідлова точка платіжної матриці.

16.2.3. Спрощення платіжної матриці гри.

 

16.1. Основні поняття та визначення

Теорія ігор – це сукупність математичних методів для аналізу й оцінки правил поведінки в конфліктних ситуаціях.

Гра – це спрощена, формалізована модель конфліктної ситуації.

Гра відрізняється від реальної ситуації тим, що ведеться вона по цілком визначених правилах. Ці правила визначають можливі варіанти дій учасників гри, послідовність чергування дій сторін і кількісний результат, до якого приводить дана сукупність дій сторін.

Кожна зі сторін, що суперничають, у теорії ігор називається гравцем.

Розвиток гри в часі представляється у виді окремих рішень, послідовних чи етапів ходів.

2. Ходом називається вибір одного з передбачених правилами гри варіантів рішення. Ходи поділяються на особисті і випадкові.

3. Особистим ходом називається свідомий вибір гравцем одного з можливих у даній ситуації гри рішень (наприклад – будь-який хід у шаховій чи шашковій грі).

4. Випадковим ходом називається вибір рішення деяким "механізмом випадкового вибору" (наприклад – кидання монети, вибір карти з перетасованої колоди і т.п.). Ігри, що складаються тільки з випадкових ходів теорією ігор не розглядаються.

Розрізняють ігри з повною інформацією і гри з неповною інформацією.

5. Гра з повною інформацією – це така гра, у якій кожен гравець при кожнім особистому ході знає результат усіх попередніх ходів супротивника і його можливостей (наприклад – шахи, шашки, карткові ігри в "відкриту").

6. Гра з неповною інформацією – якщо не виконуються умови попередньої гри з повною інформацією (наприклад доміно, бойові дії, карткові ігри в "закриту").

Відзначимо, що більшість конфліктних ситуацій, узятих із практики, представляють гри з неповною інформацією.

7. Стратегія гравця – є докладний опис того, як повинен діяти гравець (яке повинен обирати рішення) у всіх можливих ситуаціях, що склалися в процесі гри.

Поняття стратегії – одне з основних у теорії ігор, зупинимося на ньому трохи докладніше.

Звичайно гравець у процесі гри не дотримує якихось твердих, фіксованих правил, а рішення в кожнім ході приймається в залежності від сформованої ситуації. Однак, теоретично справа не зміниться, якщо така система рішень буде прийнята заздалегідь. У цьому випадку говорять, що гравець вибрав визначену стратегію. Тоді він може і не брати участь у грі особисто, а замінити свою участь списком правил, що за нього буде застосовувати незацікавлена особа (суддя, ЕОМ).

У залежності від кількості можливих стратегій ігри поділяються на кінцеві і нескінченні.

8. Кінцева гра – це така гра, у якій у кожного гравця мається тільки кінцеве число стратегій.

9. Нескінченна гра – це така гра, у якій хоча б в одного з гравців мається нескінченне число стратегій.

10. Якщо стратегія має вигляд "вибрати певне рішення", те така стратегія називається чистою стратегією.

11. Якщо стратегія має вид "вибрати рішення з імовірністю , рішення з імовірністю , рішення з імовірністю ( і )", то така стратегія називається змішаною стратегією.

 

Класифікація ігор.

 

Класифікацію ігор можна проводити: за кількістю гравців, кількістю стратегій, характеру взаємодії гравців, характеру виграшу, кількості ходів, стану інформації і т.ін.

В залежності від кількості гравців розрізняють ігри двох і n гравців. Перші з них найбільш вивчені. Ігри трьох і більше гравців менш досліджені через виникаючі принципові труднощі і технічні можливості одержання рішення. Чим більше гравців - тим більше проблем.

За кількістю стратегій ігри поділяються на кінцеві і нескінченні. Якщо в грі всі гравці мають кінцеве число можливих стратегій, то вона називається кінцевою. Якщо ж хоча б один із гравців має нескінченну кількість можливих стратегій гра називається нескінченною.

За характером взаємодії ігри поділяються на:

безкоаліційні: гравці не мають права вступати в угоди, утворювати коаліції;

коаліційні (кооперативні) – можуть вступати в коаліції.

У кооперативних іграх коаліції наперед визначені.

За характером виграшів ігри поділяються на: ігри з нульовою сумою (загальний капітал усіх гравців не міняється, а перерозподіляється між гравцями; сума виграшів усіх гравців дорівнює нулю) і ігри з ненульовою сумою.

За видом функцій виграшу ігри поділяються на: матричні, біматричні, неперервні, опуклі, сепарабельні, типу дуелей і ін.

Матрична гра – це кінцева гра двох гравців з нульовою сумою, у якій задається виграш гравця 1 у виді матриці (рядок матриці відповідає номеру застосовуваної стратегії гравця 2, стовпець – номеру застосовуваної стратегії гравця 2; на перетині рядка і стовпця матриці знаходиться виграш гравця 1, що відповідає застосовуваним стратегіям).

Для матричних ігор доведено, що кожна з них має рішення і воно може бути легко знайдене шляхом зведення гри до задачі лінійного програмування.

Біматрична гра – це кінцева гра двох гравців з ненульовою сумою, у якій виграші кожного гравця задаються матрицями окремо для відповідного гравця (у кожній матриці рядок відповідає стратегії гравця 1, стовпець – стратегії гравця 2, на перетині рядка і стовпця в першій матриці знаходиться виграш гравця 1, у другій матриці – виграш гравця 2.)

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

Неперервною вважається гра, у якій функція виграшів кожного гравця є неперервною в залежності від стратегій. Доведено, що ігри цього класу мають рішення, однак не розроблено практично прийнятних методів їхнього перебування.

Якщо функція виграшів є опуклою, то така гра називається опуклою. Для них розроблені прийнятні методи рішення, що складаються у відшуканні чистої оптимальної стратегії (певного числа) для одного гравця й імовірностей застосування чистих оптимальних стратегій іншого гравця. Така задача вирішується порівняно легко.

 

16.2. Матричні парні антагоністичні ігри з нульовою сумою.

16.2.1 Платіжна матриця гри.

 

Мається кінцева гра, у якій перший гравець , що прагне одержати максимальний виграш, має стратегій, а другий гравець має стратегій. Така гра називається грою чи матричною грою.

Позначимо:

стратегії гравця : ;

стратегії гравця : .

Припустимо, що кожна сторона вибрала свою стратегію: , . Якщо гра складається тільки з особистих ходів (особистий хід – свідомий вибір гравцем одного з можливих у даній ситуації рішення), то вибір стратегій , однозначно визначає результат гри – виграш гравця (позитивний чи негативний). Позначимо його (позитивні коефіцієнти – є виграш гравця , негативні коефіцієнти – є виграш гравця чи програш гравця ).

Якщо гра містить крім особистих і випадкові ходи, то виграш при парі стратегій і є величина випадкова. У цьому випадку оцінкою очікуваного виграшу (будемо говорити надалі завжди про виграш гравця ) є математичне очікування (середнє значення). Будемо його позначати так само через .

Припустимо, що нам відомі значення при кожній парі стратегій. Значення в парній грі зручніше за все представляти у виді прямокутної таблиці (матриці). Рядка цієї матриці відповідають стратегіям , а стовпці – стратегіям . Така матриця називається матрицею чи гри платіжною матрицею.

 

A i B j B 1 B 2 .... B n
A 1 a 11 a 12 .... a 1n
A 2 a 21 a 22 .... a 2n
.... .... .... .... ....
A m a m1 a m2 .... a mn

 

 

16.2.2 Рішення гри в чистих стратегіях. Ціна гри. Сідлова точка платіжної матриці.

 

Оптимальною стратегією гравця називається така стратегія, яка при багаторазовому повторенні гри забезпечує даному гравцю максимально можливий середній виграш (мінімально можливий середній програш). При виборі цієї стратегії в теорії ігор виходять із припущення, що супротивник щонайменше так само розумний, як і ми самі, і робить все для того, щоб перешкодити нашому виграшу.

Будемо розглядати поки тільки чисті стратегії. Визначимо найкращу серед наших стратегій: . Розглянемо послідовно кожну стратегію від до . Причому, вибираючи - ту стратегію, ми повинні розраховувати, що супротивник відповість на неї тією з стратегій , для якої наш виграш мінімальний. Знайдемо в -му рядку мінімальне з чисел і позначимо його .

.

Випишемо числа (мінімуми рядків) праворуч поруч з матрицею у виді додаткового стовпця. Після визначення ми повинні обрати з усіх стратегій ту, для якої число максимальне. Позначимо це максимальне значення , тоді

,

чи підставляючи, маємо

.

Величина називається нижньою ціною гри, чи максимальним виграшем (максиміном). Та стратегія, гравця А, що відповідає максимину , називається його максиминною стратегією.

Проведемо аналогічні міркування за супротивника В. Природно, він зацікавлений у тому, щоб звернути наш виграш у мінімум, тобто він повинен переглянути усі свої стратегії від до , і виділити для кожної з них максимальне значення виграшу. Знайдемо в -м стовпці максимальне з чисел і позначимо його :

.

Випишемо числа (максимуми стовпців) знизу матриці у вигляді додаткового рядка. Після визначення гравець В обирає із усіх стратегій ту, для якої число мінімальне. Позначимо це мінімальне значення через , тоді

,

чи після підстановки

.

Величина називається верхньою ціною гри, чи мінімаксним виграшем (мінімаксом). Та стратегія гравця В, що відповідає мінімаксу , називається його мінімаксною стратегією.

Принцип обережності, що диктує гравцям вибір відповідних стратегій (максимінну і мінімаксну), є в теорії ігор основним і називається принципом мінімаксу.



Поделиться:


Последнее изменение этой страницы: 2016-12-29; просмотров: 1203; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.87.17.177 (0.131 с.)