第二章整数规划03

1、第二章 整数规划2.1 整数规划的提出2.2 分枝定界法2.3 0-1整数规划2.4 指派问题2.5 整数规划的几个典型问题及其数学模型2014/3/27运筹学史慧萍22.1 整数规划的提出n一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。n整数线性规划的几种类型1.当要求全部变量取整数值的，称为纯整数规划(Pure Integer Programming，IP).2.要求一部分变量取整数值的，称为混合整数规划(Mixed Integer Programming，MIP).3.决策变量全部取0或1的规划称为01整数规划(Binary Integer Programming，

2、BIP).4.如果模型是线性的，称为整数线性规划（Integer Linear Programming, ILP）。 2014/3/27运筹学史慧萍3 例如1：某从事集装箱运输的公司，集装箱的标准是：体积24m3，净载重不超过13T。如果客户要求托运甲、乙两种货物，甲货物每箱体积为5m3，重量为2T；乙货物每箱体积为4m3，重量为5T，公司每运输一箱甲货物的利润是2000元，每运输一箱乙货物的利润是1000元。该公司怎样在充分利用集装箱空间和承重的能力下，获得最大的利润？ 解：设甲、乙两种货物的托运箱数为x1、x2,则规划模型的表达式如下：且为整数; 0,1352244510002000max

