Алгоритм приведення матричної гри до задачі лінійного програмування - Оптимальне планування виробництва методами лінійного програмування

Для побудови алгоритмів розв'язання задач матричних ігор використовується властивість оптимальних змішаних стратегій: оптимальна змішана стратегія першого гравця гарантує йому виграш не менший ціни гри за будь-яких стратегій другого гравця і рівній ціні гри за оптимальної стратегії другого гравця. Використання названої властивості матричних ігор дає можливість привести задачу пошуку оптимальних змішаних стратегій до задачі лінійного програмування. Розглянемо одну з методик побудови відповідного алгоритму[9].

Маємо матричну гру за відомої матриці

H = {hIj} (I=1,2,..., m; j=1,2,..., n).

Перший гравець має чисті стратегії А1, А2,..., Аm, другий - В1, В2,...,Вn. Необхідно знайти оптимальні змішані стратегії

SA0 =(p10,p20,..., pM0) та SB0 =(g10, g20,..., gM0),

Де pI0 та gJ0 - ймовірності використання відповідних чистих стратегій гравцями.

Використовуючи можливість афінних перетворень матриці, без застережень можна вважати, що hIj>=0 і V >0.

Якщо перший гравець використовує свою оптимальну змішану стратегію

SA0=(p10, p20,...,pM0)

Проти будь-якої чистої стратегії BIj другого гравця, то його очікуваний гарантований виграш, тобто математичне сподівання виграшу

HJ =.

Наголосимо, що значення {pI0} поки що невідомі. За оптимальної стратегії

SA0= (p10, p20,..., pM0)

Гравця А його середні виграші за будь-якої чистої стратегії супротивника будуть не менше ціни гри V, тому можемо записати і гарантувати виконання системи:

(2.2)

Кожну з наведених нерівностей помножимо на 1/V і введемо нові зміни:

X1=p10/v; x2=p20/v;......;xM=pM0/v.

За нових змінних система запишеться так:

(2.3)

Скориставшись умовою

P10+p20+...+pM0 =1

(сума всіх ймовірних дорівнює ймовірності достовірної події) та, маємо:

X1+x2+...+xM =1/v.

Мета першого гравця - максимізувати гарантований виграш, тобто ціну гри V. Але максимізація ціни гри V обумовлює мінімізацію величини 1/V, тому розв'язання задачі пошуку величин x1,x2..., xM Можна сформулювати так: знайти величини змінних xI так, щоб вони задовольняли системі лінійних обмежень за умови досягнення найменшого значення лінійної функції:

Z=x1+ x2+...+ xM.

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

Та максимальний гарантований виграш V.

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

Другого гравця використовуються умови:

    1. середній очікуваний програш другого гравця за умови використання ним оптимальної стратегії не перевищує ціни гри, які б стратегії не використовував перший гравець; 2. гравець В прагне мінімізувати свій гарантований програш, тобто досягти максимуму величини 1/V.

За названих умов змінні g10, g20,..., gN0 задовольняють нерівностям:

(2.4)

Якщо ввести нові змінні

То система матиме вигляд:

(2.5)

До того ж змінні мають задовольнити умові:

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

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

Похожие статьи




Алгоритм приведення матричної гри до задачі лінійного програмування - Оптимальне планування виробництва методами лінійного програмування

Предыдущая | Следующая