原问题与对偶问题PPT演示文稿

§2原问题与对偶问题1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。情形一：原问题对偶问题情形二：证明化为标准对称型2、非对称形式的对偶若原问题的约束条件是等式，则原问题对偶问题推导:原问题根据对称形式的对偶模型,可直接写出上述问题的对偶问题:令，得对偶问题为：证毕。目标函数max目标函数min目标函数中变量的系数约束条件右端项约束条件右端项目标函数中变量的系数原问题(对偶问题)对偶问题(原问题)例:对偶问题为例:§3对偶问题的基本性质弱对偶性；强对偶性；最优性;无界性;互补松弛性掌握原问题和其对偶问题解之间的关系对偶问题的对偶是原问题。对偶问题原问题租借方引例化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：对偶问题用两阶段法求解的最终的单纯形表化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表：两个问题作一比较:1.两者的最优值相同2.变量的解在两个单纯形表中互相包含原问题最优解（决策变量）对偶问题最优解（决策变量）从引例中可见：原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。理论证明：原问题与对偶问题解的关系在下面的讨论中,假定线性规划原问题和对偶问题分别如下原问题对偶问题1.弱对偶性是其对偶问题的可行解，则恒有若是原问题的可行解，证明：从弱对偶性可得到以下重要结论：（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。原问题对偶问题2.最优性若是原问题的可行解，提示,则是原问题的最优解，是其对偶问题的最优解。设是原问题的最优解，是其对偶问题的最优解。是其对偶问题的可行解,且有3.无界性若原问题(对偶问题)具有无界解,则其对偶问题(原问题)无可行解.说明逆命题不成立。即原问题(对偶问题)无可行解，则其对偶问题(原问题)或无可行解或具有无界解,反证法结合弱对偶性4.强对偶性(对偶定理)若原问题有最优解,则其对偶问题也一定有最优解,且有证明：将原问题化成标准形式用单纯形法求得最优解，则有即即故是对偶问题的可行解,又因由性质2即可证得。5.互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之如果约束条件取严格不等式,则该对应的对偶变量一定为零。即：如果则如果则证明：由弱对偶性知，由最优性知从而因此6.互补的基解线性规划的原问题及其对偶问题之间①存在一对互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量；②这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量；③将这对互补的基解分别代入对偶问题的目标函数有z=w.说明：原问题的检验数恰好是对偶问题的基解.原问题化为极小问题，最终单纯形表：对偶问题用两阶段法求解的最终的单纯形表化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表：说明：1)只需求解其中一个问题,从最优解的单纯形表中同时得到另一个问题的最优解.2)单纯形法迭代的每一步中,原问题及对偶问题解的关系可行解非可行解可行解非可行解最优z>zmaxz0,y2*>0,由互补松弛性知解得x3*=x4*=4.所以(L)的最优解为X*=(0,0,4,4)T因为代入(1),(2)得