中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 5 整数规划（Integer Programming）

运筹学Chapter5整数规划(Integer Programming)本章主要内容：整数规划的特点及应用分支定界法分配问题与匈牙利法-1-?China University of Mining and Technology

-1- China University of Mining and Technology 运 筹 学 Chapter5 整数规划 ( Integer Programming ) 本章主要内容： 整数规划的特点及应用 分支定界法 分配问题与匈牙利法

运筹学学习要点：1.掌握一般整数规划问题概念及模型结构；2.能够用分支定界法求解一般整数规划问题：3.掌握整数规划的求解方法：分枝定界法，割平面法，匈牙利法。-2-China University of Mining and Technology

-2- China University of Mining and Technology 运 筹 学 学习要点： 1.掌握一般整数规划问题概念及模型结构； 2.能够用分支定界法求解一般整数规划问题； 3.掌握整数规划的求解方法：分枝定界法，割平面 法，匈牙利法

运筹学5.整数规划问题及其数学模型-3-￥China University of Mining and Technology

-3- China University of Mining and Technology 运 筹 学 5.1 整数规划问题 及其数学模型

运筹学整数规划问题(简称：IP)整数规划要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为为整数线性规划。整数线性规划数学模型的一般形式：Ecxmax Z(或min Z)=2(i = 1.2...m)a,x, =b,-x,≥0(j=1.2n)且部分或全部为整数-4-X主页上一页质退银万China University of Mining and Technology

-4- China University of Mining and Technology 运 筹 学 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。 不考虑整数条件，由余下的目标函数和约束条件构成 的规划问题称为该整数规划问题的松弛问题。若该松弛问题 是一个线性规划，则称该整数规划为整数线性规划。 整数线性规划数学模型的一般形式：               且部分或全部为整数 或 0 (j 1.2 n) ( 1.2 ) max ( min ) 1 1   j n j ij j i n j j j x a x b i m Z Z c x 整数规划问题

运筹学整数规划问题整数线性规划问题的种类纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另部分可以不取整数值的整数线性规划。。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。-5-￥主页一页广银ChinaUniversityof Miningand Technology下

-5- China University of Mining and Technology 运 筹 学 整数线性规划问题的种类： 纯整数线性规划：指全部决策变量都必须取整数值的整数线 性规划。 混合整数线性规划：决策变量中有一部分必须取整数值，另 一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。 整数规划问题

运筹学整数规划问题整数规划的典型例子工厂A,和A生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A，和A两个。这种物资的需求地有B,B,B,,B四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费Ci，见下表：B1B2B3B4年生产能力932A400A1837600A25762200A31545A42200350400300150年需求量工厂A，或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A，还是A4，才能使今后每年的总费用最少。-6-X主页下一页退出上一页后退China University of Mining and Technology

-6- China University of Mining and Technology 运 筹 学 整数规划的典型例子 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建 一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有 B1 ,B2 ,B3 ,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求 地的单位物资运费cij，见下表： B1 B2 B3 B4 年生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 年需求量 350 400 300 150 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。 整数规划问题

运筹学整数规划问题解：这是一个物资运输问题，特点是事先不能确定应该建A，还是A中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：若建工厂(i = 1,2)=V若不建工厂再设x为由A，运往B的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：-7-米主页页银China University of Mining and TechnologyK

-7- China University of Mining and Technology 运 筹 学 解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量： ( 1,2) 0 1     y  i i 若不建工厂 若建工厂 再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用， 单位万元。 则该规划问题的数学模型可以表示为： 整数规划问题

运筹学整数规划问题min z =ZZCijX; +[1200 y, +1500 y2]i=1 j=1Xi1 + X21 + X31 + X41 = 350X12 + X22 + X32 + X42 = 400X13 + X23 + X33 + X43 = 300X14 + X24 + X34 + X44 = 150X11 + X12 + X13 + Xi4 = 400混合整数规划问题S.tX21 +X22 + X23 + X24 = 600X31 + X32 + X33 + X34 = 200 yi年生产B1B2B3B4能力X41 + X42 + X43 + X44 = 200 y23A1294004(i, j = 1,2,3,4)Xj ≥035A2876002A3612007[y; = 0,1 (i=1,2)525A4200年需350400300150-8-求量X人下页后退退出主页上一页China University of Mining and Technology

-8- China University of Mining and Technology 运 筹 学                                                            0,1 ( 1,2) 0 ( , 1,2,3,4) 200 200 600 400 150 300 400 350 . min [1200 1500 ] 4 1 4 2 4 3 4 4 2 3 1 3 2 3 3 3 4 1 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 1 4 2 4 3 4 4 4 1 3 2 3 3 3 4 3 1 2 2 2 3 2 4 2 1 1 2 1 3 1 4 1 4 1 4 1 1 2 y i x i j x x x x y x x x x y x x x x x x x x x x x x x x x x x x x x x x x x s t z c x y y i i j i j i j i j 混合整数规划问题 B1 B2 B3 B4 年生产 能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 年需 求量 350 400 300 150 整数规划问题

运筹学整数规划问题现有资金总额为B。可供选择的投资项目有n个，项目i所需投资额和预期收益分别为a;和c；（j=1,2,…,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2，反之不一定；项目3和4中至少选择一个项自5,6,7中恰好选择2个。应该怎样选择投资项自，才能使总预期收益最大。9.米上一页人下页主页后退银China University of Mining and Technology

-9- China University of Mining and Technology 运 筹 学 现有资金总额为B。可供选择的投资项目有n个，项目j 所需投资额和预期收益分别为aj和cj（j＝1,2,.,n），此外由 于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2，反之不一定; 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。 整数规划问题

运筹学整数规划问题因此分解：对每个投资项目都有被选择和不被选择两种可能，别用0和1表示，令x；表示第个项目的决策选择，记为对项目投资(j = 1,2..., n)对项目不投资nZex,投资问题可以表示为：z=maxj=1"Wajx, ≤BX, ≥ Xis.tX+x ≥1Xs +X +X, = 2x,=0或者1(j=1,2,...n)-10-退出主页上一页页后退China University of Mining and Technology

-10- China University of Mining and Technology 运 筹 学 解：对每个投资项目都有被选择和不被选择两种可能，因此分 别用0和1表示，令xj表示第j个项目的决策选择，记为： ( 1,2,., ) 0 1 j n j j xj      对项目 不投资 对项目 投资 投资问题可以表示为：                        x 或 者 （ n） x x x x x x x a x B s t z c x j n j j j n j j j 0 1 j 1,2, 2 1 . max 5 6 7 3 4 2 1 1 1 整数规划问题