第四章数规圳与分配问题 §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 = 即
3.两组条件满足其中一组 若x1≤4,则x2≥1(第一组条件);否则当x1>4时, x2≤3(第二组条件 定义逻辑变量: y=1第7组条件不起作用 0,第组条件起作(1=12) 又设M为任意大正数,则问题可表达为 x1≤4+y1M x2≥1-y1M需注意,当约束 x1>4-y2M 为大于时,右端 ≤3+y2M 项中用减号
3. 两组条件满足其中一组 若 x1≤4，则 x2≥1（第一组条件）；否则当 x1>4 时， x2≤3（第二组条件）. 定义逻辑变量： （ ） ，第 组条件起作用 ，第 组条件不起作用 1,2 0 1 = = i i i yi 又设 M 为任意大正数，则问题可表达为： + = + − − + 1 3 4 1 4 1 2 2 2 1 2 2 1 1 1 y y x y M x y M x y M x y M 需注意，当约束 为大于时，右端 项中用减号
4.用以表示含固定费用的函数 用x代表产品j的生产数量,其生产费用函数表示为 K+cx(x1>0) 0 (x;=0) 其中K;是同产量无关的生产准备费用,问题的目标是使 所有产品的总生产费用为最小,即 mX=∑C(x) I 定义逻辑变量(表示是否生产产品j x.>0 0,x:=0
4. 用以表示含固定费用的函数 用 xj代表产品 j 的生产数量，其生产费用函数表示为 = + = 0 ( 0) ( 0) ( ) j j j j j j j x K c x x C x 其中 Kj 是同产量无关的生产准备费用，问题的目标是使 所有产品的总生产费用为最小，即 = = n j j j z C x 1 max ( ) 定义逻辑变量（表示是否生产产品 j ） = = 0 0 1 0 j j j x x y ，
又设M为任意大正数,为了表示上述定义,引入约束 ≤My 显然,当x>0时,y=1 将目标函数与约束条件合起来考虑有: min z ∑(cx+Kxy,) 0≤x,≤My y,=0或1 由此看出,当x=0时,为使z极小化,应有y=0 习题4.2
又设 M 为任意大正数，为了表示上述定义，引入约束： j My j x 显然，当 xj> 0 时，yj=1。 将目标函数与约束条件合起来考虑有： ( ) = = + = 0 1 0 min 1 j 或 j j n j j j j j y x My z c x K y 由此看出，当 xj = 0 时，为使 z 极小化，应有 yj = 0 习题 4.2
§2.分配问题与匈牙利法 问题的提岀与数学模型 分配问也称指派题( assignment problem) 是一种特殊的整数规划问题。假定有m项任务分配给m 个人去完成,并指定每人完成其中一项,每项只交给其中 个人去完成,应如何分配使总的效率为最高。 如果完成任务的效率表现为资源消耗,考虑的是如何 分配任务使得目标极小化;如果完成任务的效率表现为生 产效率的高低,则考虑的是如何分配使得目标函数极大化 在分配问题中,利用不同资源完成不同计划活动的效 率通常用表格形式表示为效率表,表格中数字组成效率 矩阵
§2．分配问题与匈牙利法 一、问题的提出与数学模型 分配问题也称指派问题（assignment problem）， 是一种特殊的整数规划问题。假定有 m 项任务分配给 m 个人去完成，并指定每人完成其中一项，每项只交给其中 一个人去完成，应如何分配使总的效率为最高。 如果完成任务的效率表现为资源消耗，考虑的是如何 分配任务使得目标极小化；如果完成任务的效率表现为生 产效率的高低，则考虑的是如何分配使得目标函数极大化。 在分配问题中，利用不同资源完成不同计划活动的效 率通常用表格形式表示为效率表，表格中数字组成效率 矩阵
例2.有一份说明书,要分别翻译成英、日、德、俄 四种文字,交甲、乙、丙、丁四个人去完成。因各人专长 不同,使这四个人分别完成四项任务总的时间为最小。效 率表如下: 人 工作 甲|乙丙丁 译成英文11097 译成日文154148 译成德文13141611 译成俄文415139 效率矩阵用nl表示,为 21097 154148 13141611 415139
例2. 有一份说明书，要分别翻译成英、日、德、俄 四种文字，交甲、乙、丙、丁四个人去完成。因各人专长 不同，使这四个人分别完成四项任务总的时间为最小。效 率表如下： 效率矩阵用[aij] 表示，为 = 4 15 13 9 13 14 16 11 15 4 14 8 2 10 9 7 [ ] ai j