运筹学胡运权清华版302表上作业法课件.ppt

《运筹学胡运权清华版302表上作业法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二、最优性检验检验原则（Min）所有检验数都≥0时最优检验数的计算方法1——闭回路法方法2——对偶变量法（位势法）1闭回路法闭回路——从一个无圈格出发，沿水平（或垂直）方向前进，遇到适当的带圈格转直角弯，再沿水平（或垂直）方向前进，如此下去，最后回到出发格，从而得到一条闭回路。（全部由水平或垂直线组成）注1：从每个无圈格出发，有且仅有一条闭回路注2：不存在全部由带圈格构成的闭回路销地产地B1B2B3B4产量A116A210A322销量814121448412411210398561182101486X11格的闭回路与检验

2、数若x11为入基变量，x11增加1，运费的变化为4-4+3-2=1。这个变化就是x11的检验数，故σ11=4-4+3-2=1销地产地B1B2B3B4产量A116A210A322销量814121448412411210398561182101486σ12=12-11+6-5=2X12格的闭回路与检验数销地产地B1B2B3B4产量A116A210A322销量814121448412411210398561182101486σ22=10-3+4-11+6-5=1X22格的闭回路与检验数闭回路法求检验数结果销地产地B1B2B3B

3、4产量A116A210A322销量814121448412411210398561182101486121-11012非最优检验数的计算对于带圈格，求解ui,vj:ui+vj=cij指定某一个ui或vj＝02)对于无圈格，计算检验数位势2位势法分析：m+n个约束－m+n个对偶变量基变量检验数＝0对所有带圈格，有方程个数＝m＋n－1未知量个数＝m＋n自由变量1个任选一个ui或vj＝0带圈格总数m+n－1销地产地B1B2B3B4uiA1u1=A2u2=A3u3=vjv1=v2=v3=v4=412411210398561182

4、1014866个方程7个未知数，不妨设u2＝0计算位势位势销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=－4vjv1=2v2=9v3=3v4=10412411210398561182101486销地产地B1B2B3B4uiA1u1=A2u2=A3u3=vjv1=v2=v3=v4=412411210398561182101486表上计算位势销地产地B1B2B3B4uiA1u1=A2u2=0A3u3=vjv1=v2=v3=v4=412411210398561182101486u2+v1=c21销地产地B1B2

5、B3B4uiA1u1=A2u2=0A3u3=vjv1=2v2=v3=v4=412411210398561182101486u2+v3=c23销地产地B1B2B3B4uiA1u1=A2u2=0A3u3=vjv1=2v2=v3=3v4=412411210398561182101486u1+v3=c13销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=vjv1=2v2=v3=3v4=412411210398561182101486u1+v4=c14销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=vjv

6、1=2v2=v3=3v4=10412411210398561182101486u3+v4=c34销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=-4vjv1=2v2=v3=3v4=10412411210398561182101486u3+v2=c32销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=-4vjv1=2v2=9v3=3v4=10412411210398561182101486计算非基变量检验数销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=-4vjv1=2v2=9v3=

7、3v4=10412411210398561182101486c11-u1-v1销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=-4vjv1=2v2=9v3=3v4=10412411210398561182101486c12-u1-v21销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=-4vjv1=2v2=9v3=3v4=10412411210398561182101486c22-u2-v212销地产地B1B2B3B4uiA1u1=1A2u2=0A3u3=-4vjv1=2v2=9v3=3v4=1

8、0412411210398561182101486121-11012非最优3闭回路法与位势法比较当产地和销地数目比较多时，采用位势法计算检验数比闭回路法简单。