3、21212121xxxxxxstxxz2014/3/27运筹学史慧萍4整数规划问题的图解法且为整数; 0,1352244510002000max21212121xxxxxxstxxz(0,6)(4.8,0)(0,2.6)(6.5,0)x1x2C点线性规划最优解(4.8,0)，值为z=9600B点整数规划最优解(4,1)，值为z=90005x1+4x2=242x1+5x2=13A点 (4,0)，值为z=80002014/3/27运筹学史慧萍5整数线性规划数学模型的一般形式 松弛问题：不考虑取整数条件，由余下的目标函数和约束条件构成的规划问题成为该整数规划问题的松弛问题。1c)-(2 ,1b)-(

4、2 , 2 , 1, 01a)-(2 , 2 , 1,),(1)-(2 )(2111中部分或全部取整数或或或njnjijijnjjjxxxnjxmibxastxczminmax2014/3/27运筹学史慧萍62.2 分枝定界法n分枝定界法是20世纪60年代由Land Doig和Dakin等人提出的。n其基本思想是根据某种策略将原问题的可行区域分解为越来越小的子域，并检查每个子域内整数解的情况，直到找到最优的整数解或证明整数解不存在。2014/3/27运筹学史慧萍7分枝的定义 所谓分枝：若整数规划的松弛问题的最优解不符合整数的要求，假设xjbj不符合整数的要求，bj是不超过bj的最大整数，则构造

5、两个约束条件xjbj ， xj bj1，分别将其并入整数规划的松弛问题中，从而形成两个分支，即两个后继问题。两个后继问题的可行域中包含原整数规划的问题的所有可行解。而在原问题中，满足 bj xjbj1的一部分区域在以后的求解过程中被遗弃了，然而它不包含整数规划的任何可行解。根据需要，各后继问题可以类似的产生自己的分支，即自己的后继问题。如此不断继续，直到获得整数规划的最优解。2014/3/27运筹学史慧萍8定界的定义 指在分枝过程中，若某个后继问题恰巧获得整数规划的一个可行解，那么，它的目标值就是一个“界限” ，可以作为衡量处理其他分枝的一个依据。因为整数规划问题的可行集是它的松弛问题可行集的

6、一个子集，前者最优解的目标函数值不会优于后者最优解的目标函数值。所以，对于那些相应松弛问题最优解的目标函数值比上述“界限” 差的后继问题，就可以剔除而不再考虑了。如果在以后的分枝过程中出现更好的“界限” ，则可以用它来取代原来的“界限” ，这样可以提高定界的效果。2014/3/27运筹学史慧萍9 分枝定界法要不断应用分枝、定界、估界来进行判断。当我们求解某子问题的松弛问题时，只要出现下列情况之一，该问题就已探明：n(1) 松弛问题没有可行解，则原问题也没有可行解；n(2) 松弛问题的最优解恰好全取整数，则该最优解也是其对应的子问题的最优解；n(3) 松弛问题的最大值（对于目标函数为最大值的整数

7、规划）小于现有的下界z，则无论其最优解是否取整数值，都将对应的子问题剪枝；（目标函数为最小值的整数规划类似）n 已探明的子问题就不再用分枝了，如果所有的子问题都已探明，则原整数规划的最优解就一定可以求出，或可以判定它无解。2014/3/27运筹学史慧萍10注意：1.求解整数规划所对应的线性规划松弛问题时就得到了一个整数解，这个解一定是整数规划的最优解；2.求解整数规划所对应的线性规划松弛问题时得到的解不是一个整数解，最优解的值一定不会优于所得到的线性规划松弛问题的目标函数值；3.在求解过程中，已经找到了一个整数解，则最优解的值一定不会劣于该整数解。2014/3/27运筹学史慧萍11设Z0表示松

8、弛问题的解值；Zi表示已经找到的最好整数解的值；Z*表示最优整数解的值；中部分或全部取整数或或或njnjijijnjjjxxxnjxmibxastxczminmax, 2 , 1, 0, 2 , 1,),()(2111iiZZZZZZZZZZZZZ*00*对于最小问题：对于最大问题：一定满足一下关系：表示下界，则最优解表示上界2014/3/27运筹学史慧萍12 例1解：设甲、乙两种货物的托运箱数为x1、x2,则规划模型的表达式如下：LP问题的最优解：x14.8，x20,z9600且为整数; 0,1352244510002000max21212121xxxxxxstxxz0,1352244510

9、002000max21212121xxxxxxstxxz松弛问题IP问题LP问题9600Z0Zx14.8,得到两个约束条件： x14.8=4, x14.8+1=5,2014/3/27运筹学史慧萍13将两个约束条件加到IP问题中： x14.8=4, x14.8+1=5,得到两个子问题： IP1问题 IP1问题且为整数; 0,51352244510002000max211212121xxxxxxxstxxz且为整数; 0,41352244510002000max211212121xxxxxxxstxxz找到的最好的整数解0ZIP1问题的松弛问题LP1最优解：无可行解IP1问题的松弛问题LP1最优解

10、：x14，x21，z90009000Z比较IP及IP1上界改进为9600Z所以IP最优解：x14，x21，z90009000Z90009000*ZZZ2014/3/27运筹学史慧萍14整数规划问题分枝界定的图解法(0,6)(4.8,0)(0,2.6)(6.5,0)x1x2且为整数; 0,1352244510002000max21212121xxxxxxstxxzLP可行域x14的分枝的可行域x15 的分枝无可行域LP1无可行解LP1Z=9000X1=4X2=1LPZ=9600X1=4.8X2=0 x15 x142014/3/27运筹学史慧萍15LP1无可行解LP1Z=9000X1=4X2=1L

11、PZ=9600X1=4.8X2=0解整数规划的框图流程x15 x149600, 0ZZ90009000900090009000*ZZZZZZZZ找到的最好整数解，作为下界松弛问题的解，作为上界松弛问题的解，作为上界2014/3/27运筹学史慧萍16求解下例IP问题(图解法)(0,8)0 ,926()213 , 0(10,0)且为整数; 0,7020756799040max21212121xxxxxxstxxz解整数规划的框图流程LPZ=356x1=4.81x2=1.82LP1Z=349x1=4x2=2.1LP1Z=341x1=5x2=1.57LP2Z=340 x1=4x2=2LP2Z=327x

12、1=1.42x2=3LP3Z=308x1=5.44x2=1LP3无可行解 x14 x15 x22 x23 x21 x222014/3/27运筹学史慧萍17求解下例IP问题解整数规划的框图流程341, 0ZZ且为整数; 0,7020756799040max21212121xxxxxxstxxzLP2Z=340X1=4.00X2=2.00LP2Z=327X1=1.42X2=3.00LP1Z=349X1=4.00X2=2.10LP3Z=308X1=5.44X2=1.00LP3无可行解LP1Z=341X1=5.00X2=1.57LPZ=356X1=4.81X2=1.82x14 x15x22 x23x2

13、1 x22356, 0ZZ349, 0ZZ340Z340340*ZZZ找到的最好整数解，作为下界松弛问题的解值的值，作为上界2014/3/27运筹学史慧萍182.3 0-1整数规划 各类决策问题中常遇到：是否执行某些问题或活动；在什么时间或地点执行决策等问题。回答这类“是与否” 或“有与无” 的问题可借助整数规划中的0-1变量。 0-1变量的一般表示方式为：否如果决策为：是，如果决策jjxj , 0 12014/3/27运筹学史慧萍19例：某公司有5个项目列入投资计划，各项目的投资额和期望的投资收益见下表： 该公司只有600万元可用于投资，由于技术上的原因，投资受到以下约束：1.在项目1、2和

14、3中必须只有一项被选中；2.在项目3和4中只能选中一项；3.项目5选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，是投资收益最大？项目投资额投资收益1210160230021031506041308052601802014/3/27运筹学史慧萍205 , 4 , 3 , 2 , 11011600260130150300210. .18080602101605 , 4 , 3 , 2 , 1, 01 15433215432154321ixxxxxxxxxxxxxtsxxxxxmaxziiixii，或则未被选中项目被选中，项目解：设只有600万元可用于投资在项目1、2和3中必

15、须只有一项被选中在项目3和4中只能选中一项项目5选中的前提是项目1必须被选中2014/3/27运筹学史慧萍21n最优解：投资项目1，4，5。可获投资收益420万元。2014/3/27运筹学史慧萍22例：求解下面的0-1型整数规划321, 10 64 34422523max3221321321321，或 ixxxxxxxxxxxstxxxzi2014/3/27运筹学史慧萍23解法一：1.可行解(x1, x2, x3 )(1,0,0) 目标函数z 312050 3。2.增加一个约束条件 3x12x25x23321, 1035236434422523max3213221321321321，或 ixx

16、xxxxxxxxxxxxstxxxzi找到的的整数解为最大化的下界，称为过滤条件。2014/3/27运筹学史慧萍240-1型整数规划计算表点(x1, x2, x3)约束条件的左侧的值满足条件?是否z值(0,0,0)0(0,0,1)5-11015(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)802118(1,1,0)1(1,1,1)6隐枚举法：共计算16次，全枚举法：共计算32次(八个解，四个约束条件)。（最优解为1，0，1，最优值8）2014/3/27运筹学史慧萍25解法二：重新排列xj的顺序(max按系数递减)321, 106434422235max232121321321

17、3，或 ixxxxxxxxxxxstxxxzi321, 106434422523max3221321321321，或 ixxxxxxxxxxxstxxxzi2014/3/27运筹学史慧萍260-1型整数规划计算表目标函数z 3x12x25x3 5x33x12x2 最大值的上限是8，第二大的值是5点(x3, x1, x2)约束条件满足条件?是否z值(1,1,0)8 8隐枚举法：共计算5次(均满足约束条件)。 （最优解为1，0，1，最优值8）可根据计算逐渐改变过滤条件(该例因最大值的点满足其他四个约束，即找到最大化问题的最好的整数解。就不需验证计算第二大值的点是否满足约束条件)2014/3/27运

18、筹学史慧萍27例：求解下面的0-1型整数规划321, 1013344352234min21321321321，或 ixxxxxxxxxstxxxzi 2014/3/27运筹学史慧萍28解：系数按递增序列排列(min按系数递减) 因为xi取0或1，最小值下界点为(x3,x2,x1)=(0,0,0)，z值为0； 其次为 (x3,x2,x1)=(1,0,0)点， z值为2； 再次(x3,x2,x1)=(0,1,0)点， z值为3； 321, 10in32321321321，或 ixxxxxxxxxstxxxzi321, 10in2312312312

19、3，或 ixxxxxxxxxstxxxzi2014/3/27运筹学史慧萍290-1型整数规划计算表最优解为： (x1,x2,x3)=(0,0,1)最优值为：2点(x3, x2, x1)约束条件满足条件?是否z值过滤条件(0,0,0)0(1,0,0)22最小值0对应的点不满足 约束，改变过滤条件，再验证计算次小值2对应的点满足 约束，即找到最小化问题的最好的整数解。逐渐改变过滤条件2014/3/27运筹学史慧萍302.4 指派问题（assignment problem） 某单位需完成n项任务，恰好有n人可以承担，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或需总时间最小)。这类问题称

