管理運籌學對策論課件

對策論由“齊王賽馬”引入對策論由“齊王賽馬”引入11.對策論的基本概念三個基本要素；1.局中人：參與對抗的各方；2.策略集：局中人選擇對付其它局中人的行動方案稱為策略。某局中人的所有可能策略全體稱為策略集；3.局勢對策的益損值：各局中人各自使用一個對策就形成一個局勢，一個局勢決定了個局眾人的對策結(jié)果（量化）稱為該局勢對策的益損值）1.對策論的基本概念三個基本要素；2“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）3其中：齊王的策略集:S1={1,2,3,4,5,6}田忌的策略集：S1={1,2,3,4,5,6}下列矩陣稱齊王的贏得矩陣：

3111-1113111-1A=1-13111-111311111-13111-1113其中：41.基本概念（續(xù)）二人有限零和對策：（又稱矩陣策略）局中人為2；每局中人的策略集中策略權(quán)目有限；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。1.基本概念（續(xù)）二人有限零和對策：（又稱矩陣策略）51.基本概念（續(xù)）記矩陣對策為:

G={S1,S2,A}

甲的策略集甲的贏得矩陣乙的策略集“齊王賽馬”即是一個矩陣策略.1.基本概念（續(xù)）記矩陣對策為:62.矩陣對策的最優(yōu)純策略在甲方贏得矩陣中：A=[aij]m*ni行代表甲方策略i=1,2…mJ列代表乙方策略j=1,2…naij代表甲方取策略i,乙方取策略j,這一局勢下甲方的益損值，此時乙方的益損值為-aij（零和性質(zhì)）。在討論各方采用的策略是必須注意一個前提就是對方是理智的。這就是要從最有把握取得的益損值情況考慮。2.矩陣對策的最優(yōu)純策略在甲方贏得矩陣中：72.矩陣對策的最優(yōu)純策略(續(xù))例：有交易雙方公司甲和乙，甲有三個策略1，2，3；乙有四個策略1，2，3，4，根據(jù)獲利情況建立甲方的益損值贏得矩陣。

-30-20A=2301-2-4-13問：甲公司應(yīng)采取什么策略比較適合？2.矩陣對策的最優(yōu)純策略(續(xù))例：有交易雙方公司甲和乙，甲有8甲：采取1至少得益–3(損失3）203-4(損失4）乙：采取1甲最多得益2（乙最少得益-2）23（乙得益-3）30（乙得益0）43（乙得益-3）取大則取2maxminaij=0

ij取小則取3minmaxaij=0ji甲：取大則取2取小則取39甲采取策略2不管乙采取如何策略，都至少得益。乙采取策略3不管甲采取如何策略，都至少可以得益。（最多損失0）分別稱甲，乙公司的最優(yōu)策略，由唯一性又稱最優(yōu)純策略。存在前提：

maxminaij=minmaxaij=v

ijji又稱（2，3）為對策G={s1,s2,A}的鞍點。值V為G的值。甲采取策略2不管乙采取如何策略，都至少得益。103.矩陣對策的混合策略設(shè)矩陣對策G={S1,S2,A}當maxminaijminmaxaij

ijji時，不存在最優(yōu)純策略求解混合策略。3.矩陣對策的混合策略設(shè)矩陣對策G={S1,S2,A}113.矩陣對策的混合策略例：設(shè)一個贏得矩陣如下:

min595A=max6策略2866imax89min8

策略1

j3.矩陣對策的混合策略例：設(shè)一個贏得矩陣如下:12矛盾：甲取2，乙取時1，甲實際贏得8比預期多2（乙就少2）這對乙講是不滿意的，考慮這一點，乙采取策略2，若甲分析到這一點，取策略1，則贏得更多為9…此時，甲，乙方?jīng)]有一個雙方均可接受的平衡局勢。一個思路：對甲（乙）給出一個選取不同策略的概率分布，以使甲（乙）在各種情況下的平均贏得（損失）最多（最少）。-----即混合策略矛盾：甲取2，乙取時1，甲實際贏得8比預期多2（乙就少13求解方法：線性規(guī)劃法（其他方法：圖解法，迭代法，線性方程法等略）例：59設(shè)在最壞的情況下，A=甲贏得的平均值為V.

