Chapter4整数规划 Integer Programming) 本章主要内容： ·整数规划的特点及应用 。分支定界法 ·分配问题与匈牙利法
Chapter4 整数规划 ( Integer Programming ) 整数规划的特点及应用 分支定界法 分配问题与匈牙利法 本章主要内容：
整数规划的特点及应用 Page2 整数规划（简称：P) 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。不考虑整数条件，由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题。若该松弛问 题是一个线性规划，则称该整数规划为整数线性规划。 整数线性规划数学模型的一般形式： maxZ(或minZ)=∑c,x, 20,x=bi=12m x,≥0(0=1.2.n)且部分或全部为整数
整数规划的特点及应用 Page 2 整数规划（简称：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
整数规划的特点及应用 Page 3 整数线性规划问题的种类： ·纯整数线性规划：指全部决策变量都必须取整数值的整数 线性规划。 ·混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。 ·0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划
整数规划的特点及应用 Page 3 整数线性规划问题的种类： 纯整数线性规划：指全部决策变量都必须取整数值的整数 线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划
整数规划的特点及应用 Page 4 整数规划的典型例子 例4.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费c,见下表： B1 B2 B3 B4 年生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 > 6 1 2 200 A4 4 5 2 5 200 年需求量 350 400 300 150 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万 元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用 最少
整数规划的特点及应用 Page 4 整数规划的典型例子 例4.1 工厂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，才能使今后每年的总费用 最少
整数规划的特点及应用 Page 5 解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量： 若建工厂 若不建工厂 (i=1,2) 再设x为由A运往B的物资数量，单位为千吨；表示总费用， 单位万元。 则该规划问题的数学模型可以表示为：
整数规划的特点及应用 Page 5 解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量： ( 1,2) 0 1 = y = i i 若不建工厂 若建工厂 再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用， 单位万元。 则该规划问题的数学模型可以表示为：