QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 10102|回复: 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解法  I, C' E0 T) A
    一、 从规划问题引入
    % A- N3 ]0 g: Z7 ]$ q$ l/ D( L) v: X3 V% Y3 i, e3 P1 y
      在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?3 k8 F" F! |! p. z! _
    ) b- r$ l1 A+ |7 ?
    二、 软件分析与选择7 j- x0 u% _7 L" B4 R3 Y- @3 Q& J

    % d: R$ b( ?' ~. a  Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。) U2 ]' |" ~  e1 d* |  r
    0 K3 ?9 U: R2 ?5 Q) h; m1 u
      首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。
    $ c) M( H* `) g% L1 w2 P7 U  而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答
    2 Y7 p! S1 _) {* Z+ e, N* phttps://www.zhihu.com/question/49319704/answer/165923451: k+ N1 q$ z) R* z+ F! ?

    ) i7 c  w0 q: X, E  用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。
    , j' ]; B% ~; b9 k" H  然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
      y, H1 K! G1 j9 R1 j% M  而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。. S2 {4 N# a& V* h, |2 o5 G
    5 \+ I! r% F8 @. d# v) I/ x
      那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。
    , e8 K& w0 x8 v' y$ P0 ?: }" Y4 ]3 u0 d( }/ R6 Z: k
    三、 如何上手Lingo  d$ f  v( G5 h% e+ \: ~1 |

    / ?4 V. f% b& Q; I$ h  有很多人对于Lingo的评价都是,非常简单的软件,很好上手。 " }0 C& A& x2 R$ N
      “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。' e' i' X+ Y6 R( X8 L( t8 e3 d
    4 d/ |  K7 ~# e& [! o$ b
    四、 Lingo的基本语法规则0 E" G1 `8 i+ s6 c, v9 ^! y
    # v& ], c( U: Z# S
    1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示;
    0 ~' k& _4 z7 V* r1 Y' I2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行; 6 p% z6 l' i, d" q6 A6 v
    3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写;
    ( A  I9 y! [6 m4、可以给语句加上标号; 4 J/ {" o% G! P% K1 F
    5、注释以“!”开头以“;”结束; + s6 [( i" o: \
    6、默认所有的决策变量为非负数; - k3 ?" j7 a7 Q' b% J
    7、Lingo模型以“MODEL”开头以“END”结束。
    ' y" L" T" S& ^8 G% f3 @7 x8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。 ! g3 s$ ]: ~  |5 T$ R! P( z. w/ t
    9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。 2 }! a  G4 X4 o) z
    10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。+ F' K7 T- ?. O' n  F9 f

    & C/ i& K! Z; j! h- Y五、 谈一谈例子8 V) i2 ?6 |1 r) \

    & j% B+ Y; X* X% x& r- X+ Z/ ?  那么Lingo用起来到底有多简单呢,我们来看一个例子。% R3 W  T% J3 b; o8 W; \9 m! j

    $ }1 G# |8 s5 t& @+ g9 y例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:
    - Z: d+ ~% g! |8 V  z+ \
    + b4 Q9 V9 q4 R/ l         每个书桌        每个餐桌        每个椅子        现有资源总数; D9 R. {8 m9 _" p9 U' \3 m0 k$ S
    木料        8个单位        6个单位        1个单位        48个单位1 ]1 D, U. a* x' ^) _/ l
    漆工        4个单位        2个单位        1.5个单位        20个单位
    ! i- [/ f3 l3 U7 j& w木工        2个单位        1.5个单位        0.5个单位        8个单位
    5 g& S1 \; ^5 u+ R* S# Z成品单价        60个单位        30个单位        20个单位         
    2 r* J; G  I1 O( N! S( c  若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?
    $ K' {6 X4 r9 w; y6 C; s
    ! p# P) L4 n' P解:代码, k7 A/ r, \/ V+ V3 E. p

    . L9 E' y5 A3 p6 K+ F  r2 h. i* B! Jmax = 60 * desks + 30 * tables + 20 * chairs;
    ( V: j; r6 Z) \4 U& o$ B* J      8 * desks + 6 * tables + chairs <= 48;9 P) L1 n1 }2 Y
          4 * desks + 2 * tables + 1.5 * chairs <= 20;( B$ J' N1 P( ^7 W& K/ I1 {
          2 * desks + 1.5 * tables + .5 * chairs <= 8;
    6 G# b2 P8 V3 otables <= 5;
    5 I, p! B# z6 w/ I1
      _; `! u) d1 \- g, o24 x- M6 M  {7 m# ?
    3
    9 S" c0 O1 ?/ B$ F4+ e9 H0 v, i+ ~/ o
    5/ B9 I5 t# {& f+ p( J
    可以得到结果: * j2 L; w. _7 P% }# Y' [* w

    8 b. r. u1 l9 ~$ j7 l) b, `  这里的 Total solver iteration 表示一共迭代2次得到最优解。 " w( z& h! Y: U/ r6 o
      Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。 3 Y# [. o9 Q' ]9 z' R5 v
      可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。9 l! ?: u! U+ P* Q% Z0 M4 x! O/ x3 a
    ) o* X9 X0 e- }+ A: y; L
    例2:给定一个直角三角形,求包含该三角形的最小正方形。
    4 m1 }- l8 k' I- j% o* x+ O( f5 A6 e& V( j
    我们可以作出如下正方形:
    4 U: o$ j, _5 A# U* s$ g6 F
    ! `) S6 n: G& L. a8 R: {1 {/ N! m% s3 }
      CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx
    0 a2 G$ b$ |: N" [8 ]; O  @' q5 l  转化为了规划问题那么正方形面积最小的时候即为最优解。 , u4 t; Q) \. ~
      代码:
    $ Y! w- ~0 N' h- i+ P: O$ b( g4 u& A' I3 u0 D6 K% N. l3 a: P0 ^
    model:$ ?& F+ M$ W) w: j( @7 w
    sets:# V2 p/ E. @+ I! s9 |$ a, x
        object/1..3/:f;2 d# n7 Q9 B& O1 m( n
    endsets; J% e1 h  q' p1 _
    data:
    # N; C' z5 d7 v    a, b = 3, 4;& J6 I7 p- r$ b, b- U8 c* n
    enddata; x. Q% T  P9 U6 H
        f(1) = a * @sin(x);
    3 Q- K# w; p; @( C    f(2) = b * @cos(x);6 S- M0 @$ U7 H
        f(3) = a * @cos(x) + b * @sin(x);
    0 y! x/ c0 o6 B  y1 t2 o3 |    min = @smax(f(1), f(2), f(3));
    / t0 N% A/ \- I% g    @bnd(0, x, 1.57);1 I0 \- o8 o% U
    end. x5 s$ O1 e7 c7 T( W2 |. V' p
    1
    ( {) H* s1 I6 R# I9 Q. l2, v+ S5 U5 a0 P( C
    3
    7 Y: N/ i& T  U, c5 f; C4- O" `+ {1 M7 E, k8 q
    5' Y) _5 ^0 I' Q1 L1 s. S
    6; @4 w3 n$ W6 g* X
    7& d8 e4 c* F" H4 P( _) b7 v
    8% b" h, Q7 W: f+ l! Z% O' u
    9
    : e9 L' T9 h, U10: ~" L( z3 C- O& A/ m3 t- Q4 w
    11) y5 K! J" Q& e9 w% M+ g$ K
    12
    + q0 p8 Q7 H7 Q, v13
    , c' T% X. A  ]* m+ o  得到结果: . w- n5 E5 d3 P' ~4 O( G

    & ]. {/ y! t8 B' G' c$ U! k% }5 B) `' Y; k. K2 l) U5 b
      这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。  u4 S* M% m2 v- o3 D4 W  m
      那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?& R) i6 G" G2 z

    2 M9 p8 O& X1 `4 u/ L/ b8 J例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 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为
    . S: Q; d! Z2 e∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    , C, R/ |2 f/ U- a1 b∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj, q9 q5 V. i4 U; r! y# Q% ?
    由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。
    & C* {& H$ P! ?, q) k) \1 {- `: ^; H9 w0 }- \
    代码:2 d# Q( y# G2 F( I5 ^- t
    : q3 m6 c( p7 D. r
    !旅行商问题;
    ; W( L6 Y  ^9 ~& }3 O0 kmodel:
    9 p" _9 x1 D3 m! wsets:
    ' Z" u7 g$ Z* v  c1 g- ^    city / 1.. 5/: u;
    2 C4 E, O1 z) s' d) ~    link(city, city):% B  i% g% X- f, \6 l' D. }
            dist, x; !距离矩阵;! r! N% k" R2 j! i6 i- P' t) `
    endsets
    : P/ b  {) I4 H' J) N' @/ ?! V    n = @size(city);
    ! p- M9 |2 g8 ]. v, I6 C! ddata: !距离矩阵,它并不需要是对称的;0 u) g0 j/ t" z  Y
        dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;9 u! S( V; ?0 D, \7 a4 h" J
    enddata
    0 _8 W3 G3 D( l( ~    min = @sum(link:dist * x);
    $ K( E/ i# l& u+ ~6 p" r3 D    @FOR(city(K):
    : W# i1 v: }. A6 K' l        @sum(city(I)|I #ne# K: x(I, K)) = 1;
      O& v9 I; t) M% }& Z0 A: R- b        !进入城市K;' M4 o8 K' s# O9 H' }
            @sum(city(J)|J #ne# K: x(K, J)) = 1;
    * P; n/ ?  b; @1 I    );3 x6 }4 j9 n% U# ^
        @for(city(I)|I #gt# 1:$ @. e  x" g1 C9 k" J/ l
            @for(city( J)| J#gt#1 #and# I #ne# J:  y' l8 K3 K; C
                 u(I) - u(J) + n * x(I,J) <= n - 1);* K- `* S+ U3 E7 ~
        );
    ) b& E; O5 S" k4 k, P- l- _8 B@for(city(I)|I #gt# 1: u(I) <= n - 2);( T- m7 _) _+ K, O
    @for(link: @bin(x));
    6 o2 A# L2 D1 P5 W- R8 qend
    % j! T" @0 l7 ]1% W, e% ]. c. q) u/ ?& i$ _' b
    2& u2 p, p5 _/ _8 x/ y
    3
    , h6 M% c$ \/ m/ i3 ~5 v: C! V' r' N4! D$ [- \) A* u$ z
    5* U& w, o# j1 {% p5 o3 T/ B. G
    6
      t' w0 [; u& Q5 ?2 K* h3 @; U76 ~( ]5 g; U7 X6 Z  u
    8
    . H9 V' |' m  l. d9
    . t/ n# B* c3 W: L10- p4 B2 U# ~) X
    11
    7 ^/ _: F8 d+ j; }126 t% M' x% M$ p; P& Z4 h- u
    135 f6 d, \, f& x4 q! s; x+ N7 u
    14
    + P4 Y8 t& ?9 ~, Y3 Q158 p& o! Z! o9 k$ ^0 R& ^+ s
    16! q8 Q: p7 K# H$ S) e) Q& |, m
    17. o% Z1 r, R5 d& ^2 g( e
    18" M; {8 k) N; i* x, X8 [) ^
    19- k5 j, l' d/ Q$ N7 y
    207 J* ^8 {6 v# \) O9 S
    21
    6 H0 f; m) w$ d22  m, X3 o# X' u+ I
    23
    . V- c: a1 M; T# [$ l24
    : W: H# n5 [0 l% I, m% l6 n' P* b可以得到结果:
    / r2 l) w: s" e: T% ^" o+ I
    2 _) E0 a8 ~! D3 R9 W8 c---------------------
    + d, w9 [0 e) P- W  V! Q" B) w2 o+ f7 H1 T3 B

    $ u$ ]: _) M2 H! N( p
    * g4 B' m) m+ L  v% S( q% V2 n' A# _# B. \1 m: u: ^5 X" ^

    1 b, }3 l$ `& g$ E* o* r
    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, 2026-6-15 00:05 , Processed in 0.589790 second(s), 51 queries .

    回顶部