Oyun modellərinin konsepsiyası. Ödəniş matrisi

PRAKTİKİ İŞ №3

Oyun nəzəriyyəsi modelləri

Oyun modellərinin konsepsiyası

Oyun nəzəriyyəsi şəraitdə qərar qəbul etmək üçün müxtəlif növ tövsiyələrin hazırlanması ilə məşğul olur münaqişə vəziyyəti. Münaqişə vəziyyətlərini riyazi olaraq formalaşdıraraq, iki, üç və ya daha çox oyunçunun oyunu kimi təmsil oluna bilər, hər biri digər oyunçunun hesabına öz qazancını maksimuma çatdırmaq məqsədi güdür. Münaqişə vəziyyətinin riyazi modeli deyilir oyun, münaqişədə iştirak edən tərəflər - oyunçular, və münaqişənin nəticəsidir qalib. Hər rəsmiləşdirilmiş oyun üçün təqdim edirik qaydalar, yəni. müəyyən edən şərtlər sistemi:

1. oyunçu seçimləri;

2. tərəfdaşların davranışı haqqında hər bir oyunçunun malik olduğu məlumatların miqdarı;

3. hər bir hərəkət toplusunun gətirdiyi nəticə.

Bir qayda olaraq, qalibiyyət kəmiyyətlə müəyyən edilə bilər (məsələn, məğlubiyyət - 0, qələbə - 1, heç-heçə - ½). Oyun adlanır buxar otağı, əgər iki oyunçu iştirak edirsə və çoxsaylı oyunçuların sayı ikidən çox olduqda. Oyun adlanır sıfır məbləğli oyun oyunçulardan birinin qazancı digərinin itkisinə bərabər olarsa. Qaydalarda nəzərdə tutulmuş hərəkətlərdən birinin seçilməsi və həyata keçirilməsi deyilir hərəkət oyunçu. Hərəkətlər şəxsi və təsadüfi ola bilər. şəxsi hərəkət- oyunçunun mümkün hərəkətlərdən birinin şüurlu seçimi (şahmat oyununda hərəkət), təsadüfi hərəkət- təsadüfi seçilmiş hərəkət (qarışdırılmış göyərtədən kart seçmək).

Oyunçu strategiyası vəziyyətdən asılı olaraq hər bir şəxsi hərəkət üçün onun hərəkətinin seçilməsini müəyyən edən qaydalar toplusu adlanır. Oyun adlanır son oyunçunun məhdud sayda strategiyası varsa və sonsuz- əks halda.

Oyunu həll etmək və ya tapmaq üçün oyun qərarı, hər bir oyunçu üçün optimallıq şərtini təmin edən strategiya seçmək lazımdır, yəni. oyunçulardan biri qəbul etməlidir maksimum qalibiyyət ikincisi öz strategiyasına sadiq qaldıqda. Eyni zamanda, ikinci oyunçu olmalıdır minimum itki birincisi öz strategiyasına sadiq qalarsa. Bu cür strategiyalar optimal adlanır. məqsəd oyun nəzəriyyəsi hər bir oyunçu üçün optimal strategiyanı müəyyən etməkdir. Optimal strategiyanı seçərkən hər iki oyunçunun öz maraqları baxımından ağlabatan davrandığını güman etmək təbiidir.

Ödəniş matrisi. Oyunun aşağı və yuxarı qiyməti

Qoşalaşmış sonlu oyunu nəzərdən keçirək. Qoy oyunçu AMMA var m qeyd etdiyimiz şəxsi strategiyalar A 1, A 2,…, A m. Qoy oyunçu B mövcuddur nşəxsi strategiyalar, biz onları işarə edirik B 1 , B 2 ,…, B n . Deyirlər ki, oyunun bir ölçüsü var m ´ n. Oyunçuların hər hansı bir cüt strategiya seçməsi nəticəsində A i Və B j oyunun nəticəsi unikal şəkildə müəyyən edilir, yəni. qalib aij oyunçu AMMA(müsbət və ya mənfi) və itki (- aij) oyunçu IN. Matris P=(a ij), onun elementləri strategiyalara uyğun gəlirlərdir A i Və B j, adlanır ödəniş matrisi və ya oyun matrisi.

Nümunə - "Axtarış" oyunu

Oyunçu AMMA 1-ci sığınacaqda gizlənə bilər - bu strategiya kimi işarə edək A 1 və ya sığınacaqda 2 - strategiya A 2. Oyunçu IN ilk oyunçunu sığınacaq 1-də axtara bilər - strategiya 1-də, və ya sığınacaqda 2 - strategiya 2-də. Əgər oyunçu AMMA Vault 1-də yaşayır və oyunçu tərəfindən aşkar edilir IN, yəni. bir neçə strategiya həyata keçirilir (A 1, B 1), sonra oyunçu AMMA cərimə ödəyir, yəni. a 11=–1. Eynilə, biz də alırıq a 22=–1. Aydındır ki, strategiyalar (A 1, B 2) Və (A 2, B 1) oyunçuya verin AMMA 1 qazan, yəni a 12=a 21=1. Beləliklə, ödəmə matrisini alırıq

Oyunu nəzərdən keçirin m ´ n matris ilə P=(a ij) və oyunçunun strategiyaları arasında ən yaxşısını müəyyənləşdirin AMMA. Strategiya seçimi A i, oyunçu AMMA oyunçunu gözləmək lazımdır IN ona strategiyalardan biri ilə cavab verəcək j-da, bunun üçün oyunçu üçün ödəniş AMMA minimal (oyunçu IN oyunçuya "zərər verməyə" çalışır AMMA).

ilə işarələyin a i oyunçunun ən aşağı gəliri AMMA strategiya seçərkən A i bütün mümkün oyunçu strategiyaları üçün IN(ən kiçik ədəd i-ödəniş matrisinin üçüncü sırası), yəni. .

Bütün nömrələr arasında a iən böyüyü seçin: . a zəng edək aşağı oyun qiyməti , və ya maksimum qalibiyyət (maksimum ). Bu B oyunçusunun istənilən strategiyası üçün A oyunçusunun zəmanətli qazancı. Nəticədə, .

Maksiminə uyğun strategiya deyilir maksimum strategiya. Oyunçu IN oyunçunun qazancını azaltmaqda maraqlıdır AMMA; strategiyanın seçilməsi B j, A. İşarə üçün maksimum mümkün gəliri nəzərə alır.

