《运筹学教程》胡云权 第五版 运筹学复习

运筹学复习,运筹学课程大纲,课程性质：方法技能类专业必须课课时数：1-14周，3，42学时课程框架考核方案：作业（50%）+考试（50%）,约束条件、目标最大/小化、最优方案,线性规划,整数规划,动态规划,运输问题,对策论,决策分析,图与网络分析,运筹学教材内容,线性规划第一章1-5节运输问题第三章1-4节整数规划第五章1-5节动态规划第七章1-4节图与网络分析第八章1-3节对策论第十二章1-3节决策论第十三章1-3节,第一章线性规划及单纯形法,主要内容,线性规划问题及其数学模型线性规划解的概念、图解法单纯形法原理线性规划应用,每个问题都用一组未知变量表示目标函数和约束条件。有一个目标函数，且可表示为一组未知量的线性函数，目标函数可以是求最大也可以求最小。存在一组约束条件，都可以用一组未知量的线性等式或不等式表示。,线性规划问题的特征,线性规划模型三要素,决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,xn表示目标函数决策变量的函数，目标可以是最大化或最小化约束条件对决策变量取值的限制条件，由决策变量x1,x2,xn的不等式组或方程组构成,线性规划模型的标准形式,目标函数：,约束条件：,目标最大化约束为等式决策变量均非负右端项非负,a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1,x2,xn0其中bi0，i=1,2,m,maxz=c1x1+c2x2+cnxn,解的重要概念,线性规划的求解方法图解法,图解法步骤：1、建立直角坐标系；2、图示约束条件，判断可行域；3、图示目标函数和寻找最优解；,MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20,o,x1,1234,4321,2x1+2x2=8,2x2=4,Z=2,Z=6,最优解：x1=2,x2=2最优值：Z=6,图解法求解的四种情况,定理1：线性规划问题的可行域为凸集。定理2：凸集的每个顶点对应一个基可行解。基可行解的个数是有限的，当然凸集的顶点个数也是有限的。定理3：若线性规划有最优解，必在可行域某顶点上达到。在有限个基可行解中间存在最优解。,基本定理,从一个初始基可行解出发，通过对基变量的迭代运算（每次迭代更换一个基变量，相当于从一个可行极点移动至与其相邻的另一个可行极点）而得到下一个基可行解，同时使目标函数值得到改善；经过有限次的迭代运算，就能得到LP的最优解。,单纯形法的基本原理,最优性条件：判断是否达到最优解的条件，以及确定下一次应调入哪一个非基变量为基变量，可使目标函数值得到改善；可行性条件：确定应调出哪一个基变量（使其成为非基变量）可确保新的基本解仍然是可行解。,，,由于基可行解数目有限（），因此，经过有限次迭代即可找到最优解。前提：线性规划为标准型。,单纯形法基本步骤,求初始基可行解确定换入变量的最优性条件确定换出变量的可行性条件运用初等行变换求出新的基可行解,单纯形法求解I.求初始基可行解,因为，基可行解是由一个可行基决定，所以，构造初始基可行解，相当于确定一个初始可行基,方法：若A中含I，则；若A中不含I，则用人工变量法（大M法）构造一个I。,问题：若，则例1中的,单纯形法求解II.最优性检验,把目标函数用非基变量表示：,检验数向量，记为。当时，当前解为最优解。,方法：计算每个的检验数若所有，则当前解为最优解否则，有，则找到最大的，其对应的作为换入变量。,单纯形法求解III.可行性检验,因为，基可行解与基相对应，所以，寻找新的可行解，即将初始可行基转化为，称基变换。,基变换的原则,换入变量：中最大的所对应的换入基；,换出变量：由决定出基变量。,方法：令令,检验比,单纯形法求解IV.求解新的基可行解,方法：用入基变量替换基变量中的换出变量，得到一个新的基；对应这个基可以找到一个新的基可行解；重复步骤II和III，直到结束，求出最优解。,旋转变换的实质就是用一系列的初等行变换将主元列变为单位列向量，其中主元变为1，主元列的其余元素都为零。,?,单纯形表：基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。单纯形表的主要结构,单纯形法求解单纯形表,1,1A,问题：第一张表的检验数的公式在哪里？,1=？,单位矩阵I,1,在哪里？,1,中的第j列,例2用单纯形法求解线性规划问题,单纯形法求解,解：（1）转化为标准型,主元素,大M法：若给定问题标准化后，系数矩阵中不存在m个线性无关的单位列向量，则在某些约束的左端加入非负变量（人工变量），使得变化后的系数矩阵中恰有m个线性无关的单位列向量，并且在目标函数中减去这些人工变量与M的乘积（M是相当大的一个正数）。对于变化后的问题，取这m个单位列向量构成的单位矩阵为初始基，该基对应的解一定是基可行解。,单纯形法的进一步讨论大M法,第一阶段（目的是求解该问题的一个初始基可行解）：在约束中加入人工变量使系数矩阵出现单位阵，然后目标函数变为maxW-人工变量，如果所得最优解中所有的人工变量都为零则得到原问题的一个基可行解（而非最优解），否则原问题无可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。,第二阶段：将第一阶段得到的基可行解作为原问题的初始基可行解，以原目标函数为目标函数进行计算，然后按照单纯形法求解原问题的最优解。,单纯形法的进一步讨论两阶段法,线性规划最优解的几种情况,教材P35,单纯形法小结,作业p44,1.1图解法1.21.31.61.71.101.121.131.14（1）,基矩阵（基）：设A是阶系数矩阵()，秩A=m，则A中一定存在m个线性无关的列向量，称由m个线性无关的列向量构成的可逆矩阵为问题L的一个基，L最多有个基。系数矩阵A中的m阶可逆子阵，记为B。其余为非基矩阵，记为N。基向量：基矩阵B中的列，其余为非基向量。基变量：与基矩阵B中列向量所对应的变量为基变量，记为，其余变量为非基变量，记为。,1.3线性规划标准型解的概念,1.3（2）答案,【解】此线性规划问题的系数矩阵A为,令A=(P1，P2，P3，P4),P1，P2线性无关，（P1,P2）为基.x1,x2为基变量，令非基变量x3,x4为0，得x1=-1/3，x2=11/3则基解为（-1/3,11/3,0,0），非可行解。,P1，P3线性无关，（P1,P3）为基.x1,x3为基变量，令非基变量x2,x4为0，得x1=5/2，x3=11/5则基解为（5/2,0,11/5,0），可行解。（5/2,0,11/5,0）为基可行解，z2=43/5,最优解为（5/2,0,11/5,0），最优值为43/5。,1.6（1）答案,【解】大M法,化为标准型，并加入人工变量得,由此可得，最优解X*=(45/7，4/7，0，0，0，0),Z*=102/7，具有唯一解。,1.6（1）答案,【解】两阶段法,第一阶段的数学模型,由此可得，第一阶段最优解X*=(45/7，4/7，0，0，0，0),原线性规划的基可行解。,原线性规划的最优解X*=(45/7，4/7，0，0，0),Z*=102/7，具有唯一解。,1.6（1）答案,第二阶段的目标函数,1.12答案,【解】（1）,为0的常数，则正负不变，最优解X*=(B-1b,0)T不变。,（2）,正负无法判断，因此最优解可能发生变化。,（3）,1.12答案,【解】（1）,为0的常数，则正负不变，最优解X*=(B-1b,0)T不变。,（2）,正负无法判断，因此最优解可能发生变化。,（3）,1.14（1）,教材P122例1,第二章运输问题,主要内容,运输问题模型特征表上作业法其它运输问题建模,运输问题的数学模型,针对单一品种物资运输调度问题设某物资有m个产地A1，A2，Am，产量分别是a1，a2，am，有n个销地B1，B2，Bn，销量分别是b1，b2，bn。从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是cij。如何调运这些物资使得总费用最小？,运输问题的数学模型,目标函数,约束条件,（1）产销平衡运输问题,（2）产过于求运输问题,（3）产不应求运输问题,约束条件的系数矩阵,产销平衡运输问题的数学模型特征,元素为0或1；列向量有两个非0元素，一个变量在前m个方程中出现一次，一个在后n个方程中出现一次矩阵的秩=m+n-1,产销平衡运输问题解法表上作业法,不需要写出上述模型，直接在运输表中进行计算,1、确定初始基可行解（1）最小元素法：优先考虑单位运价最小（或运距最短）的运输，最大限度满足其运输量，然后次小，直至给出初始调运方案。找出运输表中最小元素cij，优先赋值对应的xij=minai,bj。若xij=ai，则第i个产地全部运出，划掉运价表中的第i行；若xij=bj，则第j个销地全部满足，划掉运价表中的第j列；在剩下的运输表中，取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个，即可得初始基可行解。,产销平衡运输问题解法表上作业法,例1某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为t），以及各工厂到各销售点的单位运价（元/t）见下表。请问产品如何调运才能使费用最小？,产销平衡运输问题解法表上作业法,产地,销地,4,12,11,4,2,10,9,3,8,5,6,11,产地,销地,4,12,11,4,2,10,9,3,8,5,6,11,产销平衡运输问题解法表上作业法,8,2,10,14,8,6,初始基可行解：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8,其余均为0。z=246满足所有约束条件，非0变量的个数为6=3+4-1,1、确定初始基可行解最小元素法只考虑局部费用最小，可能为节省一处运费，而增加它处运费，导致总费用非最小。（2）沃格尔（Vogel）法：考虑产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。计算各行各列的罚数，罚数=次小费用-最小费用找出最大的罚数行或列所对应的最小费用优先安排重复计算步骤和,产销平衡运输问题解法表上作业法,产地,销地,4,12,11,4,2,10,9,3,8,5,6,11,产销平衡运输问题解法表上作业法,0,1,1,5,1,3,2,14,0,1,2,1,3,2,8,0,1,2,1,2,8,7,6,1,2,12,0,0,2,2,4,初始基可行解：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8,其余均为0。z=244,当最小元素或最大罚数对应的ai和bj相等时，即对应的产量和销量相等时，为保证基变量的个数为m+n-1个，除了在产销平衡表填xij=ai外，还应在产销平衡表中的第i行或第j列某空格（相应运价未被划掉）处填一个“0”，然后同时划去运价表上的第i行和第j列，该“0”看作是数字格。,产销平衡运输问题解法表上作业法,1、确定初始基可行解,2、最优性检验检验数：对于空格xij，假定给它一个单位运量，调整其它有关数字格运量，使产销平衡，则这一系列变化导致的总运费变化值称为该空格的检验数，记为。最优方案的判别准则：如果一个可行方案的所有空格的检验数都大于等于零，则该方案是最优方案。,产销平衡运输问题解法表上作业法,2、最优性检验（1）闭回路法寻找非基变量的闭回路。以空格（非基变量xij）为起点，沿水平或垂直方向前进，碰到基变量数字格后转90，继续前进直至回到起始空格为止。非基变量的计算检验数。假定给空格（非基变量xij）一个单位运量，调整该闭回路上所有数字格的运量，使产销平衡，则闭回路上总运费的变化值就等于。,产销平衡运输问题解法表上作业法,产地,销地,4,12,11,4,2,10,9,3,8,5,6,11,产销平衡运输问题解法表上作业法,2、最优性检验（1）闭回路法缺点：当变量个数较多时，寻找闭回路以及计算检验数的计算量较大。,产销平衡运输问题解法表上作业法,2、最优性检验（2）位势法（对偶变量法）在运输表中增加位势行ui和位势列vj计算行位势和列位势由公式，计算非基变量（空格）的检验数,产销平衡运输问题解法表上作业法,产地,销地,4,12,11,4,2,10,9,3,8,5,6,11,产销平衡运输问题解法表上作业法,设,21-11012,3、解的改进在运输表中，找出检验数为负的空格（非基变量xij）对应的闭回路Lij，在满足所有约束的前提下，尽可能增大xij，并相应调整此闭回路上其它数字格的运输量，得到另一个更好的基可行解。以xij为换入变量，找出它在运输表中的闭回路以空格（Ai,Bj）为第一个顶点，沿闭回路的顺（或逆）时针方向前进，对数字格依次编号在闭回路所有偶数数字格中，找出运输量最小的数字格，作为换出变量以偶数数字格最小运输量为调整量，将该闭回路中所有奇数格都增加这一数值，所有偶数格都减少这一数值，从而得出新的运输方案重复第2步最优性检验和第3步解的改进，直至得到最优解。,供销平衡运输问题解法表上作业法,产地,销地,4,12,11,4,2,10,9,3,8,5,6,11,产销平衡运输问题解法表上作业法,21-11012,偶数数字格的最小值,故，做出调整,得到新的基可行解,若运输问题的某一基可行解有多个非基变量的检验数为负，选择中最小的那个作为换入变量。当迭代到运输问题的最优解时，若有某非基变量的检验数为0，则该运输问题有多重最优解。当某部分产地的产量和，与某部分销地的销量和相等时，在迭代过程中可能在某一格填入一个运量时，需同时划去运输表中的一行和一列，则出现退化。为了使表上作业法顺利迭代，应在同时划去行或列中的某格填入数字0，表示该格为基变量，且取值为0，以保证基变量个数始终为m+n-1个。,产销平衡运输问题解法表上作业法,产大于销总产量大于总销量，则多余物资无处运输，需要考虑多余物资在哪些产地就地存储的问题。将该地的仓库设成一个假想的销地Bn+1，该销地总需求量:,产销不平衡的运输问题,产大于销若某产地i允许物资就地存储，则ci,n+1=0。因为物资就地存储不存在运输费用问题，运输单价应该是“0”。若某产地i不允许物资就地存储，则ci,n+1=M。M是一个相当大的正数。这样对于产地i，如果物资就地存储就付出相当大的代价，使得在求解时不得不将产地I的物资都运出去。在最优解中，产地Ai到虚拟销地Bj的运量，就是产地Ai就地存储的多余物资的数量。,产销不平衡的运输问题,产小于销总销量大于总产量，则某销地缺货，需要考虑确定哪些销地缺货多少的问题。设虚拟产地Am+1，总产量为,产销不平衡的运输问题,产小于销若某销地j允许缺货，则cm+1,j=0，结果会出现从虚拟产地Am+1向销地Bj运送货物，实际上这部分运量不可能存在，是最后分配方案中Bj的缺货量。由于这个产地不存在，当然运价为0。若某销地j不允许缺货，则cm+1,j=M，M是一个相当大的正数。意味着不可能从虚拟产地Am+1向销地Bj运送货物，则销地Bj的销量bj需要完全从产地A1Am运来，保证销地j不缺货。在最优解中，虚设产地Am+1到销地Bj的运量实际上就是最后分配方案中Bj的缺货量。,P96例4,产销不平衡的运输问题,作业p103,3.13.23.73.93.11,3.1,p82,3.9,【解】总产量大于总销量，增加虚拟食品厂4，需求量=10，并考虑单位利润，得到产销平衡运输表,3.11,【解】总需求量=320+250+350=920总供应量=400+450=850,缺少70，增加虚拟电站，能力为70。将城市1和3的需求量分为两部分，第一部分为必须供应，第二部分为可变供应。则得到产销平衡的运输表如下,第三章整数规划,主要内容,整数规划数学模型分枝定界法割平面法01规划指派问题,整数规划数学模型,部分或全部决策变量是整数的规划，称为整数规划。若模型是线性的，称为整数线性规划。本章只讨论整数线性规划。,纯整数规划：全部决策变量取整数值，又称全整数规划；混合整数规划：部分决策变量取整数值；0-1规划：决策变量只能取0或1。,割平面法,纯整数线性规划松弛问题,设aij(i=1,2,m;j=1,2,，n)和bi(i=1,2,m)皆为整数，若不为整数，可以乘上一个倍数化的整数。,（3.1a）,（3.1b）,（3.1c）,（3.1d）,（3.1a）,（3.1b）,（3.1c）,割平面法从X*的非整数分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题，形成一个新的线性规划，再求解。若新的线性规划最优解满足整数要求，即为纯整数规划的最优解，否则，重复上述步骤，直到获得整数最优解为止。新加约束条件基本性质已获得的不符合整数要求的线性规划最优解不满足该线性约束条件，以使原来的非整数最优解不再出现。凡整数可行解均满足该线性约束条件，以使整数最优解始终被保留在每次形成的线性规划可行域中。,割平面法,原松弛问题的最优解不可行,整数规划的整数可行解可行,最大整数与非负真分数之和,割平面法,割平面法计算步骤（1）运用单纯形法求松弛问题的最优单纯形表（2）针对非整数变量，增加新的约束条件（3）运用对偶单纯形法求解加入新约束条件后的单纯形表（4）重复步骤（2）、（3），直至得到整数解,分枝定界法,求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,求解0-1规划的隐枚举法,找出任意一可行解，目标函数值为Z0；原问题求最大值时，则增加一个约束当原问题求最小值时，上式改为小于等于约束；列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值；目标函数值最大（最小）的解就是最优解。,(*),指派问题,指派问题的标准形式：有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,n)，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。引入n2个0-1变量：数学模型,指派第i个人做第j件事,不指派第i个人做第j件事,(i,j=1,2,n),(i,j=1,2,n),(j=1,2,n),(i=1,2,n),【解】最优分配方案是安排四人工作，使完成工作总时间最少，最小值问题。,第一步：找出效率矩阵每行最小元素，每行分别减去其最小元素,Min3408,第二步：找出效率矩阵每列最小元素，每列分别减去其最小元素,Min,指派问题,第三步：用最少的直线覆盖所有“0”，得,第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算。,（1）从矩阵未被直线覆盖的数字中找出一个最小的数k，表中k3。,（2）直线相交处的元素加上k，未被直线覆盖的元素减去k，被直线覆盖而没有相交的元素不变，得到下列矩阵,指派问题,回到第三步:用最少的直线覆盖所有“0”，得,未被直线覆盖元素中最小元素k=2,直线相交处的元素加上2，未被直线覆盖的元素减去2，被直线覆盖而没有相交的元素不变，得到下列矩阵,指派问题,画线，,最少直线数等于4。,第五步：最优分配,最优解：,最优值Z73878288330,指派问题,作业p146,5.15.25.35.45.55.9,第四章动态规划,主要内容,多阶段决策过程动态规划基本概念动态规划基本思想动态规划求解方法动态规划应用,一般的动态规划基本方程可表示为,动态规划的基本方程,(4.2a),(4.2b),最优化原理：一个过程的最优策略具有这样的性质，无论初始状态及初始决策如何，对于先前决策所形成的状态而言，以后的决策应构成最优策略。,模型建立步骤确定过程的分段，构造状态变量；设置决策变量，写出状态转移；列出阶段指标和指标函数；写出基本方程，由此逐段递推求解。,动态规划模型建立,关键：识别问题的多阶段特征，将其分解为可用递推关系联系起来的若干子问题难点：状态变量的选择可知性：过程演变的各阶段状态变量的取值，能直接或间接确定无后效性重点：明确指标函数，得出基本方程（状态转移方程）,动态规划解法比较,作业p221,7.17.2,第五章图论与网络分析,图的基本概念最小支撑树问题最短路径问题,主要内容,定义1：由点和边组成，记作G=(V，E)，其中V=v1，v2，vn为结点的集合，E=e1，e2，em为边的集合。,点表示研究对象,边表示表示研究对象之间的特定关系,1.图,图的基本概念,注意：上面定义的图区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。,V、E为有限集合，则为有限图，反之无限图。,问题：求网络的支撑树，使其权和最小。,3、最小支撑树问题,算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。,【例】求上例中的最小支撑树,【解】,4,最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,3、最小支撑树问题,最小支撑树问题,5,5.5,v2,v3,v4,v5,3.5,4,2,3,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,3、最小支撑树问题,最小支撑树问题,5,v1,v2,v3,v4,v5,3.5,4,2,3,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,3、最小支撑树问题,最小支撑树问题,5,v1,v2,v3,v4,v5,3.5,2,3,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,3、最小支撑树问题,最小支撑树问题,解法1：Dijkstra（狄克斯拉）标号法,基本思想：从起点vs开始，逐步给每个结点vj标号dj，vi，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。,最短路问题,0,v1,1,v1,(1)给起点v1标号0,v1,(3)考虑所有这样的边vi,vj，其中viVA，vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4)重复(2)、(3)，直至终点vn标上号dn,vi，则dn即为v1vn的最短距离，反向追踪可求出最短路。,步骤：,0,v1,1,v1,3,v1,0,v1,1,v1,3,v1,5,v3,0,v1,1,v1,3,v1,5,v3,6,v2,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,此时终点v9已标号12,v5，则12即为v1vn的最短距离，反向追踪可求出最短路,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,v1到v9的最短路为：v1v3v2v5v9，最短距离为12,解法2：Floyd（弗洛伊德）算法,基本思想：从图的权矩阵D=(dij)nn开始，递归地进行n次更新，即由矩阵D(0)=D，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。,最短路问题,解法2：Floyd（弗洛伊德）算法,步骤：（1）输入权重矩阵D(0)=D（2）计算D(k)=(dij(k)nn(k=1,2,n)其中，dij(k)=mindij(k-1)，dik(k-1)+dkj(k-1)（3）D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。,最短路问题,【例】求图G中任意两点的最短路,【解】图G的权矩阵,表示从vi点到vj点或直接有边，或经v1为中间点时的最短路长,最短路问题,表示从vi点到vj点或直接有边，或最多经v1v2为中间点时的最短路长,最短路问题,作业p256,8.18.6,第六章对策论,主要内容,对策/博弈论概念及要素三个重要结论矩阵对策构建和求解方法,基本概念,对策论又称博弈论，研究冲突对抗条件下最优决策问题的理论。策略形势：不完全竞争条件下的对抗行为，各方收益由自身行为和其他方行为共同决定。,基本要素局中人（I）：有权决定自己行动方案的对策参加者，理性人策略集（S）：供局中人选择的实际可行完整行动方案的集合，一局对策中，各局中人选定策略的集合，称局势赢得函数（H(s)）:对于任一局势，局中人的赢得值。支付函数,严格占优策略/严格劣势策略上策均衡/纳什均衡,典型案例和重要结论,结论1：不要选择严格劣势策略。结论2：个人理性选择导致非最优。结论3：学会换位思考。,囚徒困境智猪博弈,求解方法：删除严格劣势策略,矩阵对策的策略,纯策略：确定的选择某策略混合策略：以某一概率分布选择各策略。,矩阵对策的纯策略,矩阵对策的一般表达,矩阵对策的纯策略,理智行为：从各自最不利情形中选择最有利I：最大最小原则II：最小最大原则,平衡局势：双方均可接受，且对双方都是最稳妥的结果。（2，2），局中人I和II的最优纯策略。,矩阵对策的最优纯策略,1231,3746,矩阵对策的纯策略,34,56,无鞍点,矩阵对策的混合策略,1、混合策略,矩阵对策的混合策略,2、混合局势,3、赢得期望,4、混合策略对策模型,矩阵对策的混合策略,5、最优混合策略,矩阵对策的混合策略,定理2：矩阵对策G在混合策略意义下有解的充要条件是：存在，使得对于任意，有,例：求解矩阵对策G=,其中,解：（1）不存在鞍点，为混合策略求解问题。（2）图解法求解设局中人I的混合策略为（x,1-x）T，。,0,1,I,I,II,II,数轴上坐标为0和1的两点分别做两条垂线I-I和II-II。,画出局中人II的不同策略下局中人I的赢得线段。,2,5,7,2,3,11,1=2x+7(1-x),2=3x+5(1-x),3=11x+2(1-x),图解法,仅适用于赢得矩阵为2n或m2阶的矩阵对策问题。,1:v11=2x+7(1-x)2:v12=3x+5(1-x)3:v13=11x+2(1-x),由于局中人II理性，局中人I从最少可能收入中选择最大的一个，为局中人I的最优对策。B2,求解方程组可得最优混合策略和矩阵对策的值。,0,1,I,I,II,II,2,5,7,2,3,11,1=2x+7(1-x),2=3x+5(1-x),3=11x+2(1-x),B1,B2,B3,B4,联立过B2点两条直线的方程组为,可解得,则，局中人I的最优策略为,由图可见局中人II的混合策略只有2和3组成。,图解法,设局中人II的最优混合策略为，且,求局中人II的最优混合策略。,同理，可得局中人II的赢得，,1:v21=3y2+11y32:v22=5y2+2y3,画出赢得线段，见右图,局中人I理性，局中人II取最大损失的最小值,联立方程组可得,解得,图解法,方程组法,定理：设，则为G的解的充要条件是：存在数v，使得x*,y*分别是下列不等式组的解，且v=VG。,若xi*,yj*均不为0，则上述不等式的求解