Konsep model permainan. Matriks pembayaran

KERJA AMALI №3

Model teori permainan

Konsep model permainan

Teori permainan memperkatakan pembangunan pelbagai jenis cadangan untuk membuat keputusan dalam keadaan situasi konflik. Membentuk situasi konflik secara matematik, mereka boleh diwakili sebagai permainan dua, tiga atau lebih pemain, yang setiap satunya mengejar matlamat untuk memaksimumkan hasil dengan mengorbankan pemain lain. Model matematik situasi konflik dipanggil permainan, pihak yang terlibat dalam konflik - pemain, dan hasil konflik ialah menang. Untuk setiap permainan rasmi, kami memperkenalkan peraturan, iaitu sistem keadaan yang mentakrifkan:

1. pilihan pemain;

2. jumlah maklumat setiap pemain mempunyai tentang tingkah laku rakan kongsi;

3. ganjaran yang membawa kepada setiap set tindakan.

Sebagai peraturan, kemenangan boleh ditentukan secara kuantitatif (contohnya, kalah - 0, menang - 1, seri - ½). Permainan itu dipanggil bilik wap, jika dua pemain mengambil bahagian di dalamnya, dan pelbagai jika bilangan pemain lebih daripada dua orang. Permainan itu dipanggil permainan jumlah sifar jika keuntungan salah seorang pemain adalah sama dengan kerugian yang lain. Pilihan dan pelaksanaan salah satu tindakan yang disediakan oleh peraturan dipanggil bergerak pemain. Pergerakan boleh menjadi peribadi dan rawak. langkah peribadi- pilihan sedar oleh pemain salah satu tindakan yang mungkin (langkah dalam permainan catur), bergerak rawak- tindakan yang dipilih secara rawak (memilih kad daripada dek yang dikocok).

Strategi pemain dipanggil set peraturan yang menentukan pilihan tindakannya untuk setiap langkah peribadi, bergantung pada keadaan. Permainan itu dipanggil muktamad jika pemain mempunyai bilangan strategi yang terhad, dan tidak berkesudahan- jika tidak.

Untuk menyelesaikan permainan, atau untuk mencari keputusan permainan, seseorang harus memilih untuk setiap pemain strategi yang memenuhi keadaan optimum, i.e. salah seorang pemain mesti menerima kemenangan maksimum apabila yang kedua berpegang pada strateginya. Pada masa yang sama, pemain kedua mesti mempunyai kerugian minimum jika yang pertama berpegang pada strateginya. Strategi sedemikian dipanggil optimum. matlamat teori permainan adalah untuk menentukan strategi yang optimum untuk setiap pemain. Apabila memilih strategi yang optimum, adalah wajar untuk menganggap bahawa kedua-dua pemain berkelakuan munasabah dari sudut pandangan minat mereka.

Matriks pembayaran. Harga yang lebih rendah dan atas permainan

Pertimbangkan permainan terhingga berpasangan. Biarkan pemain A mempunyai m strategi peribadi, yang kami nyatakan A 1 , A 2 ,…, A m . Biarkan pemain B tersedia n strategi peribadi, kami menandakannya B 1 , B 2 ,…,B n . Mereka mengatakan bahawa permainan itu mempunyai dimensi m ´ n. Hasil daripada pilihan pemain mana-mana pasangan strategi A i dan B j keputusan permainan ditentukan secara unik, i.e. menang aij pemain A(positif atau negatif) dan kerugian (- aij) pemain V. Matriks P=(a ij), yang unsur-unsurnya ialah imbuhan yang sepadan dengan strategi A i dan B j, dipanggil matriks pembayaran atau matriks permainan.

Contoh - permainan "Cari"

Pemain A boleh bersembunyi di tempat perlindungan 1 - mari kita nyatakan strategi ini sebagai A 1 atau di tempat perlindungan 2 - strategi A 2. Pemain V boleh mencari pemain pertama di tempat perlindungan 1 - strategi DALAM 1, atau di tempat perlindungan 2 - strategi DALAM 2. Jika pemain A berada dalam Bilik Kebal 1 dan ditemui oleh pemain V, iaitu beberapa strategi sedang dilaksanakan (A 1, B 1), kemudian pemain A membayar denda, i.e. a 11=–1. Begitu juga, kita dapat a 22=–1. Jelas sekali strateginya (A 1, B 2) dan (A 2, B 1) berikan pemain A menang 1, jadi a 12=a 21=1. Oleh itu, kita mendapat matriks bayaran

Pertimbangkan permainan m ´ n dengan matriks P=(a ij) dan tentukan yang terbaik antara strategi pemain A. Memilih strategi A i, pemain A harus mengharapkan pemain V akan menjawabnya dengan salah satu strategi Dalam j, yang mana ganjaran untuk pemain A minimum (pemain V berusaha untuk "memudaratkan" pemain A).

Nyatakan dengan a i bayaran terendah pemain A apabila memilih strategi A i untuk semua strategi pemain yang mungkin V(nombor terkecil dalam i-baris ke- matriks hasil), i.e. .

Antara semua nombor a i pilih yang terbesar: . Jom panggil a harga permainan yang lebih rendah , atau kemenangan maksimum (maksimin ). ini ganjaran terjamin pemain A untuk mana-mana strategi pemain B. Oleh itu, .

Strategi yang sepadan dengan maximin dipanggil strategi maksimum. Pemain V berminat untuk mengurangkan ganjaran pemain A; memilih strategi B j, ia mengambil kira bayaran maksimum yang mungkin untuk A. Nyatakan .

