Matlab 0-1线性规划问题

moutqvw

1. function [x,f]=L01p_e(c,A,b,N)
   
2. % [x,f]= L01p_e(c,A,b,N)用枚举法求解下列
   
3. %       0-1线性规划问题
   
4. %       min f=c'*x, s.t. A*x<=b,x的分量全为整数0或1,
   
5. %  其中N表示约束条件 Ax ≤ b中的前N个是等式，N= 0时可以省略。
   
6. %  返回结果x是最优解，f是最优解处的函数值。
   
7. %  
   
8. %例 max f=3x1+5x2+2x3+4x4+2x5+3x6
   
9. %   s.t. 8x1+13x2+6x3+9x4+5x5+7x6<=24, x1,…,x6均为0或1
   
10. %求解
    
11. %  c=-[3,5,2,4,2,3];a=[8,13,6,9,5,7];b=24;
    
12. %  x=l01p_e(c,a,b)
    
13. 
    
14. % By X.D. Ding， June 2000
    
15. 
    
16. if nargin<4,N=0;end
    
17. c=c(:);b=b(:);
    
18. [m,n]=size(A);x=[];f=abs(c')*ones(n,1);i=1;
    
19. while i<=2^n
    
20.    B=de2bi(i-1,n)';
    
21.    t=A*B-b;t11=find(t(1:N,:)~=0);
    
22.    t12=find(t(N+1:m,:)>0);t1=[t11;t12];
    
23.    if isempty(t1)
    
24.       f=min([f,c'*B]);
    
25.       if c'*B==f,x=B;end
    
26.    end
    
27.    i=i+1;
    
28. end
    

复制代码