86（未知）STEP11)設(shè)甲使用策略1的概率為X1′X1′+X2′=1設(shè)甲使用策略2的概率為X2′X1′,X2′0求解方法：線性規(guī)劃法142)無論乙取何策略，甲的平均贏得應(yīng)不少于V:對乙取1：5X1’+8X2’V對乙取2：9X1’+6X2’V注意V>0,因為A各元素為正。STEP2作變換：X1=X1’/V;X2=X2’/V得到上述關(guān)系式變?yōu)椋篨1+X2=1/V(V愈大愈好）待定5X1+8X219X1+6X21X1,X202)無論乙取何策略，甲的平均贏得應(yīng)不少于V:15建立線性模型：

minX1+X2

s.t.5X1+8X21X1=1/21

9X1+6X21X2=2/21X1,X201/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.建立線性模型：16同樣可求乙的最優(yōu)混合策略：設(shè)乙使用策略1的概率為Y1′Y1′+Y2′=1設(shè)乙使用策略2的概率為Y2′Y1′,Y2′0設(shè)在最壞的情況下，甲贏得的平均值為V.這也是乙損失的平均值，越小越好作變換：Y1=Y1’/V;Y2=Y2’/V建立線性模型：

maxY1+Y2

s.t.5Y1+9Y21Y1=1/14

8Y1+6Y21Y2=1/14Y1,Y201/V=Y1+Y2=1/7所以：V=7

同樣可求乙的最優(yōu)混合策略：17返回原問題：Y1’=Y1V=1/2

Y2’=Y2V=1/2于是乙的最優(yōu)混合策略為：以1/2的概率選1；以1/2的概率選2最優(yōu)值V=7.當贏得矩陣中有非正元素時，V0的條件不一定成立，可以作下列變換：選一正數(shù)k，令矩陣中每一元素加上k得到新的正矩陣A’，其對應(yīng)的矩陣對策G’={S1,S2,A’}與G={S1,S2,A}解相同，但VG=VG’-k返回原問題：Y1’=Y1V=1/218例：求解“齊王賽馬”問題（見備課稿）優(yōu)超原則：假設(shè)矩陣對策G={S1,S2,A}

