|
O'yinlar nazaryasi masalasini chiziqli praogramalashtrish masalasiga keltrish
|
səhifə | 2/5 | tarix | 10.06.2023 | ölçüsü | 144,86 Kb. | | #116464 |
| O\'YINLAR NAZARYASI MASALASINI CHIZIQLI PRAOGRAMALASHTRISH MASALASIGA KELTRISH2 Matritsali o‘yinning yechimi
Yutuqlar matritsasi
ko‘rinishda bo‘lgan matritsali o‘yinni qaraylik. Agar A o‘ynovchi i-sof strategiyani tanlasa, u kamida
yutuqqa ega bo‘ladi va A o‘ynovchi o‘zining yutug‘ini maksimal qilishga harakat qiladi.Demak, u shunday i-sof strategiyani tanlashi kerakki, natijada uning yutug‘i maksimal bo‘lsin, yа’ni A o‘ynovchi
natijani beruvchi sof strategiyani tanlaydi. Ushbu kattaliknи 𝛼 bilan belgilaymiz:
Bu yerda, 𝛼 - A o‘ynovchining ishonchli yutug‘idan iborat bo‘lib u «o‘yinning quyi bahosi» deb ataladi: 𝛼 yutuqqa erishishga imkon beruvchi -sof strategiya «maksmin» deb ataladi. B o‘ynovchi o‘z navbatida, o‘zining eng katta mumkin bo‘lgan yutqazuvini minimallashtirishga harakat qiladi. Shuning uchun,
yutqazuvni beruvchi j-sof strategiyani tanlaydi. Bu yerda, 𝛽 - B o‘ynovchining ishonchli minimal yutqazuvidan iborat bo‘lib, u «o‘yinning yuqori bahosi» deb ataladi. 𝛽 yutqazuvga erishishga imkon beruvchi yurish ( -sof strategiya) «minimaks» deb ataladi.
Teorema.Har qanday matritsali o‘yinda o‘yinning 𝛼 quyi bahosi uning 𝛽 yuqori bahosidan oshmaydi, yа’ni .
Isboti. Tа’rifga asosan,
,
Bu munosabatlarni birlashtirsak,
munosabatga ega bo‘lamiz. Bundan, tengsizlikni hosil qilamiz. Bu tenglik i va j indekslarning ixtiyoriy kombinatsiyalari uchun, shu jumladan,
shartlarni qanoatlantiruvchi i va j lar uchun ham o‘rinlidir. Demak, tengsizlikka ega bo‘lamiz. Teorema isbotlandi.
Agar matritsali o‘yinning quyi va yuqori baholari o‘zaro teng bo‘lsa, yа’ni shart bajarilsa, u holda ushbu o‘yin egar nuqtaga hamda quyidagi shartni qanoatlantiruvchi bahoga ega deyiladi.
Bu holda, A matritsaning shartni qanoatlantiruvchi ( juftlikka mos keluvchi elementi egar nuqta deb ataladi. Bu element ustunda maksimal bo‘ladi va qatorda minimal bo‘ladi, yа’ni:
Agar B o‘ynovchi o‘zining minimaks strategiyasidan voz kechsa, uning yutqazuvi oshadi. Xuddi shuningdek, agar A o‘ynovchi o‘zining maksimin strategiyasidan voz kechsa, uning yutug‘i kamayadi. Demak, egar nuqtalarga o‘yinning , optimal strategiyalari mos keladi, hamda to‘plam o‘yinning yechimi deyiladi.
Dostları ilə paylaş: |
|
|