运筹学教学 | 分配问题代码分享（Java代码及详细注释）
内容提要
什么是分配问题
什么是匈牙利算法
匈牙利算法的实例教学
1
问题描述
什么是分配问题：
分配问题也称指派问题，是一种特殊的整数规划问题，分配问题的要求一般是这样的：
n个人分配n项任务，一个人只能分配一项任务，一项任务只能分配给一个人，将一项任务分配给一个人是需要支付报酬，如何分配任务，保证支付的报酬总数最小。
简单的说：就是n*n矩阵中，选取n个元素，每行每列各有一个元素，使得和最小。
2
匈牙利算法
解决分配问题的算法有多种，但是最常用的是匈牙利算法。
什么是匈牙利算法？
1、理论基础：
若从指派问题的系数矩阵的某行（列）各元素中分别减去或者加上常数k，其最优任务分解问题不变。
2.匈牙利算法的流程图
3.计算步骤
这个流程图...
看起来很复杂的样子？
下面小编用一个简单的例子来说明
例如：有A、B、C、D四项任务，需要分配给甲乙丙丁四个人来完成。他们完成任务所需要支付的酬劳如下表所示，问，如何分配任务，可使总费用最少？
得到的支付矩阵是：
Step 1: 行归约
找出每行的最小元素，分别从每行中减去这个最小元素；
矩阵变换如下：
Step 2 : 列归约
找出每列的最小元素，分别从每列中减去这个最小元素
经过以上两步变换，矩阵的每行每列都至少有了一个零元素。接下来就进行第三步，试着指派任务。
Step 3 : 指派任务
① 确定独立零元素。
i 从第一行(列)开始，若该行（列）中只有一个零元素，对该零元素标1，表示这个任务就指派给某人做。
每标一个1，同时将该零元素同列的其他零元素标为2，表示此任务已不能由其他人来做。（此处标1、2的操作与课本画圈、划去操作同理）
如此反复进行，直到系数矩阵中所有的零元素都已经被标为1或者2为止。
我们得到的矩阵如下：
② 指派
我们观察到，系数矩阵中标记为1的零元素正好等于4，这表示已经确定了最优的指派方案。
此时，只需将0（1）所在位置记为1，其余位置记为0，则获得了该问题的最优解。
最优解为：
即：A任务交给丙负责，B任务交给丁负责，C任务交给甲负责，D任务交给乙负责。
此时总报酬为：1+5+2+3 = 11；
至此，指派问题就解决拉？
这么..简单吗？
好吧，上例仅为一种理想情况
正常情况下，我们在对支付矩阵进行变换时
会出现两种情况
① 出现零元素的闭合回路
②标记成1的元素个数小于n
为了让支付矩阵中出现个独立零元素，需要对支付矩阵进行变换。
下面我们针对这两种情况举例说明：
01
i.出现零元素的闭合回路（有多于两行或两列存在两个以上的零元素。）
对于矩阵：
我们所有变化后，得到矩阵：
图的第一行的一二列零元素和第四行的一二列零元素构成回路
这里我们的处理方法是：
先对cost方阵做一个备份（因为会出现多解），然后我们可以顺着回路的走向，对间隔的零元素标记成1，然后对标记成1的零元素所有的行列划一条直线，把这两条直线的其他零元素标记成2,得到一种结果后，再求出多解。
这里我们采用间隔标记法，得到矩阵：
最优解为：
最小酬劳为：1+2+2+2=7
02
ii. 矩阵中所有标记成1的零元素小于n。
例如矩阵：
经过所有变换后得到矩阵：
被标为1的0总共有3个，小于4。
因此，我们需要对其进行【画盖0线】的操作。（即画出可以覆盖最多0元素的直线）
（1）画盖0线：利用最少的水平线和垂直线覆盖所有的零。
具体操作如下：
① 对没有标记为1的零元素所在的行打√；
②在已打“√”的行中，对标记为2的零元素所在列打√
③ 在已打“√”的列中，对标记为1的零元素所在行打“√”
④重复②和③，直到再不能找到可以打√的行或列为止。
⑤对没有打“√”的行画一横线，对打“√”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。
对矩阵进行操作：
① 打勾
② 划线
（2）继续变换系数矩阵
①在未被覆盖的元素中找出一个最小元素。
②对未被覆盖的元素所在行中各元素都减去这一最小元素。这时已被覆盖的元素中会出现负元素。
③对负元素所在的列中各元素加上这一最小元素。
对上述矩阵：20为未被覆盖元素中最小的元素。变换矩阵，并寻找得：
Step4
我们发现，在经过一次变换后，独立零元素的个数仍然少于4.此时返回第三步，反复进行，直到矩阵中每一行都有一个被标记为1的元素为止。
例如在上述矩阵中：
矩阵中独立零元素仍然小于n。对矩阵执行打勾、划线等操作，得出未被覆盖区最小元素为5，进行系数变换之后得到矩阵：
我们发现得到的矩阵每行列有多个零元素（零元素的闭合回路），再运用上述方法可以得到矩阵：
最优解为：
最小酬劳为：15+65+25+50=155
以上，我们的指派问题和匈牙利算法原理就
搞！定！拉！
3
代码实例说明
import java.util.InputMismatchException;
import java.util.Scanner;
public class Main
{
public static Matrix hungary = new Matrix();
public static int[][] result;
static Matrix input() //初始输入
{
Scanner in = new Scanner(System.in);
int i,j;
Matrix hungary = new Matrix();
System.out.println("指派问题的匈牙利解法");
System.out.println("请输入cost矩阵的阶数:");
try
{
hungary.matrixsize = in.nextInt();
System.out.println("请输入代表工人和工件的" + hungary.matrixsize + "阶矩阵:\n");
for(i=1;i<=hungary.matrixsize;i++)
{
for(j=1;j<=hungary.matrixsize;j++)
{
hungary.cost[i][j] = in.nextInt();
hungary.costforout[i][j]=hungary.cost[i][j];
}
}
in.close();
}
catch(InputMismatchException e)
{
System.out.println(e);
System.exit(-1);
}
return hungary;
}
static void zeroout(Matrix hungary) //减去行列的最小值得到零元素
{
int i,j;
int tem; //表示同行的最大元素或同列的最小元素
for(i=1;i<=hungary.matrixsize;i++) //减去同行最小元素
{
tem=hungary.cost[i][1];
for(j=2;j<=hungary.matrixsize;j++)
if(hungary.cost[i][j]<tem)
tem=hungary.cost[i][j];
for(j=1;j<=hungary.matrixsize;j++)
hungary.cost[i][j]=hungary.cost[i][j]-tem;
}
for(j=1;j<=hungary.matrixsize;j++) //减去同列最小元素
{
tem=hungary.cost[1][j];
for(i=2;i<=hungary.matrixsize;i++)
if(hungary.cost[i][j]<tem)
tem=hungary.cost[i][j];
for(i=1;i<=hungary.matrixsize;i++)
hungary.cost[i][j]=hungary.cost[i][j]-tem;
}
}
static void circlezero(Matrix hungary) //圈出单行列零元素
{
int i,j,p;
int flag;
for(i=0;i<=hungary.matrixsize;i++) //在矩阵外面构建半圈矩阵标记0的个数；
hungary.cost[i][0]=0;
for(j=1;j<=hungary.matrixsize;j++)
hungary.cost[0][j]=0;
for(i=1;i<=hungary.matrixsize;i++)
for(j=1;j<=hungary.matrixsize;j++)
if(hungary.cost[i][j]==0)
{
hungary.cost[i][0]++;
hungary.cost[0][j]++;
hungary.cost[0][0]++;
}
for(i=0;i<=hungary.matrixsize;i++) //新建一个矩阵
for(j=0;j<=hungary.matrixsize;j++)
hungary.zeroelem[i][j]=0;
flag=hungary.cost[0][0]+1;
while(hungary.cost[0][0]<flag) //未被标记为(1)或(2)的0元素个数在两遍搜索后不变则结束循环
{
flag=hungary.cost[0][0];
for(i=1;i<=hungary.matrixsize;i++) //第一遍先行后列
{
if(hungary.cost[i][0]==1) //行中仅存在1个未被任何标记的0元素
{
for(j=1;j<=hungary.matrixsize;j++)
if(hungary.cost[i][j]==0&&hungary.zeroelem[i][j]==0)
break;
hungary.zeroelem[i][j]=1;
hungary.cost[i][0]--;
hungary.cost[0][j]--;
hungary.cost[0][0]--;
if(hungary.cost[0][j]>0) //对标(1)的0元素所在列的其它未被标记的0元素标(2)
for(p=1;p<=hungary.matrixsize;p++)
if(hungary.cost[p][j]==0&&hungary.zeroelem[p][j]==0)
{
hungary.zeroelem[p][j]=2;
hungary.cost[p][0]--;
hungary.cost[0][j]--;
hungary.cost[0][0]--;
}
}
}
for(j=1;j<=hungary.matrixsize;j++) //第二遍先列后行
{
if(hungary.cost[0][j]==1) //列中仅存在1个未被任何标记的0元素
{
for(i=1;i<=hungary.matrixsize;i++)
if(hungary.cost[i][j]==0&&hungary.zeroelem[i][j]==0)
break;
hungary.zeroelem[i][j]=1;
hungary.cost[i][0]--;
hungary.cost[0][j]--;
hungary.cost[0][0]--;
if(hungary.cost[i][0]>0) //对标(1)的0元素所在行的其它未被标记的0元素标(2)
for(p=1;p<=hungary.matrixsize;p++)
if(hungary.cost[i][p]==0&&hungary.zeroelem[i][p]==0)
{
hungary.zeroelem[i][p]=2;
hungary.cost[i][0]--;
hungary.cost[0][p]--;
hungary.cost[0][0]--;
}
}
}
}
if(hungary.cost[0][0]>0) //存在未被标记为(1)或(2)的0元素
twozero(hungary);
else
judge(hungary,result);
}
static void judge(Matrix hungary,int result[][]) //判断是否符合匈牙利算法条件
{
int i,j;
int num=0; //线的条数
int start; //每组解的储存开始位置
for(i=1;i<=hungary.matrixsize;i++)
for(j=1;j<=hungary.matrixsize;j++)
if(hungary.zeroelem[i][j]==1)
num++; //划线的条数/标记为(1)的0元素个数
if(num==hungary.matrixsize) //与矩阵阶数相同则符合
{
start=result[0][0]*hungary.matrixsize+1;
for(i=1;i<=hungary.matrixsize;i++)
for(j=1;j<=hungary.matrixsize;j++)
if(hungary.zeroelem[i][j]==1)
{
result[start][0]=i;
result[start++][1]=j;
}
result[0][0]++;
}
else //否则需要进行变形
refresh(hungary);
}
static void twozero(Matrix hungary)
{
int i,j;
int p,q;
int m,n;
int flag;
Matrix backup = new Matrix();
for(i=1;i<=hungary.matrixsize;i++)
if(hungary.cost[i][0]>0)
break;
if(i<=hungary.matrixsize)
{
for(j=1;j<=hungary.matrixsize;j++)
{
backup= hungary.clone();//备份以寻找多解
if(hungary.cost[i][j]==0&&hungary.zeroelem[i][j]==0)
{
hungary.zeroelem[i][j]=1;
hungary.cost[i][0]--;
hungary.cost[0][j]--;
hungary.cost[0][0]--;
for(q=1;q<=hungary.matrixsize;q++)
if(hungary.cost[i][q]==0&&hungary.zeroelem[i][q]==0)
{
hungary.zeroelem[i][q]=2;
hungary.cost[i][0]--;
hungary.cost[0][q]--;
hungary.cost[0][0]--;
}
for(p=1;p<=hungary.matrixsize;p++)
if(hungary.cost[p][j]==0&&hungary.zeroelem[p][j]==0)
{
hungary.zeroelem[p][j]=2;
hungary.cost[p][0]--;
hungary.cost[0][j]--;
hungary.cost[0][0]--;
}
flag=hungary.cost[0][0]+1;
while(hungary.cost[0][0]<flag)
{
flag=hungary.cost[0][0];
for(p=i+1;p<=hungary.matrixsize;p++)
{
if(hungary.cost[p][0]==1)
{
for(q=1;q<=hungary.matrixsize;q++)
if(hungary.cost[p][q]==0&&hungary.zeroelem[p][q]==0)
break;
hungary.zeroelem[p][q]=1;
hungary.cost[p][0]--;
hungary.cost[0][q]--;
hungary.cost[0][0]--;
for(m=1;m<=hungary.matrixsize;m++)
if(hungary.cost[m][q]==0&&hungary.zeroelem[m][q]==0)
{
hungary.zeroelem[m][q]=2;
hungary.cost[m][0]--;
hungary.cost[0][q]--;
hungary.cost[0][0]--;
}
}
}
for(q=1;q<=hungary.matrixsize;q++)
{
if(hungary.cost[0][q]==1)
{
for(p=1;p<=hungary.matrixsize;p++)
if(hungary.cost[p][q]==0&&hungary.zeroelem[p][q]==0)
break;
hungary.zeroelem[p][q]=1;
hungary.cost[p][q]--;
hungary.cost[0][q]--;
hungary.cost[0][0]--;
for(n=1;n<=hungary.matrixsize;n++)
if(hungary.cost[p][n]==0&&hungary.zeroelem[p][n]==0)
{
hungary.zeroelem[p][n]=2;
hungary.cost[p][0]--;
hungary.cost[0][n]--;
hungary.cost[0][0]--;
}
}
}
}
if(hungary.cost[0][0]>0) //确保hungary.cost[][]中的0元素都在zeroelem[][]中被完全标记出来。
twozero(hungary);
else
judge(hungary,result);
}
hungary=backup;
}
}
}
static void refresh(Matrix hungary) //不符合条件，对矩阵进行变形
{
int i,j,min=0;
int flag1=0,flag2=0;
for(i=1;i<=hungary.matrixsize;i++)
{
for(j=1;j<=hungary.matrixsize;j++)
if(hungary.zeroelem[i][j]==1)
{
hungary.zeroelem[i][0]=1; //有独立零元素
break;
}
}
while(flag1==0)
{
flag1=1;
for(i=1;i<=hungary.matrixsize;i++)
if(hungary.zeroelem[i][0]==0)
{
hungary.zeroelem[i][0]=2;
for(j=1;j<=hungary.matrixsize;j++)
if(hungary.zeroelem[i][j]==2)
{
hungary.zeroelem[0][j]=1;
}
}
for(j=1;j<=hungary.matrixsize;j++)
{
if(hungary.zeroelem[0][j]==1)
{
hungary.zeroelem[0][j]=2;
for(i=1;i<=hungary.matrixsize;i++)
if(hungary.zeroelem[i][j]==1)
{
hungary.zeroelem[i][0]=0;
flag1=0;
}
}
}
} //对打勾的行和列标记成2
for(i=1;i<=hungary.matrixsize;i++)
{
if(hungary.zeroelem[i][0]==2)
{
for(j=1;j<=hungary.matrixsize;j++)
{
if(hungary.zeroelem[0][j]!=2)
if(flag2==0)
{
min=hungary.cost[i][j];
flag2=1;
}
else
{
if(hungary.cost[i][j]<min)
min=hungary.cost[i][j];
}
}
}
} //寻找未被覆盖的最小值
for(i=1;i<=hungary.matrixsize;i++)
{
if(hungary.zeroelem[i][0]==2)
for(j=1;j<=hungary.matrixsize;j++)
hungary.cost[i][j]=hungary.cost[i][j]-min;
}
for(j=1;j<=hungary.matrixsize;j++)
{
if(hungary.zeroelem[0][j]==2)
for(i=1;i<=hungary.matrixsize;i++)
hungary.cost[i][j]=hungary.cost[i][j]+min;
} //未被划线的行减去未被覆盖的最小值，被划线的列加上未被覆盖的最小值
for(i=0;i<=hungary.matrixsize;i++)
for(j=0;j<=hungary.matrixsize;j++)
hungary.zeroelem[i][j]=0; //矩阵清0
circlezero(hungary);
}
static void output(int result[][],Matrix hungary)
{
int num; //解的数量
int minsum; //最小的工作成本
int i,j;
int start; //每个解的储存开始位置
minsum=0;
for(i=1;i<=hungary.matrixsize;i++)
{
minsum=minsum+hungary.costforout[i][result[i][1]];
}
System.out.println("最优解的目标函数值为" + minsum + "。");
num=result[0][0];
System.out.println("有" + num + "种解。");
for(i=1;i<=num;i++)
{
System.out.println("第" + i + "种解：");
start=(i-1)*hungary.matrixsize+1;
for(j=start;j<start+hungary.matrixsize;j++)
System.out.println("第" + result[j][0] + "个人做第" + result[j][1] + "件工作。");
System.out.println();
}
}
public static void main(String[] args)
{
result = new int [5041][2];
result[0][0]=0;
hungary=input();
zeroout(hungary);
circlezero(hungary);
output(result,hungary);
}
}
class Matrix
{
public int[][] cost;
public int[][] zeroelem;
public int[][] costforout;
public int matrixsize;
public Matrix()
{
costforout = new int [101][101];
zeroelem = new int [101][101];
cost = new int [101][101];
}
public Matrix(Matrix m)
{
costforout = new int [101][101];
zeroelem = new int [101][101];
cost = new int [101][101];
for(int q = 0; q < 101; q++)
{
for(int w = 0; w < 101; w++)
{
this.costforout[q][w] = m.costforout[q][w];
this.zeroelem[q][w] = m.zeroelem[q][w];
this.cost[q][w] = m.cost[q][w];
}
}
this.matrixsize = m.matrixsize;
}
public Matrix clone()
{
return new Matrix(this);
}
}
需要注意的是，为了让支付矩阵中出现个独立零元素而对支付矩阵进行变换的过程是一个递归过程。如果数据规模较大或矩阵中花费较为接近，规约后出现0的数目较多，就需要多次嵌套地进行间隔标记或画盖0线的操作，这样一来，计算时间将会呈阶乘级别增加。
举个简单的例子，对于花费全部为1的4阶矩阵，测试得到的计算时间为0.301s；对于花费全部为1的5阶矩阵，测试得到的计算时间为1.41s，而对于花费全部为1的6阶矩阵，测试得到的计算时间则为5.21s。可以预见，当同等类型数据的规模进一步加大时，求解问题所需的时间将是惊人的。
以上即为分配问题算法及代码的全部内容，你看明白了吗？
-The End-
代码改写：吕其乐（华中科技大学管理学院本科二年级）
指导老师：秦虎老师 （华中科技大学管理学院）
如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。
腾讯云开发者
