OR-chapter4整数规划与分配问题.pdf

Chapter4 整数规划与分配问题 本章主要内容： 整数规划的特点及应用 分枝定界法 0 －1 整数规划 指派问题 在很多场合，我们建立最优化模型时，实际问题要求决 策变量只能取整数值而非连续取值。此时，这类最优化 模型就称为整数规划（离散最优化）模型。 整数规划的求解往往比线性规划求解困难得多，而且， 一般来说不能简单地将相应的线性规划的解取整来获得。 整数规划的特点及应用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。不考虑整数条件，由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题。若该松弛问 题是一个线性规划，则称该整数规划为整数线性规划。 整数线性规划数学模型的一般形式： n max Z (或min Z ) c x j j j 1  n a x b (i 1.2 m)  ij j i j 1  x j  0 (j 1.2n) 且部分或全部为整数  整数规划的特点及应用 整数线性规划问题的种类： 纯整数线性规划：指全部决策变量都必须取整数值的整数 线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。 整数线性规划的一般形式 纯整数线性规划 0-1整数规划 T min cT x min c x Ax b Ax b   s.t . s.t . x  0 (x I ) xi 0,1 (i 1,2, ,n)   min cT x  混合整数 Ax b  线性规划 s.t .x  0  x I i J  1,2, ,n  i   整数规划的特点及应用 整数规划的典型例子 例1 工厂A 和A 生产某种物资。由于该种物资供不应求，故需要再 1 2 建一家工厂。相应的建厂方案有A 和A 两个。这种物资的需求地有 3 4 B ,B ,B ,B 四个。各工厂年生产能力、各地年需求量、各厂至各需 1 2 3 4 求地的单位物资运费cij ，见下表： B1 B2 B3 B4 年生产能力