《原问题与对偶问题》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)单纯形法迭代的每一步中,原问题及对偶问题解的关系,可行解,非可行解,可