运筹学教学-整数规划.ppt

《运筹学教学-整数规划.ppt》由会员分享，可在线阅读，更多相关《运筹学教学-整数规划.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件整数线性规划整数线性规划Integer Linear ProgrammingInteger Linear Programming1第一节第一节 整数规划问题的特点及应用整数规划问题的特点及应用2在整数规划模型中，逻辑变量起着很大的作用，下在整数规划模型中，逻辑变量起着很大的作用，下面说明逻辑变量的应用：面说明逻辑变量的应用：34567应用案例应用案例n投资组合问题投资组合问题n旅游售货员问题旅游售货员问题n背包问题背包问题8投资组合问题投资组合问题n背背 景景n实实 例例n模模 型型9背背 景景n证

2、券投资证券投资：把一定的资金投入到合适的：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利有价证券上以规避风险并获得最大的利润。润。n项目投资项目投资：财团或银行把资金投入到若：财团或银行把资金投入到若干项目中以获得中长期的收益最大干项目中以获得中长期的收益最大。10案案 例例n某财团有某财团有 万元的资金，经出其考察选中万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其个投资项目，每个项目只能投资一个。其中第中第 个项目需投资金额为个项目需投资金额为 万元，预计万元，预计5年后获利年后获利 （）万元，问应如何）万元，问应如何选择项目使得选择项目使得5年后总收益最大？年

3、后总收益最大？11模模 型型n变量变量每每个项目是否投资个项目是否投资n约束约束总总金额不超过限制金额不超过限制n目标目标总收益最大总收益最大1213旅游售货员问题旅游售货员问题n背景背景n案例案例n模型模型14背背 景景n旅游线路安排旅游线路安排 预定景点走且只走一次预定景点走且只走一次 路上时间最短路上时间最短n配送线路配送线路货郎担问题货郎担问题 送货地到达一次送货地到达一次 总路程最短总路程最短15案案 例例n有一旅行团从有一旅行团从 出发要遍游城市出发要遍游城市 ，已知从，已知从 到到 的旅费为的旅费为 ，问应如何安排行程使总费用最，问应如何安排行程使总费用最小小？16模模 型型n变

4、量变量是是否从否从i第个城市到第第个城市到第j个城市个城市n约束约束 每个城市只能到达一次、离开一次每个城市只能到达一次、离开一次17n目标目标总总费用最小费用最小1819背包问题背包问题n背景背景n案例案例n模型模型20背背 景景n邮递包裹邮递包裹 把形状可变的包裹用尽量少的车辆运走把形状可变的包裹用尽量少的车辆运走n旅行背包旅行背包 容量一定的背包里装尽可能的多的物品容量一定的背包里装尽可能的多的物品21实实 例例n某人出国留学打点行李，现有三个旅行包，容某人出国留学打点行李，现有三个旅行包，容积大小分别为积大小分别为1000毫升、毫升、1500毫升和毫升和2000毫升，毫升，根据需要列出

5、需带物品清单，其中一些物品是根据需要列出需带物品清单，其中一些物品是必带物品共有必带物品共有7件，其体积大小分别为件，其体积大小分别为400、300、150、250、450、760、190、（单、（单位毫升）。尚有位毫升）。尚有10件可带可不带物品，如果不件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。方案把物品放在三个旅行包里。22物品物品123456

6、78910体积体积200350500430320120700420250100价格价格154510070507520090203023问题分析问题分析n变量变量对对每个物品要确定是否带同时要确定每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设的总容量就很难写

7、成变量的函数。为此我们设变量为变量为第第i个物品是否放在个物品是否放在第第j个包裹个包裹中中24n约束约束包裹容量限制包裹容量限制必带物品限制必带物品限制选带物品限制选带物品限制25n目标函数目标函数未未带物品购买费用最小带物品购买费用最小26模模 型型27第二节第二节 割平面法割平面法问题：问题：28解：用割平面法。解：用割平面法。1。先解去掉取整条件的线性规划问题。先解去掉取整条件的线性规划问题2x25/2011/2-1/23x113/410-1/43/4 cj3200 cj-zj00-1/4-5/4cBxBbx1x2x3x4设其最终单纯形表为设其最终单纯形表为292。找出非正数解变量中分

8、数部基变量（此处为。找出非正数解变量中分数部基变量（此处为x2），并写出这一行的约束），并写出这一行的约束将上式中所有常数写成正数和一个正分数之和将上式中所有常数写成正数和一个正分数之和分数项移到右边，整数项移到左边分数项移到右边，整数项移到左边30由于左边为整数，所以右边也为整数，所以由于左边为整数，所以右边也为整数，所以所以所以由于由于加入松弛变量加入松弛变量放入单纯形表放入单纯形表3132由上表用同样的方法，得由上表用同样的方法，得放入单纯形表，得放入单纯形表，得3334得最优解得最优解35第三节第三节 分枝定界法分枝定界法3637Max z=14.47059 x1=3.705882,x

9、2=2.352941Max z=14,x1=3,x2=2.66667Max z=14.42857x1=4,2=2.142857Max z=12x1=3,x2=2Max z=13.5x1=2.25,x2=3Max z=14.4x1=4.2,x2=2无解无解x13x14x22x23x22x2338Max z=12x1=6,x2=0Max z=14x1=4,x2=2Max z=14.28571x1=5,x2=1.428571Max z=14.2x1=5.6,x2=1无解无解Max z=13x1=5,x2=1Max z=14.14286x1=6,x2=0.714286x1=4x15x21x2=2x1=

