06-对策论 运筹学 教学课件.pptVIP

定理2：矩阵对策 G = { S1，S2；A }，在混合策略意义下有解的充分必要条件是： 存在混合局势（ X*，Y*），使得对一切 X?S1*，Y? S2* 均有 E（X，Y*）? E（X*，Y*）? E（X*，Y） 定理3：对给定的矩阵对策 G = { S1，S2；A } 设X*? S1* Y* ? S2*则混合局势（ X*，Y*）是G的解且V=VG*的充分必要条件是： 对一切 i,j均有 E（ ?i， Y*） ? V ? E（X*， ?j ） 定理4：任意一个给定的矩阵对策在混合策略意义下一定有解。 矩阵对策的解可能不只一个，但对策值是唯一。 例5（订货计划）某厂制造和销售一种新仪器，需要外购一种配件。现有三个厂生产这种配件，牌号为A，B，C。 A配件每只10元，但有次品，装配的仪器也是次品，每台损失100元；B配件每只55元，也有次品，但装配的仪器出售后可在保修期内稍加修理就能使用，修理费55元； C配件每只118元，没有次品；问该厂应如何购置各种配件，使总费用（包括损失费和修理费）最少？ 例6（费用分摊问题）假设沿某河流有相邻的三个城市：A，B，C。各城市都想建立自来水厂解决用水问题。各城市可单独建立自来水厂，也可以合作建一个大水厂，再用管道送到各城市。经估计，合作建一个大水厂比单独建三个自来水厂的总费用少。三个城市有意合作，但是否实施，看总费用的分摊是否合理。问题是如何合理分摊费用，使合作建立大水厂的方案得以实现。 例7（拍卖问题）拍卖形式是先由拍卖商对拍卖品描述一番，然后提出第一个报价。接下来由买者报价，每一次都比前次高，最后谁出的价格高拍卖品即归谁所有。假设报价为p1,p2… pn-1 , pn,设p1p2 … pn-1 pn.买主只要略高于pn-1就能买到。问题是，各买主之间可能知道他人的估价，也可能不知道他人的估价，每人应如何报价对自己能以较低的价格得到拍卖品最为有利？ 例8（囚犯难题）设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干的，则每人各判刑7年；如果两人都不承认，则由于证据不足，两人各判刑1年； 如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑9年。因此，对两个囚犯来说，面临着一个“承认”和“不承认”之间两个策略的选择的难题。 矩阵对策的解法 一、 m*n 矩阵对策的线性规划法 求解矩阵对策可以等价地转化成求解互为对偶的线性规划问题，对给定的赢得矩阵 A=(aij)mn 转化成两个互为对偶的线性规划问题 ( LP) min ? pi st ? pi aij ? 1 (j=1,2,….. n) i pi ? 0 (i=1,2,….. m) (DLP) max ? qj st ? qj aij ? 1 (i=1,2,….. m) j qj ? 0 (j=1,2,….. n) 且 ? pi = ? qj = 1/ V 例9 对给定的赢得矩阵A A，=（ aij +2） 0 1 -1 2 3 1 A= -1 0 1 A，= 1 2 3 1 -1 0 3 1 2 （ LP） min （p1 +p2+p3 ） st 2p1 +p2+3p3 ? 1 3p1 +2p2+p3 ? 1 p1 +3p2+2p3 ? 1 pi ? 0 (I = 1,2 , 3) ( DLP) max （q1 + q2 + q3 ） st 2q1 + 3q2 + q3 ? 1 q1 + 2q2 + 3q3 ? 1 3