运筹学复习总结

《交通系统分析》复习及习题讲解龙建成[e-mail]一、线性规划问题标准形式线性规划解的概念单纯形法大M法，二阶段法对偶理论对偶单纯形灵敏度分析max(min)zcxcxcxnn1122staxaxaxbaxaxaxbaxaxaxbnnnmmmnnm..(.)(.)(.)1111221n1211222221122xxxn110,,一般形式目标函数约束条件非负约束条件max(min)zcxcxcxnn1122staxaxaxbaxaxaxbaxaxaxbnnnmmmnnm..(.)(.)(.)1111221n1211222221122xxxn110,,一般形式价值系数技术系数资源数量2.线性规划标准型及其如何化标准型nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111..0,,11nxxxnjjjxc1zmaxnjijijibxats1m...,2,,1..n...,2,1,j0jx1.繁写形式简写形式化标准型maxZ’=x1–2x2+3x3e.g.minZ=-x1+2x2–3x31.若目标函数为minZ=CX,令Z’=-Z,把目标函数转化为maxZ’=-CX。2.约束条件为不等式1）若左≥右，左–剩余变量=右（剩余变量≥0）2）若左≤右，左+松弛变量=右（松弛变量≥0）e.g.x1+2x2≤8x1+2x2+x3=8e.g.x1-x2+x3≥2x1-x2+x3-x4=23.若存在无约束的变量xk,令xk=xk’-xk”，代入其中,xk’，xk”≥0。minz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=5x1,x2≥0,x3无约束s.t.x1+x2+(x3’-x3”)+x4=7x1-x2+(x3’-x3”)-x5=2-3x1+x2+2(x3’-x3”)=5x1,x2,x3’,x3”,x4,x5≥0maxz’=x1-2x2+3(x3’-x3”)+0x4+0x54.若某约束变量xr有上下界，xr≥u,令xr’=xr–u,用xr’+u取代xrxr≤v，令xr’=v–xr,用v–xr’取代xr(xr’≥0)minz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=5x1,x2≥0,x3≥3s.t.x1+x2+(x3’+3)+x4=7x1-x2+(x3’+3)-x5=2-3x1+x2+2(x3’+3)=5x1,x2,x3’,x4,x5≥0maxz’=x1-2x2+3(x3’+3)+0x4+0x53.线性规划解的概念及其几何意义解的基本概念可行解满足约束条件的解。最优解使目标函数达到最大值的可行解。nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111..0,,11nxxx基(Basis)对于线性规划的约束条件AX=bX≥0设B是A矩阵中的一个非奇异的m×m子矩阵（|B|≠0），则称B为线性规划的一个基。其中A=mnm3m2m1.2n2322211n131211a...aaaa...aaaa...aaab=mbbbb.321],...,,[21ncccCmmm3m2m1.2m2322211m131211a...aaaa...aaaa...aaa设B=)P...,,P,P(m21Pj(1≤j≤m)为基向量；其余的为非基向量（n-m个）。设B是线性规划的一个基，则A可以表示为A=[B,N]NBXXXX也可相应地分成其中XB为m×1向量，称为基变量XN为(n-m)×1向量，称为非基变量约束方程AX=b的分块矩阵表示bXX.NB,NBAX=b可表示为或BXB+NXN=b若XN取确定的值，则XB有唯一的值与之对应XB=B-1b-B-1NXN特别，取XN=0，这时有XB=B-1b线性规划的解01bBXXXNB基解与基可行解若其中B-1b0，则称以上的基解为基可行解相应的基B称为可行基若在基解中出现基变量为0的情况，称为退化解称为线性规划与基B对应的基解可行解基解基最优解基可行解线性规划问题的性质性质1：线性规划的可行域是凸集。性质2：线性规划的基可行解x对应于可行域的顶点。性质3：线性规划的最优解在极点上。4.线性规划的求解方法图解法单纯形法图解法几种情形(a)可行域有界唯一最优解(b)可行域有界多个最优解(c)可行域无界唯一最优解(d)可行域无界多个最优解(e)可行域无界目标函数无界(f)可行域为空集无可行解O123123xx21ABCDx3=0x4=0x2=0x1=0可行域(可行解全体)基可行解(可行域顶点、极点)基解2.单纯形法从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解，每次转换要使新的基可行解对应的目标函数比前一次的要优，直到目标函数达到最优解。基本思想用单纯形法求解如下线性规划问题：12121212max235156224,0zxxxxxxxx单纯型法的基本步骤1.化标准形，找到初始可行基，确定初始可行解，建立初始单纯形表。对于“≤”的约束，左边+松弛变量=右边2.检验各非基变量xj的检验数。若≤0，则已达到最优，停止。否则转第3步。miijijjacc1j4.以alk为主元素进行矩阵的行变换，使Pk变换为第l行的元素为1，其余的为0，并将XB列中的xl换成xk，重复进行2-4步，直到终止。3.换入变量和换出变量的确定换入变量：max{σj0}=σk,确定xk为换入变量；换出变量：，确定xl为换出变量。lklikikiabaab}0|min{“≥，＝”情况变标准型：对于“≥”的约束，左边-剩余变量+人工变量=右边对于“=”的约束，左边+人工变量=右边0,,12324112..332131321321321xxxxxxxxxxxtsxxxZMin1,2,...,7012324112..0037316532143217654321jxxxxxxxxxxxxxtsMxMxxxxxxZMaxj2．两阶段法第一阶段：不考虑原有问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化．0,,12324112..332131321321321xxxxxxxxxxxtsxxxZMin1,2,...,7012324112..73165321432176jxxxxxxxxxxxxxtsxxwMinjcj０００00-１-１cBxBbx1x2x3x4x5x6x7θi0-1-1x4x6x711311-211000-4120-110-2010001113/21Z-4-6130-100x3换入，x7换出1,2,...,7012324112..'73165321432176jxxxxxxxxxxxxxtsxxwMaxj第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表．（通常一步计算结束）cj3-1-100cBxBbx1x2x3x4x5θi0-1-1x4x2x312113001-20100-1-201004--cj-zj1000-1x1换入，x4换出PP45,1.6题（2）采用两阶段法求解如下线性规划问题：12312312123min234283210,,0zxxxxxxxxxxxTmnmTnbbbcccyyyxxx),,,(),,,(),,,(),,,(21212121bCYX上两式中mnmmnnaaaaaaaaaA2122221112110XbAXCX..)(max:tsxf原问题0YCYAYb..)(min:tsyg对偶问题5.对偶理论的一个基解。验数行对应其对偶问题则原问题单纯形表的检它的对偶问题是设原问题是0min0maxSSSSC;Y,YYYb,YAwb;X,XXCX,AXZ定理7-Y-YYB-CNB-CCXXXSS-B-BNSNB021115.对偶单纯形法043232..432min321321321321xxxxxxxxxtsxxxw043232..432max5432153214321321xxxxxxxxxxxxxtsxxxz043232..432max5432153214321321xxxxxxxxxxxxxtsxxxzcj-2-3-400CBXBbx1x2x3x4x50x40x5-3-4-1-2-110-21-301Ｚ０-2-3-400检查b列的数字，若至少还有一个负分量，检验数保持非正，则选取最小的b负分量为换出变量。rkkkrjrjjjyzcyyzc0|min1}34,,22min{x1为换入变量cj-2-3-400CBXBbx1x2x3x4x50x40x5-3-4-1-2-110-21-301Ｚ-2-3-400对偶单纯形法的基本思想1.对偶单纯形法是运用对偶原理来求解原问题的一种方法，而不是求解对偶问题的单纯形法。2.单纯形法是从一个原始问题的基本可行解转到另一个基本可行解，在迭代过程中保持原问题的可行性，即检验数从有0开始逐步变为为止。0bj03.对偶单纯形法则是保持对偶问题是基本可行解（所有的检验数），而原问题在非可行解（）的基础上通过逐步迭代达到基本可行解（）。这样，同时达到原问题和对偶问题的最优解。00b0b对偶单纯形法的优点和缺陷1.初始解可以是非可行解，只要检验数全部非负时就可以进行基变换，不需要引入人工变量。j2.如果原问题约束很多，而变量很少，则可以把原问题变成对偶问题，再用对偶单纯形法求解，减少工作量。3.灵敏度分析中有时要用到对偶单纯形法，使问题简化。优点：缺点：1.对于大多数的线性规划问题，很难找到对偶问题的一个初始可行基，即很难满足所有的，因此该方法很少单独使用。0j※资源数量bi的改变※目标函数系数cj的改变※技术系数aij的改变灵敏度分析※资源数量bi的改变rrrbbb')(''11bbBbBXBTrbb)0,...,0,,...,0(其中变，则最优基不变。而且最终表中检验数不只要,0'BX0,124164)12(82..32max21212121xxxxxxtsxxz※目标函数系数cj的改变1.若cj是非基变量xj的系数，这时它在计算表中所对应的判别数jPBCcBjj1jjjccc'01jPBCccBjjj2.若cr是基变量xr的系数，这时它在计算表中所对应的判别数0)('11rjrjrjrBjBBjjacacPBCcPBCCcjj0)(0)(rjarrjarabacrjjrjj6.灵敏度分析什么是灵敏度分析？1.当发生变化时，对已求得的线性规划问题的最优解的影响。研究系数在什么样的范围内变化，原最优基仍然是最优的。jiijcba,,2.若原最优基不再是最优的，如何用最简便的方法来找到新的最优解。3.当线性规划问题增加一个新的变量或新的约束，如何在