对偶理论和灵敏度分析(新).ppt

1,对偶理论和灵敏度分析,对偶的定义原始对偶关系目标函数值之间的关系最优解之间的互补松弛关系对偶问题的性质对偶的经济解释对偶单纯形法灵敏度分析,DUAL,2,第3节 线性规划对偶问题的提出,现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润为最大？,3,解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：,maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则问题变成对于甲乙两种原材料企业以多少最低价愿意出让？,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y20,4,第4节 线性规划的对偶理论对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“号。则称这些线性规划问题具有对称性。,max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0,min w=b1y1+b2y2+bmyms.t.a11y1+a21y2+am1ym c1 a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1,y2,ym 0,Max Z=CX s.t.AXb X0,Minw=Yb s.t.AYC Y0,5,原始问题max z=CXs.t.AXb X 0,对偶问题min w=Ybs.t.AYCY 0,max,b,A,C,C,AT,b,min,m,n,m,n,4.1原问题与对偶问题的关系,6,举例：,maxZ=3x1+2x2 s.t.-x1+2x24 3x1+2x214 x1-x2 3 x1,x20,minw=4y1+14y2+y3 s.t.-y1+3y2+y33 2y1+2x2-y32 y1,y2,y30,y1,y2,y3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x1,x2,7,原始问题为min z=2x1+3x2-x3s.t.x1+2x2+x36 2x1-3x2+2x39 x1,x2,x30,根据定义，对偶问题为max y=6y1+9y2s.t.y1+2y22 2y1-3y23 y1+2y2-1 y1,y20,原始问题是极小化问题原始问题的约束全为原始问题有3个变量，2个约束原始问题的变量全部为非负,对偶问题是极大化问题对偶问题的约束全为对偶问题有2个变量，3个约束原始问题的变量全部为非负,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)原始问题约束条件的个数(2)等于对偶问题变量的个数(2),8,非对称形式的原对偶问题,minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1+2x3-x44 x2+x3+x4=6 x10,x2,x30,x2+x3+x46x2+x3+x46,-x1=x1，x10;x4-x4”=x4,x4 0,x4”0,minz=-2x1+3x2-5x3+(x4-x4”)1+x2-3x3+(x4-x4”)5 2x1-2x3+(x4-x4”)-4 x2+x3+(x4-x4”)6-x2-x3-(x4-x4”)-6 x1,x2,x3,x4,x4”0,y1,y2,y3,y3”,maxw=5y1-4y2+6(y3-y3”)1+2y2-2 y1+(y3-y3”)3-3y1-2y2+(y3-y3”)-5 y1+y2+(y3-y3”)1-y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0,9,maxw=5y1-4y2+6(y3-y3”)1+2y2-2 y1+(y3-y3”)3-3y1-2y2+(y3-y3”)-5 y1+y2+(y3-y3”)1-y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0,设y2=-y2,y3=y3-y3”,则y20,y3无约束此时对偶问题变为,maxw=5y1+4y2+6y3 s.t.y1+2y2 2 y1+y3 3-3y1+2y2+y3-5 y1-y2+y3=1 y10,y20,y3无约束,minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1+2x3-x4 4 x2+x3+x4=6 x10,x2,x30,10,原 始 对 偶 表,11,对偶关系,1、极大与极小的对偶2、价值系数与资源系数的对偶3、约束条件系数矩阵的对偶是矩阵的转置4、反向不等式与非正的决策变量的对偶5、等式与非负限制的决策变量的对偶6、最优解与检验数的对偶,12,min z=2x1+4x2-x3s.t.3x1-x2+2x3 6-x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max y=6w1+12w2+8w3+15w4s.t.3w1-w2+2w3+w4 2-w1+2w2+w3+3w4 4 2w1-3w2+2w3-w4-1 w1 0,w2,w3 0,w4 0,=,Free,=,x10,x20,x3:Free,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（1）,13,写对偶问题的练习（2）,原始问题,max z=2x1-x2+3x3-2x4s.t.x1+3x2-2x3+x412-2x1+x2-3x48 3x1-4x2+5x3-x4=15 x10,x2:Free,x30,x40,min y=12w1+8w2+15w3s.t.w1-2w2+3w32 3w1+w2-4w3=-1-2w1+5w33 w1-3w2-w3-2 w10,w20,w3:Free,对偶问题,14,maxZ=x1-2x2+3x3 s.t.2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1,x30,练习,minw=100y1+200y2+150y3 s.t.2y1+3y2+5y31 4y1-2y2+3y3=-2 3y1+6y2+4y33 y10,y20,minZ=2x1+2x2+4x3 s.t.x1+3x2+4x32 2x1+x2+3x33 x1+4x2+3x3=5 x1 0,x20,maxw=2y1+3y2+5y3 s.t.y1+2y2+y32 3y1+y2+4y3 2 4y1+3y2+3y34 y10,y20,15,原始和对偶问题可行解目标函数值比较,min z=2x1+3x2s.t.x1+3x23 2x1+x2 4 x1,x2 0,max w=3y1+4y2s.t.y1+2y22 3y1+y2 3 y1,y2 0,16,单纯形法计算的矩阵描述,Max Z=CX AXb X0其中X(x1,x2xn)T,Max Z=CX+0Xs AX+IXs=b X,Xs0其中Xs(xn+1,xn+2xn+m)TI 为mm的单位矩阵,17,对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为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。,18,当B为最优基时，XB为最优解时，则有：,CN-CBB-1N0,-CBB-10,CB-CBI=0,代入得：CNCBB-1N+CB-CBI0CCBB-1(B+N)0,整理得：CCBB-1 A0-CBB-10,令CBB-1为单纯形乘子，YCBB-1,则：CY A0-Y0,Y AC Y 0,WYb=CBB-1b=Z,所以当原问题为最优解时，对偶问题为可行解且具有相同的目标函数值。,19,maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y20,y1,y2,x1,x2,maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0,minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5Y2-y4=5 y1,y2,y3,y40,20,解原问题：,21,22,23,Z=4.540/7524/7=300/7,24,解对偶问题：,w=245/14406/7=300/7,25,(x3,x4)=(0,0),(y3,y4)=(0,0),-y1,-y2,-y4,-y3,x1,x2,x4,x3,26,（1）对称性：对偶问题的对偶,max z=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20,minw=2y1+3y2-y3s.t.y1+2y2+y36 2y1-3y2+2y39 y1,y2,y30,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。,max u=6w1+9w2s.t.w1+2w22 2w1-3w23 w1+2w2-1 w1,w20,4.2对偶问题的基本性质,27,maxZ=x1+4x2+2x3 s.t.5x1-x2+2x38 x1+3x2-3x35 x1,x2,x30,minw=8y1+5y2 s.t.5y1+y21-y1+3y24 2y1-3y2 2 y1,y20,28,4.2 对偶问题的基本性质,原始问题max z=CXs.t.AXb X 0,对偶问题min w=Ybs.t.AYCY 0,（2）弱对偶性若X为原问题的可行解，Y为对偶问题的可行解，则恒有CXYb,29,推论：原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。（3）无界性 如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。推论：若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界 若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。,30,maxZ=x1+x2 s.t.-x1+x2+x3 2-2x1+x2+x3 1 x1,x2,x3,0,minw=2y1+y2 s.t.-y1-2y2 1 y1+y2 1 y1-y2 0 y1,y20,试用对偶理论证明上述线性规划问题无最优解,例。已知线性规划问题,证：首先该问题存在可行解。,可知对偶问题无可行解，因原问题有可行解，故无最优解。,31,（4）最优性若X为原问题的可行解，Y为对偶问题的可行解，且CXYb则X，Y分别为原问题和对偶问题的最优解。,（5）强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。,32,（6）互补松弛定理在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为0，则该约束条件取严格等式，既松弛变量或剩余变量为0；反之如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格不等式，既松弛变量或剩余变量不为0.,若yi 0,则aijxj=bi，即xsi=0若yi 0,则aijxjbi，即xsi0即xsiyi=0,同理若xj 0,则aijyi=cj，即ysj=0若xj 0,则aijyicj，即ysj0即ysjxj=0,33,maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0,minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40,X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7,y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/7,34,利用互补松弛关系求解线性规划,min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0,max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20,原始问题,对偶问题,最优解为(y1,y2)=(6,0)max y=6,先用图解法求解对偶问题。,35,min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0,max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20,max 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,y2|y3,y4,y5),x2=x3=x4=0,x1=1,x5=2,(x1,x2,x3,x4,x5)=(1,0,0,0,2),36,第5节 对偶问题的经济解释资源的影子价格(Shadow Price),影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,yi=w/bi=最大利润的增量/第i种资源的增量=第i种资源的边际利润,w=b1y1+b2y2+biyi+bmym,w+w=b1y1+b2y2+(bi+bi)yi+bmym,w=biyi,37,Z*=8.5X=(7/2,3/2),Z*=8.75X=(15/4,5/4),Z=9X=(3,3),maxZ=2x1+x2 s.t.2x215 6x1+2x224 x1+x25 x1,x20,思考:如果第一种资源增加1，也就是把15变为16,目标函数值将怎么变化?为什么?,38,资源的影子价格是一种机会成本根据互补松弛定理,若yi 0,则aijxj=bi，若yi 0,则aijxjbi，,某种资源bi未得到充分利用时，该种资源的影子价格为0；当资源的影子价格不为0，表示该种资源在生产中已消耗完毕。,j=cj-zj=cj-CBB-1Pjcj表示第i种产品的产值，aijyi表示生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。,39,Maxz=4x1+10 x2 s.t.3x1+6x25 x1+3x22 2x1+5x24 x1,x20,已知原问题为：,则对偶问题为：,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30,Maxz=4x1+10 x2 s.t.3x1+6x2+x3=5 x1+3x2+x4=2 2x1+5x2+x5=4 xj0(j=1,2,5),Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),40,初始单纯形表为：,此时对偶问题的解为Y（0，0，0，4，10）代入,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),不是对偶问题的可行解,41,初始单纯形表为：,此时对偶问题的解为Y（0，0，0，4，10）代入,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),不是对偶问题的可行解,42,对原问题进行迭代得：,此时对偶问题的解为Y（0，10/3，0，-2/3，0）代入,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),不是对偶问题的可行解,43,对原问题进行迭代得：,此时对偶问题的解为Y（0，10/3，0，-2/3，0）代入,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),不是对偶问题的可行解,44,对原问题进行迭代得：,此时对偶问题的解为Y（2/3，2，0，0，0）代入,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),是对偶问题的可行解,45,单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。,46,第6节 对偶单纯形法,对于对偶单纯形法刚好和单纯形法的思路相反，就是在始终保持对偶问题可行的条件下，不断改进原问题可行性的过程。一个从原问题不可行的解，经过几次叠代，逐步向原问题可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。,47,步骤：1.确定初始解一般设松弛变量为初时基可行解2.判断 若所有的基变量值均0，则此解为线性规划问题的最优解，若存在基变量的值0，则问题还没有达到最优解，需要进行改进。3.改进选择换出变量min bi/bi0假设选取xk为换出变量选择换入变量min(cj-zj)arj|arj0,cj-zj0则假设选取xl为换出变量4.迭代。使得alk1，其余aik为0,48,Minw=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,y30,Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3+y4=4-6y1-3y2-5y3+y5=10 yi0(i=1,2,5),49,50,51,52,53,54,55,56,57,58,此时对偶问题和原问题都达到可行，所以均达到了最优解Y（2/3.2,0,0,0)W=-22/3W=22/3,59,Minw=2x1+3x2+4x3 s.t.x1+2x2+x33 2x1-x2+3x34 x1,x2,x30,练习:用对偶单纯形法求解并求出对偶变量的最优解,Maxw=-2x1-3x2-4x3 s.t.-x1-2x2-x3-3-2x1+x2-3x3-4 x1,x2,x30,Maxw=-2x1-3x2-4x3 s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4 xi0(i=1,2,5),60,此时对偶问题和原问题都达到可行，所以均达到了最优解Y（11/5.2/5,0,0,0)W=-28/5W=28/5,61,Maxz=3y1+4y2 s.t.y1+2y22 2y1-y23 y1+3y24 y1,y20,Maxz=3y1+2y2 s.t.y1+2y2+y32 2y1-y2+y43 y1+3y2+y54 yi0,62,对偶单纯形法的特点：当约束条件为“”时，不需要引入人工变量，从而使计算更为简便。用对偶单纯形法求解时，目标函数必须是求极大化的。,63,Maxz=3x1-4x2 s.t.x1+2x22 3x1+x24 x1-x21 x1+x23 x1,x20,Maxz=3x1-4x2 s.t.-x1-2x2-2-3x1-x2-4 x1-x21 x1+x23 x1,x20,Maxz=3x1-4x2 s.t.-x1-2x2+x3=-2-3x1-x2+x4=-4 x1-x2+x5=1 x1+x2+x6=3 xj0,64,可以看出，这时候原问题和对偶问题都不可行,列出初始单纯形表：,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,此时对偶问题和原问题都达到可行，所以均达到了最优解X（4/3.1/3,0,1/3,0,4/3)Z=8/3,84,第7节 灵敏度分析,前提条件:原线性规划问题已取得了最优解；每次只讨论一种参数的变化，而参数之间的变化互不关联。,85,某厂准备用甲乙两种原料生产A，B，C，D四种产品，相关参数见表。问如何安排生产总利润为最大。,Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x418 2x3+1/2x43 xj0(j=1,2,3,4),Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x4+x5=18 2x3+1/2x4+x6=3 xj0(j=1,2,6),86,用单纯形法对该线性规划进行求解，得初始单纯行表和最优单纯形表,Z*=88,-y1,-y2,-y3,-y4,-y5,-y6,87,7.1资源系数（右端常数项bi）发生变化的分析X=(XB,0)T其中XB=B-1bZ=CBB-1b当bi 发生变化时：bi=b+(0,bi,0)T=b+b则:XB=B-1b=B-1(b+b)=B-1b+B-1bXB+B-1b如果XB=XB+B-1b0，则原最终单纯形表中的基变量不变，基变量的值将发生变化如果XB=XB+B-1b0，则需采用对偶单纯形表进行重新求解。,88,假设：甲原材料的供给量从18变为6，则b=(6,3)T,可以看出甲的供给量发生变化后，x4的值=-40，所以用对偶单纯形表求新解。,89,90,91,92,93,94,当右端常数项发生变化时，主要考虑在最优单纯行表中基变量的值是否仍然大于等于0，如果仍然大于等于0，则线性规划问题的基变量不变，但是基变量的值将发生变化；如果右端常数项发生变化时，最优单纯行表中基变量的值小于0，则将用对偶单纯形法对原最优单纯形表进行继续求解。,95,7.2目标函数中cj发生变化的分析1.非基变量的cj发生变化x1的利润值由9变为9+c1则：1=9+c1-219+25=-4+c1如果1=-4+c10，最优解不发生变化；1=-4+c10，最优解将发生变化。所以当c1 4时，最优解不发生变化。对于某一非基变量可以看出，它的价值系数发生变化时，只影响最优单纯行表中该非基变量的检验数，而基变量的检验数都不会发生变化，所以只需要考虑该非基变量的价值系数变化后的检验数是否仍然小于等于0，如果仍然小于等于0，则最优解不发生变化。,96,思考：如果x2的系数发生变化，c2在什么范围内变化，最优解不变？,97,2.基变量的cj发生变化假设x4的利润由19变为19+c4,-4-2c4,-2/3-4/3c4,-13/3-2/3c4,-10/3+10/3c4,当且仅当所有的非基变量的检验数都仍然小于等于0则最优解不变。,98,当目标函数中cj发生变化，将影响最终单纯形表非基变量的检验数。如果是非基变量的价值系数发生变化，只影响该非基变量的检验数，如果变化后的检验数仍然小于等于0，则最优解不变；如果是基变量的价值系数发生变化，将影响所有非基变量的检验数，只有当所有的非基变量检验数都仍然小于等于0，最优解才不变。,99,7.3增加一个变量 假设用甲乙两种原材料还可以生产新产品为E，需要甲原料3个单位，乙原料1个单位，利润为10，问该种新产品是否应该生产？设生产E产品x7个，则线性规划方程为：,Maxz=9x1+8x2+50 x3+19x4+10 x7 s.t.3x1+2x2+10 x3+4x4+3x718 2x3+1/2x4+x73 xj0(j=1,2,3,4,7),Maxz=9x1+8x2+50 x3+19x4+10 x7 s.t.3x1+2x2+10 x3+4x4+3x7+x5=18 2x3+1/2x4+x7+x6=3 xj0(j=1,2,7),100,P7=(3,1)T,7=c7-CBP7=10-(19,50)(13/4,5/6)T=-19/30,因为x7的检验数小于0，所以原最优单纯形表即为最优单纯形表，最优解不变。,考虑影子价格：y1=13/3，y2=10/3则生产一件E产品所需要的隐含成本为：13/3*3+10/3*1=49/310(每件E产品的利润）所以也不生产。,101,增加一个变量也就是多生产一种产品，只须考虑该种产品的检验数是否大于0，如果大于0则表示应该生产，用单纯形表进行求解；如果小于0则该种产品不用生产，最优解不发生变化。同时也可以考虑影子价格，如果该种新产品的利润大于隐含成本，则应该生产用单纯形表进行求解；如果小于隐含成本则该种产品不用生产。,102,7.4增加一个约束条件假设原线性规划问题变为,Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x418 2x3+1/2x43 2x1+x2+x3+2x48 xj0(j=1,2,3,4),Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x4+x5=18 2x3+1/2x4+x6=3 2x1+x2+x3+2x4+x7=8 xj0(j=1,2,7),103,104,此时x7的值3大于0，所以原问题和对偶问题都达到可行解，并分别为最优解。不需要进行下一步计算,105,增加一个约束条件，可能影响的只是该约束条件的松弛变量的值，如果该松弛变量的值大于等于0，则线性规划最优解不变；如果该松弛变量的值小于0，则采用对偶单纯形表进行计算。,106,7.5技术系数aij发生变化,Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x418 2x3+1/2x43 xj0(j=1,2,3,4),3x1+x2+10 x3+4x418,则P2=(2,0)T,P2=(1,0)T,2=c2-CBP2=8-(19,50)(2/3,-1/6)T=11/30,107,108,109,110,改变aij只会影响检验数，如果所有的检验数均小于等于0，则最有解不变，如果存在检验数大于0，则用单纯形法进行求解。,111,灵敏度分析总结,目标函数中价值系数发生变化,增加一个变量,aij发生变化,右端常数项发生改变,增加一个约束条件,用单纯形法求解,用对偶单纯形法求解,112,第一二章总结,线性规划问题的引出线性规划的一般模型线性规划的标准形式单纯形法的原理单纯形法大M法和两阶段法,113,对偶问题的提出根据原问题写对偶问题对偶问题的基本性质对偶单纯形表灵敏度分析,114,习题,1.研究线性规划问题,Maxz=4x1+4x2 s.t.2x1+7x221 7x1+2x249 xj0(j=1,2),问：1）用图解法求该问题的最优解2）使（写x1*,x2*）保持最优情况下目标函数系数的比值范围是多少？,115,2.研究方程组,x1+2x2-3x3+5x4+x5=45x1-2x2-6x4+x6=82x1+3x2-2x3+3x4+x7=3-x1+x3+2x4+x8=0 xj0(j=1,2,8),问：1）设(x5,x6,x7,x8)T为初始基变量，如果把x1换入为基变量，则应该把初始基变量中的哪个变量换出？2）如果将x1换入，x5换出，将得到什么解？3）如果将x1换入，x8换出，将得到什么解？,116,3.用图解法求下列线性规划问题,Maxz=-x1+2x2 s.t.x1+x22-x1+x21 x23 xj0(j=1,2),Maxz=-x1+3x2 s.t.X1-2x24-x1+x23 xj0(j=1,2),117,4.研究以下线性规划问题,已知线性规划目标函数为maxz=5x1+3x2,约束条件均为“，所有变量均0.,此时Z10，求a-g?,118,5.求线性规划问题已知该问题约束条件均为“，所有变量0.x3,x4,x5为松弛变量，根据以下单纯形表求线性规划问题,119,6.研究线性规划问题,Maxz=5x1+2x2+3x3 s.t.x1+5x2+2x3b1 x1-5x2-6x3b2 xj0(j=1,2,3),问：1）用两种方法求b1,b22）求a-e3）求对偶问题最优解,120,在第k个约束条件两边同乘以，原问题和对偶问题的解有何变化？,7.线性规划问题max z=CXs.t.AXb X 0,121,8.研究线性规划问题,问：1）写原问题2）写出对偶问题3）c2在什么范围内变化最优解不变4）增加一个约束条件 x2+x32,最优解是否发生变化，如果有求新解5）增加一个变量x6,P6=(1,2)T,c6=4,最优解是否发生变化，如果有求新解,122,9.线性规划问题为Maxz=6x1+14x2+13x3 s.t.1/2x1+2x2+x324 x1+2x2+4x360 xj0(j=1,2,3)计算得最优解,当约束条件1变为x1+4x2+2x368最优解有何变化？,123,10.线性规划问题为Maxz=5x1+3x2+6x3 s.t.x1+2x2+x318 2x1+x2+3x316 x1+x2+x310 xj0(j=1,2),Maxz=5x1+3x2+6x3-6x3”s.t.x1+2x2+x3-x3”+x4=18 2x1+x2+3x3-3x3”=16 x1+x2+x-x3”=10 xj0(j=1,2,3),最优解为：,求对偶问题最有解?,124,11.已知线性规划问题max Z=3x1+2x2-x1+2x24 3x1+2x214 x1-x23 x1,x201）写出它的对偶问题2）应用对偶理论证明原问题和对偶问题都存在最优解,125,12.已知线性规划问题min Z=2x1-x2+2x3-x1+x2+x3=4-x1+x2-kx36 x10,x20,x3 无约束其最优解为x1=-5,x2=0,x3=-11）求k的值2）写出并求出其对偶问题的最优解,126,13.已知线性规划问题min Z=8x1+6x2+3x3+6x4 x1+2x2+x43 3x1+x2+x3+x46 x3+x42 x1+x3 2 x1,x2 x3,x4 01）写出其对偶问题2）已知原问题最优解为X*（1，1，2，0），试根据对偶理论，直接求出对偶问题最优解。,127,14.某农场有100土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日，春夏季4000人日，如劳动力本身用不了时可外出干活，春夏季收入为2.1元人日,秋冬季收入为1.8元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入为400元、头奶牛。养鸡时不占土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收入为2元/只鸡。农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。三种作物每年需要的人工及收入情况如表所示。试决定该农场的经营方案，使年净收入为最大。,128,