整数规划解法.ppt

《整数规划解法.ppt》由会员分享，可在线阅读，更多相关《整数规划解法.ppt（64页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、4.5 整数规划的解法整数规划的解法分支定界法割平面法匈牙利法14.5.1 整数规划解法 分枝定界法n步骤：步骤：1、寻找替代问题并求解、寻找替代问题并求解2、分枝与定界、分枝与定界3、剪枝、剪枝21、基本思路：、基本思路：整数规划的最优解不会优于相应整数规划的最优解不会优于相应的线性规划的最优解的线性规划的最优解。对于。对于极大值极大值问题，问题，相应线性相应线性规划规划的最大值成为整数规划目标函数的的最大值成为整数规划目标函数的上界上界。maxZ=CXAX=bX 0(A)max Z=CXAX=bX 0X为整数为整数(B)(B)为为(A)的松弛问题。的松弛问题。（1）替代问题的确定）替代问题

2、的确定3（2）替代问题的求解）替代问题的求解max Z=CXAX=bX 0(B)采用相应的方法（如图解法）求解出替代问题的采用相应的方法（如图解法）求解出替代问题的最优解最优解，观察其是否满足整数解的要求。如其，观察其是否满足整数解的要求。如其最最优解就为整数优解就为整数，则，则结束结束；如含有；如含有分数分数，则需要进，则需要进行行分支定界分支定界操作。操作。4（3）分支与定界）分支与定界增加约束增加约束如替代问题的解如替代问题的解不符合整数条件不符合整数条件，则需要对原问题进行，则需要对原问题进行分支分支。分支方法分支方法：假设替代问题的解为：假设替代问题的解为i，i+1之间的一个数，则分

3、成两支：之间的一个数，则分成两支：一支一支增加约束增加约束xji，另一支另一支增加约束增加约束xj i+1；对上述两个问题进行求解：对上述两个问题进行求解：不考虑整数问题时不考虑整数问题时，求解对应的线性规划，求解对应的线性规划问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到全部整数解为止。全部整数解为止。X*Xj*i+1i(C)(D)(B)Xj i+1(B)Xj i5 max Z=40X1+90X2 9X1+7X2 567X1+20X2 70X1,X2 0 X1,X2为为整数整数例：例：6解：先解该整数规划对应的松弛

4、问题解：先解该整数规划对应的松弛问题X*=4.8091.817Z*=355.890，上界上界Z*选选X1分枝分枝问题问题(2)(1)X1 4问题问题(3)(1)X1 5将将4,5之间的非整数部分舍去之间的非整数部分舍去7选选(2)继续分枝继续分枝问题问题(4)(2)X2 2问题问题(5)(2)X2 3解为解为X1=4X2=2.1Z=349.0解为解为X1=5X2=1.571Z=341.39问题问题2问题问题38(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283340327.12(6)5.4441340307.76(7

5、)无解无解X1 4X1 5X2 2X2 1X2 2X2 3分支定界过程分支定界过程94.5.2 整数规划解法2割平面法n割平面法的基本思想基本思想：n在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束，高莫雷约束或割平面)，使问题的可行域逐步缩小可行域逐步缩小。但每次切割时，只割去问题的部分非整数解只割去问题的部分非整数解，而不不切割任何整数的可行解切割任何整数的可行解，直到使问题的目标函数值达到最优的整数点整数点成为缩小后可行域的一个顶点一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。104.5.3 整数规划的解法匈牙利法应用于分配问题或指派问题分配问题或指派问题

6、n分配问题也称分配问题也称指派问题指派问题，是一种，是一种特殊的特殊的整数规划问题整数规划问题。n假定有假定有m项任务分配给项任务分配给m个人去完成个人去完成，并，并指定每人完成其中一项指定每人完成其中一项，每项只交给其每项只交给其中一个人去完成中一个人去完成，应如何分配使，应如何分配使总的效总的效率为最高率为最高。111、指派问题一般模型的引出、指派问题一般模型的引出n例：有一份说明书，要分别译成英、日、德、俄四种文字，例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的

