最小生成树kruskal算法，最短路dijkstra算法 ，动态规划

% 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数规划(在MATLAB5.3使用) % *bnbgui - 非线性整数规划图形工具(在MATLAB5.3使用) % *mintreek - 最小生成树kruskal算法 % *minroute - 最短路dijkstra算法 % *krusk - 最小生成树kruskal算法mex程序 % *dijkstra - 最短路dijkstra算法mex程序 % *dynprog - 动态规划

%%本程序是用分枝定界法求解整数线性规划问题
%%问题的标准形式：
%%  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