第六章任务分派方案的优化方法课件

引例----一个任务分派问题优化方法----匈牙利法应用和推广第六章任务分派方案的优化方法工人与任务的广泛含义最大总收益问题非标准形式的任务分派问题写出费用矩阵费用矩阵行列缩减重复第三步，直至得到最优方案1精选课件ppt第一节一个任务分派问题安排甲、乙、丙、丁四人完成车、铣、刨、磨床工作。不同工人对不同机床的熟练程度有区别，根据以往的资料，估算出每个工人对各种工种的预制工夹具等准备时间的数据如下表；工种车床铣床刨床磨床甲21057乙154148丙13141211丁415139一个工人担任一个工种；一个工种工作由一个工人来完成。如何合理的分配任务，使得所有工人化费的准备时间总和尽可能的小？2精选课件ppt有n项任务，恰好n个人承担，第i人完成第j项任务的花费(时间或费用等)为cij≥0，如何指派使总花费最省？第j项工作由一个人做第i人做一项工作标准形式的任务分派问题可行的分派方案：每人一项任务，每项任务由一个人承担。可行解可表示为：3精选课件ppt例有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？第二节优化方法阶数①写出费用矩阵4精选课件ppt已知条件可用系数矩阵（效率矩阵）表示为：其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：5精选课件ppt-2-4-11-4

若某行(列)已有0元素，那就不必再减了。例中的计算为：

根据结论1、结论2进行行列缩减，使系数矩阵各行、各列出现零元素。作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。②费用矩阵行列缩减6精选课件ppt试求最优解：如能找出n个位于不同行不同列的零元素，独立0令对应的xij=1，其余xij=0，得最优解，结束；否则下一步。作法：由独立0元素的行（列）开始，独立0元素处画标记，在有的行列中划去其它0元素；再在剩余的0元素中重复此做法，直至不能标记为止③画线盖0，调整0的布局独立0的个数=n,最优分派。未得到最优分配方案ⅰ以最少的直线数覆盖所有的0。未被直线覆盖的最小元素为cij；ⅱ未被直线覆盖处减去cij；ⅲ仅被一条直线覆盖的元素不变；ⅳ直线交叉点元素加上cij，。得新效益矩阵。对新矩阵，重新试分配。7精选课件ppt-2可以分派④求最优解最优分派方案是甲----刨床乙----铣床丙----磨床丁----车床总的准备时间=5+4+11+4=24小时8精选课件ppt第三节应用和推广一、工人与任务的广泛含义166页例美学文学哲学史学周二50406030周三60303020周四30202030周五30201030工会应怎样安排，使缺席听课的职工人数最少？工人任务9精选课件ppt解：①费用矩阵②费用矩阵行列缩减-30-20-20-10-10③画线盖0，调整0的布局④重复上述步骤。10精选课件ppt标号法分派----多重最优解。周二------美学周三------史学周四------文学周五------哲学总缺席人数：50+20+20+10=100人11精选课件ppt二、最大总收益问题有六名工人在六个岗位上的效率以百分数表示如下：任务

工人123456192738085979927575989186823809490919980479979682808858476948893726769274867388求使总效率最高的任务分配方案。12精选课件ppt设最大总收益问题的收益矩阵为B=（bij）（i=1,2,…,n;j=1,2,…,n）。如果则令构成矩阵，那末，以为费用矩阵的最优方案就是原最大总收益问题的最优方案。本例，13精选课件ppt对C行列缩减，画线盖0，调整0的布局。再次调整0的布局，14精选课件ppt回到原问题，得最优解。工人1-----岗位6，工人2-----岗位3，工人3-----岗位5，工人4-----岗位2，工人5-----岗位1，工人6-----岗位4，最大总效率：99+98+99+97+84+86=563%

15精选课件ppt三、非标准形式的任务分派问题泳式运动员蛙泳自由泳蝶泳仰泳赵12.011.611.511.2钱12.311.711.611.1孙11.911.411.511.0李11.811.611.711.2周12.111.711.511.1应选哪几名运动员组成4×100的接力队。总费用最小的问题。16精选课件ppt工人数≠任务数，称为非标