Bütün nömrələr arasından ən kiçikini seçib ona zəng edirik b yüksək oyun qiyməti , və ya minimum qazanc (minimaks ). Bu A oyunçusunun istənilən strategiyası üçün B oyunçusunun itirilməsinə zəmanət verilir. Nəticədə, .

Minimax strategiyası deyilir Minimax strategiyası. Oyunçulara ən ehtiyatlı minimum və maksimum strategiyaların seçimini diktə edən prinsip adlanır. Minimax prinsipi.

statistik oyunlar

Oyuna aparan bir çox vəzifələrdə qeyri-müəyyənlik hərəkətin həyata keçirildiyi şərtlər haqqında məlumatın olmamasından qaynaqlanır. Bu şərtlər başqa oyunçunun şüurlu hərəkətlərindən deyil, adətən "təbiət" adlanan obyektiv reallıqdan asılıdır. Belə oyunlar təbiətlə oyunlar adlanır (statistik oyunlar).

Bir tapşırıq

Bir neçə illik istismardan sonra sənaye avadanlığı aşağıdakı vəziyyətlərdən birindədir: 1-də - avadanlıq profilaktik təmirdən sonra növbəti ildə istifadə edilə bilər; B 2 - gələcəkdə avadanlıqların problemsiz işləməsi üçün onun ayrı-ayrı hissələrini və birləşmələrini dəyişdirmək lazımdır; 3-də - avadanlıq əsaslı təmir və ya dəyişdirilməsini tələb edir.

Mövcud vəziyyətdən asılı olaraq B 1, B 2, B 3, müəssisənin rəhbərliyi aşağıdakı qərarlar qəbul edə bilər: A 1 - avadanlığın zavod mütəxəssisləri tərəfindən təmiri, bunun üçün müvafiq xərclər tələb olunur a 1 = 6, a 2 = 10 və 3 = 15 pul vahidi; A 2 - xüsusi təmirçilər qrupunu çağırın, bu vəziyyətdə xərclər b 1 \u003d 15, b 2 \u003d 9, b 3 \u003d 18 pul vahidi olacaq; A 3 - köhnəlmiş avadanlığı qalıq dəyərinə sataraq avadanlığı yenisi ilə əvəz edin. Bu tədbirin nəticələrinin ümumi xərcləri müvafiq olaraq 1 =13, 2 =24, 3 =12 pul vahidi ilə bərabər olacaqdır.

Tapşırıq

1. Təsvir edilən vəziyyətə oyun sxemi verərək, onun iştirakçılarını müəyyənləşdirin, tərəflərin mümkün təmiz strategiyalarını göstərin.

2. Matrisin a ij elementlərinin mənasını izah edərək (onlar niyə mənfidir?) ödəniş matrisini tərtib edin.

3. Aşağıdakı fərziyyələr əsasında itkiləri minimuma endirmək üçün müəssisə rəhbərliyinə növbəti ildə avadanlığın istismarı ilə bağlı hansı qərarın tövsiyə edilməsinin məqsədəuyğun olduğunu öyrənin: a) müəssisədə analoji avadanlığın istismarında əldə edilmiş təcrübə göstərir avadanlığın göstərilən vəziyyətlərinin ehtimallarının müvafiq olaraq q 1 = 0,15 olduğunu; q 2 =0,55; q 3 \u003d 0,3 (Bayes testini tətbiq edin); b) təcrübə göstərir ki, avadanlığın hər üç mümkün vəziyyəti eyni dərəcədə ehtimal olunur (Laplas meyarını tətbiq edin); c) avadanlığın ehtimalı haqqında dəqiq heç nə demək olmaz (Wald, Savage, Hurwitz meyarlarını tətbiq edin). Hurvits kriteriyasında g=0,8 parametrinin qiyməti təyin edilir.

Həll

1) Təsvir edilən vəziyyət statistik bir oyundur.

Statistika müəssisənin rəhbərliyidir, o, aşağıdakı qərarlardan birini qəbul edə bilər: avadanlığı özbaşına təmir etmək (strategiya A 1), təmirçiləri çağırmaq (strategiya A 2); avadanlığı yenisi ilə əvəz edin (strategiya A 3).

İkinci oyun tərəfi - təbiət, biz avadanlıqların vəziyyətinə təsir edən amillərin birləşməsini nəzərdən keçirəcəyik: avadanlıq profilaktik baxımdan sonra istifadə edilə bilər (vəziyyət B 1); avadanlığın fərdi komponentlərini və hissələrini dəyişdirmək lazımdır (vəziyyət B 2): lazım olacaq əsaslı təmir və ya avadanlığın dəyişdirilməsi (B 3 vəziyyəti).

2) Oyunun qazanc matrisini tərtib edin:

Ödəniş matrisi elementi a ij seçilmiş strategiya A i ilə avadanlıq B j vəziyyətində olarsa, müəssisə rəhbərliyinin xərclərini göstərir. Ödəniş matrisinin elementləri mənfidir, çünki hər hansı seçilmiş strategiya üçün müəssisə rəhbərliyi xərcləri öz üzərinə götürməli olacaq.

a) avadanlığa oxşar müəssisədə toplanmış əməliyyat təcrübəsi göstərir ki, avadanlığın vəziyyətlərinin ehtimalları q 1 =0,15-ə bərabərdir; q 2 =0,55; q 3 \u003d 0.3.

Ödəniş matrisini aşağıdakı kimi təqdim edək:

harada , (i=1,3)

Bayes meyarına görə, təmiz A i strategiyası optimal olaraq qəbul edilir, bu zaman statistikin orta qazancı maksimumlaşdırılır, yəni. =max tərəfindən təmin edilir.

Bayesian optimal strategiyası A 1 strategiyasıdır.

b) təcrübə göstərir ki, avadanlığın hər üç mümkün vəziyyəti eyni dərəcədə ehtimal olunur, yəni. = 1/3.

Orta qələbələr:

1/3 * (-6-10-15) \u003d -31/3 "-10.33;

1/3*(-15-9-18) = -42/3 = -14;

1/3 * (-13-24-12) \u003d -49/3 "-16.33.

Laplasa görə optimal strategiya A 1-dir.

