運(yùn)籌學(xué)2-對策論

1、運(yùn) 籌 學(xué) 制作：1 第四章 對策論1、對策論的基本概念2、矩陣對策的最優(yōu)純策略3、矩陣對策的混合策略 引：“齊王賽馬”21. 對策論的基本概念三個基本要素；(1). 局中人：參與對抗的各方；(2). 策略集：局中人選擇對付其它局中人的行動方案稱為策略。某局中人的所有可能策略全體稱為策略集；(3). 局勢對策的益損值：各局中人各自使用一個對策就形成一個局勢，一個局勢決定了個局眾人 的對策結(jié)果，稱為該局勢對策的益損值。3“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）4齊王的策略集: S1=1, 2, 3, 4, 5, 6田忌的策略集： S2=1, 2, 3, 4, 5, 6下列矩陣稱齊王的贏

2、得矩陣： 3 1 1 1 -1 1 1 3 1 1 1 -1A= 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 -1 1 1 3 51. 基本概念（續(xù)）二人有限零和對策：(又稱矩陣策略)局中人為2；每局中人的策略集中策略數(shù)目有限；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。61. 基本概念（續(xù)）記矩陣對策為: G = S1, S2, A 甲的策略集 甲的贏得矩陣 乙的策略集“齊王賽馬”即是一個矩陣策略.72.矩陣對策的最優(yōu)純策略 在甲方贏得矩陣 A=aijm*n 中： i行代表甲方策略 i =1,2m j列代表乙方策略 j

