《对偶理论作业》PPT课件.ppt
对偶问题作业王 莉 莉四川农业大学数学系2011年11月,3-2,最优解为：X（11/3，8/3）,min z=46/3,用对偶理论求其对偶问题的最优解.,解：引入松弛变量x3,x4,x5,x6,最优解为：X（11/3，8/3，0，0，4/3，4/3）,引入松弛变量y5,y6,其对偶问题,由互补松弛性定理,X（11/3，8/3，|0，0，4/3，4/3）,Y（y1，y2，y3，y4，|y5，y6）,y5=0,y6=0,y3=0,y4=0,将Y（y1，y2，0，0，0，0）代到对偶问题中,解得y1=4/3,，y2=1/3，即对偶问题的最优解为,X（4/3，1/3，0，0）min w=46/3,标准化,引进松弛变量x5，x6,3-4(1),写出单纯形表,1 2-3/4-,-1/2 2/3-,最优解为：X（7，0，4，0）,min z=7,标准化,引进松弛变量x4，x5,3-5,写出单纯形表,根据目标函数系数，选择x3进基；根据约束条件，确定x4离基。,2035,最优解为：X（0，20，0，0，10）min z=-100，max z=100,(1)第一个约束条件右端常数由20变为45,对于资源数量b的变化，考虑B-1b0,B-1为最优表中松弛变量所对应的系数矩阵，故,原最优表,新条件下的表,-1 5/4-,-1/5-,最优解为：X（0，0，9，18，0）min z=-117，max z=117,(2)第二个约束条件右端常数由90变为95,对于资源数量b的变化，考虑B-1b0,B-1为最优表中松弛变量所对应的系数矩阵，故,(3)目标函数中x3的价值常数由13变为8,由最优表可知，基变量为x2,x5，非基变量为x1,x3,x4,对于价值系数c的变化，考虑CBTB-1N-CNT0,B-1N为最优表中非基变量所对应的系数矩阵，故,原线性规划模型,CBT=(c2,c5)=(-5,0)，CNT=(c1,c3,c4)=(5,-8,0),目标函数x3的价值系数由13变成8，即c3=-8,因基变量为x2,x5，非基变量为x1,x3,x4,故最优解不变.,(4)目标函数中x2的价值常数由5变为6,由基变量为x2,x5，非基变量为x1,x3,x4,对于价值系数c的变化，考虑CBTB-1N-CNT0,B-1N为最优表中非基变量所对应的系数矩阵，故,CBT=(c2,c5)=(-6,0)，CNT=(c1,c3,c4)=(5,-13,0),由10，故最优解要发生变化.,原最优表,新条件下的表,-5/8,最优解为：X（5/8，165/8，0，0，0）min z=-965/8，max z=965/8,(5)x1的系数列向量变为P1=(0,5)T，它的价值系数变为-2,由基变量为x2,x5，非基变量为x1,x3,x4,对于系数矩阵A的变化，考虑CBTB-1Pj-cj0,CBT=(c2,c5)=(-5,0)，c1=2,故最优解不变.,(6)x2的系数列向量变为P2=(2,5)T，它的价值系数变为6,由基变量为x2,x5，非基变量为x1,x3,x4,对于系数矩阵A的变化，考虑CBTB-1Pj-cj,CBT=(c2,c5)=(-6,0)，c2=-6,由于x2为基变量，它的系数列向量B-1P2不再是单位阵，且CBTB-1P2-C20，故最优解会发生变化.,原最优表,新条件下的表,此单纯形表非最优表，因为系数矩阵中没有单位阵.,20/316,最优解为：X（0，0，20/3，0，70/3）min z=-260/3，max z=260/3,(7)增加一个新变量x6，其系数列向量变为P6=(3,5)T，它的价值系数变为10,由基变量为x2,x5，,对于系数矩阵A的变化，考虑CBTB-1Pj-cj0,CBT=(c2,c5)=(-5,0)，c6=-10,故最优解不发生变化.,(8)第二个约束条件变为10 x1+4x2+12x3100,约束条件发生变化，一般会导致最优解发生变化,原最优表,新条件下的表,最优解为：X（0，20，0，0，20）min z=-100，max z=100,(9)增加一个新约束条件2x1+3x2+5x350,将原最优解带入新增约束条件，检查是否满足？若是,则最优解不变，否则发生变化.,原问题的最优解为：X（0，20，0，0，10）,故最优解发生变化.,原最优表,新条件下的表,-1/2 5/3-,最优解为：X（0，25/2，5/2，0，15，0）min z=-95，max z=95,
