分析：若当作一般线性规划求T解，图解法的结果如下。x +0.5x, = 4.51.非整数规划最优解(3.25，2.5)显然不是整数规划的可行解。2.四舍五入后的结果(3，3)也不是整数规划的可行解。3可行解是阴影区(3.25,2.5)域交叉点，可比较这些点对应的函数值，找出最优。(4，1)2x +3x2 =143xi2024-10-27
2024-10-27 7 分析： 若当作一般线性规划求 解，图解法的结果如下。 1. 非整数规划最优解 显然不是整数规划的可行解。 2. 四舍五入后的结果 也不是整数规划的可行解。 (3.25, 2.5) (3, 3) 3. 可行解是阴影区 域交叉点，可比较这 些点对应的函数值， 找出最优。 1 x 2 x 2x1 3x2 14 x1 0.5x2 4.5 2 2 3 2 1 z x x (3.25, 2.5) (4, 1)
S23指派问题及牙利解法指派问题与模型m项任务分配给m个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高？C;是第j个人完成第项任务的效率。人员21m任务1CllC12C1m.2C21C22C2m........mCmlCm2Cmm2024-10-278
2024-10-27 8 §2 指派问题及匈牙利解法 一 、 指派问题与模型 m项任务分配给m个人去完成，每人只能完成其中一项， 每项任务只能分给一人完成，应如何分配使得效率最高？ cij是第j个人完成第i项任务的效率。 人员 任务 1 2 . m 1 c11 c12 . c1m 2 c21 c22 . c2m . . . . . m cm1 cm2 cmm
1第人完成第项任务设Xi10否则于是建立模型如下：mmZZcyminz=i-l j=lmZ(i=1,2,.. m)X, = 1,j-=1Z(j=1,2... m)=1,Xii=1,=0或1,(i, j=1,2... m)Xii2024-10-27
2024-10-27 9 设 于是建立模型如下： 否则 第 个人完成第 项任务 0 1 j i xij m i m j ij ij z c x 1 1 min 0 1, i, j 1,2 . m 1, j 1,2 . m 1, i 1,2 . m 1 1 或 ， ， ， ij m i ij m j ij x x x
指派问题的匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更有效。解法思想：效率矩阵的元素ci>0，若有一组位于不同行不同列的零元素，则令这些位置的决策变量取值为1，其余均为0，这显然就是最优解。102024-10-27
2024-10-27 10 二、 指派问题的匈牙利解法 该指派问题可当作运输问题解决，但匈牙利解法更有效。 解法思想：效率矩阵的元素cij≥0，若有一组位于不同行不 同列的零元素，则令这些位置的决策变量取值为1，其余均 为0，这显然就是最优解
例：有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高人甲乙丙丁任务729英文108日文15414德文1314161149俄文1513112024-10-27
2024-10-27 11 例：有一份说明书，要分别译成英、日、德、俄四种语言， 交给甲、乙、丙、丁四人去完成，各人的效率不同，如何 分配任务，可使总效率最高。 人 任务 甲 乙 丙 丁 英文 2 10 9 7 日文 15 4 14 8 德文 13 14 16 11 俄文 4 15 13 9