Matlab随筆之指派問題的整數規劃

原文: Matlab随筆之指派問題的整數規劃

注：除了指派問題外，一般的整數規劃問題無法直接利用Matlab函數，必須Matlab程式設計實作分支定界法和割平面解法。

常用Lingo等專用軟體求解整數規劃問題。

%指派矩陣為 
% 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=[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按列拉直，然後賦給c， 
       %例如矩陣C=[1 ,2,3;4,5,6]，操作完後就是列向量1,4,2,5,3,6 
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])%reshape函數重新調整矩陣的行數、列數、維數 
y
      

運作結果

x =

     0     0     0     0     1 
     0     0     1     0     0 
     0     1     0     0     0 
     0     0     0     1     0 
     1     0     0     0     0


y =

    21