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

第,*,页,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运 筹 学 课 件,整数线性规划,Integer Linear Programming,1,第一节 整数规划问题的特点及应用,2,在整数规划模型中，逻辑变量起着很大的作用，下面说明逻辑变量的应用：,3,4,5,6,7,应用案例,投资组合问题,旅游售货员问题,背包问题,8,投资组合问题,背 景,实 例,模 型,9,背 景,证券投资,：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。,项目投资,：财团或银行把资金投入到若干项目中以获得中长期的收益最大,。,10,案 例,某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计,5,年后获利 （）万元，问应如何选择项目使得,5,年后总收益最大？,11,模 型,变量,每,个项目是否投资,约束,总,金额不超过限制,目标,总收益最大,12,13,旅游售货员问题,背景,案例,模型,14,背 景,旅游线路安排,预定景点走且只走一次,路上时间最短,配送线路,货郎担问题,送货地到达一次,总路程最短,15,案 例,有一旅行团从 出发要遍游城市,，已知从 到 的旅费为 ，问应如何安排行程使总费用最小,？,16,模 型,变量,是,否从,i,第个城市到第,j,个城市,约束,每个城市只能到达一次、离开一次,17,目标,总,费用最小,18,19,背包问题,背景,案例,模型,20,背 景,邮递包裹,把形状可变的包裹用尽量少的车辆运走,旅行背包,容量一定的背包里装尽可能的多的物品,21,实 例,某人出国留学打点行李，现有三个旅行包，容积大小分别为,1,000,毫升、,1,500,毫升和,2,000,毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有,7,件，其体积大小分别为,400,、,300,、,150,、,250,、,450,、,760,、,190,、（单位毫升）。尚有,10,件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,22,物品,1,2,3,4,5,6,7,8,9,10,体积,200,350,500,430,320,120,700,420,250,100,价格,15,45,100,70,50,75,200,90,20,30,23,问题分析,变量,对,每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为,第,i,个物品是否放在,第,j,个包裹,中,24,约束,包裹容量限制,必带物品限制,选带物品限制,25,目标函数,未,带物品购买费用最小,26,模 型,27,第二节 割平面法,问题：,28,解：用割平面法。,1,。先解去掉取整条件的线性规划问题,2,x2,5/2,0,1,1/2,-1/2,3,x1,13/4,1,0,-1/4,3/4,c,j,3,2,0,0,c,j,-z,j,0,0,-1/4,-5/4,c,B,x,B,b,x,1,x,2,x,3,x,4,设其最终单纯形表为,29,2,。找出非正数解变量中分数部基变量（此处为,x2,），并写出这一行的约束,将上式中所有常数写成正数和一个正分数之和,分数项移到右边，整数项移到左边,30,由于左边为整数，所以右边也为整数，所以,所以,由于,加入松弛变量,放入单纯形表,31,32,由上表用同样的方法，得,放入单纯形表，得,33,34,得最优解,35,第三节 分枝定界法,36,37,Max,z,=14.47059,x,1,=3.705882,x,2,=2.352941,Max,z,=14,x,1,=3,x,2,=2.66667,Max,z,=14.42857,x,1,=4,2,=2.142857,Max,z,=12,x,1,=3,x,2,=2,Max,z,=13.5,x,1,=2.25,x,2,=3,Max,z,=14.4,x,1,=4.2,x,2,=2,无解,x,1,3,x,1,4,x,2,2,x,2,3,x,2,2,x,2,3,38,Max,z,=12,x,1,=6,x,2,=0,Max,z,=14,x,1,=4,x,2,=2,Max,z,=14.28571,x,1,=5,x,2,=1.428571,Max,z,=14.2,x,1,=5.6,x,2,=1,无解,Max,z,=13,x,1,=5,x,2,=1,Max,z,=14.14286,x,1,=6,x,2,=0.714286,x,1,=4,x,1,5,x,2,1,x,2,=2,x,1,=5,x,1,6,x,2,=0,x,2,=1,Max,z,=14.4,x,1,=4.2,x,2,=2,无解,39,第四节,0,1,规划的隐枚举法,40,41,42,43,可能的解,Z是否满足约束,是否可行解,备注,x,3,x,1,x,5,x,2,x,4,0,0,0,0,0,8,否,0,0,0,0,1,6,否,0,0,0,1,0,6,否,0,0,1,0,0,5,是,0,1,0,0,0,5,否,0,0,0,1,1,4,是,停止,44,第五节 分配（指派）问题与匈牙利法,指派问题的数学模型一般形式如下：,45,46,例：有一份说明书，分别译成英、日、德、俄四种语言，现打算交给甲、乙、丙、丁四人完成。因各人专长不同，他们完成翻译不同文字所需的时间如下表所示，应如何分配，才使这四个人分别完成这四项任务总的时间为最小。,甲,乙,丙,丁,译英文,2,10,9,7,译日文,15,4,14,8,译德文,13,14,16,11,译俄文,4,15,13,9,47,匈牙利法：,48,定理,2:,若矩阵,A,的元素可分为“,0”,与非“,0”,两部分，则覆盖“,0”,元素的最少直线数等于位于不同行不同列的“,0”,元素的最大个数。,证明,:,设,覆盖全部“,0”,元素的最少直线数是,m,，位于,不同行不同列的“,0”,元素,M,个。,覆盖,M,个中的每一个“,0”,元素至少需要一条直线，所以,mM,。下证,mM,。,如图，假定覆盖所有,0,元的,M,条直线有,r,行（,i,1,i,2,i,r,）,c,列（,j,1,j,c,）,m=,r+c,.,49,显然在每一行上至少存在一个不在,j1,j,c,列上的,0,，设某一行上这些不在,j,1,j,c,列上的,0,元素下标集合,对,i,1,i,r,行分别有集合,S,i1,S,ir,。从这些集合中任意取,k,个（,k=r,）其集合中的不同元素个数必不小于,k,，否则这,k,行的直线可用少于,k,条列线代替，与,m,是覆盖,0,元素最少直线数的假定矛盾。所以在,r,条行线上存在不少于,r,个位于不同列的,0,，且这些,0,不位于,j,1,j,c,列上。,同理，可证在,c,条列线上存在不少于,c,个位于不同行的,0,，且这些,0,不位于,i,1,i,r,行上。,若上述两部分的,0,的个数之和是,S,，则,50,解,:,匈牙利法求解过程如下,:,51,各行减去最小的元素,各列减去最小的元素,52,十字交叉线上除它本身外，无其它,0,元,十字交叉线上除它本身外，其它,0,元的个数为,1,。,53,54,第一列出现负值后，该列加上最小值,2,。,55,56,显然可将效率矩阵提出一个公因子,100,，得到等价的效率矩阵,:,然后对这个效率矩阵用匈牙利法求解即可。,57,58,甲,乙,丙,丁,戊,仰泳,37.7,32.9,33.8,37,35.4,蛙泳,43.4,33.1,42.2,34.7,41.8,蝶泳,33.3,28.5,38.9,30.4,33.6,自由泳,29.2,26.4,29.6,28.5,31.1,59,解：该问题可看作指派问题。添加一个虚拟项目，得到如下效率矩阵,甲,乙,丙,丁,戊,仰泳,37.7,32.9,33.8,37,35.4,蛙泳,43.4,33.1,42.2,34.7,41.8,蝶泳,33.3,28.5,38.9,30.4,33.6,自由泳,29.2,26.4,29.6,28.5,31.1,虚拟,0,0,0,0,0,等价化简,60,甲,乙,丙,丁,戊,仰泳,4.8,0,0.9,4.1,2.5,蛙泳,10.3,0,9.1,1.6,8.7,蝶泳,4.8,0,10.4,1.9,5.1,自由泳,2.8,0,3.2,2.1,4.7,虚拟,0,0,0,0,0,最后的效率矩阵为,61,甲,乙,丙,丁,戊,仰泳,3.9,1.9,0,4.1,1.6,蛙泳,7.8,0.3,6.6,0,6.2,蝶泳,2,0,7.6,0,2.3,自由泳,0,0,0.4,0.2,1.9,虚拟,0,2.8,0,0.9,0,62,