7、时间完成翻译不同文字所需的时间(h)如表所示。问：如何分如表所示。问：如何分配任务使效率最高（配任务使效率最高（所需总时间最短所需总时间最短）？）？人人工作工作 甲甲乙乙丙丙丁丁译译成英文成英文21097译译成日文成日文154148译译成德文成德文13141611译译成俄文成俄文415139从人的从人的角度看角度看从任务从任务角度看角度看12指派问题的一般模型指派问题的一般模型n假设：假设：naij表示指派问题的效率矩阵表示指派问题的效率矩阵nxij表示决策变量，决策变量的取值：表示决策变量，决策变量的取值：13n指派问题的一般数学模型 指派问题的一般模型指派问题的一般模型142、指派问题的求

8、解方法、指派问题的求解方法n 单纯形法单纯形法n 表上作业法表上作业法n 匈牙利法匈牙利法15（1）指派问题的求解）指派问题的求解匈牙利法匈牙利法n核心思路核心思路：基于这样一个事实：如果效率矩阵的所有元素aij0，而其中存在一组位一组位于于不同行、不同列不同行、不同列的的零元素零元素，则只要令对对应于这些零元素的应于这些零元素的xij=1（分配任务）（分配任务），其余的其余的xij=0，则目标函数z必然会取得最小（0）。0149392002320038512140只需令：只需令：x11=1，x23=1，x32=1，x44=1，即第一项各种分配给甲，即第一项各种分配给甲，二工作二工作丙，三丙，

9、三乙，四乙，四丁。丁。总工作时间最少。总工作时间最少。效效率率矩矩阵阵16问问 题题n要求：效率矩阵中存在零元素，同时存在不在同要求：效率矩阵中存在零元素，同时存在不在同一行、同一列的零元素。一行、同一列的零元素。n实际的效率矩阵中，是不可能存在实际的效率矩阵中，是不可能存在0元素的，那元素的，那么么如何获得这种特殊的效率矩阵？如何获得这种特殊的效率矩阵？n如何让效率矩阵中产生零元素；如何让效率矩阵中产生零元素；n如何让产生的零元素位于不同行和不同列如何让产生的零元素位于不同行和不同列。17（2）零元素的产生方法）零元素的产生方法：匈牙利法的基本定理匈牙利法的基本定理1n如果从分配问题效率矩阵

10、如果从分配问题效率矩阵aij的每的每一行一行元素中元素中分别分别减去减去(或加上或加上)一个一个常数常数ui(被被称为该行的位势称为该行的位势)，从，从每一列每一列分别分别减去减去(或加上或加上)一个一个常数常数vj(称为该列的位势称为该列的位势)，得到一个得到一个新的效率矩阵新的效率矩阵bij，若其中，若其中n则则bij的最优解等价于的最优解等价于aij的最优解的最优解（说（说明，经过变换后，有零的新效率矩阵取得最优解时，明，经过变换后，有零的新效率矩阵取得最优解时，原效率矩阵也同时取得最优解）原效率矩阵也同时取得最优解）18（3）独立零元素独立零元素的判断方法的判断方法：匈牙利法的基本定理

11、匈牙利法的基本定理2n若矩阵若矩阵A的元素可分成的元素可分成“0”与非与非“0”两部两部分，则分，则覆盖覆盖“0”元素元素的的最少直线最少直线数等于数等于位位于不同行、不同列的于不同行、不同列的“0”元素的最大个数元素的最大个数。19n若矩阵若矩阵A的元素可分成的元素可分成“0”与非与非“0”两两部分，则覆盖部分，则覆盖“0”元素的最少直线数等元素的最少直线数等于位于不同行、不同列的于位于不同行、不同列的“0”元素的最元素的最大个数。大个数。n将确定一个效率矩阵中最大独立零元素的将确定一个效率矩阵中最大独立零元素的个数，转化为寻找覆盖所有零元素所需的个数，转化为寻找覆盖所有零元素所需的最少直线

12、数。最少直线数。20匈牙利法的计算步骤 n 基本步骤：在效率矩阵中产生零元素基本步骤：在效率矩阵中产生零元素判断独立的零元素个数是否等于任务数判断独立的零元素个数是否等于任务数或人数？或人数？如是，则对效率矩阵中独立如是，则对效率矩阵中独立零元素所处的位置进行指派（对应的决零元素所处的位置进行指派（对应的决策变量为策变量为1），完成），完成如否，则要继续产如否，则要继续产生足够的独立零元素。生足够的独立零元素。n通过实例来说明匈牙利法求解指派问题通过实例来说明匈牙利法求解指派问题的过程。的过程。21例：例：n有一份说明书，要分别译成英、日、德、俄四种文有一份说明书，要分别译成英、日、德、俄四种

