运筹学__指派问题

1、 在实际中经常会遇到这样的问题，在实际中经常会遇到这样的问题，有有n n 项不同的任务，项不同的任务，需要需要n n 个人分别完成其中的一项，个人分别完成其中的一项，但由于任务的性质和各人的专长不同，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。（或花费的时间或费用）也就不同。于是产生了一个于是产生了一个问题问题: :应指派哪个人去完成哪项任务，应指派哪个人去完成哪项任务，使完成使完成 n n 项任务的总效率最高（或所需时间最少），项任务的总效率最高（或所需时间最少），这类问题称为这类问题称为指派问题指派问题或分派

2、问题。或分派问题。 有一份中文说明书，有一份中文说明书，要分别译成要分别译成英、日、德、俄英、日、德、俄四种文字四种文字，分别记作分别记作E E 、 J J 、 G G 、 R ,R ,交与交与甲、乙、丙、丁甲、乙、丙、丁 四个人四个人去完成去完成. .因个人专长不同，因个人专长不同，他们完成翻译不同语种的说明书所需的时间他们完成翻译不同语种的说明书所需的时间(h)(h)如表所示如表所示. .应如何指派，使四个人分别完成这四项任务应如何指派，使四个人分别完成这四项任务总时间总时间为最小？为最小？ 任务任务人员人员E EJ JG GR R甲甲2 2151513134 4乙乙10104 41414

3、1515丙丙9 9141416161313丁丁7 78 811 119 9一、指派问题的数学模型一、指派问题的数学模型（一）（一）举例举例v这是一个这是一个标准型的指派问题标准型的指派问题指派指派v对应每个指派问题，需有类似上表那样的数表，对应每个指派问题，需有类似上表那样的数表，效率效率矩阵矩阵或或系数系数矩阵矩阵C=(cij)nn=c11 c12 c1n c21 c22 c2n cn1 cn1 cnn C=(cij )=2151341041415914161378119则该指派问题的数学模型为：则该指派问题的数学模型为：11121314434441412151341191141140 11

4、4min(, ). .(, )(, )ijjijiijzxxxxxxxistxjxi j或或，求解题时通常需引入求解题时通常需引入0-10-1变量变量：x xij ij=1 (i=1,2,3,4)=1 (i=1,2,3,4)表示第表示第i i人只能完成一项任务人只能完成一项任务Sx xij ij=1 (j=1,2,3,4)=1 (j=1,2,3,4)表示第表示第j j 项任务只能由一人去完成。项任务只能由一人去完成。满足约束条件的解称为可行解，满足约束条件的解称为可行解，可写成矩阵形式，叫作可写成矩阵形式，叫作解矩阵解矩阵。)4 , 1j;4 , 1i (ji, 0ji, 1xij 项项任任务

5、务个个人人去去完完成成第第不不分分配配第第项项任任务务个个人人去去完完成成第第分分配配第第 1000000101000010 xij如本例的一个可行解矩阵（但不一定是最优解）如本例的一个可行解矩阵（但不一定是最优解）指派问题的指派问题的解矩阵解矩阵应具有如下应具有如下特点特点：（1 1）解矩阵解矩阵(x(xij ij) )中各行各列的元素之和都是中各行各列的元素之和都是1 1；（2 2）可行解（最优解）中恰含有个非零元，即可行解（最优解）中恰含有个非零元，即4 4个个1 1；（3 3）可行解（最优解）矩阵中的可行解（最优解）矩阵中的1 1恰取于恰取于不同行不同列。不同行不同列。可以看到可以看到

6、指派指派问题问题既是既是0-1 规划问题，也是运输问题规划问题，也是运输问题，所以也可用整数规划，所以也可用整数规划，0-1 规划，规划，或运输问题的解法去求解。或运输问题的解法去求解。（二）（二）指派问题的数学模型指派问题的数学模型 1. 指派问题的一般指派问题的一般提法提法： v设设m个人被指派去做个人被指派去做m件工作，件工作， 规定每个人只做一件工作，规定每个人只做一件工作， 每件工作只有一个人去做。每件工作只有一个人去做。v已知第已知第i个人去做第个人去做第j 件工作的的效率（件工作的的效率（ 时间或费用）时间或费用） 为为cij (i=1.2m;j=1.2m) ，并假设，并假设ci

7、j 0。 问应如何指派才能使总效率最高或总时间问应如何指派才能使总效率最高或总时间 总费用最低总费用最低 ？设设c cij ij 表示指派问题的表示指派问题的效率矩阵效率矩阵，令，令)m, 1j;n, 1i (ji, 0ji, 1xij 项项任任务务个个人人去去完完成成第第不不分分配配第第项项任任务务个个人人去去完完成成第第分分配配第第则指派问题的数学模型一般形式为：则指派问题的数学模型一般形式为： )m, 1jn, 1i (10 x)m, 1j (1x)n, 1i (1x. t . sxczmax)(minijn1iijm1jijm1im1jijij；或或或或x xij ij 为第为第 i

8、i 个人个人指派指派去做去做第第 j j 项任务；项任务；c cij ij 为第为第 i i 个人为完成第个人为完成第 j j 项任务时的工时消项任务时的工时消耗耗，或称效率，或称效率； c cij ij n n mm 为为效率矩阵效率矩阵2.2. 指派问题数学模型指派问题数学模型一般形式一般形式如果一个指派模型满足以下三个条件：如果一个指派模型满足以下三个条件： 1) 1)目标要求为目标要求为minmin 2) 2)效率矩阵效率矩阵(c (cij ij) )为为mm阶方阵阶方阵 3)3)效率矩阵中所有元素效率矩阵中所有元素c cij ij00, ,且为常数且为常数则称上面的数学模型为指派问题

