精华内容
下载资源
问答
  • 线性规划

    2020-06-08 18:14:10
    线性规划1 线性规划1.1 一般线性规划程序实例1.2可转化为线性规划的问题2 运输问题(产销平衡)3 指派问题4 对偶理论与灵敏性分析4.1 对偶问题4.2 灵敏性分析4.3 参数线性规划5 投资的收益和风险模型1 固定风险水平,...

    1 线性规划

    1.1 一般线性规划程序实例

    线性规划的实例
    与高中的知识相似,通过约束条件求得目标函数的最大或最小值
    有所不同的是,现在通过计算机程序来帮助解决计算问题。
    分为两种程序来编写线性规划的问题:matlab和lingo。
    lingo程序更加容易编写,与自然语言类似。
    程序

    max=4*x1+3*x2;
    2*x1+x2<=10;
    x1+x2<=8;
    x2<=7;
    x1>=0;
    x2>=0;
    

    结果
    在这里插入图片描述
    matlab则是通过linprog这个函数来进行计算。
    [x,fval]=linprog(c,A,b,Aeq,Beq,LB,UB,X0,OPTIONS);

    matalb中的线性规划标准型

    example.m
    c=[2;3;-5];
    a=[-2,5,-1;1,3,1];
    b=[-10;12];
    aeq=[1,1,1];
    beq=7;
    x=linprog(-c,a,b,aeq,beq,zeros(3,1))
    value=c'*x
    ------------------------------------------------------------------------------------------
    >> example
    Optimization terminated.
    
    x =
    
        6.4286
        0.5714
        0.0000
    
    
    value =
    
       14.5714
    

    1.2可转化为线性规划的问题

    规划问题为
    min |x1|+|x2|+…+x|xn|;
    s.t. Ax<=b;
    对任意xi,存在ui,vi>=0使得xi=ui-vi,|xi|=ui+vi
    即:ui=(xi+|xi|)/2,vi=(|xi|-xi)/2;
    就可以将上述问题转化为
    min
    规划问题为
    min{max(ei)};
    即转化为
    a=min(ei);
    s.t.
    ei<=a;i=(1~n);

    2 运输问题(产销平衡)

    在这里插入图片描述
    lingo程序

    model:
    !6发点8收点运输问题;
    sets:
      warehouses/wh1..wh6/: capacity;
      vendors/v1..v8/: demand;
      links(warehouses,vendors): cost, volume;
    endsets
    !目标函数;
      min=@sum(links: cost*volume);
    !需求约束;
      @for(vendors(J):
        @sum(warehouses(I): volume(I,J))=demand(J));
    !产量约束;
      @for(warehouses(I):
        @sum(vendors(J): volume(I,J))<=capacity(I));
     
    !这里是数据;
    data:
      capacity=60 55 51 43 41 52;
      demand=35 37 22 32 41 32 43 38;
      cost=6 2 6 7 4 2 9 5
           4 9 5 3 8 5 8 2
           5 2 1 9 7 4 3 3
           7 6 7 3 9 2 7 1
           2 3 9 5 7 2 6 5
           5 5 2 2 8 1 4 3;
    enddata
    end
    
    

    结果

     Global optimal solution found.
      Objective value:                              664.0000
      Infeasibilities:                              0.000000
      Total solver iterations:                            15
    
      Model Class:                                        LP
    
      Total variables:                     48
      Nonlinear variables:                  0
      Integer variables:                    0
    
      Total constraints:                   15
      Nonlinear constraints:                0
    
      Total nonzeros:                     144
      Nonlinear nonzeros:                   0
    
                                    Variable           Value        Reduced Cost
                              CAPACITY( WH1)        60.00000            0.000000
                              CAPACITY( WH2)        55.00000            0.000000
                              CAPACITY( WH3)        51.00000            0.000000
                              CAPACITY( WH4)        43.00000            0.000000
                              CAPACITY( WH5)        41.00000            0.000000
                              CAPACITY( WH6)        52.00000            0.000000
                                 DEMAND( V1)        35.00000            0.000000
                                 DEMAND( V2)        37.00000            0.000000
                                 DEMAND( V3)        22.00000            0.000000
                                 DEMAND( V4)        32.00000            0.000000
                                 DEMAND( V5)        41.00000            0.000000
                                 DEMAND( V6)        32.00000            0.000000
                                 DEMAND( V7)        43.00000            0.000000
                                 DEMAND( V8)        38.00000            0.000000
                              COST( WH1, V1)        6.000000            0.000000
                              COST( WH1, V2)        2.000000            0.000000
                              COST( WH1, V3)        6.000000            0.000000
                              COST( WH1, V4)        7.000000            0.000000
                              COST( WH1, V5)        4.000000            0.000000
                              COST( WH1, V6)        2.000000            0.000000
                              COST( WH1, V7)        9.000000            0.000000
                              COST( WH1, V8)        5.000000            0.000000
                              COST( WH2, V1)        4.000000            0.000000
                              COST( WH2, V2)        9.000000            0.000000
                              COST( WH2, V3)        5.000000            0.000000
                              COST( WH2, V4)        3.000000            0.000000
                              COST( WH2, V5)        8.000000            0.000000
                              COST( WH2, V6)        5.000000            0.000000
                              COST( WH2, V7)        8.000000            0.000000
                              COST( WH2, V8)        2.000000            0.000000
                              COST( WH3, V1)        5.000000            0.000000
                              COST( WH3, V2)        2.000000            0.000000
                              COST( WH3, V3)        1.000000            0.000000
                              COST( WH3, V4)        9.000000            0.000000
                              COST( WH3, V5)        7.000000            0.000000
                              COST( WH3, V6)        4.000000            0.000000
                              COST( WH3, V7)        3.000000            0.000000
                              COST( WH3, V8)        3.000000            0.000000
                              COST( WH4, V1)        7.000000            0.000000
                              COST( WH4, V2)        6.000000            0.000000
                              COST( WH4, V3)        7.000000            0.000000
                              COST( WH4, V4)        3.000000            0.000000
                              COST( WH4, V5)        9.000000            0.000000
                              COST( WH4, V6)        2.000000            0.000000
                              COST( WH4, V7)        7.000000            0.000000
                              COST( WH4, V8)        1.000000            0.000000
                              COST( WH5, V1)        2.000000            0.000000
                              COST( WH5, V2)        3.000000            0.000000
                              COST( WH5, V3)        9.000000            0.000000
                              COST( WH5, V4)        5.000000            0.000000
                              COST( WH5, V5)        7.000000            0.000000
                              COST( WH5, V6)        2.000000            0.000000
                              COST( WH5, V7)        6.000000            0.000000
                              COST( WH5, V8)        5.000000            0.000000
                              COST( WH6, V1)        5.000000            0.000000
                              COST( WH6, V2)        5.000000            0.000000
                              COST( WH6, V3)        2.000000            0.000000
                              COST( WH6, V4)        2.000000            0.000000
                              COST( WH6, V5)        8.000000            0.000000
                              COST( WH6, V6)        1.000000            0.000000
                              COST( WH6, V7)        4.000000            0.000000
                              COST( WH6, V8)        3.000000            0.000000
                            VOLUME( WH1, V1)        0.000000            5.000000
                            VOLUME( WH1, V2)        19.00000            0.000000
                            VOLUME( WH1, V3)        0.000000            5.000000
                            VOLUME( WH1, V4)        0.000000            7.000000
                            VOLUME( WH1, V5)        41.00000            0.000000
                            VOLUME( WH1, V6)        0.000000            2.000000
                            VOLUME( WH1, V7)        0.000000            6.000000
                            VOLUME( WH1, V8)        0.000000            6.000000
                            VOLUME( WH2, V1)        1.000000            0.000000
                            VOLUME( WH2, V2)        0.000000            4.000000
                            VOLUME( WH2, V3)        0.000000            1.000000
                            VOLUME( WH2, V4)        32.00000            0.000000
                            VOLUME( WH2, V5)        0.000000            1.000000
                            VOLUME( WH2, V6)        0.000000            2.000000
                            VOLUME( WH2, V7)        0.000000            2.000000
                            VOLUME( WH2, V8)        0.000000            0.000000
                            VOLUME( WH3, V1)        0.000000            4.000000
                            VOLUME( WH3, V2)        11.00000            0.000000
                            VOLUME( WH3, V3)        0.000000            0.000000
                            VOLUME( WH3, V4)        0.000000            9.000000
                            VOLUME( WH3, V5)        0.000000            3.000000
                            VOLUME( WH3, V6)        0.000000            4.000000
                            VOLUME( WH3, V7)        40.00000            0.000000
                            VOLUME( WH3, V8)        0.000000            4.000000
                            VOLUME( WH4, V1)        0.000000            4.000000
                            VOLUME( WH4, V2)        0.000000            2.000000
                            VOLUME( WH4, V3)        0.000000            4.000000
                            VOLUME( WH4, V4)        0.000000            1.000000
                            VOLUME( WH4, V5)        0.000000            3.000000
                            VOLUME( WH4, V6)        5.000000            0.000000
                            VOLUME( WH4, V7)        0.000000            2.000000
                            VOLUME( WH4, V8)        38.00000            0.000000
                            VOLUME( WH5, V1)        34.00000            0.000000
                            VOLUME( WH5, V2)        7.000000            0.000000
                            VOLUME( WH5, V3)        0.000000            7.000000
                            VOLUME( WH5, V4)        0.000000            4.000000
                            VOLUME( WH5, V5)        0.000000            2.000000
                            VOLUME( WH5, V6)        0.000000            1.000000
                            VOLUME( WH5, V7)        0.000000            2.000000
                            VOLUME( WH5, V8)        0.000000            5.000000
                            VOLUME( WH6, V1)        0.000000            3.000000
                            VOLUME( WH6, V2)        0.000000            2.000000
                            VOLUME( WH6, V3)        22.00000            0.000000
                            VOLUME( WH6, V4)        0.000000            1.000000
                            VOLUME( WH6, V5)        0.000000            3.000000
                            VOLUME( WH6, V6)        27.00000            0.000000
                            VOLUME( WH6, V7)        3.000000            0.000000
                            VOLUME( WH6, V8)        0.000000            3.000000
    
                                         Row    Slack or Surplus      Dual Price
                                           1        664.0000           -1.000000
                                           2        0.000000           -4.000000
                                           3        0.000000           -5.000000
                                           4        0.000000           -4.000000
                                           5        0.000000           -3.000000
                                           6        0.000000           -7.000000
                                           7        0.000000           -3.000000
                                           8        0.000000           -6.000000
                                           9        0.000000           -2.000000
                                          10        0.000000            3.000000
                                          11        22.00000            0.000000
                                          12        0.000000            3.000000
                                          13        0.000000            1.000000
                                          14        0.000000            2.000000
                                          15        0.000000            2.000000
    
    

    3 指派问题

    指派问题是由匈牙利算法解决的。
    先说明一下啥是匈牙利算法把。
    在这里插入图片描述
    不断的对矩阵的行或列做此类运算(即减去该行中最小的元素使得0为一个特征元素,通过找每一行中都有一个0元素且不同且该列0元素最少得出最优指派)
    求解指派问题,其系数矩阵为
    在这里插入图片描述
    lingo代码

    model:
      !4个工人,4个工作的分配问题;
    sets:
      workers/w1..w4/;
      jobs/j1..j4/;
      links(workers,jobs): cost,volume;
    endsets
      !目标函数;
      min=@sum(links: cost*volume);
      !每个工人只能有一份工作;
      @for(workers(I):
        @sum(jobs(J): volume(I,J))=1;
      );
      !每份工作只能有一个工人;
      @for(jobs(J):
        @sum(workers(I): volume(I,J))=1;
      );
    data:
      cost= 16 15 19 22
    	 17 21 19 18
    	 24 22 18 17
    	 17 19 22 16;
    enddata
    end
    
    

    结果

    Global optimal solution found.
      Objective value:                              66.00000
      Infeasibilities:                              0.000000
      Total solver iterations:                             6
    
      Model Class:                                        LP
    
      Total variables:                     16
      Nonlinear variables:                  0
      Integer variables:                    0
    
      Total constraints:                    9
      Nonlinear constraints:                0
    
      Total nonzeros:                      48
      Nonlinear nonzeros:                   0
    
                                    Variable           Value        Reduced Cost
                               COST( W1, J1)        16.00000            0.000000
                               COST( W1, J2)        15.00000            0.000000
                               COST( W1, J3)        19.00000            0.000000
                               COST( W1, J4)        22.00000            0.000000
                               COST( W2, J1)        17.00000            0.000000
                               COST( W2, J2)        21.00000            0.000000
                               COST( W2, J3)        19.00000            0.000000
                               COST( W2, J4)        18.00000            0.000000
                               COST( W3, J1)        24.00000            0.000000
                               COST( W3, J2)        22.00000            0.000000
                               COST( W3, J3)        18.00000            0.000000
                               COST( W3, J4)        17.00000            0.000000
                               COST( W4, J1)        17.00000            0.000000
                               COST( W4, J2)        19.00000            0.000000
                               COST( W4, J3)        22.00000            0.000000
                               COST( W4, J4)        16.00000            0.000000
                             VOLUME( W1, J1)        0.000000            4.000000
                             VOLUME( W1, J2)        1.000000            0.000000
                             VOLUME( W1, J3)        0.000000            6.000000
                             VOLUME( W1, J4)        0.000000            10.00000
                             VOLUME( W2, J1)        1.000000            0.000000
                             VOLUME( W2, J2)        0.000000            1.000000
                             VOLUME( W2, J3)        0.000000            1.000000
                             VOLUME( W2, J4)        0.000000            1.000000
                             VOLUME( W3, J1)        0.000000            7.000000
                             VOLUME( W3, J2)        0.000000            2.000000
                             VOLUME( W3, J3)        1.000000            0.000000
                             VOLUME( W3, J4)        0.000000            0.000000
                             VOLUME( W4, J1)        0.000000            1.000000
                             VOLUME( W4, J2)        0.000000            0.000000
                             VOLUME( W4, J3)        0.000000            5.000000
                             VOLUME( W4, J4)        1.000000            0.000000
    
                                         Row    Slack or Surplus      Dual Price
                                           1        66.00000           -1.000000
                                           2        0.000000           -12.00000
                                           3        0.000000           -17.00000
                                           4        0.000000           -17.00000
                                           5        0.000000           -16.00000
                                           6        0.000000            0.000000
                                           7        0.000000           -3.000000
                                           8        0.000000           -1.000000
                                           9        0.000000            0.000000
    
    

    4 对偶理论与灵敏性分析

    4.1 对偶问题

    原问题
    在这里插入图片描述
    对偶问题
    在这里插入图片描述

    4.2 灵敏性分析

    1 当这些系数有一个或几个发生变化时,已求得的线性规划问题的最优解会有说明变化
    2 这些系数在什么范围内变化时,线性规划的最优解或最优基不变

    4.3 参数线性规划

    不懂

    5 投资的收益和风险

    目标函数
    在这里插入图片描述
    约束条件
    在这里插入图片描述
    从此可以看出这是一个多目标规划的一个问题。
    多目标规划的问题可以将之分为几个模型求解。采用的方法是控制变量法与加权平均法。
    这道题分为以下三种模型。

    模型1 固定风险水平,优化收益

    在这里插入图片描述
    求解
    在这里插入图片描述
    通过控制风险的大小来确定收益的最优化。

    >>  a=0;
    hold on
    while a<0.05
    c=[-0.05,-0.27,-0.19,-0.185,-0.185];
    A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])];
    b=a*ones(4,1);
    Aeq=[1,1.01,1.02,1.045,1.065];
    Beq=1;
    LB=zeros(5,1);
    [x,Q]=linprog(c,A,b,Aeq,Beq,LB);
    Q=-Q;
    plot(a,Q,'*r');
    a=a+0.001;
    end
    

    在这里插入图片描述

    模型2 固定收益水平,极小化风险

    在这里插入图片描述
    求解
    在这里插入图片描述
    其matlab程序还不会编
    先写一下lingo的程序把。

    在这里插入代码片
    

    模型3 加权线性规划

    在这里插入图片描述
    求解
    在这里插入图片描述

    展开全文
  • 线性规划线性规划线性规划线性规划线性规划线性规划
  • 线性规划2 线性规划2 线性规划2 线性规划2
  • 数学建模学习——线性规划线性规划
  • 关于运筹学的PPt,里面有关于线性规划,非线性规划,图论的一些详细介绍
  • 线性规划-源码

    2021-02-21 06:35:01
    线性规划
  • 一、单纯法求解线性规划的原理 一般线性规划问题中当线性方程组的变量数大于方程个数,这时会有不定数量的解,而单纯形法是求解线性规划问题的通用方法。 具体步骤是,从线性方程组找出一个个的单纯形,每一个单纯形...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,796
精华内容 4,718
关键字:

线性规划