影子价格和对偶单纯形法

影子价格和对偶单纯形法

ID:37425314

大小:485.10 KB

页数:24页

时间:2019-05-12

影子价格和对偶单纯形法_第1页
影子价格和对偶单纯形法_第2页
影子价格和对偶单纯形法_第3页
影子价格和对偶单纯形法_第4页
影子价格和对偶单纯形法_第5页
资源描述:

《影子价格和对偶单纯形法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、Chapter2DualityTheoryandSensitivityAnalysis第2章对偶理论与灵敏度分析对偶问题的基本性质对称性弱对偶性无界性最优解性质对偶定理互补松驰性原问题与对偶问题的关系XBXNXS0CB-CBB-1N-CBB-1YS1-YS2-Y例题试用对偶理论找出原问题的最优解。已知其对偶问题的最优解为:练习第三章对偶理论与灵敏度分析第五节对偶问题的经济解释——影子价格XBXNXS0CB-CBB-1N-CBB-1YS1-YS2-Y第五节对偶问题的经济解释——影子价格XBXNXS0CB-CBB-1N-CBB-1YS1-YS2-Y影子价格(shado

2、wprice)不同于一般意义上的市场价格,按照资源最优分配理论,可定义为“机会成本的货币表现”,是指某种资源或劳务被用于一种用途,而放弃另一种用途时的价值。这正是资源利用问题的数学规划中对偶模型的最优解。这是著名的前苏联数学家线性规划创始人、诺贝尔经济学奖获得者康特罗维奇发现的。检验线性规划的图解法-例2-1GraphicalsolutionoflinearprogrammingA(8,5)第五节对偶问题的经济解释——影子价格第五节对偶问题的经济解释——影子价格第三章对偶理论与灵敏度分析写出下面问题的对偶问题,然后用单纯形法求解。第三章对偶理论与灵敏度分析1850

3、800MCByBby1y2y3y4y5y6My651[5]0-10118y342210-1025M+32zjM+165M+168-M-8Mzj-cjM-25M-340-M-8050y211/510-1/501/558y32[8/5]012/5-1-2/55/466zj22.8508-6.8-86.8zj-cj4.800-6.8-86.8-M50y23/401-1/8-1/41/81/418y15/4105/81/4-5/8-1/460zj18505-8-58zj-cj00-3-8-58-M?第三章对偶理论与灵敏度分析第六节对偶单纯形法一、对偶单纯形法的基本原理由原

4、问题与对偶问题之间的关系知道,在单纯形表中进行迭代时,在b列得到的是原问题的基可行解,而在检验数行得到的是对偶问题的基解。经过迭代计算,当检验数行得到的对偶问题的解也是基可行解时,则得到最优解。第六节对偶单纯形法二、对偶问题的计算步骤列出初始单纯形表;若B-1b≥0,σj=cj–zj≤0,则问题得到最优解,否则进入下一步;取对应的基变量xi*为换出变量;由确定换入变量xj*,当所有的ai*j≥0时,问题无可行解;5.以ai*j*为主元素,按原单纯形法进行迭代,得到新的计算表;6.重复2~5步。例:用对偶单纯形法求例3-4的解第三章对偶理论与灵敏度分析-18-50-

5、800CBYBby1y2y3y4y50y4-5-1[-5]0100y5-4-2-2-101-Z=0cj-zj-18-50-800-50y23/401-1/8-1/41/8-18y15/4105/81/4-5/8-Z=60cj-zj00-3-8-5-50y211/510-1/500y5-2[-8/5]0-1-2/51-Z=50cj-zj-80-8-100课堂讨论比较单纯形算法与对偶单纯形算法的异同对偶单纯形法例子-2-3-40000-3-4-1-2-21-1-31001-2-3-400单纯形法和对偶单纯形法的步骤是是是是否否否否所有所有得到最优解计算计算原规划的基本

6、解是可行的原规划的基本解的检验数≤0所有所有计算计算以aek为主元素进行迭代以aek为主元素进行迭代停无界解无可行解单纯形法对偶单纯形法对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题在引入松弛变量化为标准型之后,约束等式两侧同乘-1,能够立即得到检验数全部非正的原规划基本解,可以直接建立初始对偶单纯形表进行求解,非常方便。对于有些线性规划模型,如果在开始求解时不能很快使所有检验数非正,最好还是采用单纯形法求解。因为,这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看,可以说,对偶单纯形法是单纯形法的一个补充。除此之外,在对线性规划进行灵

7、敏度分析中有时也要用到对偶单纯形方法,可以简化计算。对偶单纯形法的优点初始解可以是非可行的,检验数都为负数,可以进行基变换。(无需加入人工变量)变量个数多于约束条件个数。(对偶化)灵敏度分析中可以使问题简化。缺点:很难找到一个初始可行基。小结??作业P75/2.7/(1)/2.8/(1)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。