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

3-Misol. To’lovlar matritsasi 5-jadvalda berilgan o’yinning yechimi va bahosi topilsin.

5-jadval II I
	1	2	3
	3	1	1
	1	3	1

Bu o’yinga mos keluvchi chiziqli programmalashtirish ikkilanma masalalar juftini tuzamiz:

(8)
(9)
Dastlab (9) masalani simpleks – usul bilan yechamiz. Buning uchun yangi o’zgaruvchilar kiritib, uni kanonik shaklga keltiramiz:

Bu masala uchun mos dastlabki simpleks-jadval 6-jadval ko’rinishda bo’ladi. Simpleks-jadvalar ustida ketma-ket shakl almashtirishlar o’tkazib, uchinchi iterasiyada optimal yechimni hosil qilamiz (7-9-jadvallar)


6-jadval

			1	1	1	0	0	0
	bazis
0		1	1	2	3	1	0	0	1
0		1	3	1	1	0	1	0	1/3
0		1	1	3	1	0	0	1	1
		0	-1	-1	-1	0	0	0

7-jadval

			1	1	1	0	0	0
	bazis
0		2/3	0	5/3	8/3	1	-1/3	0	2/5
1		1/3	1	1/3	1/3	0	1/3	0	1
0		2/3	0	8/3	2/3	0	-1/3	1	1/4
		1/3		-2/3	-2/3	0	1/3	0

8-jadval

			1	1	1	0	0	0
	bazis
0		1/4	0	0	9/4	1	-1/8	-5/8	1/18
1		1/4	1	0	1/4	0	3/8	-1/8	1
1		1/4	0	1	1/4	0	-1/8	3/8	1
		1/2	0	0	-1/2	0	1/4	1/4

9-jadval

			1	1	1	0	0	0
	bazis
1		1/9	0	0	1	4/9	-1/18	-5/18
1		2/9	1	0	0	-1/9	7/18	-1/18
1		2/9	0	1	0	-1/9	-1/9	4/9
		5/9	0	0	0	2/9	2/9	1/9

Oxirgi 9-jadvaldan (9) masala yechimini topamiz:

Demak, II o’yinchining optimal aralash strategiyasi va o’yin bahosi quyidagicha bo’ladi.

(8) masala uchun optimal yechimni 9-jadvalning satrida turgan ikkilanma baholardan foydalanib topamiz: Demak, I o’yinchining optimal aralash strategiyasi quydagichadir:



Muammoli masala va topshiriqlar

Ikki o’yinchining nol yig’indili o’yini uchun shunday to’lovlar matritsasini tuzingki, uni:

a) 2x2 o’yinga keltirish mumkin bo’lsin;
b) 2x2 o’yinga keltirish mumkin bo’lmasin.
1- topshiriqda ko’rsatilgan har bir holga mos tuzilgan o’yinlardan bittadan hal qiling.
Quyidagi o’yinlarni soddalashtiring:
a) ; b) ; d) .
3- topshiriqda keltirilgan o’yinlar uchun mos chiziqli programmalashtirish masalalari juftlarini tuzing va ularni yechish yordamida o’yinchilarning optimal strategiyalarini aniqlang.


Mustaqil ishlash uchun savollar:

1. 
   Takrorlanuvchi (ekvivalent) va befoyda strategiyalar qanday aniqlanadi?
   
2. 
   Matritsaviy o’yinni soddalashtirish haqidagi teorema. U qanday qo’llaniladi?
   
3. 
   Matritsaviy o’yin chiziqli programmalashtirishning qanday masalalar juftiga keltiriladi?
   
4. 
   Matritsaviy o’yinga mos chiziqli programmalashtirish masalalari yechimi asosida o’yin yechimi va bahosi qanday topiladi?
   

Mavzuni mustahkamlash uchun tavsiya etiladigan adabiyotlar

1. Вагнер Г. Основы исследований операции. Т. 1–3. М.: Мир. 1972-73.

2. Зайченко Ю. Б. Исследование операций. Киев. 1979.
3. Таха Х. Введение в исследование операций. Т. 1, 2. М.: Мир. 1981.
4. Дюбин Г. Н., Суздал В. Г. Введение в прикладную теорию игр. М.: Наука, 1981.