1、1对偶理论与灵敏度分析对偶理论与灵敏度分析1 1 单纯形法的矩阵描述单纯形法的矩阵描述 设max z=CX AX=b X 0 A为mn阶矩阵 RankA=m,取B为可行基,N为非基，NBNBCCCNBAXXX ,0,maxNBNBNNBBXXbNXBXXCXCz2bBCbBNBIBN111-1 0 0 :矩阵单纯形表0zXCXCbNXBXNNBBNBbBCzXNBCCXbBNXBBXBBNBNBNB11111)(0bBCzXXbBNXBIXBNNBNB11103bBCzXXbBNXBIXBNNBNB1110NBCCbBCzbBXXBNNBBN111 ,0 得令.,0 !出则最优解直接由上式求若
2、能找到最优为最优基的使注BBNbBCzbBXB11 0 目标函数基可行解4求解步骤：.42 .,.4.,)()(0)()()(min ,)(0)(max .3.,0.2,.111111111步直到求出结果重复的求出此得到新的出基行对应的则若入基则若基变换否则转下一步则得最优解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklikikiikkNjNjBNN532利润12kg40材料B16kg04材料A8台时 21设备台时限制 2 2 对偶问题的提出对偶问题的提出 eg.1 制定生产计划 M1:max z=2x1+3x2 1x1+2x2 8 4x1 16 4x2 12 x1，x2 0
3、 6 现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B转让附加费(kg-1)则M2为M1的对偶问题，反之亦然。M2:min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y3 3 y1,y2,y3 032利润12kg40材料B16kg04材料A8台时 21设备台时限制 0,124 16 482 32max 212121211xxxxxxxxzM7 一般的，原问题：max z=CX AX b X 0 对偶问题：min w=Yb YA C Y 0 比较：max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “”“”83 3 对偶问题的化
4、法对偶问题的化法 1、典型情况 eg.2 max z=x1+2x2+x3 2x1+x2 6 2x2+x3 8 x1,x2,x3 0对偶：min w=6y1+8y2 2y1 1 y1+2y2 2 y2 1 y1,y2 09 2、含等式的情况 eg.3 max z=x1+2x2+4x3 2x1+x2+3x3=3 x1+2x2+5x3 4 x1,x2,x3 0对偶：min w=3y1-3y1”+4y2 2y1-2y1”+y2 1 y1-y1”+2y2 2 3y1-3y1”+5y2 4 y1,y1”,y2 0令y1=y1-y1”,则：min w=3y1+4y2 2y1+y2 1 y1+2y2 2 3y
5、1+5y2 4 y2 0，y1无约束一般，原问题第i个约束取等式，对偶问题第i个变量无约束。2x1+x2+3x3 3-2x1-x2-3x3-310 3、含“”的max问题 eg.4 max z=x1+2x2+4x3 2x1+x2+3x3 3 x1+2x2+5x3 4 x1,x2,x3 0对偶：min w=-3y1+4y2 -2y1+y2 1 -y1+2y2 2 -3y1+5y2 4 y1,y2 0令y1=-y1，则：min w=3y1+4y2 2y1+y2 1 y1+2y2 2 3y1+5y2 4 y1 0,y2 0-2x1-x2-3x3-311一般:max问题第i个约束取“”，则min问题第
6、i个变量 0；min问题第i个约束取“”，则max问题第i个变量 0；原问题第i个约束取等式，对偶问题第i个变量 无约束；max问题第j个变量 0,则min问题第j个约束取“”；min问题第j个变量 0，则max问题第j个约束取“”；原问题第j个变量无约束，对偶问题第j个约束取等式。约束条件符号判断：约束条件符号判断：max-min相同，min-max相反决策变量符号判断：决策变量符号判断：max-min相反，min-max相同12 eg.5 min z=2x1+3x2-5x3+x4 x1+x2-3x3 +x4 5 2x1 +2x3-x4 4 x2+x3+x4=6 x1 0,x2,x3 0,x
7、4无约束对偶：max w=5y1+4y2+6y3 y1+y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1-y2+y3=1 y1 0,y2 0,y3无约束 13对偶问题的基本性质一、单纯形法计算的矩阵描述Max Z=CX AXb X0其中X(x1,x2xn)TMax Z=CX+0Xs AX+IXs=b X,Xs0其中Xs(xn+1,xn+2xn+m)TI 为mm的单位矩阵14 项目非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0 项目基变量非基变量XBXNXsCBXBB-1 bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵I，迭代
8、后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）（B，N，I），迭代后为（B-1B，B-1N，B-1I）（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。15maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5x25 y1,y20y1y2x1x2maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0minw=24y1+40y
9、2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40y1y2x1x216cj4.5500CBXBbx1x2x3x40 x3243210120 x44045018cj-zj4.55000 x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7Z=4.540/7524/7=300/7解原问题：17解对偶问题：w=245/14406/7=300/7cj244000CBYBby1y2y3y424y15/1410-5/74/740y26
10、/7012/7-3/7cj-zj0040/724/718cj4.5500CBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000CBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x3原问题对偶问题19二、对偶问题的基本性质原始问题max z=CXs.t.AXb X 0对偶问题min w=Ybs.t.ATYCY 01.弱对偶性若X为原问题的可行解，Y为对
11、偶问题的可行解，则恒有CXYb20推论：原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界 若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。212.最优性若X为原问题的可行解，Y为对偶问题的可行解，且CXYb则X，Y分别为原问题和对偶问题的最优解。3.强对偶性若原问题和对偶问题均具有可行解，则两者均具有最
12、优解，且他们的最优解的目标值相等。224.互补松弛定理在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为0，则该约束条件取严格等式，既松弛变量或剩余变量为0；反之如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格不等式，既松弛变量或剩余变量不为0.若yi 0,即xsi=0若yi 0,即xsi0即xsiyi=0同理若xj 0,即ysj=0若xj 0,即ysj0即ysjxj=023maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0y1y2minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1
13、+5x2-y4=5 y1,y2,y3,y40 x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/724利用互补松弛关系求解线性规划min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20原始问题对偶问题0 1 2 3 4 5 6 7 8654321w1w2y=-1 y=1y=3y=6最优解为(y1,y2)=(6,0)max y=6先
14、用图解法求解对偶问题。25min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20max w=y1-y2s.t.y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1,y2,y3,y4,y50(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)min z=6x1+8x2+3x3s.t.x1+x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1,x2,x3,x4,x50(x1,x2,x3|x4,x5)(y1,
15、y2|y3,y4,y5)x2=x3=x4=0 x1=1,x5=2引进剩余变量 求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)264 4 对偶问题的性质对偶问题的性质 1、对称性 对偶问题的对偶为原问题.0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 ,min 0 ,maxYCYAYbwXbAXCXz270)min(XbAXCXw证毕令0 max maxmax)min(XbAXCXzwzCXwww28.,:的可行解分别为原问题和对问题设证明YXXCXAYCAY
16、CYAbYXAYbXAbAX证毕bYXCbYXAYXC bYXC 则存在,为对偶问题的可行解Y,为原问题的可行解X设偶性弱2.对29推论：(1)max问题任一可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。30 4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时，X*，Y*分别为最优解。证毕为最优解即为最优解即由弱对偶性题的任一可行解分别为原问题和对
17、偶问设证明 *)2()1(.,:*YbYbYbYCXbYXCXXCCXbYXCYX31 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。*11*1*1*1*11*0)(:,0.:wbYbBCbBCCCXzbBXbBCbYwYBCYCAYCABCABCCXBNBBBBB则其目标值为因原问题最优解则为对偶问题的可行解若其中全部检验数可表示为则其对应的基矩阵存在为原问题的最优解设证明32Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。证明：0
18、,0max:SSSXXbXAXXCXz设原问题为0,0min:SSSYYCYYAYYbw设对偶问题为330,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYbw)(将b,Cb,C分别代入目标函数：;,0,0,*为最优解时当为可行解若YXzwXYXYYXSS证毕必有则分别为最优解若另一方面0 ,0,*SSXYXYzwYX34TSmSSSTnxxxXxxxX)()(*2*1*2*1*)()(*2*1*2*1*snSSSmyyyYyyyY 其中：用分量表示：mixynjxySiijSj,2,1 ,0;,2,1 ,0*35
19、 7、检验数与解的关系 (1)原问题非最优检验数的负值为对偶问题的一个基解。(2)原问题最优检验数的负值为对偶问题的最优解。分析：max z=CX+0Xs=(C 0)(X Xs)T AX+Xs=b X,Xs 0 min w=Yb+YS0 YA-Ys=C Y,Ys 0 检验数：=(C 0)-CBB-1(A I)=(C-CBB-1A -CBB-1)=(c s)c=C-CBB-1A X对应的检验数 s=-CBB-1 Xs对应的检验数 36 eg.6 已知：min w=20y1+20y2 的最优解为y1*=1.2,y2*=0.2-ys1 y1+2y2 1 试用松弛性求对偶-ys2 2y1+y2 2 问
20、题的最优解。-ys3 2y1+3y2 3 -ys4 3y1+2y2 4 y1,y2 0 解：对偶问题 max z=x1+2x2+3x3+4x4 x1+2x2+2x3+3x4 20 +xs1 2x1+x2+3x3+2x4 20 +xs2 x1,x2,x3,x4 0 y1*xs1*=0 y2*xs2*=0 ys1*x1*=0 ys2*x2*=0 ys3*x3*=0 ys4*x4*=037 y1*=1.2,y2*0.2 0 xs1*=xs2*=0 由 y1*+2y2*=1.6 1 ys1*0 x1*=0 由 2y1*+y2*=2.6 2 ys2*0 x2*=0 由 2y1*+3y2*=3=右边 ys
21、3*=0 x3*待定 由 3y1*+2y2*=4=右边 ys4*=0 x4*待定 有 2x3*+3x4*=20 3x3*+2x4*=20 x3*=4 x4*=4 最优解：x1*=0 x2*=0 x3*=4 x4*=4 xs1*=0 xs2*=0 最大值：z*=28=w*385 5 对偶问题的经济含义对偶问题的经济含义影子价格影子价格 最优情况：z*=w*=b1y1*+biyi*+bmym*的影子价格为称i*i*ibzbyyi*x2x1Q2 eg.7 max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1,x2 0b1：8 9 Q2(4，2.5)z*=15.5 z*=z*
22、-z*=3/2=y1*b2：16 17 Q2”(4.25，1.875)z*”=14.125 z*=z*”-z*=1/8=y2*b3：12 13 z*=0=y3*Q2Q2”396 6 对偶单纯形法对偶单纯形法 单纯形法：由 XB=B-1b 0，使j 0，j=1,m对偶单纯形法：由j 0(j=1,n)，使XB=B-1b 0 步骤：步骤：(1)保持j 0，j=1,n，确定XB，建立计算表格；(2)判别XB=B-1b 0是否成立？若成立，XB为最优基变量；若不成立，转(3)；40(4)消元运算，得到新的XB。(3)基变换 出基变量，出基；，则若lliiixmibbb,10min入基变量，入基。则若ka
23、ljajxalkkljj0min重复（2）-（4）步，求出结果。41 eg.8 用对偶单纯形法求解 min w=2x1+3x2+4x3 x1+2x2+x3 1 2x1-x2+3x3 4 x1,x2,x3 0解：max z=-2x1-3x2-4x3+0 x4+0 x5 -x1-2x2-x3+x4 =-1 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 042-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：最优解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目标值：目标值：w*=-z*=443对偶单纯形法练习
24、：0,1252652415min32132132321yyyyyyyyyyyw44复习：1、写出如下问题的对偶问题无约束321321321321321,0,022122maxxxxxxxxxxxxxxxxz约束条件符号判断：约束条件符号判断：max-minmax-min相同，相同，min-maxmin-max相反相反决策变量符号判断：决策变量符号判断：max-minmax-min相反，相反，min-maxmin-max相同相同45复习：2、用对偶单纯形法求解线性规划问题10,5223318124min3213231321xxxxxxxxxxz467 7 灵敏度分析灵敏度分析njpBCcABCC
25、NBCCjBjjBBNN,2,1,0 0 0 :111 或或最优性条件分析 变化对最优解的影响。j ,ijiacb0 :1bBXB可行性条件47的变化资源ib 1.7TiTmiiiibbbbbbbbbbbb)0b 0 0()(21 bBbBbbBbBXB1111)(.,0 11这里用到可行性条件保持问题的最优性不变的变化范围求出由ibbBbB48例1 已知下述问题的最优解及最优单纯形表,0,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz.,)12使最优基不变的变化范围求 b.4 )21时的最优解求b49最优单纯形表如下:0-1/8-
26、3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此时5022216 1):bbb解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最优单纯形表得:51221118/12/14/12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最优基不变b52TTbb)0 0 4()0 0 ()214 44 28024400408/12/11
27、2/1204/10244)(111bBbBbbB不可行!用对偶单纯形法计算53-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 :.0,0,2,3,4 :*5*4*3*2*1元目标值最优解zxxxxx54如下题：（1）若 增大到32，试分析最优性的变化。（2）请分析 在什么范围内变化，问题的最优基不变。最优单纯形表：0,524261550002max543215214213254
28、321xxxxxxxxxxxxxxxxxxz-1/2-1/40003/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30 x5x4x3x2x1b基CB00012x23b2b55的变化价值系数jc 2.7.01分两种情况讨论进行分析根据最优性条件NBCCBNN的变化非基变量价值系数kc.1kBkkpBCc1:原检验数/:kkkkkccccc变化kkkBkkkcpBCcc1/.,0 :/此时最优解不变令kkkkkcc56例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12i
29、x5x4x3x2x1bXBCB00032x204c8/1)8/1(8/1444c由解:.8/1 4时最优解不变即c57的变化基变量价值系数rc.2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/)(则分析:)0 0 0()(:21 rBmrBcCccccC其中.变化影响所有可见jrc58方法:.0 1/的变化范围求出令rBNNcNBC例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2592C解:0-1/8-3/2000
30、-1/81/21023+11/2-2004x5001/40014x12ix5x4x3x2x1bXBCB0003+2x2)0 0(),3 0 2(2cCCBB 1/8)-(-3/2)(43N)(/4/3/n44414/433313/3pcpBcpcpBcBBBB2C6002232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc.13 2时最优解不变即c61 当目标函数中cj发生变化，将影响最终单纯形表非基变量的检验数。如果是非基变量的价值系数发生变化，只影响该非基变量的检验数，如果变化后的检验数仍然小于等于0，则最优解不变
31、；如果是基变量的价值系数发生变化，将影响所有非基变量的检验数，只有当所有的非基变量检验数都仍然小于等于0，最优解才不变。62如下题：（1）若c1变为1.5，c2变为2，试分析最优性的变化。（2）请确定c2变化范围，使问题最优性不变。最优单纯形表：0,524261550002max543215214213254321xxxxxxxxxxxxxxxxxxz-1/2-1/40003/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30 x5x4x3x2x1b基CB00012x263的变化技术系数jia 3.7kBkkpBCc1 原T1k k k 0)a 0()
32、(,lkkTmklkkkkkklllpaaappppaaaa若分析:.k 的变化讨论非基变量技术系数la64lklkakBkBkkkBkKpBCpBCcppBCc111 )(则TlkmlkkBkapBC)00)(11 0lklkka令.,最优解不变时当lkkla65 例5 在例1的基础上，企业要增加一个新产品,每件产品需2个台时，原材料A 6kg，原材料B 3kg，利润 5元/件，问如何安排各产品的产量，使利润最大？解：0,1234 1664 822 532max3213231321321xxxxxxxxxxxxxz532利润12340料B16604料A8221设备b则有为新产品生产的件数设,
33、3x66313p )2pB计算25.025.136208/12/112/1204/1031pB0453620 81 2353133pBCcB3 )1计算表明生产新品有利。67.,)3331加入原最优表计算将pB2 ,53出基主元为入基 xx5/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix3685/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix320-5/8-
34、7/16-1/4000-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix3x35)(5.2 )(5.16 .2 ,2/3 ,1*3*2*1元增加元zxxx69如下题：若式中x2变为8、4、1，产品利润变为3，试分析最优性的变化。最优单纯形表：0,524261550002max543215214213254321xxxxxxxxxxxxxxxxxxz-1/2-1/40003/2-1/40103/21-1/21/40017/2x12-15/25/410015/2x30 x5x4x3x2x1b基CB000
35、12x270小结0 maxXbAXCXz1、对偶问题及其化法0 minYCYAYbw原问题决策变量决定对偶问题约束条件关系原问题约束条件决定对偶问题决策变量取值方向。712、检验数的计算方法njpCcpBCcjBjjBjj,2,1 ,1 或NBCCBNN1 ABCCB1 或阶矩阵阶矩阵:,:1mmBmnnmAjjpBp1723、对偶问题的性质4、对偶单纯形法弱对偶性无界性最优性松弛性检验数与对偶问题的解73对偶单纯形法的特点：当约束条件为“”时，不需要引入人工变量，从而使计算更为简便。用对偶单纯形法求解时，目标函数必须是求极大化的。74步骤：1.确定初始解一般设松弛变量为初时基可行解2.判断
36、若所有的基变量值均0，则此解为线性规划问题的最优解，若存在基变量的值0，则问题还没有达到最优解，需要进行改进。3.改进选择换出变量min bi/bi0假设选取xk为换出变量选择换入变量min(cj-zj)/arj|arj0,cj-zj0则假设选取xl为换出变量4.迭代。使得alk1，其余aik为075Minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30举例：Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3-4 -6y1-3y2-5y3-10 y1,y2,y30Maxw=-5y1-2y2-4y3 s.t.-3y1-y2
37、-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi0(i=1,2,5)76cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/3-5y12/3101/311/3-2y220112-1cj-zj00-1/3-1-1/3此时对偶问题和原问题都达到可行，所以均达到了最优解Y（2/3.2,0,0,0)W=-22/3W=22/3775、灵敏度分析前提条件:原线性规划问题已取得了最优解；每
38、次只讨论一种参数的变化，而参数之间的变化互不关联。78njpBCcjBjj,2,1,01 变化对最优解的影响分析ijjiacb,0 :1NBCCBNN最优性条件0 1ABCCB0 :1bBXB可行性条件常用公式：mijBjiijjjjjjPBCcyaczcPBPbBb11*11)(79的变化技术系数jia )3(的变化价值系数jc )2(的变化资源ib )1(80目标函数：max z=2x1+3x2约束条件：x1+2x2 8 4x1 16 4x2 12 x1，x2 02x1410000 x5400-213x2201-1/8000-3/2-1/8081第一二章总结线性规划问题的引出线性规划的一般模型线性规划的标准形式单纯形法的原理单纯形法大M法和两阶段法82对偶问题的提出根据原问题写对偶问题对偶问题的基本性质对偶单纯形表灵敏度分析83课后题复习原问题对偶问题关系84课后题复习对偶理论及性质85课后题复习两种单纯形法区别86课后题复习对偶单纯形法计算步骤87课后题复习灵敏度分析