20、为指派问题。 如果完成任务的效率表现为资源消耗，考虑的是如何分配任务如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。考虑的是如何分配使得目标函数极大化。 在指派问题中，利用不同资源完成不同计划活动的效率通常用在指派问题中，利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成表格形式表示为效率表，表格中数字组成效率矩阵效率矩阵。2014/3/27运筹学史慧萍31指派问题的标准形式及其数学模型例：有A、B、C、D四项任

21、务需分派给甲、乙、丙、丁四个人去做，这四个人都能承担上述四项任务，但完成的时间如下表，问应如何分派任务可使完成四项任务的总工时最少？ 任务 人ABCD甲(第一人)917167乙(第二人)1271416丙(第三人)8171417丁(第四人)791192014/3/27运筹学史慧萍32效率矩阵引入n2个0-1变量xij，令项任务人去完成第，当不指派第项任务人去完成第，当指派第jijixij01nnnnnnnnijcccccccccC212222111211极小化数学模型：10, 2 , 1, 1, 2 , 1, 1. .min1111或ijnjijniijninjijijxnixnjxtsxczc

22、ij表示指派第i 个人去完成第j项任务时的效率（时间、成本等）2014/3/27运筹学史慧萍33模型特点n当工作数与人数相等时，含nn个变量，nn个约束方程，所有变量均为0-1变量。克尼格(Konig)定理n定理1 如果从分配问题效率矩阵cij的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj得到一个新的效率矩阵cij ，则以cij为效率矩阵的分配问题与以cij为效率矩阵的分配问题具有相同的最优解。n定理2 (覆盖原理) 若矩阵A的元素可分成“0“与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的 “0”元(独立的零元素)的最大个数。201