Di antara semua nombor, kami memilih yang terkecil dan memanggilnya b harga permainan teratas , atau bayaran minima (minimax ). ini terjamin kehilangan pemain B untuk mana-mana strategi pemain A. Oleh itu, .

Strategi minimax dipanggil strategi minimax. Prinsip yang menentukan kepada pemain pilihan strategi minimax dan maximin yang paling berhati-hati dipanggil prinsip minimax.

permainan statistik

Dalam banyak tugas yang membawa kepada permainan, ketidakpastian disebabkan oleh kekurangan maklumat tentang keadaan di mana tindakan itu dijalankan. Keadaan ini tidak bergantung pada tindakan sedar pemain lain, tetapi pada realiti objektif, yang biasanya dipanggil "alam". Permainan sedemikian dipanggil permainan dengan alam semula jadi (permainan statistik).

Tugasan

Selepas beberapa tahun beroperasi, peralatan industri berada dalam salah satu daripada keadaan berikut: Dalam 1 - peralatan boleh digunakan pada tahun berikutnya selepas penyelenggaraan pencegahan; B 2 - untuk operasi tanpa masalah peralatan pada masa hadapan, perlu menggantikan bahagian dan pemasangannya; Dalam 3 - peralatan memerlukan pembaikan atau penggantian besar.

Bergantung pada situasi semasa B 1, B 2, B 3, pengurusan perusahaan boleh membuat keputusan berikut: A 1 - membaiki peralatan oleh pakar kilang, yang memerlukan kos yang sesuai a 1 = 6, a 2 = 10, dan 3 = 15 unit kewangan ; A 2 - hubungi pasukan pembaikan khas, kos dalam kes ini akan menjadi b 1 \u003d 15, b 2 \u003d 9, b 3 \u003d 18 unit kewangan; A 3 - gantikan peralatan dengan yang baru, jual peralatan usang pada nilai bakinya. Jumlah kos keputusan acara ini akan sama dengan, masing-masing, dengan 1 =13, dengan 2 =24, dengan 3 =12 unit kewangan.

Senaman

1. Setelah memberikan situasi yang diterangkan skema permainan, kenal pasti pesertanya, nyatakan kemungkinan strategi murni pihak-pihak.

2. Susun matriks hasil, menerangkan maksud unsur a ij matriks (mengapa ia negatif?).

3. Ketahui keputusan mengenai pengendalian peralatan pada tahun akan datang adalah dinasihatkan untuk mengesyorkan kepada pengurusan perusahaan untuk meminimumkan kerugian di bawah andaian berikut: a) pengalaman yang diperoleh di perusahaan dalam mengendalikan peralatan yang serupa menunjukkan bahawa kebarangkalian keadaan peralatan yang ditunjukkan adalah masing-masing q 1 = 0.15; q 2 =0.55; q 3 \u003d 0.3 (gunakan ujian Bayes); b) pengalaman menunjukkan bahawa ketiga-tiga kemungkinan keadaan peralatan adalah berkemungkinan sama (gunakan kriteria Laplace); c) tiada yang pasti boleh dikatakan tentang kebarangkalian peralatan (gunakan kriteria Wald, Savage, Hurwitz). Nilai parameter g=0.8 dalam kriteria Hurwitz ditetapkan.

Penyelesaian

1) Situasi yang diterangkan adalah permainan statistik.

Perangkaan ialah pengurusan perusahaan, yang boleh membuat salah satu daripada keputusan berikut: membaiki peralatan sendiri (strategi A 1), memanggil pembaikan (strategi A 2); menggantikan peralatan dengan yang baru (strategi A 3).

Bahagian bermain kedua - alam semula jadi, kami akan mempertimbangkan gabungan faktor yang mempengaruhi keadaan peralatan: peralatan boleh digunakan selepas penyelenggaraan pencegahan (keadaan B 1); adalah perlu untuk menggantikan komponen individu dan bahagian peralatan (keadaan B 2): ia perlu baik pulih atau penggantian peralatan (negeri B 3).

2) Susun matriks hasil permainan:

Elemen matriks pembayaran a ij menunjukkan kos pengurusan perusahaan jika, dengan strategi A i yang dipilih, peralatan berada dalam keadaan B j . Unsur-unsur matriks hasil adalah negatif, kerana untuk mana-mana strategi yang dipilih, pengurusan perusahaan perlu menanggung kosnya.

a) pengalaman pengendalian yang terkumpul di perusahaan yang serupa dengan peralatan menunjukkan bahawa kebarangkalian keadaan peralatan adalah sama dengan q 1 =0.15; q 2 =0.55; q 3 \u003d 0.3.

Mari kita wakili matriks bayaran seperti berikut:

di mana , (i=1.3)

Mengikut kriteria Bayes, strategi tulen A i diambil sebagai optimum, di mana keuntungan purata ahli statistik dimaksimumkan, i.e. disediakan oleh =max .

Strategi optimum Bayesian ialah strategi A 1 .

b) pengalaman menunjukkan bahawa ketiga-tiga kemungkinan keadaan peralatan adalah sama berkemungkinan, i.e. = 1/3.

Purata kemenangan ialah:

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.

Menurut Laplace, strategi optimum ialah A 1 .

c) tiada yang pasti boleh dikatakan tentang kebarangkalian peralatan tersebut.

Menurut kriteria Wald, strategi tulen diambil sebagai optimum, yang menjamin hasil maksimum di bawah keadaan yang paling teruk, i.e.

.

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

