QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 9857|回复: 0
打印 上一主题 下一主题

2-7、规划问题的Lingo解法

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2019-4-25 16:16 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    2-7、规划问题的Lingo解法4 d! I1 t* {3 \& c- D
    一、 从规划问题引入
    , ~2 e* f- L& H! I9 p2 R6 q4 M$ T( l- F9 f/ q# T9 @! {
      在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?: n3 X" `2 L9 j4 o( T5 N# J

    ) D  }- b- Y) T/ @/ h" m二、 软件分析与选择: w( |% F; u+ q' \
    ; @. w! N  t& o
      Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。1 o' H/ P# y+ F/ B
    $ ~+ N' q7 C9 m
      首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。 " n2 g' M% g( g$ [2 \
      而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答
    " U2 O; A2 F. `3 @https://www.zhihu.com/question/49319704/answer/165923451+ M( I/ K( o% o/ D1 C! O, j% X

    # V1 _1 a/ t: E( t  用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。
    + D; a5 x* Q0 F6 V1 _2 y$ p6 w  然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
    5 {9 l* g7 S6 o, P) q  而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。
    8 V- z- D0 n/ Z- v, `# i% U. }  f+ a* z( M4 Z; ~4 P
      那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。0 i4 h: \: ^5 P  a* f. w# ?" c3 \
    : i# ~4 s: Y9 ^( U9 k" ~) x1 _
    三、 如何上手Lingo/ C0 C+ B2 y# v' }

    & m# q. ?5 _: G6 {  有很多人对于Lingo的评价都是,非常简单的软件,很好上手。 ) Z0 F/ R* [. X: h! S0 M: s% x
      “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。
    9 X1 ~0 h7 s- u9 v: Q7 Y/ G* E/ P4 R! z
    四、 Lingo的基本语法规则* i4 n4 p1 l/ M* A7 _) E0 F, o8 E  W
    * i4 Q: n% J+ Z
    1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示; & g/ M7 d+ {6 J
    2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行; 9 z  J' s4 G0 U+ I: T3 _
    3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写; ' ]3 P, c* p9 {. s5 V, C8 `8 H7 b
    4、可以给语句加上标号; + j, G" b4 o6 _* p- @) t
    5、注释以“!”开头以“;”结束;
    8 {; F- v3 b! i8 o* U0 H6、默认所有的决策变量为非负数;
    / Z' }/ Y3 ]2 G  _7、Lingo模型以“MODEL”开头以“END”结束。
      A- u( s! h1 j& M2 o* ~8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。
    # ]* x0 \2 R. F- G& i9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。
    7 E5 C5 S+ E3 h2 m10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。3 y3 s8 f# r& R3 U! n9 y# u
    8 _( v3 A+ P( w
    五、 谈一谈例子; s& Q) o' v- u
    $ O# {2 e- }3 \' A0 H+ Z- ^& y
      那么Lingo用起来到底有多简单呢,我们来看一个例子。
    4 ]( }3 B2 H0 V4 @* o0 y" m. B. x  N' ?: C! L7 W
    例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:3 f6 l6 C; p1 I( i

    4 V) B: B9 S, Z' g( ^+ s+ J( T         每个书桌        每个餐桌        每个椅子        现有资源总数0 G, d9 C6 b. @, W% m
    木料        8个单位        6个单位        1个单位        48个单位) H$ j+ t! [  k, D. A' v
    漆工        4个单位        2个单位        1.5个单位        20个单位
    % m$ L. n& e' Z" E木工        2个单位        1.5个单位        0.5个单位        8个单位: ?8 X: J0 ~+ l# w! o
    成品单价        60个单位        30个单位        20个单位         * c" }! O. B8 q7 ]
      若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?( {( }7 P6 N. y% \

    ! [  T# x- \* f解:代码0 i( M6 I+ u/ x% n+ X5 A. U
    ; k. k0 L. o+ F* }  L4 M
    max = 60 * desks + 30 * tables + 20 * chairs;' a1 [, }7 _3 k6 }# R7 H
          8 * desks + 6 * tables + chairs <= 48;
    & b- H8 [% l# h      4 * desks + 2 * tables + 1.5 * chairs <= 20;" ]2 t; d4 T( a! p/ ?% x
          2 * desks + 1.5 * tables + .5 * chairs <= 8;
    1 n* i8 H3 p7 |% J6 a8 _; ztables <= 5;
    3 o) J$ V- M, n1 ]6 Z) \/ j15 S1 g  D$ f% z- H
    2# N7 s: \; F8 j6 f
    35 ]+ q7 Z( V, O5 R
    4
    1 t4 W" m" d4 p$ Q5
    4 J. q4 C1 C; Y7 h7 M可以得到结果:
    4 L6 {5 M/ y( c$ O( n% r2 X1 S" E# B; z, `# I1 C, Q1 @
      这里的 Total solver iteration 表示一共迭代2次得到最优解。
      I6 e# x  P9 |2 k7 o3 X  Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。 3 _5 S2 r  }7 ^6 M; ?$ r3 n
      可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。
    % V; n/ A; a0 H% Y
    0 w" }) k$ a& Y. t6 u例2:给定一个直角三角形,求包含该三角形的最小正方形。. G' \/ O  a. Q/ ]

    2 Y1 q5 e! r! \我们可以作出如下正方形:
    8 W1 D, H! S- ]. I* M7 s$ o7 p0 w  I! n8 @. b4 ?+ ?  t

    0 M" X9 ^' z6 C( m  CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx
    " o$ m5 Q1 k0 Y7 i  y+ F* v  转化为了规划问题那么正方形面积最小的时候即为最优解。
    , J0 H" G- ]+ U, u9 y$ J6 T  代码:# d1 H7 u+ A$ \
    & O4 q8 T9 P3 }3 a7 u
    model:4 W7 J2 m* u2 d/ V% \/ b
    sets:+ `1 C; I: c- Z$ v
        object/1..3/:f;
    9 B0 [" Z' B* m2 u* K1 q$ Rendsets9 j- @/ {3 E8 `' e5 p$ d* [
    data:7 z4 B3 L# W( [
        a, b = 3, 4;) f# d, S6 e: T- u- H1 R
    enddata
    ) F$ i8 }9 p! D4 P    f(1) = a * @sin(x);0 y6 j5 C' X- Z& B7 ^
        f(2) = b * @cos(x);8 J5 F# W0 Z' G
        f(3) = a * @cos(x) + b * @sin(x);
    . y4 i8 @  E& F2 y- X$ i. Z    min = @smax(f(1), f(2), f(3));( E. ~! c! x" A2 R' f" m
        @bnd(0, x, 1.57);
    % s2 J! Z* A% F- @9 ^end
    6 O8 j$ v6 Q, U1
    : A* Y; z3 Y) p9 }2
    ; F3 O: x  m5 e! x  }7 D3
    5 X$ g/ E. b  S6 ~( u: Z. g4* M4 H1 A, G. M$ X! m4 C' ~; H
    5
    ! L! s* ?' \1 E66 Z' t( m& F. \* B) M4 i4 a
    74 x* W4 C+ O& n. F1 U- Q
    8
    + t! X6 w. l% |% ]( {; ]9
    0 C6 G& N4 R) ]6 l109 v3 q- j. ?5 O6 M2 A
    11
    6 x8 m% N2 M3 t* G8 n' O+ q* q12
    . F! @, H4 X+ T( K# j, ]1 I13
    0 f/ Y& d  G: B1 D3 ~  得到结果: ) s% Y# D7 M) f& m1 T. K
    & v7 r* k4 c- x2 x# A

    3 K+ A  w7 ^/ U! g' l! H3 U2 ]  这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。
    0 S; J7 F& _: \( [$ o, j! L" L/ h  那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?( u  u7 b0 X4 V/ {+ D5 U7 i

    - L9 a+ @" \1 ^8 y$ c例3: 现需在一台机器上加工 nn 个零件(如烧瓷器),这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求,加工零件 jj 时机器必须处于相应状态 sjsj(如炉温)。设起始未加工任何零件时机器处于状态 s0s0 ,且当所有零件加工完成后需恢复到 s0s0 状态。已知从状态 sisi 调整到状态 sj(j≠i)sj(j≠i) 需要时间 cijcij 零件 jj 本身加工时间为 pjpj。为方便起见,引入一个虚零件 00,其加工时间为 00,要求状态为 s0s0,则 0,1,2,…,n0,1,2,…,n 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为
    7 s0 O0 o" j( w" y∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    + t$ T9 o' m- l3 u! W* y∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    2 `2 j3 b+ o5 x0 p2 Q5 q) U' ^由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。% I) @: v( R2 v
    : z) R$ x: T5 y) {  ?/ G% J0 E( y
    代码:/ r" `2 L. G5 }/ C7 \

    / }  K  V9 u+ C! u1 y1 f8 }) M1 j!旅行商问题;
    2 n  U3 V2 i9 r# F6 `% cmodel:
      o  D. |+ _  k9 f2 q6 rsets:6 h( E2 F- o9 ?; Q$ Q8 ~1 E3 T3 d
        city / 1.. 5/: u;2 _: v- m7 v$ U# T
        link(city, city):
    / u; h7 c5 h* ~        dist, x; !距离矩阵;1 i% v- |$ }; L7 \
    endsets( |' I4 V6 x3 @
        n = @size(city);7 I1 {  \: `; Z: c
    data: !距离矩阵,它并不需要是对称的;
    6 G& |" f$ F" T, e6 q    dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;
    8 i6 L6 {$ l3 ?" d7 S' I; F( M2 k# uenddata
    # }9 S7 \: ^- n- h( [9 g    min = @sum(link:dist * x);2 j! ^& W+ W( s1 |4 N( ^
        @FOR(city(K):& t3 ]: p. }3 @+ v" n
            @sum(city(I)|I #ne# K: x(I, K)) = 1;4 Q; x% w0 x+ _7 H  W1 F) G
            !进入城市K;
    ; R5 U" c4 D- [; x$ r. I# r        @sum(city(J)|J #ne# K: x(K, J)) = 1;/ V' u4 ?0 O' H( [5 g; y
        );
    - y0 F& f( K3 R    @for(city(I)|I #gt# 1:8 n( n! N, U) `& i9 _0 ~1 T: B0 ~- l
            @for(city( J)| J#gt#1 #and# I #ne# J:, @( K: b' Z3 e
                 u(I) - u(J) + n * x(I,J) <= n - 1);
    : F& [& `& {6 I- U    );1 D& ?; U( ?4 s! q0 q( L; \, ]
    @for(city(I)|I #gt# 1: u(I) <= n - 2);+ b. k1 V8 t! }! v& ?3 Q; q/ E
    @for(link: @bin(x));8 K$ i) s& j/ N8 U7 F! i+ ~
    end: L4 n5 B4 e4 ?) a: P
    1
    ( A6 n! G* [/ _$ N) F2 W2
    ) X5 W& D1 s* k7 L0 w3
    8 r* i9 K1 w) `' U. [& r* f4 d4
    . A; b2 o$ L" B, i" H6 L" C& K52 i3 b# x  c) v! \5 h7 E5 k
    6
    % q5 n7 U& C% Q% J5 ]74 f" [7 c7 K5 m2 q
    8
    ; G9 d$ |, e8 M# }. U0 e91 p$ k0 \& q4 l/ m) @! t3 H5 j
    10
    ; {6 _9 M3 |) T% s% l# L& }118 W) O% [" H# V, V
    12
    ( T0 V! U* d. ^& s6 ~# h' t6 ~13
    ! K6 L9 [" W" Z14! {3 i' k/ ~& F7 q) s3 F- o
    15
    5 o' ?! v8 h# ^16  x! M2 S% C6 N! f
    17
    9 S9 I6 ^3 n$ o8 Y* J7 s18
    1 ~- s6 ]% |! N# ?' i9 k. ^: `6 A19
    5 {& H; C& n- \* Q) f2 l20
    1 k" Z6 @/ M1 q* ?0 S5 g217 X# B7 \3 \( j# y6 Y- }
    22
    . x9 i4 z* `" i23' M+ D5 J. V2 _
    24' U/ P9 [+ }! H# R
    可以得到结果:
    7 E$ C  j, P, r# K- Z
    9 `& x7 @' C' h---------------------
    % j9 [) K$ d: \9 z: d9 }
    ! P. A0 h9 p9 j2 L' k9 X" S+ R# Q. B5 i" W; B
    ' v" c  e3 y7 @9 J- g. O2 X7 A  h

    - _& |% s6 Q! H0 y( W9 L/ d8 v, Q+ d8 S% p! i8 [5 ]9 g* P5 l: T
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-11-10 09:02 , Processed in 0.303221 second(s), 50 queries .

    回顶部