QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 9653|回复: 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解法
    7 u3 Z% C3 Z$ w9 L! W一、 从规划问题引入
    ' p0 x( }' c/ p4 d
    9 }- _  _; x) X& q% ], w  在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?
    0 O9 p: l8 F6 _, A
    . {6 v. r" D+ G' b" P7 z6 ^  z( X二、 软件分析与选择
    9 J5 [) A7 k9 `* \- I2 }
    : U) h% r( j( B  Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。
    & ^4 q$ b6 H4 Q( v
    " G, S6 |; I" G  首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。
      k! b- O* }! C. ]  而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答
    , g9 s  g9 ~# m7 }  Q- mhttps://www.zhihu.com/question/49319704/answer/1659234514 Z% `: S0 d, v/ B4 {. Q; Q6 g, u2 Y
    9 e& X5 B8 `# e7 R  c. y& H! L
      用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。
    . A( q0 e1 d; s6 l- V  然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
    $ d( X7 [4 t( {$ H  而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。
    8 k6 o6 j# V5 R3 b
      U% @' c' c3 X$ x! m4 k1 I# [  那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。
    ; l) q7 F1 m1 O: \/ d0 K# S) s9 ?2 C1 v4 {
    三、 如何上手Lingo
    7 J& G& [7 s5 I1 M# H. s7 c; s6 b7 `. e; M5 |2 Z
      有很多人对于Lingo的评价都是,非常简单的软件,很好上手。
    $ E# u+ J2 f% E7 I% D  “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。
    / t) }( x; I9 K5 e
    ( f8 f" c/ Y( \7 C3 B) W# e四、 Lingo的基本语法规则" b; L; m- [3 w. ~) x* w

    5 d8 b% E8 h1 V1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示;
    5 g# }/ {. `$ q2 ~* [2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行;
    1 j2 r( p+ f. A: H% ~3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写;
    ) X$ p) t- P, ]4、可以给语句加上标号;
    ' j/ L8 Z* r) o  G  W: g! H5、注释以“!”开头以“;”结束;
    - u3 m, N6 ~( [: K9 l! q6、默认所有的决策变量为非负数; ( A& p; |( N  G8 d' a$ k0 c! h
    7、Lingo模型以“MODEL”开头以“END”结束。 ; y( f1 ^) ?# l; ^) ?+ B
    8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。 1 `8 K2 l9 f$ e4 w7 H3 l, \8 a( L
    9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。 ' y! y; N& ]9 y$ X/ D5 f# D
    10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。1 y) X- I. ?  g- A$ e

    ) v. ^5 `/ i& I* N' k# t五、 谈一谈例子
    6 g& v7 D$ ~/ f, ~* J& S" _& _+ p- S2 _+ I$ a  h' R
      那么Lingo用起来到底有多简单呢,我们来看一个例子。
    ' K( C3 c1 K/ G2 H, c- g$ S2 l) i
    % O$ W" N: _9 S6 r例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:
    1 d2 L% `/ a" }/ h- G8 F3 d2 K7 U9 B- B2 F
             每个书桌        每个餐桌        每个椅子        现有资源总数& b, X2 k1 S- p8 I! ?; r6 n9 X
    木料        8个单位        6个单位        1个单位        48个单位+ L4 Q' F* i, E$ k+ @; t
    漆工        4个单位        2个单位        1.5个单位        20个单位
    4 V+ u* f8 _) W木工        2个单位        1.5个单位        0.5个单位        8个单位
    7 v1 C) x; L% ^/ b6 J; m成品单价        60个单位        30个单位        20个单位         
    8 H' i( b6 n8 Z- o3 I* X4 h  若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?* _+ Y: Y5 }3 K7 X- P

    $ Q$ `) ^, e, ?' c9 X" |1 p. M解:代码4 [8 p$ n6 R1 e2 X2 O- G$ j8 g' y

    + P( `  D9 C" J2 p! v  Xmax = 60 * desks + 30 * tables + 20 * chairs;
    % l4 n6 P  O7 r8 H' Z7 n- ^! O      8 * desks + 6 * tables + chairs <= 48;! x$ \' c! M" K7 R' p
          4 * desks + 2 * tables + 1.5 * chairs <= 20;3 A) w8 z, s( y3 s9 i
          2 * desks + 1.5 * tables + .5 * chairs <= 8;' Z# R2 Q7 v0 `+ q4 C- _$ g  Z
    tables <= 5;; i5 b+ N2 ~2 E& ]; g
    1
    % I7 r5 B5 Y7 |27 y, q5 o: ]5 U  C; N0 G
    38 L  ^# C" [: Q, p
    4
    # _8 T" w4 {8 p5
    % v" V3 i1 x# u可以得到结果: 7 X: _; p4 h% c" S7 v) ?2 O1 k

      K) c6 U6 o3 ~: R6 R  这里的 Total solver iteration 表示一共迭代2次得到最优解。
    & n0 N! P7 @1 z0 X1 [  Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。
    6 @. [) l2 f& e9 {3 M( @  可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。
    . M) Q$ M: P$ @' Y6 B9 x  K6 s0 i
    3 s: n6 ]* A, C# Y9 k+ }$ O例2:给定一个直角三角形,求包含该三角形的最小正方形。; d3 [, j. {4 @5 g- o/ ^' C( c
    ' Z$ H2 ~- g- f
    我们可以作出如下正方形:
    0 [" T9 A! r( q5 V; S( K, G. B3 J! w1 R" K% y- r) }

    % }5 n* O* F) q* b  CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx; O; @9 q5 H4 T' O& f. d) D
      转化为了规划问题那么正方形面积最小的时候即为最优解。
    " R. N3 K* s: ?0 @  代码:2 A! ^, ~5 Z/ k- G1 {

    * u  O; D3 Q2 v# tmodel:) H8 j3 T3 S: T) k. Y
    sets:
    : A1 v) w; [  O- U: K1 t5 z    object/1..3/:f;  U. P8 m8 U. a
    endsets; e4 n8 Z5 L: z" R
    data:. [, T( ~( _3 e, ?; K' t5 p) ]
        a, b = 3, 4;5 I  Q9 J' Z0 U2 |- H+ q
    enddata
    3 j& }% V0 G; g! g- m/ s6 s    f(1) = a * @sin(x);
      x0 F6 V& G* ^- x+ k+ \    f(2) = b * @cos(x);) X3 z4 z- J' g% y' d& y
        f(3) = a * @cos(x) + b * @sin(x);
    + J3 F( N) a. B3 K& J- ~5 q, L    min = @smax(f(1), f(2), f(3));
    5 p- l& N& a) v8 d& A* s    @bnd(0, x, 1.57);
    ; {* l' r2 S! S8 a! Send
    $ f& k0 ~' X' c9 u, X& e1% K8 a2 A3 c0 `/ i& O3 P
    2' w0 M  I  ^- v
    3
      k% d+ ?3 y! X; ^42 f; l6 c% n4 q; m) V6 V; o6 U
    5  W/ _9 _, D5 w; L/ ]5 Y5 I
    6
    # d( @% ^' X; g7 Z" @- J$ `6 }+ K& e7' c; g, v5 X  m- a- W7 W) U3 H
    8
    & l$ l8 m! e  [4 J; C+ s( R9
    ! n+ w! |6 ]: n: K. y7 A107 T, i& j7 s7 Y! B
    11: Z" s" J. X0 n% [/ y
    12: W; R4 u5 K  X/ u: G7 q/ t  z
    13/ }* U  g' G. Q$ ^+ ]# N( w; ~2 ]
      得到结果:
    ! _  H1 w* @0 S9 K" V8 h: c5 G
    6 F8 ]0 I* h/ D! G/ Z# `/ d
    $ R- K6 J0 d  f9 u5 ]  这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。2 E0 n- J  C9 c9 z7 [4 H. Q
      那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?( t, H- S% Y( A
    , {/ J! O* b5 p3 a3 P3 S; G
    例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 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为 : K, c9 A. [' y, R; v2 v
    ∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj/ S5 O& u5 ?& K, M, n' ?) z3 n; L
    ∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj) v: p. f5 b& n0 Y; g
    由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。  g* P  @6 n; |$ x$ @

    " D4 @" y0 X" j) ?' B代码:
    9 P5 m, r/ z% ]# t, e) l0 Q
    & \% b; S$ M/ P# Y! b  [4 m!旅行商问题;6 f3 ~: D2 ^* y, S" C
    model:' f; Q3 l1 P4 Z" F* Z
    sets:
    ) }4 |# T7 _$ A" w$ R- A    city / 1.. 5/: u;9 n  `5 l1 q9 a
        link(city, city):: T7 _* i1 f! z. r# i
            dist, x; !距离矩阵;: l! @/ Q4 a* K& F+ l# M
    endsets5 M  m! R! h8 C' x: E
        n = @size(city);" S8 I* b; C$ I% e* d* i7 Q% `- T
    data: !距离矩阵,它并不需要是对称的;5 o  g/ ?/ V2 Q
        dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;
    4 n% _8 {% a3 ienddata
    * V/ U2 {! t9 {5 Y/ ]6 ?    min = @sum(link:dist * x);
    % S1 j0 z' j1 ]. n    @FOR(city(K):$ F4 w7 G. ~' ]) D) D. r7 b
            @sum(city(I)|I #ne# K: x(I, K)) = 1;
    ( U: i1 G. `! Z+ n- s4 w        !进入城市K;9 ?0 d  {8 c7 U
            @sum(city(J)|J #ne# K: x(K, J)) = 1;. [  [' k& A* }0 ?: ], Y
        );2 j9 ^8 W9 Y# v- Q; ]' N7 b
        @for(city(I)|I #gt# 1:) {9 }& L( P3 V% F  g: L1 Z5 F
            @for(city( J)| J#gt#1 #and# I #ne# J:
    % n: c+ v- X( E7 b' [- m             u(I) - u(J) + n * x(I,J) <= n - 1);8 g" V( H1 u# E* r( J( E
        );
    , V) G- I0 t3 r% O' ~@for(city(I)|I #gt# 1: u(I) <= n - 2);& S2 \" i4 }' }" ?
    @for(link: @bin(x));. R! O7 K. {+ J: C" i9 _+ ~
    end
    ! c5 T1 Z3 K* i: ?1 W1 ~1! Z" G4 {- N/ v" i
    2! k0 u6 `; _0 [! j
    3
    8 U. t, X$ V$ b. s4
      h! u: ~" o1 f5
    : _: U& s; {' `- C69 Z8 d% x& F( t+ q- S
    77 j1 Q; o& w$ F7 _
    8
    ( @% N) V* W4 n5 q* i/ C9
    ; J7 p/ Q, T8 n1 M2 D9 J10, ^( Q" u0 ]# ?' |2 }. C
    11
    $ i2 h2 T: O) a12! s  V. S8 R0 u" S3 w
    137 u/ M& L) ^: g) `
    14" [0 Z: R  i1 ~" L
    159 ~" p) Q( m6 W
    162 R: q  i8 A% B5 u. m( T
    17
    & T7 A% S2 ?  s) T2 W0 u: r18
    5 i; s8 L/ D0 W9 C; `2 l19
    3 v  B5 _0 O' v20
    ' K8 L7 ?4 N- ~+ p4 ]21! U8 S8 b. R( T& y* [  z
    22
    * C. i# W3 Y! C  H23$ _% [, M1 J4 R* U
    24
    $ \- e( |  E/ J0 I4 T2 v5 o可以得到结果:
    6 ?; N+ c& d5 _/ f  `* C
    8 X& j1 k5 p( [0 O/ g1 n9 l--------------------- 2 v& ], D2 x& A5 C0 X: b4 b9 e; U

    + M, F8 `5 ~: T% c  Z1 W+ i' X8 U

    + b" e* f& X* x9 m
    . Q3 ^2 @) P4 x9 t/ s- V  Y- w; m# G& S7 [9 w
    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-7-11 19:26 , Processed in 0.329758 second(s), 50 queries .

    回顶部