9-ma’ruza. Matritsali o’yinni chiziqli programmalash yordamida yechish Reja

2. Matritsaviy o’yinni chiziqli programmalashtirish ikkilanma masalalar juftiga keltirish

Endi va istalgan natural sonlar bo’lgan -matritsaviy o’yinni qaraymiz (4-jadval). Faraz qilaylikki, bu o’yinda egar nuqta mavjud bo’lmasin.

Bunday o’yinni aralash strategiyalarda yechishni chiziqli programmalashtirishning ikkilanma masalalar juftiga keltirish mumkinligini ko’rsatamiz.

4-jadval

II I			. . .		. . .
			. . .		. . .
			. . .		. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .
			. . .		. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .
			. . .		. . .

To’lovlar matritsasining barcha elementlarini manfiymas deb hisoblaymiz. Aks holda sonni matritsaning barcha elementlariga qo’shib, bahosi ga oshgan, lekin o’yinchilarning optimal strategiyalari o’zgarmasdan qolgan va to’lovlar matritsasi elementlari manfiymas bo’lgan o’yinni hosil qilish mumkin.

Agar I o’yinchi optimal aralash strategiyasini qo’llasa, u kafolatlangan yutuqqa ega bo’ladi, ya’ni bu holda II o’yinchi qanday strategiyasini qo’llamasin I o’yinchining yutug’i bo’lib, tengsizlik bajariladi( -o’yin bahosi). Shunday qilib,
, (1)
shartga ega bo’lamiz. (1) ning chap va o’ng taraflarini o’yin bahosi ga bo’lib,
, (2)
munosabatni hosil qilamiz. Yangi belgilash kiritamiz:
. (3)
U vaqtda (2) tengsizliklar
, (4)
ko’rinishda yoziladi. Bu yerda barcha , chunki , .
tenglikdan hamda (3) ifodadan o’zgaruvchilarning
(5)
shartni qanoatlantirishi kelib chiqadi.
I o’yinchining ni maksimallashtirishga intilishini hisobga olib, (4) va (5)dan
(6)
chiziqli programmalashtirish masalasiga kelamiz. (6) masalani yechib, o’yin bahosi va I o’yinchining optimal strategiyasi ni

formulalar bo’yicha topamiz.
II o’yinchining optimal strategiyasini topish uchun yuqoridagiga o’xshash ish yuritib
(7)
masalaga kelamiz. Bu masalaning optimal yechimidan foydalanib II o’yinchi uchun optimal strategiyani
,
formula bo’yicha topamiz.
Chiziqli programmalashtirishda (6) va (7) masalalar o’zaro ikkilanma masalalar juftini tashkil etadi.
Shunday qilib, -matritsaviy o’yinni yechish uchun quyidagi o’zaro ikkilanma masalalar juftiga ega bo’lamiz.

Agar , va , – bu masalalarning optimal yechimlari bo’lsa, o’yin bahosi va optimal strategiyalar

formulalar bo’yicha topiladi.