9、的标准形则称上面的数学模型为指派问题的标准形. .3.3. 指派问题数学模型指派问题数学模型标准形式标准形式4.4. 指派模型的标准形的指派模型的标准形的特点特点: :含有含有mmmm个决策变量个决策变量, ,均为均为0-10-1变量变量m+mm+m2m2m个约束方程个约束方程 给定一个指派问题时，必须给出效率矩阵（系数矩阵）给定一个指派问题时，必须给出效率矩阵（系数矩阵） C=(cC=(cij ij) )mxmmxm, ,且且c cij ij 0 0，因此必有最优解，因此必有最优解 。 m1im1jijij0 xcMinZ指派问题有指派问题有2m2m个约束条件，个约束条件，但但可行解（即解矩

10、阵）中可行解（即解矩阵）中有且只有有且只有mm个个是是非零非零值值，即即mm个值取为，其余取为个值取为，其余取为, , 是自然高度退化的是自然高度退化的。 指派指派问题问题是是0-1 规划的特例，规划的特例， 也是运输问题的特例，所以可用整数规划，也是运输问题的特例，所以可用整数规划，0-1 规划或运输问题的解法去求解，规划或运输问题的解法去求解， 但这就如同用单纯形法去求解运输问题一样，但这就如同用单纯形法去求解运输问题一样， 是不合算的。是不合算的。 根据指派问题的特点可以有更简便的解法，根据指派问题的特点可以有更简便的解法， 就是就是匈牙利算法匈牙利算法， 其重要其重要依据依据是：是：

11、系数矩阵中独立系数矩阵中独立 0 元素的最多个数等于能覆盖元素的最多个数等于能覆盖所有所有 0 元素的最少直线数。元素的最少直线数。 二二 匈牙利算法匈牙利算法思路思路算法原理算法原理算法步骤算法步骤 匈牙利法基于这样一个匈牙利法基于这样一个明显的明显的事实事实： 如果在如果在m m阶效率矩阵中，所有元素阶效率矩阵中，所有元素c cijij00， 而其中有而其中有m m个位于不同行不同列的一组个位于不同行不同列的一组0 0元素，元素， 则在解矩阵中，只要令对应于这些则在解矩阵中，只要令对应于这些0 0元素位置的元素位置的x xijij1 1，其余的，其余的x xijij0 0，就得到最优解。，

12、就得到最优解。 此时的最优解为此时的最优解为（一） 思路0141208302323020939140令令x x11 11=1=1，x x2323=1=1，x x3232=1=1，x x4444=1=1，即可得最优解，即可得最优解，其其解矩阵解矩阵为为如如效率矩阵效率矩阵为为恰有恰有4 4个不同行个不同行不同列的不同列的0 0系数系数 1000001001000001问题是如何找到位于不同行、不同列的问题是如何找到位于不同行、不同列的mm个个0 0元素？元素？min Z=Z0匈牙利数学家狄匈牙利数学家狄康尼格康尼格(D(DKonigKonig) )证明的两个定理证明的两个定理（二）算法的基本原理

