1、管理運(yùn)籌學(xué)對(duì)策論第1頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二1.對(duì)策論的基本概念三個(gè)基本要素；1.局中人：參與對(duì)抗的各方；2.策略集：局中人選擇對(duì)付其它局中人的行動(dòng)方案稱為策略。 某局中人的所有可能策略全體稱為策略集；3.局勢對(duì)策的益損值：各局中人各自使用一個(gè)對(duì)策就形成一個(gè)局勢，一個(gè)局勢決定了個(gè)局眾人 的對(duì)策結(jié)果（量化）稱為該局勢對(duì)策的益損值）第2頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）第3頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二其中：齊王的策略集: S1=1,2,3,4,5,6田忌的策略集：S1

2、=1,2,3,4,5,6 下列矩陣稱齊王的贏得矩陣： 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 第4頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二1.基本概念（續(xù)）二人有限零和對(duì)策：（又稱矩陣策略）局中人為2；每局中人的策略集中策略權(quán)目有限；每一局勢的對(duì)策均有確定的損益值，并且對(duì)同一局勢的兩個(gè)局中人的益損值之和為零。第5頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二1.基本概念（續(xù)）記矩陣對(duì)策為: G = S1, S2, A 甲的策略集 甲的贏得矩陣 乙的策

3、略集“齊王賽馬”即是一個(gè)矩陣策略.第6頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二2.矩陣對(duì)策的最優(yōu)純策略在甲方贏得矩陣中： A=aijm*ni行代表甲方策略 i=1,2mJ列代表乙方策略 j=1,2naij代表甲方取策略i,乙方取策略j,這一局勢下甲方的益損值，此時(shí)乙方的益損值為-aij（零和性質(zhì)）。在討論各方采用的策略是必須注意一個(gè)前提就是對(duì)方是理智的。這就是要從最有把握取得的益損值情況考慮。第7頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二2.矩陣對(duì)策的最優(yōu)純策略(續(xù))例：有交易雙方公司甲和乙，甲有三個(gè)策略1，2，3；乙有四個(gè)策略1，2，3，4，根據(jù)獲利情況建立甲方

4、的益損值 贏得矩陣。 -3 0 -2 0 A= 2 3 0 1 -2 -4 -1 3問：甲公司應(yīng)采取什么策略比較適合？第8頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二甲：采取1至少得益3(損失 3） 2 0 3 -4(損失 4）乙：采取1甲最多得益2 （乙最少得益-2） 2 3（乙得益-3） 3 0（乙得益 0） 4 3（乙得益-3）取大則取2 max min aij= 0 i j取小則取3 min max aij= 0 j i第9頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二甲采取策略2 不管乙采取如何策略，都至少得益。乙采取策略3 不管甲采取如何策略， 都至少可以得益

5、。（最多損失0） 分別稱甲，乙公司的最優(yōu)策略，由唯一性又稱最優(yōu)純策略。存在前提： max min aij = min max aij = v i j j i又稱（ 2 ，3 ）為對(duì)策G=s1,s2,A的鞍點(diǎn)。值V為G的值。第10頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二3.矩陣對(duì)策的混合策略設(shè)矩陣對(duì)策 G =S1,S2,A當(dāng) max min aij min max aij i j j i 時(shí)，不存在最優(yōu)純策略 求解混合策略。第11頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二3.矩陣對(duì)策的混合策略例：設(shè)一個(gè)贏得矩陣如下: min 5 9 5 A = max 6 策略2

6、8 6 6 i max 8 9 min 8 策略1 j第12頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二矛盾：甲取2 ，乙取時(shí)1，甲實(shí)際贏得8比預(yù)期多2（乙就少2）這對(duì)乙講是不滿意的，考慮這一點(diǎn)，乙采取策略2，若甲分析到這一點(diǎn)，取策略1，則贏得更多為9此時(shí)，甲，乙方?jīng)]有一個(gè)雙方均可接受的平衡局勢。一個(gè)思路：對(duì)甲（乙）給出一個(gè)選取不同策略的概率分布，以使甲（乙）在各種情況下的平均贏得（損失）最多（最少）。-即混合策略第13頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二求解方法：線性規(guī)劃法（其他方法：圖解法，迭代法，線性方程法等略）例： 5 9 設(shè)在最壞的情況下， A= 甲贏

7、得的平均值為V. 8 6 （未知）STEP 11)設(shè)甲使用策略1的概率為X1 X1+X2=1 設(shè)甲使用策略2的概率為X2 X1,X20第14頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二2)無論乙取何策略，甲的平均贏得應(yīng)不少于V:對(duì)乙取1：5X1+ 8X2V對(duì)乙取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, X20第15頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二建立線性模型： min X1+

8、X2 s.t. 5X1+8X21 X1= 1/21 9X1+6X21 X2= 2/21 X1, X20 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.第16頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二同樣可求乙的最優(yōu)混合策略：設(shè)乙使用策略1的概率為Y1 Y1+Y2=1 設(shè)乙使用策略2的概率為Y2 Y1,Y20設(shè)在最壞的情況下，甲贏得的平均值為V. 這也是乙損失的平均值，越小越好 作變換： Y1= Y1/V ; Y2= Y2/V建立線性模型：

9、 max Y1+Y2 s.t. 5Y1+9Y21 Y1= 1/14 8Y1+6Y21 Y2= 1/14 Y1, Y20 1/V= Y1+Y2=1/7 所以：V=7 第17頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二返回原問題： Y1= Y1V= 1/2 Y2= Y2V= 1/2 于是乙的最優(yōu)混合策略為： 以1/2的概率選1；以1/2的概率選2 最優(yōu)值V=7.當(dāng)贏得矩陣中有非正元素時(shí)，V0的條件不一定成立，可以作下列變換： 選一正數(shù)k，令矩陣中每一元素加上k得到新的正矩陣A，其對(duì)應(yīng)的矩陣對(duì)策 G= S1,S2,A與 G = S1,S2,A 解相同，但VG = VG - k第18頁，共

10、23頁，2022年，5月20日，8點(diǎn)12分，星期二例：求解“齊王賽馬”問題（見備課稿）優(yōu)超原則： 假設(shè)矩陣對(duì)策 G = S1,S2,A 甲方贏得矩陣 A=aijmn- 若存在兩行（列），s 行（列）的各元素均優(yōu)于 t 行（列）的元素，即 asjatj j=1,2n ( ais ait i=1,2m ) 稱甲方策略s優(yōu)超于t ( s優(yōu)超于t)3.矩陣對(duì)策的混合策略(續(xù))第19頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二- 優(yōu)超原則：當(dāng)局中人甲方的策略t被其它策略所優(yōu)超時(shí)，可在其贏得矩陣A中劃去第t行（同理，當(dāng)局中人乙方的策略t被其它策略所優(yōu)超時(shí)，可在矩陣A中劃去第t列）。 如此得到階

11、數(shù)較小的贏得矩陣A，其對(duì)應(yīng)的矩陣對(duì)策 G= S1,S2,A與 G = S1,S2,A 等價(jià)，即解相同。3.矩陣對(duì)策的混合策略(續(xù))第20頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二例 設(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.矩陣對(duì)策的混合策略(續(xù))第21頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二續(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.矩陣對(duì)策的混合策略(續(xù))第22頁，共23頁，2022年，5月20日，8點(diǎn)12分，星期二對(duì)A4計(jì)算，用線性規(guī)劃方法得到：（注意：余下的策略為3，4，1，2）甲： X* = (0，0，1/15，2/15，0)T V=5 X*= (0，