Oleh itu, strategi A 1 adalah optimum.

Mari bina matriks risiko , di mana .

Strategi pemain ialah pelan mengikut mana dia membuat pilihan dalam sebarang situasi yang mungkin dan dengan sebarang maklumat fakta yang mungkin. Sememangnya, pemain membuat keputusan semasa permainan berlangsung. Walau bagaimanapun, secara teorinya boleh diandaikan bahawa semua keputusan ini dibuat oleh pemain terlebih dahulu. Kemudian keseluruhan keputusan ini membentuk strateginya. Bergantung kepada bilangan strategi yang mungkin, permainan dibahagikan kepada terhingga dan tidak terhingga. Tugas teori permainan adalah untuk membangunkan cadangan untuk pemain, iaitu, untuk menentukan strategi optimum untuk mereka. Strategi optimum ialah strategi yang, apabila permainan diulang berkali-kali, memberikan pemain yang diberi hasil purata maksimum yang mungkin.

Jenis permainan strategik yang paling mudah ialah permainan jumlah sifar dua orang (jumlah bayaran bagi pihak adalah sifar). Permainan ini terdiri daripada dua gerakan: pemain A memilih salah satu strateginya yang mungkin Ai (i = 1, 2, m), dan pemain B memilih strategi Bj (j = 1, 2, ., n), dan setiap pilihan dibuat dalam kejahilan sepenuhnya pilihan pemain lain.

Matlamat pemain A adalah untuk memaksimumkan fungsi φ (Ai, Bj), seterusnya, matlamat pemain B adalah untuk meminimumkan fungsi yang sama. Setiap pemain boleh memilih salah satu pembolehubah di mana nilai fungsi bergantung. Jika pemain A memilih beberapa strategi Ai, maka ini dengan sendirinya tidak boleh menjejaskan nilai fungsi φ (Ai, Bj).

Pengaruh Ai, pada magnitud nilai φ (Ai, Bj) adalah tidak pasti; kepastian berlaku hanya selepas pilihan, berdasarkan prinsip pengecilan φ (Ai, Bj), oleh pemain lain pembolehubah Bj. Dalam kes ini, Bj ditentukan oleh pemain lain. Biarkan φ (Ai, Bj)= aij. Mari kita buat matriks A:

Baris matriks sepadan dengan strategi Ai, lajur sepadan dengan strategi Bj. Matriks A dipanggil bayaran atau matriks permainan. Elemen aij matriks ialah ganjaran pemain A jika dia memilih strategi Ai, dan pemain B memilih strategi Bj.

Biarkan pemain A memilih beberapa strategi Ai ; maka dalam kes yang paling teruk (contohnya, jika pilihan menjadi pemain terkenal C) dia akan menerima ganjaran yang sama dengan min aij. Menjangkakan kemungkinan ini, pemain A mesti memilih strategi untuk memaksimumkan bayaran minimum a:

a = maks min aij

Nilai a - bayaran terjamin pemain A - dipanggil harga permainan yang lebih rendah. Strategi Ai0, yang memastikan penerimaan a, dipanggil maximin.

Pemain B, memilih strategi, meneruskan prinsip berikut: apabila memilih beberapa strategi Bj, kerugiannya tidak akan melebihi nilai maksimum unsur-unsur lajur ke-j matriks, i.e. kurang daripada atau sama dengan maks aij

Memandangkan set max aij untuk makna yang berbeza j, pemain B secara semula jadi akan memilih nilai j supaya kerugian maksimumnya β diminimumkan:

β = min miax aij

Nilai β dipanggil kos atas permainan, dan strategi Bj0 sepadan dengan bayaran β dipanggil strategi minimax.

Ganjaran sebenar pemain A dengan tindakan munasabah rakan kongsi dihadkan oleh harga yang lebih rendah dan atas permainan. Jika ungkapan ini adalah sama, i.e.

Teori permainan ialah satu disiplin matematik, subjeknya ialah kaedah membuat keputusan dalam situasi konflik.

Keadaan itu dipanggil konflik, jika kepentingan beberapa (biasanya dua) orang yang mengejar matlamat bertentangan bertembung di dalamnya. Setiap pihak boleh menjalankan beberapa aktiviti untuk mencapai matlamat mereka, dan kejayaan satu pihak bermakna kegagalan pihak yang lain.

Dalam ekonomi, situasi konflik adalah sangat biasa (hubungan antara pembekal dan pengguna, pembeli dan penjual, jurubank dan pelanggan). Situasi konflik terdapat di banyak kawasan lain.

Situasi konflik dijana oleh perbezaan kepentingan rakan kongsi dan keinginan setiap daripada mereka untuk membuat keputusan yang optimum yang merealisasikan matlamat yang ditetapkan pada tahap yang paling besar. Pada masa yang sama, setiap orang perlu mengira bukan sahaja dengan matlamat mereka sendiri, tetapi juga dengan matlamat pasangan, dan mengambil kira keputusan yang tidak diketahui yang akan dibuat oleh rakan kongsi.

Biasanya situasi konflik sukar untuk dianalisis secara langsung kerana banyak faktor masuk sekunder. Untuk membolehkan analisis matematik situasi konflik, ia mesti dipermudahkan, dengan mengambil kira faktor utama sahaja. Model formal yang dipermudahkan bagi situasi konflik dipanggil permainan, pihak yang terlibat dalam konflik - pemain, dan hasil konflik - menang. Biasanya, keuntungan (atau kerugian) boleh dikira; sebagai contoh, anda boleh menilai kerugian dengan sifar, menang dengan satu dan seri sebanyak 1/2.