甲方贏得矩陣A=[aij]mn--若存在兩行（列），s行（列）的各元素均優(yōu)于t行（列）的元素，即asjatjj=1,2…n(ais

aiti=1,2…m)稱甲方策略s優(yōu)超于t(s優(yōu)超于t)3.矩陣對策的混合策略(續(xù))例：求解“齊王賽馬”問題（見備課稿）3.矩陣對策的混合策略(19--優(yōu)超原則：當局中人甲方的策略t被其它策略所優(yōu)超時，可在其贏得矩陣A中劃去第t行（同理，當局中人乙方的策略t被其它策略所優(yōu)超時，可在矩陣A中劃去第t列）。如此得到階數(shù)較小的贏得矩陣A’，其對應(yīng)的矩陣對策

G’={S1,S2,A’}與G={S1,S2,A}等價，即解相同。3.矩陣對策的混合策略(續(xù))--優(yōu)超原則：當局中人甲方的策略t被其它策略所優(yōu)超時，可20例設(shè)甲方的益損值贏得矩陣。

32030

被第3、4行所優(yōu)超

50259

被第3行所優(yōu)超A=7395946875.560883得到73959被第1列所優(yōu)超A1=46875.5被第2列所優(yōu)超608833.矩陣對策的混合策略(續(xù))例設(shè)甲方的益損值贏得矩陣。3.矩陣對策的混合策略(續(xù))21續(xù)例得到739A2=465.5

603

被第1行所優(yōu)超得到739

被第1列所優(yōu)超A3=465.573最終得到A4=463.矩陣對策的混合策略(續(xù))續(xù)例得到3.矩陣對策的混合策略(續(xù))22對A4計算，用線性規(guī)劃方法得到：（注意：余下的策略為3，4，1，2）甲：X*=(0，0，1/15，2/15，0)TV=5X*’=(0，0，1/3，2/3，0)T

乙：Y*=(1/10，1/10，0，0，0)TV=5Y*’=(1/2，1/2，0，0，0)T

注：利用有超原則化簡贏得矩陣時，有可能將原對策問題的解也劃去一些（多解情況）；線性規(guī)劃求解時有可能是多解問題。習題：P343-1，3，43.矩陣對策的混合策略(續(xù))對A4計算，用線性規(guī)劃方法得到：3.矩陣對策的混合策略(續(xù))23對策論由“齊王賽馬”引入對策論由“齊王賽馬”引入241.對策論的基本概念三個基本要素；1.局中人：參與對抗的各方；2.策略集：局中人選擇對付其它局中人的行動方案稱為策略。某局中人的所有可能策略全體稱為策略集；3.局勢對策的益損值：各局中人各自使用一個對策就形成一個局勢，一個局勢決定了個局眾人的對策結(jié)果（量化）稱為該局勢對策的益損值）1.對策論的基本概念三個基本要素；25“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）26其中：齊王的策略集:S1={1,2,3,4,5,6}田忌的策略集：S1={1,2,3,4,5,6}下列矩陣稱齊王的贏得矩陣：

3111-1113111-1A=1-13111-111311111-13111-1113其中：271.基本概念（續(xù)）二人有限零和對策：（又稱矩陣策略）局中人為2；每局中人的策略集中策略權(quán)目有限；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。1.基本概念（續(xù)）二人有限零和對策：（又稱矩陣策略）281.基本概念（續(xù)）記矩陣對策為:

G={S1,S2,A}

甲的策略集甲的贏得矩陣乙的策略集“齊王賽馬”即是一個矩陣策略.1.基本概念（續(xù)）記矩陣對策為:292.矩陣對策的最優(yōu)純策略在甲方贏得矩陣中：A=[aij]m*ni行代表甲方策略i=1,2…mJ列代表乙方策略j=1,2…naij代表甲方取策略i,乙方取策略j,這一局勢下甲方的益損值，此時乙方的益損值為-aij（零和性質(zhì)）。在討論各方采用的策略是必須注意一個前提就是對方是理智的。這就是要從最有把握取得的益損值情況考慮。2.矩陣對策的最優(yōu)純策略在甲方贏得矩陣中：302.矩陣對策的最優(yōu)純策略(續(xù))例：有交易雙方公司甲和乙，甲有三個策略1，2，3；乙有四個策略1，2，3，4，根據(jù)獲利情況建立甲方的益損值贏得矩陣。

-30-20A=2301-2-4-13問：甲公司應(yīng)采取什么策略比較適合？2.矩陣對策的最優(yōu)純策略(續(xù))例：有交易雙方公司甲和乙，甲有31甲：采取1至少得益–3(損失3）203-4(損失4）乙：采取1甲最多得益2（乙最少得益-2）23（乙得益-3）30（乙得益0）43（乙得益-3）取大則取2maxminaij=0

ij取小則取3minmaxaij=0ji甲：取大則取2取小則取332甲采取策略2不管乙采取如何策略，都至少得益。乙采取策略3不管甲采取如何策略，都至少可以得益。（最多損失0）分別稱甲，乙公司的最優(yōu)策略，由唯一性又稱最優(yōu)純策略。存在前提：

maxminaij=minmaxaij=v

ijji又稱（2，3）為對策G={s1,s2,A}的鞍點。值V為G的值。甲采取策略2不管乙采取如何策略，都至少得益。333.矩陣對策的混合策略設(shè)矩陣對策G={S1,S2,A}當maxminaijminmaxaij

ijji時，不存在最優(yōu)純策略求解混合策略。3.矩陣對策的混合策略設(shè)矩陣對策G={S1,S2,A}343.矩陣對策的混合策略例：設(shè)一個贏得矩陣如下:

min595A=max6策略2866imax89min8

策略1

j3.矩陣對策的混合策略例：設(shè)一個贏得矩陣如下:35矛盾：甲取2，乙取時1，甲實際贏得8比預期多2（乙就少2）這對乙講是不滿意的，考慮這一點，乙采取策略2，若甲分析到這一點，取策略1，則贏得更多為9…此時，甲，乙方?jīng)]有一個雙方均可接受的平衡局勢。一個思路：對甲（乙）給出一個選取不同策略的概率分布，以使甲（乙）在各種情況下的平均贏得（損失）最多（最少）。-----即混合策略矛盾：甲取2，乙取時1，甲實際贏得8比預期多2（乙就少36求解方法：線性規(guī)劃法（其他方法：圖解法，迭代法，線性方程法等略）例：59設(shè)在最壞的情況下，A=甲贏得的平均值為V.

86（未知）STEP11)設(shè)甲使用策略1的概率為X1′X1′+X2′=1設(shè)甲使用策略2的概率為X2′X1′,X2′0求解方法：線性規(guī)劃法372)無論乙取何策略，甲的平均贏得應(yīng)不少于V:對乙取1：5X1’+8X2’V對乙取2：9X1’+6X2’V注意V>0,因為A各元素為正。STEP2作變換：X1=X1’/V;X2=X2’/V得到上述關(guān)系式變?yōu)椋篨1+X2=1/V(V愈大愈好）待定5X1+8X219X1+6X21X1,X202)無論乙取何策略，甲的平均贏得應(yīng)不少于V:38建立線性模型：

