指派工人加工零件

数 学 与 信 息 科 学 学 院数 学 建 模 论 文论文题目 指派工人加工零件 专 业 数学与应用数学 班 级 2012 级 1 班 学 号 姓 名 开课学期 2014-2015 学年第一学期完成时间 2014 年 10 月 26 日 1指派工人加工零件摘 要本文主要探讨指派问题针对所给问题，我们先用 0-1 变量表示人员 是否i加工零件 ，然后以总花费时间为目标函数，建立 0-1 规划模型，最后借助jlingo11 软件，求解得到最终的分派方案：甲乙丙丁分别加工零 CDAB，可使所求最少关键词：指派 0-1 规划 lingo111．问题的重述今欲指派甲乙丙丁四个人加工 A、B、C、D 四种不同的零件，每个人加工四种零件所需的时间如下表所示：表 1 工人加工零件的工作效率人 零件 A B C D甲 4 6 5 8乙 6 10 7 4丙 7 8 11 9丁 9 3 8 6试问指派谁加工何种零件可以使得总的花费时间最少？2．模型的假设与符号说明2．1 模型的假设（1）假设 1 每人只能加工一种零件；（2）假设 2 每种零件只能由一个人独立完成；（3）假设 3 每人都能在规定的时间内完成工作；2．2 符号说明 ：第 个人i：第 种零件j：人员 加工零件 所需时间ijcij：ijx0,ijxijij=1人 员 加 工 零 件 j其 他：总的花费时间z23．模型的建立与求解3．1 模型建立（1）决策变量：甲乙丙丁加工零件的情况。

设甲乙丙丁分别为人员 记 A、B、C、D 分别为零件 记1,24i 1,234j人员 加工零件 所需时间为 引入 0-1 变量 ：ijijcijx0,ijxijij=1人 员 加 工 零 件其 他（2）决策目标：总花费时间最少设 为总的花费时间，z41minijjzxc（3）约束条件：①每人必须而且只需完成其中一项，此时对 ，有1,234i41ijx②4 种零件均被加工，即每种零件有且只有一个人来加工此时对 ，,234j有51ijx由此得基本模型：（1）41minijjzcx（2）41.,2,3ijst（3）51,,4ijx（4）0,ij3．2 模型求解利用 lingo11（见附录 1）,可得Global optimal solution found.Objective value: 19.00000Objective bound: 19.00000Infeasibilities: 0.0000003Extended solver steps: 0Total solver iterations: 0Variable Value Reduced CostC( 1, 1) 4.000000 0.000000C( 1, 2) 6.000000 0.000000C( 1, 3) 5.000000 0.000000C( 1, 4) 8.000000 0.000000C( 2, 1) 6.000000 0.000000C( 2, 2) 10.00000 0.000000C( 2, 3) 7.000000 0.000000C( 2, 4) 4.000000 0.000000C( 3, 1) 7.000000 0.000000C( 3, 2) 8.000000 0.000000C( 3, 3) 11.00000 0.000000C( 3, 4) 9.000000 0.000000C( 4, 1) 9.000000 0.000000C( 4, 2) 3.000000 0.000000C( 4, 3) 8.000000 0.000000C( 4, 4) 6.000000 0.000000X( 1, 1) 0.000000 4.000000X( 1, 2) 0.000000 6.000000X( 1, 3) 1.000000 5.000000X( 1, 4) 0.000000 8.000000X( 2, 1) 0.000000 6.000000X( 2, 2) 0.000000 10.00000X( 2, 3) 0.000000 7.000000X( 2, 4) 1.000000 4.000000X( 3, 1) 1.000000 7.000000X( 3, 2) 0.000000 8.000000X( 3, 3) 0.000000 11.00000X( 3, 4) 0.000000 9.000000X( 4, 1) 0.000000 9.000000X( 4, 2) 1.000000 3.000000X( 4, 3) 0.000000 8.000000X( 4, 4) 0.000000 6.000000Row Slack or Surplus Dual Price1 19.00000 -1.0000002 0.000000 0.0000003 0.000000 0.0000004 0.000000 0.0000005 0.000000 0.0000006 0.000000 0.0000007 0.000000 0.00000048 0.000000 0.0000009 0.000000 0.000000从而 13243142,,,xx所以应指派甲乙丙丁分别加工零件 C、D、A、B，才能使总花费时间最少。

4．模型结果的分析与检验4．1 分析与检验：采用穷举法，指派工人加工零件的方案共有 4！种，如下表所示：表 2 分派工人加工零件的方案由表中数据知，当指派甲加工 C,乙加工 D，丙加工 A，丁加工 B 时，总花费时间最少，为 19 小时与所建立的 0-1 规划模型所求结果一致，故所建模型合理5．模型的评价5．1 模型的优点：相比传统的穷举法，该模型借助计算机软件，大大提供了解题的速度5.2 模型的缺点模型假设还不够完善甲 乙 丙 丁 总时 间 甲 乙 丙 丁 总时 间A B C D 31 B A C D 29A B D C 31 B A D C 29A C B D 25 B C A D 26A C D B 23 B C D A 31A D B C 24 B D A C 25A D C B 22 B D C A 30C A B D 25 D A B C 30C A D B 23 D A C B 28C B A D 28 D B A C 33C B D A 33 D B C A 38C D A B 19 D C A B 25C D B A 26 D C B A 325附录附录一model:sets:person/1..4/;position/1..4/;link(person,position):c,x;endsetsdata:c=4,6,5,8,6,10,7,4,7,8,11,9,9,3,8,6;enddatamin=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));end。