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