一、前言
??優化模型主要有線性規劃、非線性規劃、動態規劃和整數規劃，而指派問題是整數規劃中一類重要的問題：
有\(n\)項任務，由\(n\)個人來完成，每個人只能做一件，第\(i\)個人完成第\(j\)項任務要\(c_{ij}\)小時，如何合理安排時間才能使總用時最小？
二、 指派問題的數學模型
我們引入 0 - 1變數 \(x_{ij}\)
\[x_{ij} = \begin{cases} 1, & \text{表示指派第i個人完成第j項作業} \\ 0, & \text{表示不指派第i個人完成第j項作業} \end{cases} \]用x_{ij}表示第i個人完成第j項作業所需要的資源數，稱之為價值系數，因此指派問題的數學模型是:
\[min \ z = \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} \]\[s.t = \begin{cases} \sum_{i=1}^n x_{ij}=1,\ \ \ \ \ i=1,2,···,n\\ \sum_{j=1}^n x_{ij}=1,\ \ \ \ \ j=1,2,···,n\\ x_{ij}=0或1,\ \ \ \ \ i,j = 1,2,···,n \end{cases} \]- 第一個式子表示完成全部n項作業所消耗的總資源數要最少；
- 第二個式子表示第i個人只完成一項作業；
- 第三個式子表示第j項作業只能由一個人完成；
- 第四個式子表示決策變數只能取0或者1，
指派問題可以看作0 - 1整數規劃問題來求解，也可以用更簡單的匈牙利演算法來求解，
三、 0 - 1規劃求解(Matlab)
我們先給出這樣一個例題，圖中數值為第i個人要完成第j個任務需要消耗的資源數\(x_{ij}\)，求解:如何安排才能使的總資源消耗最少，
編程思路：
根據規劃問題的要求：
每個人只能完成一個任務，每個任務只能由一個人完成，也正如第三部分中的第二個式子和第三個式子，當該4x4矩陣表示\(x_{ij}\)，即指派第i個人完成第j個任務時，此時每一行相加的值和為1，每一列相加的值和為1，（\(x_{ij}\)的值只能為0或者1）根據該思路，我們可以來進行Matlab變成，
c=[2,15,13,4,10,4,14,15,9,14,16,13,7,8,11,9]';
Aeq=[1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0;
0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0;
0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0;
0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1;
1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0;
0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0;
0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0;
0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1];
beq=[1;1;1;1;1;1;1;1];
lb=zeros(16,1);
ub=ones(16,1);
[x,fval] = linprog(c,[],[],Aeq,beq,lb,ub)
x=reshape(x,[4,4])'
其中Aeq和beq代表的是等式約束，Aeq的前四行分別表示 4x4的\(x_{ij}\)矩陣中四行中每行相加的值為1；Aeq的后四行分別表示4x4的\(x_{ij}\)矩陣找那個的四列中每列相加的值為1，（實際上它就是將4x4的矩陣按照行進行展開成了1x16的矩陣），
然后再呼叫linprog()線性規劃的函式，輸入相應引數進行求解，求解所得的x是16x1的矩陣，我們為了便于觀察，最后將該矩陣轉換成4x4的矩陣，
以上代碼也可以用for回圈對其優化，將線性規劃轉換成整數規劃進行求解
c=[2,15,13,4;10,4,14,15;9,14,16,13;7,8,11,9];
c=c(:);a=zeros(8,16);intcon=1:16;
for i=1:4
a(i,(i-1)*4+1:4*i)=1;
a(4+i,i:4:16)=1;
end
b=ones(8,1);lb=zeros(16,1);ub=ones(16,1);
x=intlinprog(c,intcon,[],[],a,b,lb,ub)
x=reshape(x,[4,4])
在對于指派問題中，還有一個經典演算法時匈牙利演算法，核心是尋找增廣路徑，用增廣路徑求二分圖最大匹配的演算法，后面會有一篇博客專門分享我對匈牙利演算法理解及matlab實戰，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/286362.html
標籤：大數據
上一篇：powerDisigner使用
下一篇：SQL常用命令