第四章整数规划与分配问题 本章主要内容： 整数规划的特点及作用 ·分配问题与匈牙利法 兼分支定界法 兼割平面法（自学） 豢 0-1型整数规划应用举例 2014-12-15 1
2014-12-15 1 第四章 整数规划与分配问题 整数规划的特点及作用 分配问题与匈牙利法 分支定界法 割平面法（自学） 0-1型整数规划应用举例 本章主要内容：
§1整数规划的特点及作用 整数规划（简称：IP) 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。（线性整数规划、非线性整数规划等） 整数规划问题的种类： ·纯整数规划：指全部决策变量都必须取整数值的整数规划。 ·混合整数规划：决策变量中有一部分必须取整数值，另一 部分可以不取整数值的整数规划。 ·0-1型整数规划：决策变量只能取值0或1的整数规划。 2014-12-15
2014-12-15 2 §1 整数规划的特点及作用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。（线性整数规划、非线性整数规划等） 纯整数规划：指全部决策变量都必须取整数值的整数规划。 混合整数规划：决策变量中有一部分必须取整数值，另一 部分可以不取整数值的整数规划。 0-1型整数规划：决策变量只能取值0或1的整数规划。 整数规划问题的种类：
§1整数规划的特点及作用 例1设整数规划问题如下 max Z=3x+2x2 2x1+3x2≤14 s.tx1+0.5x2≤4.5 x1,x2≥0且为整数 首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题) 0 max Z=3x+2x2 2x1+3x2≤14 s.t. x1+0.5x2≤4.5 x1,x2≥0 2014-12-15 3
2014-12-15 3 §1 整数规划的特点及作用 例1 设整数规划问题如下 , 0且为整数 0.5 4.5 2 3 14 . . max 3 2 1 2 1 2 1 2 1 2 x x x x x x st Z x x 首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。 , 0 0.5 4.5 2 3 14 s.t. max 3 2 1 2 1 2 1 2 1 2 x x x x x x Z x x
§1整数规划的特点及作用 用图解法求出最优解为：X,=3.252=2.5,且有7=14.75 现求整数解（最优解）：如用舍 入取整法可得到4个点即(4， 3),(4,2),3,3),3,2)。显然， 它们都不可能是整数规划的最优 解。 按整数规划约束条件，其可行 3.25,2.5) 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(4,1)点的目标函 数值最大，即为Z=14。 2014-12-15
2014-12-15 4 §1 整数规划的特点及作用 用图解法求出最优解为：x 1＝3.25, x 2 = 2.5，且有Z = 14.75 现求整数解(最优解):如用舍 入取整法可得到4个点即(4， 3),(4，2),(3，3),(3，2)。显然， 它们都不可能是整数规划的最优 解。 x1 x2 ⑴ ⑵ 4 4 (3.25,2.5) 按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(4,1)点的目标函 数值最大，即为Z=14
§1整数规划的特点及作用 整数规划问题的求解方法： 。匈牙利法（指派问题） ·分支定界法和割平面法 2014-12-15 5
2014-12-15 5 §1 整数规划的特点及作用 整数规划问题的求解方法： 匈牙利法（指派问题） 分支定界法和割平面法