13、文字，交甲、乙、丙、丁四个人去完成。因各人专长字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间不同，他们完成翻译不同文字所需的时间(h)如表所如表所示。问：如何分配任务使效率最高？示。问：如何分配任务使效率最高？人工作 甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文41513922效率矩阵23步骤一：零元素的产生。步骤一：零元素的产生。方法：方法：找出效率矩阵找出效率矩阵每行每行的的最小元素最小元素，并，并分别从每行中减去它。分别从每行中减去它。min实际含义：从事情的角度来考虑，表示此事分配给此人效率最高。实际含义：从事情的角度

14、来考虑，表示此事分配给此人效率最高。591100532410011578041142913154111614138144157910224步骤二：继续产生零元素步骤二：继续产生零元素方法：方法：再找出矩阵再找出矩阵每列每列的的最小元素最小元素，再分，再分别从各列中减去它。别从各列中减去它。min 0 0 5 0实际含义：从人的角度来考虑，表示某人做此事效率最高。实际含义：从人的角度来考虑，表示某人做此事效率最高。5411000324501152802 259110053410011578025步骤三：判断零元素是否位于不同行、不步骤三：判断零元素是否位于不同行、不同列？同列？n经过上述两步变换

15、后，矩阵的每行每列至经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。少都有了一个零元素。n确定能否找出确定能否找出m个位于不同行不同列的零个位于不同行不同列的零元素的集合元素的集合(本例中本例中m=4)，直观法：直观法：m很小时，直接判断得到；很小时，直接判断得到；非直观法：非直观法：m很大时，根据一定规则寻找。很大时，根据一定规则寻找。26直观法直观法541100032450115280只有只有3个个0元素元素位于不同行、位于不同行、不同列不同列27非直观法非直观法-步骤步骤1（试指派过程）（试指派过程）n(1)从从第一行第一行开始，若开始，若该该行只有一个零元素行只有一个零元素，就

16、对这个，就对这个零元素打上零元素打上()号号。n同时，对打同时，对打()号零元素号零元素所在所在列列画一条直线，画一条直线，表示表示此列已经确定（人员确定），不能再从事其他行此列已经确定（人员确定），不能再从事其他行的工作（任务）的工作（任务）。n若该行若该行没有零元素没有零元素或有或有两个以上零元素两个以上零元素(已划去的已划去的零元素不计在内零元素不计在内)，则，则转下一行转下一行，按照上述方法依，按照上述方法依次进行到最后一行；次进行到最后一行；28例：从行开始的独立零元素的寻找与判断例：从行开始的独立零元素的寻找与判断（）（）从行开始标定独立零元从行开始标定独立零元素时，只能找到两个独

17、素时，只能找到两个独立的零元素。立的零元素。29非直观法非直观法-步骤步骤2n(2)在行寻找的基础上，从在行寻找的基础上，从第第一列一列开始，若开始，若该列该列只有只有一个零元素一个零元素就对就对这个这个零元素打上零元素打上()号号(同样不考虑已划去的零元同样不考虑已划去的零元素素)，n对打对打()号零元素号零元素所在行所在行画一条直线画一条直线（任务分（任务分配完毕，不能再分配给其他人）。配完毕，不能再分配给其他人）。n若该列没有零元素或有两个以上零元素，则若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列；转下一列，依次进行到最后一列；30例：从列开始的独立零元素的寻找与判

18、断例：从列开始的独立零元素的寻找与判断（）在行标定后的基础上，在行标定后的基础上，从第一列开始标定独立从第一列开始标定独立零元素时，只能找到一零元素时，只能找到一独立的零元素。独立的零元素。31问问 题题只能对三个零元素进行标定（代表独立的零只能对三个零元素进行标定（代表独立的零元素只有三个），后续如何操作？元素只有三个），后续如何操作？32非直观法-步骤3（第一种情形）n(3)重复重复(1)、(2)两个步骤两个步骤，可能出现三，可能出现三种情况：种情况：n 效率矩阵效率矩阵每行都有一个打每行都有一个打()号的零元号的零元素素，很显然，按上述步骤得到的打，很显然，按上述步骤得到的打()号号的零