c) avadanlığın ehtimalları haqqında dəqiq heç nə demək olmaz.

Wald meyarına görə, ən pis şərtlərdə maksimum qazancı təmin edən təmiz strategiya optimal olaraq qəbul edilir, yəni.

.

= maks(-15, -18, -24) = -15.

Beləliklə, A 1 strategiyası optimaldır.

Gəlin bir risk matrisi quraq, burada.

Oyunçunun strategiyası onun hər hansı mümkün vəziyyətdə və hər hansı faktiki məlumatla seçim etdiyi plandır. Təbii ki, oyunçu oyun irəlilədikcə qərarlar verir. Lakin nəzəri olaraq bütün bu qərarların oyunçu tərəfindən əvvəlcədən verildiyini güman etmək olar. O zaman bu qərarların məcmusu onun strategiyasını təşkil edir. Mümkün strategiyaların sayından asılı olaraq oyunlar sonlu və sonsuza bölünür. Oyun nəzəriyyəsinin vəzifəsi oyunçular üçün tövsiyələr hazırlamaq, yəni onlar üçün optimal strategiyanı müəyyən etməkdir. Optimal strategiya, oyun dəfələrlə təkrar edildikdə, verilmiş oyunçuya maksimum mümkün orta gəliri təmin edən strategiyadır.

Strateji oyunun ən sadə növü iki nəfərlik sıfır məbləğli oyundur (tərəflərin qazanclarının cəmi sıfırdır). Oyun iki hərəkətdən ibarətdir: A oyunçusu Ai (i = 1, 2, m) mümkün strategiyalarından birini seçir, B oyunçusu isə Bj (j = 1, 2, ., n) strategiyasını seçir və hər seçim burada edilir. tam məlumatsızlıq başqa bir oyunçunun seçimi.

A oyunçusunun məqsədi φ (Ai, Bj) funksiyasını maksimuma çatdırmaqdır, öz növbəsində B oyunçusunun məqsədi eyni funksiyanı minimuma endirməkdir. Oyunçuların hər biri funksiyanın dəyərinin asılı olduğu dəyişənlərdən birini seçə bilər. Əgər A oyunçusu Ai strategiyalarından bəzilərini seçirsə, bu, özlüyündə φ (Ai, Bj) funksiyasının dəyərinə təsir göstərə bilməz.

Ai-nin φ (Ai, Bj) dəyərinin böyüklüyünə təsiri qeyri-müəyyəndir; əminlik yalnız Bj dəyişəninin başqa oyunçusu tərəfindən φ-nin (Ai, Bj) minimuma endirilməsi prinsipinə əsaslanan seçimdən sonra baş verir. Bu halda Bj başqa oyunçu tərəfindən müəyyən edilir. φ (Ai, Bj)= aij olsun. Gəlin A matrisini yaradaq:

Matrisin sətirləri Ai strategiyalarına, sütunlar Bj strategiyalarına uyğundur. A matrisi qazanc və ya oyun matrisi adlanır. Matrisin aij elementi Ai strategiyasını, oyunçu B isə Bj strategiyasını seçdiyi təqdirdə oyunçunun qazancıdır.

Qoy A oyunçusu Ai strategiyasını seçsin; sonra ən pis halda (məsələn, seçim olarsa məşhur oyunçu C) o, min aij-ə bərabər mükafat alacaq. Bu ehtimalı gözləyərək, A oyunçusu minimum qazancını artırmaq üçün strategiya seçməlidir:

a = maksimum min aij

A dəyəri - oyunçu A-nın zəmanətli gəliri - oyunun aşağı qiyməti adlanır. a-nın alınmasını təmin edən Ai0 strategiyası maksimum adlanır.

Oyunçu B, strategiya seçərək, aşağıdakı prinsipdən çıxış edir: bəzi Bj strategiyasını seçərkən, onun itkisi matrisin j-ci sütununun elementlərinin dəyərlərinin maksimumunu keçməyəcək, yəni. max aij-dən az və ya ona bərabərdir

üçün maksimum aij dəstini nəzərə alaraq müxtəlif mənalar j, oyunçu B təbii olaraq j dəyərini elə seçəcək ki, onun maksimum itkisi β minimuma ensin:

β = min miax aij

β dəyəri oyunun yuxarı qiyməti, β-yə uyğun gələn Bj0 strategiyası isə minimax strategiyası adlanır.

Tərəfdaşların ağlabatan hərəkətləri ilə A oyunçusunun faktiki qazancı oyunun aşağı və yuxarı qiymətləri ilə məhdudlaşır. Bu ifadələr bərabərdirsə, yəni.

Oyun nəzəriyyəsi riyazi bir intizamdır, mövzusu münaqişə vəziyyətlərində qərar qəbul etmə üsullarıdır.

Vəziyyət deyilir münaqişə, onda əks məqsədlər güdən bir neçə (adətən iki) şəxsin maraqları toqquşarsa. Tərəflərin hər biri öz məqsədlərinə çatmaq üçün bir sıra fəaliyyətlər həyata keçirə bilər və bir tərəfin uğuru digərinin uğursuzluğu deməkdir.

İqtisadiyyatda konfliktli vəziyyətlər çox yaygındır (təchizatçı ilə istehlakçı, alıcı və satıcı, bankir və müştəri arasındakı münasibətlər). Münaqişə vəziyyətlərinə bir çox başqa sahələrdə də rast gəlinir.

Münaqişə vəziyyəti tərəfdaşların maraqları arasındakı fərq və onların hər birinin qarşıya qoyulan məqsədləri ən böyük dərəcədə həyata keçirən optimal qərarlar qəbul etmək istəyi ilə yaranır. Eyni zamanda, hər kəs təkcə öz məqsədləri ilə deyil, həm də tərəfdaşın məqsədləri ilə hesablaşmalı və tərəfdaşların verəcəyi bilinməyən qərarları nəzərə almalıdır.

Adətən münaqişə vəziyyətləri bir çox ikincil daxil olan amillərə görə birbaşa təhlil üçün çətindir. Münaqişə vəziyyətinin riyazi təhlilini mümkün etmək üçün yalnız əsas amillər nəzərə alınmaqla sadələşdirilməlidir. Münaqişə vəziyyətinin sadələşdirilmiş rəsmiləşdirilmiş modeli deyilir oyun, münaqişədə iştirak edən tərəflər - oyunçular və münaqişənin nəticəsi - qalib. Tipik olaraq, qazanc (və ya itki) kəmiyyətlə müəyyən edilə bilər; məsələn, itkini sıfır, qələbəni bir və heç-heçəni 1/2 ilə qiymətləndirə bilərsiniz.