Permainan ini adalah koleksi peraturan menggambarkan tingkah laku pemain. Setiap contoh bermain permainan dalam beberapa cara tertentu dari awal hingga akhir adalah pesta permainan. Pilihan dan pelaksanaan salah satu tindakan yang disediakan oleh peraturan dipanggil bergerak pemain. Pergerakan boleh menjadi peribadi dan rawak. langkah peribadi- ini adalah pilihan sedar oleh pemain tentang salah satu tindakan yang mungkin (contohnya, langkah dalam permainan catur). Pergerakan rawak- ini juga merupakan pilihan salah satu daripada banyak pilihan, tetapi di sini pilihan itu tidak dipilih oleh pemain, tetapi oleh beberapa mekanisme pemilihan rawak (melempar syiling, memilih kad dari dek yang dikocok).

strategi Pemain ialah satu set peraturan yang menentukan pilihan tindakannya untuk setiap pergerakan peribadi, bergantung pada situasi.

Jika permainan hanya terdiri daripada gerakan peribadi, maka keputusan permainan ditentukan jika setiap pemain telah memilih strateginya sendiri. Walau bagaimanapun, jika terdapat pergerakan rawak dalam permainan, maka permainan itu akan bersifat probabilistik dan pilihan strategi pemain belum lagi menentukan keputusan akhir permainan.

Untuk memutuskan permainan, atau mencari penyelesaian kepada permainan, adalah perlu bagi setiap pemain untuk memilih strategi yang memenuhi syarat optimum, mereka. salah seorang pemain mesti menerima kemenangan maksimum, apabila yang kedua berpegang pada strateginya. Pada masa yang sama, pemain kedua mesti mempunyai kerugian minimum jika yang pertama berpegang pada strateginya. Strategi sedemikian dipanggil optimum. Strategi optimum mesti memenuhi keadaan kestabilan, i.e. ia sepatutnya tidak menguntungkan bagi mana-mana pemain untuk meninggalkan strategi mereka dalam permainan ini.

Matlamat teori permainan adalah untuk menentukan strategi optimum untuk setiap pemain.

Pertimbangkan permainan terhingga berpasangan. Biarkan pemain A mempunyai m strategi peribadi, yang kami nyatakan A 1 , A2 , ..., A m . Biarkan pemain V tersedia n strategi peribadi, kami menandakannya B1 , B2 , ..., B m . Mereka mengatakan bahawa permainan itu mempunyai dimensi m × n . Hasil daripada pilihan pemain mana-mana pasangan strategi

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

keputusan permainan ditentukan secara unik, i.e. menang aij pemain A (positif atau negatif) dan kerugian ( - aij ) pemain V . Mari kita anggap bahawa nilai OU dikenali untuk mana-mana pasangan strategi (A i, B j ). Matriks , yang unsur-unsurnya ialah imbuhan yang sepadan dengan strategi Ai dan B j , dipanggil matriks pembayaran atau matriks permainan. Borang am matriks sedemikian dibentangkan dalam Jadual 3.1.

Jadual 3.1

Barisan jadual ini sepadan dengan strategi pemain A , dan lajur ialah strategi pemain V . Mari kita buat matriks bayaran untuk perlawanan seterusnya.

Pertimbangkan permainan m × n dengan matriks P = (a ij), i = 1, 2, ..., m; j = 1, 2, ..., n dan tentukan yang terbaik antara strategi A 1 , A2 , ..., A m . Memilih strategi Ai pemain A harus mengharapkan pemain V akan menjawabnya dengan salah satu strategi B j , yang mana ganjaran untuk pemain A minimum (pemain V berusaha untuk "memudaratkan" pemain A ). Nyatakan dengan a i , bayaran terkecil pemain A apabila memilih strategi Ai untuk semua strategi pemain yang mungkin V (nombor terkecil dalam i-baris ke- matriks hasil), i.e.

Strategi yang sepadan dengan maximin dipanggil strategi maksimum. Pemain V berminat untuk mengurangkan ganjaran pemain A ; memilih strategi B j , ia mengambil kira bayaran maksimum yang mungkin untuk A . Tandakan

Strategi yang sepadan dengan minimax dipanggil strategi minimax. Prinsip yang menentukan kepada pemain pilihan strategi minimax dan maximin yang paling "berhati-hati" dipanggil prinsip minimax. Prinsip ini mengikut andaian munasabah bahawa setiap pemain berusaha untuk mencapai matlamat lawan lawan. Marilah kita menentukan harga yang lebih rendah dan atas permainan dan strategi yang sepadan dalam masalah.

Jika harga atas dan bawah permainan adalah sama, maka maksud umum atas dan harga lebih rendah permainan α = β = v dipanggil harga bersih permainan , atau dengan kos permainan . Strategi minimax yang sepadan dengan harga permainan adalah strategi yang optimum, dan keseluruhannya ialah penyelesaian yang optimum , atau keputusan permainan. Dalam kes ini pemain A menerima jaminan maksimum (bebas daripada tingkah laku pemain) V ) menang v , dan pemain V mencapai jaminan minimum (tanpa mengira tingkah laku pemain A ) kerugian v . Penyelesaian kepada permainan dikatakan mempunyai kelestarian , iaitu jika salah seorang pemain berpegang pada strategi optimumnya, maka tidak akan menguntungkan bagi yang lain untuk menyimpang dari strategi optimumnya.

