%%本程序是用分枝定界法求解整數線性規劃問題
%%問題的標準形式：
%%??min?c‘*x
%%?s.t.?A*x<=b
%%??????Aeq*x=beq
%%??x要求是整數
%例?min?Z=x1+4x2
%?s.t.??2x1+x2<=8
%???????x1+2x2>=6
%???????2x1+3x2=9;
%???????x1?x2>=0且為整數
%先將x1+2x2>=6化為?-?x1?-?2x2<=?-6
%c=[1?4];
%A=[2?1;-1?-2];
%b=[8;-6];
%Aeq=[2?3];
%beq=9;
%[yfval]=BranchBound（cAbAeqbeq）



function?[yfval]=BranchBound（cAbAeqbeq）
NL=length（c）;??
UB=inf;
LB=-inf;
FN=[0];
AA（1）={A};
BB（1）={b};
k=0;?
flag=0;
while?flag==0;??????
????[xfvalexitFlag]=linprog（cAbAeqbeq）;
????if?（exitFlag?==?-2）?|?（fval?>=?UB）????
????????FN（1）=[];
????????if?isempty（FN）==1????
????????????flag=1;
????????else
????????????k=FN（1）;
????????????A=AA{k};
????????????b=BB{k};
????????end
????else
????????for?i=1:NL
????????????if?abs（x（i）-round（x（i）））>1e-7????
????????????????kk=FN（end）;
????????????????FN=[FNkk+1kk+2];???
????????????????temp_A=zeros（1NL）;
????????????????temp_A（i）=1;
????????????????temp_A1=[A;temp_A];
????????????????AA（kk+1）={temp_A1};
????????????????b1=[b;fix（x（i））];
????????????????BB（kk+1）={b1};
????????????????temp_A2=[A;-temp_A];
????????????????AA（kk+2）={temp_A2};
????????????????b2=[b;-（fix（x（i））+1）];
????????????????BB（kk+2）={b2};
????????????????FN（1）=[];
????????????????k=FN（1）;
????????????????A=AA{k};
????????????????b=BB{k};
????????????????break;???
????????????end
????????end
????????if?（i==NL）?&?（abs（x（i）-round（x（i）））<=1e-7）???????
????????????UB=fval;
????????????y=x;
????????????FN（1）=[];??
????????????if?isempty（FN）==1
????????????????flag=1;
????????????else
????????????????k=FN（1）;
????????????????A=AA{k};
????????????????b=BB{k};
????????????end
????????end
????end
end
y=round（y）;
fval=c*y;

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2020-04-17?21:00??離散優化\
?????文件???????14681??2003-08-22?08:34??離散優化\BNB18.M
?????文件?????????677??2003-08-22?08:34??離散優化\BNBGUI.M
?????文件????????1789??2008-09-13?17:18??離散優化\BranchBound.m
?????文件????????1573??2003-08-22?08:34??離散優化\DIJKSTRA.M
?????文件????????3151??2003-08-22?08:34??離散優化\DYNPROG.M
?????文件?????????289??2008-09-13?16:45??離散優化\ENUM.M
?????文件????????1633??2003-08-22?08:34??離散優化\KRUSK.C
?????文件???????40960??2003-08-22?08:34??離散優化\KRUSK.DLL
?????文件????????1479??2003-08-22?08:34??離散優化\KRUSKAL.M
?????文件?????????749??2003-08-22?08:34??離散優化\L01p_e.m
?????文件?????????963??2003-08-22?08:34??離散優化\L01p_ie.m
?????文件????????2038??2008-09-13?16:48??離散優化\LPINT.M
?????文件????????2048??2008-09-13?16:57??離散優化\LPINT.asv
?????文件????????1259??2003-08-22?08:34??離散優化\MINROUTE.M
?????文件????????1824??2003-08-22?08:34??離散優化\MINTREEK.M
?????文件?????????664??2008-09-13?16:38??離散優化\MONTE.M
?????文件?????????427??2008-09-13?17:19??離散優化\離散優化.txt