运筹学大学课件42对偶问题的基本性质文档.pptx
《运筹学大学课件42对偶问题的基本性质文档.pptx》由会员分享,可在线阅读,更多相关《运筹学大学课件42对偶问题的基本性质文档.pptx(37页珍藏版)》请在文库网上搜索。
1、返回返回返回返回继续继续继续继续第二节第二节 对偶问题的基本性质对偶问题的基本性质n单纯形法形法计算的矩算的矩阵描述描述n引例引例n对称性称性n弱弱对偶性偶性n最最优性性n对偶性(偶性(强对偶性)偶性)n互互补松弛性松弛性 单纯形法的矩阵描述单纯形法的矩阵描述不妨设基为不妨设基为基变量基变量非基变量非基变量设线性规划问题设线性规划问题则则 单纯形法的矩阵描述单纯形法的矩阵描述其中其中令令 得当前的基解为:得当前的基解为:当前基解当前基解约束方程组约束方程组当前目标值当前目标值目标函数目标函数令令 得当前的目标函数值为:得当前的目标函数值为:单纯形法的矩阵描述单纯形法的矩阵描述当前检验数当前检验
2、数 单纯形法的矩阵描述单纯形法的矩阵描述检验数检验数其中其中当前当前 对应的系数列对应的系数列单纯形法计算的矩阵描述单纯形法计算的矩阵描述线性规划问题线性规划问题化为标准型,引入松弛变量化为标准型,引入松弛变量初始单纯形表初始单纯形表非基变量非基变量基变量基变量初始基变量初始基变量单纯形法计算的矩阵描述单纯形法计算的矩阵描述基变量基变量非基变量非基变量当基变量为当基变量为 时,新的单纯形表时,新的单纯形表单纯形法计算的矩阵描述单纯形法计算的矩阵描述当前检验数当前检验数当前基解当前基解单纯形法形法计算的矩算的矩阵描述描述 从上两表可看出,当迭代后基变量为XB时,其在初始单纯形表中的系数矩阵为B,
3、则有:(1)对应初始单纯形表中的单位矩阵I,迭代后的单纯形表中为B-1 (2)初始单纯形表中基变量Xs b,迭代后的表中 (3)初始单纯形表中约束系数矩阵为A,I=B,N,I,迭代后的表中约束系数矩阵为 B-1A,B-1I=B-1B,B-1N,B-1I=I,B-1N,B-1。单纯形法形法计算的矩算的矩阵描述描述 (4)若初始矩阵中变量xj的系数向量为Pj 迭代后为 则有则有 (5)当B为最优基时,在新的单纯形表应有单纯形法形法计算的矩算的矩阵描述描述 可看出这时检验数行,若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值,有当原问题为最优解时,这时对偶问题为可行解,且两
4、者具有相同的目标函数值对对偶偶问问题题原原问问题题收收购购厂厂家家n引例引例()原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题化为极小问题,最终单纯形表:原问题化为极小问题,最终单纯形表:原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表()原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题化为极小问题
5、原问题原问题最优解最优解对偶问题对偶问题最优解最优解原问题化为极小问题,最终单纯形表:原问题化为极小问题,最终单纯形表:n两个问题作一比较两个问题作一比较:1.两者的最优值相同两者的最优值相同2.变量的解在两个单纯形表中互相包含变量的解在两个单纯形表中互相包含原问题最优解原问题最优解(决策变量)(决策变量)对偶问题最优解对偶问题最优解(决策变量)(决策变量)对偶问题的松弛变量对偶问题的松弛变量原问题的松弛变量原问题的松弛变量从引例中可见:从引例中可见:原问题与对偶问题在某种意义上来说,原问题与对偶问题在某种意义上来说,实质上是一样的,因为第二个问题仅仅在第实质上是一样的,因为第二个问题仅仅在第
6、一个问题的另一种表达而已。一个问题的另一种表达而已。理论证明:理论证明:原问题与对偶问题解的关系原问题与对偶问题解的关系对偶偶问题的基本性的基本性质一、对称定理:一、对称定理:定理:定理:对偶问题的对偶是原问题对偶问题的对偶是原问题。设原问题(设原问题(1 1)对偶问题(对偶问题(2 2)二、弱对偶性定理:二、弱对偶性定理:若若 和和 分别是原问题(分别是原问题(1 1)及对偶问题(及对偶问题(2 2)的可行解,则有)的可行解,则有 证明:证明:对偶偶问题的基本性的基本性质从弱对偶性可得到以下重要结论:从弱对偶性可得到以下重要结论:n(1 1)极大化问题(原问题)的任一可行解所对应的目)极大化
7、问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。标函数值是对偶问题最优目标函数值的下界。n(2 2)极小化问题(对偶问题)的任一可行解所对应的)极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。目标函数值是原问题最优目标函数值的上界。n(3 3)若原问题有可行解,但其目标函数值无界,则对)若原问题有可行解,但其目标函数值无界,则对偶问题无可行解。偶问题无可行解。n(4 4)若对偶问题可行,但其目标函数值无界,)若对偶问题可行,但其目标函数值无界,则原问题无可行解。则原问题无可行解。n(5 5)若原问题有可行解而其对偶问题无可行)若原问
8、题有可行解而其对偶问题无可行解,则原问题目标函数值无界。解,则原问题目标函数值无界。n(6 6)对偶问题有可行解而其原问题无可行解,)对偶问题有可行解而其原问题无可行解,则对偶问题的目标函数值无界。则对偶问题的目标函数值无界。例题例题判断下例说法是否正确,为什么?A 如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解 B 如果线性规划的对偶问题无可行解,则原问题也一定无可行解。C 在互为对偶的一对原问题和对偶问题中,不管原问题是求极大或者极小,原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。A不对。因为原问题为无界解时(它当然有可行解),其对偶问题无可行解。B此句为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 大学 课件 42 对偶 问题 基本 性质 文档