北京交通大学：《管理运筹学》课程教学课件（讲稿）第5章 整数规划 Integer Programming

第5音整数以北京交通大学经济管理興院Soctoales以往模型中，决策变量的取值可以为分数，但现实中，很多决策变量必须为整数，比如下料问题中的每种方案数必须为整数，再如制定汽车的最优生产计划，只能为整数台。按照以前的方法得显然行到的最优解可能为小数，不通！！此时应该怎么办？

第5章 整数规划 Integer Programming 整数规划问题的提出 分支定界解法 0-1型整数规划 指派问题 规划问题的Excel求解 以往模型中，决策变量的取值可 以为分数，但现实中，很多决策 变量必须为整数，比如下料问题 中的每种方案数必须为整数，再 如制定汽车的最优生产计划，只 能为整数台。按照以前的方法得 到的最优解可能为小数，显然行 不通！此时应该怎么办？

北京交通大学经济管理学院本节内容提要nicsandManagomentshastonuny整数规划问题的提出重点分支定界解法小结北京交通大学

本节内容提要 整数规划问题的提出 分支定界解法 小结 重点

例现要100套钢架，每套用长为2.9m，2.1m和1.5m各一根。知原料长7:4m，问应如何下料，使用的原材料最省。XXX3A方案VIIX +2x +x +x 3 1000102. 9m0201100X +2x +3xs +2x+x012. 1m020321X+x+3x4+2x+3x,+4x3100323041011. 5mminz=x, +x, +x,+x+x,+x+x+Xg00. 90. 10. 31.10.20.81.4余料

例： 现要做100套钢架，每套用长为2.9m，2.1m和1.5m各一根。 已知原料长7.4m，问应如何下料，使用的原材料最省。 2.9m 2.1m 1.5m 余料 I 1 1 1 II 2 0 1 0.9 0.1 方案 III 1 2 0 0.3 IV 1 0 3 0 V 0 3 0 1.1 VI 0 2 2 0.2 VII 0 1 3 0.8 VIII 0 0 4 1.4

北京交通大学低诚健min z = X, +x2 +X, +X4 +Xs +X+X + Xg3100X +2x +x +x3100+2xs+3x +2x +xX100+3x4S+2x +3x +4xX+xx,3 0, i=1,2,L ,8,x,I I正确吗？北京交通大学

正确吗？

北京交通大学经济管理学院-例 1整数规划问题的提出nicsandManagomentStingstongount货物重量体积利润2520甲乙45102413托运限制max z = 20x; +10x每箱某厂拟托运甲乙两种货物，的体积、重量、可获利润以及托5x +4x2 f 24运限制如上表所示，问两种货物2x +5x f13各托运多少箱，可使获得利润为最大？X,x3 0X,xI1北京交通大学

整数规划问题的提出——例1 货物 体积 重量 利润 甲 乙 5 4 2 5 20 10 托运限制 24 13 某厂拟托运甲乙两种货物，每箱 的体积、重量、可获利润以及托 运限制如上表所示，问两种货物 各托运多少箱，可使获得利润为 最大？

北京交通大学经济管理学院max z = 20x, +10x,School of EgruManagomentI0S4Boiljing JiaopngUniversity5x +4x 242x +5x2 132X,x, 3 0,x,1 14x = 4.8,x2 = 0,z = 96加上整数约束后怎样求解？将松驰问题的最优解取整可以吗？枝举法怎样？北京交通大学

0 1 2 1 2 3 4 加上整数约束后怎样求解？ 将松弛问题的最优解取整可以吗？ 枚举法怎样？

IP比LP更难求解。一般不能“枚举”、不能“四舍五入”。如例1，不考虑整数条件，最优解为x*=(4.8，0)T,Z=96z*=96。四舍五入得X2Z=90x=(5, 0)T,不是可行解(4,1)x=(4, 0)T,不是最优解X1(4.8,0而最优解是)x*=(4， 1)T， z*=90

z=90 z=96 x1 x2 (4.8,0 ) (4,1) IP比LP更难求解。一般不能“枚举” 、不能 “四舍五入”。如例1， 不考虑整数条件，最 优 解 为 x *=(4.8， 0)T ， z *=96。四舍五入得             x=(5，0)T ， 不是可行解 x=(4，0)T ， 不是最优解 而最优解是 x * =(4，1)T ，z *=90

北京交通大学经济管理学院整数规划的数学模型School of Eoics andManagomentBoijingJiaotong University数学模型的一般形式nmax Z(或min Z)=a cjxjj=1n1oa(i=1.2L m)a,x, f(= 3)b:11j-1:1<130（j=1,2L n）且部分或全部为整数t依照决策变量取整要求的不同，整数规划可分为纯（全整数规划）、混合整数规划、0一1整整数规划数规划。北京交通大学

整数规划的数学模型 依照决策变量取整要求的不同，整数规划可分为纯 整数规划（全整数规划）、混合整数规划、0－1整 数规划。 数学模型的一般形式

北京交通大学经济管理学院SchoolotandManagomentBoijingJiaotong University纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0一1整数规划：所有决策变量只能取0或1两个整数。北京交通大学

纯整数规划：所有决策变量要求取非负整数 （这时引进的松弛变量和剩余变量可以不要求 取整数）。            混合整数规划：只有一部分的决策变量要求取 非负整数，另一部分可以取非负实数。 0－1整数规划：所有决策变量只能取 0 或 1 两 个整数

北京交通大学整数规划与线性规划的关系经济管理学院School of Econcnics andManagomentBojing Jiaotong University注：从数学模型上看IP似乎是LP的一种特殊形式,但求解并不能在LP的基础上.通过舍入取整得到满足整数要求的解.实际上两者有很大的不同,通过舍入得到的解（整数）不一定就是最优解，有时甚至不能保证所得到的解是整数可行解.（如例1）求解Excel求解IP的常用方法有：分支定界法和割平面法：特别的0一1规划问题采用隐枚举法和匈牙利法北京交通大学

整数规划与线性规划的关系 注：从数学模型上看IP似乎是LP的一种特殊 形式,但求解并不能在LP的基础上,通过舍入 取整得到满足整数要求的解.实际上两者有很 大的不同,通过舍入得到的解（整数）不一定 就是最优解,有时甚至不能保证所得到的解是 整数可行解.（如例1） 求解IP的常用方法有： 分支定界法和割平面法; 特别的0－1规划问题采用隐枚举法和匈牙利法. Excel 求解