《《原问题与对偶问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《原问题与对偶问题》PPT课件.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2 原问题与对偶问题原问题与对偶问题1对称形式的对偶对称形式的对偶 当原问题对偶问题只含有不等式约束当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。时，称为对称形式的对偶。原原问题对偶偶问题情形一：情形一：原原问题对偶偶问题情形二：情形二：证明明对偶对偶化为标准对称型化为标准对称型2、非对称形式的对偶非对称形式的对偶 若原若原问题的的约束条件是等式，束条件是等式，则原原问题对偶偶问题推推导:原原问题根据根据对称形式的称形式的对偶模型偶模型,可直接可直接写出上述写出上述问题的的对偶偶问题:令令 ，得，得对偶偶问题为：证毕。证毕。原问题原问题(对偶问题对偶问题)对偶问题对偶问题(原问题原问
2、题)目标函数目标函数max目标函数目标函数min目标函数中变量的系数目标函数中变量的系数约束条件右端项约束条件右端项约束条件右端项约束条件右端项目标函数中变量的系数目标函数中变量的系数例例:对偶偶问题为例例:3对偶偶问题的基本性的基本性质弱弱对偶性；偶性；强对偶性；偶性；最最优性性;无界性无界性;互互补松弛性松弛性掌握原掌握原问题和其和其对偶偶问题解之解之间的关系的关系对偶问题的对偶是原问题对偶问题的对偶是原问题。对对偶偶问问题题原原问问题题租借租借方方厂厂家家n引例引例（）原原问题的的变量量原原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量化为极小问题原原问题化化为极小极小问
3、题，最，最终单纯形表：形表：（）原原问题的的变量量原原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量化为极小问题原原问题化化为极小极小问题，最，最终单纯形表：形表：原原问题的的变量量原原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量对偶偶问题用两用两阶段法求解的最段法求解的最终的的单纯形表形表（）原原问题的的变量量原原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量化为极小问题化为极小问题原原问题最最优解解对偶偶问题最最优解解原原问题化化为极小极小问题，最，最终单纯形表：形表：两个两个问题作一比作一比较:原问题最优解原问题最优解（决策变量）（决策变
4、量）对偶问题最优解对偶问题最优解（决策变量）（决策变量）对偶问题的松弛变量对偶问题的松弛变量原问题的松弛变量原问题的松弛变量从引例中可见：从引例中可见：原问题与对偶问题在某种意义上原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达问题仅仅在第一个问题的另一种表达而已。而已。理理论证明：明：原原问题与与对偶偶问题解的关系解的关系在下面的在下面的讨论中中,假定假定线性性规划原划原问题和和对偶偶问题分分别如下如下原问题原问题对偶问题对偶问题1.弱对偶性弱对偶性是其对偶问题的可行解，则恒有是其对偶问题的可行解，则恒有是其对偶问题
5、的可行解，则恒有是其对偶问题的可行解，则恒有若若若若是原问题的可行解，是原问题的可行解，是原问题的可行解，是原问题的可行解，证明：证明：（1 1）极大化）极大化问题（原（原问题）的任一可行）的任一可行解所解所对应的目的目标函数函数值是是对偶偶问题最最优目目标函数函数值的下界。的下界。（2 2）极小化）极小化问题（对偶偶问题）的任一可）的任一可行解所行解所对应的目的目标函数函数值是原是原问题最最优目目标函数函数值的上界。的上界。（3 3）若原）若原问题可行，但其目可行，但其目标函数函数值无无界，界，则对偶偶问题无可行解。无可行解。（4 4）若）若对偶偶问题可行，但其目可行，但其目标函数函数值无界
6、，无界，则原原问题无可行解。无可行解。（5 5）若原）若原问题有可行解而其有可行解而其对偶偶问题无无可行解，可行解，则原原问题目目标函数函数值无界。无界。（6 6）对偶偶问题有可行解而其原有可行解而其原问题无可无可行解，行解，则对偶偶问题的目的目标函数函数值无界。无界。原问题原问题对偶问题对偶问题2.最优性最优性若若是原问题的可行解，是原问题的可行解，提提示示,则则是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。设设是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。是其对偶问题的可行解是其对偶问题的可行解,且有且有3.无界性无界性若
7、原问题若原问题(对偶问题对偶问题)具有无界解具有无界解,则其对偶问则其对偶问题题(原问题原问题)无可行解无可行解.说明说明逆命题不成立。逆命题不成立。即原问题即原问题(对偶问题对偶问题)无可行解，则其对偶问无可行解，则其对偶问题题(原问题原问题)或无可行解或具有无界解或无可行解或具有无界解,反证法结合弱对偶性反证法结合弱对偶性4.强对偶性强对偶性(对偶定理对偶定理)若原问题有最优解若原问题有最优解,则其对偶问题则其对偶问题也一定有最优解也一定有最优解也一定有最优解也一定有最优解,且有且有证明：证明：证明：证明：将原问题化成标准形式将原问题化成标准形式用单纯形法求得最优解用单纯形法求得最优解，则
8、有，则有即即即即故故是对偶问题的可行解是对偶问题的可行解,又因又因由性质由性质2即可证得。即可证得。5.5.互补松弛性互补松弛性互补松弛性互补松弛性在线性规划问题的最优解中在线性规划问题的最优解中,如果对应某一约如果对应某一约束条件的对偶变量值为非零束条件的对偶变量值为非零,则该约束条件取严格则该约束条件取严格等式等式;反之如果约束条件取严格不等式反之如果约束条件取严格不等式,则该对应则该对应的对偶变量一定为零。的对偶变量一定为零。即：即：如果如果则则如果如果则则证明：证明：由弱对偶性知，由弱对偶性知，由最优性知由最优性知从而从而因此因此6.6.互补的基解互补的基解互补的基解互补的基解线性规划
9、的原问题及其对偶问题之间线性规划的原问题及其对偶问题之间存在一对互补的基解存在一对互补的基解,其中原问题的松弛变量对其中原问题的松弛变量对应对偶问题的变量应对偶问题的变量,对偶问题的剩余变量对应原问对偶问题的剩余变量对应原问题的变量；题的变量；这些互相对应的变量如果在一个问题的解中是这些互相对应的变量如果在一个问题的解中是基变量基变量,则在另一问题的解中是非基变量；则在另一问题的解中是非基变量；将这对互补的基解分别代入对偶问题的目标函将这对互补的基解分别代入对偶问题的目标函数有数有z=w.说明：说明：原问题的检验数原问题的检验数恰好是对偶问题的基解恰好是对偶问题的基解.（）原原问题的的变量量原
10、原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量化为极小问题原原问题化化为极小极小问题，最，最终单纯形表：形表：原原问题的的变量量原原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量对偶偶问题用两用两阶段法求解的最段法求解的最终的的单纯形表形表（）原原问题的的变量量原原问题松弛松弛变量量对偶偶问题剩余剩余变量量对偶偶问题的的变量量化为极小问题化为极小问题原原问题最最优解解对偶偶问题最最优解解原原问题化化为极小极小问题，最，最终单纯形表：形表：说明：说明：1)只需求解其中一个问题只需求解其中一个问题,从最优解的单纯从最优解的单纯形表中同时得到另一个问题的最优解形表中同时得到另一个问题的最优解.2)单纯形法迭代的每一步中单纯形法迭代的每一步中,原问题及对偶原问题及对偶问题解的关系问题解的关系目标函数值目标函数值原问题原问题对偶对偶问题问题可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解可行解可行解非可行解非可行解非可行解非可行解最优最优最优最优z zz zmaxmaxz z0,y2*0,由互由互补松弛性知松弛性知解得解得x3*=x4*=4.所以所以(L)的最的最优解解为X*=(0,0,4,4)T因因为代入代入(1),(2)得得