知识库 > 数学方法 > 优化方法

线性规划    

  •     线性规划是数学规划的一个重要分支,也是最简单、最基础的一类问题,它历史悠久,理论较成熟,方法也校完善。 这里我们的模型把整数规划也包含进来。


        式中,,,均为常数,且
        

        定义: Prog_L (c:array,A:array,B:array,Aeq:array,Beq:array,Lb:array,Ub:array,x0:array, options:array,ozarr:array,intarr:array):array;
        说明:使用单纯形法,和起作用集法,系统默认使用起作用集方法求解线性规划问题,即求解目标都为线性和约束条件都为线性的规划问题
        参数:
        f : 线性目标,一维数字数组,不可缺省
        a : 线性约束,二维数字数组,不可缺省
        b : 线性约束,一维数字数组,不可缺省
        Aeq : 线性约束,二维数字数组,缺省为空
        Beq : 线性约束,一维数字数组,缺省为空
        Lb : 下界 约束,一维数字数组,缺省为空
        Ub : 上界约束,一维数字数组,缺省为空
        x0 : 初始值,一维数组
        options : 选项设置,数据表类型,见表9-1
        Ozarr : 01约束条件,第1个变量为01变量则ozarr := array(0)
        Intarr : 整数约束条件,第2,3两个变量为整数变量则 intarr:=array(1,2) 
        

        线性规划option字段介绍
    字段含义取值
    'algorithm'求解方法'simplex' 单纯形'activeset' 作用集法(整数规划)
    'maxiter'最大迭代次数400
    'tolcon'约束容忍误差1.0e-10
    'tolfun'目标最小误差1.0e-8
    'tolx'变量最小变化1.0e-8

        例:某车间有一批长度为7.4m的同型钢管,砍用它们来做100套钢架,已知每套钢架需用长2.9m、2.1m和1.5m的钢管各一根。问如何下料方可使所用材料最省?
        解:因为所需钢材总长度是固定的,所以要使用料的根数最少,也就是要使裁下来的残料最少、而残料的多少取决于裁取方法,故设为按第j种方法裁取钢管的跟数,则对各种可能的裁取方法所产生的残料:
    所裁长度/m裁料方案所需根数
    12345678
    2.921110000100
    2.100212130100
    1.513012304100
    残料长度/m0.100.30.90.20.81.11.4

         
        
        

        f := array(0.1,0,0.3,0.9,0.2,0.8,1.1,1.4);
        a := array();
        b := array();
        aeq := array((2,1,1,1,0,0,0,0),(0,0,2,1,2,1,3,0),(1,3,0,1,2,3,0,4));
        beq := array(100,100,100);
        lb := array(0,0,0,0,0,0,0,0);
        ub := array();
        x0 := array();
        options := array();
        Ozarr := array();
        Intarr := array(0,1,2,3,4,5,6,7);
        return prog_L(f,a,b,aeq,beq,lb,ub,x0,options,ozarr,Intarr); 
        

        结果:
        array("X":
        (10.00,30.00,50.00,0.00,0.00,0.00,0.00,0.00),"Fval":16.00,"Error_M":1,"Iter":8)
        "Error_M"的各输出值的含义详见表9-2。
    Error_M取值含义
    1函数得到收敛的解
    3目标函数值变化小于设定精度
    4发现局部最优值
    5方向倒数小于精度
    0达到迭代次数
    -1算法终止
    -2没有发现可行解
    -3发散问题
    -4无可行下降方向
    -7不能继续求解,问题可能病态