minX1+X2

s.t.5X1+8X21X1=1/21

9X1+6X21X2=2/21X1,X201/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.建立線性模型：39同樣可求乙的最優(yōu)混合策略：設(shè)乙使用策略1的概率為Y1′Y1′+Y2′=1設(shè)乙使用策略2的概率為Y2′Y1′,Y2′0設(shè)在最壞的情況下，甲贏得的平均值為V.這也是乙損失的平均值，越小越好作變換：Y1=Y1’/V;Y2=Y2’/V建立線性模型：

maxY1+Y2

s.t.5Y1+9Y21Y1=1/14

8Y1+6Y21Y2=1/14Y1,Y201/V=Y1+Y2=1/7所以：V=7

同樣可求乙的最優(yōu)混合策略：40返回原問題：Y1’=Y1V=1/2

Y2’=Y2V=1/2于是乙的最優(yōu)混合策略為：以1/2的概率選1；以1/2的概率選2最優(yōu)值V=7.當贏得矩陣中有非正元素時，V0的條件不一定成立，可以作下列變換：選一正數(shù)k，令矩陣中每一元素加上k得到新的正矩陣A’，其對應(yīng)的矩陣對策G’={S1,S2,A’}與G={S1,S2,A}解相同，但VG=VG’-k返回原問題：Y1’=Y1V=1/241例：求解“齊王賽馬”問題（見備課稿）優(yōu)超原則：假設(shè)矩陣對策G={S1,S2,A}

甲方贏得矩陣A=[aij]mn--若存在兩行（列），s行（列）的各元素均優(yōu)于t行（列）的元素，即asjatjj=1,2…n(ais

aiti=1,2…m)稱甲方策略s優(yōu)超于t(s優(yōu)超于t)3.矩陣對策的混合策略(續(xù))例：求解“齊王賽馬”問題（見備課稿）3.矩陣對策的混合策略(42--優(yōu)超原則：當局中人甲方的策略t被其它策略所優(yōu)超時，可在其贏得矩陣A中劃去第t行（同