Mustaqil yechish uchun misollar
Butun sonli programmalashtirish masalasini yeching.
1.
butun
x
x
x
x
x
x
x
x
x
Z
,
0
,
0
6
3
2
35
5
7
max
2
2
1
2
1
2
1
2
1
2.
5
,
1
,
,
0
3
3
9
3
3
24
4
6
max
2
2
5
2
1
4
2
1
3
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
x
x
x
x
x
Z
j
J:
8
max
,
3
;
2
*
x
Z
X
opt
J:
19
max
,
3
;
3
;
2
;
1
;
3
*
x
Z
X
opt
3.
4
,
1
,
,
0
9
2
3
6
2
min
4
2
1
3
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
x
x
Z
j
4.
4
,
1
,
,
0
10
4
8
3
2
min
3
4
4
2
1
3
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
x
x
Z
j
J:
3
min
,
1
;
2
;
1
;
2
*
x
Z
X
opt
J:
11
min
,
1
;
1
;
1
;
2
*
x
Z
X
opt
5.
4
,
1
,
,
0
9
3
2
5
2
min
4
2
1
3
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
x
x
Z
j
6.
2
,
1
,
,
0
6
20
2
5
max
9
16
2
1
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
Z
j
J:
3
min
,
0
;
2
;
3
;
0
*
x
Z
X
opt
J:
68
max
,
4
;
2
*
x
Z
X
opt
7.
2
,
1
,
,
0
15
10
3
7
2
4
max
4
2
1
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
Z
j
6.
2
,
1
,
,
0
3
3
2
6
3
2
max
3
2
1
2
1
2
1
j
butun
x
x
x
x
x
x
x
x
Z
j
J:
5
max
,
1
;
1
*
x
Z
X
opt
J:
4
max
,
1
;
1
*
x
Z
X
opt
51
V-bob. O’yinlar nazariyasi
5.1. O’yinlar nazariyasi modeli haqida tushuncha
Matematik modellashtirishda optimal yechim va strategiyalar XVIII asrda
taklif etilgan. Emmanuel Lasker, Ernst Sermelo va Emil Borel kabi olimlar XX asr
boshlarida matematik ziddiyatli maqsadlar nazariyasi g`oyasini ilgari surdilar.
So`ngra o`yinlar nazariyasi Dj. Nesh tomonidan tahlil qilinadi, bunga ko`ra,
o`yinda qatnashayotgan o`yinchilardan biri g`olib bo`lib yutishi, ikkinchi
o`yinchining esa yutqazishidan iborat bo`lgan ziddiyatli vaziyat hosil bo`lib, bunda
o`yinchilar uchun,
muvozanat turg`unligiga
asoslangan
optimal strategiyalar
aniqlanadi. Bunga ko`ra, o`yinchilar o`zlarining optimal strategiyalarida qolishligi
talab etiladi, aksincha esa o`yin natijasi o`yinchilar foydasiga hal bo`lmaydi.
Amaliyotda shunday masalalar bo`ladiki, aniqmaslik sharoitida qaror qabul
qilishga to`g`ri keladi, ya`ni ziddiyatli vaziyatlar sodir bo`ladi, ya`ni ikki (undan
ham ko`p bo`lishi mumkin) tomonning qiziqishlari har xil bo`lib, ular har birining
ziddiyatli vaziyatdagi harakati, boshqasining harakatiga bog`liq bo`ladi.
Shunday vaziyatlarda, bir qatnashuvchi harakatining samarasi, boshqa
qatnashuvchilarning
harakatiga
bog`liq
bo`lishi,
ikki
turga
bo`linadi:
qatnashuvchilarning maqsadlari mos tushib, ular kelishgan holda birgalikda
harakat qilishadi va qatnashuvchilarning maqsadlari mos tushmaydi. Ikkinchi tur
vaziyat,
ziddiyatli vaziyat
deyiladi. Ziddiyatli vaziyatlarning matematik modellarini
qurish, hamda bunday vaziyatdagi masalalarni yechish uchun usullar ishlab chiqish
bilan, o`yinlar nazariyasi shug`ullanadi. Ziddiyatli vaziyatlarda optimal qaror qabul
qilish uchun, ziddiyatli vaziyatlarning matematik nazariyasini ishlab chiqish
o`yinlar nazariyasi
deyiladi.
Ziddiyatli vaziyatlarga misollar: korxonaning tovar sotishdan oladigan
daromadi, tovarga qo`yilgan narx bilan birga, iste`molchilarning sotib olgan shu
tovarlari miqdoriga ham bog`liq. Tashkilot, tovarlar assortimentini tanlashda,
boshqa tashkilotlarning qanday assortimentdagi tovarlar ishlab chiqarishlarini
hisobga olishi zarur.
Iqtisodiyotda ziddiyatli vaziyatlar ko`p uchrab, u xilma-xil xarakterda
bo`ladi. Masalan, ta`minotchi va iste`molchi, bank va mijoz, sotuvchi va xaridor
orasidagi
munosabatlar. Ular har birining, o`z maqsadlari bo`lib, unga erishish
uchun, optimal yechim qabul qilishadi. Bunda ularning har biri, o`z maqsadlari
bilan birga, o`z sheriklarining maqsadga erishish uchun qabul qilayotgan
qarorlarini ham hisobga olishlari kerak.
O`yinlar nazariyasining masalasi
, o`yinchilarning har biri uchun aniq
optimal strategiya ishlab chiqishdan iborat.
O`yinchining strategiyasi
deb, shunday
mumkin bo`lgan harakatlar sistemasiga aytiladiki, o`yinning har bir etapida
alternativ variantlardan shunday yurish tanlanadiki, bu boshqa o`yinchilarning
harakatiga qarshi bo`lgan bir qiymatli aniqlangan eng yaxshi yurish hisoblanadi.
Optimal strategiya
, o`yin ko`p marta qaytarilganda, o`yinchini maksimal
o`rtacha yutuq bilan ta`minlaydi (yoki qarshi tomonni minimal o`rtacha yutqazish
bilan ta`minlaydi).
52
Ziddiyatli vaziyat,
antagonistik (nol yig`indili)
deyiladi, agar bir tomon
yutug`ining biror miqdorga o`sishi, ikkinchi tomon yutug`ining shu miqdorga
kamayishiga olib kelsa va aksincha.
O`yin – bu real ziddiyatli vaziyatning matematik modelidir.
O`yinda
qatnashayotgan tomonlar,
o`yinchilar
deyiladi. Ziddiyatning natijasi
yutuq
deyiladi. O`yin qoidasi – o`yinchilar harakatlari variantlarini aniqlaydigan sistema
bo`lib: bu o`yinchining sherigi to`g`risidagi axborotlar hajmi, yutuqqa olib
boradigan harakatlar to`plamidan iboratdir. O`yin qoidasiga asosan, harakatlar
variantini tanlash va amalga oshirish, o`yinchining
yurishi
deyiladi.
Shaxsiy yurish
– o`yinchining ongli ravishda, harakatlar variantidan birini
tanlashdan iborat (masalan, shaxmat o`yinida).
Tasodifiy yurish
– o`yinchining tasodifiy tanlagan harakatidir (masalan,
o`yin soqqasini otish). Biz faqat shaxsiy yurishlarni ko`rib chiqamiz.
O`yinchi yurishni, o`yinning har bir bosqichidagi konkret vaziyatga bog`liq
ravishda tanlaydi. O`yinchi ma`lum bir strategiyani, oldindan tanlagan bo`lishi
ham mumkin.
O`yin
chekli
deyiladi, agar har bir o`yinchining chekli sondagi strategiyalari
mavjud bo`lsa, va aksincha bo`lsa,
cheksiz
deyiladi.
O`yin
juft
deyiladi, agar unda ikkita o`yinchi qatnashsa.
Ko`pchilik bilan
o`yin bo`ladi, agar unda ikkitadan ortiq o`yinchi qatnashsa. Biz faqat juft o`yinlarni
ko`rib chiqamiz. O`yinchilarni
A
va
B
bilan belgilaymiz.
Antagonistik o`yinning yechimi, bu har bir o`yinchi uchun
optimal
strategiyalarni
aniqlashdan iborat. Bunga ko`ra,
B
o`yinchi qanday strategiyani
tanlashidan qat`iy nazar,
A
o`yinchi kafolatlangan maksimal yutuqni olishi kerak,
ikkinchi holda esa,
A
o`yinchi qanday strategiyani tanlashidan qat`iy nazar,
B
o`yinchi o`zining minimal yutqizishiga erishishi zarur. Optimal strategiyalar,
turg`unligi
bilan xarakterlanadi, ya`ni bunda har bir o`yinchining optimal
strategiyalaridan chetlanishi, ular uchun zararli oqibatlarga olib keladi.
|
