运筹学上机试题2--指派问题.doc

练习一：有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。 工作工人ABCD甲15182124乙19232218丙26171619丁19212317最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 0 1 0 0 2 1 0 0 0 3 0 0 1 0 4 0 0 0 1此运输问题的成本或收益为: 70此问题的另外的解如下： 起 至 销点 发点 1 2 3 4 - - - - - 1 1 0 0 0 2 0 0 0 1 3 0 0 1 0 4 0 1 0 0此运输问题的成本或收益为: 70练习二：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案。B1B2B3B4A112797A27171214A3151466A4410710A56558A64576解析B1B2B3B4B5B6A11279700A2717121400A315146600A441071000A5655800A6457600 最优解如下* 起 至 销点 发点 1 2 3 4 5 6 - - - - - - - 1 0 0 0 0 1 0 2 0 0 0 0 0 1 3 0 0 0 1 0 0 4 1 0 0 0 0 0 5 0 0 1 0 0 0 6 0 1 0 0 0 0此运输问题的成本或收益为: 20练习三：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由3家建筑公司分别承建。已知第Ai(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B3家商店不能由第A1个建筑公司承办，求使总费用最少的指派方案B1B2B3B4B5A14871512A279171410A3691287解析：B1B2B3B4B5B62791714100A36912870A114810015120A21791714100A316912870 最优解如下* 起 至 销点 发点 1 2 3 4 5 - - - - - - 1 1 0 0 0 0 2 0 0 0 0 1 3 0 0 1 0 0 4 0 1 0 0 0 5 0 0 0 0 0 6 0 0 0 1 0此运输问题的成本或收益为: 42注释：总供应量多出总需求量 1 第5个产地剩余 1此问题的另外的解如下： 起 至 销点 发点 1 2 3 4 5 - - - - - - 1 1 0 0 0 0 2 0 0 0 0 1 3 0 0 0 1 0 4 0 1 0 0 0 5 0 0 0 0 0 6 0 0 1 0 0此运输问题的成本或收益为: 42注释：总供应量多出总需求量 1 第5个产地剩余 1练习四：某人事部门拟招聘4人任职4项工作，对他们综合考评的 得分如下表（满分100分），如何安排工作使总分最多解析： 最优解如下* 起 至 销点 发点 1 2 3