Mavzu: O’yinlar nazariyasi masalasini chiziqli programmalashtirish masalasiga keltirish

2-teorema. va  aralash strategiyalar jufti va V haqiqiy son matritsali o‘yinning yechimi bo‘lishi uchun  sof strategiyalarda
 (10.1)
bo‘lib,  sof strategiyalarda
_ (10.2)
tengsizlik o‘rinli bo‘lishi zarur va yetarlidir. Teorema shartlarini qanoatlantiruvchi aralash strategiyalar optimal strategiya, V haqiqiy son esa, o‘yinning bahosi deb ataladi.Demak,  to‘plamni matritsali o‘yinning yechimi ekanligini tekshirish uchun (10.1) va (10.2) tengsizliklarning bajarilishini tekshirish lozim.
3-misol. matritsa bilan berilgan o‘yinning yechimini toping Yechish.Avvalo o‘yinning egar nuqtasi bor-yo‘qligini tekshiramiz.Buning uchun, har bir satrnining minimal elementi: ni va har bir ustunning maksimal elementi: ni topamiz.U holda,

Demak, o‘yin egar nuqaga ega emas va o‘yinning yechimi aralash optimal strategiya bo‘ladi, o‘yinning bahosi esa chegarada yotadi.A o‘ynovchining aralash strategiyasi vektor-satr, B o‘ynovchining aralash strategiyasi vektor-ustundan iborat bo‘lsin.2-teoremaga asosan,

Bunga,

tenglamani qo‘shamiz.Sistemani yechib, ekaligini topamiz.

Ikkinchi tomondan,

Bundan,

Shunday qilib, bu o‘yinda



_{vektorlar optimal strategiyalar bo‘lib, o‘yinning bahosi}


3. Matritsali o‘yinni chiziqli programmalash masalasiga keltirish
 o‘lchovli matritsa bilan berilgan o‘yinni qaraymiz:

matritsa egar nuqtaga ega emas, deb hisoblaylik va shuning uchun o‘yinning yechimini  ва  aralash strategiyalar shaklida izlaymiz. 2-teoremaga asosan, birinchi A o‘ynovchining optimal strategiyasi va V o‘yin bahosi uchun
(10.3)
tengsizlik o‘rinli bo‘ladi.Aniqlik uchun, V>0 deylik.Bunga hamma vaqt erishish mumkin, chunki matritsaning barcha elementlariga bitta shunday C o‘zgarmasni qo‘shish mumkinki, u optimal strategiyasini o‘zgarishiga olib kelmaydi, faqatgina o‘yin bahosini C ga oshiradi xolos.
(10.3) tengsizlikni ikkala tomonini V ga bo‘lib,



<sub>ni hosil qilamiz.

deb belgilasak, u holda


(10.4)


(10.5)
ni hosil qilamiz.Kiritilgan belgilashga ko‘ra, shart ko‘rinishda yoziladi.Shundai qilib, birinchi o‘yinchi eng katta yutuqqa ega bo‘lishga intilar ekan, u miqdorni minimumini tа’minlashi lozim. Bu munosabatdan birinchi o‘yinchining optimal strategiyasini aniqlash (10.4),(10.5) shartlarni qanoatlaniruvchi
(10.6)
funksiyaning minimum qiymatini topishga keltiriladi.


Yuqoridagi mulohazalardan, ikkinchi o‘yinchining optimal strategiyasini aniqlash
(10.7)</sub>


(10.8)
<sub>shartlarni qanoatlantirvshi


(10.9)
funksiyaning maksimum qiymatini topishga keltiriladi, bu yerda .
Shunday</sub> qilib, matritsa bilan berilgan masalani yechish uchun quyidagi _{ikkilanishlar masalalari jufini tuzish va ularning yechimlarini topish zarur.}
To‘g‘ri masala: (10.7), (10.8) shartlarni qanoatlantiruvchi (10.9) funksiyaning maksimum qiymatini toping.
Ikkilanish masalasi: (10.4), (10.5) shartlarni qanoatlantiruvchi (10.6) funksiyaning minimum qiymatini toping.
Ikkilanishlar masalalalari juftining yechimidan foydalanib,

larni topamiz.

Shunday qilib, o‘yinlar yechimini chiziqli programmalashtirish masalasi metodini qo‘llab topish jarayoni quyidagi bosqichni o‘z ichiga oladi.
1,Berilgan matritsali o‘yinga mos ikkilanish masalalari jufti tuziladi.
2. Iikkilanish masalalari juftining optimal rejasi topiladi.
3. Iikkilanish masalalari jufti rejasi bilan o‘yinning optimal strategiyasi va yutug‘i orasidagi munosabatlardan foydalanib, o‘yinning yechimi topiladi.

4-masala.

matritsa bilan berilgan o‘yinning yechimini toping.