OR教学投影片(第13章)(OK).pptVIP

第十三章競賽理論 林吉仁 著 高立圖書公司出版 13-1概　論 競賽理論 (game theory) 又稱遊戲理論或對局理論 競賽中有至少兩位的競賽者，每位競賽者的目標互相衝突，彼此對抗，因此競賽者均有種種的策略，以期能打敗其他競賽者而獲得最大報酬或最小損失。 13-2競賽的類型 機率競賽 v.s 策略競賽 策略競賽可分為： 兩人競賽、多人(兩人以上)競賽 常數和競賽、非常數和競賽。本書討論零和競賽是一種特殊的常數和競賽 單純策略競賽與混合策略競賽 確定性競賽與機率性競賽 13-3 競賽的基本元素與假設 競賽架構中有三種基本元素： 競賽者 (player)：至少兩人 ( 方 )，但三人以上的競賽不在本書範圍 策略 (strategy)：每位競賽者至少有2個策略。但每回合雙方僅可選定一個策略 報酬 (payoff)：選定策略後的報酬。當雙方均採用最佳策略時，所獲得之報酬稱為競賽值 (value of the game)。競賽值為0的競賽，稱為公平的競賽。 報酬矩陣： 競賽的基本假設： 雙方均知道報酬矩陣 雙方均採理性的行動，追求最大報酬或最小損失 雙方均採取保守戰略 13-4 凌越規則 優勢策略 與 劣勢策略 凌越規則如下： 每個第 i1 列元素 ? 同行第 i2 列元素，則可刪去第 i2 列 每個第 j1 行元素 ? 同列第 j2 行元素，則可刪去第 j2 行 例題13-1 解： 重要性質 ? 定義13-1 ?在 m?n 報酬矩陣的競賽，若甲方採用第 i 個策略的機率為 xi，則稱機率向量 R =[x1, x2, ?, xm] 為甲方的策略；乙方採用第j個策略的機率為 yj，則稱 C=[y1, y2, ?, yn] 為乙方的策略。 ? 定理13-1 ?若A報酬矩陣的甲方最佳決策為R*，乙方最佳決策為C*，則競賽值E (R*, C*) = R*A(C*)T。 ? 定理13-2 ?每個競賽的競賽值是唯一的 13-5單純策略競賽 甲方準則：小中取大，自每一列中先選出最小值，再自這些數值中找出最大值 乙方準則：大中取小，先自每一行中選出最大值，再自這些數值中找出最小值 甲方、乙方所選取的元素為同一個時，此元素稱為鞍點。有鞍點的矩陣其競賽為單純策略競賽，雙方的最佳決策，競賽值均可自鞍點求出 無鞍點的矩陣則為混合策略競賽 例題13-2 設兩人零和競賽報酬陣為 請求雙方的最佳決策及競賽值？ 13-5 2?2混合策略競賽 無鞍點的混合策略的競賽，雙方常因應對方行動調整自己的行動，因此只能以機率來描述雙方的策略。 一般而言，無鞍點的競賽必須利用線性規劃模式加以求解 2?2 矩陣的競賽另有公式法 m?2，或 2?n 矩陣的競賽可用圖解法或拆成多個2?2競賽再比較 例題13-3 例題13-4 13-7線性規劃法 例題13-5 假設甲、乙兩人玩剪刀、石頭、布猜拳遊戲，勝方自敗方獲得1元，平手則報酬為0，請寫出報酬矩陣，並求雙方最佳決策與競賽值。 13-8兩策略競賽之解法 求解m?2或2?n的競賽矩陣方法有： (1) 將競賽拆成數個2?2子競賽 (sub-game) 再求解 (2) 將線性規劃模式簡化，利用圖解法加 以求解。 13-8-1a 2?2子競賽矩陣法 例題13-6 13-8-2 2?n,m?2競賽之圖解法 例題13-7 例題13-8 13-9 解題步驟 兩人零和競賽解題可依循以下步驟： 步驟1：以小中取大，大中取小準則尋找鞍點； 有鞍點，停止運算；無鞍點到步驟2 步驟2：以凌越規則簡化矩陣 步驟3：(1)2?2 矩陣，以公式法、圖解法、線性 規劃法求解 (2)2?n，m?2 矩陣以圖解法或線性規劃法 求解 (3)m?n；m, n ? 3之矩陣，以線性規劃法 求解 13-8-1b 2?2子競賽矩陣法 解： 圖13-1 圖13-2 解： 圖13-3 作業研究 解： ∴ 有鞍點的競賽，競賽值6 甲方最佳決策R*= [0,0,1,0]，即第Ⅲ策略 乙方最佳決策C*= [0,0,1,0]，亦為第Ⅲ策略 解： 解： 解： 解：