13、（二）算法的基本原理定理定理1 1 如果从指派问题效率矩阵如果从指派问题效率矩阵c cij ij 的每一行元素中分别的每一行元素中分别减去减去( (或加上或加上) )一个常数一个常数u ui i( (被称为该行的位势被称为该行的位势) )，从每一列分别减去从每一列分别减去( (或加上或加上) )一个常数一个常数v vj j( (称为该列的位势称为该列的位势) )，得到一个新的效率矩阵得到一个新的效率矩阵bbij ij ，若其中若其中b bij ij=c=cij ij-u-ui i-v-vj j，则则bbij ij 的最优解的结构等价于的最优解的结构等价于c cij ij 的最优解的结构的最优解

14、的结构. .将从将从bbij ij 中得到的解中得到的解代入分配问题模型的目标函数式，有代入分配问题模型的目标函数式，有 m1jjm1im1iim1jijijm1iijm1jjm1im1jijm1iim1jijijm1im1jijjiijm1im1jijijvuxcxvxuxcx)vuc(xbzv利用这个性质，可使原系数矩阵变换为含有很多利用这个性质，可使原系数矩阵变换为含有很多 0 0元素的新系数矩阵，而最优解保持不变，元素的新系数矩阵，而最优解保持不变，v在系数矩阵在系数矩阵(b(bij ij) )中，把位于不同行不同列的中，把位于不同行不同列的0 0元素，元素， 简称为简称为独立的独立的

15、0 0元素元素。v问题是问题是： 能否找到位于不同行、不同列的能否找到位于不同行、不同列的mm个个0 0元素？元素？ 若能在系数矩阵若能在系数矩阵(b(bij ij) )中找出中找出mm个独立的个独立的0 0元素；元素； 则令则令 解矩阵解矩阵(x(xij ij) )中对应这中对应这mm个独立的个独立的0 0元素的元素的x xij ij取值为取值为1 1， 其他元素取值为其他元素取值为0 0。 将其代入目标函数中得到将其代入目标函数中得到z zb b=0=0，它一定是最小值。，它一定是最小值。v这就是以这就是以(b(bij ij) )为系数矩阵的指派问题的最优解。为系数矩阵的指派问题的最优解。

16、 从而也就得到了原问题的最优解。从而也就得到了原问题的最优解。库恩（库恩（W.W.KuhnW.W.Kuhn）于）于19551955年给出了指派年给出了指派 问题的问题的解法，解法，他引用匈牙利数学家狄他引用匈牙利数学家狄康尼格（康尼格（d.konigd.konig) )关于矩关于矩阵中独立零元素的定理阵中独立零元素的定理( (即定理即定理2)2)：系数矩阵中独立的系数矩阵中独立的“0”0”元素的最多个数等于覆盖元素的最多个数等于覆盖所有所有“0”0”元素的最少直线数元素的最少直线数 -匈牙利算法基本思想匈牙利算法基本思想2 2库恩给出的指派问题的解法称为库恩给出的指派问题的解法称为匈牙利算法匈

17、牙利算法定理定理2 2 若效率矩阵若效率矩阵C C的元素可分成的元素可分成“0”0”与非与非“0”0”两部分，则两部分，则覆盖所有覆盖所有“0”0”元素的元素的独立的独立的“0”0”元素的元素的最多个数最多个数 已知矩阵中有若干已知矩阵中有若干0 0元素，设覆盖全部元素，设覆盖全部0 0元素元素最少需最少需mm条直线条直线，又设位于，又设位于不同行不同列的不同行不同列的0 0有有MM个个. .因覆盖因覆盖MM中的每个中的每个0 0至少用一条直线，故有至少用一条直线，故有mm MM下面要证明下面要证明M M m.m.i1i2irj1j2jc如图假定覆盖所有如图假定覆盖所有0 0元素的元素的mm条

18、直线条直线有有r r行、行、c c列，列，m=r+c.m=r+c.所有所有r r行上不在行上不在j j1 1，j jc c列上的列上的0 0元元素个数素个数 r r，这些，这些0 0元素至少有元素至少有r r个位个位于不同列于不同列同理：所有同理：所有c c列上不在列上不在i i1 1，i ir r行上行上的的0 0元素个数元素个数c c ，且这些，且这些0 0元素至元素至少有少有c c个位于不同个位于不同若上述两部分若上述两部分0 0个数总和为个数总和为S S，则，则SSmm；其中有；其中有mm个，又它们个，又它们必无重复元素，彼此独立，必无重复元素，彼此独立，则则S S M,M,故故有有m

