收藏 分销(赏)

运筹学1-4.ppt

上传人:xrp****65 文档编号:13781345 上传时间:2026-04-13 格式:PPT 页数:147 大小:2.90MB 下载积分:10 金币
下载 相关
运筹学1-4.ppt_第1页
第1页 / 共147页
运筹学1-4.ppt_第2页
第2页 / 共147页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精品课程,运筹学,第四节 解线性规划问题的,进一步讨论,4.1,两阶段法及关于单纯形方法的几点说明,4.2,线性规划问题的对偶及对偶单纯形法,4.3,线性规划问题的灵敏度分析,精品课程,运筹学,4.1,两阶段法,及关于单纯形方法的几点说明,第一个阶段是判断线性规划是否有可行解,如果没有可行解,当然就没有基本可行解,计算停止;如果有可行解,按第一阶段的方法可以求得一个初始的基本可行解,使运算进入第二阶段,.,第二阶段是从这个初始的基本可行解开始,使用单纯形方法或者判定线性规划问题无界,或者求得一个最优解,.,(1),两阶段法,精品课程,运筹学,设,原问题为,精品课程,运筹学,LP,问题,(1.4.1),与它的辅助,LP,问题,(1.4.2),之间的关系,(1.4.2),精品课程,运筹学,第一个基本可行解为,目标函数有下界,问题,(1.4.2),必有最优解,精品课程,运筹学,问题,(1.4.2),解的情形,情形,1,精品课程,运筹学,问题,(1.4.2),解的情形,情形,2,情形,3,但仍是基变量,.,精品课程,运筹学,旋转,精品课程,运筹学,0,精品课程,运筹学,例,1.4.1,求解,精品课程,运筹学,解,增加人工变量 得到辅助,LP,问题,精品课程,运筹学,形成如下形式的表,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,例,1.4.2,求解,精品课程,运筹学,解,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,无可行解,精品课程,运筹学,(2,)关于单纯形方法的几点说明,1.,在以上几节的讨论中,我们总假定基本可行解是非退化的,这保证了单纯形法的每一次迭代使目标函数值严格下降,因此已出现过的基本可行解不可能重复出现,.,由于基本可行解的个数有限,因此迭代一定在有限步结束,.,但如果在对程序法迭代过程中遇到退化的基本可行解,就不能保证目标函数值通过迭代得到改进,.,于是有可能使单纯形的迭代在进行了若干次旋转变换后又回到了前面的某个基本可行解,.,这意味着算法将无限的循环下去,这种现象称为,循环,.,精品课程,运筹学,幸而这种情况在实际中极少出现,.,当然避免发生循环的方法是有的,如摄动法、字典序方法和,Bland,反循环算法等等,.,按照这些方法所给出的有关规则进行单纯形法的迭代,不论是否出现退化情况,均保证单纯形在有限次迭代后终止运算,.,下面分别介绍一下摄动法、,Bland,反循环算法,.,精品课程,运筹学,a.,摄动法,设给定了线性规划,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,摄动法的具体做法,.,给定了线性规划问题,:,(3.1),精品课程,运筹学,得到下列线性规划问题,(3.2),:,精品课程,运筹学,如果把,(3.1),(3.1),记成,精品课程,运筹学,则,(3.2),可以写成,:,精品课程,运筹学,精品课程,运筹学,(3.3),精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,(3.3),精品课程,运筹学,精品课程,运筹学,例如约束条件,(3.4),:,精品课程,运筹学,作,(3.4),的摄动问题,:,(3.5),精品课程,运筹学,(3.6),(3.7),精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,它的每个分量都非负,是基本可行解,.,精品课程,运筹学,例,用摄动法求解,LP,问题,精品课程,运筹学,精品课程,运筹学,做出单纯形表,:,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,迭代后的表为,:,精品课程,运筹学,精品课程,运筹学,再迭代一次得到,:,最优解,:,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,b.Bland,反循环算法,在,每一步迭代时,,精品课程,运筹学,2.,在计算机上实际计算的,LP,问题,一般其变量个数和约束方程个数都比较多,如何节省存贮单元和减少计算量是必须加以考虑的问题,.,仔细的分析前面所述单纯形法的各计算公式,可以使我们在保留最必要的数据前提下,精巧的处理有关运算,这就是,修正的单纯形法,或称为,逆矩阵法,.,一般在计算机上解,LP,问题时,大多采用的是修正的单纯形法,.,目前,解,LP,问题的商用软件包已经普及,大家可在计算机上直接调用,.,精品课程,运筹学,修正的单纯形方法,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,对于某些有特殊结构的线性规划问题,例如运输问题,变量有上、下界限制,或者是约束方程组的系数矩阵是稀疏的并且有某些特殊构造形式,将其化为标准形式的,LP,问题后,当然可用单纯形法求解,.,但这样做往往使变量个数和约束方程个数都增加很多,导致问题规模增大,给计算和存贮带来困难,.,已经发展了一些针对构造特殊的线性规划问题的专用单纯形算法,如解运输问题的,表上作业法,、,图上作业法,、,有界变量单纯形法,、,有效约束方法,、,Dantzig-Wolfe,的分解算法,等等,.,这些方法避免了上面提到的一些弊端,提高了单纯形方法解题的能力,.,精品课程,运筹学,D,W,分解方法,(,Dantzig-Wolfe),精品课程,运筹学,精品课程,运筹学,4.2,线性规划问题的对偶及对偶单纯形,(,1),对偶线性规划,考虑一般形式的,LP,问题,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,的,一个可行解,.,精品课程,运筹学,精品课程,运筹学,定义,1.4.1,给定一个一般形式的,LP,问题,称它为原始,LP,问题,那么它的对偶问题定义如下:,精品课程,运筹学,原问题和对偶问题的对偶约束之间的关系:,变量,无限制,行,约束,行,约束,变量,无限制,精品课程,运筹学,规范形式,标准形式,精品课程,运筹学,例,1.4.3,求,下面问题的对偶,解,精品课程,运筹学,其,对偶问题为,写成分量形式,即,精品课程,运筹学,(2),对偶理论,定理,1.4.1,如果一个,LP,问题有最优解,则它的对偶问题也有最优解,且它们的最优值相等,.,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,推论,1.4.1,精品课程,运筹学,定理,1.4.2,对偶的对偶为原始的,LP,.,(,对称性),证,将原始的,LP,的对偶问题记为,把它视为原始问题,精品课程,运筹学,按定义,1.4.1,写出它的对偶问题是,显然这就是最初的原始,LP,问题,.,精品课程,运筹学,任何一个,LP,问题总是属于下列三种情况之一,有最优解;,问题无界;,无可行解,.,一个原始问题和它的对偶问题的九种可能的组合,精品课程,运筹学,给定一个原始,LP,问题和它的对偶,则表,1.4.1,中表示的三种情况恰有一种情况出现,.,定理,1.4.3,表,1.4.1,一个原始问题和它的对偶问题的九种可能的组合,精品课程,运筹学,证,由,(1.4.7),关系式知,如果原始,LP,问题或者它的对偶,二者之中有一个是无界的,那么另一个不可能有可行解,.,因此剩下的只有表上所示的情况和,.,下述例题说明情况或是会出现的,.,考虑原始,LP,问题,其对偶问题是,精品课程,运筹学,精品课程,运筹学,定理,1.4.4,(,互补松紧性,),(1.4.8),(1.4.9),精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,互补松紧性条件说明,对于最优解,x,和,w,,,如果对偶问题中的一个约束取严格不等式,则原始问题中对应的变量必取值为零;对称地,如果一个问题中其非负变量取正值,则另一个问题中对应的约束必取等式,.,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,有关对偶问题最优解的全部信息,我们在解原始,LP,问题的最后一张单纯形表中可以得到,.,假定解原始,LP,问题开始时表的左半部是一个单位矩阵,通常它对应于人工变量或松弛变量,如下表所示,精品课程,运筹学,精品课程,运筹学,从而有,因此从最后的单纯形表中,可得到对偶的最优解为,精品课程,运筹学,我们还可看出,在最后的单纯形表中,替换了开始的单位矩阵的位置,.,最后的单纯形表如下:,精品课程,运筹学,例,1.4.5,求解,精品课程,运筹学,解,增加人工变量 得到辅助,LP,问题,精品课程,运筹学,形成如下形式的表,精品课程,运筹学,迭代得到,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,为了直接从最后的单纯形表上得到对偶问题最优解的信息,在用两阶段法求解原始,LP,问题时,当第一阶段结束后,不必去掉有关人工变量的列,即取如下形式的单纯形表,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,对于原始和对偶问题的经济解释,精品课程,运筹学,对,偶,精品课程,运筹学,现在换一个角度来考虑这个工厂的生产组织问题,精品课程,运筹学,会计价格,虚拟价格,影子价格,含义:,针对收益最大的产品生产安排,对原料所做的一种价格估计,精品课程,运筹学,(3),对偶单纯形法,因此单纯形方法可以解释为它是在保持一个原始问题可行解的前提下,向对偶可行解的方向迭代,.,原始算法,我们可以从一个对偶可行解开始,保持对偶问题的可行性,向原始可行解的方向迭代,对偶单纯形法,由单纯形方法,我们可以得到,,LP,问题的最优解应该是,可行的;,最优的;由对偶性可知,,LP,问题的最优性相当于,DLP,的可行性,,LP,问题的可行性相当于,DLP,的最优性,.,精品课程,运筹学,精品课程,运筹学,因此旋转列的选取由下式确定,精品课程,运筹学,列出初始单纯形表(它含有原始问题的一个基本解和对偶问题的一个可行解),.,对偶单纯形方法步骤,第,1,步,第,2,步,第,3,步,第,4,步,精品课程,运筹学,第,5,步,第,6,步,对偶单纯形方法步骤,例,1.4.6,解下面的,LP,问题,精品课程,运筹学,解,对应的单纯形表为,精品课程,运筹学,得,新表,精品课程,运筹学,得,新表,精品课程,运筹学,精品课程,运筹学,在设计实际的线性规划模型时,所搜集到的各个数据不是很精确;另一方面,在市场经济大环境中,各种信息瞬息万变,已形成的数学模型中的有些数据必须随之而变,.,因此,对于一个线性规划问题,研究当数据变动时解的变化情况是很重要的,.,在本节内,我们仅研究个别数据变化时导致解变化的情况,这就是灵敏度分析问题,.,4.3,线性规划问题的,灵敏度分析,(,1),改变价值向量,c,精品课程,运筹学,考虑标准形式的,LP,问题,假定已得到它的最优单纯形表如下,精品课程,运筹学,否则,需按单纯形法进行迭代,.,精品课程,运筹学,情况,1,否则,可由此进行单纯形迭代,.,精品课程,运筹学,情况,2,而,精品课程,运筹学,情况,2,精品课程,运筹学,例,1.4.7,回忆例,1.4.1,中的问题,精品课程,运筹学,它的最优单纯形表如下,精品课程,运筹学,得,新的最优单纯形表,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,需要继续迭代,精品课程,运筹学,(2),改变右端向量,b,否则,用对偶单纯形法继续求解,.,精品课程,运筹学,例,1.4.8,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,用对偶单纯形法继续求解,.,精品课程,运筹学,(3),改变系数矩阵,A,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,即,精品课程,运筹学,故这时需重新计算目标函数行,:,精品课程,运筹学,例,考虑问题,精品课程,运筹学,精品课程,运筹学,于是得,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服