19、元素都位于不同行不同列，只要的零元素都位于不同行不同列，只要令令对应打对应打()号零元素对应的决策变量号零元素对应的决策变量xij=1就找到了问题的就找到了问题的最优解最优解；33第一种情形第一种情形x11=1，x22=1，x33=1，x44=1。任务一任务一甲；二甲；二乙；三乙；三丙；丙；四四丁丁任务一任务一任务二任务二任务三任务三任务四任务四甲甲 乙乙 丙丙 丁丁34非直观法-4（第二种情形）n 打打()号的号的零元素个数小于零元素个数小于m，但，但未被划去未被划去的的零元素之间存在零元素之间存在闭回路（全以闭回路（全以0为拐点）为拐点），这，这时时可顺着闭回路可顺着闭回路的走向，对的走向

20、，对每个间隔每个间隔的的零元素打零元素打一一()号号，然后对所有打，然后对所有打()号的零元素，或所在号的零元素，或所在行，或所在列画一条直线（行，或所在列画一条直线（一般会出现多种方案一般会出现多种方案）。如：。如：或或35第二种情形第二种情形（）（）只能给两个零元素打括号，只能给两个零元素打括号，还有四个零元素不能打上括还有四个零元素不能打上括号。剩下的未被划去和未打号。剩下的未被划去和未打括号的零元素存在闭回路。括号的零元素存在闭回路。（）（）36x13=1，x22=1，x31=1，x44=1结论结论137结论结论2（）（）x14=1，x22=1，x31=1，x43=138非直观法-5（

21、第三种情形）n 矩阵中矩阵中所有零元素或被划去所有零元素或被划去，或，或打上打上()号号，但但打打()号的零元素个数小于号的零元素个数小于m，如：，如：打括号的零元素打括号的零元素3m=4。证明。证明0元素产生的元素产生的还不够，还应继续产生。还不够，还应继续产生。39步骤四：继续创造零元素。步骤四：继续创造零元素。方法方法：为设法使每一行都有一个打为设法使每一行都有一个打()号的零元素，号的零元素，需要继续按定理需要继续按定理1对矩阵进行变换。对矩阵进行变换。n(1)从矩阵从矩阵未被直线覆盖未被直线覆盖的数字中找出一的数字中找出一个个最小最小的数的数k；n(2)对对矩阵的每行矩阵的每行，当该

22、行，当该行有直线覆盖有直线覆盖时，时，令令ui=0，无直线覆盖无直线覆盖的，令的，令ui=k；n(3)对矩阵每列，对矩阵每列，有直线覆盖的列有直线覆盖的列，令，令vj=-k，对，对无直线覆盖的列无直线覆盖的列，令，令vj=0；n(4)从原矩阵的每个元素从原矩阵的每个元素aij中分别减去中分别减去ui和和vj，得到一个新的矩阵，得到一个新的矩阵（aij-ui-vj），），保证新矩阵中，原打括号的保证新矩阵中，原打括号的0元素不变，元素不变，同时产生新的零元素。同时产生新的零元素。40步骤五：回到第三步，反复进行，一直到矩阵的每一步骤五：回到第三步，反复进行，一直到矩阵的每一行都有一个打行都有一个

23、打()()号的零元素为止，即找到了最优分配号的零元素为止，即找到了最优分配方案。方案。uivj41 人工作 甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文415139n最优分配方案为：n甲将说明书译成俄文，乙译成日文，丙译成英文，丁译成德文，n全部所需时间为4+4+9+11=28小时。42回顾：指派问题的计算过程回顾：指派问题的计算过程效率效率矩阵矩阵435911005324100115780411429131541116141381441579102步骤一：产生每行的零元素。步骤一：产生每行的零元素。方法：从每行中找出最小的元素，与对应方法：从每行中找出最小的

