精华内容
下载资源
问答
  • 提出了一种改进的量子粒子群算法,并将该算法用于求解非线性混合整数规划问题。构造了一种自适应调整的惯性权重,平衡了算法的全局搜索和局部搜索能力;针对混合整数规划问题,给定一定比例的初始可行解,提高了初始种群...
  • 文件包含PSO和APSO(自适应粒子群算法)matlab代码,求解混合整数规划的matlab代码
  • 课程讲义,具体的课程可以上b站上搜索“整数规划”.整数规划是指规划中的变量(全部或部分)限制为整数,若在线性模型中,变量限制为整数,则称为整数线性规划。所流行的求解整数规划的方法往往只适用于整数线性规划...
  • 本文是关于运筹学教程第五章——整数规划的一个学习笔记。主要介绍了纯整数规划的割平面法,整数线性规划的分支定界法,0-1规划的隐枚举法和指派问题的匈牙利解法。
  • 该程序通过二进制整数编程解决数独。此代码没有任何循环编写。输入必须为填充方块的行列格式。
  • 整数规划编程

    2018-03-15 12:00:34
    用来求解0-1整数规划,可以很好的求解这类问题,用java的例子
  • 经典运筹学问题,采用MATLAB编程,可以解决0-1整数规划问题
  • 整数规划的C++代码,有实现代码和测试,创建工程后可以直接运行。
  • IntegerProgramming(线性规划、整数规划等内容的使用案例).rar 先看是否需要再下载:https://blog.csdn.net/qq_17623363/article/details/104778300
  • 管理运筹学讲义:整数规划.ppt
  • _整数规划新进展.pdf

    2020-06-15 15:34:01
    研宄, 是运筹学和管理科学中应用最广泛的优化模型之一首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法然后着重讨论整数规划若干新进展,包括二次规划的半定规划( 松弛和随机化方法, ...
  • 本代码用于求解不定二次整数优化matlab算法主要用分枝定界的思想求解,可求解任何不定二次整数规划问题。
  • 提出了一种求解非线性整数规划问题的改进粒子群优化算法.在这个算法里,对粒子群优化模型的速度方程和位置方程进行改进,加入了动态约束处理技术以提高选择最优点的能力;加入了粒子的邻域加速寻优策略以提高局部优化...
  • matlab代码适用于解决线性和非线性整数规划,混合整数非线性规划问题。
  • 里面包含一些规划的理论介绍以及实例分析,其中包括线性规划、整数规划以及非线性规划的理论和程序。
  • 关于线性规划、整数规划、非线性规划、动态规划、图与网络
  • 整数规划

    千次阅读 2019-06-11 21:45:11
    2.1秘籍内容 在上节课的学习过后,相信各位练武之人对于“数学规划”这一武功有个初步的了解,并且学习...那么何为整数规划呢?它和线性规划又有着怎样的区别和联系呢?下面我们来进一步了解一下。 规划中的变量(...

    在这里插入图片描述

    2.1秘籍内容

    在上节课的学习过后,相信各位练武之人对于“数学规划”这一武功有个初步的了解,并且学习了该武功的第一式——线性规划,但对于某些生产进度问题、旅行推销员问题、工厂 选址问题、背包问题及分配问题等线性规划并不能高效的解决并且往往最优解难以满足条件,这时候我们便需要另一个招式——整数规划。那么何为整数规划呢?它和线性规划又有着怎样的区别和联系呢?下面我们来进一步了解一下。
    在这里插入图片描述规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中, 变量限制为整数,则称为整数线性规划。如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:
    (i)变量全部限制为整数时,称纯(完全)整数规划。
    (ii)变量部分限制为整数的,称混合整数规划。

    整数规划这一招式,可谓是衍生于线性规划,但是又有其独特奥妙之处比如:
    (i) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:
    ①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
    ②整数规划无可行解。
    例 1 原线性规划为
    min z= x 1 x_1 x1+ x 2 x_2 x2
    2 x 1 x_1 x1+4 x 2 x_2 x2=5, x 1 ≥ 0 x1 \geq 0 x10 x 2 ≥ 0 x2 \geq 0 x20
    其最优实数解为: x 1 x_1 x1=0, x 2 x_2 x2= 3 2 \frac{3}{2} 23,min z= 3 2 \frac{3}{2} 23.
    若限制整数得: x 1 x_1 x1=0, x 2 x_2 x2=1,min z=2.

    (ii) 整数规划最优解不能按照实数最优解简单取整而获得。也就是说关于整数规划最优解的求法应另有其他方式。
    听完上面的讲述,大家是不是有一些头绪了,整数规划的基础实则为线性规划,合理运用上一招式中的修炼三大法,以及我们即将学习的几种修炼方法,相信整数规划问题定能迎刃而解。
    在这里插入图片描述

    2.2招式解析

    2.2.1 (分枝定界法)

    该方法首先是在上个世纪六十年代初由Land Doig 和 Dakin 等“武林高手”提出的。主要思路为,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。
    听完这些是不是觉得分枝定界法还挺玄妙,但只要我们掌握分枝、定界、剪枝与比较三步修炼大法,下面通过解决一个实际问题,看看这个方法是否行之有效呢。
    例 3 求解下述整数规划
    Max z=40 x 1 x_1 x1+90 x 2 x_2 x2
    在这里插入图片描述
    解: (i)先不考虑整数限制,即解相应的线性规划B,得最优解
    x 1 x_1 x1=4.8092, x 2 x_2 x2=1.8168,z=355.8779
    可见问题B的最优解不符合整数条件。这时 z 是问题 A的优目标函数值 z* 的上界,记作 z ⃗ \vec z z 。而 x 1 x_1 x1=0, x 2 x_2 x2=0,显然是问题 A的一个整数可行解,这时z=0,是z* 的一个下界,记作 z ‾ \underline{z} z 0 ≤ 0 \leq 0 z* ≤ 356 \leq 356 356
    (ii)因为 x 1 x_1 x1 x 2 x_2 x2当前均为非整数,故不满足整数要求,任选一个进行分枝。设选进行分枝,把可行集分成 2 个子集:
    x 1 x_1 x1 ≤ \leq [4.8092]=4, x 2 x_2 x2 ≥ \geq [4.8092]+1=5
    因为 4 与 5 之间无整数,故这两个子集的整数解必与原可行集合整数解一致。这 一步称为分枝。这两个子集的规划及求解如下:
    问题 B 1 B_1 B1:Max z=40 x 1 x_1 x1+90 x 2 x_2 x2
    在这里插入图片描述
    最优解为: x 1 x_1 x1=4.0, x 2 x_2 x2=2.1,z=349.
    问题 B 2 B_2 B2:Max z=40 x 1 x_1 x1+90 x 2 x_2 x2
    在这里插入图片描述
    最优解为: x 1 x_1 x1=5.0, x 2 x_2 x2=1.57,z=341.4.
    再定界:0 ≤ \leq z* ≤ \leq 349.
    (iii)对问题 再进行分枝得问题B11和B12,它们的最优解为:
    B11 x 1 x_1 x1=4.0, x 2 x_2 x2=2.0,z11=340.
    B12 x 1 x_1 x1=1.43, x 2 x_2 x2=3.0,z12=327.14.
    再定界:340 ≤ \leq z* ≤ \leq 341,并将B12剪枝。
    (iv)对问题B2再进行分枝得问题B21和B22,它们的最优解为
    B21 x 1 x_1 x1=5.44, x 2 x_2 x2=1.0,z21=308.
    B22:无可行解。
    将B21,B22剪枝。
    于是可以断定原问题的最优解为:
    x 1 x_1 x1=4.0, x 2 x_2 x2=2.0,z*=340.

    从以上解题过程可得用分枝定界法求解纯整数规划和混合整数规划问题的步骤:
    1.首先忽略整数约束求解,求得原问题的最优解X
    2.如果决策变量x;本是整数要求,但是得到的结果X; =u (不是整数),则将原问题归结为2个区域的线性规划求解,这个两个区域为分别增加约束条件
    x i x_i xi ≤ \leq ceil(u) 和 x i x_i xi ≤ \leq floor(u)
    3.然后分别都这两个规划模型重复上面的步骤,直到满足整数要求为止。
    4.再选出最优解。
    大家现在对于分枝定界法求解整数规划问题应该有了一定的了解,除此之外我们还有几种很实用的招式供大家学习了解。我们一起看看吧。
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190611213740337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h3bmlrYQ==,size_16,color_FFFFFF,t_70#pic_center ==200x150)

    2.2.2 0-1型整数规划

    所谓0-1型整数规划就是变量的取值只能是0或者1,这样的话,其实我们可以将不同的整数规划转化成0-1规划。下面我们来看一个实际问题在这里插入图片描述这里我们就可以直接列出一个是0-1规划的方程,设的变量 x i x_i xi,“1”表示被选中,“0”表示没被选中。0-1型整数规划的特点就是相互排斥的约束条件可以转化成同类型的。比如:
    在这里插入图片描述

    2.2.3其他三种方法

    (1)穷举法,是一种很有效的方法,而且在某些情况下只能穷举。
    (2)过渡隐枚举法
    1.先试探性求一个可行解X(随便带入求值)
    2.然后根据是求极大值还是极小值,如果是求极大值,那么凡是目标值<X的解不必检验是否满足约束条件即可删除,如果是求极小值,那么凡是目标值>X不必检验是否满足约束条件就可满足。
    3.改进新的过滤条件
    4.然后验证目标值,最终求得。
    (3)蒙特卡洛法(随机抽样法)
    就是选择不穷举全部点,而是采用随机的方式来抽取样本估计整体,如果样本足够大,可信度是很大的。
    在这里插入图片描述

    2.3武器栏

    只见蓝光一闪,MATLAB之剑横空出世,正所谓招配剑,方能招招命中。
    解非线性整数规划-----------蒙特卡罗方法
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    Matlab实现整数规划求解(分枝定界法):

    function r=checkint(x)
    %判断x(i)是不是整数了。是的话r(i)返回1,不是的话,返回0
    %输入参数:x   X向量
    %输出参数:r   R向量
    
    for i=1:length(x)
        if(min(abs(x(i)-floor(x(i))),abs(x(i)-ceil(x(i))))<1e-3)
            r(i)=1;
        else
            r(i)=0;
        end
    
    Function val=isrowinmat(arow,mat)
    %用来判断mat中是否包含与arow一样的向量
    %输入变量:arow    向量
    %         mat     矩阵
    %输出变量:val     1表示有,0表示没有
    val=0;
    rows=size(mat,1);
    for i=1:rows
        temp=(mat(i,:)==arow);
        if length(find(temp==0))==0
            val=1;
            return;
        else
            val=0;
        end; 
    end
    

    function [x,fval,exitflag,output,lambda]=linprogdis(ifint,f,A,b,Aeq,beq,lb,ub,x0,options)
    % 用法
    % [x,fval,exitflag,output,lambda]=lpint(ifint.f,A,b,Aeq,beq)
    % [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb)
    % [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub)
    % [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub,x0)
    % [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub,x0,options)

    if nargin<10, options=[];  end
    if nargin<9,  x0=[];       end
    if nargin<8,  ub=inf*ones(size(f));      end
    if nargin<7,  lb=zeros(size(f));      end
    
    [x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub,x0,options);
    
    if exitflag<=0        %表示线性规划没有最优解
        return 
    end
    
    v1=find(ifint==1);  %找到需要整数规划的变量的下标
    
    temp=x(v1);%如果不是要求整数规划的就可以返回了。
    if isempty(temp)
        return
    end
    
    v2=find(checkint(temp)==0);
    if isempty(v2)   %都是整数,得到最众解
        return
    end
    
    k=v1(v2(1));
    
    temp1=zeros(1,length(f));
    temp1(k)=1;
    low=floor(x(k));
    if isrowinmat([temp1,low],[A,b])==1
        thisA=A;
        thisb=b;
    else
        thisA=[A;temp1];
        thisb=b;
        thisb(end+1)=low;
    end
    
    [x1,fval1,exitflag1,output1,lambda1]=linprogdis(ifint,f,thisA,thisb,Aeq,beq,lb,ub,x0,options);
    
    
    temp2=zeros(1,length(f));
    temp2(k)=-1;
    high=-ceil(x(k));
    if isrowinmat([temp2,high],[A,b])==1
        thisA=A;
        thisb=b;
    else
        thisA=[A;temp2];
        thisb=b;
        thisb(end+1)=high;
    end
    
    [x2,fval2,exitflag2,output2,lambda2]=linprogdis(ifint,f,thisA,thisb,Aeq,beq,lb,ub,x0,options);
    
    if (isempty(v2) && ((exitflag1>0 && exitflag2<=0 && fval<=fval)||(exitflag2>0 && exitflag1<=0 && fval<=fval2)||(exitflag1>0 && exitflag2>0 && fval<=fval1 && fval<=fval2)))
        disp('error call');
        return ; %表示都是整数
    end
    
    if exitflag1>0&&exitflag2<=0
         x=x1;
         fval=fval1;
         exitflag=exitflag1;
         output=output1;
         lambda=lambda1;
    elseif exitflag1<=0&&exitflag2>0
         x=x2;
         fval=fval2;
         exitflag=exitflag2;
         output=output2;
         lambda=lambda2;
    elseif exitflag1>0 && exitflag2>0
        if fval1<fval2
            x=x1;
            fval=fval1;
            exitflag=exitflag1;
            output=output1;
            lambda=lambda1;
        else
             x=x2;
             fval=fval2;
             exitflag=exitflag2;
             output=output2;
             lambda=lambda2;
        end
    end
    
    展开全文
  • 通常多煤层联合开采矿井各采面技术和经济条件差异较大,不同的配采方案可以取得不同的经济效益,针对这种情况可以采用整数规划法来优化配采方案。其方法是根据各采面的实际情况建立数学模型,在满足产量和煤质等约束...
  • 解决整数规划中的0-1遗传算法代码 ,对于求0-1规划的朋友有一定帮助!
  • LINGO软件是由美国LINDO系统公司...其特色在于内置建模语言,提供十几个内部函数,可以允许决策变量是整数(即整数规划,包括 0-1 整数规划),方便灵活,而且执行速度非常快。能方便与EXCEL,数据库等其他软件交换数据。
  • 非线性整数规划是一个具有指数复杂度的NP问题,如果约束较为复杂,Matlab优化工具箱和一些优化软件比如lingo等,常常无法应用,即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。...
  • 基于0-1整数规划的作业分配,邹律龙,,根据生产工艺平衡要求,为了使生产作业单元的闲置时间最少,总循环时间最小,本文基于0-1整数规划和多项式模型,对某一生产单元的
  • 基于整数规划的非侵入式电力负荷在线分解,张晓,张建文,基于电器正常工作时的稳态电流波形具有周期性和规律性的特点,提出了一种利用电器稳态电流作为识别特征量的非侵入电力负荷在线分
  • 一、整数规划示例、 二、整数规划解决的核心问题





    一、整数规划示例



    资金总额 B \rm B B , 有 n n n 个投资项目 , 项目 j j j 所需的投资金额 是 a j a_j aj , 预期收益是 c j c_j cj , j = 1 , 2 , ⋯   , n j = 1,2,\cdots,n j=1,2,,n ;

    投资还有以下附加条件 :

    ① 如果投资项目 1 1 1 , 必须投资项目 2 2 2 ; 反之如果投资项目 2 2 2 , 没有限制 ;

    ② 项目 3 3 3 和 项目 4 4 4 必须至少选 1 1 1 个 ;

    ③ 项目 5 , 6 , 7 5,6,7 5,6,7 只能选择 2 2 2 个 ;



    决策变量分析 : 选择合适的 决策变量 决策变量取值 ;

    选取变量 , 使得变量的一组取值 , 能更好对应线性规划问题的解决方案 ;

    每个项目有对应的两个选择 , 投资 / 不投资 , 分别使用 1 1 1 0 0 0 表示 ;

    x j x_j xj 表示第 j j j 个项目的投资选择 , 投资 1 1 1 , 不投资 0 0 0 ; ( j = 1 , 2 , ⋯   , n j = 1,2, \cdots, n j=1,2,,n )


    投资额约束条件 : 所有的投资总额不能超过 B \rm B B , ∑ j = 1 n a j x j ≤ B \sum_{j = 1}^{n} a_{j} x_j \leq B j=1najxjB ;

    分析条件 ① : 投资项目 1 1 1 , 必须投资项目 2 2 2 , 此时 x 1 = x 2 = 1 x_1 = x_2 = 1 x1=x2=1 ; 投资项目 2 2 2 可以投资项目 1 1 1 , 可以不投资项目 1 1 1 , 同时投资的情况上面已经分析过 , 分析后者 x 1 = 1 , x 2 = 0 , 此 时 x 1 > x 2 x_1 = 1, x_2 = 0 , 此时 x_1 > x_2 x1=1,x2=0,x1>x2 ; 综合上述两种情况就有 x 2 ≥ x 1 x_2 \geq x_1 x2x1 ;

    分析条件 ② : 项目 3 3 3 和 项目 4 4 4 必须至少选 1 1 1 个 , 两者选择一个 , 或者都选择 , 二者相加之和是 1 1 1 2 2 2 ; 有约束方程 x 3 + x 4 ≥ 1 x_3 + x_4 \geq 1 x3+x41 ;

    分析条件 ③ : 项目 5 , 6 , 7 5,6,7 5,6,7 只能选择 2 2 2 个 , 则三者相加等于 2 2 2 即可 ; 约束方程 x 5 + x 6 + x 7 = 2 x_5 + x_6 + x_7 = 2 x5+x6+x7=2 ;


    投资问题可以表示为以下线性规划 :

    m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a j x j ≤ B x 2 ≥ x 1 x 3 + x 4 ≥ 1 x 5 + x 6 + x 7 = 2 x j = 0 , 1     (   j = 1 , 2 , ⋯   , n   ) \begin{array}{lcl} \rm maxZ = \sum_{j = 1}^{n} c_j x_j \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} a_{j} x_j \leq B \\\\ \rm x_2 \geq x_1 \\\\ \rm x_3 + x_4 \geq 1 \\\\ \rm x_5 + x_6 + x_7 = 2 \\\\ \rm x_j = 0 , 1 \ \ \ ( \ j = 1, 2, \cdots , n \ ) \end{cases}\end{array} maxZ=j=1ncjxjs.tj=1najxjBx2x1x3+x41x5+x6+x7=2xj=0,1   ( j=1,2,,n )


    根据 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 ) 博客中的整数线性规划概念 , 上述线性规划是 整数线性规划 ;

    上述整数线性规划 的 松弛问题 是一个线性规划 , 可以使用单纯形法对其进行求解 , 求出最优解后 , 可能是小数 , 那么如何得到整数问题的最优解 , 不能进行简单的四舍五入 ;





    二、整数规划解决的核心问题



    给出 整数规划问题 ,

    先求该 整数规划的松弛问题 的解 ,

    松弛问题就是不考虑整数约束 , 将整数线性规划当做普通的线性规划 , 使用单纯形法求出其最优解 ;


    简单的将其松弛问题最优解上下取整 , 得到的四个值 , 可能 不在可行域中 , 选择的整数解 , 必须在可行域中 ;


    根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;

    展开全文
  • matlab利用intlinprog函数和蒙特卡洛算法求解瓷砖整数线性规划和非线性混合规划问题
  • 一、整数规划、 1、整数规划概念、 2、整数规划分类、 二、整数规划示例、 三、整数规划解决的核心问题、 四、整数规划问题解的特征、 五、整数规划问题 与 松弛问题 示例、 六、分支定界法、 1、整数规划概念、 2、...





    一、整数规划





    1、整数规划概念


    线性规划 使用 单纯形法求解 , 线性规划中的 运输规划 使用 表上作业法 求解 ;

    之前讨论的都是线性规划问题 , 非线性规划如何求解 , 没有给出具体的方法 ;


    整数规划问题 : 要求 一部分 或 全部 决策变量 取值整数 的规划问题 , 称为整数规划 ;

    整数规划问题的松弛问题 : 不考虑 整数变量条件 , 剩余的 目标函数约束条件 构成的线性规划问题 称为 整数规划问题的松弛问题 ;

    整数线性规划 : 如果上述 整数规划问题的松弛问题 是线性规划 , 则称该整数规划为 整数线性规划 ;


    整数规划与之前的线性规划多了一个约束条件 , 变量大于等于 0 0 0 , 并且都是整数 ;


    整数线性规划数学模型一般形式 :

    m a x Z = ∑ j = 0 n c j x j s . t { ∑ j = 1 n a i j x j = b i     (   i = 1 , 2 , ⋯   , m   ) x j ≥ 0     (   j = 1 , 2 , ⋯   , n   ) 部 分 或 全 部 为 整 数 \begin{array}{lcl} \rm maxZ = \sum_{j = 0}^{n} c_j x_j \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} a_{ij} x_j = b_i \ \ \ ( \ i = 1, 2, \cdots , m \ ) \\\\ \rm x_j \geq 0 \ \ \ ( \ j = 1, 2, \cdots , n \ ) 部分 或 全部 为整数 \end{cases}\end{array} maxZ=j=0ncjxjs.tj=1naijxj=bi   ( i=1,2,,m )xj0   ( j=1,2,,n )



    2、整数规划分类


    整数线性规划分为以下几类 : ① 纯整数线性规划 , ② 混合整数线性规划 , ③ 0-1 型整数线性规划 ;


    ① 纯整数线性规划 : 全部决策变量都 必须取值整数 的 整数线性规划 ;

    ② 混合整数线性规划 : 决策变量中有一部分 必须 取整数值 , 另一部分 可以不 取值整数值 的 整数线性规划 ;

    ③ 0-1 型整数线性规划 : 决策变量 只能取值 0 0 0 1 1 1 的整数线性规划 ;





    二、整数规划示例



    资金总额 B \rm B B , 有 n n n 个投资项目 , 项目 j j j 所需的投资金额 是 a j a_j aj , 预期收益是 c j c_j cj , j = 1 , 2 , ⋯   , n j = 1,2,\cdots,n j=1,2,,n ;

    投资还有以下附加条件 :

    ① 如果投资项目 1 1 1 , 必须投资项目 2 2 2 ; 反之如果投资项目 2 2 2 , 没有限制 ;

    ② 项目 3 3 3 和 项目 4 4 4 必须至少选 1 1 1 个 ;

    ③ 项目 5 , 6 , 7 5,6,7 5,6,7 只能选择 2 2 2 个 ;



    决策变量分析 : 选择合适的 决策变量 决策变量取值 ;

    选取变量 , 使得变量的一组取值 , 能更好对应线性规划问题的解决方案 ;

    每个项目有对应的两个选择 , 投资 / 不投资 , 分别使用 1 1 1 0 0 0 表示 ;

    x j x_j xj 表示第 j j j 个项目的投资选择 , 投资 1 1 1 , 不投资 0 0 0 ; ( j = 1 , 2 , ⋯   , n j = 1,2, \cdots, n j=1,2,,n )


    投资额约束条件 : 所有的投资总额不能超过 B \rm B B , ∑ j = 1 n a j x j ≤ B \sum_{j = 1}^{n} a_{j} x_j \leq B j=1najxjB ;

    分析条件 ① : 投资项目 1 1 1 , 必须投资项目 2 2 2 , 此时 x 1 = x 2 = 1 x_1 = x_2 = 1 x1=x2=1 ; 投资项目 2 2 2 可以投资项目 1 1 1 , 可以不投资项目 1 1 1 , 同时投资的情况上面已经分析过 , 分析后者 x 1 = 1 , x 2 = 0 , 此 时 x 1 > x 2 x_1 = 1, x_2 = 0 , 此时 x_1 > x_2 x1=1,x2=0,x1>x2 ; 综合上述两种情况就有 x 2 ≥ x 1 x_2 \geq x_1 x2x1 ;

    分析条件 ② : 项目 3 3 3 和 项目 4 4 4 必须至少选 1 1 1 个 , 两者选择一个 , 或者都选择 , 二者相加之和是 1 1 1 2 2 2 ; 有约束方程 x 3 + x 4 ≥ 1 x_3 + x_4 \geq 1 x3+x41 ;

    分析条件 ③ : 项目 5 , 6 , 7 5,6,7 5,6,7 只能选择 2 2 2 个 , 则三者相加等于 2 2 2 即可 ; 约束方程 x 5 + x 6 + x 7 = 2 x_5 + x_6 + x_7 = 2 x5+x6+x7=2 ;


    投资问题可以表示为以下线性规划 :

    m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a j x j ≤ B x 2 ≥ x 1 x 3 + x 4 ≥ 1 x 5 + x 6 + x 7 = 2 x j = 0 , 1     (   j = 1 , 2 , ⋯   , n   ) \begin{array}{lcl} \rm maxZ = \sum_{j = 1}^{n} c_j x_j \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} a_{j} x_j \leq B \\\\ \rm x_2 \geq x_1 \\\\ \rm x_3 + x_4 \geq 1 \\\\ \rm x_5 + x_6 + x_7 = 2 \\\\ \rm x_j = 0 , 1 \ \ \ ( \ j = 1, 2, \cdots , n \ ) \end{cases}\end{array} maxZ=j=1ncjxjs.tj=1najxjBx2x1x3+x41x5+x6+x7=2xj=0,1   ( j=1,2,,n )


    根据 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 ) 博客中的整数线性规划概念 , 上述线性规划是 整数线性规划 ;

    上述整数线性规划 的 松弛问题 是一个线性规划 , 可以使用单纯形法对其进行求解 , 求出最优解后 , 可能是小数 , 那么如何得到整数问题的最优解 , 不能进行简单的四舍五入 ;





    三、整数规划解决的核心问题



    给出 整数规划问题 ,

    先求该 整数规划的松弛问题 的解 ,

    松弛问题就是不考虑整数约束 , 将整数线性规划当做普通的线性规划 , 使用单纯形法求出其最优解 ;


    简单的将其松弛问题最优解上下取整 , 得到的四个值 , 可能 不在可行域中 , 选择的整数解 , 必须在可行域中 ;


    根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;





    四、整数规划问题解的特征



    整数规划问题解的特征 :

    ① 整数规划问题 与 松弛问题 可行解集合关系 : 整数规划问题 可行解集合 , 是该整数规划问题的 松弛问题 可行解集合 的子集 , 任意两个可行解的 凸组合 , 不一定满足整数约束条件 , 不一定是可行解 ;

    ② 整数规划问题 与 松弛问题 最优解关系 : 整数规划问题的可行解 一定是 其 松弛问题的可行解 , 松弛问题的可行解不一定是整数规划问题的可行解 , 整数规划问题的最优解 不会优于 松弛问题的最优解 ;


    松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ;





    五、整数规划问题 与 松弛问题 示例



    假设有如下整数规划问题 :

    m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 0   并 且 为 整 数 \begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \ 并且为整数 \end{cases}\end{array} maxZ=x1+x2s.t14x1+9x2516x1+3x21x1,x20 


    上述整数规划问题对应的松弛问题 : 松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ;

    m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=x1+x2s.t14x1+9x2516x1+3x21x1,x20



    使用图解法 , 解上述 松弛问题 的最优解为 { x 1 = 3 2 x 2 = 10 3 \begin{cases} \rm x_1 = \cfrac{3}{2} \\\\ \rm x_2 = \cfrac{10}{3} \end{cases} x1=23x2=310

    此时目标函数值 m a x Z = x 1 + x 2 = 29 6 \rm maxZ = x_1 + x_2 = \cfrac{29}{6} maxZ=x1+x2=629

    在这里插入图片描述

    简单的将其松弛问题最优解上下取整 , 得到的四个点 , 如上图的四个红色点 , 都不在可行域中 , 选择的整数解 , 必须在可行域中 ;

    根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;


    穷举法 ( 有局限性 ) : 直接看上图中可行域内的整数点 , 然后再逐一代入目标函数 , 得到一个 整数规划问题 的最优解 , 但是这种方法无法推广应用 , 如果点的个数比较多 , 如几万个 , 变量的维数多 , 如 10 10 10 个约束变量 , 这种方法肯定不适用 ;


    整数规划问题的求解方法有 : ① 分支定界法 , ② 割平面法 ;

    推荐使用 分支定界法 ;





    六、分支定界法





    1、整数规划概念


    分支定界法相关概念 :

    分支 : 将一个问题不断细分为 若干子问题 , 之后逐个讨论子问题 ;

    定界 : 分支很多的情况下 , 需要讨论的情况也随之增多 , 这里就需要定界 , 决定在什么时候不在进行分支 ; 满足 ① 得到最优解 , ② 根据现有条件可以排除最优解在该分支中 , 二者其一 , 就可以进行定界 ;

    定界的作用是 剪掉没有讨论意义的分支 , 只讨论有意义的分支 ;



    2、分支定界法求解整数规划步骤


    分支定界法求解整数规划步骤 :

    ( 1 ) 求 整数规划 的 松弛问题 最优解 :

    如果 该 最优解就 是整数 , 那么得到整数规划最优解 ;

    如果 该 最优解 不是整数 , 那么转到下一个步骤 分支 与 定界 ;


    ( 2 ) 分支 与 定界 :

    任选一个 非整数解变量 x i x_i xi , 在 松弛问题 中加上约束 :

    x i ≤ [ x i ] x_i \leq [x_i] xi[xi] x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi[xi]+1

    形成 两个新的 松弛问题 , 就是两个分支 ;

    上述分支 , 分的越细致 , 限制条件越多 , 同时 最优解的质量就越差 ;

    新的分支松弛问题特征 :

    • 原问题求 最大值 时 , 目标值 是 分支问题 的上界 ;

    • 原问题求 最小值 时 , 目标值 是 分支问题 的下界 ;


    分支 1 1 1 的最优解是 x ∗ x^* x , 将最优解代入目标函数后得到最优值 f 1 f_1 f1 ;

    分支 2 2 2 的最优解是 y ∗ y^* y , 将最优解代入目标函数后得到最优值 f 2 f_2 f2 ;

    如果目标函数求最大值 , 那么就讨论 f 1 , f 2 f_1, f_2 f1,f2 谁更大 ;


    检查 分支松弛问题 的 解 及 目标函数值 :

    ① 得到最优整数解 : 如果该分支的 解 是 整数 , 并且 目标函数值 大于等于 其它分支的目标值 , 则剪去其它分支 , 停止计算 ;

    ② 没有得到最优整数解 : 如果该分支的 解 是 小数 , 并且 目标函数值 大于 整数解的目标值 , 需要 继续进行分支 , 直到得到最优解 ;



    3、分支定界理论分析


    假设考虑 分支 1 1 1 松弛问题 , 每次都要给问题找到一个界 , 开始先使用观察法找到一个界 , 找到一个整数解 f f f , 将该解代入目标函数 , 然后在 不断地计算中, 修改该界 ;

    假设 分支 1 1 1 松弛问题 目标函数 求最大值 ,

    如果求解 分支 1 1 1 松弛问题 最优解 恰好也是一个整数解 f 0 f_0 f0 , 如果 f 0 > f f_0 > f f0>f , 此时需要重新定界 , f 0 f_0 f0 作为新的界来讨论 ;

    根据新的界来看 分支 2 2 2 松弛问题是否需要讨论 , 求出 分支 2 2 2 的最优解 对应的 目标函数最优值 f ∗ f^* f ;

    如果 分支 2 2 2 的最优值 小于 分支 1 1 1 的最优值 f ∗ ≤ f 0 f^* \leq f^0 ff0 , 此时分支 2 2 2 不用再进行分支了 , 再进行分支 , 其最优值会越来越差 ;

    定界法的作用是将不符合条件的分支剪去 ;





    七、分支过程示例



    如上篇博客 【运筹学】整数规划 ( 整数规划问题解的特征 | 整数规划问题 与 松弛问题 示例 ) 中 , 求解如下 整数规划 解 :

    m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 0   并 且 为 整 数 \begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \ 并且为整数 \end{cases}\end{array} maxZ=x1+x2s.t14x1+9x2516x1+3x21x1,x20 


    其对应的松弛问题是 : 去掉整数解限制 ;

    m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=x1+x2s.t14x1+9x2516x1+3x21x1,x20


    分支都是基于松弛问题进行的 , 为松弛问题分支 , 组成两个新的松弛问题 ;


    下图是求解结果 ( 图解法 ) :

    在这里插入图片描述
    最优解 x 1 = 3 2 x_1 = \cfrac{3}{2} x1=23 , 分别为 x 1 x_1 x1 添加 x i ≤ [ x i ] x_i \leq [x_i] xi[xi] x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi[xi]+1 约束 , 形成两个新的线性规划 ;


    分支 1 1 1 整数规划 : 添加 x i ≤ [ x i ] x_i \leq [x_i] xi[xi] 约束 , 即 x 1 ≤ 1 x_1 \leq 1 x11 ;

    m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 ≤ 1 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=x1+x2s.t14x1+9x2516x1+3x21x11x1,x20


    分支 2 2 2 整数规划 : 添加 x i ≥ [ x i ] + 1 x_i \geq [x_i] +1 xi[xi]+1 约束 , 即 x 1 ≥ 2 x_1 \geq 2 x12 ;

    m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 ≥ 2 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm 14 x_1 + 9x_2 \leq 51 \\\\ \rm -6 x_1 + 3x_2 \leq 1 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=x1+x2s.t14x1+9x2516x1+3x21x12x1,x20


    这样就将一个线性规划 , 分解成了两个问题分支 , 分别找两个分支问题的所有整数解 ;

    整数规划的整数解 , 肯定在上述两个分支之一中 , 中间将一部分可行域排除在外了 , 就是下图中两个红色箭头之间的可行域部分 , 被排除掉的部分肯定没有整数解 , 都是小数 ;

    在这里插入图片描述





    八、分支定界法求整数规划示例





    1、分支定界法求整数规划示例


    使用 分支定界法 求如下整数规划 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 , x 2 ≥ 0   并 且 为 整 数 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1, x_2 \geq 0 \ 并且为整数 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x1,x20 



    2、求整数规划的松弛问题及最优解


    求上述整数规划 ( I P \rm IP IP ) 的松弛问题 ( L P \rm LP LP ) : 去掉整数限制即可得到一个一般的线性规划 ;

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x1,x20

    可以使用单纯形法求上述线性规划的最优解 , 本次使用图示法 , 求的最优化 ;

    在这里插入图片描述

    使用图示法解得上述 松弛问题 最优解 { x 1 = 18 11 ≈ 1.64 x 2 = 40 11 ≈ 3.64 \begin{cases} \rm x_1 = \cfrac{18}{11} \approx 1.64 \\\\ \rm x_2 = \cfrac{40}{11} \approx 3.64 \end{cases} x1=11181.64x2=11403.64 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 218 11 ≈ − 19.8 \rm min W = -x_1 -5 x_2 = - \cfrac{218}{11} \approx -19.8 minW=x15x2=1121819.8


    如果上述 松弛问题 最优解 是整数 , 则该整数线性规划的最优解就是 松弛问题 的最优解 ;

    上述 松弛问题 L P \rm LP LP 最优解不是整数 , 这里需要进行 分支 操作 , 分成两个 分支松弛问题 L P 1 \rm LP1 LP1 L P 2 \rm LP2 LP2 ;



    3、第一次分支操作


    分支操作 : 任选一个 非整数解变量 x i x_i xi , 在 松弛问题 中加上约束 , x i ≤ [ x i ] x_i \leq [x_i] xi[xi] x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi[xi]+1 , 形成 两个新的 松弛问题 , 就是两个分支 ;


    选择 非整数取值的变量 x 1 = 18 11 ≈ 1.64 x_1 = \cfrac{18}{11} \approx 1.64 x1=11181.64 , 作为分支变量 ,

    x i ≤ [ x i ] x_i \leq [x_i] xi[xi] 对应的 分支新增约束条件是 x 1 ≤ 1 x_1 \leq 1 x11 ;

    x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi[xi]+1 对应的 分支新增约束条件是 x 1 ≥ 2 x_1 \geq 2 x12 ;


    L P 1 \rm LP1 LP1 分支松弛问题中加入 x 1 ≤ 1 x_1 \leq 1 x11 条件后为 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≤ 1 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \leq 1 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x11x1,x20

    求上述 L P 1 \rm LP1 LP1 分支的最优解 { x 1 = 1 x 2 = 3 \begin{cases} \rm x_1 = 1 \\\\ \rm x_2 = 3 \end{cases} x1=1x2=3 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 16 \rm min W = -x_1 -5 x_2 = - 16 minW=x15x2=16

    L P 1 \rm LP1 LP1 分支的界就是 − 16 -16 16 ;



    L P 2 \rm LP2 LP2 分支松弛问题中加入 x 1 ≥ 2 x_1 \geq 2 x12 条件后为 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x12x1,x20

    求上述 L P 2 \rm LP2 LP2 分支的最优解 { x 1 = 2 x 2 = 10 3 \begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = \cfrac{10}{3} \end{cases} x1=2x2=310 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 56 3 ≈ − 18.7 \rm min W = -x_1 -5 x_2 = - \cfrac{56}{3} \approx -18.7 minW=x15x2=35618.7

    L P 2 \rm LP2 LP2 分支的目标值是 − 18.7 -18.7 18.7 ;


    L P 1 \rm LP1 LP1 分支的最优解时整数 , 界 是 − 16 -16 16 ,

    L P 2 \rm LP2 LP2 分支目标值还不是整数 , 因此需要继续分支 ;



    判定某个分支 松弛问题 是否继续向下分支的依据 :

    ① 根据整最优解是否是整数判定 : 首先看 分支 松弛问题 最优解 是否是整数 , 如果是那就停下来 , 如果不是继续向下分支 ;

    ② 根据界的优劣判定 ( 定界思想 ) : 是否继续向下分支 , 还需要看 界 的值 , 通过该 界 的值 , 讨论是否继续向下分支 ;

    • 分支条件 : 如果 本分支的界另外一个分支的界 要好 , 则继续分支下去 ;
    • 不分支条件 : 如果本分支的界比另外一个分支的界差 , 那么本分支就不再向下分支了 ;


    4、第二次分支操作


    L P 2 \rm LP2 LP2 继续向下分支 , x 1 x_1 x1 变量已经是整数变量了 ,

    这里 选择 非整数取值的变量 x 2 = 10 3 ≈ 3.33 x_2 = \cfrac{10}{3} \approx 3.33 x2=3103.33 , 作为分支变量 ,

    x i ≤ [ x i ] x_i \leq [x_i] xi[xi] 对应的 分支新增约束条件是 x 2 ≤ 3 x_2 \leq 3 x23 ;

    x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi[xi]+1 对应的 分支新增约束条件是 x 2 ≥ 4 x_2 \geq 4 x24 ;


    这里得到了 L P 2 \rm LP2 LP2 分支下的两个 分支松弛问题 L P 21 \rm LP21 LP21 L P 22 \rm LP22 LP22 ;

    L P 21 \rm LP21 LP21 分支松弛问题中加入 x 2 ≤ 3 x_2 \leq 3 x23 条件后为 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 2 ≤ 3 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_2 \leq 3 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x12x23x1,x20

    在这里插入图片描述

    求上述 L P 21 \rm LP21 LP21 分支的最优解 { x 1 = 12 5 = 2.4 x 2 = 3 \begin{cases} \rm x_1 = \cfrac{12}{5} = 2.4 \\\\ \rm x_2 = 3 \end{cases} x1=512=2.4x2=3 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 17.4 \rm min W = -x_1 -5 x_2 = - 17.4 minW=x15x2=17.4

    L P 21 \rm LP21 LP21 分支的最优解不是整数 , 而且比 L P 1 \rm LP1 LP1 分支的界 − 16 -16 16 要好 , 可需要继续分支 ;



    L P 22 \rm LP22 LP22 分支松弛问题中加入 x 2 ≥ 4 x_2 \geq 4 x24 条件后为 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 2 ≥ 4 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_2 \geq 4 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x12x24x1,x20

    上述 L P 22 \rm LP22 LP22 分支 没有可行解 , 直接停止 ;



    5、第三次分支操作


    L P 21 \rm LP21 LP21 继续向下分支 ,

    这里 选择 非整数取值的变量 x 1 = 12 5 = 2.4 x_1 = \cfrac{12}{5} = 2.4 x1=512=2.4 , 作为分支变量 ,

    x i ≤ [ x i ] x_i \leq [x_i] xi[xi] 对应的 分支新增约束条件是 x 1 ≤ 2 x_1 \leq 2 x12 ;

    x i ≥ [ x i ] + 1 x_i \geq [x_i] + 1 xi[xi]+1 对应的 分支新增约束条件是 x 1 ≥ 3 x_1 \geq 3 x13 ;

    这里得到了 L P 21 \rm LP21 LP21 分支下的两个 分支松弛问题 L P 211 \rm LP211 LP211 L P 212 \rm LP212 LP212 ;


    L P 211 \rm LP211 LP211 分支松弛问题中加入 x 1 ≤ 2 x_1 \leq 2 x12 条件后为 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 1 ≤ 2 x 2 ≤ 3 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1 \leq 2 \\\\ \rm x_2 \leq 3 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x12x12x23x1,x20

    求上述 L P 211 \rm LP211 LP211 分支的最优解 { x 1 = 2 x 2 = 3 \begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = 3 \end{cases} x1=2x2=3 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 17 \rm min W = -x_1 -5 x_2 = - 17 minW=x15x2=17

    L P 21 \rm LP21 LP21 分支的最优解是整数 , 而且比 L P 1 \rm LP1 LP1 分支的界 − 16 -16 16 要好 , 是当前最好的 界 ;

    因此这里将 界 更新为 − 17 -17 17 ;


    L P 212 \rm LP212 LP212 分支松弛问题中加入 x 1 ≥ 3 x_1 \geq 3 x13 条件后为 :

    m i n W = − x 1 − 5 x 2 s . t { x 1 − x 2 ≥ − 2 5 x 1 + 6 x 2 ≤ 30 x 1 ≤ 4 x 1 ≥ 2 x 1 ≥ 3 x 2 ≤ 3 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm min W = -x_1 -5 x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - x_2 \geq -2 \\\\ \rm 5x_1 + 6x_2 \leq 30 \\\\ \rm x_1 \leq 4 \\\\ \rm x_1 \geq 2 \\\\ \rm x_1 \geq 3 \\\\ \rm x_2 \leq 3 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minW=x15x2s.tx1x225x1+6x230x14x12x13x23x1,x20

    求上述 L P 212 \rm LP212 LP212 分支的最优解 { x 1 = 3 x 2 = 2.5 \begin{cases} \rm x_1 =3 \\\\ \rm x_2 = 2.5 \end{cases} x1=3x2=2.5 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 15.5 \rm min W = -x_1 -5 x_2 = - 15.5 minW=x15x2=15.5

    定界 : L P 212 \rm LP212 LP212 分支的最优解不是整数 , 其目标值 − 15.5 - 15.5 15.5 要比当前的界 − 17 -17 17 要差 , 因此该分支直接裁减掉 ;



    6、整数规划最优解


    该整数规划 I P \rm IP IP 的最优解 { x 1 = 2 x 2 = 3 \begin{cases} \rm x_1 = 2 \\\\ \rm x_2 = 3 \end{cases} x1=2x2=3 , 将上述最优解代入约束方程 ,

    得到整数规划最小值 m i n W = − x 1 − 5 x 2 = − 17 \rm min W = -x_1 -5 x_2 = - 17 minW=x15x2=17


    分支记录如下 :

    在这里插入图片描述

    展开全文
  • 数学建模中整数规划问题的原理分析及MATLAB求解过程

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,468
精华内容 39,787
关键字:

整数规划