0-1整數(shù)規(guī)劃有很廣泛的應(yīng)用背景，比如指派問(wèn)題，背包問(wèn)題等等，實(shí)際上TSP問(wèn)題也是一個(gè)0-1問(wèn)題，當(dāng)然這些問(wèn)題都是NP問(wèn)題，對(duì)于規(guī)模較大的問(wèn)題用窮舉法是沒(méi)有辦法在可接受的時(shí)間內(nèi)求得最優(yōu)解的，本程序只不過(guò)是一個(gè)練習(xí)，得意之處是用遞歸法把所有解都排列出來(lái)。另：胡運(yùn)權(quán)所著的《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用（第三版）》第97頁(yè)的例3，我用本程序求解得到的結(jié)果是：最優(yōu)解是x*=(1,0, 0, 0, 0)，最優(yōu)值是f(x*)=8，但書(shū)求得最優(yōu)解是x*=(1,0, 1, 0, 0)，最優(yōu)值是f(x*)=4，是不是書(shū)中寫(xiě)錯(cuò)了，請(qǐng)大家驗(yàn)證。以下是源程序，大家可以任意使用無(wú)版權(quán)問(wèn)題，另外，如果大家有大規(guī)模的0-1規(guī)劃的問(wèn)題也希望提供給我，謝謝。變量個(gè)數(shù)至少是3個(gè)

%%% 用隱窮舉法求解0-1線性規(guī)劃
%%% 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            % 滿足所有約束，則計(jì)算該的目標(biāo)值，并與當(dāng)前最優(yōu)解相比較
        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