学习匈牙利算法解决指派问题

我就是我 2024-03-30 13:34 21阅读 0赞

## 指派问题 ##

![在这里插入图片描述][de256c7b272c475498dfcef27332f868.png]

## 指派问题的标准形式 ##

![在这里插入图片描述][3badda74b941494ebbf0cf375680b7d5.png]

## 指派问题的数学模型 ##

![在这里插入图片描述][289af062c0f54b42992e17448e164ff8.png]

## 非标准形式的指派问题 ##

![在这里插入图片描述][2a5e6ada2135415198c04aaf2e5208c5.png]

## 指派问题的匈牙利解法的一般步骤 ##

![在这里插入图片描述][f7f6bcb02c324c819348603209d91fe3.png]  
![在这里插入图片描述][b9ac9eedf91c4ddcb539743eb944f204.png]  
![在这里插入图片描述][f402f3a98cd1478787193be3297dbcc5.png]  
![在这里插入图片描述][0444b2d10ea04ed082772db6d449d414.png]  
以上步骤并不好理解下面进行一些实例展示方便理解

## 匈牙利解法的实例 ##

![在这里插入图片描述][dc66fcfe45764997b0847e2496d2d4dd.png]  
![在这里插入图片描述][92e2472433cb49e1b9142050cce6c2ca.png]  
![在这里插入图片描述][7fc26d274cfa4b4f9e5e4e3c41ca11a0.png]  
![在这里插入图片描述][9c456f3932a24ed0a22f9f73d82bb0d5.png]  
这是一个比较友好的例子，一切按照步骤来就可以了  
再举一个有点绕的例子  
![在这里插入图片描述][f81f799f16164d9fbd4ce7982a85ba38.png]  
![在这里插入图片描述][ce0c040f4ade4d27a0523381b0839d4b.png]  
![在这里插入图片描述][209caef39e63477d963306e82da92f4d.png]  
![在这里插入图片描述][3315325ef4f34ad296913e719f4ac44e.png]

## 指派问题的计算机解法 ##

整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题有时可以直接利用Matlab的函数linprog。  
利用MATLAB求解下列指派矩阵  
![在这里插入图片描述][b13e757c0e894253842cf273445dd1b5.png]

c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5; 8 4 2 3 5;9 10 6 9 10];
    c=c(:);
     %把矩阵c转化为25维列向量
    a=zeros(10,25);
    %10表示有5行5列的共10个约束（行列xij的和=1）25表示有25种xij类型
    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]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1));
    %zeros(25,1),ones(25,1)指的是取值要么是0要么去1
    X=reshape(x,5,5)
    %把x变成5*5的矩阵
    opt=y

运行结果  
![在这里插入图片描述][646c99a1d2f1480988085f143e0da668.png]  
为了更好的理解代码给出矩阵a的具体元素分布  
![在这里插入图片描述][089fdc39c1364145a9ca6a768bdffa2b.png]

[de256c7b272c475498dfcef27332f868.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e85edc8341484ee0988477b3a84e715c.png
[3badda74b941494ebbf0cf375680b7d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0a70819c20094418bc9d9738a4c94c05.png
[289af062c0f54b42992e17448e164ff8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/24d7934cdbb34df68b3e25812bc3a9a9.png
[2a5e6ada2135415198c04aaf2e5208c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6724e9b243cf4b93803fc4e029eeacb4.png
[f7f6bcb02c324c819348603209d91fe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/feb98a44d1db4d86b0cebd82253af134.png
[b9ac9eedf91c4ddcb539743eb944f204.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9b8c80c8b0024e4f84b43c55787657b8.png
[f402f3a98cd1478787193be3297dbcc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c78433b62c4e436fb8fcf31211efcaa3.png
[0444b2d10ea04ed082772db6d449d414.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/03809bdd83fb4fcf8dd833d1956b91ba.png
[dc66fcfe45764997b0847e2496d2d4dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/87365037b2b64df9b7ec6396896ba12e.png
[92e2472433cb49e1b9142050cce6c2ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/32565646caa344418e3a687a6e8ce593.png
[7fc26d274cfa4b4f9e5e4e3c41ca11a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/17aad62e4af04f96abdeb23008205c08.png
[9c456f3932a24ed0a22f9f73d82bb0d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a6799b09fe68409893f9d8fa0a9b72be.png
[f81f799f16164d9fbd4ce7982a85ba38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/31a7414e49584da299a7e71544b9053e.png
[ce0c040f4ade4d27a0523381b0839d4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/edcfbff541594952b93afeae57f201a2.png
[209caef39e63477d963306e82da92f4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f39066f5302e4a959fa70753088b8f99.png
[3315325ef4f34ad296913e719f4ac44e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7eb6ab8f585445839023c88b3969d6cc.png
[b13e757c0e894253842cf273445dd1b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/501a8ea8282942688ddf6525cfcb4afa.png
[646c99a1d2f1480988085f143e0da668.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d181f94a561d4065801c1e80c8773dec.png
[089fdc39c1364145a9ca6a768bdffa2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6c1f4beac7d843fca216ea623bf67a6f.png