Oyun bir kolleksiyadır Qaydalar oyunçuların davranışlarını təsvir edir. Oyunun başdan sona müəyyən bir şəkildə oynamasının hər bir nümunəsidir oyun partiyası. Qaydalarda nəzərdə tutulmuş hərəkətlərdən birinin seçilməsi və həyata keçirilməsi deyilir hərəkət oyunçu. Hərəkətlər şəxsi və təsadüfi ola bilər. şəxsi hərəkət- bu, oyunçunun mümkün hərəkətlərdən birinin şüurlu seçimidir (məsələn, şahmat oyununda hərəkət). Təsadüfi hərəkət- bu həm də bir çox variantdan birinin seçimidir, lakin burada seçim oyunçu tərəfindən deyil, bəzi təsadüfi seçim mexanizmi (sikkələr atmaq, qarışdırılmış göyərtədən kart seçmək) tərəfindən seçilir.

strategiya Oyunçu, vəziyyətdən asılı olaraq hər bir şəxsi hərəkət üçün hərəkətlərinin seçimini müəyyən edən qaydalar toplusudur.

Oyun yalnız şəxsi hərəkətlərdən ibarətdirsə, oyunçuların hər biri öz strategiyasını seçibsə, oyunun nəticəsi müəyyən edilir. Lakin oyunda təsadüfi gedişlər olarsa, o zaman oyun ehtimal xarakterli olacaq və oyunçuların strategiya seçimi hələ oyunun yekun nəticəsini müəyyən etməyəcək.

Üçün həll etmək oyun və ya oyunun həllini tapmaq üçün hər bir oyunçunun şərti təmin edən strategiya seçməsi lazımdır optimallıq, olanlar. oyunçulardan biri qəbul etməlidir maksimum qələbə, ikincisi öz strategiyasına sadiq qaldıqda. Eyni zamanda, ikinci oyunçu olmalıdır minimum itki birincisi öz strategiyasına sadiq qalarsa. Bu cür strategiyalar optimal adlanır. Optimal strategiyalar sabitlik şərtini təmin etməlidir, yəni. oyunçulardan hər hansı birinin bu oyunda öz strategiyasından əl çəkməsi zərərli olmalıdır.

Oyun nəzəriyyəsinin məqsədi hər bir oyunçu üçün optimal strategiyanı müəyyən etməkdir.

Qoşalaşmış sonlu oyunu nəzərdən keçirək. Qoy oyunçu AMMA var m qeyd etdiyimiz şəxsi strategiyalar A 1 , A2 , ..., A m . Qoy oyunçu IN mövcuddur n şəxsi strategiyalar, biz onları işarə edirik B1 , B2 , ..., B m . Deyirlər ki, oyunun bir ölçüsü var m × n . Oyunçuların hər hansı bir cüt strategiya seçməsi nəticəsində

A i və B j (i = 1, 2, ..., m; j = 1, 2, ..., n)

oyunun nəticəsi unikal şəkildə müəyyən edilir, yəni. qalib aij oyunçu AMMA (müsbət və ya mənfi) və itki ( - aij ) oyunçu IN . Tutaq ki, dəyərlər OU hər hansı bir cüt strategiya ilə tanınır (A i, B j ). Matris , onun elementləri strategiyalara uyğun gəlirlərdir Ai Və B j , adlanır ödəniş matrisi və ya oyun matrisi. Ümumi forma belə bir matris Cədvəl 3.1-də təqdim olunur.

Cədvəl 3.1

Bu cədvəlin sətirləri oyunçunun strategiyalarına uyğundur AMMA , və sütunlar oyunçunun strategiyalarıdır IN . Gəlin növbəti oyun üçün qazanc matrisi yaradaq.

Oyunu nəzərdən keçirin m × n matris ilə P = (a ij), i = 1, 2, ..., m; j = 1, 2, ..., n və strategiyalar arasında ən yaxşısını müəyyənləşdirin A 1 , A2 , ..., A m . Strategiya seçimi Ai oyunçu AMMA oyunçunu gözləmək lazımdır IN ona strategiyalardan biri ilə cavab verəcək B j , bunun üçün oyunçu üçün ödəniş AMMA minimal (oyunçu IN oyunçuya "zərər verməyə" çalışır AMMA ). ilə işarələyin a i , oyunçunun ən kiçik qazancı AMMA strategiya seçərkən Ai bütün mümkün oyunçu strategiyaları üçün IN (ən kiçik ədəd i-ödəniş matrisinin üçüncü sırası), yəni.

Maksiminə uyğun strategiya deyilir maksimum strategiya. Oyunçu IN oyunçunun qazancını azaltmaqda maraqlıdır AMMA ; strategiyanın seçilməsi B j , üçün mümkün olan maksimum ödənişi nəzərə alır AMMA . İşarə et

Minimaxa uyğun gələn strategiya minimaks strategiyası adlanır. Oyunçulara ən "ehtiyatlı" minimax və maksimal strategiyaların seçimini diktə edən prinsip adlanır. Minimax prinsipi. Bu prinsip hər bir oyunçunun rəqibin əks məqsədinə çatmağa çalışdığı ağlabatan fərziyyədən irəli gəlir. Oyunun aşağı və yuxarı qiymətlərini və problemdə müvafiq strategiyaları müəyyən edək.

Əgər oyunun yuxarı və aşağı qiymətləri eynidirsə, o zaman ümumi mənaüst və aşağı qiymət oyunlar α = β = v çağırdı oyunun xalis qiyməti , və ya oyunun bahasına . Oyunun qiymətinə uyğun minimax strategiyaları bunlardır optimal strategiyalar, və onların məcmusudur optimal həll , və ya oyun qərarı. Bu halda oyunçu AMMA maksimum zəmanət alır (oyunçu davranışından asılı olmayaraq) IN ) qalib v , və oyunçu IN minimum zəmanətə nail olur (oyunçu davranışından asılı olmayaraq AMMA ) zərər v . Oyunun həlli olduğu deyilir davamlılıq , yəni. oyunçulardan biri öz optimal strategiyasına sadiq qalırsa, o zaman digəri üçün optimal strategiyasından kənara çıxması sərfəli ola bilməz.

