QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 10100|回复: 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解法
    . n0 \; H* X; t7 Z+ K" F' F一、 从规划问题引入7 U+ [% i' O1 A9 y/ U5 [2 H; P3 _% h

    ) n& y2 f" Q* m9 W) n; G  在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?8 r) q$ [7 ], A3 p

    $ H( G+ H' Q2 @5 w" a二、 软件分析与选择
    / A/ I9 O; n, S5 U
    & H0 L$ d3 t9 h" n8 p  n% P  Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。4 e% _7 f- M+ i8 l0 a

    ; \+ y- ^# H9 h8 ^$ u# @& W  Y  首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。 ) Q3 v+ F) H7 e9 V1 `# I, b
      而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答 : }: l3 o2 Z7 ~3 Y2 h; x% W
    https://www.zhihu.com/question/49319704/answer/165923451
    : ]8 z( N8 B3 ?8 R6 C: M
    " i4 b& H! n. ~  r1 B7 Y$ E3 e1 @  用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。
    $ C1 j% @' {3 y% c+ |$ M; g1 {  然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
    5 x# m+ h2 H( H( f  而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。$ W. {" l- L7 L1 ^+ E2 r0 T6 o& f2 r

    ( L7 j& D5 V# O  v& z  那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。5 L* \5 g; T6 e! H; q* f8 I: N  ^

    7 B+ Q+ A1 e  z; s, v' w: ?. ~三、 如何上手Lingo
    , \9 c! k  O( K+ ^+ d1 H. G
    . W+ ~$ y. `& k7 k- C2 a  有很多人对于Lingo的评价都是,非常简单的软件,很好上手。
    * b+ r% M+ a# k+ H* `: T  “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。# ^: f2 ~. E+ ~8 O0 P

    % x/ o; n0 O; J; i# l, ?0 o四、 Lingo的基本语法规则; G7 V/ _+ V6 V, c4 }! ]
      r, j1 K8 n5 _8 N8 g  x
    1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示;
    * r) [5 V/ d1 A: F/ z2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行; $ q7 D1 b/ Q# N2 D: [$ Z( t: N
    3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写; * S" X& K: F: ~' W; V. \3 z
    4、可以给语句加上标号;
    1 E8 N' a$ [2 a, _) S( y! e5、注释以“!”开头以“;”结束;
    3 z7 w2 A% {+ a% j# |" f; H2 y  v0 F6、默认所有的决策变量为非负数;
    0 U8 H5 _* K* r3 A7、Lingo模型以“MODEL”开头以“END”结束。
    " H/ ^2 H& L8 i. I0 c( `+ A' [+ n* v8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。
    1 @/ M/ j# T% k! d& e9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。
    : h( I/ Y6 a+ A' H( L! v9 U5 i10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。; T/ b% E3 ~( W" l: |
    3 Z, r; w1 S' C0 n/ d9 V- g# C# ]
    五、 谈一谈例子3 E7 K' c, ?3 l# z
    , h* M9 v; \) P2 G
      那么Lingo用起来到底有多简单呢,我们来看一个例子。. H# }' @: Q: @* k! n

    3 G* {7 X1 I5 }% Z/ R# C例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:' r: ^( {8 _0 c. m. b( U) i- w
    $ Z( T& Z: b% |* b( T- l
             每个书桌        每个餐桌        每个椅子        现有资源总数- w" n7 Q0 o% C: [
    木料        8个单位        6个单位        1个单位        48个单位" _- e7 p: |& S" t! g1 \, t/ m" f/ U% ^
    漆工        4个单位        2个单位        1.5个单位        20个单位" {8 |; p" E, Q# V& u: H
    木工        2个单位        1.5个单位        0.5个单位        8个单位. i  w% F: I$ V+ k
    成品单价        60个单位        30个单位        20个单位         + O' m- P4 K- Z: Q/ z
      若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?0 O& G; P9 N) ^5 _/ [6 n
    , Y  y2 q) \! P7 K7 e4 F
    解:代码& m" d+ T1 y7 @, @3 o

    . K. w  O$ y2 o5 g$ s( f0 Imax = 60 * desks + 30 * tables + 20 * chairs;
    * A8 S) H! D7 e  ?; t      8 * desks + 6 * tables + chairs <= 48;
    " {7 d. O( Y1 s, v! W      4 * desks + 2 * tables + 1.5 * chairs <= 20;' W; ^" c- X/ H" q
          2 * desks + 1.5 * tables + .5 * chairs <= 8;0 q- @7 Z+ g( s% v
    tables <= 5;
    6 f; M' L: v3 @: f; m, e4 m; V+ |1
    . d6 m" P& K- k5 C5 l9 p27 l8 p+ C) W* I) z: j0 r% b
    3! ~$ U) [) ]4 f# i: ?: M' s# K
    4
    4 y, O/ q! C3 b$ r& i. m! p5
    7 ?) ^6 S# h! N- J: B可以得到结果: ; a. R2 p( F0 }# W

    # _$ T" ^  r( j4 L  这里的 Total solver iteration 表示一共迭代2次得到最优解。 * _* N& s) {, H' I& N# s
      Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。 : Y, h2 z( x2 n2 H' a; K( `% j: e
      可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。5 X* R0 W. ?  R5 n7 L& p7 n
    4 T8 L' g- ?! ^
    例2:给定一个直角三角形,求包含该三角形的最小正方形。
    6 G. p! I) @4 p- b/ W" `5 ?! \) C- e0 I" V* z  y
    我们可以作出如下正方形: & a7 n+ V0 X2 V( {/ p% E  X, H
      p8 B, }# y1 C, S" u3 C
    # @; H7 S% f+ _' o; V5 R9 Q. r
      CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx
    % Z* N3 R6 L" v8 X6 H4 J  转化为了规划问题那么正方形面积最小的时候即为最优解。
    % f. B7 X+ h8 T2 a! [2 m. p  代码:% N2 X' W7 P# c9 o6 i' z% W8 W# p/ d
    ( U3 \1 K( A: o) @! ^+ _. W! n
    model:
    9 U# e: ^7 A. b7 L4 D: Z# usets:$ ^( _( u0 ]4 p" T. ?& T( J+ E5 ]( J
        object/1..3/:f;! k3 n; d. U# ^* _
    endsets- C2 a( V0 l( _- @
    data:' j, q$ [* n7 y% a
        a, b = 3, 4;
    % H! ~6 Z* D+ l8 P* tenddata# k( X$ Q, U2 i* u9 J
        f(1) = a * @sin(x);. r- J6 W  W9 U  i: M0 N+ C
        f(2) = b * @cos(x);
    ' i0 M( R& c# a    f(3) = a * @cos(x) + b * @sin(x);9 P9 s- h/ ]1 s2 B' b5 Q: \
        min = @smax(f(1), f(2), f(3));, C! U7 S2 L* L+ Z
        @bnd(0, x, 1.57);# \- @) R* X( H, `
    end1 \6 e! ]$ t2 @3 a( ?. r$ Y+ }
    1. C! M+ |! _& o
    2
    9 |# V2 @' h4 z" R6 {* _" N31 r1 `/ S. E/ v7 F3 R
    4# C* J/ L6 [" l( [5 m
    5
    ( l0 W7 x; R0 v6
    3 H; \- p, F0 h3 m$ {79 m/ j$ O# @% [% y! w) I( e4 v
    8( k) h7 q' k* {* @0 z0 [4 ]! K( D
    9
    , w7 I9 B* M9 K, C) p10: G$ Q& V5 ]3 C8 N- ?, K- t" m* [( e
    11
    ( n5 f& I& Q) y7 N12
    7 n+ Y: E1 O$ [4 n1 m2 q: `( D! }13
    ' y+ P3 [( A2 a8 C  得到结果:
    * y8 S0 @7 m3 k1 i
    % p, ^2 b: Y  c( y; n" M3 q* B! r5 {# H! m  b& W- |! i
      这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。0 D6 f1 o' \8 `# I  J3 d+ |" ^0 b+ p
      那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?7 ~: M  Y5 O+ p" }1 M: k# I
    6 l9 {0 ]1 G6 k% p$ V
    例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 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为 " R. e# m3 b  D( E" _/ |
    ∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj9 F2 r8 S2 _1 X% B* N
    ∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj: }/ S. w4 d; S& Y# L, @
    由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。
    , Y' n; A# q  L( ]9 t" l0 d& x. {- l  X$ g) A( e
    代码:" H/ t9 c' T  Y& O3 L& w/ b+ c2 S7 B
    3 ~( z0 [" U9 b( k6 Z4 V8 }$ ^( D
    !旅行商问题;
    3 ?+ s$ i- x) Umodel:7 V! d# L% }, Z, ]7 b( a  I
    sets:! D- m- O  c% z% W9 m9 F7 b4 ]4 A% R
        city / 1.. 5/: u;7 O1 R7 n2 _9 o$ G
        link(city, city):- W7 b& t# \5 Q' w7 g) p
            dist, x; !距离矩阵;7 C( m, @7 L  \  V
    endsets: Y# ?4 c( w1 b( b8 ?" _1 L- H
        n = @size(city);8 l* B, p" v0 b/ M4 i
    data: !距离矩阵,它并不需要是对称的;" k9 q8 ~% e0 N" U. H
        dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;8 o0 s. ?" M1 F: h2 G6 F# O7 `
    enddata) y% }4 e, p5 h. ^2 J0 F
        min = @sum(link:dist * x);$ v3 C4 L$ G" D! l' D2 t6 `
        @FOR(city(K):
    - n% B+ N* w# o% \- L        @sum(city(I)|I #ne# K: x(I, K)) = 1;1 w* Y% |8 y! T' @* e) |/ O
            !进入城市K;) H) x; H* L" n8 n
            @sum(city(J)|J #ne# K: x(K, J)) = 1;* i1 n1 E' p2 ?3 P( `# q# a
        );
    8 H/ s2 Q3 J5 A: t9 E+ ]5 C3 \1 O. n    @for(city(I)|I #gt# 1:1 Q5 `- a0 o  U- [% B
            @for(city( J)| J#gt#1 #and# I #ne# J:
    : Z, P0 g3 u3 K. G+ ]             u(I) - u(J) + n * x(I,J) <= n - 1);
    , H5 b7 H3 _0 M! R  [4 P    );
    " G0 |9 v/ o4 M2 e@for(city(I)|I #gt# 1: u(I) <= n - 2);( V7 x2 i2 C6 X7 X2 S0 x$ x
    @for(link: @bin(x));
    ) q& @& G/ I* X6 Qend, Y0 J3 U5 P, X
    1' c9 K* H5 |" J. }
    2
    - _, y% Y7 ^) w9 Y  o% j) {3! d9 G/ d. Z& i/ L: S8 ^3 p" b
    4
    ' Q" E. X, F4 D5
    " F1 J; X* Z! i0 j" V1 B6 w6
    1 L, R$ q( ^/ F, r& N$ N8 A7/ A6 S! W  z/ [4 h
    8  M$ R, ~; N; }, \
    93 H  q3 ~5 D0 ^
    10; s  t& ^9 d& q0 a0 ?  l
    11) |" x0 Y( P  ~! [" Q' C  u! O2 e( `) D
    129 s# Q/ i& [/ c1 T$ W/ p9 E2 g
    13
    1 A$ n, ~' H" u* n5 G( s14
    4 U/ h2 U) y' y" K, p15
    - v! r) j0 Y! [- G# q' k$ v( C16" m5 @" `$ m5 A- y( j6 b
    17
    " j( }  w3 D" U& E( [18
    5 D5 j9 e  R+ z$ W: [, \3 v19
    - B7 `. D& ~% I: P& p# X6 E/ K( j209 W2 z: @; G; D
    210 z+ G( N3 N3 |/ ^. I
    22( i2 Y, T; s; k
    23
    0 D7 ?. H/ @: c24$ k, G0 z* z0 A, a( S: k! P, F3 x1 |
    可以得到结果: : Z/ x$ q/ J8 v4 K6 L( H1 `% V7 P
    8 f; w7 D+ B; w, e8 s
    ---------------------
    + D8 I+ q5 X. _/ G6 c
    " [0 E# e) [( ]% e9 s6 G' K4 h5 S  r6 R5 y% q

    ( M. \0 Q! `: t8 a
    $ r0 C" O4 M+ [: @# F
    0 C" R- G, q6 X3 A0 G% |0 @+ m, F
    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-14 21:17 , Processed in 0.420514 second(s), 51 queries .

    回顶部