10、5x16x2=0 x2=1Max z=14.4x1=4.2,x2=2无解无解39第四节第四节 01规划的隐枚举法规划的隐枚举法40414243可能的解可能的解Z是否是否满满足足约约束束是否可行是否可行解解备备注注x3x1x5x2x4000008否否000016否否000106否否001005是是010005否否000114是是停止停止44第五节第五节 分配（指派）问题与匈牙利法分配（指派）问题与匈牙利法指派问题的数学模型一般形式如下：指派问题的数学模型一般形式如下：4546例：有一份说明书，分别译成英、日、德、俄四种语例：有一份说明书，分别译成英、日、德、俄四种语言，现打算交给甲、乙、丙、丁四

11、人完成。因各人专言，现打算交给甲、乙、丙、丁四人完成。因各人专长不同，他们完成翻译不同文字所需的时间如下表所长不同，他们完成翻译不同文字所需的时间如下表所示，应如何分配，才使这四个人分别完成这四项任务示，应如何分配，才使这四个人分别完成这四项任务总的时间为最小。总的时间为最小。甲甲 乙乙 丙丙 丁丁译英译英文文 2 10 9 7译日译日文文 15 4 14 8译德译德文文 13 14 16 11译俄译俄文文 4 15 13 947匈牙利法：匈牙利法：48定理定理2:若矩阵若矩阵A的元素可分为的元素可分为“0”与非与非“0”两部分，两部分，则覆盖则覆盖“0”元素的最少直线数等于位于不同行不同列元

12、素的最少直线数等于位于不同行不同列的的“0”元素的最大个数。元素的最大个数。证明证明:设设覆盖全部覆盖全部“0”元素的最少直线数是元素的最少直线数是m，位于，位于不同行不同列的不同行不同列的“0”元素元素M个。个。覆盖覆盖M个中的每一个个中的每一个“0”元素至少需要一条直线，元素至少需要一条直线，所以所以mM。下证。下证mM。如图，假定覆盖所有如图，假定覆盖所有0元的元的M条直线有条直线有r行行（i1,i2,ir）c列列（j1,jc）,m=r+c.49显然在每一行上至少存在一个不在显然在每一行上至少存在一个不在j1,jc列上的列上的0，设某一行上这些不在设某一行上这些不在j1,jc列上的列上的

13、0元素下标集合元素下标集合对对i1,ir行分别有集合行分别有集合Si1,Sir。从这些集合中任意。从这些集合中任意取取k个（个（k=r）其集合中的不同元素个数必不小于）其集合中的不同元素个数必不小于k，否则这，否则这k行的直线可用少于行的直线可用少于k条列线代替，与条列线代替，与m是覆是覆盖盖0元素最少直线数的假定矛盾。所以在元素最少直线数的假定矛盾。所以在r条行线上存条行线上存在不少于在不少于r个位于不同列的个位于不同列的0，且这些，且这些0不位于不位于j1,jc列上。列上。同理，可证在同理，可证在c条列线上存在不少于条列线上存在不少于c个位于不同行的个位于不同行的0，且这些，且这些0不位于

14、不位于i1,ir行上。行上。若上述两部分的若上述两部分的0的个数之和是的个数之和是S，则，则50解解:匈牙利法求解过程如下匈牙利法求解过程如下:51 各各行行减减去去最最小小的的元元素素各各列列减减去去最最小小的的元元素素52十十字字交交叉叉线线上上除除它它本本身身外外，无其它无其它0元元十十字字交交叉叉线线上上除除它它本本身身外外，其其它它0元的个数为元的个数为1。5354第一列出现负值后，第一列出现负值后，该列加上最小值该列加上最小值2。5556显然可将效率矩阵提出一个公因子显然可将效率矩阵提出一个公因子100，得到等价的效，得到等价的效率矩阵率矩阵:然后对这个效率矩阵用匈牙利法求解即可。

15、然后对这个效率矩阵用匈牙利法求解即可。5758甲甲 乙乙 丙丙 丁丁 戊戊仰泳仰泳37.732.933.83735.4蛙泳蛙泳43.433.142.234.741.8蝶泳蝶泳33.328.538.930.433.6自由自由泳泳29.226.429.628.531.159解：该问题可看作指派问题。添加一个虚拟项目，得解：该问题可看作指派问题。添加一个虚拟项目，得到如下效率矩阵到如下效率矩阵 甲甲 乙乙 丙丙 丁丁 戊戊仰仰泳泳37.732.933.83735.4蛙蛙泳泳43.433.142.234.741.8蝶蝶泳泳33.328.538.930.433.6自自由由泳泳29.226.429.628.531.1虚虚拟拟00000等价化简等价化简60 甲甲乙乙丙丙 丁丁戊戊仰仰泳泳4.800.94.12.5蛙蛙泳泳10.309.11.68.7蝶蝶泳泳4.8010.41.95.1自自由由泳泳2.803.22.14.7虚虚拟拟0 0 0 0 0,最后的效率矩阵为最后的效率矩阵为 61甲甲乙乙丙丙丁丁戊戊仰泳仰泳3.91.904.11.6蛙泳蛙泳7.80.36.606.2蝶泳蝶泳207.602.3自由泳自由泳000.40.21.9虚虚拟拟02.800.9062