整数规划与分配问题

整数规划的模型分支定界法割平面法0－1整数规划分配问题第四章整数规划与分配问题一、整数规划的模型及特点一、整数规划的模型及特点一、整数规划的模型及特点

例3设有4个教师，他们各有能力去教4门不同课程中的任一门，但因为他们的经历和经验不同，所以每个教师同样准备教某一课程平均每周所需备课时间不同，见下表。问应分配哪个教师去担任哪门课程，以使所有4门课程总的备课时间为最少？一、整数规划的模型及特点各位教师对各门课的准备时间一、整数规划的模型及特点

任务人员ABCD甲215134乙1041415丙9141613丁78119一、整数规划的模型及特点一、整数规划的模型及特点一、整数规划的模型及特点整数规划包括整数线性规划和整数非线性规划。从数学模型上看整数线性规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。整数规划与线性规划的关系4整数规划与线性规划的关系用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。整数规划与线性规划的关系因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。整数规划与线性规划的关系

设n个人被分配去做n件工作，已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？二、分配问题设决策变量1分配第i个人去做第j件工作

xij=0相反(i,j=1.2.…n)标准形式二、分配问题二、分配问题二、分配问题二、分配问题方法：可顺着闭合回路的方向，对间隔的0元素打上（）二、分配问题A.从矩阵中未被直线覆盖的数字中找出一个最小的数kB.对矩阵中横竖线交叉点的元素加kC.矩阵中划线的列不变D.矩阵中未划线的元素减k

任务人员ABCD甲215134乙1041415丙9141613丁78119二、分配问题例3二、分配问题42二、分配问题00二、分配问题最优分配方案为甲—D，乙—B，丙—A，丁—C此时最小耗时成本为28。有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982二、分配问题例55

找到3个独立零元素但m=3<n=4二、分配问题所有的零或被划去,或被圈起二、分配问题A.从矩阵中未被直线覆盖的数字中找出一个最小的数kB.对矩阵中横竖线交叉点的元素加