Cütləşdirmək təmiz strategiyalar Ai Və B j oyun üçün optimal həlli verir və yalnız uyğun element aij , həm sütununda ən böyüyü, həm də cərgəsində ən kiçikdir. Belə bir vəziyyət, əgər varsa, deyilir yəhər nöqtəsi (bir istiqamətdə yuxarı, digərində isə aşağı əyilən yəhərin səthinə bənzəyir).

İnventar idarəetmə modelinin əsas anlayışları.

Həm biznesdə, həm də istehsalatda davamlılığı təmin etmək üçün kifayət qədər maddi resurslar və ya təchizat ehtiyatı saxlamaq adi bir təcrübədir. istehsalat prosesi. Ənənəvi olaraq, inventar qaçılmaz xərc kimi baxılır, çox az inventar baha başa gələn istehsalın dayandırılmasına səbəb olur və çoxlu inventar kapitalını azaldır. İnventarın idarə edilməsinin vəzifəsi qeyd olunan iki ekstremal halı tarazlaşdıran inventar səviyyəsini müəyyən etməkdir.

İnventar idarəetmə modellərinin əsas xüsusiyyətlərini nəzərdən keçirin.

Tələb. Stoklu məhsula tələbat ola bilər deterministik(ən sadə halda - zamanla sabit) və ya təsadüfi. Tələbin təsadüfiliyi ya tələbin təsadüfi anı ilə, ya da deterministik və ya təsadüfi vaxtlarda təsadüfi tələb miqdarı ilə təsvir olunur.

Anbarın doldurulması. Anbarın doldurulması ya müəyyən fasilələrlə vaxtaşırı həyata keçirilə bilər, ya da ehtiyatlar tükəndikcə, yəni. onların müəyyən səviyyəyə endirilməsi.

Sifariş həcmi. Ehtiyatların vaxtaşırı doldurulması və təsadüfən tükənməsi halında, sifarişin miqdarı sifariş zamanı müşahidə olunan vəziyyətdən asılı ola bilər. Sifariş adətən ehtiyat müəyyən bir səviyyəyə çatdıqda eyni məbləğə təqdim olunur - sözdə sifariş nöqtələri.

Çatdırılma vaxtı.İdeallaşdırılmış inventar idarəetmə modellərində, sifariş edilən əlavənin anbara dərhal çatdırılması nəzərdə tutulur. Digər modellərdə sabit və ya təsadüfi vaxt intervalı üçün çatdırılmada gecikmə nəzərə alınır.

Çatdırılma dəyəri. Bir qayda olaraq, hər bir çatdırılmanın dəyərinin iki komponentdən - sifariş edilmiş partiyanın həcmindən asılı olmayan birdəfəlik xərclərdən və partiyanın həcmindən asılı olan (əksər hallarda xətti) xərclərdən ibarət olduğu güman edilir.

saxlama xərcləri.Əksər inventar idarəetmə modellərində ehtiyatın miqdarı praktiki olaraq qeyri-məhdud hesab edilir və saxlanılan ehtiyatın miqdarı nəzarət dəyişəni kimi istifadə olunur. Eyni zamanda, hər bir ehtiyat vahidinin vaxt vahidi üçün saxlanması üçün müəyyən haqq alındığı güman edilir.

Kəsir cəzası.İstənilən anbar qıtlığın qarşısını almaq üçün yaradılır müəyyən növ xidmət sistemindəki məhsullar. Lazımi vaxtda ehtiyatın olmaması avadanlıqların dayanması, qeyri-müntəzəm istehsal və s. ilə əlaqəli itkilərə səbəb olur. Bu itkilər adlanır kəsir cəzası.

fond nomenklaturası.Ən sadə hallarda anbarda eyni tipli məhsulların ehtiyatının və ya bircins məhsulun saxlanması nəzərdə tutulur. Daha çox çətin hallar hesab olunur çox elementli ehtiyat.

Anbar sisteminin quruluşu.Ən tam inkişaf etmişdir riyazi modellər tək şirin. Bununla belə, praktikada daha mürəkkəb strukturlar da mövcuddur: müxtəlif doldurma dövrləri və sifarişlərin çatdırılma müddətləri olan anbarların iyerarxik sistemləri, eyni iyerarxiya səviyyəli anbarlar arasında birja imkanları və s.

Qəbul edilmiş inventar idarəetmə strategiyasının effektivliyinin meyarı belədir xərc (xərc) funksiyası, ehtiyatda olan məhsulun tədarükünün ümumi dəyərini, onun saxlanmasını və cərimələrin dəyərini əks etdirir.

Ehtiyatların idarə edilməsi, maya dəyəri funksiyasının minimum dəyər aldığı inventarın doldurulması və istehlakı üçün belə bir strategiyanın tapılmasından ibarətdir.

Funksiyalara icazə verin və müvafiq olaraq ifadə edin:

Yenidən ehtiyat,

ehtiyat istehlakı,

Hazır məhsula tələbat

bir müddət üçün.

İnventar idarəetmə modelləri adətən müvafiq olaraq , , adlanan bu funksiyaların zaman törəmələrindən istifadə edir,

Oyun adlanır sıfır məbləğli oyun, və ya antaqonist, əgər oyunçulardan birinin qazancı digərinin itkisinə bərabərdirsə, yəni. oyunun tapşırığını yerinə yetirmək üçün onlardan birinin dəyərini göstərmək kifayətdir. təyin etsək a- oyunçulardan birini qazanmaq, b digərinin qazancıdır, onda sıfır məbləğli oyun üçün b = - a, buna görə də nəzərə almaq kifayətdir, məsələn, a.

Qaydalarda nəzərdə tutulmuş hərəkətlərdən birinin seçilməsi və həyata keçirilməsi deyilir hərəkət oyunçu. Hərəkətlər şəxsi və təsadüfi ola bilər.

şəxsi hərəkət- bu, oyunçunun mümkün hərəkətlərdən birinin şüurlu seçimidir (məsələn, şahmat oyununda hərəkət).

