对策论管理运筹学李军PPT课件

2020 4 24 1 第一节 引论 1 内涵 对策论亦称博弈论 GameTheory 具有竞争或对抗性质的行为称为对策行为 2 引例3 对策行为的基本要素4 对策行为的基本假设5 对策行为的分类 2020 4 24 2 1 引例 齐王赛马 齐王 上 中 下田忌 上 中 下 2020 4 24 3 1 引例 齐王赛马 齐王 上 中 下田忌 上 中 下 2020 4 24 4 2 对策行为的基本要素 1 局中人 Player 在一个对策行为中 有权决定自己行动方案的参加者称为局中人 2 策略 Strategy 一局对策中 可供局中人选择的完整的行动方案称为策略 3 赢得函数 Score 一局对策中 局中人使用每一策略都会有所得失 这种得失是全体局中人所采取的一组策略的函数 称为赢得函数 4 局势 一局对策中 各局中人选定的策略所形成的策略组称为一个局势 2020 4 24 5 3 对策行为的基本假设 对策行为总是假定每一个局中人都是 理智的 决策者 不存在利用其他局中人的决策失误来扩大自身利益的可能性或相反 2020 4 24 6 4 对策行为的分类 2020 4 24 7 第二节 矩阵对策 1 矩阵对策的数学模型2 矩阵对策解的问题3 矩阵对策的混合策略4 矩阵对策的基本定理5 矩阵对策解的性质 2020 4 24 8 1 矩阵对策的数学模型 1 矩阵对策的内涵 二人有限零和对策 即对策双方的利益是激烈对抗的 2 矩阵对策的数学模型 甲 有m个策略 表示为S1 1 2 3 m 乙 有n个策略 表示为S2 1 2 3 n 当甲选定策略 i 乙选定策略 j时 就形成了一个局势 i j 可见这样的局势总共有m n个 对任意局势 i j 甲的赢得值为aij 即甲的赢得矩阵为Am n aij 因为对策是零和的 所以乙的赢得矩阵为 Am n 2020 4 24 9 1 矩阵对策的数学模型 建立二人零和对策的模型就是要根据对实际问题的叙述 确定甲 乙两个局中人的策略集合以及相应的赢得矩阵 不难看出在 齐王赛马 的例子中 齐王的赢得矩阵为 A 31111 11333 111 13111 11131111 1131111 113 2020 4 24 10 1 矩阵对策的示例1 例1 甲的赢得矩阵 2020 4 24 11 1 矩阵对策的示例2 例2 从一张红牌和一张黑牌中随机抽取一张 在对乙保密的情况下拿给甲看 若甲看到的是红牌 他可以选择掷硬币或让乙猜 若甲选择掷硬币 出现正面甲赢p元 出现反面甲输q元 若让乙猜 当乙猜中是红牌时甲输r元 否则甲赢s元 若甲看到的是黑牌 他只能让乙猜 当乙猜中是黑牌时甲输u元 否则甲赢t元 试确定甲 乙各自的策略并建立赢得矩阵 正面1 2 2020 4 24 12 1 矩阵对策的示例2 正面1 2 若甲决定掷硬币这个策略 则乙的猜红或猜黑已无意义 若抽到黑牌 甲的掷硬币已无意义 只与乙的猜红或猜黑有关 所以 对于局势 掷硬币 猜红 甲的期望赢得为 1 2 1 2p 1 2q 1 2t 1 4 p q 2t 2020 4 24 13 1 矩阵对策的示例2 正面1 2 2020 4 24 14 2 矩阵对策解的问题 设矩阵对策G S1 S2 A 其中 S1 1 2 3 4 S2 1 2 3 A 42 6 643538 1 10 10 306 3 Min Max3 局中人甲应选择 2 此时不管局中人乙采取什么策略 甲的赢得均不小于3 2020 4 24 15 2 矩阵对策解的问题 设矩阵对策G S1 S2 A 其中 S1 1 2 3 4 S2 1 2 3 A 42 6 643538 1 10 10 306 3 Min Max3 局中人甲应选择 2 乙应采取 2策略 结果甲赢得3 乙付出3 Max836Min3 2020 4 24 16 2 矩阵对策解的问题 定义1 设矩阵对策G S1 S2 A 其中 S1 1 2 m S2 1 2 n A aij m n 若Maxminaij Minmaxaij ai j 则称ai j 为对策G的值 局势 i j 为G的解 i 和 j 分别称为局中人的最优策略 i j i j 2020 4 24 17 2 矩阵对策解的问题 由于ai j 既是其所在行的最小值 又是其所在列的最大值 于是有 aij ai j ai j定理1 设矩阵对策G S1 S2 A 在策略意义下有解的充分必要条件是存在着局势 i j 使得对于一切i与j都有aij ai j ai j成立 2020 4 24 18 2 矩阵对策解的问题 例 设矩阵对策G S1 S2 A 赢得矩阵为 A 75655 2 39 4 465755 01 12 1 Min Max 5 Max75 95 Min 5i 1 3 j 2 4 ai j 5 四个局势均为矩阵对策的解 2020 4 24 19 3 矩阵对策的混合策略 对矩阵对策G S1 S2 A 来说 局中人甲有把握的最小赢得是 v1 maxminaij局中人乙有把握的最大损失是 v2 minmaxaij当v1 v2时 对矩阵对策有策略意义下的解 然而并非总是如此 经常是v1 v2 总有v1 v2 此时没有策略意义下的解 i j i j 2020 4 24 20 3 矩阵对策的混合策略 A 44 6 643538 1 10 10 306 3 Min Max3 Max845 Min4 v1 3 v2 4 2020 4 24 21 3 矩阵对策的混合策略 v1 3 v2 4对于两个局中人来说 不存在一个双方均可接受的平衡局势 设矩阵对策G S1 S2 A 其中 S1 1 m S2 1 n A aij m n 则S1 xi 0 i 1 2 m x1 x2 xm 1 S2 yj 0 j 1 2 n y1 y2 yn 1 称为局中人的混合策略 2020 4 24 22 3 矩阵对策的混合策略 对x S1 y S2 称 x y 为一个混合局势 局中人的赢得函数记成 E x y xTAy这样便得到一个新的对策G S1 S2 E G 称为G的混合扩充 2020 4 24 23 3 矩阵对策的混合策略 G S1 S2 E 是G S1 S2 A 的混合扩充 如果maxminE x y minmaxE x y 记其值为VG 则VG为对策G 的值 使上式成立的混合局势 x y 为G在混合策略意义下的解 x y 分别称为局中人甲和乙的最优混合策略 注 策略意义下的解不存在时 自动转向混合策略意义下的解 x S1 y S2 x S1 y S2 2020 4 24 24 3 矩阵对策的混合策略 对策矩阵G S1 S2 A 在混合策略意义下有解的充分必要条件是存在着x S1 y S2 使 x y 为E x y 的一个鞍点 即对于一切x S1 y S2 有E x y E x y E x y 2020 4 24 25 3 矩阵对策的混合策略 例 对策矩阵G S1 S2 A 其中 A 显然G在策略意义下的解不存在 于是设x x1 x2 为局中人甲的混合策略 y y1 y2 为局中人乙的混合策略 则S1 xi 0 i 1 2 x1 x2 1 S2 yj 0 j 1 2 y1 y2 1 局中人甲的赢得期望值是 E x y xTAy 3 6 5 4 2020 4 24 26 3 矩阵对策的混合策略 例 E x y xTAy 3x1y1 6x1y2 5x2y1 4x2y2 4 x1 1 4 y1 1 2 9 2取x 1 4 3 4 y 1 2 1 2 则E x y E x y E x y 9 2即有E x y E x y E x y 故x 和y 分别为局中人甲和乙的最优 混合 策略 2020 4 24 27 4 矩阵对策的基本定理 定理1 设矩阵对策G S1 S2 A 在策略意义下有解的充分必要条件是存在着局势 i j 使得对于一切i与j都有aij ai j ai j成立 定理2 对策矩阵G S1 S2 A 在混合策略意义下有解的充分必要条件是存在着x S1 y S2 使 x y 为E x y 的一个鞍点 即对于一切x S1 y S2 有E x y E x y E x y 2020 4 24 28 4 矩阵对策的基本定理 定理3 设x S1 y S2 则 x y 是矩阵对策G的解的充分必要条件是对任意的i 1 2 m 和j 1 2 n 有E x y E x y E x y 2020 4 24 29 4 矩阵对策的基本定理 定理4 设x S1 y S2 则 x y 是矩阵对策G的解的充分必要条件是存在数v使得x 和y 分别是不等式组 aijxi v aijyj v xi 1 yj 1xi 0yj 0的解 且v VG i j j 1 2 n i 1 2 m i 1 2 m j 1 2 n 2020 4 24 30 4 矩阵对策的基本定理 定理5 对任一矩阵对策G S1 S2 A 一定存在混合策略意义下的解 2020 4 24 31 5 矩阵对策解的性质 性质1 设 x y 是矩阵对策G S1 S2 A 的解 v VG 则 1 若xi 0 则 aijyj v 2 若 aijyj 0 则 aijxi v 4 若 aijxi v 则yj 0 2020 4 24 32 5 矩阵对策解的性质 性质2 矩阵对策G1 S1 S2 A1 G2 S1 S2 A2 解集分别为T G1 和T G2 若其中有A1 aij A2 aij L L为任一常数 则 1 VG2 G1 L 2 T G2 T G1 2020 4 24 33 5 矩阵对策解的性质 性质3 矩阵对策G1 S1 S2 A G2 S1 S2 A 其中 为大于0的任一常数 则 1 VG2 VG1 2 T G2 T G1 2020 4 24 34 5 矩阵对策解的性质 性质4 设一矩阵对策G S1 S2 A 存在A AT 称为对称对策 则 1 VG 0 2 T1 G T2 G 分别为局中人甲 乙的最优策略集 2020 4 24 35 5 矩阵对策解的性质 性质5 设一矩阵对策G S1 S2 A 若在S1 或 和S2 中出现被优超的策略 那么去掉被优超的策略所形成的新的矩阵对策与原矩阵对策同解 A 4023 2 214 43738454656652743 例11 6 2020 4 24 36 第216页例11 6 由于第4行优超于第1行 第3行优超于第2行 故可去掉第1行和第2行 得到新的赢得矩阵 A1 738454656652743 2020 4 24 37 第216页例11 6 对于A1由于第1列优超于第3列 第2列优超于第4列 1 3 第1列 2 3 第2列 优超于第5列 故可去掉第3 4 5列 得到新的赢得矩阵 A2 734652 2020 4 24 38 第216页例11 6 对于A2由于第1行优超于第3行 故可去掉第3行 得到新的赢得矩阵 A3 7346 2020 4 24 39 第216页例11 6 对于A3易之于无鞍点存在 应用定理4求解不等式组 7x3 4x4 v3x3 6x4 vx3 x4 1x3 x4 0 7y1 3y2 v4y1 6y2 vy1 y2 1y1 y2 0 2020 4 24 40 第216页例11 6 求得解为 x3 1 3 x4 2 3y1 1 2 y2 1 2 于是原矩阵对策的一个解是 x 0 0 1 3 2 3 0 Ty 1 2 1 2 0 0 0 TVG 5 2020 4 24 41 第三节矩阵对策的求解 1 2 2对策的公式法2 2 n或m 2对策的图解法3 线性方程组求解法4 线性规划求解法 2020 4 24 42 1 2 2对策的公式法 所谓2 2对策是指局中人的赢得矩阵为2 2阶矩阵 即 如果A有鞍点 则很快就可求出各局中人的最优策略 如果A没有鞍点 则可证明各局中人的最优混合策略中的xi yj 均大于零 于是由定理6可知 为求混合策略可求解下列方程组 a11x1 a21x2 va11y1 a12y2 va12x1 a22x2 va21y1 a22y2 vx1 x2 1y1 y2 1 2020 4 24 43 2 2 n或m 2对策的图解法 例 设一矩阵对策G S1 S2 A 其中S1 1 2 S2 1 2 3 2311752 设局中人甲的混合策略为 x 1 x T x 0 1 过数轴上坐标为0和1的两点分别做两条垂线 和 垂线上点的纵坐标值分别表示局中人甲采取纯策略 1 2时 局中人乙采取各策略时的赢得值 如下图所示 当局中人甲选择每一混合策略 x 1 x T时 他可能的最少赢得为局中人乙选择 1 2 3时所确定的3条直线在x处的纵坐标值的最小值 2020 4 24 44 2 2 n或m 2对策的图解法 V 2x 7 1 x V 3x 5 1 x V 11x 2 1 x 设局中人甲的混合策略为 x 1 x T x 0 1 过数轴上坐标为0和1的两个点分别做两条垂线 和 垂线上的点的纵坐标值分别表示局中人甲采取纯策略 1 2时 局中人乙采取各策略时的赢得值 如下图所示 2020 4 24 45 甲采取混合策略最少的赢得 B1BB2B3甲确定x使赢得最大 即最小最大原则 2020 4 24 46 x OA AB即为对策值VG求解x及VG 解方程组 VG 3x 5 1 x VG 11x 2 1 x 求得x 3 11 VG 49 11 所以甲的最优策略为x 3 11 8 11 E x 1 2 3 11 7 8 11 62 11 49 11E x 2 3 3 11 5 8 11 49 11E x 3 11 3 11 2 8 11 49 11所以局中人乙的最优混合策略y 0 y2 y3 2020 4 24 47 3y2 11y3 VG 49 115y2 2y3 VG 49 11y2 y3 1求解得y 0 9 11 2 11 2020 4 24 48 例 设一矩阵对策G S1 S2 A 其中S1 1 2 3 S2 1 2 27A 66112设乙的混合策略为 y 1 y 同理有 2020 4 24 49 0 1 2 6 7 11 6 2 y A1 B1 B2 B3 乙采取混合策略最大的支付 7B1B211乙确定y使支付最小 即最大最小原则 3 2 1 A2 2020 4 24 50 OA1 y OA2VG 62y 7 1 y 66y 6 1 y 66y 6 1 y 611y 2 1 y 6求得OA1 1 5 OA2 4 9 故局中人乙的最优混合策略为y y 1 y 其中y 1 5 4 9 而故局中人甲的最优策略显然只能是x 0 1 0 即策略 2 2020 4 24 51 3 线性方程组求解法 根据定理4求解矩阵对策解 x y 的问题等价于求解 aijxi v aijyj v xi 1 yj 1xi 0yj 0又根据定理5和定理6 如果x y 中各分量均不为零 即可将不等式组转换为方程组 2020 4 24 52 3 线性方程组求解法 不等式组转换为方程组 aijxi v aijyj v xi 1 yj 1xi 0yj 0如果这两个方程组存在非负解x 和y 则已经求得了矩阵对策的解 x y 2020 4 24 53 3 线性方程组求解法 例 齐王赛马 齐王的赢得矩阵为311