19、mMM， 故可得故可得M=m.M=m.定理定理2 2说明说明：1. 1. 只要表中含有不同行或不同列的只要表中含有不同行或不同列的“0”0”元素，元素， 都可以通过直线覆盖的方式来找到它们都可以通过直线覆盖的方式来找到它们2. 2. 当覆盖直线的当覆盖直线的最少条数最少条数达到达到mm条条时，时， 必恰有必恰有mm个独立个独立“0”0”元素元素存在于表中存在于表中推论推论1 1：覆盖所有：覆盖所有“0”0”元素的元素的直线数直线数不同行不同列的不同行不同列的“0”0”元素的元素的最多个数（最多个数（mm）推论推论2 2：覆盖所有：覆盖所有“0”0”元素的元素的最少直线数最少直线数不同行不同列的

20、不同行不同列的“0”0”元素的元素的个数个数覆盖所有覆盖所有“0”0”元素的元素的独立的独立的“0”0”元素元素 的的最多个数最多个数( (三三) ) 匈牙利算法的步骤匈牙利算法的步骤 任务任务人员人员E EJ JG GR R甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811 119 9经第一步变换后，系数矩阵中每行每列都已有了经第一步变换后，系数矩阵中每行每列都已有了0 0元素元素但需找出但需找出mm个独立的个独立的0 0元素。元素。若能找出，就以这些独立若能找出，就以这些独立0 0元素对应解矩阵元素对应解矩阵(x(xij

21、 ij) )中中的元素为的元素为1 1，其余为，其余为0 0，这就得到最优解。，这就得到最优解。当当mm较小时，可用观察法、试探法去找出较小时，可用观察法、试探法去找出mm个独立个独立0 0元素。元素。若若mm较大时，就必须按一定的步骤去找，较大时，就必须按一定的步骤去找，常用的步骤为常用的步骤为: :步骤目标效率矩阵的变换：使表中有足够多的0行变换各行都有0生成的0对应的工时最小列变换各列都有0生成的0对应的工时最小检查矩阵：确定是否有m个独立0覆盖直线数列检查只有一个0，则标出以示该任务以优势方案派出并将该行划掉以示该人以优势方案安排如有多个0，则暂不标记该任务可派给多个人，哪个最优未定覆

22、盖线数不能达到“最小”行检查只有一个0，则标出以示该人以优势方案安排并将该列划掉以示该任务以优势方案派出如有多个0，则暂不标记该人可执行多个任务，哪个最优未定覆盖线数不能达到“最小”复查：当覆盖直线数m时，在未被划掉的元素中重复检查注意：注意：第一步第一步 将系数矩阵进行变换将系数矩阵进行变换经一次运算就可得每行每列都有0元素的系数矩阵，第二步第二步2在在打打 行行各元素都各元素都减去减去这这最小元素最小元素2 2在打在打 列列中各元素都中各元素都加上加上这这 最小元素最小元素2 2，以保证原来，以保证原来0 0元素不变元素不变v当指派问题的系数矩阵，经过变换得到了同当指派问题的系数矩阵，经过

23、变换得到了同行和同列中都有两个或两个以上行和同列中都有两个或两个以上0 0元素时。这元素时。这时可以任选一行时可以任选一行( (列列) )中某一个中某一个0 0元素，再划去元素，再划去同行同行( (列列) )的其他的其他0 0元素。这时会出现多重解。元素。这时会出现多重解。 9131541116141381441579102min24114 5911005324100115780min 0 0 5 0 541100032450115280( )( )( )( )( )( )22 2 06031305443000923( )( )( )( )( )( )( )( )令对应于令对应于 零元素的零元

24、素的位置的决策变量位置的决策变量x xij ij=1.=1.0010010000011000 甲甲乙乙丙丙丁丁英英日日德德俄俄即最优分配方案为即最优分配方案为: :甲译成俄文甲译成俄文乙译成日文乙译成日文丙译成英文丙译成英文丁译成德文丁译成德文全部所需时间为全部所需时间为4+4+9+11=28h.4+4+9+11=28h.得解矩阵为：得解矩阵为： 9131541116141381441579102115764戊69637丁86458丙9117129乙118957甲EDCBA费 工作 用人员4347511576469637964589117129118957 713203630452014240

25、5263402-1 -2 5032015304310140305242402 l =m=4 n=55032015304310140305242402 5032015304310140305242402 5033004203310240306231301-1-1+1 5033004203310240306231301 l =m=4 n=5 5033004203310240306231301 5033004203310240306231301 6044003202300230206130300-1+1+1+1-1-1-1 6044003202300230206130300 此问题有多个最优解此问题

