《线性规划的对偶理论2-对偶问题的性质.ppt》由会员分享，可在线阅读，更多相关《线性规划的对偶理论2-对偶问题的性质.ppt（23页珍藏版）》请在三一办公上搜索。
1、第二章 对偶理论与灵敏度分析,第二节 对偶问题的基本性质,例：某公司计划生产甲、乙两种产品，已知各生产一件时分别占用的设备A、B的台时、调试时间和调试工序每天可用于这两种产品的能力、各销售一件时的获利情况，如下表所示。问该公司应生产两种产品各多少件，使获取的利润为最大。,设 和 分别表示该公司生产甲乙两种产品的数量,(LP1),+0 x3+0 x4+0 x5,(LP2),+0 x3+0 x4+0 x,(LP1),最优解为 X=(2/7,2/3,15/2,0,0)T，代入目标函数得 z=8.5。,(LP2),两阶段法,第一阶段,第二阶段,问题 LP2 有可行解，去除人工变量，并从最后一个表出发，
2、继续用单纯形法求解。,LP2 的最优解为 Y=(0,1/4,1/2,0,0)T，代入目标函数得 w=8.5。,将 LP1 和 LP2 的最终单纯形表进行比较，我们观察有什么特点？,max z=CXs.t.AX+XS=bX,XS 0,min W=YTbs.t.ATY-YS=CTY,YS 0,XTYS=0YTXS=0,m,n,=,Y,YS,AT,-I,CT,n,=,A,XS,I,b,n,m,m,X,原问题和对偶问题变量、松弛变量的维数,y1 yi ym ym+1 ym+j yn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变
3、量,互补松弛性xj ym+j=0yi xn+i=0(i=1,2,m；j=1,2,n)即：在一对变量中，其中一个大于0，另一个一定等于0。,对偶问题的基本性质：,2无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,4强对偶性（对偶定理）：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,1弱对偶性：若 是原问题的可行解，是对偶问题的可行 解，则存在。,3最优性：设是原问题的可行解，是对偶问题的 可行解，当时，和是最优解。,5互补松弛性：若，分别是原问题和对偶问题的可行解，那么 和，当且仅当，为最优解。,1、可行解的目标函数值之间的关系 设X、Y 分别是原始问题和对偶问题的可行解，则z=CX YT b=w2、最优解的目标函数值之间的关系 设Xo、Yo 分别是原始问题和对偶问题的最优解 z=CXo=yo T b=w,3、原始问题和对偶问题最优解之间的互补松弛关系,max z=CXs.t.AX+XS=b X,XS0,max w/=-yT bs.t.AT Y-YS=CT Y,YS0,max z=CXs.t.AX b X 0,min w=YT bs.t.AT Y CT Y0,互补松弛关系,证明：该问题存在可行解，例如X=(0,0,0)，其对偶问题为,由第一约束条件可知对偶问题无可行解，因而无最优解。,