Təsadüfi hərəkət təsadüfi seçilmiş hərəkətdir (məsələn, qarışdırılmış göyərtədən kartı seçmək). İşimdə yalnız futbolçuların şəxsi gedişlərini nəzərə alacağam.

strategiya Bir oyunçu, vəziyyətdən asılı olaraq hər bir şəxsi hərəkət üçün hərəkətinin seçimini təyin edən qaydalar toplusu adlanır. Adətən oyun zamanı hər bir şəxsi hərəkətdə oyunçu konkret vəziyyətdən asılı olaraq seçim edir. Bununla belə, prinsipcə, bütün qərarların oyunçu tərəfindən əvvəlcədən (hər hansı bir vəziyyətə cavab olaraq) verilməsi mümkündür. Bu, oyunçunun qaydaların siyahısı və ya proqram şəklində verilə bilən müəyyən bir strategiya seçdiyini bildirir. (Beləliklə, kompüterdən istifadə edərək oyunu oynaya bilərsiniz). Oyun adlanır son hər bir oyunçunun məhdud sayda strategiyası varsa və sonsuz- əks halda.

Oyunu həll etmək və ya oyunun həllini tapmaq üçün hər bir oyunçu şərti qane edən strategiya seçməlidir. optimallıq, yəni. oyunçulardan biri qəbul etməlidir maksimum qalibiyyət ikincisi öz strategiyasına sadiq qaldıqda. Eyni zamanda, ikinci oyunçu olmalıdır minimum itki birincisi öz strategiyasına sadiq qalarsa. Bu cür strategiyalarçağırdı optimal. Optimal strategiyalar da qane etməlidir sabitlik vəziyyəti, yəni. oyunçulardan hər hansı birinin bu oyunda öz strategiyasından əl çəkməsi zərərli olmalıdır.

Oyun Nəzəriyyəsinin Məqsədi: hər bir oyunçu üçün optimal strategiyanın müəyyən edilməsi. Optimal strategiyanı seçərkən hər iki oyunçunun öz maraqları baxımından ağlabatan davrandığını güman etmək təbiidir.

Hər bir oyunçunun sonlu strategiya dəstinə malik olduğu antaqonist oyunlar deyilir matris oyunları. Bu ad bu cür oyunları təsvir etmək üçün aşağıdakı imkanlarla izah olunur. Satırların birinci oyunçunun strategiyalarına, sütunların ikincinin strategiyalarına, sıra və sütunların kəsişməsindəki cədvəlin xanalarının oyunun vəziyyətlərinə uyğun olduğu düzbucaqlı bir masa düzəldirik. Birinci oyunçunun qazancını hər bir hüceyrədə müvafiq vəziyyətə qoysaq, müəyyən bir matris şəklində oyunun təsvirini alırıq. Bu matris deyilir oyun matrisi və ya ödəniş matrisi.

Eyni son antaqonist oyunu bir-birindən yalnız sətir və sütunların sırasına görə fərqlənən müxtəlif matrislər ilə təsvir etmək olar.

Oyunu nəzərdən keçirin m x n matris ilə Р = (a ij), i = 1,2, ... , m;j = 1,2, ... , n və strategiyalar arasında ən yaxşısını müəyyənləşdirin A 1, A 2, ..., A m. Strategiya seçimi A i oyunçu AMMA oyunçunu gözləmək lazımdır IN ona strategiyalardan biri ilə cavab verəcək B j, bunun üçün oyunçu üçün ödəniş AMMA minimal (oyunçu IN oyunçuya "zərər verməyə" çalışır AMMA). ilə işarələyin a i, oyunçunun ən kiçik qazancı AMMA strategiya seçərkən A i bütün mümkün oyunçu strategiyaları üçün IN(ən kiçik ədəd i-ci ödəmə matrisinin xətti), yəni.

a i = aij , j = 1,...,n.

Bütün nömrələr arasında a i (i = 1,2, ... , m ) ən böyüyü seçin. zəng edək a aşağı oyun qiyməti və ya maksimum qazanc (maksimin). Bu oyunçu üçün zəmanətli qələbədir. AMMA oyunçunun istənilən strategiyası üçün IN. Nəticədə, , i = 1,... , m; j = 1,...,n

Maksiminə uyğun strategiya deyilir maksimum strategiya. Oyunçu IN oyunçunun qazancını azaltmaqda maraqlıdır AMMA; strategiyanın seçilməsi B j, üçün mümkün olan maksimum ödənişi nəzərə alır AMMA.

İşarə et: β i = aij , i = 1,... , m

Bütün nömrələr arasında B jən kiçiyini seçin və zəng edin β yüksək oyun qiyməti və ya minimum qazanc (minimax). Bu oyunçu üçün zəmanətli itkidir. IN.

Nəticədə, i = 1,... , m; j = 1,...,n.

Minimax strategiyası deyilir Minimax strategiyası.

Oyunçulara ən "ehtiyatlı" minimax və maksimal strategiyaların seçimini diktə edən prinsip adlanır. Minimax prinsipi. Bu prinsip hər bir oyunçunun rəqibin əks məqsədinə çatmağa çalışdığı ağlabatan fərziyyədən irəli gəlir.

Mühazirə 9 Oyun modellərinin konsepsiyası. Ödəniş matrisi.

§ 6 OYUN NƏZƏRİYYƏSİNİN ELEMENTLƏRİ

6.1 Oyun modellərinin konsepsiyası.

Münaqişə vəziyyətinin riyazi modeli deyilir oyun , münaqişədə iştirak edən tərəflər oyunçular və münaqişənin nəticəsi qalib .

Hər rəsmiləşdirilmiş oyun üçün təqdim edirik qaydalar , olanlar. aşağıdakıları müəyyən edən şərtlər sistemi: 1) oyunçuların hərəkətləri üçün seçimlər; 2) hər bir oyunçunun partnyorların davranışı haqqında məlumatının miqdarı; 3) hər bir hərəkət toplusunun gətirdiyi gəlir. Tipik olaraq, qazanc (və ya itki) kəmiyyətlə müəyyən edilə bilər; məsələn, itkini sıfır, qələbəni bir və heç-heçəni 1/2 ilə qiymətləndirə bilərsiniz. Oyunun nəticələrinin kəmiyyətcə qiymətləndirilməsi deyilir ödəniş .

