运筹学五章(整数规划)课件.ppt

1、运筹学 管理科学与工程系 经济与管理学院第五章 整数规划5.1 5.1 整数规划数学模型和解的特点整数规划数学模型和解的特点5.2 5.2 割平面法和分支定界法割平面法和分支定界法5.3 0-15.3 0-1整数规划整数规划5.4 5.4 隐枚举法隐枚举法5.5 5.5 匈牙利法匈牙利法本章学习要求p熟悉分支定界法和割平面法的原理及其应用p掌握求解0-1规划问题的隐枚举法p掌握求解指派问题的匈牙利法5.1整数规划数学模型和解的特点整数规划数学模型和解的特点n整数规划的类型整数规划的类型n整数规划的数学模型实例整数规划的数学模型实例n整数规划解的特点整数规划解的特点1.整数线性规划（整数线性规划

2、（ILP）的类型）的类型线性规划模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20整数规划模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20 x1,x2 为整数0 1 2 3 4 5 6 7 84321A(2.6,3.8)B(5,3)2.整数线性规划（整数线性规划（ILP）实例）实例线性规划的最优解A(x1,x2)=(2.6,3.8)不是整数解，目标函数值为z=17.8。整数规划的最优解B(x1,x2)=(5,3)目标函数值为z=17。线性规划最优解A(2.6,3.8)四舍五入得到的解为(3,4)，不是可行

