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

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

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

Tayanch so’z va iboralar: takrorlanuvchi (ekvivalent) strategiyalar, befoyda strategiyalar, strategiyalar qavariq kombinasiyasi, chiziqli programmalashtirish masalasi, ikkilanma masalalar jufti, optimal yechim, optimal strategiyalar, o’yin bahosi.


1. Matritsaviy o’yinni soddalashtirish

Agar o’yinning to’lovlar matritsasi egar nuqtaga ega bo’lmasa, optimal aralash strategiyalarni va o’yin bahosini topish masalasi matritsa o’lchamlari kattalashgan sari murakkablashadi.

To’lovlar matritsasini tahlil qilish shuni ko’rsatadiki, takrorlanuvchi va befoydaligi ayon bo’lgan strategiyalardan voz kechish yordamida o’yin o’lchamini kichraytirish va natijada, uni yechishni bir muncha osonlashtirish mumkin.
To’lovlar matritsasi , , , bo’lgan – o’lchamli o’yin berilgan bo’lsin. O’yinning bahosini orqali, I va II o’yinchi sof strategiyalarini , , aralash strategiyalarini esa orqali belgilaymiz.
1-ta’rif. Agar matritsaning biror satrining ( ustunining) hamma elementlari boshqa bir satri ( ustuni) mos elementlariga teng bo’lsa, ya’ni bo’lsa, strategiyalar takrorlanuvchi yoki ekvivalent strategiyalar deb ataladi.
2-ta’rif. Agar matritsa biror satrining ( ustunining) barcha elementlari boshqa bir satr ( ustuni) elementlaridan katta (kichik bo’lmasa), ya’ni bo’lsa, strategiya befoyda strategiya deb ataladi.
Berilgan -o’lchamli matritsaning -satrini ( -ustunini) o’chirgandan keyin hosil bo’lgan ( )-o’lchamli matritsani bilan belgilaymiz.
Quyidagi teorema o’rinlidir.
1-teorema. Faraz qilaylikki, I (II) o’yinchining strategiyasi befoyda yoki biror strategiyaga ekvivalent bo’lsin. U holda:
1)
2) I (II) o’yinchining o’yindagi optimal aralash strategiyasi o’yinda ham optimal bo’ladi;
3) agar I o’yinchining II o’yinchining) o’yindagi optimal strategiyasi bo’lsa, I o’yinchining (II o’yinchining) o’yindagi optimal strategiyasi bo’ladi.
Bu teoremadan foydalangan holda matritsaviy o’yin o’lchamini kichraytirish quyidagicha bajariladi.
Agar to’lovlar matritsasining biror - satri ( -ustuni) shu matritsa qolgan satrlari (ustunlari) qavariq kombinasiyasidan katta (kichik) bo’lmasa, o’yinni yechish uchun shu satrni (ustunni) o’chirish mumkin. Bunda I (II) o’yinchining ( ) optimal strategiyasida deb olinadi.
1-misol. To’lovlar matritsasi 1-jadvalda berilgan o’yin soddalashtirilsin va yechimi topilsin.
1-jadval