运筹学第6讲.ppt

《运筹学第6讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学第六讲复习a线性规划的原问题与其对偶问题之间存在互为对偶的关系，即线性规划对偶问题的对偶是原问题。b若原问题第i个约束为等式，则其对偶问题中第i个变量为自由变量；反之，若原问题的第j个变量是自由变量，则其对偶问题的第j个约束为等式性质1：（弱对偶性）设X、Y分别是原问题（L）和对偶问题（D）的任一可行解，则CX≤Yb性质3：（无界性）如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。性质2：（最优性）设是原问题（L）的可行解，是对偶问题（D）的可行解，且，则、是各自问题的最优解。性质4：（强对偶性）如果原问题有最

2、优解，则其对偶问题也一定具有最优解，且有maxz=minw。性质5：（互补松驰性）在线性规划问题的最优解中，如果对应某一约束条件的对偶变量为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：性质6：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。4影子价格4影子价格4影子价格5

3、对偶单纯形法5对偶单纯形法5对偶单纯形法5对偶单纯形法5对偶单纯形法cj-12-8-16-1200cBxBbx1x2x3x4x5x60x5-2-2-1-40100x6-3-2-20[-4]01检验数00-1/2-5/40x5-2-2[-1]-4010-12x43/41/21/2010-1/4检验数-6-2-1600-3-8x222140-10-12x4-1/4[-1/2]0-211/2-1/4检验数-20-80-2-3-8x2101-441-1-12x11/2104-2-11/2检验数000-4-4-25对偶单纯形法6灵敏度分析6灵敏

4、度分析6灵敏度分析6灵敏度分析例：某工厂生产Ⅰ、Ⅱ两种型号计算机，为了生产一台Ⅰ型和Ⅱ型计算机，所需要原料分别为2和3个单位，需要的工时分别为4和2个单位。在计划期内可以使用的原料为100个单位，工时为120个单位。已知生产每台Ⅰ、Ⅱ型计算机可获得利润分别为6和4个单位，试确定获利最大的生产方案。6灵敏度分析已知例题的最优解及最优值如下：cj6400cBxBbx1x2x3x40x310023100x41204201检验数6400cj6400cBxBbx1x2x3x44x220011/2-1/46x12010-1/43/8检验数00-1

5、/2-5/4最初的单纯形表如下6灵敏度分析6灵敏度分析cj12400cBxBbx1x2x3x44x220011/2-1/412x12010-1/43/8检验数001-7/2cj12400cBxBbx1x2x3x40x340021-1/212x13011/201/4检验数0-20-36灵敏度分析6灵敏度分析已知例题的最优解及最优值如下：cj6400cBxBbx1x2x3x40x310023100x41204201检验数6400cj6400cBxBbx1x2x3x44x220011/2-1/46x12010-1/43/8检验数00-1/2

6、-5/46灵敏度分析cj6400cBxBbx1x2x3x40x310023100x41204201检验数6400cj6400cBxBbx1x2x3x44x220011/2-1/46x12010-1/43/8检验数00-1/2-5/4=(N,E)6灵敏度分析6灵敏度分析cj6400cBxBbx1x2x3x44x22070011/2-1/46x120-510[-1/4]3/8检验数00-1/2-5/4cj6400cBxBbx1x2x3x44x2602101/20x320-401-3/2检验数-200-2最优解：(0,60,20-原料剩余,

7、0-工时剩余)最优值：z=240