|
Matritsali uyin bilan chizikli programmalash masalasining ekvivalentligi
Faraz qilaylik, quyidagi matritsali o‘yin berilgan bo‘lsin:
Yuqoridagi 4, 5-ta’riflarga ko‘ra o‘ynovchi shunday vektor va sonini izlashi kerakki, ular quydagi sistemani qanoatlantirsin:
(9.3.1)
Xuddi shuningdek, o‘ynovchi shunday vektorni aniqlashi kerakki, u
(9.3.2)
sistemani qanoatlantirsin.
matritsaning har bir elementini musbat qilish mumkin. Buning uchun uning barcha elementlariga mos ravishda biror o‘zgarmas son qo‘shiladi. Demak, deyish mumkin. (9.3.1), (9.3.2) sistemalarning har bir tengsizlik va tengliklarini ga bo‘lamiz va
deb qabul qilamiz, bunda
Shuning uchun yutug‘ini maksimallashtirishi kerak bo‘lgan o‘ynovchi
ni minimallashtirish lozim. o‘ynovchi esa yig‘indini maksimallashtirishi kerak.
Bunday shartlarda (9.3.1), (9.3.2) munosabatlarni ularga ekvivalent chiziqli programmalash masalasi Bilan almashtirish va quyidagi simmetrik ikkalangan masalalarni hosil qilish mumkin.
1 – m a s a l a . Shunday vektorni aniqlash kerakki, u yig‘indiga minimal qiymat berib,
shartlarni qanoatlantirsin.
II m a s a l a (I masalaga ikkilangan masala). Ushbu
shartlari qanoatlantiruvchi va yig‘indiga maksimum qiymat beruvchi vektor aniqlansin.
Har bir o‘yin yechimga ega bo‘lganligi uchun yuqoridagi ikkilangan chiziqli programmalash masalalarining optimal planlari mavjud va
Ikkilangan masalalarning va optimal planlaridan ekvivalent o‘yinning optimal aralash strategiyalariga o‘tishni va vektorlarning har bir komponentlarini mos ravishda va larga bo‘lish bilan bajariladi.
Agar o‘zaro ikkilangan masalalrdan biri simpleks usul bilan yechilgan bo‘lsa, ikkinchisining optimal plani oxirgi simpleks jadvalda hosil bo‘lar edi. Planning komponentlari yechilgan masalaning qo‘shimcha o‘zgaruvchilarga mos keluvchi lardan iborat bo‘ladi.
O‘yin muammosini chiziqli programmalash masalasiga keltirishning ikkinchi usuli quyidagicha:
o‘ynovchi uchun masala yana (9.3.1) munosabatlar Bilan beriladi. (9.3.1) dagi birinchi ta tengsizlikni manfiy bo‘lmagan qo‘shimcha o‘zgaruvchilar kiritish yo‘li Bilan teng kuchli tenglamalarga aylantiramiz, ya’ni
Birinchi tenglama keyingi ta tenglamaning har biridan ayiramiz hamda birinchi tenglamaning chap qismini chiziqli funksiya deb qabul qilamiz. Natijada quyidagi chiziqli programmalash masalasini hsil qilamiz:
M i s o l . Matritsali o‘yin berilgan:
Unga ekvivalent chiziqli programmalash masalasini tuzish uchun yuqorida keltirilgan usullarning ikkinchisidan foydalanamiz.
Chegaraviy shartlar sistemasini tuzamiz:
Manfiy bo‘lmagan o‘zgaruvchilarni kiritib, tengsizliklarni tenglamalarga aylantiramiz:
Birinchi tenglamani ikkinchi va uchinchi tenglamalardan ayirib, berilgan matritsali o‘yinga ekvivalent bo‘lgan chiziqli programmalash masalasining chegaraviy shartlarini hosil qilamiz:
Masalaning chiziqli funksiyasi esa dan iborat bo‘ladi.
Endi berilgan chiziqli programmalash masalasini matritsali o‘yin ko‘rinishida ifodalash mumkin ekanini ko‘ramiz.
Quyidagi chiziqli programmalash masalasi berilgan bo‘lsin:
(9.3.3)
(9.3.4)
Bu masalaga ikkilangan chiziqli programmalash masalasi:
(9.3.5)
(9.3.6)
Bizga ma’lumki, bunday ikkilangan masalalardan biri optimal planga ega bo‘lsa, ikkinchisi ham yechimga ega bo‘lib, bo‘ladi.
Faraz qilaylik (9.3.3) – (9.3.6) shartlar Bilan berilgan (masalalarning optimal planlari mavjud va mos ravishda birinchi va ikkinchi masalalarning optimal plani bo‘lsin,
(9.3.3) sistemaning birinchi tengsizligini ga ikkinchisini ga va hokazo ko‘paytirib qo‘shish natijasida
(9.3.7)
tengsizilkni hosil qilamiz. (9.3.5) munosabatlarni qo‘llansak, berilgan va unga ikkilangan masalalarning hamma planlari uchun o‘rinli bo‘lgan
(9.3.8)
tengsizlik hosil bo‘ladi. bunda esa kelib chiqadi. (9.3.8) tengsizlikka teskari tengsizlik
ko‘rinishdadir, yoki
(9.3.9)
Bu tengsizlikdan ekani kelib chikadi. Bulardan esa (9.3.3), (9.3.5) tengsizliklarniyechish,berilgan va unga ikkilangan masalalarning optimal planlarini aniklashga olib keladi vabunda buldadi. (9.3.3), (9.3.5) va (9.3.9) sistemalarning har bir tengsizligini noma’lum musbat o‘zgaruvchiga ko‘paytirib, quyidagini hosil qilamiz:
(9.3.10)
bu yerda (9.3.10) sistemani shartdagi yechimidan berilgan va ikkilangan masalalarning optimal planini osongina hosil qilish mumkin. (9.3.10) sistemani quyidagi
(9.3.11)
matritsa formada yozish mumkin. Bu yerda matritsa o‘lchovli vektor qatorlar, 0 esa o‘lchovli nol vektor ustun (9.1.11) formadagi matritsani ikki o‘lchovli nol summali simmetrik o‘yin matritsasi, vektor qatorni – yutug‘ini maksimum qiladigan o‘ynovchining aralash strategiyasi deb qarash mumkin. Simmetrik o‘yin narxi nolga teng bo‘lishi uchun 5-ta’rifdan (9.3.11) tengsizliklar sistemasining
shartdagi yechimi unga mos o‘yinning yechimi bo‘ladi.
O‘yinlar nazariyasining asosiy teoremasiga ko‘ra bu o‘yinning yechimi hamma vaqt mavjuddir. Biroq o‘yinga ekvivalent bo‘lgan chiziqli programmalash masalasi yechimga ega bo‘lmasligi mumkin. Bunday hol simmetrik o‘yinning optimal strategiyasida bo‘lgan holda yuz beradi.
Agar optimal strategiyada bo‘lsa, berilgan va unga ikkilangan chiziqli programmalash masalalarining yechimlari quyidagi formulalar orqali aniqlanadi:
; ,
bu yerda vektor ko‘rilayotgan simmetrik o‘yinning optimal aralash strategiyasi.
Do'stlaringiz bilan baham: |