Oyun adlanır buxar otağı , iştirak edən iki oyunçu varsa, və çoxsaylı , oyunçuların sayı ikidən çox olduqda. Biz yalnız qoşalaşmış oyunları nəzərdən keçirəcəyik. Onları iki oyunçu oynayır AMMA Və IN, maraqları bir-birinə ziddir və oyun dedikdə bir sıra hərəkətləri nəzərdə tuturuq AMMA Və IN.

Oyun adlanır sıfır məbləğli oyun və ya antaqonist skoy , oyunçulardan birinin qazancı digərinin itkisinə bərabərdirsə, yəni. hər iki tərəfin ödənişlərinin cəmi sıfırdır. Oyunun tapşırığını yerinə yetirmək üçün onlardan birinin dəyərini göstərmək kifayətdir . təyin etsək Amma- oyunçulardan birini qazanmaq, b – digərinin qazancı, sonra isə sıfır məbləğli oyun üçün b= –Amma, buna görə də, məsələn, nəzərə almaq kifayətdir Amma.

Qaydalarda nəzərdə tutulmuş hərəkətlərdən birinin seçilməsi və həyata keçirilməsi deyilir hərəkət oyunçu. Hərəkətlər ola bilər şəxsi Və təsadüfi . şəxsi hərəkət – mümkün hərəkətlərdən birinin (məsələn, şahmat oyununda gediş) oyunçunun şüurlu seçimidir. Hər bir şəxsi gediş üçün mümkün variantlar toplusu oyun qaydaları ilə tənzimlənir və hər iki tərəfin əvvəlki hərəkətlərinin cəmindən asılıdır.

Təsadüfi hərəkət – bu təsadüfi seçilmiş bir hərəkətdir (məsələn, qarışdırılmış göyərtədən kartı seçmək). Oyunun riyazi olaraq müəyyən edilməsi üçün oyunun qaydaları hər bir təsadüfi hərəkət üçün müəyyən edilməlidir ehtimal paylanması mümkün nəticələr.

Bəzi oyunlar yalnız təsadüfi hərəkətlərdən (saf şans oyunları adlanır) və ya yalnız şəxsi hərəkətlərdən (şahmat, dama) ibarət ola bilər. Kart oyunlarının əksəriyyəti qarışıq tipli oyunlara aiddir, yəni həm təsadüfi, həm də şəxsi hərəkətləri ehtiva edir. Bundan sonra biz yalnız oyunçuların şəxsi hərəkətlərini nəzərdən keçirəcəyik.

Oyunlar yalnız hərəkətlərin təbiətinə görə (şəxsi, təsadüfi) deyil, həm də başqasının hərəkətləri ilə bağlı hər bir oyunçu üçün mövcud olan məlumatların xarakteri və miqdarı ilə təsnif edilir. Oyunların xüsusi sinfi sözdə "oyunlar"dır tam məlumat». Tam məlumatı olan bir oyun Hər bir oyunçunun hər bir şəxsi hərəkətdə həm şəxsi, həm də təsadüfi bütün əvvəlki hərəkətlərin nəticələrini bildiyi bir oyun adlanır. Mükəmməl məlumatlı oyunlara misal olaraq şahmat, dama və məşhur oyun"X O oyunu". Praktiki əhəmiyyət kəsb edən oyunların əksəriyyəti tam məlumatı olan oyunlar sinfinə aid deyil, çünki rəqibin hərəkətləri haqqında naməlum adətən münaqişə vəziyyətlərinin vacib elementidir.

Oyun nəzəriyyəsinin əsas anlayışlarından biri də konsepsiyadır strategiyalar .

strategiya Bir oyunçu, vəziyyətdən asılı olaraq hər bir şəxsi hərəkət üçün hərəkətinin seçimini təyin edən qaydalar toplusu adlanır. Adətən oyun zamanı hər bir şəxsi hərəkətdə oyunçu konkret vəziyyətdən asılı olaraq seçim edir. Bununla belə, prinsipcə bütün qərarların oyunçu tərəfindən əvvəlcədən qəbul edilməsi mümkündür (hər hansı bir vəziyyətə cavab olaraq). Bu, oyunçunun qaydaların siyahısı və ya proqram şəklində verilə bilən müəyyən bir strategiya seçdiyini bildirir. (Beləliklə, kompüterdən istifadə edərək oyunu oynaya bilərsiniz). Oyun adlanır son , hər bir oyunçunun məhdud sayda strategiyası varsa və sonsuz .– əks halda.

Üçün həll etmək oyun , və ya tapın oyun qərarı , hər bir oyunçunun şərti qane edən strategiya seçməsi lazımdır optimallıq , olanlar. oyunçulardan biri qəbul etməlidir maksimum qələbə, ikinci onun strategiya çubuqlar zaman, Eyni zamanda, ikinci oyunçu olmalıdır minimum itki , birincisi öz strategiyasına əməl edərsə. Belə strategiyalar adlanır optimal . Optimal strategiyalar da şərti təmin etməlidir davamlılıq , olanlar. oyunçulardan hər hansı birinin bu oyunda öz strategiyasından əl çəkməsi zərərli olmalıdır.

Əgər oyun kifayət qədər təkrarlanırsa, o zaman oyunçular hər bir xüsusi oyunda qalib gəlmək və uduzmaqda maraqlı olmaya bilər, Ammaorta qələbə (məğlubiyyət) bütün partiyalarda.

Oyun nəzəriyyəsinin məqsədi hər bir oyunçu üçün optimal strategiyanı müəyyən etməkdir.

6.2. Ödəniş matrisi. Oyunun aşağı və yuxarı qiyməti

Oyunçunun oynadığı oyunu bitir AMMA Bu var T strategiyalar və oyunçu B - səh strategiyalara oyun deyilir.

Oyunu nəzərdən keçirin
iki oyunçu AMMA Və IN("biz" və "rəqib").

Qoy oyunçu AMMA var T qeyd etdiyimiz şəxsi strategiyalar
. Qoy oyunçu IN mövcuddur nşəxsi strategiyalar, biz onları işarə edirik
.

Qoy hər tərəf müəyyən strategiya seçsin; bizim üçün belə olacaq , düşmən üçün . Oyunçuların hər hansı bir cüt strategiya seçməsi nəticəsində Və (
) oyunun nəticəsi unikal şəkildə müəyyən edilir, yəni. qalib oyunçu AMMA(müsbət və ya mənfi) və itirmək
oyunçu IN.