24、元素，与对应的每行元素相减的每行元素相减min每行减去每行减去对应的最对应的最小元素小元素44步骤二：产生位于每列的零元素步骤二：产生位于每列的零元素方法：方法：再找出矩阵再找出矩阵每列每列的的最小元素最小元素，再分，再分别从各列中减去。别从各列中减去。min 0 0 5 05411000324501152805911005324100115780每列减去每列减去对应的最对应的最小元素小元素保证每行、每列都至少有一个保证每行、每列都至少有一个0元素。元素。45步骤三：判断零元素是否位于不同行、不同列。步骤三：判断零元素是否位于不同行、不同列。方法：首先从行开始试指派，只有一个零元素时，对零元方

25、法：首先从行开始试指派，只有一个零元素时，对零元素打括号，并对所在列画直线。而有多个零元素，或零元素打括号，并对所在列画直线。而有多个零元素，或零元素已被画去，则转下一行；行分析完毕后，然后从列开始素已被画去，则转下一行；行分析完毕后，然后从列开始试指派，对每列只有一个零元素时，打括号，并画去其所试指派，对每列只有一个零元素时，打括号，并画去其所在的行。在的行。541100032450115280（）（）行试指派过程行试指派过程541100032450115280（）（）列试指派过程列试指派过程（）46步骤四：继续创造零元素。步骤四：继续创造零元素。方法：从未被画去的元素中，找到一个最小的元素

26、方法：从未被画去的元素中，找到一个最小的元素k。（1）对行的操作：选择行位势）对行的操作：选择行位势ui，如果行被直线覆盖，则，如果行被直线覆盖，则ui=0；如果；如果未被覆盖，未被覆盖，ui=k；（2）列的操作：列位势）列的操作：列位势vj，如果列被直线覆盖，如果列被直线覆盖，vj=-k；如果未被覆盖，；如果未被覆盖，vj=0。（3）产生新的效率矩阵：）产生新的效率矩阵：bij=aij-ui-vj541100032450115280（）（）（）1、最小元素、最小元素k=2；2、ui依次为依次为2、2、0和和2；3、vj依次取为依次取为-2、-2、0和和0.。ui2202vj-2-200bij

27、=aij-ui-vj32110005423011308047步骤五：继续判断零元素是否位于不同行、不同列。步骤五：继续判断零元素是否位于不同行、不同列。方法：方法：首先从行开始试指派，只有一个零元素时，对零元素打首先从行开始试指派，只有一个零元素时，对零元素打括号，并对所在列画直线。而有多个零元素，或零元素已被画括号，并对所在列画直线。而有多个零元素，或零元素已被画去，则转下一行；行分析完毕后，然后从列开始试指派，对每去，则转下一行；行分析完毕后，然后从列开始试指派，对每列只有一个零元素时，打括号，并画去其所在的行。列只有一个零元素时，打括号，并画去其所在的行。3211000542301130

28、80（）（）（）（）最终结果最终结果321100054230113080（）（）（）（）48步骤六：获得最后结果。步骤六：获得最后结果。方法：对于打括号的零元素处进行指派，即可获得最短时间。方法：对于打括号的零元素处进行指派，即可获得最短时间。321100054230113080（）（）（）（）p x13=1（工作一（工作一丙）丙）p x22=1（工作二（工作二乙）乙）p x34=1（工作三（工作三丁）丁）p x41=1（工作四（工作四甲）甲）最短时间为：最短时间为：9+4+11+4=28 h。指派结果指派结果494.5.4 极大化的指派问题极大化的指派问题对于目标为求极大的指派问题，先要对对

29、于目标为求极大的指派问题，先要对效率矩阵进行处理：效率矩阵进行处理：（1）找出效率矩阵中的最大值，分别用）找出效率矩阵中的最大值，分别用它去减阵中每一元素，得到新矩阵；它去减阵中每一元素，得到新矩阵；（2）对新得到的矩阵用原匈牙利法求解。）对新得到的矩阵用原匈牙利法求解。5051例、有例、有 4 种机械要分别安装在种机械要分别安装在4个工地，它们个工地，它们 在在4个工地的工作效率不同，问应如何指个工地的工作效率不同，问应如何指 派，可使派，可使4台机械发挥的总效益最大？台机械发挥的总效益最大？工地工地机器机器 甲甲 乙乙 丙丙 丁丁 30 25 40 32 32 35 30 36 35 40