berpasangan strategi murni Ai dan B j memberikan penyelesaian yang optimum kepada permainan jika dan hanya jika elemen yang sepadan aij , ialah yang terbesar dalam lajurnya dan yang terkecil dalam barisnya. Keadaan sedemikian, jika wujud, dipanggil titik pelana (serupa dengan permukaan pelana, yang melengkung ke atas ke satu arah dan ke bawah di arah yang lain).

Konsep asas model pengurusan inventori.

Dalam kedua-dua perniagaan dan pembuatan, adalah menjadi amalan biasa untuk mengekalkan stok sumber atau bekalan bahan yang munasabah untuk memastikan kesinambungan. proses pengeluaran. Secara tradisinya, inventori telah dilihat sebagai kos yang tidak dapat dielakkan, dengan terlalu sedikit inventori yang membawa kepada penutupan pengeluaran yang mahal, dan terlalu banyak modal mematikan inventori. Tugas pengurusan inventori adalah untuk menentukan tahap inventori yang mengimbangi dua kes ekstrem yang disebutkan.

Pertimbangkan ciri utama model pengurusan inventori.

Permintaan. Permintaan untuk produk berstok boleh deterministik(dalam kes paling mudah - malar dalam masa) atau rawak. Rawak permintaan diterangkan sama ada oleh momen rawak permintaan, atau dengan jumlah rawak permintaan pada masa yang pasti atau rawak.

Pengisian semula gudang. Pengisian semula gudang boleh dilakukan sama ada secara berkala pada selang waktu tertentu, atau apabila stok habis, i.e. mengurangkan mereka ke tahap tertentu.

Jumlah pesanan. Dalam kes penambahan semula berkala dan kehabisan stok secara tidak sengaja, kuantiti pesanan mungkin bergantung pada keadaan yang diperhatikan pada masa pesanan. Pesanan biasanya diserahkan untuk jumlah yang sama apabila stok mencapai tahap tertentu - yang dipanggil mata pesanan.

Masa penghantaran. Dalam model pengurusan inventori yang ideal, diandaikan bahawa pengisian semula yang dipesan dihantar ke gudang serta-merta. Dalam model lain, kelewatan dalam penghantaran untuk selang masa tetap atau rawak dipertimbangkan.

Kos penghantaran. Sebagai peraturan, diandaikan bahawa kos setiap penghantaran terdiri daripada dua komponen - kos sekali sahaja yang tidak bergantung pada volum batch yang dipesan, dan kos yang bergantung (paling kerap secara linear) pada volum batch.

kos penyimpanan. Dalam kebanyakan model pengurusan inventori, jumlah storan dianggap hampir tidak terhad, dan jumlah inventori yang disimpan digunakan sebagai pembolehubah kawalan. Pada masa yang sama, diandaikan bahawa bayaran tertentu dikenakan untuk penyimpanan setiap unit stok seunit masa.

Penalti defisit. Mana-mana gudang diwujudkan untuk mengelakkan kekurangan jenis tertentu produk dalam sistem perkhidmatan. Kekurangan stok pada masa yang tepat membawa kepada kerugian yang berkaitan dengan masa henti peralatan, pengeluaran tidak teratur, dsb. Kerugian ini dipanggil penalti defisit.

nomenklatur saham. Dalam kes yang paling mudah, diandaikan bahawa stok jenis produk yang sama atau produk homogen disimpan di dalam gudang. Dalam lebih kes yang sukar dipertimbangkan stok berbilang item.

Struktur sistem gudang. Paling berkembang sepenuhnya model matematik manis bersendirian. Walau bagaimanapun, dalam praktiknya terdapat juga struktur yang lebih kompleks: sistem hierarki gudang dengan tempoh penambahan yang berbeza dan masa penghantaran pesanan, dengan kemungkinan pertukaran saham antara gudang pada tahap hierarki yang sama, dsb.

Kriteria untuk keberkesanan strategi pengurusan inventori yang diterima pakai ialah fungsi kos (kos), mewakili jumlah kos membekalkan produk yang disimpan, penyimpanannya dan kos denda.

Pengurusan inventori terdiri daripada mencari strategi sedemikian untuk penambahan dan penggunaan inventori, di mana fungsi kos mengambil nilai minimum.

Biarkan fungsi , dan nyatakan masing-masing:

Menyimpan semula,

penggunaan stok,

Permintaan untuk produk berstok

untuk satu tempoh masa.

Model pengurusan inventori biasanya menggunakan derivatif masa bagi fungsi ini, , , dipanggil, masing-masing,

Permainan itu dipanggil permainan jumlah sifar, atau antagonis, jika keuntungan salah seorang pemain adalah sama dengan kehilangan yang lain, i.e. untuk menyelesaikan tugas permainan, sudah cukup untuk menunjukkan nilai salah satu daripadanya. Jika kita tentukan a- menang salah seorang pemain, b ialah bayaran bagi yang lain, kemudian untuk permainan jumlah sifar b = - a, jadi sudah memadai untuk mempertimbangkan, sebagai contoh, a.

Pilihan dan pelaksanaan salah satu tindakan yang disediakan oleh peraturan dipanggil bergerak pemain. Pergerakan boleh menjadi peribadi dan rawak.

langkah peribadi- ini adalah pilihan sedar oleh pemain tentang salah satu tindakan yang mungkin (contohnya, langkah dalam permainan catur).

Pergerakan rawak ialah tindakan yang dipilih secara rawak (contohnya, memilih kad daripada dek yang dikocok). Dalam kerja saya, saya hanya akan mempertimbangkan langkah peribadi pemain.