23、4/3/27运筹学史慧萍34指派问题的匈牙利解法(Hungarian method )解：引入42=16个0-1变量xij，令项任务人去完成第，当不指派第项任务人去完成第，当指派第jijixij01极小化数学模型：)4 , 3 , 2 , 1,( 104 , 3, 2 , 1, 14 , 3 , 2 , 1, 1911179min43214321444312414111jixixxxxjxxxxstxxxxxczijiiiijjjjijijij或 任务 人ABCD甲(第一人)917167乙(第二人)1271416丙(第三人)8171417丁(第四人)791192014/3/27运筹学史慧萍35

24、标准指派问题的解的矩阵形式0100100000100001 0010000101001000 0100000100101000XXX2014/3/27运筹学史慧萍36指派问题的匈牙利解法的步骤n1.变换效率(系数)矩阵，使其每行每列都出现零元素。画圈：由某行某列中零元素最少的行或列开始将零画上圆圈，同时画去该零元素所在行和列的其它零元素。n2.确定效率(系数)矩阵中独立的零元素（具有一组处于不同行又不同列的零元素）。 a.若独立的零元素的个数等于矩阵的阶数，则得到最优解。这时每行每列都有一个画上圆圈的零，其对应位置的xij=1,其余位置的xij=0。2014/3/27运筹学史慧萍37b.若独立

25、的零元素的个数少于矩阵的阶数，则可按下面的方法进行（覆盖原理：可找出覆盖零元素的最少直线数目的直线）：对没有画圈的零所在的行打“” ；在已打“” 的行中，对划去的零所在的列打“” ；在已打“” 的列中，对画圈的零所在的行打“” ；重复 ，直到再也不能找到可以打“” 的行或列为止；对没有打“”的行划一横线，对打“”的列划一垂线，这样就得到了所有覆盖零元素的最少直线数目的直线集合。2014/3/27运筹学史慧萍38n3.继续变换距阵。方法是在未被直线覆盖的元素中找出一个最小元素。对未被覆盖的元素所在行或列中减去一最小元素。这样，在未被直线覆盖的元素中必然会出现零元素，但同时却又使已被直线覆盖的元素

26、中出现负元素。为了消除负元素，只要对它们所在列或行中各元素都加上这一最小元素即可。返回步骤2。2014/3/27运筹学史慧萍39指派问题的匈牙利解法的步骤的关键是：n如何实现矩阵系数具有一组处于不同行又不同列的零元素(独立元素)，以保证所画的零元素的圈的个数等于矩阵的阶数。当每一行和每一列都有一个零元(独立元素)时，对应“0”的位置的xij=1，其余位置的xij=0，即得最优解。2014/3/27运筹学史慧萍40指派问题的匈牙利解法最优解为：20209290930505102449119717141781614712716179ijC24209690970509102(-7)(-7)(-8)(

27、-7)(-4)0100000100101000*Xx14=1, x22=1, x31=1, x43=1,其余xij=0 ,z=7+7+8+11=332014/3/27运筹学史慧萍41 例：某商业公司计划开办五家新商店。为了尽快建成营业，某商业公司决定由五家公司分别承建。已知建筑公司Ai（i=1,2,3,4,5）对新商店Bi（j=1,2,3,4,5）的建造费用报价为cij（i, j=1,2,3,4,5） ，见下表。商业公司应当对五家建筑公司怎样分配建造任务，才能使总的建造费用最少？ Bj cijAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56

28、9121062014/3/27运筹学史慧萍42解：设0-1变量则问题的数学模型为），（时不承建，当时承建，当5432101jiBABAxjijiij)5 , 4 , 3 , 2 , 1,( 105 , 4 , 3, 2 , 1, 15 , 4 , 3 , 2 , 1, 161084min5432154321555412515111jixixxxxxjxxxxxstxxxxxczijiiiiijjjjjijijij或2014/3/27运筹学史慧萍43指派问题的系数矩阵为61012961061476781296101417971215784C-4-7-6-6-6046304081012630371

29、020811340-1 -3043204050012320377108110302014/3/27运筹学史慧萍44对没有画圈的零所在的行打“” ；在已打“” 的行中，对划去零所在的列打“” ；在已打“” 的列中，对画圈的零所在的行打“” ；重复 ，直到再也不能找到可以打“” 的行或列为止；对没有打“”的行划一横线，对打“”的列划一垂线，这样就得到了所有覆盖零元素的最少直线数目的直线集合。043204050012320377108110302014/3/27运筹学史慧萍45n3.继续变换距阵。方法是在未被直线覆盖的元素中找出一个最小元素。对未被覆盖的元素所在行或列中减去这一最小元素。这样，在未被

30、直线覆盖的元素中必然会出现零元素，但同时却又使已被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在列或行中各元素都加上这一最小元素即可。返回步骤2。04320405001232037710811030043204050001211266018110301043214050101210266008110312014/3/27运筹学史慧萍46画圈：由某行某列中零元素最少的行或列开始将零画上圆圈，同时画去该零元素所在行和列的其它零元素。043214050101210266008110311000001000000010001000100*X最优解：3466697min55443122515

31、113xxxxxxCzijijij最优值：2014/3/27运筹学史慧萍47对零元素画圈的次序不同有可能影响结果043214050101210266008110312014/3/27运筹学史慧萍48对零元素画圈的次序不同有可能影响结果(覆盖零元素的最少直线数目=n说明什么？该例独立零元为多少？)04321405010121026600811031对没有画圈的零所在的行打“” ；在已打“” 的行中，对划去零所在的列打“” ；在已打“” 的列中，对画圈的零所在的行打“” ；重复 ，直到再也不能找到可以打“” 的行或列为止；对没有打“”的行划一横线，对打“”的列划一垂线，这样就得到了所有覆盖零元素的

32、最少直线数目的直线集合。2014/3/27运筹学史慧萍49指派问题的非标准型及其转化 匈牙利解法只适用于目标函数要求为最小和矩阵为方阵的条件1.目标函数要求为最大，其目标函数为（最优解：相同。最优值？）ninjijijxcz11maxninjijijxcz11)(min)()(min1111中的最大值一般可取注：ijninjijijninjijijcMxbxcMzbij为缩减矩阵2014/3/27运筹学史慧萍502.效率(系数)矩阵不是方阵 如果有m种设备指派完成n种任务，行数i=1，2，m；列数j=1，2，n，cij为费用。 n m，增添mn列 n m ，增添nm行 注：增添的列或增添的行的

33、cij =03.某人i不能够完成某项工作j。 引入充分大正数 M，令 cij = M 即可。 Bj cijAiB1B2BnA1c11c12c1nA2c21c22c2nAmcm1cm2cmn2014/3/27运筹学史慧萍51 例：某商业公司计划开办五家新商店。为了尽快建成营业，某商业公司决定选三家公司分别承建。已知建筑公司Ai（i=1,2,3）对新商店Bi（j=1,2,3,4,5）的建造费用报价为cij（i=1,2,3； j=1,2,3,4,5 ）见表。根据实际情况，可以允许每家建筑公司承建一家或二家商店，求使总费用最少的指派方案。 Bj cijAiB1B2B3B4B5A14871512A279

34、171410A36912872014/3/27运筹学史慧萍52解：设0-1变量则问题的数学模型为），（时不承建，当时承建，当543213 , 2 , 101jiBABAxjijiij)5 , 4 , 3 , 2 , 1,( 103, 2 , 1, 25 , 4 , 3 , 2 , 1, 17884min54321321353412315111jixixxxxxjxxxstxxxxxczijiiiiijjjijijij或2014/3/27运筹学史慧萍53解：指派问题的效率(系数)矩阵为B1 B2 B3 B4 B5781296101417971215784781296781296101417971

35、0141797125784125784B1 B2 B3 B4 B5A1 A2 A3A1 A1 A2 A2 A3A3 承建一家或二家2014/3/27运筹学史慧萍54指派问题的系数矩阵为078129607812960101417970101417970121578401215784B1 B2 B3 B4 B5 B6A1 A1 A2 A2 A3A3 引入虚事B62014/3/27运筹学史慧萍55078129607812960101714970101714970121578401215784000512000512039713039713057000057000-4 -8 -7 -8 -710051

36、2100512028602028602157000157000n最优解为：x11=1， x23=1， x36=1， x42=1， x55=1， x64=1，其余 xij=0。n最优值为：minz= 4x11 + 7x23+0 x36+9x42+7 x55+8 x64=35。2014/3/27运筹学史慧萍562.5 整数规划的几个典型问题及其数学模型n一、背包问题：设有n件物品准备装入背包内，其中第j件物品重aj，价值bj。问怎样选择物品装入包，才能使在总重量不超过C的条件下，总价值最大？), 1, 2 , 1( 10. .:210111nnjxCxatsxbmaxSnjjjxjnjjjnjjj

37、j或则该问题的数学模型为），（件物品不被选中，表示第件物品被选中，表示第解：设总价值总重量限制2014/3/27运筹学史慧萍57n二、设备购置问题：某厂拟用M元资金购买m种设备A1， A2， Am，其中设备Ai的单价为pi(i=1,2, ,m)。现有n个地点 B1， B2， ，Bn可装备这些设备，其中设备Bj处最多可装置bj台(j=1,2, ,n) 。预计将一台设备Ai置于处Bj可获利cij元，问如何购置这些设备，才能使预计总利润最大？为整数），（），（），（则该问题的数学模型为处的台数，装置于设备的台数，为购买设备解：设iijiijmijimijijnjiijminjijijjiijiiyx

38、njmiyxMypnjbxmiyxtsxcmaxSBAxAy,21;210, 021210. .:11111各处安装设备Ai的台数总和不超过购买Ai的台数Bj处安装的最多台数总和为bj台总的资金限额总利润2014/3/27运筹学史慧萍58分析：yi为购买设备Ai的台数，xij为设备Ai装置于Bj处的台数。 地点 单位利润设备B1B2B3 Bn各设备的单位费用A1c11c12c13c1np1A2 c21c22c23c2np2 Amcm1cm2cm3cmnpm各地总台数b1b2b3bn2014/3/27运筹学史慧萍59n三、投资问题：设某部门在n年计划期内进行投资，各年的投资额为bj(j=1,2,

39、n)，现有m个不同的投资项目Bi可供选择。如果第i个投资项目在第j年所需投资为cij，第i个项目Bi的资金回收率为di，问如何在预算范围内，可使总的资金回收额最大？), 2 , 1( 10), 2 , 1(. .)()( :2101111mixnjbxctscxdmaxSjimiBBxjmijiijminjijiiiii或为计划期的各年为投资项目，则该问题的数学模型为），（，选择项目，选择项目解：设第i个项目在第1至n年的投资额m个投资项目在第1至n年的回收资金总额m个投资项目在第j年的投资额资金限额2014/3/27运筹学史慧萍60分析： 年份 投资额度投资项目123 n各项目资金回收率1c

40、11c12c13c1nd12 c21c22c23c2nd2 mcm1cm2cm3cmndm各年的总投资额度b1b2b3bn)( ), 2 , 101为计划期的各年为投资项目，（，选择项目，选择项目jimiBBxiii2014/3/27运筹学史慧萍61n四、选址问题：某种商品有n个销地，各销地的需求量分别为bj吨/天(j=1,2,n)。现拟在m个地点选址建厂，生产这种商品，规定一址最多只能建一个工厂。若选i址建厂，将来生产能力为ai吨/天，固定费用为di元/天(i=1,2,m)。已知i址至销地的运价为cij元/吨，问如何选择厂址和安排调运，才能使总费用最少？10, 0), 2 , 1(), 2