3、 =1,2n aij代表甲方取策略i,乙方取策略j,這一局勢下甲方的益損值，此時乙方的益損值為-aij（零和性質(zhì)）。 在討論各方采用的策略是必須注意一個前提就是對方是理智的。這就是要從最有把握取得的益損值情況考慮。 82. 矩陣對策的最優(yōu)純策略(續(xù))例：有交易雙方公司甲和乙，甲有三個策略1，2，3；乙有四個策略1，2，3，4，根據(jù)獲利情況建立甲方的益損值 贏得矩陣。 -3 0 -2 0 A = 2 3 0 1 -2 -4 -1 3問：甲公司應(yīng)采取什么策略比較適合？9甲：采取1至少得3(損失 3） 2 0 3 -4(損失 4）乙：采取1甲最多得2（乙得-2） 2 3（乙得-3） 3 0（乙得 0

4、） 4 3（乙得-3）取大則取2 max min aij= 0 i j取小則取3 min max aij= 0 j i10甲采取策略2 不管乙采取如何策略，都至少得益。乙采取策略3 不管甲采取如何策略， 都至少可以得益。（最多損失0） 分別稱甲，乙公司的最優(yōu)策略，由唯一性又稱最優(yōu)純策略。存在前提： max min aij = min max aij = v i j j i又稱（ 2 ，3 ）為對策G=s1,s2,A的鞍點(diǎn)。值V為G的值。11作業(yè) P373 - 1123.矩陣對策的混合策略設(shè)矩陣對策 G =S1,S2,A當(dāng) max min aij min max aij i j j i 時，不存

5、在最優(yōu)純策略 求解混合策略。133.矩陣對策的混合策略例：設(shè)一個贏得矩陣如下: min 5 9 5 A = max 6 策略2 8 6 6 i max 8 9 min 8 策略1 j14矛盾：甲取2 ，乙取時1，甲實(shí)際贏得8比預(yù)期多2（乙就少2）這對乙講是不滿意的，考慮這一點(diǎn)，乙采取策略2，若甲分析到這一點(diǎn)，取策略1，則贏得更多為9此時，甲，乙芳沒有一個雙方均可接受的平衡局勢。一個思路：對甲（乙）給出一個選取不同策略的概率分布，以使甲（乙）在各種情況下的平均贏得（損失）最多（最少）。-即混合策略15求解方法：線性規(guī)劃法（其他方法：圖解法，迭代法，線性方程法等略）例： 5 9 設(shè)在最壞的情況下，

6、 A= 甲贏得的平均值為V. 8 6 （未知）STEP 11) 設(shè)甲使用策略1的概率為x1 x1+x2=1 設(shè)甲使用策略2的概率為x2 x1,x20162)無論乙取何策略，甲的平均贏得應(yīng)不少于V:對乙取1：5x1+ 8x2V對乙取2：9x1+ 6x2V 注意 V0,因?yàn)锳各元素為正。STEP 2 作變換： x1= x1/V ; x2= x2/V得到上述關(guān)系式變?yōu)椋?x1+ x2=1/V (V愈大愈好）待定 5x1+ 8x21 9x1+ 6x21 x1, x2017建立線性模型： min x1+x2 s.t. 5x1+8x21 x1= 1/21 9x1+6x21 x2= 2/21 x1, x20

7、 1/V= x1+x2=1/7 所以：V=7. 返回原問題： x1= x1V= 1/3; x2= x2V= 2/3 于是甲的最優(yōu)混合策略為： 以1/3的概率選1；以2/3的概率選2 最優(yōu)值V=7.18同樣可求乙的最優(yōu)混合策略：設(shè)乙使用策略1的概率為y1 y1+y2=1設(shè)乙使用策略2的概率為y2 y1, y20設(shè)在最壞的情況下，甲贏得的平均值為V.這也是乙損失的平均值，越小越好作變換： y1= y1/V; y2= y2/V. 建立線性模型： max y1+y2 y1= 1/14 s.t. 5y1+9y21 y2= 1/14 8y1+6y21 1/V= y1+y2=1/7 y1, y20 所以：V

8、=7 19返回原問題： y1= y1V= 1/2 y2= y2V= 1/2于是乙的最優(yōu)混合策略為：以1/2的概率選1；以1/2的概率選2. 最優(yōu)值V=7.當(dāng)贏得矩陣中有非正元素時，V0的條件不一定成立，可以作下列變換： 選一正數(shù)k，令矩陣中每一元素加上k得到新的正矩陣A，其對應(yīng)的矩陣對策 G= S1,S2,A與 G = S1,S2,A 解相同，但VG = VG - k20再討論“齊王賽馬”“齊王賽馬”的贏得矩陣A有 max min aij1 min max aij3 i j j i 故需求混合策略，由于A中有非正元素，可選k2，令矩陣中每一元素加上k得到新的正矩陣A： 5 3 3 3 1 3

9、3 5 3 3 3 1 A = 3 1 5 3 3 3 1 3 3 5 3 3 3 3 3 1 5 3 3 3 1 3 3 521再討論“齊王賽馬”(續(xù))求甲方(齊王)最優(yōu)策略的線性規(guī)劃模型： min x1+x2 +x3 +x4 +x5 +x6 s.t. 5x1+3x2 +3x3 + x4 +3x5 +3x6 1 3x1+5x2 + x3 +3x4 +3x5 +3x6 1 3x1+3x2 +5x3 +3x4 +3x5 + x6 1 3x1+3x2 +3x3 +5x4 + x5 +3x6 1 x1+3x2 +3x3 +3x4 +5x5 +3x6 1 3x1+ x2 +3x3 +3x4 +3x5

10、+5x6 1 x1，x2，x3，x4，x5，x6 0 可得兩組解：(0,1/9,1/9,0,0,1/9)T, (1/18,1/18,1/18,1/18,1/18,1/18)T ,V=3于是，x(0,1/3,1/3,0,0,1/3)T, x(1/6,1/6,1/6,1/6,1/6,1/6)T V = V-2 = 1即齊王的最優(yōu)混合策略值是贏1千金22再討論“齊王賽馬”(續(xù))求乙方(田忌)最優(yōu)策略的線性規(guī)劃模型： max y1+y2 +y3 +y4 +y5 +y6 s.t. 5y1+3y2 +3y3 +3y4 + y5 +3y6 1 3y1+5y2 +3y3 +3y4 +3y5 + y6 1 3y

11、1+ y2 +5y3 +3y4 +3y5 +3y6 1 y1+3y2 +3y3 +5y4 +3y5 +3y6 1 3y1+3y2 +3y3 + y4 +5y5 +3y6 1 3y1+3y2 + y3 +3y4 +3y5 +5y6 1 y1，y2，y3，y4，y5，y6 0 可得兩組解：(1/9,0,0,1/9,1/9,0)T, (1/18,1/18,1/18,1/18,1/18,1/18)T ,V=3于是，y(1/3,0,0,1/3,1/3,0)T, y(1/6,1/6,1/6,1/6,1/6,1/6)T V = V-2 = 1即田忌的最優(yōu)混合策略值是輸1千金23優(yōu)超原則： 假設(shè)矩陣對策 G

12、= S1,S2,A 甲方贏得矩陣 A=aijmn- 若存在兩行，s 行的各元素均優(yōu)于 t 行的元素，即 asj atj j =1,2n 稱甲方策略s優(yōu)超于t - 若存在兩列，s 列的各元素均優(yōu)于 t 列的元素，即 ais ait i =1,2,m 稱乙方策略 s優(yōu)超于t3.矩陣對策的混合策略(續(xù))24- 優(yōu)超原則：當(dāng)局中人甲方的策略 t 被其它策略所優(yōu)超時，可在其贏得矩陣A中劃去第t行（同理，當(dāng)局中人乙方的策略t被其它策略所優(yōu)超時，可在矩陣A中劃去第t列）。 如此得到階數(shù)較小的贏得矩陣A，其對應(yīng)的矩陣對策 G= S1,S2,A與 G = S1,S2,A 等價，即解相同。 3.矩陣對策的混合策略(續(xù))25例 設(shè)甲方的益損值 贏得矩陣。 3 2 0 3 0 被第3、4行所優(yōu)超 5 0 2 5 9 被第3行所優(yōu)超 A= 7 3 9 5 9 4 6 8 7 5.5 6 0 8 8 3得到 7 3 9 5 9 被第1列所優(yōu)超 A1= 4 6 8 7 5.5 被第2列所優(yōu)超 6 0 8 8 33.矩陣對策的混合策略(續(xù))26續(xù)例 得到 7 3 9 A2= 4 6 5.5 6 0 3 被第1行所優(yōu)超得到 7 3 9 被第1列所優(yōu)超 A3= 4 6 5.5 7 3最終得到 A4= 4 6 3.矩陣對策的混合策略(續(xù))27對A4計(jì)算，用線性規(guī)劃方法得到：（注意：余下的策略為3，