26、有多个最优解 6044003202300230206130300 6044003202300230206130300 有一份中文说明书，需译成英、日、德、有一份中文说明书，需译成英、日、德、 俄四种文字，分别记作俄四种文字，分别记作A A、B B、C C、D D。现有甲、乙、丙、。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，间如下表所示，问如何分派任务，可使总时间最少？问如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982求解过程如下：求解过程如下：第一

27、步，变换系数矩阵：第一步，变换系数矩阵：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，试指派：第二步，试指派：找到找到 3 3 个独立零元素个独立零元素 但但 m = 3 n = 4m = 3 n = 4 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素：独立零元素的个数独立零元素的个数mm等于最少直线数等于最少直线数l l，即，即l lm=3m=3n n=4=4； 第四步，变换矩阵第四步，变换矩阵( (bij) )以增加以增加0

28、 0元素：没有被直线覆盖的所有元素：没有被直线覆盖的所有元素中的最小元素为元素中的最小元素为1 1，然后打，然后打各行都减去各行都减去1 1；打；打各列都加上各列都加上1 1，得如下矩阵，并转第二步进行试指派：，得如下矩阵，并转第二步进行试指派： 0100001000011000得到得到4 4个独个独立零元素，立零元素， 所以最优解所以最优解矩阵为：矩阵为：06244251343 15 6244251343 在实际应用中，经常遇到非标准形式的指派在实际应用中，经常遇到非标准形式的指派问题。处理方法：问题。处理方法：化标准，再按匈牙利算法求解。化标准，再按匈牙利算法求解

29、。三、非标准形指派问题三、非标准形指派问题1. 1. 最大化指派问题最大化指派问题目标函数变为：目标函数变为： m1im1jijijxazmaxa)a)上述目标函数等价于：上述目标函数等价于： m1im1jijijxazminb)b)应用应用定理一定理一，将之，将之化为标准形化为标准形：设最大化分配：设最大化分配问题效率矩阵问题效率矩阵A=aA=aij ij, ,其中其中最大元素最大元素为为mm。令。令B= B= bbij ij=m+(-am+(-aij ij) ) = =m-am-aij ij, , 则以则以B B为系数矩阵的最小为系数矩阵的最小化指派问题和以化指派问题和以A A为系数矩阵的

30、原最大化指派问为系数矩阵的原最大化指派问题有题有相同最优解相同最优解。最大化指派问题最大化指派问题 有有4 4种机械要分别安装在种机械要分别安装在4 4个工地，它们个工地，它们在在4 4个工地工作效率（见下表）不同。问应个工地工作效率（见下表）不同。问应如何指派安排，才能使如何指派安排，才能使4 4台机械发挥总的效台机械发挥总的效率最大？率最大？ 工地工地机器机器甲甲 乙乙 丙丙 丁丁30 25 40 3232 35 30 36 35 40 34 2728 43 32 38设最大化的指派问题系数阵设最大化的指派问题系数阵 ， 其中最大元素为其中最大元素为mm（本例中（本例中m=43m=43），

