分配问题与实验

第四章 分配问题与实验 这类问题称为分配问题，又称为指派问题（Assignment Problem）。分配问题是运输问题的特殊情况，并且其特殊的结构允许作为线性规划中更有效的原始对偶单纯形法的应用，全部的程序能在一个简单排列上产生，并且其标号过程是简单的，此结果是匈牙利（Hungarian）算法。4.1 分配问题的数学模型标准分配问题模型 设有n个人被分配去做n件事，规定每个人只做一件工作，每件工作只由一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为（ ），并假设。问应如何分配才能使总效率（总时间或总费用最少等）最高？设决策变量（其中）。那么第i个人做第j件工作的效率为。从而i=1,n; j=1,n;的综合即为总效率。每件工作都有人去做，使用数学表达式为同样，每个人都有工作做，为于是分配问题的数学模型为：；s.t.类似对运输问题特点的分析可知，分配问题约束条件系数矩阵A的秩为2n-1，故它的基可行解中共有2n-1个基变量。但实际上只需要找出n个1即可（即分配n个人去做n件不同的工作），而其余n-1个基变量取值为0，因此这是一个高度退化的线性规划问题。考察分配问题的数学模型，将目标函数的系数排成下列矩阵：称之为分配问题的效益矩阵。它有下列基本性质。定理4.1 从效益矩阵的第k行（或第k列）的每一个元素中减去一个常数a，得到新效益矩阵所表示的分配问题与原问题具有相同的最优解。其证明比较简单，读者可自行证明。记效益矩阵的某行（列）的每一个元素中减去一个常数得到新的效益矩阵称为缩减效益矩阵。根据定理4.1，可以将求解效益矩阵为的分配问题化成求解效益矩阵为的分配问题。这里是由的各行、各列中分别减去该行、该列的最小元素而得到的。不难看出中的每行、每列中至少有一个零元素。如果这些零元素分布在效益矩阵的不同行和不同的列上，则称这些零元素为独立的零元素。如果这些独立的零元素的个数恰好等于效益矩阵的阶数，则将独立零元素所在位置对应的取1，将其余变量取为0。这时，已找到了这个分配问题的最优解。如果没有得到独立的零元素，或者独立零元素的个数小于效益矩阵的阶数，则必须寻找某种方法继续调整缩减效益矩阵，直至找到独立零元素的个数等于效益矩阵的阶数为止。称这些独立零元素对应的效益矩阵为全分配矩阵。由此，分配问题求解的关键是如何调整效益矩阵，使之成为全分配矩阵。下面介绍的关于矩阵中零元素的定理就是构造这类算法的基础。定理4.2 若一方阵中的一部分元素为0，一部分元素为非0，则覆盖方阵内所有0元的最少直线数恰好等于那些位于不同行、不同列的0元的最多个数。(证明省略) 。匈牙利算法基于一种必须兼备下述三个条件的称为分配模型的标准形模型：（1） 目标要求为min；（2） 效益矩阵为n阶方阵；（3） 阵中所有元素，且为常数。4.2 分配问题和匈牙利算法根据以上两个定理，可将匈牙利算法的解题步骤归纳如下：第一步：将原分配问题的效益矩阵进行变换得矩阵，使各行各列中都出现零元素。其方法是：（1） 从效益矩阵得每行元素中减去该行得最小元素；（2） 再从所得效益矩阵得每列元素中减去该列得最小元素。第二步：进行试分配，求此按以下步骤进行。（1） 从零元素最少的行（或列）开始，给这个零元素加“横杠”，记作。然后划去该零元素所在列（或行）得其它零元素，记作。（2） 给只有一个零元素的列（或行）中的零元素加“横杠”，然后划去该零元素所在行（或列）的零元素，记作。（3） 反复进行（1），（2）两步，直到所有零元素都被“横杠”划出或划去为止。（4） 若仍有没有被“横杠”划出或划去的零元素，且同行（或列）的零元素至少有两个。这时可用不同的方案去试探。从剩有零元素最少的行（或列）开始，比较这行零元素所在列中零元素的数目，选择零元素较少的那列的这个零元素加“横杠”，然后划去同行同列的其它零元素。如此反复进行，直到所有的零元素都已划出或划去。（5） 若元素的数目m等于矩阵的阶数n，那么这个分配问题的最优解已经得到，令划“横杠”处的变量，其余变量，即为所求的最优解。否则，若，则转入下一步。第三步：寻找覆盖所有零元素的最少直线，以确定该矩阵中能找到的最多的独立零元素的个数。为此按以下步骤进行。（1） 对没有的行打*号；（2） 对已打*号的行中所有含元素的列打*号；（3） 再对打有*号的列中含有元素的行打*号；（4） 重复（2），（3），直到得不出新的打*号的行、列为止。（5） 对没有打*号的行划横线，有打*号的列划纵线，这就得 到覆盖所有零元素的最少直线数。令这直线数为l。若 ，说明必须再变换当前的矩阵，才能找到n个独立 零元素，则转第四步；若，而，则返回第三步 （4），另行试探。第四步：调整，使之增加一些零元素。为此按如下步骤进行。（1） 在没有被直线段覆盖的元素中，找出最小元素；（2） 在没有被直线段覆盖的元素中，减去这个最小元素；（3） 在被两条直线段覆盖（横线和纵线交叉处）的元素加上 这个最小元素；（4） 被一条直线覆盖（横线和纵线）的元素不变。 得新的缩减矩阵，再返回第二步。 例4.1 设有五项工作A，B，C，D，E，需分配甲、乙、丙、丁、戊五个人去完成。每个人只能完成一件工作，每件工作只能由一个人去完成。五个人分别完成各项工作所需得费用如表4.1所示。问如何分配工作才能使费用最省？表4.1费 工作ABCDE 用人甲乙丙丁戊8979461245610738791151151298811解： 第一步：先将效益矩阵进行如下变换，矩阵右边表示减区去所对应的行中减去最小元素，矩阵下边行表示减去所对应的列中最小元素若是最小元素零则不表示。 第二步：进行试分配，求初始分配方案得 第三步：寻找覆盖所有零元素的最少直线，以确定最多独立零元素的个数。为此，先对矩阵的第4行打*，再对第2列打*，最后对第1行打*，得再用直线去覆盖第2，3，5行和第2列，得覆盖所有零元素得最少直线数为（矩阵的阶数）。第四步：调整，使之增加一些零元素。为此，先找出没有被直线覆盖的元素的最小元素。然后将矩阵变换为再返回第二步。进行试分配，得再进行第三步，寻找覆盖所有零元素的最少直线，得此时最少直线仍为。再进行第四步。先找出未被直线覆盖得最小元素。再进行调整，得再返回第二步，进行试分配，得此时，独立零元素得个数。于是已经求得最优解，其余。目标函数最优值：。这个问题有多个最优解，例如也是最优解。一般说来，当分配问题得效益矩阵经过变换后，得到的缩减矩阵中，若同行和同列都有两个或两个以上的零元素，这时可以任选一行（列）中某一个零元素进行分配，同时划去同行（列）中的其它零元素，这时会出现多种最优解。其算法归纳为： 求出未被左线覆盖部分中的最小元素； 将右标号各行的元都减去； 将有标号（）各列中的元都加上。缩减矩阵中元素变化概括为有标号(*) 的列无标号(*) 的列有标号(*) 的行 不变 无标号(*) 的行 + 不变用直线覆盖来概括为缩减矩阵中所未覆盖的元都减去；单重覆盖（只被一条直线覆盖）者不变；双重覆盖（同时被纵横两条直线覆盖）者增加。4.3 LINGO软件计算实例使用LINGO软件来计算上例，程序编制如下：model:! A 5 Worker, 5 Job Assigment Problem;SETS: WORKER / W1, W2, W3, W4, W5/ : CAPACITY; JOB / J1, J2, J3, J4,J5/ : DEMAND; ROUTES( WORKER,JOB ) : COST, VOLUME;ENDSETS! The objective; OBJ MIN = SUM( ROUTES: COST * VOLUME);! The demand constraints; FOR( JOB( J): DEM SUM( WORKER( I): VOLUME( I, J) = DEMAND( J);! The supply constraints; FOR( WORKER( I): SUP SUM( JOB( J): VOLUME( I, J) = CAPACITY( I);! Here are the parameters;DATA: CAPACITY = 1, 1, 1, 1, 1; DEMAND = 1, 1, 1, 1, 1; COST = 8, 6, 10, 9, 12, 9, 12, 7, 11, 9, 7, 4, 3, 5, 8, 9, 5, 8, 11, 8, 4, 6, 7, 5, 11;ENDDATAend程序各行执行的含义分析见运输问题，而与运输问题比较改变的是发量和需量，其分配问题的发量和需量都为1。 选用Generate命令将出现：使用SOLVE命令，得到数值结果如下（去掉其中效益矩阵系数），同计算一样，例4.2 设有七项工作A、B、C、D、E、F、G需分配a、b、c、d、e、f、g七个人去完成。每个人只能完成一件工作，每件工作只能由一个人去完成。七个人分别完成各项工作所需得费用如表4.2所示。问如何分配工作才能使费用最省？表4.2费 工作ABCDEFG 用人abcdefg6457259292635265179237393521248797842542211558376410解：使用LINGO软件来计算例4.2，程序编制如下：MODEL:! A 7 Workers, 7 Jobs Assigment Problem;SETS: WORKERS / W1 W2 W3 W4 W5 W6 W7/: CAPACITY; JOBS / J1 J2 J3 J4 J5 J6 J7 / : DEMAND; LINKS( WORKERS, JOBS): COST, VOLUME;ENDSETS! The objective; MIN = SUM( LINKS( I, J): COST( I, J) * VOLUME( I, J);! The demand constraints; FOR( JOBS( J): SUM( WORKERS( I): VOLUME( I, J) = DEMAND( J);! The capacity constraints; FOR( WORKERS( I): SUM( JOBS( J): VOLUME( I, J) = CAPACITY( I);! Here is the data;DATA: CAPACITY = 1 1 1 1 1 1 1; DEMAND = 1 1 1 1 1 1 1 ; COST = 6 2 6 7 4 2 5 4 9 5 3 8 5 8 5 2 1 9 7 4 3 7 6 7 3 9 2 7 2 3 9 5 7 2 6 5 5 2 2 8 11 4 9 2 3 12 4 5 10;ENDDATAEND此程序各行的解释，详细参见运输问题。使用SOLVE命令，得到数值计算结果如下：（去掉效益矩阵和任务与工作约束系数的系数表示）求得最优解，其余。目标函数最优值：。4.5 匹配问题匹配问题模型：有N件物体，设法以最小的费用来匹配成对。例如，假设班级同学分配宿舍，每个宿舍两人，对于对（）和（）是难以分辨的，即等同的，所以我们只需要以的配对，换句话表示，我们并不需要通常多余和有序对，而只需要那些的对（），下面描述匹配问题的LINGO软件程序设计。MODEL:SETS: ANALYSTS / 1.8/; PAIRS( ANALYSTS, ANALYSTS) | &2 #GT# &1: RATING, MATCH;ENDSETSDATA: RATING = 9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4;ENDDATAMIN = SUM( PAIRS( I, J): RATING( I, J) * MATCH( I, J);FOR( ANALYSTS( I): SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) = 1 );FOR( PAIRS( I, J): BIN( MATCH( I, J);END第4行定义8个所要匹配的事件。第6行PAIR(OBJ，OBJ)&1#LT#2:C;X；表示对LT两类元素都来自于原始集合OBJ。这里建立对集中元素对(OBJ，OBJ)必须满足&1小于(#LT#)&2。解LINGO软件，解只有存在形式而序对与相同。使用SOLVE命令，得到数值计算结果如下：（去掉效益矩阵和任务与工作约束系数的系数表示）求得最优解，其余。目标函数最优值：。4. 6 二次分配问题模型本节中补充使用LINGO 软件中二次分配问题模型和求解，现从例子作简单解释。给定飞机间转机认输和登机门间的距离，二次分配问题将解出如何安排飞机至登机门总的转换飞机人的总距离最小？具体问题为，有三架飞机和四个登机口，此模型求解三架飞机和4个登机们，N表示飞机间转换人数，T为登机门间距离，分别使用集合FLIGHT和集合GATE赋值，登机口间的距离矩阵为T，而飞机间转机人数矩阵为N，程序分别使用GXG(，)和FXF(，)来赋值，这里， MODEL:! A quadratic assignment problem: Given transfers between flights and distance between gates, assign flights to gates to minimize total transfer distance; SETS: FLIGHT/1.3/; ! There are three flights; GATE/1.4/; ! There are five gates; FXG( FLIGHT, GATE): X; !Flight-gate assignment; GXG( GATE, GATE): T; !Distance between gates; FXF( FLIGHT, FLIGHT): N; !Transfers btwn flights; ENDSETS DATA: N = 0 30 5 ! No. transfers between flights; 20 0 0 30 40 0 ; T = 0 5 10 14 ! distance between gates; 5 0 5 10 10 4 0 6 15 10 5 0 ; ENDDATA SETS: ! Transfer between 2 flights must be required and related to 2 different gates. Warning: this set gets big fast.; TGTG( FLIGHT, GATE, FLIGHT, GATE)| &1 #LT# &3 #AND# ( N( &1, &3) #NE# 0) #AND# ( T( &2, &4) #NE# 0) #OR# ( N( &3, &1) #NE# 0) #AND# ( T( &4, &2) #NE# 0): Y; ENDSETS ! Each flight, B, must be assigned to a gate; FOR( FLIGHT( B): SUM( GATE( J): X( B, J) = 1); ! Each gate, J, can receive at most one flight; FOR( GATE( J): SUM( FLIGHT( B): X( B, J) = X( B, J) + X( C, K) - 1); ! Min the sum of transfers * distance; MIN = SUM( TGTG( B, J, C, K): Y( B, J, C, K) * ( N( B, C) * T( J, K) + N( C, B) * T( K, J); ! Make the Xs 0/1 (Ys will naturally be 0/1); FOR( FXG: BIN( X);END求解得为飞机和登机门间分配。表示分配至和分配至。求得总的转机人的总距离最短，最优值为Objective value.使用SOLVE命令，得到数值结果如下: 迭代150次获得最优值为760单位，最优解为其余即飞机1分配于第一个登机口，飞机2分配于第2个登机口，飞机3分配于第3个登机口。4.7 分配问题的应用多次分组会议的最佳安排方案（本问题由97年美国大学生数模赛题简化而得）某公司举行一个由29个委员参加的会议。会议分七场进行，每场会议又分5个小组，每个小组人数均衡。现要求给出7场会议的每一场各个组中，有哪些委员参加的安排表。这个安排方案应尽可能使任二个委员之间有相互交流的机会。模型建立与分析：显然在这七场会议中不可能使任二个委员都有机会见面，所以尽可能使任二个委员有相互交流的机会。设变量指标：表示：委员指标，；表示：组别指标，；表示：场次指标，；见面的定义为当二个委员在某场会议中被安排在同一小组，则认为该两个委员见了一次面，其他情况的会面不计入见面次数。对某场会议的委员分组，使用一个分组矩阵来描述分组情况。对于委员i来说，他被分在某一组，那么他在该组出现的次数记为“1”，否则记为“0”。若某场会议的分组矩阵为295方阵：委员小组111291相应地可得一个矩阵01000100000100000010由题意知，该分组矩阵有如下特点：1) 每一个元素为0或1；2) 每一行元素之和为1；3) 每一列元素之和为5或6。一般情况，有分组矩阵p1,1 p 1,2 p 1,5P= p 2,1 p 2,2 p 2,5 =( p ik)295p 29,1 p 29,2 p 29,.5其中，表示pik委员i在第k组中出现的次数，也表示委员i是否被分在第k