Опуклі множини та їх властивості

Опуклі множини та їх властивості

При дослідженні задач математичного програмування велеке значення має така глобальна властивість функцій f і як опуклість (увігнутість) та тісно зв’язана з нею властивість опуклості множин.

Озн. Множина W C називаэться опуклою якщо для всіх x, y є W та λ є [0,1] виконується умова λx + (1- λ)y є w.

Озн. Проекцію точки на опуклу множину W наз таку точку є W, що || - || = =d при цьому d наз відстанню точки від множини W.

Теорема (про проекцію точки на множину): Для довільної опуклої замкненої множини W і довільної точки існує єдина точка з множини W, що є проекцією на W.

Теорема (про відділяючу гіперплощину): Нехай W замкнена опукла множина і не належить цій множині тоді існує гіперплощина (a,x)+b=0 така що (a, )+b >0, (a,y)+b <0 у є W.

Іншими словами гіперплощина (a,x)+b=0 строго відділяє точку від множини W.

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

Теорема (про опорну гіперплощину): Через кожну точку межі опуклої замкненої множини W можна провести принаймні одну опорну гіперплощину.

Наслідок: якщо w c замкнена опукла обмежена множина, то через довільну точку є (скінченну), не належить W можна провести опорну гіперплощину, тобто існує вектор C≠0 такий, що для всіх y є W (с, y- )≤ 0 або (c, y) ≤ (c, ).

Теорема (про гіперплощину, яка розділяє дві опуклі площини, що не перетинаються): Якщо множина внутрішніх точок опуклої множини Х, не порожня і не перетинається з опуклою множиною У, то для всіх множин Х та У існує розділяюча їх гіперплощина, тобто існує вектор С≠0 такий, що (с,x) ≤ (c,y) для всіх х є Х, та для всіх у є У.

Загальна ЗЛП та її допустима область

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

Загальна задача лінійного програмування записується у вигляді:

(1)

(2)
.(3)

Вектор , координати якого задовольняють систему обмежень (2) та умови невід’ємності змінних (3), називається допустимим розв’язком (планом) задачі лінійного програмування.

Перехід від загальної ЗЛП до стандартної