strategi Seorang pemain dipanggil satu set peraturan yang menentukan pilihan tindakannya untuk setiap gerakan peribadi, bergantung pada situasi. Biasanya semasa permainan, pada setiap pergerakan peribadi, pemain membuat pilihan bergantung pada situasi tertentu. Walau bagaimanapun, pada dasarnya, adalah mungkin bahawa semua keputusan dibuat oleh pemain terlebih dahulu (sebagai tindak balas kepada sebarang situasi tertentu). Ini bermakna pemain telah memilih strategi tertentu, yang boleh diberikan dalam bentuk senarai peraturan atau program. (Jadi anda boleh bermain permainan menggunakan komputer). Permainan itu dipanggil muktamad jika setiap pemain mempunyai bilangan strategi yang terhad, dan tidak berkesudahan- jika tidak.

Untuk menyelesaikan permainan atau mencari penyelesaian kepada permainan, adalah perlu bagi setiap pemain untuk memilih strategi yang memenuhi syarat. optimum, iaitu salah seorang pemain mesti menerima kemenangan maksimum apabila yang kedua berpegang pada strateginya. Pada masa yang sama, pemain kedua mesti mempunyai kerugian minimum jika yang pertama berpegang pada strateginya. begitu strategi dipanggil optimum. Strategi optimum juga mesti memuaskan keadaan kestabilan, iaitu ia sepatutnya tidak menguntungkan bagi mana-mana pemain untuk meninggalkan strategi mereka dalam permainan ini.

Tujuan Teori Permainan: menentukan strategi optimum untuk setiap pemain. Apabila memilih strategi yang optimum, adalah wajar untuk menganggap bahawa kedua-dua pemain berkelakuan munasabah dari sudut pandangan minat mereka.

Permainan antagonis di mana setiap pemain mempunyai set strategi terhingga dipanggil permainan matriks. Nama ini dijelaskan oleh kemungkinan berikut untuk menerangkan permainan jenis ini. Kami membuat jadual segi empat tepat di mana baris sepadan dengan strategi pemain pertama, lajur sepadan dengan strategi kedua, dan sel jadual di persimpangan baris dan lajur sepadan dengan situasi permainan. Jika kita meletakkan bayaran pemain pertama dalam situasi yang sepadan dalam setiap sel, maka kita mendapat penerangan tentang permainan dalam bentuk matriks tertentu. Matriks ini dipanggil matriks permainan atau matriks imbuhan.

Permainan antagonis akhir yang sama boleh diterangkan oleh matriks yang berbeza, berbeza antara satu sama lain hanya dalam susunan baris dan lajur.

Pertimbangkan permainan m x n dengan matriks Р = (a ij), i = 1,2, ... , m;j = 1,2, ... , n dan tentukan yang terbaik antara strategi A 1, A 2, ..., A m. Memilih strategi A i pemain A harus mengharapkan pemain V akan menjawabnya dengan salah satu strategi B j, yang mana ganjaran untuk pemain A minimum (pemain V berusaha untuk "memudaratkan" pemain A). Nyatakan dengan a i, bayaran terkecil pemain A apabila memilih strategi A i untuk semua strategi pemain yang mungkin V(nombor terkecil dalam i-th garisan matriks bayaran), i.e.

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

Antara semua nombor a i (i = 1,2, ... , m ) pilih yang terbesar. Jom telefon a harga permainan yang lebih rendah atau bayaran maksimum (maksimum). Ini adalah kemenangan yang dijamin untuk pemain. A untuk sebarang strategi pemain V. Oleh itu, , i = 1,... , m; j = 1,...,n

Strategi yang sepadan dengan maximin dipanggil strategi maksimum. Pemain V berminat untuk mengurangkan ganjaran pemain A; memilih strategi B j, ia mengambil kira bayaran maksimum yang mungkin untuk A.

Nyatakan: β i = aij , i = 1,... , m

Antara semua nombor B j pilih yang terkecil dan panggil β harga permainan teratas atau bayaran minimax (minimax). Ini adalah kerugian yang dijamin untuk pemain. V.

Oleh itu, i = 1,... , m; j = 1,...,n.

Strategi minimax dipanggil strategi minimax.

Prinsip yang menentukan kepada pemain pilihan strategi minimax dan maximin yang paling "berhati-hati" dipanggil prinsip minimax. Prinsip ini mengikut andaian munasabah bahawa setiap pemain berusaha untuk mencapai matlamat lawan lawan.

Kuliah 9 Konsep model permainan. Matriks pembayaran.

§ 6 UNSUR TEORI PERMAINAN

6.1 Konsep model permainan.

Model matematik situasi konflik dipanggil permainan , pihak yang terlibat dalam konflik tersebut pemain dan akibat konflik menang .

Untuk setiap permainan rasmi, kami memperkenalkan peraturan , mereka. sistem syarat yang menentukan: 1) pilihan untuk tindakan pemain; 2) jumlah maklumat setiap pemain mempunyai tentang tingkah laku rakan kongsi; 3) ganjaran yang membawa kepada setiap set tindakan. Biasanya, keuntungan (atau kerugian) boleh dikira; sebagai contoh, anda boleh menilai kerugian dengan sifar, menang dengan satu dan seri sebanyak 1/2. Mengira keputusan permainan dipanggil bayaran .

Permainan itu dipanggil bilik wap , jika terdapat dua pemain yang terlibat, dan pelbagai , jika bilangan pemain lebih daripada dua orang. Kami akan mempertimbangkan hanya permainan berpasangan. Mereka dimainkan oleh dua pemain A dan V, yang kepentingannya bertentangan, dan dengan permainan yang kami maksudkan adalah siri tindakan di pihak A dan V.

Permainan itu dipanggil permainan jumlah sifar atau antagonis skoy , jika keuntungan salah seorang pemain adalah sama dengan kerugian yang lain, i.e. jumlah bayaran kedua-dua pihak adalah sifar. Untuk menyelesaikan tugas permainan, sudah cukup untuk menunjukkan nilai salah satu daripadanya . Jika kita tentukan a- menang salah seorang pemain, b – bayaran yang lain, kemudian untuk permainan jumlah sifar b= –a, jadi ia memadai untuk dipertimbangkan, sebagai contoh a.

Pilihan dan pelaksanaan salah satu tindakan yang disediakan oleh peraturan dipanggil bergerak pemain. Bergerak boleh peribadi dan rawak . langkah peribadi – ia adalah pilihan sedar oleh pemain tentang salah satu tindakan yang mungkin (contohnya, langkah dalam permainan catur). Set pilihan yang mungkin untuk setiap langkah peribadi dikawal oleh peraturan permainan dan bergantung pada keseluruhan gerakan sebelumnya di kedua-dua belah pihak.

Pergerakan rawak – ia adalah tindakan yang dipilih secara rawak (contohnya, memilih kad daripada dek yang dikocok). Untuk permainan ditakrifkan secara matematik, peraturan permainan mesti ditentukan untuk setiap pergerakan rawak taburan kebarangkalian kemungkinan hasil.

Sesetengah permainan mungkin hanya terdiri daripada pergerakan rawak (yang dipanggil permainan peluang murni) atau hanya gerakan peribadi (catur, dam). Kebanyakan permainan kad tergolong dalam permainan jenis campuran, iaitu, ia mengandungi kedua-dua pergerakan rawak dan peribadi. Dalam perkara berikut, kami akan mempertimbangkan hanya langkah peribadi pemain.

Permainan diklasifikasikan bukan sahaja oleh sifat pergerakan (peribadi, rawak), tetapi juga oleh sifat dan jumlah maklumat yang tersedia untuk setiap pemain mengenai tindakan yang lain. Kelas permainan khas ialah apa yang dipanggil "permainan dengan maklumat lengkap». Permainan dengan maklumat lengkap Permainan dipanggil di mana setiap pemain mengetahui keputusan semua gerakan sebelumnya, baik peribadi dan rawak, pada setiap gerakan peribadi. Contoh permainan dengan maklumat yang sempurna ialah catur, dam dan permainan terkenal"tic-tac-toe". Kebanyakan permainan yang mempunyai kepentingan praktikal tidak tergolong dalam kelas permainan dengan maklumat lengkap, kerana perkara yang tidak diketahui tentang tindakan pihak lawan biasanya merupakan elemen penting dalam situasi konflik.

Salah satu konsep asas teori permainan ialah konsep strategi .

strategi Seorang pemain dipanggil satu set peraturan yang menentukan pilihan tindakannya untuk setiap gerakan peribadi, bergantung pada situasi. Biasanya semasa permainan, pada setiap pergerakan peribadi, pemain membuat pilihan bergantung pada situasi tertentu. Walau bagaimanapun, pada dasarnya adalah mungkin bahawa semua keputusan dibuat oleh pemain terlebih dahulu (sebagai tindak balas kepada sebarang situasi tertentu). Ini bermakna pemain telah memilih strategi tertentu, yang boleh diberikan dalam bentuk senarai peraturan atau program. (Jadi anda boleh bermain permainan menggunakan komputer). Permainan itu dipanggil muktamad , jika setiap pemain mempunyai bilangan strategi yang terhad, dan tidak berkesudahan .– sebaliknya.

Untuk memutuskan permainan , atau cari keputusan permainan , adalah perlu bagi setiap pemain untuk memilih strategi yang memenuhi syarat optimum , mereka. salah seorang pemain mesti menerima kemenangan maksimum, apabila kedua berpegang kepada strateginya, Pada masa yang sama, pemain kedua mesti mempunyai kerugian minimum , jika yang pertama mematuhi strateginya. Strategi sedemikian dipanggil optimum . Strategi optimum juga mesti memenuhi syarat kelestarian , mereka. ia sepatutnya tidak menguntungkan bagi mana-mana pemain untuk meninggalkan strategi mereka dalam permainan ini.

Jika permainan diulang cukup kali, maka pemain mungkin tidak berminat untuk menang dan kalah dalam setiap permainan tertentu, apurata menang (kalah) dalam semua pihak.

Matlamat teori permainan adalah untuk menentukan strategi optimum untuk setiap pemain.

6.2. Matriks pembayaran. Harga yang lebih rendah dan atas permainan

Tamat permainan di mana pemain A Ia mempunyai T strategi, dan pemain B - hlm strategi dipanggil permainan.

Pertimbangkan permainan
dua pemain A dan V("kami" dan "lawan").

Biarkan pemain A mempunyai T strategi peribadi, yang kami nyatakan
. Biarkan pemain V tersedia n strategi peribadi, kami menandakannya
.

Biarkan setiap pihak memilih strategi tertentu; bagi kita ia akan menjadi , untuk musuh . Hasil daripada pilihan pemain mana-mana pasangan strategi dan (
) keputusan permainan ditentukan secara unik, i.e. menang pemain A(positif atau negatif) dan kalah
pemain V.

Mari kita anggap bahawa nilai dikenali dengan mana-mana pasangan strategi ( ,). Matriks
,
, yang unsur-unsurnya adalah ganjaran yang sepadan dengan strategi dan , dipanggil matriks pembayaran atau matriks permainan. Barisan matriks ini sepadan dengan strategi pemain A, dan lajur adalah strategi pemain B. Strategi ini dipanggil tulen.

Matriks Permainan
kelihatan seperti:

Pertimbangkan permainan
dengan matriks

dan tentukan yang terbaik antara strategi
. Memilih strategi , pemain A harus mengharapkan pemain V akan menjawabnya dengan salah satu strategi , yang mana ganjaran untuk pemain A minimum (pemain V berusaha untuk "memudaratkan" pemain A).

Nyatakan dengan bayaran terendah pemain A apabila memilih strategi untuk semua strategi pemain yang mungkin V(nombor terkecil dalam i-baris ke- matriks hasil), i.e.

(1)

Antara semua nombor (
) pilih yang terbesar:
.

Jom telefon
harga rendah ngra, atau kemenangan maksimum (maksimum). Ini adalah ganjaran terjamin pemain A untuk mana-mana strategi pemain B. Oleh itu,

. (2)

Strategi yang sepadan dengan maximin dipanggil strategi maksimum . Pemain V berminat untuk mengurangkan ganjaran pemain A, memilih strategi , ia mengambil kira bayaran maksimum yang mungkin untuk A. Tandakan

. (3)

Antara semua nombor pilih yang terkecil

dan panggil harga permainan teratas atau bayaran minima (minimaks). Ego menjamin kehilangan pemain B . Oleh itu,

. (4)

Strategi minimax dipanggil strategi minimax.

Prinsip yang menentukan kepada pemain pilihan strategi minimax dan maximin yang paling "berhati-hati" dipanggil prinsip minimax . Prinsip ini mengikut andaian munasabah bahawa setiap pemain berusaha untuk mencapai matlamat lawan lawan.

Teorem.Harga permainan yang lebih rendah tidak pernah melebihi harga atas permainan.
.

Jika harga atas dan bawah permainan adalah sama, maka jumlah nilai harga atas dan bawah permainan
dipanggil harga bersih permainan, atau harga permainan. Strategi minimax yang sepadan dengan harga permainan adalah strategi yang optimum , dan keseluruhannya penyelesaian yang optimum atau keputusan permainan. Dalam kes ini pemain A menerima jaminan maksimum (bebas daripada tingkah laku pemain) V) menang v, dan pemain V mencapai jaminan minimum (tanpa mengira tingkah laku pemain A) kalah v. Penyelesaian kepada permainan dikatakan mempunyai kelestarian , mereka. jika salah seorang pemain berpegang pada strategi optimumnya, maka tidak akan menguntungkan bagi yang lain untuk menyimpang dari strategi optimumnya.

Jika salah seorang pemain (contohnya A) berpegang pada strategi optimumnya, dan pemain lain (V) akan menyimpang daripada strategi optimumnya dalam apa jua cara, maka bagi pemain yang membuat sisihan, ini tidak boleh memberi manfaat; seperti penyelewengan pemain V mungkin paling baik membiarkan keuntungan tidak berubah. dan dalam kes yang paling teruk, tingkatkannya.

Sebaliknya, jika V mematuhi strategi optimumnya, dan A menyimpang daripada sendiri, maka ini sama sekali tidak boleh memberi manfaat kepada A.

Beberapa strategi tulen dan memberikan penyelesaian yang optimum kepada permainan jika dan hanya jika elemen yang sepadan ialah yang terbesar dalam lajurnya dan yang terkecil dalam barisnya. Keadaan sedemikian, jika wujud, dipanggil titik pelana. Dalam geometri, titik pada permukaan yang mempunyai sifat: minimum serentak di sepanjang satu koordinat dan maksimum di sepanjang yang lain, dipanggil pelana dot, dengan analogi istilah ini digunakan dalam teori permainan.

Permainan yang
, dipanggil permainan mata pelana. unsur , yang mempunyai sifat ini, ialah titik pelana matriks.

Jadi, untuk setiap permainan dengan mata pelana, terdapat penyelesaian yang menentukan sepasang strategi optimum untuk kedua-dua belah pihak, yang berbeza dalam sifat berikut.

1) Jika kedua-dua pihak berpegang pada strategi optimum mereka, maka pulangan purata adalah sama dengan kos bersih permainan v, iaitu harga yang lebih rendah dan harga atasnya.

2) Jika salah satu pihak berpegang kepada strategi optimumnya, manakala yang lain menyimpang dari sendiri, maka pihak yang menyeleweng hanya boleh rugi daripada ini dan tidak boleh meningkatkan keuntungannya.

Kelas permainan dengan titik pelana sangat diminati dari sudut teori dan praktikal.

Dalam teori permainan, terbukti bahawa, khususnya, setiap permainan dengan maklumat lengkap mempunyai titik pelana, dan, akibatnya, setiap permainan sedemikian mempunyai penyelesaian, iaitu, terdapat sepasang strategi optimum untuk satu pihak dan yang lain, memberikan bayaran purata sama dengan harga permainan. Jika permainan dengan maklumat yang sempurna hanya terdiri daripada pergerakan peribadi, maka, apabila setiap pihak menggunakan strategi optimumnya sendiri, ia mesti sentiasa berakhir dengan hasil yang agak pasti, iaitu, hasil yang sama persis dengan harga permainan.