3、解；舍去尾数取整的解为(2,3)，目标函数值z=14。因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。0 1 2 3 4 5 6 7 84321A(2.6,3.8)B(5,3)3.整数线性规划（整数线性规划（ILP）解的特点）解的特点5.2 割平面法和分支定界法割平面法和分支定界法n割平面法（割平面法（Gomory法）法）n分支定界法分支定界法1.割平面法割平面法1.割平面法割平面法ikikibxaxbibikikikifNxfNx)(bikikfxf1.割平面法割平面法且为整数,4,1,020546242132121jxxxxxxxxxMaxZjCj1100CBXBbx1x

4、2x3x40 x3621100 x4204501j1100 35x1入 x3出1x1311/21/200 x4803-21j01/2-1/20 68/3x2入 x4出1x28/301-2/3 1/31x15/3105/6-1/6j00-1/6-1/6356165431xxx32)1(3265654143xxxx5456543xxx54)2(54545435xxxxcj11000CBXBbx1x2x3x4x51X15/3105/6-1/601X28/301-2/3 1/300 x500-5/6-5/61j00-1/6-1/60-1/51/5-1X11100-111X216/50101-4/50

5、x34/50011-6/5j0000-1/5cj110000CBXBbx1x2x3x4x5x61X11100-1101X2 16/50101-4/500 x3 4/50011-6/500 x6-4/50000-4/51j0000-1/501X10100-105/41X2401010-10X3200110-3/20 x5100001-5/4j00000-1/44)0,1,0,2,4,0(*ZXT2.分支定界法分支定界法松弛问题没有可行解，松弛问题没有可行解，ILP也没有可行解，停止计算。也没有可行解，停止计算。松弛问题有最优解，并符合松弛问题有最优解，并符合ILP的整数条件，则此最优解即为的整数

6、条件，则此最优解即为ILP的最优解，停止计算。的最优解，停止计算。松弛问题有最优解，但不符合松弛问题有最优解，但不符合ILP的整数条件，记它的目标函数值的整数条件，记它的目标函数值为为 ；ZZZZZ*(11/4,9/4),Z=31/4(3,3/2),Z=15/2(2,2),Z=6无解无解例：且为整数0,21260522121212121xxxxxxxxxxMaxZ(11/4,9/4)x12x13(2,2)(3,3/2)x21x22(19/6,1),Z=22/3(3,1),Z=7(19/6,1)x13x145.3 0-1整数规划整数规划n背包问题背包问题n厂址选择问题厂址选择问题n多决策问题多决

7、策问题n固定费用问题固定费用问题1.背包问题背包问题一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为x1，x2，x3件，总价值为z。max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元1041201772352.厂址选择模型厂址选择模型在5个备选地点中选择3处建设

8、生产同一产品的工厂，每个地点建厂所需投资，占用农田，建成以后的生产能力如下。总投资不超过800万元，占有农田不超过60亩。如何选择厂址，使总生产能力最大。3202802402101802018151187055422811设5个01变量x1，x2，x3，x4，x5，）（地建厂在地不建厂在54321ii1i0 xi,max z=70 x1+55x2+42x3+28x4+11x5s.t.320 x1+280 x2+240 x3+210 x4+180 x5800 20 x1+18x2+15x3+11x4+8x5 60 x1+x2+x3+x4+x5=3x1，x2，x3，x4，x5 为 01变量这个01

9、规划问题的最优解为：x1=1，x2=0，x3=1，x4=1，x5=0，max z=140即在地点1、3和4建3个厂，总生产能力最大，可以达到140万吨。3.多决策问题多决策问题一个工厂用3种设备生产5种产品，三种设备的能力（小时），生产每种产品需要占有的各种设备的能力（小时/件）以及5种产品的利润（元/件）如下：5.01.03.02.04.018003.04.01.05.025003.02.01.03.02.02200求使总利润最大的生产计划。max z=24x1+18x2+21x3+17x4+22x5s.t.5.0 x1+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0

10、 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x1，x2，x3，x4，x50 x1，x2，x3，x4，x5为整数设五种产品产量之间有以下逻辑关系：p五种产品中，安排生产的产品不能超过3种p每一种产品如果安排生产，最小批量为50件p如果产品1安排生产，产品2就不能生产p如果产品4生产，产品5必须生产，而且至少生产50件设5个01变量y1，y2，y3，y4，y5）（生产产品不生产产品5,4,3,2,110iiiyimax z=24x1+18x2+21x3+17x4+22x5s.t.5.0 x1+1.0 x2+

11、3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x110000y1 x210000y2 x310000y3 x410000y4 x510000y5 y1+y2+y3+y4+y5 3 50y1x1 50y2x2 50y3x3 50y4x4 50y5x5 y1+y21 y4y5 x1，x2，x3，x4，x50 x1，x2，x3，x4，x5为整数 y1，y2，y3，y4，y5为01变量4.固定费用问题固定费用问题即生产成本和产量成线性关系。如果产品不生产，不

12、发生任何成本，如果产品生产，则产量增加一倍，成本也增加一倍。这样的成本称为变动成本。在实际问题中，除了变动成本以外，还有固定成本。如果产品不生产，固定成本为0，如果产品生产，就发生固定成本，而且固定成本是一个常数，与产品产量无关。有固定成本的最小化目标函数的表达式为n1jjjxcmin一般的成本最小化目标函数表达式为0 xdxc0 x0jjjjjj种产品的成本第产量成本固定成本变动成本产量成本变动成本设n种设备，第j种设备的产量为xj，设备运行的变动成本为cj，设备开工的固定成本为dj。引进0-1变量y1，y2，yn，yj=0表示设备j不生产，yj=1表示设备j生产。考虑变动成本和固定成本，使

13、总成本最小化的目标函数为n1jjjn1jjjydxcmin设备开工与否与产量的逻辑关系，用以下约束条件表示xjMyj其中M为一个足够大的正数。具有固定成本的最小生产费用问题炼焦厂以原煤为原料生产焦炭，同时得到焦炉煤气和煤焦油。有4台不同生产能力的炼焦炉，有关的数据为0.640.680.710.73232527280.120.150.170.1940012002600310085817876100150200250要求焦炭产量不低于280吨，煤气产量不低于10000m3，煤焦油产量不低于60吨，编制使总成本最低的生产计划。不考虑固定成本，使变动成本最小化min z=85x1+81x2+78x3+

14、76x4s.t.0.64x1+0.68x2+0.71x3+0.73x4280 23x1+25x2+27x3+28x4100000.12x1+0.15x2+0.17x3+0.19x460 x1，x2，x3，x40最优解为：x1=x2=0，x3=137.32，x4=250，max z=29711.27考虑变动成本和固定成本，使总成本最小化。Min z=85x1+81x2+78x3+76x4 +400y1+1200y1+2600y3+3100y4s.t.0.64x1+0.68x2+0.71x3+0.73x4280 23x1+25x2+27x3+28x4100000.12x1+0.15x2+0.17x

15、3+0.19x460 x1100y1x2150y2x3200y3x4250y4x1，x2，x3，x40，y1，y2，y3，y4：0-1变量最优解为：y1=0，y2=1，y3=0，y4=1 x1=0，x2=143.38，x3=0，x4=250，max z=34913.975.4 隐枚举法隐枚举法n基本原理基本原理n举例说明举例说明1.基本原理基本原理检查变量取值为0或1的每一个组合，比较目标函数值的大小以求得最优解。只检查变量取值组合的一部分，就能求得问题的最优解的方法。步骤：步骤：如求极大化问题，根据目标函数中价值系数Cj的递增顺序，对目标函数和约束不等式中的变量重新排序，找一个可行解，其目标

16、函数值定为过滤值。考察各变量的组合，若产生Z劣于此时的过滤值，则不考虑，继续下一个组合，若优于此时的过滤值，则逐个考察是否满足约束条件，只要有一个不满足，则该组合为不可行解，继续下一个组合；如果满足所有约束，则产生新的过滤值，继续下一个组合。例：例：3,2,11064344225233221321321321jxxxxxxxxxxxxxxMaxZj，或(x2,x1,x3)Z值约束条件Z过滤值（0,0,0)（0,0,1)（0,1,0)（0,1,1)（1,0,0)（1,0,1)（1,1,0)（1,1,1)3,2,110643434225323212312312312jxxxxxxxxxxxxxxM

17、axZj，或0055388-231658888所以，该问题的最有解为（0，1，1），最优值为85.5 匈牙利法匈牙利法n标准指派问题标准指派问题n匈牙利法步骤匈牙利法步骤n实例实例n非标准指派问题非标准指派问题1.标准指派问题标准指派问题 njixnixnjxxCMinZijnjijniijnjniijij,1,10,1,1,1,11111，或2.匈牙利法步骤匈牙利法步骤3.实例实例61012961061476781296101417971215784046304081012630371020811340043204050012320377108110300331050601113103670081002010000010000000100010001004.非标准指派问题非标准指派问题