Задачу (3.1)—(3.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (3.2) всі b_i (i = 1, 2, …, m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь b_i від’ємне, то, помноживши i -те обмеження на
(– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i -те обмеження має вигляд нерівності а_{i 1} х ₁+ а_{i 2} х ₂+…+ а_inx_n ≤ b_i, то останню завжди можна звести до рівності, увівши додатковузмінну x_{n +1}:

a_{i 1} x ₁+ a_{i 2} x ₂+…+ a_inx_n + x_{n + 1} = b_i.

Аналогічно обмеження виду а_{k 1} x ₁ + a_{k 2} x ₂ + … + a_knx_n ≥ b_k зводять до рівності, віднімаючи від лівої частини додаткову змінну х_{n +2}, тобто:

a_{k 1} x ₁ + a_{k 2} x ₂ + … + a_knx_n – x_{n + 2} = b_k (х_{n +1} ≥ 0, х_{n +2} ≥ 0).

АЛГОРИТМ СИМПЛЕКС МЕТОДУ

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

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

4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунку елементів нової симплекс таблиці.

5. Повторення дій, починаючи з пункту (3).

У разі застосування симплекс методу до розв’язування задач лінійного програмування можливі такі випадки:

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

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

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

Симплекс-таблицi

Спочатку розглянемо допоміжне твердження, що дозволяє стандартним чином (за допомогою симплекс-перетворення) обчислювати симплекс-рiзницi для змінних у КЗЛП.

Нехай на s-у кроцi симплекс-методу є КЗЛП

Лема 1.5. Якщо з цільової функції L(x) КЗЛП виключити базисні змінні, то коефіцієнтами при небазисних змінних будуть відповідні їм симплекс-рiзницi i з'являється вільний член, що дорівнює значенню цільової функції в базисній точці, що розглядається.

Тепер симплекс-рiзницi змінних у КЗЛП легко одержати, якщо на початковій iтерацiї додати до вихідних непрямих обмежень ЗЛП рівняння L(x) = 0, з якого виключені базисні змінні. На наступних iтерацiях симплексне перетворення застосовується також i до цього нового рівняння.

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

6.

7. Метод штучного базису

:

застосовується в тих випадках, коли для канонічної форми задачі ЛП не означений початковий опорний план. Тоді симплекс-методом розв’язується перетворена задача зі штучним базисом. Вона утворюється з початкової задачі додаванням до лівої частини векторного рівняння-обмеження стількох штучних одиничних векторів з відповідними невід’ємними штучними змінними, щоб створена матриця містила систему т одиничних, лінійно-незалежних векторів. В цільову функцію початкової задачі додається складова, яка дорівнює добутку суми штучних змінних на число (- М), в разі максимізації Z, або + М, в разі мінімізації Z, де М - досить велике число.

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

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

Розглянемо задачу лінійного програмування:

(2.60)

(2.61)

(2.62)

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

(2.63)

У результаті додавання змінних у рівняння системи (2.61) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (2.63) називають розширеною, або М-задачею

8.

9.

10.11.

Муравйов

Олішевський

Метод мінімального елемента

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

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

кожному кроцi побудови початкового базисного розв'язку для завантаження вибирається клітинка з мінімальним значенням c _{i j}.

Метод мінімального елемента в результаті також дає допустимий базисний

розв'язок ТЗЛП.

У таблицях 2.2 та 2.3 наведені початкові базисні розв'язки ТЗЛП, побудовані

за методом пiвнiчно-захiдного кута (невироджений та вироджений).

Наведемо приклад побудови початкового базисного розв'язку методом мінімального елемента (таблиця 2.4).

Таблиця 2.4

Таблиця 2.2

15.

16.

Рудик

Рудик

Аракелова

Метод Форда-Фалкерсона

Дан граф , де А − множина вузлів, В − множина дуг. Граф G має одне джерело s і один стік t. Дуги b_ij мають обмежену пропускну здібність.

,

(3.1)

де f_ij – можливий потік через гілку b_ij;

U_ij – задане значення пропускної здібності для гілки b_ij.

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

,

(3.2)

Задача складається у визначенні дугових потоків f_ij таких, щоб загальний потік з джерела s в стік t був максимальним:

,

(3.3)

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

де g_i, g_j – кількість одиниць потоку.

Позитивна помітка збільшує потік по гілці b_ij, але так, щоб сумарний потік не перевищував U_ij; негативна помітка зменшує потік по гілці b_ij, але так, щоб він не став від’ємним.

Вузли помічаються послідовно від 1 до n.

Якщо вузол a_i помічений, то a_j можна помітити з нього по прямій гілці на величину не більшу, за , а по зворотній гілці на величину .

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

Потім всі мітки стираються і переходять до наступної ітерації.

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

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

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

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

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

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

Приклад 3. Дан граф

1 ітерація. Шлях: 1-3-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =2

2 ітерація. Шлях: 1-2-3-4-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

3 ітерація. Шлях: 1-2-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

4 ітерація. Шлях: 1-3-2-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

5 ітерація. Шлях: 1-4-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

6 ітерація. Ще будь-який шлях вибрати неможливо.

Максимальний потік в мережі, поданий графом, що розглядається, дорівнює сумі приростів потоків на кожній ітерації, тобто V = 6.

В даному прикладі можна визначити максимальний потік, використовуючи теорему про максимальний потік і мінімальний розріз, яким являється розріз .

Другий метод Гоморi

Другий метод Гоморi призначається для розв'язування частково (зокрема,

повнiстю) цiлочисельних ЗЛП (ЧЦЗЛП):

(4.17)

(4.18)

(4.19)

-ціле, j =1,…,p (4.20)

Метод розв'язування задачі (4.17) – (4.20) грунтується на тій же ідеї, що i метод розв'язування ПЦЗЛП. А саме: розв'язується допоміжна ЗЛП (4.17) – (4.19), що одержується з вихідної відкиданням умови цiлочисельностi (4.20). Якщо ця задача розв'язку не має, то, очевидно, i вихідна ЧЦЗЛП не має розв'язку. Якщо ж ЗЛП (4.17) – (4.19) має розв'язок, то він аналізується на допустимість для задачі (4.17) – (4.20). Якщо знайдений оптимальний розв'язок є цiлочисельним (у розумінні умов (4.20)), то він одночасно є оптимальним i для задачі (4.17) – (4.20). Iнакше від розв'язаної ЗЛП переходять до нової допоміжної ЗЛП додаванням лінійного обмеження, яке задовольняють цiлочисельнi розв'язки вихідної ЧЦЗЛП, але не задовольняє одержаний нецiлочисельний розв'язок вихідної ЗЛП. Це

додаткове обмеження визначає деяку вiдтинаючу площину i називається

правильним вiдтином. Додавання нових правильних вiдтинiв відбувається доти, поки на деякому кроцi не буде одержано цiлочисельний розв'язок допоміжної задачі, що є, очевидно, оптимальним розв'язком ЧЦЗЛП.

Нехай на останній iтерацiї симплекс-методу при розв'язуванні допоміжної

ЗЛП її непрямі обмеження набули вигляду:

i, отже, її розв'язком є n -вимiрний вектор .

Нехай існує номер такий, що — дробове число. Тоді правильний

вiдтин у другому методі Гоморi будується згідно наступної теореми, яку ми наводимо без доведення.

Теорема 4.2. Лiнiйне обмеження

або, що рiвносильно,

де

(4.23)

a - додаткова змінна, є правильним вiдтином для ЧЦЗЛП (4.17) – (4.20).

Зауважимо, що якщо r в обмеженні (4.22) є індекс першої нецiлочисельної змінної серед перших p змінних, то алгоритм другого методу Гоморi, що формулюється нижче, є скiнченним.

Третiй метод Гоморi

Розглядаємо ПЦЗЛП:

(4.14)

(4.25)

(4.26)

-ціле, j =1,…,n (4.27)

Нехай непрямі обмеження ЗЛП (4.24) – (4.26), наприклад, у базисі A 1,..., A m

приведені до майже канонічного вигляду:

де — цілі i симплекс-рiзницi Якщо , i = 1,...,m, то обмеження визначають оптимальний розв'язок задачі (4.24) – (4.27), iнакше визначається деякий цiлочисельний МДБР вихідної ЗЛП. Можна було б, звичайно, вибрати один з індексів i, для якого  i < 0, i виконати iтерацiю двоїстого симплекс-методу. Проте у цьому випадку цiлочисельнiсть параметрів нової симплекс-таблицi була б, взагалі кажучи, порушена через необхідність

ділення на ведучий елемент перетворення. Цiлочисельнiсть нової nтаблиці гарантується лише тоді, коли ведучий елемент дорівнює – 1.

Виявляється,що можна побудувати додаткове обмеження, якому задовольняють всі цiлочисельнi розв'язки задачі (4.24) – (4.27) i яке разом з тим визначає ведучий рядок перетворення, що має ведучий елемент – 1. Будується

воно за l -м обмеженням системи (4.28), для якого

(4,29)

Якщо серед обмежень (4.28) є декілька з від'ємною правою частиною, то l

вибирається, як правило, з умови

Подiлимо обидві частини (4.29) на довільне число a > 0 I запишемо одержаний результат у вигляді:

(4.30)

Лiва частина (4.30) при , j = 1,...,n, являє собою різницю двох величин

тобто строго більша – 1. Отже,права частина, будучи цілим числом при цiлочисельних x j, задовольняє умову

(4.31)

яка є вірною для будь-якого допустимого розв'язку задачі (4.24) – (4.27).

Уводячи додаткову змінну x n+1, перепишемо (4.31) у вигляді

(4.32)

Очевидно, що з від'ємності випливає від'ємність [ ] i навпаки. Тому [ ] < 0 i серед чисел [ ] є від'ємні, тобто рядок таблиці, що визначається новим обмеженням (4.32), може бути прийнятий за ведучий для наступного симплексного перетворення. Разом з тим при

кожному від'ємному , j = m +1,...,n, відповідає [ ] = – 1, тобто ведучий

елемент цього перетворення явно дорівнює – 1.

Отже, розширюємо наявну симплекс-таблицю за рахунок (m+1)-го рядка з

елементами [ ] (елементи, що відповідають базисним змінним, рівні нулю) та

одиничного стовпця A n+1, що відповідає додатковій змінній . Потiм виконується симплекс-перетворення з (m+1)-м ведучим рядком I ведучим стовпцем, що вибирається за правилами двоїстого симплекс-методу. Тоді нова симплекс-таблиця буде повністю цiлочисельною.Описана послідовність дій складає окрему iтерацiю алгоритму третього методу Гоморi. Iтерацiї виконуються доти, поки не буде отримана симплекс-таблиця, в якій усі праві частини невід'ємні, або є рядок з від'ємною правою частиною i невід'ємними рештою елементів. У першому випадку ПЦЗЛП розв'язана, у другому — її обмеження є суперечливими. Якщо на будь-якiй iтерацiї одна з додаткових змінних переходить з небазисних у базисні, то відповідні їй рядок i стовпець симплекс-таблицi викреслюються з подальшого розгляду.

Стельмах

Стельмах

29-32.

Задачі теорії гри

Теорія ігор вперше була систематично викладена Нейманом і Моргенштерном та оприлюднена лише 1944 року в монографії «Теорія ігор і економічної поведінки», хоча окремі результати були опубліковані ще в 20-х роках. Нейман і Моргенштерн написали оригінальну книгу, яка містила переважно економічні приклади, оскільки економічні задачі простіше за інші описати за допомогою чисел. Під час другої світової війни і одразу після неї теорією ігор серйозно зацікавились військові, які одразу побачили в ній математичний апарат для дослідження стратегічних проблем і підготовки рішень. Потім головна увага знову була звернута до економічних проблем. Нині сфера застосування теорії ігор значно розширилась. Так, у соціальних науках апарат теорії ігор застосовується у психології для аналізу торгових угод та переговорів, а також для вивчення принципів формування коаліцій тощо.

Основні поняття теорії ігор

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

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

За умов ринкової економіки все частіше мають місце конфліктні ситуації, коли два або більше колективів (індивідуумів) мають протилежні цілі та інтереси, причому результат дії кожної із сторін залежить і від дії супротивника. Класичним прикладом конфліктної ситуації в економіці є відношення продавець — покупець (монополія — монопсонія). Складніші ситуації виникають, коли в суперечці інтересів беруть участь об'єднання чи коаліції.

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

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

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

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

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

Існує дуже багато різних ігор. Прикладом «гри» в буквальному розумінні цього слова, передусім, є спортивна, карточна гра, шахи тощо. Від реальної конфліктної ситуації гра відрізняється не лише спрощеною формою, а також наявністю певних правил, за якими мають діяти її учасники. Дослідження таких формалізованих ігор звичайно не може дати чітких рекомендацій для реальних умов, проте є найзручнішим об'єктом для вивчення конфліктних ситуацій і оцінки можливих рішень з різних поглядів. Розраховані на основі ігрових моделей оптимальні плани не визначають єдино правильне рішення за складних реальних умов, проте слугують математично обґрунтованою підставою для прийняття таких рішень.

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

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

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

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

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

Матричні ігри двох осіб

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

Отже, маємо два гравці А і В (гра двох осіб з нульовою сумою). Кожний гравець вибирає одну із можливих стратегій: позначимо стратегії гравця А - , стратегії гравця В - .

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

Нехай виграш гравця А, виграш гравця В.

Оскільки гра з нульовою сумою, то . Тоді в разі, якщо , то .

Отже, мета гравця А — максимізувати величину , а гравця В — мінімізувати її. Нехай , тобто маємо матрицю А:

,

де рядки відповідають стратегіям , а стовпці — стратегіям .

Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці — це виграш гравця А, якщо він вибрав стратегію , а гравець В — стратегію .

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

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

Така стратегія гравця А позначається і має назву максимінної, а величина гаран

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: