運(yùn)籌學(xué)課件第六章對(duì)策論基礎(chǔ)

1、 概論基本概念與名詞對(duì)策分類(lèi) 矩陣對(duì)策的基本理論矩陣對(duì)策的數(shù)學(xué)模型最優(yōu)純策略混合策略與混合擴(kuò)充 基本概念與名詞 對(duì)策分類(lèi)博弈現(xiàn)象下棋與打牌體育比賽戰(zhàn)爭(zhēng)市場(chǎng)進(jìn)入談判生產(chǎn)管理決策競(jìng)拍 博弈論是研究博弈現(xiàn)象的規(guī)律的數(shù)學(xué)理論和方法 博弈現(xiàn)象的要素局中人（參與人） 二人或多人行動(dòng)與策略有限或無(wú)限信息完全或不完全支付函數(shù)可正可負(fù) 局中人 策略與策略集 局勢(shì) 贏得函數(shù) 零和對(duì)策 矩陣對(duì)策：二人有限零和對(duì)策一）按對(duì)策雙方是否存在有約束力的協(xié)議來(lái)分：合作對(duì)策非合作對(duì)策二）按局中人數(shù)分類(lèi)：二人對(duì)策多人對(duì)策三）按策略數(shù)分類(lèi)：有限策略對(duì)策無(wú)限策略對(duì)策 二人非合作對(duì)策是我們討論的重點(diǎn)。 非合作博弈的進(jìn)一步分類(lèi)非合作博弈

2、零和博弈 純策略博弈 混合策略博弈 非零和博弈 完全信息博弈 w 靜態(tài)博弈 w 動(dòng)態(tài)博弈 不完全信息博弈 w 靜態(tài)博弈 w 動(dòng)態(tài)博弈 非零和的四種博弈也可以有純策略和混合策略博弈之分。 動(dòng)態(tài)時(shí)行動(dòng)和策略不同，要素有五個(gè)；而靜態(tài)時(shí)行動(dòng)與策略不加區(qū)別，要素有三個(gè)。 矩陣對(duì)策的數(shù)學(xué)模型矩陣對(duì)策的數(shù)學(xué)模型 最優(yōu)純策略最優(yōu)純策略 混合策略與混合擴(kuò)充混合策略與混合擴(kuò)充一、矩陣對(duì)策的數(shù)學(xué)模型一、矩陣對(duì)策的數(shù)學(xué)模型 以齊王賽馬為例說(shuō)明齊王賽馬二人非合作零和對(duì)策 局中人齊王和田忌 策略 上 中下三種等級(jí)的馬的組合 ，比三次，有六組策略：( 上，中，下) 、 ( 中，上，下) 、 ( 上，下，中) 、 ( 中，下

3、，上) 、 ( 下，上，中) 、 ( 下，中，上) . 對(duì)齊王，這六組策略用 表示， 對(duì)田忌，則用 表示。 支付函數(shù)贏了得一千金，輸了付一千金。6 , 5 , 4 , 3 , 2 , 1, ii6 , 5 , 4 , 3 , 2 , 1, ii齊王賽馬贏得函數(shù)31111-11311-111-13111-11131111-1131111-113 (上中下) (上下中)齊 (中上下)王 (中下上) (下中上) (下上中)田 忌654321654321 二人矩陣對(duì)策用下列式子表示 其中I、II表示兩個(gè)局中人，S1、S2分別表示局中人I、II的策略集，A則表示贏得矩陣：ASSGASSIIIG,2121