31、令矩阵），令矩阵nnijcC)(nnijnnijcmbB)()(本例中本例中38324328273440353630353232402530C511015169387138111131813B-3-7-3-0511015136050614801510-451101113601061080156圈圈0 0覆盖覆盖打打511011136010610801561B-1-1+141001012500062080166圈02B此时此时m=n=4,m=n=4,因此决策变量矩阵为因此决策变量矩阵为0010000110000100X即指派机械即指派机械安装在工地丙，安装在工地丙，机械机械安装在工安装在工地丁，

32、机械地丁，机械安装在工地甲，机械安装在工地甲，机械安装在工安装在工地乙，才能使地乙，才能使4 4台机器发挥总的效率最大。其台机器发挥总的效率最大。其总效率为总效率为38324328273440353630353232402530v人数和任务数不等的指派问题：人数和任务数不等的指派问题：v若人少任务多时，则添上一些虚拟的若人少任务多时，则添上一些虚拟的“人人”。这。这些虚拟的些虚拟的“人人”完成各任务的费用系数可取完成各任务的费用系数可取0，理解为这些费用实际上不会发生。理解为这些费用实际上不会发生。v若人多任务少时，则添上一些虚拟的若人多任务少时，则添上一些虚拟的“任

33、务任务”。这些虚拟的这些虚拟的“任务任务”被各人完成的费用系数同样被各人完成的费用系数同样也取也取0。三、非标准形指派问题三、非标准形指派问题 2 . 人数和任务数不等人数和任务数不等 工工作作 人人 1 3 6 2 6 2 7 1 4 4 3 3 6 5 8 4 6 4 3 7 5 5 2 4 3 6 5 7 6 2 工工作作 人人 1 3 6 2 6 0 0 2 7 1 4 4 0 0 3 3 6 5 8 0 0 4 6 4 3 7 0 0 5 5 2 4 3 0 0 6 5 7 6 2 0 0 增加假想列，以达到标准形式增加假想列，以达到标准形式 若某个人可做几件事，则可将该人化作相若某

34、个人可做几件事，则可将该人化作相同的几个同的几个“人人”来接受分配。这几个来接受分配。这几个“人人”做做同一件事的同一件事的费用系数费用系数当然都当然都一样一样。4.4.某事某事一定不能由某人做一定不能由某人做的分配问题：的分配问题： 若某事一定不能由某人做，则可将相应的若某事一定不能由某人做，则可将相应的费用系数取做足够大的数费用系数取做足够大的数MM，以使费用最小的，以使费用最小的最优解中一定不会出现相应的分配方案。最优解中一定不会出现相应的分配方案。3.3.一个人一个人可完成可完成多多件件任务任务的分配问题：的分配问题：三、非标准形指派问题三、非标准形指派问题某商业公司计划开办五家新商店

35、某商业公司计划开办五家新商店B Bi i(i (i=1,2,=1,2,5),5)。为了尽早建成。为了尽早建成 营业，商业公司营业，商业公司决定由决定由5 5家建筑公司家建筑公司A Aj j(j (j=1,2,=1,2,5),5)分别承建。已分别承建。已知建筑公司对新商店的建造报价（万元）为知建筑公司对新商店的建造报价（万元）为c cij ij(i,j(i,j=1,2,=1,2,5) ,5) 。商业公司应当对。商业公司应当对5 5家建筑公司家建筑公司 怎样分配建筑任务，才能使总的建筑费用最少？怎样分配建筑任务，才能使总的建筑费用最少？C610129610614767812961014179712

36、1578454321AAAAA54321BBBBB对于上例的指派问题，为了保证工程质量，经研对于上例的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司究决定，舍弃建筑公司 A A4 4 和和 A A5 5 ，而让技术，而让技术力量较强的建筑公司力量较强的建筑公司 A A1 1 、 A A2 2 和和 A A3 3 来承来承建。根据实际情况，可以允许每家建筑公司承建建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。一家或两家商店。求使总费用最少的指派方案。反映投标费用的系数矩阵为反映投标费用的系数矩阵为7812961014179712157841A2A3A1

37、B2B3B4B5B由于每家建筑公司最多可承建两家新商店，因此，把每家由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司（建筑公司化作相同的两家建筑公司（ 和和这样，系数矩阵变为：这样，系数矩阵变为：iA)3 , 2 , 1, iAi7812967812961014179710141797121578412157841B2B3B4B5B1A1A2A2A3A3A上面的系数矩阵有上面的系数矩阵有6 6行行5 5列，为了使列，为了使“人人”和和“任务任务”的数目相的数目相同，同，引入一件虚事引入一件虚事B B6 6 ，使之成为标准指派问题的系数矩阵：，使之成为标准指派问题

38、的系数矩阵：6B078129607812960101417970101417970121578401215784C1A1A2A2A3A3A1B2B3B4B5B6B再利用匈牙利法求解。再利用匈牙利法求解。078129607812960101417970101417970121578401215784C列变换00051200051203610130361013057000057000圈000051200051203610130361013057000057000-1-1+1再变换打覆盖100512100512025902025902157000157000圈00100000010001000000

39、00010000100000001X1A2A3A1B2B3B4B5B6B最优解最优解: : A A1 1承建承建B B1 1和和B B3 3 , A , A2 2承建承建B B2 2 , A , A3 3承建承建B B4 4 和和B B5 5 总建筑费用为总建筑费用为 总建筑费用为总建筑费用为010000001000100000000010000100000001X1A2A3A1B2B3B4B5B6B781296781296101417971014179712157841215784C3578974Z （万元）（万元） 下表所示分配问题：下表所示分配问题：甲甲 乙乙 丙丙 丁丁A AB BC C3 3 2 -2 1 2 -2 12 2 -2 0 - -2 0 - -1 1 0- -1 1 0效率阵中的元素表示四个人效率阵中的元素表示四个人完成三项工作所创造的利润完成三项