QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 9717|回复: 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解法" j# ]0 F, T+ \1 s/ y
    一、 从规划问题引入
    4 h/ ^; [* x5 m& `2 _9 ?1 _
    8 e& |% j. @" I5 x  在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?
    1 m( H4 }) u4 a3 o6 b: ?1 X/ Z5 x1 C' ?% \
    二、 软件分析与选择
    0 G  n, f' ]2 z6 ]/ v9 w. K2 P3 ?( j8 e% \8 o3 h' Q7 F
      Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。
    * g8 w4 ?$ @$ y/ x9 [& |1 {! A, v2 Q7 m; i" n
      首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。
    ; ^% b; U6 h" a  X  Z  而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答
    ; J4 w, t1 @8 `. D- ^https://www.zhihu.com/question/49319704/answer/165923451, ]- M) B' z) {! x5 b" f
    6 D* H$ g5 w0 w
      用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。 / ?- _# H6 |/ }$ l# r
      然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
    / e4 O1 l3 s: @4 N5 I  而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。/ ~; b4 u3 i2 |  I, r# p" |

    % k& W: Q' {, t- Z) s  那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。9 g8 T$ u* }3 @

    9 s9 _- ^0 q" s% H+ p" M三、 如何上手Lingo' B8 V6 L; F! [* X9 G6 Q
    ' ~+ ]9 x3 D, F) n9 K- ~
      有很多人对于Lingo的评价都是,非常简单的软件,很好上手。
    / C1 ]6 s1 ^7 k  “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。: E/ \! ~& h# u. u7 _. }9 o! O

    # f3 Q+ L; J, v) A' c四、 Lingo的基本语法规则
    " X" p% [7 R& A7 _1 h! b/ c) s4 B3 c- `& ~. Q
    1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示;
    : t# s! S) F$ E2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行;
    3 U( o. @; F% z/ G3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写;
    1 N/ m; P& {# ~/ F& p' c& e4、可以给语句加上标号;
    . O/ d3 n, V% l* Q5、注释以“!”开头以“;”结束; ! ^$ Y3 T$ d( j- G6 d2 }6 N+ C
    6、默认所有的决策变量为非负数;
    3 V8 `8 ?6 Q3 f5 T- |7、Lingo模型以“MODEL”开头以“END”结束。
    : b( S/ Y! U8 @8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。
    7 _: _6 H% C$ I5 \% w9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。 2 f( j3 I& A& K, O) w; m6 T
    10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。
    # n, l0 Q' B6 m4 f* j
    8 D4 X, `& J! r9 Q7 X) F1 [五、 谈一谈例子
    2 G7 H  n  y) L( i" x
    6 f/ x% t$ x; Q( `* p  那么Lingo用起来到底有多简单呢,我们来看一个例子。
    % H) d; c# I) \9 v; W
    1 W( `% `" X9 K1 U例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:$ n7 E) K& F+ w8 B9 l/ {

    - H( S( e) N2 p$ z- s         每个书桌        每个餐桌        每个椅子        现有资源总数
    , w& y! Y( x! N3 q% w木料        8个单位        6个单位        1个单位        48个单位! n( \( y0 Z1 I$ l( W
    漆工        4个单位        2个单位        1.5个单位        20个单位
    ( j& z7 \& S" C+ e8 t7 {9 t; T木工        2个单位        1.5个单位        0.5个单位        8个单位( P% f9 J7 ]( t# M
    成品单价        60个单位        30个单位        20个单位         . L7 a2 p* f% G. {! X9 ~
      若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?% b! t( U6 T* E* K

    0 d" E  A4 p' x2 {解:代码. F  H. H5 ]6 l0 V

    ( U3 A2 A  h4 A- i/ N; qmax = 60 * desks + 30 * tables + 20 * chairs;# s$ _+ B1 f8 l/ o3 Q
          8 * desks + 6 * tables + chairs <= 48;
    . n3 z, A, i4 L4 u# X6 f      4 * desks + 2 * tables + 1.5 * chairs <= 20;4 A/ y  w8 \9 L% J8 [6 o( y
          2 * desks + 1.5 * tables + .5 * chairs <= 8;
    6 Z+ L' H; G6 M( Atables <= 5;
    1 I4 m% P" |2 s1
    * o: Q( ~; T$ M- q$ P" n- \7 q2
    $ V; ~; e$ D( K- D; b% d3 n0 o3
    # d1 D# P' J9 j" X7 U, D4 m4
    7 e; ]& l; E6 D5
    ( q2 Y: c; T# I可以得到结果: 4 j) C. M% l3 L
    3 v/ ~: |& z. b
      这里的 Total solver iteration 表示一共迭代2次得到最优解。 # }' A* V: w* H7 c  u; U
      Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。
    4 @2 k6 s( G3 {  可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。" f- H9 e  O- B" o2 y4 w# D% L
    7 L) l$ d, ]9 N0 Y
    例2:给定一个直角三角形,求包含该三角形的最小正方形。
    % L! Z6 F. r: D7 Q8 A4 G' j. ]0 B& O8 v4 J" G
    我们可以作出如下正方形:
    , @4 F9 _. y$ X/ B6 b0 M. K1 a) T+ O8 `5 \1 Q

    * w8 L1 U5 d' w. @1 P! \. S  CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx" j6 ?' i0 D7 E7 W5 A
      转化为了规划问题那么正方形面积最小的时候即为最优解。
      Z. X& j6 M6 U  代码:( \: g! E. [, ~' d: Q8 L) r

    : ~7 n* w1 _% R2 Imodel:* N: f' D. z% v. T
    sets:
    0 O$ q+ Q( _& G2 I+ ]( g, w    object/1..3/:f;. C# s+ P" j6 N, ^  f
    endsets
    - u4 j/ O  o$ F) ]( o1 g; N" G+ Edata:
    ; g! Q; ?( }- p( h  R0 [    a, b = 3, 4;
    . T/ D/ }( i+ K+ g& T# V* senddata, v2 h( X& ?6 K8 E  o% w5 U6 E9 k
        f(1) = a * @sin(x);7 s4 r' w+ a% r' p$ k
        f(2) = b * @cos(x);5 ~6 G6 z0 P! O% r+ T
        f(3) = a * @cos(x) + b * @sin(x);
    0 M  v9 W* u7 h: Q2 ~, i    min = @smax(f(1), f(2), f(3));/ n; f, k6 C+ J4 d0 }' {
        @bnd(0, x, 1.57);
    # m$ v! A9 j4 x% D) q( x( Lend
    $ I  r. e' T/ I1 f3 O$ k- n# j; k1
    ! d/ x+ a& C: U# L1 R0 _+ L2
    3 ?* a4 ~9 G, k/ L6 z) B4 }; q3; @: G4 Y  e! g1 H/ P. p
    4
    ' E4 V" Z( g+ |  z2 B' K5
    + N' E: R6 }+ `$ P9 q( B. z6
    8 m  I  }# C: M( W) D7. r% O7 }5 U( c0 w
    8
    1 J# Z' _& m" E. ?% w9- T: i- _& i9 U
    10* N! `, M# U6 O! D9 B
    118 b2 o* X( H- \: n0 Z
    12
    1 K; A+ l0 ~. c4 q% K; y7 G13$ i1 N2 u% [. Q4 X+ V2 A$ s( T
      得到结果:
    * M6 ~3 r5 ?' U6 A4 p& y8 \
    5 W" ?3 L' C" y7 J+ i  l+ s3 ^2 A8 B+ ]7 c5 K9 P3 ~* C+ b
      这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。. p3 [) G$ C" y5 Y1 B# l
      那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?' I, P2 @: I& S8 C) `7 Q: c! v

    , l/ x! u1 Y. t+ @% h: w例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 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为 : A; J9 G$ e) h7 U3 X4 w
    ∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    + p6 s3 v# U, ^& g6 [∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    " t3 y) S3 |( g由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。/ C) Y' _+ y- }) L4 q3 g. p
    & n0 Q; u2 ~1 S1 z) L. j4 g; `' x
    代码:1 H3 u$ T/ v8 N& l  l! g
    + A" s/ h" n( t. v; g
    !旅行商问题;' ?" g" v4 M( j( A
    model:) b7 ?- k" X2 s5 \) v9 z6 d3 {
    sets:
    % d( G7 W8 Z/ I1 U0 [' r    city / 1.. 5/: u;
    * `% J* u# y" O! s    link(city, city):
    ) S" w1 h* K- ]7 |9 y1 W        dist, x; !距离矩阵;. Q- Q3 X: d1 P4 y! t% e2 r5 ^
    endsets
    % j9 p6 t; o. c2 J, g( |    n = @size(city);
    ( o* W. l; h; I2 D! idata: !距离矩阵,它并不需要是对称的;- x1 H1 B, V! n6 B  J% [$ C
        dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;* ~  a2 I+ V, E8 T. y
    enddata
    1 Q" ~8 \# ^* n' l; @    min = @sum(link:dist * x);9 c; U* S1 I$ {+ C7 Z
        @FOR(city(K):8 X# Q2 i1 Y6 S, f
            @sum(city(I)|I #ne# K: x(I, K)) = 1;
    / l& k* t1 A: e! j( Q  j# t        !进入城市K;+ H+ X9 X% a) {, s9 c
            @sum(city(J)|J #ne# K: x(K, J)) = 1;5 x$ c5 x0 B( J9 I
        );
    , b$ v7 i; N) V' f4 |$ h    @for(city(I)|I #gt# 1:
    6 Z6 [2 @( _6 @) L" b' T( Y; U        @for(city( J)| J#gt#1 #and# I #ne# J:8 X  b& `9 L8 C  Y: E( T
                 u(I) - u(J) + n * x(I,J) <= n - 1);
    ( N% ^9 k; m# r8 a9 E; S( x    );
    * U( o/ E0 G3 W, Z& v" p$ L: P@for(city(I)|I #gt# 1: u(I) <= n - 2);& \' _7 S* k1 C$ K! D7 g2 {, r
    @for(link: @bin(x));, i/ a# S1 H4 w! f
    end
    & ^  l; V; i. r* P9 p0 b16 S; J% B' M+ F- R5 D: e/ _
    2/ D6 g0 \( T7 S
    3
    6 H' d! z' O$ E4 H8 Y& v5 [9 w7 G: W4- S4 F4 X/ i0 J  y5 e6 h' D9 j( R
    5/ v8 n% ~& X5 R9 @4 F2 }( h3 ^+ T
    6
    0 W7 X- t0 \6 D, q# M6 l7
    $ `& f, [4 x" a8/ L8 t0 \* s. m: B+ H' b' P4 ?
    9, G. p! X3 d7 H# ?1 m. H- n
    10
    ' k- G7 F2 o* Q4 w11
    & e; o' N1 I1 F8 C121 m2 y+ r$ i6 L: M5 M5 [
    136 d% u# {6 v" o1 Z  N; F" ~
    14+ m+ f$ g/ l; J8 B' K) I2 y& @% A
    15- ]! B7 S* Q5 }9 e/ v# a
    16
    , L; f  A1 b: E* C6 C  K1 Z17
    % s  v* \6 z1 [18
    . m8 Z9 {5 u# T: z19
    ; k4 x$ U* i& L200 v2 \0 }& x3 Y2 y
    21
    . P$ F: A; z  ?9 c8 e22' x8 H- b7 `+ m; \8 a
    23
      l/ W' k# o, X5 V* c0 E, g24
    # F3 o6 ^5 }2 h# r6 F( h可以得到结果: 4 ^' C' ?; ?7 a# h1 }
      {# `# i8 n7 e+ G, \
    --------------------- . b2 Z* K" n* [& y( t: b: z

    - v' G, K2 M3 [! `# F: h
    ; L8 i2 ~, }/ }8 V0 F% t- u6 O
    6 z  q/ l  r! r4 Y9 Y8 D% Y9 {4 R# ]( H

    8 f9 G2 l/ m! L& p
    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-31 05:01 , Processed in 0.908112 second(s), 51 queries .

    回顶部