中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 5 整数规划（Integer Programming）

运筹学整数规划问题指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩(百分制）如表所示，如何安排他们的工作使总成绩最好。工作BDA福人员甲85929073乙9587789582837990丙丁86908088-11-X主页后退退出上一页一页China University of Mining and Technology

-11- China University of Mining and Technology 运 筹 学 指派问题或分配问题。人事部门欲安排四人到四个不同 岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩 （百分制）如表所示，如何安排他们的工作使总成绩最好。 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 整数规划问题

运筹学整数规划问题分配第i人做工作时设不分配第人做工作时数学模型如下：maxZ=85x+92x,+73x3+90xi4+95x21+87x22++78x23+95x24+82x+83x32+79x33+90x34++86x41+90x42+80x43+88x44要求每人做一项工作，约束条件为：工作BX +X +X +X4 =1A人员X21 + X22 + X23 +X24 = 1甲85927390X31 +X32 +X33 +X34 = 1乙95789587X41+X42+X43+X44= 1丙8283799012-丁86908088X页页页下后退退出主LChina University of Mining and Technology

-12- China University of Mining and Technology 运 筹 学 设     不分配第人做 工作时 分配第 人做 工作时 i j i j xij 0 1 数学模型如下： 4 1 4 2 4 3 4 4 2 3 2 4 3 1 3 2 3 3 3 4 1 1 1 2 1 3 1 4 2 1 2 2 8 6 9 0 8 0 8 8 7 8 9 5 8 2 8 3 7 9 9 0 max 8 5 9 2 7 3 9 0 9 5 8 7 x x x x x x x x x x Z x x x x x x                   要求每人做一项工作，约束条件为：                        1 1 1 1 4 1 4 2 4 3 4 4 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 x x x x x x x x x x x x x x x x 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 整数规划问题