4、或)(ijaA 現(xiàn)有一矩陣對(duì)策 其中ASSG,216104801213936,4321321321243211ASS 若滿(mǎn)足 則上述條件規(guī)定的局勢(shì) 叫做最優(yōu)純局勢(shì)，也是矩陣對(duì)策的最優(yōu)解，是局中人I、II的最優(yōu)純策略。 定理：矩陣對(duì)策G=S1,S2,A有純策略解的充要條件是存在一個(gè)純局勢(shì) 使得maxminminmaxijijijjiaa),(*ji),(*jinjmiaaajijiij, 2 , 1;, 2 , 1,* 在上述定理中 因此符合條件 的即為最優(yōu)純策略。 上述例子的最優(yōu)純策略為：最優(yōu)局勢(shì) 且G=2為局中人I的贏得值。)(max),(min*ijijiijjijaaaa)(min)(m

5、ax*jijijiaa),(22 基本概念：當(dāng) 時(shí)不存在最優(yōu)純策略，此時(shí)需要應(yīng)用混合策略的方法確定參加對(duì)策的純策略。 例如maxminminmaxijijijjiaaASSG,212431,2121212211ASS 因?yàn)?所以 此時(shí)假設(shè)局中人I以概率x選取策略1，以概率(1-x)選取策略2；局中人II以概率y選取策略1，以概率(1-y)選取策略2。則對(duì)于局中人I來(lái)說(shuō)，贏得的期望值為E(x,y)，它等于3maxmin, 2minmaxijijijjiaamaxminminmaxijijijjiaa 贏得期望值 在x=1/2，y=1/4時(shí)，贏得函數(shù)取得最優(yōu)值5/2。這實(shí)際上是對(duì)策雙方都滿(mǎn)意的結(jié)果

6、。我們把純策略對(duì)應(yīng)的概率向量叫做混合策純策略對(duì)應(yīng)的概率向量叫做混合策略略，最優(yōu)解則是最優(yōu)混合策略。本例中，最優(yōu)混合策略是(1/2,1/2)和(1/4,3/4)。2/5)4/1)(2/1(42/52/124)1)(1 (2)1 (4)1 (3),(yxyxxyyxyxyxxyyxE 令純策略集對(duì)應(yīng)的概率向量是 它們滿(mǎn)足 混合策略的集合 將 叫做G的混合擴(kuò)充。),(),(2121nmyyyYxxxX11, 2 , 1;, 2 , 1, 0,11njjmiijiyxnjmiyx,*2*1YSXS,*2*1*ESSG 若令 并有 則稱(chēng)(X*,Y*)為最優(yōu)混合局勢(shì)，或叫做G在混合策略下的解，V叫做對(duì)策G

7、的值。X*、Y*分別是局中人I、II的最優(yōu)混合策略。),(min),(),(max),(*2*1*YXEYXEYXEYXESYSXVYXEYXESXSY),(max),(min*1*2 如果G的值是V，則局中人I和II的最優(yōu)策略是下列兩組不等式的解： 關(guān)于混合對(duì)策問(wèn)題的解，我們有如下定理：0, 1, 2 , 1,11imiimiiijxxnjVxa0, 1, 2 , 1,11jnjjnjjijyymiVya 如果(X*,Y*)是對(duì)策G的最優(yōu)混合局勢(shì)，則對(duì)于某個(gè)i或j來(lái)說(shuō)，有：0,)4(0,) 3(0)2(0) 1 (*1*1*1*1*jmiiijinjjijmiiijjnjjijiyVxaxV

8、yaVxayVyax則若則若，則若，則若 對(duì)于G=S1,S2,A38806678649593795205030435432154321A 劃去普遍較小的行，例如第1、2行，得 劃去普遍較大的列，例如第3、4、5三列，結(jié)果如上。46987580686493754354321A06364754321A 上述結(jié)果的第一行比第三行普遍更優(yōu)，因此再劃去第三行，得 若混合策略均不為零，由上述定理知混合對(duì)策問(wèn)題數(shù)學(xué)模型的不等式應(yīng)為等式。因此有64374321A 最優(yōu)混合策略滿(mǎn)足如下方程組 解得0,1634743434343xxxxVxxVxx0,1643721212121yyyyVyyVyy5, 2/1, 2/1; 3/2, 3/12143Vyyxx5)0 , 0 , 0 , 2/1 , 2/1 ()0 , 3/2 , 3/1 , 0 , 0(VYXTT記T(G)為矩陣對(duì)策G的解集定理1 設(shè)有兩個(gè)矩陣對(duì)策 G1=S1,S2,A1， G2=S1,S2,A2， 其中A1=(aij)， A2=(aij+L)， L為一任意常數(shù)，則 (G)T(G)T )2( ) 1 (2112LVVGG 定理2 設(shè)有兩個(gè)矩陣