川大《运筹学》课件-4整数规划.ppt

《川大《运筹学》课件-4整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹帷幄之中决胜千里之外运筹学课件整数线性规划IntegerLinearProgramming1第一节整数规划问题的特点及应用2在整数规划模型中，逻辑变量起着很大的作用，下面说明逻辑变量的应用：34567第二节割平面法问题：8解：用割平面法。1。先解去掉取整条件的线性规划问题2x25/2011/2-1/23x113/410-1/43/4cj3200cj-zj00-1/4-5/4cBxBbx1x2x3x4设其最终单纯形表为92。找出非正数解变量中分数部基变量（此处为x2），并写出这一行的约束将上式中所

2、有常数写成正数和一个正分数之和分数项移到右边，整数项移到左边10由于左边为整数，所以右边也为整数，所以所以由于加入松弛变量放入单纯形表1112由上表用同样的方法，得放入单纯形表，得1314得最优解15第三节分枝定界法1617Maxz=14.47059x1=3.705882,x2=2.352941Maxz=14,x1=3,x2=2.66667Maxz=14.42857x1=4,2=2.142857Maxz=12x1=3,x2=2Maxz=13.5x1=2.25,x2=3Maxz=14.4x1=4.2,

3、x2=2无解x1≤3x1≥4x2≤2x2≥3××x2≤2x2≥318Maxz=12x1=6,x2=0Maxz=14x1=4,x2=2Maxz=14.28571x1=5,x2=1.428571Maxz=14.2x1=5.6,x2=1无解Maxz=13x1=5,x2=1Maxz=14.14286x1=6,x2=0.714286x1=4x1≥5x2≤1x2=2x1=5x1≥6x2=0x2=1××Maxz=14.4x1=4.2,x2=2无解19分配（指派）问题与匈牙利法指派问题的数学模型一般形式如下：202

4、1例：有一份说明书，分别译成英、日、德、俄四种语言，现打算交给甲、乙、丙、丁四人完成。因各人专长不同，他们完成翻译不同文字所需的时间如下表所示，应如何分配，才使这四个人分别完成这四项任务总的时间为最小。甲乙丙丁译英文21097译日文154148译德文13141611译俄文41513922匈牙利法：23定理2:若矩阵A的元素可分为“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。证明:设覆盖全部“0”元素的最少直线数是m，位于不同行不同列的“0”元素M个。

5、覆盖M个中的每一个“0”元素至少需要一条直线，所以m>M。下证m

6、且这些0不位于j1,…jc列上。同理，可证在c条列线上存在不少于c个位于不同行的0，且这些0不位于i1,…ir行上。若上述两部分的0的个数之和是S，则25解:匈牙利法求解过程如下:26各行减去最小的元素各列减去最小的元素27十字交叉线上除它本身外，无其它0元十字交叉线上除它本身外，其它0元的个数为1。2829第一列出现负值后，该列加上最小值2。3031显然可将效率矩阵提出一个公因子100，得到等价的效率矩阵:然后对这个效率矩阵用匈牙利法求解即可。3233甲乙丙丁戊仰泳37.732.933.83735

7、.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.134解：该问题可看作指派问题。添加一个虚拟项目，得到如下效率矩阵甲乙丙丁戊仰泳37.732.933.83735.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1虚拟00000等价化简→35甲乙丙丁戊仰泳4.800.94.12.5蛙泳10.309.11.68.7√蝶泳4.8010

8、.41.95.1√自由泳2.803.22.14.7√虚拟00000√→……,最后的效率矩阵为36甲乙丙丁戊仰泳3.91.904.11.6蛙泳7.80.36.606.2蝶泳207.602.3自由泳000.40.21.9虚拟02.800.9037作业381，分配甲、乙、丙、丁四个人完成ABCDE五项任务，每个人完成各项任务的时间如表所示：ABCDE甲2529314237乙3938262033丙3427284032丁2442362345由于任务多于人数，故考虑：（a）任务E