Tutaq ki, dəyərlər hər hansı bir cüt strategiya ilə tanınır ( ,). Matris
,
, onun elementləri strategiyalara uyğun gəlirlərdir Və , çağırdı ödəniş matrisi və ya oyun matrisi. Bu matrisin sıraları oyunçunun strategiyalarına uyğundur AMMA, və sütunlar oyunçunun strategiyalarıdır B. Bu strategiyalar təmiz adlanır.

Oyun Matrix
oxşayır:

Oyunu nəzərdən keçirin
matris ilə

və strategiyalar arasında ən yaxşısını müəyyənləşdirin
. Strategiya seçimi , oyunçu AMMA oyunçunu gözləmək lazımdır IN ona strategiyalardan biri ilə cavab verəcək , bunun üçün oyunçu üçün ödəniş AMMA minimal (oyunçu IN oyunçuya "zərər verməyə" çalışır A).

ilə işarələyin oyunçunun ən aşağı gəliri AMMA strategiya seçərkən bütün mümkün oyunçu strategiyaları üçün IN(ən kiçik ədəd i-ödəniş matrisinin üçüncü sırası), yəni.

(1)

Bütün nömrələr arasında (
) ən böyüyü seçin:
.

zəng edək
aşağı qiymət gra, və ya maksimum qalibiyyət (maksimum). Bu, B oyunçusunun istənilən strategiyası üçün A oyunçusunun zəmanətli qazancıdır. Nəticədə,

. (2)

Maksiminə uyğun strategiya deyilir maksimum strategiya . Oyunçu IN oyunçunun qazancını azaltmaqda maraqlıdır AMMA, strategiyanın seçilməsi , üçün mümkün olan maksimum gəliri nəzərə alır AMMA.İşarə et

. (3)

Bütün nömrələr arasında ən kiçiyini seçin

və zəng edin yüksək oyun qiyməti və ya minimum qazanc (minimax). Eqo oyunçu B itkisinə zəmanət verdi . Buna görə də,

. (4)

Minimax strategiyası deyilir Minimax strategiyası.

Oyunçulara ən "ehtiyatlı" minimax və maksimal strategiyaların seçimini diktə edən prinsip adlanır. Minimax prinsipi . Bu prinsip hər bir oyunçunun rəqibin əks məqsədinə çatmağa çalışdığı ağlabatan fərziyyədən irəli gəlir.

teorem.Oyunun aşağı qiyməti heç vaxt oyunun yuxarı qiymətini keçmir.
.

Oyunun yuxarı və aşağı qiymətləri eyni olarsa, oyunun yuxarı və aşağı qiymətlərinin ümumi dəyəri
çağırdı oyunun xalis qiyməti, və ya oyunun qiyməti. Oyunun qiymətinə uyğun minimax strategiyaları bunlardır optimal strategiyalar , və onların məcmusudur optimal həll və ya oyun qərarı. Bu halda oyunçu AMMA maksimum zəmanət alır (oyunçu davranışından asılı olmayaraq) IN) qalib v, və oyunçu IN minimum zəmanətə nail olur (oyunçu davranışından asılı olmayaraq AMMA) itirmək v. Oyunun həlli olduğu deyilir davamlılıq , olanlar. oyunçulardan biri öz optimal strategiyasına sadiq qalırsa, o zaman digəri üçün optimal strategiyasından kənara çıxması sərfəli ola bilməz.

Əgər oyunçulardan biri (məsələn AMMA)öz optimal strategiyasına sadiq qalır və digər oyunçu (IN) o zaman istənilən yolla öz optimal strategiyasından kənara çıxacaq sapmayı edən oyunçu üçün bu heç vaxt faydalı ola bilməz; oyunçunun belə bir sapması INən yaxşı halda qazancı dəyişməz qoya bilər. və ən pis halda, onu artırın.

Əksinə, əgər IN onun optimal strategiyasına riayət edir və AMMAözündən kənara çıxarsa, bu heç bir şəkildə faydalı ola bilməz AMMA.

Bir neçə təmiz strategiya Və oyun üçün optimal həlli verir və yalnız uyğun element sütununda həm ən böyüyü, həm də cərgəsində ən kiçikdir. Belə bir vəziyyət, əgər varsa, deyilir yəhər nöqtəsi. Həndəsədə səthdə bir koordinat boyunca eyni vaxtda minimum və digəri boyunca maksimum xüsusiyyətə malik olan nöqtə deyilir. yəhər nöqtə, bənzətmə ilə bu termin oyun nəzəriyyəsində istifadə olunur.

Bunun üçün oyun
, çağırdı yəhər nöqtəsi oyunu. Element Bu xassəyə malik olan , matrisin yəhər nöqtəsidir.

Beləliklə, yəhər nöqtəsi olan hər oyun üçün hər iki tərəf üçün aşağıdakı xüsusiyyətlərdə fərqlənən bir cüt optimal strategiya müəyyən edən bir həll var.

1) Əgər hər iki tərəf optimal strategiyalarına sadiq qalırsa, orta qazanc oyunun xalis dəyərinə bərabərdir. v, bu onun həm aşağı, həm də yuxarı qiymətidir.

2) Əgər tərəflərdən biri öz optimal strategiyasına əməl edərsə, digəri isə özündən kənara çıxarsa, o zaman azmış tərəf bundan ancaq uduzur və heç bir halda qazancını artıra bilməz.

Yəhər nöqtəli oyunlar sinfi həm nəzəri, həm də praktiki baxımdan böyük maraq doğurur.

Oyun nəzəriyyəsində sübut edilmişdir ki, xüsusən də tam məlumatı olan hər bir oyunun bir yəhər nöqtəsi var və nəticədə, hər bir belə oyunun həlli var, yəni bir tərəf və digər tərəf üçün bir cüt optimal strategiya var. oyunun qiymətinə bərabər olan orta gəlir. Mükəmməl informasiyaya malik oyun yalnız şəxsi hərəkətlərdən ibarətdirsə, onda hər bir tərəf öz optimal strategiyasını tətbiq etdikdə, o, həmişə kifayət qədər müəyyən nəticə ilə, yəni oyunun qiymətinə tam bərabər olan gəlirlə başa çatmalıdır.