QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 9860|回复: 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解法
    0 u) T* h0 d; N( a5 C. a$ v一、 从规划问题引入
    ; g7 q, |' |$ X( y1 F' m% K1 z" ~+ y3 }9 W
      在我们学习探索的各个领域,规划问题都是无处不在的。通过列出约束条件及目标函数,再画出约束条件所表示的可行域,就能在可行域内求得目标函数的最优解以及最优值。当然我们在高中就已经学习过线性规划的相关知识,对于理科同学来说,大多数同学应该感觉难度不大,或者说是送分考点。然而到了大学阶段,一些规划问题的求解已经不是人力可以轻松算出来的了,必须借助于计算机来进行计算。那么对于规划问题的软件选择,又应当如何进行呢?8 [+ t: S) F8 H9 `5 K+ l" x  N
    ( z8 b% F4 ?6 t1 u! g9 W4 C
    二、 软件分析与选择) z( f9 w. \4 U5 i7 D8 D

    - \3 x& M9 b' w! R5 p" Q) @  Matlab相比之下是一个面面俱到的编程软件,也可用于求解规划问题。但是如果一定要去和某些“针对特定功能而开发的软件”去比的话,Matlab有时也会稍显逊色。就好比一款顶级的耳机能通吃高中低音,但是去和另一款顶级的为高音而设计的耳机去比较的话,也难免会被比下去。这也就是为什么在规划问题上,很多人会去使用Lingo进行求解。. B* P3 y4 O0 u1 Z  E$ a
    4 c6 k: U0 _% Y# A; {+ z
      首先我们来区分一下Lindo和Lingo这两款软件。Lingo是在Lindo基础之上做成的软件,处理解线性规划问题之外还加了非线性的求解器,更关键的是还追加了集的概念。可以更方便的解决复杂的问题。所以本文只对Lingo进行讲解。
    / x* D) j# v3 P' l5 J& f6 x+ q  而对于Matlab与Lingo的区别,就好比手动挡与自动挡的区别,有针对性的专业软件会对用户做很多的优化。这里引用知乎上大佬 花开花落 的回答 + ], M8 f/ J6 r
    https://www.zhihu.com/question/49319704/answer/1659234513 Q. E$ R' d/ a, w2 `

    8 }2 I2 c" L8 L1 T2 s2 b7 @' @4 t  用MATLAB求解线性规划和整数规划问题,需要先将问题转化成如下标准型,其中X只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。
    3 K% Y3 o. K/ d$ _* K  然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。 , g0 {  I& {5 h* s: L
      而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。# V* p4 c, [- e4 W$ y
      e8 V7 _0 h8 s  a+ q1 p' N' V
      那么现在我们基本上对LINGO和MATLAB对规划问题的处理方面有了初步认识与了解,至于是执着于MATLAB还是选择开辟LINGO这片新的领域,取决于队伍自身了。6 N6 q, h! X# j" M+ A( p, X

    4 w' c" g# K6 c. {9 V& W- e* _' R三、 如何上手Lingo
    : |2 k+ E" g& G( `
    1 Y! {$ R: [1 a+ x; o  有很多人对于Lingo的评价都是,非常简单的软件,很好上手。 * P+ {9 o3 u' I+ |4 N8 _
      “简单”一词我觉得还比较恰当。Lingo的各种版本几乎全部都是免安装版本的,界面很简单,功能用法很简单,处理问题的方式简单快捷。确实是跟“简单”一词挂钩的。但是任何一款软件想要精通,都是有一定难度的。如果你只需要用Lingo处理一些简单的线性问题,那么2个小时不到,0编程基础的朋友就能上手。如果你认准了Lingo就是你处理各类规划问题的御用软件,那么还是有很长一段路要走的。当然这也取决于用户的编程基础。如果学习过面向对象的程序设计课程的朋友,对于类与对象概念有所了解,那么对于集这一概念也能快速理解上手,学习起来更加轻松。- R9 c- D$ m# S

    0 [" g. \6 a) {0 P四、 Lingo的基本语法规则) T7 N0 e$ C% h+ ~3 N  N1 n

    5 ]; V. s" n; D: Z1、求目标函数的最大最小值用 MAX=MAX= 和 MIN=MIN= 来表示; ; g9 `  o9 u0 {' m9 A2 J
    2、每个语句必须用分号“;”结束,每行可以有许多语句,一个语句可以跨行; " a- r6 r4 u6 z3 ?7 Y
    3、变量名必须以字母A-Z开头,由字母、数字0-9和下划线组成,长度不超过32个字符,不区分大小写; ' f# y+ k. o+ k
    4、可以给语句加上标号; 2 ?& I* M. F$ @2 E3 x( a
    5、注释以“!”开头以“;”结束;
    0 d8 W- [1 }! b. Z" o  j6 h. O1 _6、默认所有的决策变量为非负数; 7 n/ A: v: i- [
    7、Lingo模型以“MODEL”开头以“END”结束。 1 ?% z) e! ~1 X
    8、Lingo把相联系的对象聚合成集,借助集,就能够用一个单一的长的简明的公式表示一系列相应的约束。
    1 U% _9 C8 A# G& M; q' v( e; L9、Lingo程序会包含集合段,数据输入段,优化目标和约束段,初始段和数据预处理部分。 / I: X6 W) N3 b; z) Z% f# `
    10、Lingo函数包括有数学函数,金融函数,概率函数,变量界定义函数,集操作函数,集循环函数,输入输出函数,辅助函数等等。9 u: a  d0 s6 [+ u
    # o. K8 @3 F- p; a7 _, L' ~
    五、 谈一谈例子% w2 k! c1 ~2 G9 e
    * |, a) m6 d. n
      那么Lingo用起来到底有多简单呢,我们来看一个例子。/ I1 j1 ~! r5 J; u

    , d: F, }# l) z+ o  Z4 F例1:某家公诉制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示:6 P1 g1 S7 n# T$ S  Q! J; n

    5 T. M# P! Y+ }8 ?5 M. g         每个书桌        每个餐桌        每个椅子        现有资源总数$ q0 `6 {3 Y% O) r* b
    木料        8个单位        6个单位        1个单位        48个单位# N, Z8 l$ j% T! h" t7 ]
    漆工        4个单位        2个单位        1.5个单位        20个单位1 I/ h2 u* L; P8 l7 W
    木工        2个单位        1.5个单位        0.5个单位        8个单位; k' S8 P$ m6 E9 N7 _
    成品单价        60个单位        30个单位        20个单位         
    ' _' D8 D, w: z6 ?; l/ d/ J  若要求桌子的生产量不超过5件,如何安排三种产品的生产可使利润最大?
    ; {, I5 c5 e! S% R. ~4 r/ E/ J
    + G" i+ v6 Z/ c7 {% g4 g+ h8 b解:代码
    3 a& G7 |$ U! R& |3 r  `4 b
    : o# Z- m6 z- h0 {max = 60 * desks + 30 * tables + 20 * chairs;
    . a/ y9 ]) F: \" p$ ~      8 * desks + 6 * tables + chairs <= 48;
    4 Z9 T) p0 ]: I) a  Q7 p8 Z6 z& J* O      4 * desks + 2 * tables + 1.5 * chairs <= 20;
    2 p* I/ }- Z$ P. F2 u      2 * desks + 1.5 * tables + .5 * chairs <= 8;2 Q+ R: D5 I0 k$ U- Z: v. R
    tables <= 5;. d+ ?2 |# g. ~
    1; M/ M- w7 W6 c. \3 T/ t
    2
    + t/ `$ F; B# L; z% j1 g7 G, [) j3
    ! e/ H) C7 V5 Z3 x) o4
    9 P. O1 ^* X; _9 i5
    2 e0 w1 q! m. R8 Z$ R7 F可以得到结果: & n2 ^& R( Z4 G  Y; {
    + @4 r+ [" i- c1 U6 z6 K" v" f
      这里的 Total solver iteration 表示一共迭代2次得到最优解。
    * k* U2 N& k, h  Objective value 表示最优值为280,而取280的时候各个变量取多少呢,底下的表格给出了答案。
    / ]% _8 k" n% n% E  可以看到,没有定义变量,简简单单一个函数一个约束条件,迅速计算出了答案。Lingo看上去就像是为了非编程人员量身定制的一样。
    1 F2 K2 O; t5 i: ], `  r3 A4 E; w
    ) T( f. c" c# ?7 `例2:给定一个直角三角形,求包含该三角形的最小正方形。
    ; i  ~* @% L! w' t
      E3 ?, b$ E1 N( I( {我们可以作出如下正方形: * S- I7 g1 ~* d( ^( Q0 u) D3 J

    $ P$ s3 Q' O5 C( Z! ~9 G6 p  ~9 @# L% @+ j8 ^
      CE=asinx,AD=bcosx,DE=acosx+bsinxCE=asinx,AD=bcosx,DE=acosx+bsinx  Y0 ?& a" q6 s( u" X& a
      转化为了规划问题那么正方形面积最小的时候即为最优解。 5 `* u2 H0 O3 w- o* ]; `, D% Z
      代码:. F7 ?# i  {7 e) ^7 [
    / L  c- I. P9 v! W" c2 D) ~
    model:: C3 ~6 v: P7 m6 P) h
    sets:
    7 u% M4 n2 T9 [, h3 i: j    object/1..3/:f;* m$ H# F+ b2 J" W9 U7 ^
    endsets; E4 H8 q: b3 E/ V1 z8 l
    data:
    0 h' L2 [- Q9 \$ k2 K5 h    a, b = 3, 4;
    9 T. h1 e0 M/ henddata2 k0 O7 E% p# F. s
        f(1) = a * @sin(x);* Q% d- M0 D& F; J( O
        f(2) = b * @cos(x);
    ' o1 e  G9 a! T# v  R! G    f(3) = a * @cos(x) + b * @sin(x);: }. a* D$ `6 q% R/ a9 Q
        min = @smax(f(1), f(2), f(3));
    , T* {. j: @5 P! O* ^0 T    @bnd(0, x, 1.57);
    ( `& L& P3 W: [: h4 rend$ q9 k  c0 c' @6 B
    1
    2 Q' R9 ~/ D& H" n, B2/ P6 n6 o1 ?; }2 p
    3
    . X$ u8 I2 k+ I1 {! a4
    7 G. t0 p/ M0 `. _+ L: W50 H+ _/ a/ C5 \% {+ f
    6
    1 t% q0 u: `( |! I6 I! z7
    3 @7 i! L; |0 O8
    ' p% Q$ H3 I. t  x  `5 N+ z9
    2 R6 l& b/ {  w1 p4 p) O7 R" |100 k9 h3 ^: f0 Y+ c7 z
    11
    / B+ Z0 J! z, d- L12
    & _% o6 |4 f) N, j8 h130 S1 w. I, I: N+ S8 N1 f7 G
      得到结果: . S7 o, o9 E+ H. W

    ; w6 V8 o, G. J1 m: w$ m: \0 z' B0 x  [
    % M: W' X3 t1 t# ?4 O) C  这里需要注意,lingo中如果没有代码说明,是默认 xx 的值大于0的。代码中用 bndbnd 函数限制了 xx 的范围。
    / X* {" `4 o' l+ N6 ]8 o9 u$ G( c. X- a  那么再进阶一下,Lingo在处理TSP问题的时候表现如何呢?( L1 `# d+ X' G$ }9 w

    ) F4 o4 C- A/ z例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 的一个圈置换 ππ 就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为
    7 K1 G/ l( M- Q1 _4 C/ b  m∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj
    0 w: n8 c; i* B( N# v$ g/ I" t; ~∑i=0n(ciπ(i)+piπ(i))=∑i=0nciπ(i)+∑j=0npj$ d7 g: L# t6 Q: V; @
    由于 ∑nj=0pj∑j=0npj 是一个常数,故该零件的加工顺序问题变成TSP。
    2 o' X2 W* w" z8 {# N
    7 m9 ~( d# [  g5 z8 J3 D# G* y8 {代码:
    : K$ A- ^5 V& R" g1 u4 v! Y! i
    !旅行商问题;/ f+ v) V/ k, U; L
    model:3 r, n7 x& U" J  B: C& l9 k+ z
    sets:
    ' u+ j2 j" ?6 V' `6 L' ^  u0 |# O9 P    city / 1.. 5/: u;
    ; H+ r8 ?$ |( w6 N    link(city, city):  A& }* A- B, p8 q, W' d: D9 B: z/ z
            dist, x; !距离矩阵;3 g/ X$ I$ Q/ D8 |
    endsets+ P; a% H8 V( n# _$ H
        n = @size(city);
    4 U& g9 K8 j3 M8 V8 I0 Gdata: !距离矩阵,它并不需要是对称的;
    - f- a! W9 M; x/ D+ N    dist = @qrand(1); !随机产生,这里可改为你要解决的问题的数据;
    5 B8 W% y/ K: U; M7 p% B4 M; s. |enddata& }  p2 i  A; }' a# V1 S$ ]
        min = @sum(link:dist * x);8 N4 Y, u0 |3 f3 Q
        @FOR(city(K):# V1 B- u+ A- M( T) V
            @sum(city(I)|I #ne# K: x(I, K)) = 1;( P: b! d3 ~8 r5 M* t
            !进入城市K;6 V2 `9 I2 Y% H7 ]( F
            @sum(city(J)|J #ne# K: x(K, J)) = 1;
    + f8 g2 H2 h! L: N2 Q    );% e6 L4 `8 x( w0 L5 E
        @for(city(I)|I #gt# 1:9 P% C+ M% a8 G& J1 X
            @for(city( J)| J#gt#1 #and# I #ne# J:
    7 t5 Y) M$ c& S( B/ A& r             u(I) - u(J) + n * x(I,J) <= n - 1);
    3 }3 g9 o; n# l) u    );
    , [) L, c4 n' u, j@for(city(I)|I #gt# 1: u(I) <= n - 2);; e$ `- p# W; s+ f  D
    @for(link: @bin(x));, O/ `9 n2 j7 ?7 u
    end6 p' X- z+ u; x; y% u
    1! Z+ O# V5 G2 z. D9 m  y7 x/ [
    2. @6 s* k! d# R% B7 t
    39 w& E1 _0 g9 v4 W0 ^" [' X. e
    4+ A9 G% y- }; `" D- |  }5 s
    5
    6 j; s  L8 o1 Q6 ^6
    0 I' s0 X9 ^# _. Q1 F8 _- h7
    3 `$ G- e2 F4 A8
    4 W$ J; i. S, {; l: `9$ _. z6 |2 E' ~  w$ O
    10
    ! z1 e8 }$ f+ ~7 X11
    ( q2 c* j, |, Q% Y12
    & {: f' _4 t% J' E& H6 i13
    1 A2 Z1 @0 D& Z# l! L; ~14$ V, |0 U- \- V4 {4 R1 Z; ]: x$ }
    15; H$ `: U0 F; S- F6 ^9 G- d
    16
    $ J6 b" r5 o) F$ \: ?173 E' [( P$ H$ @% N$ G- y9 X6 U
    18
    % z  ~" F" ~  q) i' f196 o1 s) f3 J1 H7 O# D& i
    20' q* Q( F2 K/ `; g
    210 C/ O4 g  Y: V+ F) \# o2 A
    22, C( ]: l. x5 X5 U
    234 `( |& `- p0 V, F8 W
    24  g5 W% D+ N7 a# R$ `% t6 S9 v
    可以得到结果: $ l* c( I% X0 Z; c+ b8 J
    # `* _+ d4 Q0 l& c0 u) ^, d1 f
    --------------------- ! ?, s0 }6 ^& E9 S2 V0 z$ @* E

    0 @  Z1 M* E! _- s
    3 }" D1 v* t$ d! C' p
    2 D( F9 _9 S% D. }7 `
    ! O$ K; t+ ]  @; B
    + a2 m5 b& j- A, ]0 C9 i& c$ A
    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-11-10 15:13 , Processed in 1.519349 second(s), 50 queries .

    回顶部