php中文网 | cnphp.com

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 476|回复: 0

求解整数线性规划的分支定界法通用程序

[复制链接]

2574

主题

2581

帖子

9108

积分

管理员

Rank: 9Rank: 9Rank: 9

UID
1
威望
0
积分
6412
贡献
0
注册时间
2021-4-14
最后登录
2024-3-29
在线时间
654 小时
QQ
发表于 2022-6-16 17:55:15 | 显示全部楼层 |阅读模式
function [x,min_fval] = Ch1_FZDJ(f,A,b,Aeq,beq,lb,ub)
%% 程序功能说明
%求解整数线性规划的分支定界法通用程序
%====输入参数====
  %f            目标函数系数向量
  %A            不等式约束矩阵
  %b            不等式约束右端向量
  %Aeq          等式约束矩阵
  %beq          等式约束右端向量
  %lb           自变量下界
  %ub           自变量上界
%====输出参数====
  %x            目标函数取最小值时的自变量值
  %min_fval     目标函数的最小值
%程序编写时间:2012年05月;完善时间:2015年12月。
%参考文献:龚纯, 王正林. 精通MATLAB最优化计算[M]. 电子工业出版社, 2009年4月
%参考文献:张建林. MATLAB定量预测与决策——运作案例精编[M]. 北京:电子工业出版社, 2012年7月

%% 程序主体部分
x = NaN;
fm = NaN;
NF_lb = zeros(size(lb));
NF_ub = zeros(size(ub));
NF_lb(:,1) = lb;
NF_ub(:,1) = ub;
F = inf;

while 1
    sz = size(NF_lb);
    k = sz(2);
    opt = optimset('TolX',1e-9);
    %求解线性规划
    [xm,fv,exitflag] = linprog(f,A,b,Aeq,beq,NF_lb(:,1),NF_ub(:,1),[],opt);
    if exitflag == -2   %不存在最优解
        xm = NaN;
        fv = NaN;
    end
    if xm == NaN
        fv = inf;
    end
    if fv ~= inf
        if fv < F
            if max(abs(round(xm) - xm))<1.0e-7   %判断最优解的各个分量是否为整数
                F = fv;
                x = xm;
                tmpNF_lb = NF_lb(:,2:k);         %去掉第一列
                tmpNF_ub = NF_ub(:,2:k);         %去掉第一列
                NF_lb = tmpNF_lb;                %新的下界
                NF_ub = tmpNF_ub;                %新的上界
                if isempty(NF_lb) == 0
                    continue;
                else
                    if x ~= NaN
                        min_fval = F;
                        return;
                    else
                        disp('不存在最优解!');
                        x = NaN;
                        min_fval = NaN;
                        return;
                    end
                end
            else
                lb1 = NF_lb(:,1);
                ub1 = NF_ub(:,1);
                tmpNF_lb = NF_lb(:,2:k);
                tmpNF_ub = NF_ub(:,2:k);
                NF_lb = tmpNF_lb;
                NF_ub = tmpNF_ub;
                [bArr,index] = find(abs((xm - round(xm)))>=1.0e-7);
                p = bArr(1);
                new_lb = lb1;
                new_ub = ub1;
                new_lb(p) = max(floor(xm(p)) + 1,lb1(p));
                new_ub(p) = min(floor(xm(p)),ub1(p));
                NF_lb = [NF_lb new_lb lb1];
                NF_ub = [NF_ub ub1 new_ub];
                continue;
            end
        else
            tmpNF_lb = NF_lb(:,2:k);
            tmpNF_ub = NF_ub(:,2:k);
            NF_lb = tmpNF_lb;
            NF_ub = tmpNF_ub;
            if isempty(NF_lb) == 0
                continue;
            else
                if x ~= NaN
                    min_fval = F;
                    return;
                else
                    disp('不存在最优解!');
                    x = NaN;
                    fm = NaN;
                    return;
                end
            end
        end
    else     
        tmpNF_lb = NF_lb(:,2:k);
        tmpNF_ub = NF_ub(:,2:k);
        NF_lb = tmpNF_lb;
        NF_ub = tmpNF_ub;
        if isempty(NF_lb) == 0
            continue;
        else
            if x ~= NaN
                min_fval = F;
                return;
            else
                disp('不存在最优解!');
                x = NaN;
                min_fval = NaN;
                return;
            end
        end
    end
end





上一篇:基于Python的笑脸识别
下一篇:python 绘制时钟
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|php中文网 | cnphp.com ( 赣ICP备2021002321号-2 )51LA统计

GMT+8, 2024-3-29 22:15 , Processed in 0.180622 second(s), 36 queries , Gzip On.

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2020, Tencent Cloud.

申明:本站所有资源皆搜集自网络,相关版权归版权持有人所有,如有侵权,请电邮(fiorkn@foxmail.com)告之,本站会尽快删除。

快速回复 返回顶部 返回列表