① 求二分图最大匹配的Matlab程序
[numh]=maxnum(g);%g是二分图邻接矩阵
%调用了一个自己写maxnum函数，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的内容，用的是匈牙利算法
其中还用了一个递归的incpath函数，寻找增广路径
function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩阵hij记录选中
globalG_g;%矩阵gij记录匹配
globalG_v;%记录当前一次路径访问过的节点
G_h=false(s);%矩阵hij初始为空
G_g=g;%矩阵gij就是传递进来的参数g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化径访问过的节点为空
incpath(i);%从Ai开始寻找增广路径
end
h=G_h;num=sum(h(:));%输出最大匹配数，和匹配矩阵h
clearglobal'G_h';clearglobal'G_g';
end
functionOK=incpath(i)%从Ai开始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%寻找合条件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，标记Bj为以访问节点
ii=find(G_h(:,j));%寻找Bj在原来匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增广路径末端，返回true
ok=incpath(ii);%如果在原来的匹配中，根据匹配对应的Aii递归调用incpath寻找
ifok%如果递归寻找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路径反色返回true
end
② 求下列所示的有效矩阵的指派问题最优解3 8 2 10 128 7 2 9 76 ...
为了解你这道题,我又重新把运筹学又看了一遍,然后去matlab论坛找解决方案.最终得出指派矩阵如下：1
0
0
0
00
0
1
0
00
1
0
0
00
0
0
1
00
0
0
0
1最优值为22ps：如果手动解的话,可以采用匈牙利算法,但是不提倡使用手动求解.将相应的算法变成程序,用的时候直接调用程序比较方便(如参加数学建模的时候,这类程序最好提前准备).另外,像这种比较专业的问题,我建议你去专业论坛去问或查看一些帖子对你一定非常有帮助.matlab程序如下（非原创）：>>
c=[3
8
2
10
12;8
7
2
9
7;6
4
2
7
5
8
4
2
3
5;9
10
6
9
10];
c=c(:);
a=zeros(10,25);
for
i=1:5
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),y
③ 二分图最大匹配Matlab程序（在线等，感激不尽！）
第一个问题比较简单，这里懒得对着你的图片敲数据，用随机数代替
long=100;
A=0.1*rand(long,1);
B=0.15*rand(long,1);
[AA BB]=meshgrid(A,B);
gg=0.5017*AA-0.65*BB;
g=gg>=-0.03&gg<=0.03; %这就是gij矩阵，相当于二分图的连接矩阵
[num h] = maxnum(g);%第二个问题就是求二分图的最大匹配问题，这里
%调用了一个自己写maxnum函数，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的内容，用的是匈牙利算法
其中还用了一个递归的incpath函数，寻找增广路径
function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩阵hij记录选中
globalG_g;%矩阵gij记录匹配
globalG_v;%记录当前一次路径访问过的节点
G_h=false(s);%矩阵hij初始为空
G_g=g;%矩阵gij就是传递进来的参数g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化径访问过的节点为空
incpath(i);%从Ai开始寻找增广路径
end
h=G_h;num=sum(h(:));%输出最大匹配数，和匹配矩阵h
clearglobal'G_h';clearglobal'G_g';
end
functionOK=incpath(i)%从Ai开始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%寻找合条件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，标记Bj为以访问节点
ii=find(G_h(:,j));%寻找Bj在原来匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增广路径末端，返回true
ok=incpath(ii);%如果在原来的匹配中，根据匹配对应的Aii递归调用incpath寻找
ifok%如果递归寻找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路径反色返回true
end
④ 匈牙利算法网上下载的MATLAB程序（fenpei.m)为什么会出现死循环跪求答案！！
那估计是因为输入的新的数据不符合程序允许,或者超过极限值之类的吧
⑤ 急急急！！！寻匈牙利算法、KM算法的代码！
寻匈牙利算法:
function [result,msum]=sbppp(cost,m)
if nargin==1
dd=cost;
else
dd=max(max(cost))-cost;
end
[nop,nop]=size(cost);msum=0;
for i=1:nop
dd(i,:)=dd(i,:)-min(dd(i,:));
end
for j=1:nop
dd(:,j)=dd(:,j)-min(dd(:,j));
end
backup=dd;
for z=1:nop
bh=nop;bl=nop;result=[];
for k=1:nop
for i=1:nop
h=find(dd(i,:)==0);
if length(h)~=0&length(h)<bh
bh=length(h);
ch=i;
end
end
L=find(dd(ch,:)==0);
for j=1:length(L)
l=find(dd(:,L(j))==0);
if length(l)<bl
bl=length(l);
cl=L(j);
end
end
result(1,k)=ch;result(2,k)=cl;
dd(ch,:)=1;dd(:,cl)=1;
bl=nop;bh=nop;
if length(find(dd==0))==0
break
end
end
if length(result(1,:))==nop
break
end
dd=backup;DD=dd;d=zeros(nop);
for i=1:length(result(1,:))
d(result(1,i),result(2,i))=1;
end
D=~(d+dd);
p=[];q=[];k=1;zx=inf;
for i=1:nop
if sum(d(i,:))==0
p(k)=i;
k=k+1;
end
end
for j=1:length(p)
q=find(D(p(j),:)==1);
for e=1:length(q)
pp=find(d(:,q(e))==1);
if pp~=0
p(k)=pp;
k=k+1;
end
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
DD(:,q(u))=inf;
end
end
for l=1:length(p)
if min(DD(p(l),:))<zx
zx=min(DD(p(l),:));
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
dd(:,q(u))=dd(:,q(u))+zx;
end
end
for l=1:length(p)
dd(p(l),:)=dd(p(l),:)-zx;
end
backup=dd;
end
for i=1:length(result(1,:))
msum=msum+cost(result(1,i),result(2,i));
end
匈牙利算法的MatLab实现 收藏
程序文件 fenpei.m
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function [z,ans]=fenpei(marix)
%//////////////////////////////////////////////////
%输入效率矩阵 marix 为方阵;
%若效率矩阵中有 M,则用一充分大的数代替;
%输出z为最优解，ans为 最优分配矩阵；
%//////////////////////////////////////////////////
a=marix;
b=a;
%确定矩阵维数
s=length(a);
%确定矩阵行最小值，进行行减
ml=min(a');
for i=1:s
a(i,:)=a(i,:)-ml(i);
end
%确定矩阵列最小值，进行列减
mr=min(a);
for j=1:s
a(:,j)=a(:,j)-mr(j);
end
% start working
num=0;
while(num~=s) %终止条件是“（0）”的个数与矩阵的维数相同
%index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0
index=ones(s);
index=a&index;
index=~index;
%flag用以标记划线位，flag=0 表示未被划线，
%flag=1 表示有划线过，flag=2 表示为两直线交点
%ans用以记录 a 中“（0）”的位置
%循环后重新初始化flag,ans
flag = zeros(s);
ans = zeros(s);
%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，
%即在flag>0位,index=0
while(sum(sum(index)))
%按行找出“（0）”所在位置，并对“（0）”所在列划线，
%即设置flag,同时修改index,将结果填入ans
for i=1:s
t=0;
l=0;
for j=1:s
if(flag(i,j)==0&&index(i,j)==1)
l=l+1;
t=j;
end
end
if(l==1)
flag(:,t)=flag(:,t)+1;
index(:,t)=0;
ans(i,t)=1;
end
end
%按列找出“（0）”所在位置，并对“（0）”所在行划线，
%即设置flag,同时修改index,将结果填入ans
for j=1:s
t=0;
r=0;
for i=1:s
if(flag(i,j)==0&&index(i,j)==1)
r=r+1;
t=i;
end
end
if(r==1)
flag(t,:)=flag(t,:)+1;
index(t,:)=0;
ans(t,j)=1;
end
end
end %对 while(sum(sum(index)))
%处理过程
%计数器：计算ans中1的个数，用num表示
num=sum(sum(ans));
% 判断是否可以终止，若可以则跳出循环
if(s==num)
break;
end
%否则，进行下一步处理
%确定未被划线的最小元素，用m表示
m=max(max(a));
for i=1:s
for j=1:s
if(flag(i,j)==0)
if(a(i,j)<m)
m=a(i,j);
end
end
end
end
%未被划线，即flag=0处减去m；线交点，即flag=2处加上m
for i=1:s
for j=1:s
if(flag(i,j)==0)
a(i,j)=a(i,j)-m;
end
if(flag(i,j)==2)
a(i,j)=a(i,j)+m;
end
end
end
end %对while(num~=s)
%计算最优（min）值
zm=ans.*b;
z=0;
z=sum(sum(zm));
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
运行实例：
>> a=[37.7 32.9 38.8 37 35.4
43.4 33.1 42.2 34.7 41.8
33.3 28.5 38.9 30.4 33.6
29.2 26.4 29.6 28.5 31.1
0 0 0 0 0];
>> [z,ans]=fenpei(a)
z =
127.8000
ans =
0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0
⑥ 匈牙利算法 matlab程序出现问题 运行时出现 Undefined function or variable 'a'.
调用 Edmonds 时，忘了个 实际参数 a（有值得）或数值了。
也可以 用默认参数值。
function [Matching,Cost] = Edmonds(a)
if nargin==0
a=.......;
end
Matching = zeros(size(a));
.........
⑦ 求kM算法和匈牙利算法的程序代码
我学pascal的。本来我是有程序的。既然你要c的那我只好查给你了。问算法过程的话可以追问匈牙利算法1 #include<stdio.h>
2 #include<string.h>
3 bool g[201][201];
4 int n, m, ans;
5 bool b[201];
6 int link[201];
7 bool init()
8 {
9 int _x, _y;
10 memset(g, 0, sizeof(g));
11 memset(link, 0, sizeof(link));
12 ans = 0;
13 if (scanf("%d%d", &n, &m) == EOF)
14 return false;
15 for (int i = 1; i <= n; i++) {
16 scanf("%d", &_x);
17 for (int j = 0; j < _x; j++) {
18 scanf("%d", &_y);
19 g[i][_y] = true;
20 }
21 }
22 return true;
23 }
24
25 bool find(int a)
26 {
27 for (int i = 1; i <= m; i++) {
28 if (g[a][i] == 1 && !b[i]) {
29 b[i] = true;
30 if (link[i] == 0 || find(link[i])) {
31 link[i] = a;
32 return true;
33 }
34 }
35 }
36 return false;
37 }
38
39 int main()
40 {
41 while (init()) {
42 for (int i = 1; i <= n; i++) {
43 memset(b, 0, sizeof(b));
44 if (find(i))
45 ans++;
46 }
47 printf("%d\n", ans);
48 }
49 }KM算法#include <cstdio>
#include <memory.h>
#include <algorithm> // 使用其中的 min 函数
using namespace std;
const int MAX = 1024;
int n; // X 的大小
int weight [MAX] [MAX]; // X 到 Y 的映射（权重）
int lx [MAX], ly [MAX]; // 标号
bool sx [MAX], sy [MAX]; // 是否被搜索过
int match [MAX]; // Y(i) 与 X(match [i]) 匹配
// 初始化权重
void init (int size);
// 从 X(u) 寻找增广道路，找到则返回 true
bool path (int u);
// 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配
int bestmatch (bool maxsum = true);
void init (int size)
{
// 根据实际情况，添加代码以初始化
n = size;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
scanf ("%d", &weight [i] [j]);
}
bool path (int u)
{
sx [u] = true;
for (int v = 0; v < n; v ++)
if (!sy [v] && lx[u] + ly [v] == weight [u] [v])
{
sy [v] = true;
if (match [v] == -1 || path (match [v]))
{
match [v] = u;
return true;
}
}
return false;
}
int bestmatch (bool maxsum)
{
int i, j;
if (!maxsum)
{
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
weight [i] [j] = -weight [i] [j];
}
// 初始化标号
for (i = 0; i < n; i ++)
{
lx [i] = -0x1FFFFFFF;
ly [i] = 0;
for (j = 0; j < n; j ++)
if (lx [i] < weight [i] [j])
lx [i] = weight [i] [j];
}
memset (match, -1, sizeof (match));
for (int u = 0; u < n; u ++)
while (1)
{
memset (sx, 0, sizeof (sx));
memset (sy, 0, sizeof (sy));
if (path (u))
break;
// 修改标号
int dx = 0x7FFFFFFF;
for (i = 0; i < n; i ++)
if (sx [i])
for (j = 0; j < n; j ++)
if(!sy [j])
dx = min (lx[i] + ly [j] - weight [i] [j], dx);
for (i = 0; i < n; i ++)
{
if (sx [i])
lx [i] -= dx;
if (sy [i])
ly [i] += dx;
}
}
int sum = 0;
for (i = 0; i < n; i ++)
sum += weight [match [i]] [i];
if (!maxsum)
{
sum = -sum;
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
weight [i] [j] = -weight [i] [j]; // 如果需要保持 weight [ ] [ ] 原来的值，这里需要将其还原
}
return sum;
}
int main()
{
int n;
scanf ("%d", &n);
init (n);
int cost = bestmatch (true);
printf ("%d ", cost);
for (int i = 0; i < n; i ++)
{
printf ("Y %d -> X %d ", i, match [i]);
}
return 0;
}
⑧ MATLAB 匈牙利算法运行busy
是不是你的程序掉进死循环了
你检查下
输入的新的数据不符合程序允许,或者超过极限值
寻匈牙利算法:
function [result,msum]=sbppp(cost,m)
if nargin==1
dd=cost;
else
dd=max(max(cost))-cost;
end
[nop,nop]=size(cost);msum=0;
for i=1:nop
dd(i,:)=dd(i,:)-min(dd(i,:));
end
for j=1:nop
dd(:,j)=dd(:,j)-min(dd(:,j));
end
backup=dd;
for z=1:nop
bh=nop;bl=nop;result=[];
for k=1:nop
for i=1:nop
h=find(dd(i,:)==0);
if length(h)~=0&length(h)<bh
bh=length(h);
ch=i;
end
end
L=find(dd(ch,:)==0);
for j=1:length(L)
l=find(dd(:,L(j))==0);
if length(l)<bl
bl=length(l);
cl=L(j);
end
end
result(1,k)=ch;result(2,k)=cl;
dd(ch,:)=1;dd(:,cl)=1;
bl=nop;bh=nop;
if length(find(dd==0))==0
break
end
end
if length(result(1,:))==nop
break
end
dd=backup;DD=dd;d=zeros(nop);
for i=1:length(result(1,:))
d(result(1,i),result(2,i))=1;
end
D=~(d+dd);
p=[];q=[];k=1;zx=inf;
for i=1:nop
if sum(d(i,:))==0
p(k)=i;
k=k+1;
end
end
for j=1:length(p)
q=find(D(p(j),:)==1);
for e=1:length(q)
pp=find(d(:,q(e))==1);
if pp~=0
p(k)=pp;
k=k+1;
end
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
DD(:,q(u))=inf;
end
end
for l=1:length(p)
if min(DD(p(l),:))<zx
zx=min(DD(p(l),:));
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
dd(:,q(u))=dd(:,q(u))+zx;
end
end
for l=1:length(p)
dd(p(l),:)=dd(p(l),:)-zx;
end
backup=dd;
end
for i=1:length(result(1,:))
msum=msum+cost(result(1,i),result(2,i));
end
匈牙利算法的MatLab实现 收藏
程序文件 fenpei.m
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function [z,ans]=fenpei(marix)
%//////////////////////////////////////////////////
%输入效率矩阵 marix 为方阵;
%若效率矩阵中有 M,则用一充分大的数代替;
%输出z为最优解，ans为 最优分配矩阵；
%//////////////////////////////////////////////////
a=marix;
b=a;
%确定矩阵维数
s=length(a);
%确定矩阵行最小值，进行行减
ml=min(a');
for i=1:s
a(i,:)=a(i,:)-ml(i);
end
%确定矩阵列最小值，进行列减
mr=min(a);
for j=1:s
a(:,j)=a(:,j)-mr(j);
end
% start working
num=0;
while(num~=s) %终止条件是“（0）”的个数与矩阵的维数相同
%index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0
index=ones(s);
index=a&index;
index=~index;
%flag用以标记划线位，flag=0 表示未被划线，
%flag=1 表示有划线过，flag=2 表示为两直线交点
%ans用以记录 a 中“（0）”的位置
%循环后重新初始化flag,ans
flag = zeros(s);
ans = zeros(s);
%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，
%即在flag>0位,index=0
while(sum(sum(index)))
%按行找出“（0）”所在位置，并对“（0）”所在列划线，
%即设置flag,同时修改index,将结果填入ans
for i=1:s
t=0;
l=0;
for j=1:s
if(flag(i,j)==0&&index(i,j)==1)
l=l+1;
t=j;
end
end
if(l==1)
flag(:,t)=flag(:,t)+1;
index(:,t)=0;
ans(i,t)=1;
end
end
%按列找出“（0）”所在位置，并对“（0）”所在行划线，
%即设置flag,同时修改index,将结果填入ans
for j=1:s
t=0;
r=0;
for i=1:s
if(flag(i,j)==0&&index(i,j)==1)
r=r+1;
t=i;
end
end
if(r==1)
flag(t,:)=flag(t,:)+1;
index(t,:)=0;
ans(t,j)=1;
end
end
end %对 while(sum(sum(index)))
%处理过程
%计数器：计算ans中1的个数，用num表示
num=sum(sum(ans));
% 判断是否可以终止，若可以则跳出循环
if(s==num)
break;
end
%否则，进行下一步处理
%确定未被划线的最小元素，用m表示
m=max(max(a));
for i=1:s
for j=1:s
if(flag(i,j)==0)
if(a(i,j)<m)
m=a(i,j);
end
end
end
end
%未被划线，即flag=0处减去m；线交点，即flag=2处加上m
for i=1:s
for j=1:s
if(flag(i,j)==0)
a(i,j)=a(i,j)-m;
end
if(flag(i,j)==2)
a(i,j)=a(i,j)+m;
end
end
end
end %对while(num~=s)
%计算最优（min）值
zm=ans.*b;
z=0;
z=sum(sum(zm));
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
运行实例：
>> a=[37.7 32.9 38.8 37 35.4
43.4 33.1 42.2 34.7 41.8
33.3 28.5 38.9 30.4 33.6
29.2 26.4 29.6 28.5 31.1
0 0 0 0 0];
>> [z,ans]=fenpei(a)
z =
127.8000
ans =
0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0
⑨ matlab 向量排序。
排序不等式是：倒序<=乱序<=顺序；所以最好是A和B都排序成顺序才会得到最大值。但如果A保持不动，让B排序使得得到的乘积最大，这其实是一个整数二元线性规划问题。你可以设一个矩阵C，这个矩阵是7x7的，行元素表示对应A中1到7的位置，列元素的含义是对应B元素不排序的值。在7x7矩阵中aij表示：A中从头开始第i个元素与B中从头开始第j个元素相对应，则在此处取值为1，否则取值为零。而7x7矩阵每一行求和为1，每一列求和为1。这样只有求解max（CA）就ok。解决这样的二元整数规划，你可以尝试使用匈牙利算法，或者直接使用Lingo或者Matlab求解。这属于运筹学问题。