运筹学概论第2章线性规划的对偶理论.ppt

第二章 线性规划的对偶理论,线性规划的对偶问题 对偶问题的基本性质 影子价格,第一节 线性规划的对偶问题,窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象,例1 美佳公司计划制造甲、乙两种家电产品，已知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时； A设备每天可用15小时， B设备可用24小时，调试工序每天可用5小时。已知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？,例2 假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。,对偶问题,原问题,一、对偶问题的提出,二、对称形式下对偶问题的一般形式,用矩阵形式表示：,任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义,例 3,假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？,设A、B资源的出售价格分别为 y1 和 y2 显然商人希望总的收购价越小越好(目标) 工厂希望出售资源后所得不应比生产产品所得少（约束）,对偶问题的对偶即原问题。同样，可以将对偶问题当作原问题，写出其对偶问题。,课堂练习：,三、非对称形式的原-对偶问题关系,转换为对偶问题的思路是：先将其转化成对称形式，再按对应关系来写。因例中目标函数为max，故约束条件应换为“”号，所有的变量均应“0”，,-3x1+x2-6x3-1,x1+x2+x34 -x1-x2-x3-4,x2=-x2；x3=x3-x3,y2=-y2；y3=y3-y3；（3）式 两端乘“-1”，（4）、（5）合并。,解：设对偶变量为y1,y2,y3,对偶问题模型为： Max w=5y1+4y2+6y3 y1 +2y2 y1 + y3 -3y1 +2y2 +y3 y1 - y2 +y3,2 3 -5 =1,y10, y20, y3无约束,2,课堂练习：,第二章 线性规划的对偶理论,线性规划的对偶问题 对偶问题的基本性质 影子价格,第二节 对偶问题的基本性质,为了便于讨论，下面不妨总是假设：,原线性规划问题的矩阵表达式加上松弛变量后为：,一、单纯形法的矩阵描述,上式中Xs为松弛变量， ，I为mm单位矩阵。,单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出，而A中去掉若干列后剩下的列组成矩阵N，这样初始单纯形表可列成如下形式。,当迭代若干步后，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换，对应XS的系数矩阵在新表中应为B-1。故当基变量为XB时，新的单纯形表具有如下形式。,当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有： （1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 （2）初始单纯形表中基变量Xs=b，迭代后的表中 XB= B-1 b （3）初始单纯形表中约束系数矩阵为 ，迭代后的表中约束系数矩阵为(B-1 左乘) :,（4）若初始矩阵中变量Xj的系数向量为Pj ，迭代后为 ，则有:,（5）当B为最优基时，应有:,这时从检验数行看出，若取其相反数恰好是其对偶问题的一个可行解。 将这个解代入对偶问题的目标函数值，有：,因XB的检验数可写为:,XN的检验数,XS的检验数,XB的检验数,例1 两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：,二、原规划与对偶规划问题的变量及解之间的对应关系,两个问题的最终单纯形表见下页：,二、原规划与对偶规划问题的变量及解之间的对应关系,对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值 对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值 更一般地讲，不管原问题是否标准，在最优解的单纯形表中，都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,三、线性规划的对偶定理,如果xj*(j=1,2n)是原问题(max)的可行解，yi*(i=1,2m)是对偶问题(min)的可行解，则恒有,1.弱对偶定理,证明：,弱对偶定理推论:,max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限。 如果原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 如果原问题（对偶问题）有可行解，其对偶问题（原问题）无可行解，则原问题（对偶问题）为无界解。 注意：如果原问题（对偶问题）无可行解，对偶问题（原问题）或具有无界解或无可行解。,2. 最优性（最优解判别定理）,如果xj*(j=1,n)是原问题的可行解， yi*(i=1,m)是其对偶问题的可行解，且有： 则xj*(j=1,n)是原问题的最优解， yi*(i=1,m)是其对偶问题的最优解。,3.强对偶性（对偶定理）,如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。,4. 互补松弛性（互补松弛定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零的，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为0。也即,第二章 线性规划的对偶理论,线性规划的对偶问题 对偶问题的基本性质 影子价格,例1 美佳公司计划制造甲、乙两种家电产品，已知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时； A设备每天可用15小时， B设备可用24小时，调试工序每天可用5小时。已知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？,例2 假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。,yi*表示资源最优利用条件下对第i种资源的估价,第三节 影子价格,三种资源的拥有量,对偶问题的经济解释 影子价格,bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义是在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。