文档介绍：第四章整数规划与分配问题
§
§
§
§
§
§
在实际问题中,全部或部分变量的取值必须是整数。比如人或机器是不可分割的,选择建厂地点可以设置逻辑变量等。
在一个线性规划问题中要求全部变量取整数值的,称纯整数线性规划或简称纯整数规划;只要求一部分变量取整数值的,称为混合整数规划。
对整数规划问题求解,有人认为可以不考虑对变量的整数约束,作为一般线性规划问题求解,当解为非整数时,用四舍五入或凑整方法寻找最优解,我们从下面的例子说明这样的方法是不合适的。
例1. 求下述整数规划问题的最优解
解:如果不考虑整数约束(称为整数规划问题的松弛问题)用图解法得最优解为( , )
考虑到整数约束,用凑整法求解时,比较四个点(4 , 3),(4 , 2),(3 , 3)(3 , 2),前三个都不是可行解,第四个虽然是可行解,但 z=13 不是最优。实际问题的最优解为(4 , 1)这时 z*= 14。
逻辑(0-1)变量在建立数学模型中的作用
1. m 个约束条件中只有 k 个起作用
设 m 个约束条件可以表示为:
定义逻辑变量
又设 M 为任意大的正数,则约束条件可以改写为:
定义逻辑变量:
此时约束条件可以改写为:
2. 约束条件的右端项可能是 r 个值中的某一个
即
3. 两组条件满足其中一组
若 x1≤4,则 x2≥1(第一组条件);否则当 x1>4 时,x2≤3(第二组条件).
定义逻辑变量:
又设 M 为任意大正数,则问题可表达为:
需注意,当约束为大于时,右端项中用减号。
4. 用以表示含固定费用的函数
用 xj 代表产品 j 的生产数量,其生产费用函数表示为
其中 Kj 是同产量无关的生产准备费用,问题的目标是使所有产品的总生产费用为最小,即
定义逻辑变量(表示是否生产产品 j )
又设 M 为任意大正数,为了表示上述定义,引入约束:
显然,当 xj> 0 时,yj=1。
将目标函数与约束条件合起来考虑有:
由此看出,当 xj = 0 时,为使 z 极小化,应有 yj = 0<br****题
§
一、问题的提出与数学模型
分配问题也称指派问题(assignment problem),是一种特殊的整数规划问题。假定有 m 项任务分配给 m 个人去完成,并指定每人完成其中一项,每项只交给其中一个人去完成,应如何分配使总的效率为最高。
如果完成任务的效率表现为资源消耗,考虑的是如何分配任务使得目标极小化;如果完成任务的效率表现为生产效率的高低,则考虑的是如何分配使得目标函数极大化。
在分配问题中,利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表,表格中数字组成效率矩阵。
例2. 有一份说明书,要分别翻译成英、日、德、俄四种文字,交甲、乙、丙、丁四个人去完成。因各人专长不同,使这四个人分别完成四项任务总的时间为最小。效率表如下:
效率矩阵用[aij] 表示,为