穷举法求解0-1整数规划的matlab程序.txt

0-1整数规划有很广泛的应用背景

0-1整数规划有很广泛的应用背景，比如指派问题，背包问题等等，实际上TSP问题也是一个0-1问题，当然这些问题都是NP问题，对于规模较大的问题用穷举法是没有办法在可接受的时间内求得最优解的，本程序只不过是一个练习，得意之处是用递归法把所有解都排列出来。另：胡运权所著的《运筹学基础及应用（第三版）》第97页的例3，我用本程序求解得到的结果是：最优解是x*=(1,0, 0, 0, 0)，最优值是f(x*)=8，但书求得最优解是x*=(1,0, 1, 0, 0)，最优值是f(x*)=4，是不是书中写错了，请大家验证。以下是源程序，大家可以任意使用无版权问题，另外，如果大家有大规模的0-1规划的问题也希望提供给我，谢谢。变量个数至少是3个

%%% 用隐穷举法求解0-1线性规划
%%% min c'x
%%% s.t. Ax<=b
function [y,fval]=qiongju(c,A,b)
guimo=length(c);
suoyoujie=lingyi(guimo);   % 所有可能解的排列
[m,n]=size(A);
opt_solution=inf;          % 解的上界
for i=1:2^guimo
    yueshu=A*suoyoujie(i,:)';
    for j=1:m
        if yueshu(j)>b(j)   % 不满足某约束条件，则不是解
            break;
        end
    end
    if j==m            % 满足所有约束，则计算该的目标值，并与当前最优解相比较
        val=c'*suoyoujie(i,:)';
        if val<=opt_solution
            opt_solution=val;
            y=suoyoujie(i,:);
        end
    end
end
fval=opt_solution;

 

function y=lingyi(k)
if k==3
    y=[0 0 0;
       0 0 1;
       0 1 0;
       0 1 1;
       1 0 0;
       1 0 1;
       1 1 0;
       1 1 1];
else
    lc=2^(k-1);
    xinlie1=zeros(lc,1);
    xinlie2=ones(lc,1);
    xinlie=[xinlie1;xinlie2];
    pre_lingyi=lingyi(k-1);
    pre_lingyi=[pre_lingyi;pre_lingyi];
    y=[xinlie,pre_lingyi];
end