第四章数规圳与分配问题 §1.整数规划的特点及作用 §2.分配问题与匈牙利法 §3.分枝定界法 §4.割平面法 §5.应用举例
第四章 整数规划与分配问题 §1．整数规划的特点及作用 § 2．分配问题与匈牙利法 § 3．分枝定界法 § 4．割平面法 § 5．应用举例
§1.整数规划的特点及应用 在实际问题中,全部或部分变量的取值必须是整数。 比如人或机器是不可分割的,选择建厂地点可以设置逻辑 变量等。 在一个线性规划问题中要求全部变量取整数值的,称 纯整数线性规划或简称整数规划只要求一部分变量 取整数值的,称为泥台整数规划 对整数规划问题求解,有人认为可以不考虑对变量的 整数约束,作为一般线性规划问题求解,当解为非整数时 用四舍五入或凑整方法寻找最优解,我们从下面的例子说 明这样的方法是不合适的
§1．整数规划的特点及应用 在实际问题中，全部或部分变量的取值必须是整数。 比如人或机器是不可分割的，选择建厂地点可以设置逻辑 变量等。 在一个线性规划问题中要求全部变量取整数值的，称 纯整数线性规划或简称纯整数规划；只要求一部分变量 取整数值的，称为混合整数规划。 对整数规划问题求解，有人认为可以不考虑对变量的 整数约束，作为一般线性规划问题求解，当解为非整数时， 用四舍五入或凑整方法寻找最优解，我们从下面的例子说 明这样的方法是不合适的
例1.求下述整数规划问题的最优解 max z=3x,+2x 2x1+3x<14 +0.5x,<4.5 x,x2≥0,且均取整数值 解:如果不考虑整数约束(称为整数规划问题的松弛 厄)用图解法得最优解为(3.25,25) 考虑到整数约束,用凑整法求解 时,比较四个点(4,3),(4,2) (3,3)(3,2),前三个都不是可行 解,第四个虽然是可行解,但z13不 325,25) 是最优。实际问题的最优解为(4,1) 这时z=14。 23 678"x1
例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 z x x 解：如果不考虑整数约束（称为整数规划问题的松弛 问题）用图解法得最优解为（3.25 , 2.5） 考虑到整数约束，用凑整法求解 时，比较四个点（4 , 3）,（4 , 2）, （3 , 3）（3 , 2），前三个都不是可行 解，第四个虽然是可行解，但 z=13 不 是最优。实际问题的最优解为（4 , 1） 这时 z *= 14
逻(0-1)变量在建立数学模型中的作用 1.m个约束条件中只有k个起作用 设m个约束条件可以表示为: ∑anx,≤b 定义逻辑变量 ,假定第i个约東条件不起作用 0,假定第i个约束条件起作用 又设M为任意大的正数,则约束条件可以改写为: x:<b+Mi 1+… m-k
逻辑（0-1）变量在建立数学模型中的作用 1. m 个约束条件中只有 k 个起作用 设 m 个约束条件可以表示为： ( 1, , ) 1 a x bi i m n j i j j = = 定义逻辑变量 = ，假定第 个约束条件起作用 ，假定第 个约束条件不起作用 0 1 i i yi 又设 M 为任意大的正数，则约束条件可以改写为： + + + = − + = y y y m k a x b My m i i n j i j j 1 2 1
2.约束条件的右端项可能是r个值中的某一个 即∑axsb或b或…或b 定义逻辑变量: ∫,假定约束右端项为b 0,其 此时约束条件可以改写为: ∑ax≤∑ y1+y2+…+y=1
定义逻辑变量： = ，其它 ，假定约束右端项为 0 1 i i b y 此时约束条件可以改写为： + + + = = = 1 2 1 1 1 r r i i i n j i j j y y y a x b y 2. 约束条件的右端项可能是 r 个值中的某一个 r n j ai jxj b1 或b2 或或b 1 = 即