- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 81
- 收听数
- 1
- 能力
- 120 分
- 体力
- 539959 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 167366
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5324
- 主题
- 5250
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
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
|