对偶理论和灵敏度分析新

1、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,假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则 问题变成对于甲乙两种原材

2、料企业以多少最低价愿意出让,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5y25 y1,y20,4,第4节 线性规划的对偶理论对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“号。则称这些线性规划问题具有对称性,max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,min w=b1y1+b2y2

3、+bmym s.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=CX s.t. AXb X 0,对偶问题 min w=Yb s.t. AYC Y 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

4、+y3 s.t. -y1+3y2+y33 2y1+2x2-y32 y1,y2,y30,y1,y2,y3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x1,x2,7,原始问题为 min z=2x1+3x2-x3 s.t. x1+2x2+x36 2x1-3x2+2x39 x1, x2, x30,根据定义，对偶问题为 max y=6y1+9y2 s.t. y1+2y22 2y1- 3y23 y1+2y2-1 y1, y20,原始问题是极小化问题 原始问题的约束全为 原始问题有3个变量，2个约束 原始问题的变量全部为非负,对偶问题是极大化问题 对偶问题的约束全为 对偶问题有2个变量，3

5、个约束 原始问题的变量全部为非负,原始问题变量的个数(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+x46 x2+x3+x46,x1=x1 ，x10;x4-x4”=x4,x4 0,x4” 0,minz=-2x1+3x2-5x3+(x4-x4”) s.t.-x1+x2-3x3+(x4-x4”)5 2x1 -2x3+(x4-x4”)-4 x2+x3 +(x4-x4”

6、) 6 -x2-x3-(x4-x4”) -6 x1,x2,x3 ,x4,x4” 0,y1,y2,y3,y3,maxw=5y1-4y2+6(y3-y3”) s.t.-y1+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”) s.t.-y1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2 +(y3-y3”) -5 y1+y2+(y3-y3”) 1 -y1-y2-(y3-y3”) -1 y1,y2 ,

7、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、等式与非

8、负限制的决策变量的对偶 6、最优解与检验数的对偶,12,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max y=6w1+12w2+8w3+15w4 s.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)。 原始问题变量的性

9、质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质,写对偶问题的练习（1,13,写对偶问题的练习（2,原始问题,max z=2x1-x2+3x3-2x4 s.t. x1 +3x2 - 2x3 + x412 -2x1 + x2 -3x48 3x1 - 4x2 +5x3 - x4 = 15 x10, x2:Free, x30, x40,min y=12w1+8w2+15w3 s.t. w1 - 2w2 + 3w32 3w1 + w2 - 4w3=-1 -2w1 +5w33 w1 - 3w2 - w3-2 w10,w20, w3:Free,对偶问题,14,maxZ=x1-2

10、x2+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,原始和对偶问题可行解目

11、标函数值比较,min z=2x1+3x2 s.t. x1+3x23 2x1+x2 4 x1, x2 0,max w=3y1+4y2 s.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)T I 为mm的单位矩阵,17,对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1； 初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b； 约束矩阵（A，I）（B，N，I），迭代后为 （B-1B，B-1N，

12、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-CBI0 CCBB-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,m

13、inw=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,2

14、6,1）对称性：对偶问题的对偶,max z=6x1+9x2 s.t. x1+2x22 2x1- 3x23 x1+2x2-1 x1, x20,minw=2y1+3y2-y3 s.t. y1+2y2+y36 2y1-3y2+2y39 y1, y2, y30,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题,max u=6w1+9w2 s.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,min

15、w=8y1+5y2 s.t. 5y1+y21 -y1+3y24 2y1-3y2 2 y1,y20,28,4.2 对偶问题的基本性质,原始问题 max z=CX s.t. AXb X 0,对偶问题 min w=Yb s.t. AYC Y 0,2）弱对偶性 若X为原问题的可行解，Y为对偶问题的可行解，则恒有 CXYb,29,推论： 原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。 （3）无界性 如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题

16、无界解或无可行解。 推论： 若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界 若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界,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分别为原问题和对偶

17、问题的最优解,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+5x

18、2 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/5 X4=0,4x1+5x2=40,y2=6/7,y3=0, 3y1+4y2=5,x1=40/7 y4=0, 2y1+5y2=5,x2=24/7,34,利用互补松弛关系求解线性规划,min z=6x1+8x2+3x3 s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0,max w=y1-y2 s.t. y

19、1+ y2 6 y1+2y2 8 y2 3 y1,y20,原始问题,对偶问题,最优解为(y1, y2)=(6, 0) max y=6,先用图解法求解对偶问题,35,min z=6x1+8x2+3x3 s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0,max w=y1-y2 s.t. y1+ y2 6 y1+2y2 8 y2 3 y1, y20,max w=y1-y2 s.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,

20、 2, 3,min z=6x1+8x2+3x3 s.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=最大

21、利润的增量/第i种资源的增量 =第i种资源的边际利润,w=b1y1+b2y2+biyi+bmym,w+w=b1y1+b2y2+(bi+bi)yi+bmym,w=biyi,37,Z*=8.5 X=(7/2,3/2,Z*=8.75 X=(15/4,5/4,Z=9 X=(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未得到充分利用时

22、，该种资源的影子价格 为0； 当资源的影子价格不为0，表示该种资源在生产中已 消耗完毕,j=cj-zj=cj-CBB-1Pj cj表示第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 +x

23、5=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=

24、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

25、）代入,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5,是对偶问题的可行解,45,单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解,46,第6节 对偶单纯形法,对于对偶单纯形法刚好和单纯形法的思路相反，就是在始终保持对偶问题可行的条件下，不断改进原问题可行性的过程。一个从原问题不可行的解，经过几次叠代，逐步向原问题可行

26、解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解,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,举

27、例,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/3 W=22/3,59,Minw=2x1+3x2+4x3 s.t. x1+2x2+ x33 2x1- x2+3x34 x1,x2,x30,练习:用对偶单纯形法求解并求出对

28、偶变量的最优解,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/5 W=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 y

29、1+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,可以看出，这时候原问题和对偶问题

30、都不可行,列出初始单纯形表,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

31、(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-1b Z=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，则原最终单纯

32、形表中的基变量不变 ，基变量的值将发生变化 如果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.非基变量的c

33、j发生变化 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-

34、4/3c4,13/3 -2/3c4,10/3 +10/3c4,当且仅当所有的非基变量的检验数都仍然小于等于0则最优解不变,98,当目标函数中cj发生变化，将影响最终单纯形表非基变量的检验数。如果是非基变量的价值系数发生变化，只影响该非基变量的检验数，如果变化后的检验数仍然小于等于0，则最优解不变；如果是基变量的价值系数发生变化，将影响所有非基变量的检验数，只有当所有的非基变量检验数都仍然小于等于0，最优解才不变,99,7.3增加一个变量 假设用甲乙两种原材料还可以生产新产品为E，需要甲原料3个单位，乙原料1个单位，利润为10，问该种新产品是否应该生产？ 设生产E产品x7个，则线性规划方程为,M

35、axz=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 则生产一

36、件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+ x

37、3+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

38、 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,第一二章总结

39、,线性规划问题的引出 线性规划的一般模型 线性规划的标准形式 单纯形法的原理 单纯形法 大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=4 5x1-2x2 -6x4+x6=8 2x1+3x2-2x3+3x4+x7=3 -x1 +x3+2

40、x4+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