请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 8100|回复: 0

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

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

5250

主题

81

听众

16万

积分

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

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

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

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    发表于 2019-4-25 16:16 |显示全部楼层
    |招呼Ta 关注Ta
    2-7、规划问题的Lingo解法% m# v4 A) ^8 a$ N! R+ \, e
    一、 从规划问题引入
    1 N$ Z* u( `7 ?' F( g4 a- M$ D3 m% G/ y: R' ~' T; V' k
      在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?4 s) {/ G2 T+ A1 V: l; i- i

    7 A) y2 |! h* D二、 软件分析与选择
    ; y- M3 M# j- E+ @0 I8 C5 B7 ~& V% `7 {( E% {. H$ [
      Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。. Q% h1 \4 o" a6 r8 a

    : ^# P0 y% H9 h+ y  首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。
    ; q: r( P& |3 _  而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答
    5 \: [, h( ?$ \+ p% u& _https://www.zhihu.com/question/49319704/answer/165923451
    7 C. Z4 B9 P$ }; ]1 G' x9 W+ D3 E& P6 ]0 L% Y7 M& {
      用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。 9 Z( I% I, D  b- {9 P6 D
      然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
    2 G! a; U2 J, L7 L  而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。
    - f1 m9 S1 [6 a% Z8 P; L) x" i% c, D6 V' O- W* O) H
      那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。
    : K0 G- ]8 [/ d/ S* a) M. K9 b9 R7 Q( h( ^, L4 O8 z
    三、 如何上手Lingo8 M* X( C9 w; N+ `: {/ K

    0 [" d$ O9 ^( f2 a- m  有很多人对于Lingo的评价都是,非常简单的软件,很好上手。
    # [0 ?* g2 O8 }; G  “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。6 M8 g2 A! ~( X5 m% Y

    5 [) U% U6 B' Z# o7 N四、 Lingo的基本语法规则
    4 R& q7 W: P: H* W' H& _) Q
    ' ?* M" F! x! l" {1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示; ; Z7 j, l9 P% _( _
    2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行; $ Y5 u+ x8 q9 u# a
    3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写;
    ' O0 ?& ?) e- Q0 z) E" n4、可以给语句加上标号;
    0 q+ B1 s4 v- A7 p7 L; S7 P5、注释以“!”开头以“;”结束; , q% X5 _+ u9 k7 |) J) E# L
    6、默认所有的决策变量为非负数; 8 o: q- F6 I% f( I
    7、Lingo模型以“MODEL”开头以“END”结束。 4 `( z7 {7 u' B' n) G
    8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。
    5 }4 r, d/ L/ j9 x% J( G+ w% z9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。 ! K( c: T8 |/ k( i- r
    10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。
    3 f) o: _6 y; T# F2 E" [+ b
    6 k- @. E, e% k( m1 X+ `) Z' q五、 谈一谈例子
      |! s" \9 m% N6 A6 H) G9 O( [( H6 d+ B/ \
      那么Lingo用起来到底有多简单呢,我们来看一个例子。
    . Y! v/ r1 s; Q! B6 Q! q2 m! H  y# ^
    例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:+ o# b& a6 ~- [2 x6 U" [) }

      ~- m' B5 f$ o9 O( l5 @         每个书桌        每个餐桌        每个椅子        现有资源总数
    * Q" I9 w, }" s  W; U木料        8个单位        6个单位        1个单位        48个单位6 @, t: d. E5 \
    漆工        4个单位        2个单位        1.5个单位        20个单位
    0 p3 L# ?: [/ i' B( W5 P木工        2个单位        1.5个单位        0.5个单位        8个单位2 e, [& r' f+ i& V
    成品单价        60个单位        30个单位        20个单位         
    . r+ V3 S' ^) t0 \$ g& p- T- Y  若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?9 S  I9 a+ ]0 Y# X
    " T! e3 }/ Y4 ^1 A2 o; I
    解:代码
    ) c0 B3 ?( I: s  p" l8 A$ L5 v' O( [
    max = 60 * desks + 30 * tables + 20 * chairs;
    & d0 _0 |3 o/ D6 ~/ L. R$ Q      8 * desks + 6 * tables + chairs <= 48;+ h9 j& l& a2 \3 D0 R
          4 * desks + 2 * tables + 1.5 * chairs <= 20;
    ) F. m: x& Q7 H9 c3 ?$ u$ f      2 * desks + 1.5 * tables + .5 * chairs <= 8;- m! j! b: t- B+ v; [
    tables <= 5;3 D, f: ^9 i" @8 D( r$ n8 P$ k$ e( c
    1
    ) ?9 o5 q0 ?( @& F$ i2 a% D1 q2
    3 Q/ ~9 f3 y+ M9 a) m1 P3. P# w# K5 x& Q3 Z( f
    46 x1 {! N$ n# f8 A
    5
    4 H( Y. i' f" J, Q7 y% M可以得到结果: 7 P5 n* X7 F4 t

    ) h+ s) n- S' k# s# u  这里的 Total solver iteration 表示一共迭代2次得到最优解。 0 I* C$ V9 |/ w
      Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。
    ! ^: Y4 ~0 Z7 F# m* m  可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。
    4 O% ?9 [- D" q4 S- A4 F& ~
    3 s) p! P! `2 R$ x: G( `4 N例2:给定一个直角三角形,求包含该三角形的最小正方形。
    : I$ b( z5 z2 r
    ' R. w+ }3 C; v7 ?+ G. I我们可以作出如下正方形: % a% q: g, z2 [' f
    & O8 b9 {5 N$ j2 S. P

    . }  R$ O4 `& N  CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx
    8 P, L$ r" {: j; L  转化为了规划问题那么正方形面积最小的时候即为最优解。 ! ]8 h+ d1 z3 @' }; @) B/ ~
      代码:3 m+ q& j; A9 c; _
    ; t' n8 B- ^) u
    model:1 C- R3 ?+ ]( m0 ?+ m# i( c& n
    sets:* R: [. d& ]+ X% l
        object/1..3/:f;
    9 G7 h" K$ z$ ^0 P& J' V$ Kendsets
    % [  {; h& e3 O" t4 a4 m1 Gdata:
    4 H; C3 n/ j- B( L2 D    a, b = 3, 4;& |9 V- V, i) S
    enddata
    - P. Z' y0 S7 |; v    f(1) = a * @sin(x);7 O1 j; N/ e0 W2 T- u0 Q+ }6 s4 F1 m' y
        f(2) = b * @cos(x);8 r6 b) V& ?0 V" y2 ?( i
        f(3) = a * @cos(x) + b * @sin(x);
    - N( m2 N3 J) ~' U; d; E    min = @smax(f(1), f(2), f(3));7 R( X. F2 D' c6 _/ r, M6 ]4 ^; C0 U
        @bnd(0, x, 1.57);# L, Q* w# ?5 U
    end3 E1 ?9 q" u* N: n7 P. Q
    1
    ! X, K' j% ~; ~# b2
    - H% Q% p) b& s6 g$ Y  [0 C& z, g36 h! W0 |' I6 a/ i
    4% L) l; B8 r* m# W
    5
    9 ~7 @' H% b9 X; u/ m- P4 w6- X9 `1 H+ j9 A$ c* p: N6 Q6 ?
    7; @6 j, @% F. ^; _
    8
    ( u$ i& Q& H7 D7 ]9
    ; Q, B5 S% ^5 @; k10
    9 m7 r: G, d5 G' y# Z* L  @7 `11- `; g! M% d; W( D* }
    12# a' v" B% p+ E3 H* }
    139 m; C: w2 `5 K3 Z
      得到结果: : e9 Z' T6 B# `$ l7 }. m) |# o) Z
    ( Y- O$ w  ~" S

    ! e! w( S) h0 }4 x% ^3 |  这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。
    2 a( S) `6 d( q9 \% |/ j; v  那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?
    : j! Y# ]/ _! e. `( l* u" A5 \8 L) t0 m0 e/ L' s- `
    例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 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为 * L- L, Z7 L$ c. [9 m2 J
    ∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    8 V9 G, x5 f$ J1 ]∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj9 `; `( E6 L5 \4 w
    由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。- p% A1 z/ p" F0 y
    - d1 Y# k* r7 ?: q7 p7 Z) i7 c. ?
    代码:! r8 f! [# G! J" \7 W

    - n3 n' A& e$ y/ {/ U0 y% r8 @$ K!旅行商问题;
    ) f9 L$ |# S# z$ Xmodel:7 R' V" A% P3 q3 K% m
    sets:$ y& U4 J+ g) L4 f1 o
        city / 1.. 5/: u;% F# L7 h, L8 m4 Y& g* O$ ?! u, _, Q
        link(city, city):* o, G" l9 }% `. b+ ^* }
            dist, x; !距离矩阵;) O1 Q+ b1 C& u. U/ U5 X5 a
    endsets
    ! D$ [9 u2 c' J$ m    n = @size(city);
    ) j2 X- i5 r+ T& T( {data: !距离矩阵,它并不需要是对称的;1 Q# h" F9 w! ^! v5 E. U
        dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;3 @5 M1 D  Z6 Q' n
    enddata
    ; T) e1 k  G! h7 Q( ]) G/ ~  r5 u: C0 p    min = @sum(link:dist * x);! Q" e+ A( D) m4 i* W6 m9 Y
        @FOR(city(K):
    . j8 B1 T9 c. ~$ [) i+ h        @sum(city(I)|I #ne# K: x(I, K)) = 1;
    3 \$ ]3 X; n/ @; @, ?1 Z0 r        !进入城市K;2 ~! E$ r9 p7 K$ ~: h
            @sum(city(J)|J #ne# K: x(K, J)) = 1;
    1 u) q+ z/ u9 P6 O% o    );
    $ ]& C  `9 h) h! ]. h6 s) B) p+ }. g    @for(city(I)|I #gt# 1:
    7 w5 J& D* w# ]7 b4 s- I        @for(city( J)| J#gt#1 #and# I #ne# J:
      l' c" f, X% }; b$ t             u(I) - u(J) + n * x(I,J) <= n - 1);4 b) x+ X# w5 w
        );
    ; n) N$ Y' I8 ?8 ^6 G& j; ?@for(city(I)|I #gt# 1: u(I) <= n - 2);
    8 o9 j: k8 z! }+ ?8 h: ]@for(link: @bin(x));
    . C5 ]% X( k1 E2 y0 _  Kend7 H8 j: Z+ f6 r4 {2 c
    1) s7 J( Z+ A! M( E" z7 @1 S: f
    2
    4 E- o( d0 ?9 ]# p' ^$ I3
    1 I0 i3 L+ T* D/ ]+ `4% w: |) L$ O; @
    5
    2 }8 k: R% c" A4 Y- u6
    9 v" N4 H  d# X- J; _3 k7
    1 h7 S! }7 p& r, t0 k80 B* D3 Y; [4 n9 W/ G9 {( m- |
    9) O0 ?; q! H4 o
    10
    1 W  _/ P3 [; ]2 u- P0 [8 ]. G2 h11
    5 z; C% a9 z3 g; `; |12& J3 A4 [5 d6 u7 g  r- x
    134 W% A. e: q4 A! x8 M  `* b4 N3 C! A
    14. X" R+ M- {9 S& x. e& C
    15
    * J+ f9 c7 h: T16
    5 o$ t# N" L$ k4 F1 E3 r3 F17; T/ X/ j1 g  h5 }3 [6 |1 H8 p
    18
    6 r4 J) V1 b8 T- U! c19. U+ b% \; K' a' i# W
    20. x. G# O6 q& C" l
    21; Z# |5 E2 ]0 z8 b# X
    22
    ; |: f* L3 ~4 `& l! x, J& f, v23
    . W0 j+ Z8 G5 L) Z$ y24
    1 ?+ N; G7 P3 C6 p7 p可以得到结果:
    " h( q) k6 Q" }& A
    ) y% q) U1 z' h---------------------
    + i8 S3 p$ H5 X
    / ~& T( w( ^6 B% `/ L
    0 R8 E% X) l' x1 L) T" z6 h  u: T- t  }0 x* k# O
    8 z: @: ?; d6 E% H! T, e6 a+ _

    3 g$ `( ^/ y+ t$ G, t
    zan
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2024-3-29 10:28 , Processed in 0.370062 second(s), 51 queries .

    回顶部