41、, 1(. .)( :)/(210111111或为销地为厂址为，则该问题的数学模型天吨的运量址到销地为从），（址建厂，不在址建厂，若在解：设iijmijijnjiiijmiiiminjijijijiyxnjbxmiyaxtsydxcminSjijixmiiiy运费与建厂费用i厂址生产的产品运到各销地的总和小于该厂址i生产产品的总数各个厂址生产的产品运到销地j的总数等于销地j的需求2014/3/27运筹学史慧萍62分析: 销地 单位运价产地123 n各产地的生产能力（吨/天）固定费用为(元/天)1c11c12c13c1na1d12 c21c22c23c2na2d2 mcm1cm2cm3cmnam

42、dm各销地的需求量b1b2b3bn);()/(2101为销地为厂址，天吨的运量址到销地为从），（址建厂，不在址建厂，若在jijixmiiiyiji2014/3/27运筹学史慧萍630-1型整数规划中特殊约束的处理1.互斥的约束 1）矛盾的约束 2）多种选一的约束 3）右边选择取值2.逻辑关系约束2014/3/27运筹学史慧萍641.互斥的约束1）矛盾的约束可引入一个0-1整数变量y，设M为充分大的正数。形式如下： 约束条件起作用，约束条件起作用，注：)52(0)42(1y )32( 0)( )22( 05)(xfxf )52( )( )42( )1 (5)(MyxfyMxf2014/3/27运

43、筹学史慧萍65n例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润及托运受限制如下表，问各托运多少箱，可是获得利润最大？货物体积每箱(米3)重量每箱(百斤)利润每箱(百元)甲5220乙4510托运限制2415且为整数划模型为：的托运箱数，则整数规分别为甲、乙两种货物解：设; 0,13522445 1020max ,2121212121xxxxxxstxxzxx2014/3/27运筹学史慧萍66n今设有车运和船运两种方式，如船运时关于体积的限制条件为n则两条件是互相排斥的，应该将他们怎样统一在同一个问题中？453721 xx)2( 4537) 1 (24452121xx xx12120-10 1 (1)(2)5424 (3)7345(1) (4)0(3)(1) (4)1(4)(2) (3)yxxyMxxy Myy为了