30、 34 27 28 43 32 3852解：解：原效益矩阵中原效益矩阵中 max Cij=Cij=43所以所以 bij=43 Cij (i,j=1,2,3,4）534.5.5 人数和任务数不相等人数和任务数不相等例例、4项工作分配给项工作分配给6个人完成，有人可不做个人完成，有人可不做 工作人 123456 3 6 2 6 7 1 4 4 3 6 5 8 6 4 3 7 5 2 4 3 5 7 6 2 54解：虚设两项假想的任务解：虚设两项假想的任务 工作工作人人 123456 3 6 2 6 0 0 7 1 4 4 0 0 3 6 5 8 0 0 6 4 3 7 0 0 5 2 4 3 0

31、0 5 7 6 2 0 055 工作工作人人 123456 0 5 0 4 0 0 4 0 2 2 0 0 0 5 3 6 0 0 3 3 1 5 0 0 2 1 2 1 0 0 2 6 4 0 0 0（0）（0）（0）（0）（0）（0）人员安排：人员安排：1，2 ；3 ；4，5休息；休息；6 总的时间为：总的时间为：2+1+3+2=856 工作工作人人 123456 0 5 0 4 0 0 4 0 2 2 0 0 0 5 3 6 0 0 3 3 1 5 0 0 2 1 2 1 0 0 2 6 4 0 0 0（0）（0）（0）（0）（0）（0）人员安排：人员安排：1，2 ；3 ；4，5休息；休

32、息；6 总的时间为：总的时间为：2+1+3+2=857例、例、4人完成人完成5项任务，每人可完成项任务，每人可完成12项项 任务任务人人A B C D E甲乙丙丁 25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36 23 4558解：解：因每个人可担任因每个人可担任一至二项一至二项任务，因此将任务，因此将4人人 看作看作8人人，再，再虚设虚设3项任务项任务，化为平衡指派问题。，化为平衡指派问题。任务任务 人人 A B C D E F G H甲甲乙乙丙丙丁丁甲甲乙乙丙丙丁丁 25 29 31 42 37 0 0 0 39 38 26 20

33、33 0 0 0 34 27 28 40 32 0 0 0 24 42 36 23 45 0 0 0 25 29 31 42 37 0 0 0 39 38 26 20 33 0 0 0 34 27 28 40 32 0 0 0 24 42 36 23 45 0 0 059最优解：甲最优解：甲无无 乙乙C,D 丙丙B,E 丁丁Amin Z=12960例、例、4人完成人完成5项任务，其中一人完成两项，其余每人一项项任务，其中一人完成两项，其余每人一项 任务任务人人A B C D E甲乙丙丁 25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36

34、23 4561解：虚设一人戊，完成各任务时间为甲、乙、解：虚设一人戊，完成各任务时间为甲、乙、丙、丁中最小者，化为平衡指派问题。丙、丁中最小者，化为平衡指派问题。任务任务 人人A B C D E甲乙丙丁戊 25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36 23 45 24 27 26 20 32最优方案：甲最优方案：甲B 乙乙D、C 丙丙E 丁丁A 最小时间最小时间13162nP109:4.3n有有4个工人，要指派他们分别完成个工人，要指派他们分别完成4项工作，项工作，每人做每项工作所消耗的时间如表所示。每人做每项工作所消耗的时间如表所

35、示。问指派哪个人去完成哪项工作，可使总的问指派哪个人去完成哪项工作，可使总的消耗时间最小？（表中时间单位为消耗时间最小？（表中时间单位为h）工作工作 工人工人ABCD甲甲15182124乙乙19232218丙丙26171619丁丁19212317作作业业63nP109:4.4n已知下列已知下列5名运动员各种姿势的游泳成绩（距离名运动员各种姿势的游泳成绩（距离为为50m）如表所示。试问如何从中选拔一个参加）如表所示。试问如何从中选拔一个参加200m混合泳的接力队（四种游泳姿势），使预混合泳的接力队（四种游泳姿势），使预期比赛成绩最好。（表中时间单位为期比赛成绩最好。（表中时间单位为S）思思 考考 人人 项目项目赵赵钱钱张张王王周周仰泳仰泳37.732.933.83735.4蛙泳蛙泳43.433.142.234.741.8蝶泳蝶泳33.328.538.930.433.6自由泳自由泳29.226.429.628.531.164