- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36395 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13879
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
问题描述: 某市消防中心同时接到了三处火警电话。根据当前的火势,三处火警地点分 别需要 2 辆、2 辆和 3 辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度:记 为第 j 辆消防车到达火警地点i的时间,则三处火警地点的损失分别为![]()
" v- L9 D d7 F# p3 U* c) ^8 j+ u1 h3 H2 S G6 B
% K8 }6 x4 F: j. _2 Y5 B" c( P
; 。目前可供消防中心调度的消防车正好有 7辆,分别属于三个消防站(可用消防车数量分别为 3 辆、2 辆、2 辆)。消防车从三个消 防站到三个火警地点所需要的时间如表 6 所示。应如何调度消防车,才能使总损失最 小?
4 W' H2 d! g6 [, Y3 y4 D3 ~7 C: `2 Z) j+ C* k
![]()
( r7 J. e! K( W2 |: n
{4 [' t! W* x问题二:如果三处火警地点的损失分别为 ;,调度方案是否需要改变?
9 h, I4 `+ z9 P( x9 i+ x1 j4 S: Z; D5 L3 z, \2 h& @; i
- C- e* A0 x+ V! I7 C$ E3 o! w6 {, _+ G1 s# D
(1)问题分析( {2 A! \5 Q% W& z% e
8 X G; @- R' c( R; A3 H本题考虑的是为每个火警地点分配消防车的问题,初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形,我们下面首先把它变成一个运输问题建模求解。
& y- V$ ]0 G8 u* J0 h p" [) U4 B L4 h7 l4 ]; ^9 O8 }
(2)决策变量- Y$ p# p1 P P
* I7 Y9 Q* g1 h. D# B/ N3 B
为了用运输问题建模求解,我们很自然地把 3 个消防站看成供应点。如果直接把 3 个火警地点看成需求点,我们却不能很方便地描述消防车到达的先后次序,因此难以确 定损失的大小。下面我们把 7 辆车的需求分别看成 7 个需求点(分别对应于到达时间 . 用 表示消防站i是否向第 j 个需求点派车(1 表示派车,0表示不派车),则共有 21 个 0−1 变量.
; e0 M# `# c% {( _, R; d9 a3 F. R( J) E8 C
(3)模型建立
$ ~7 d4 O5 T- l. y7 }, c s3 S. {' i! @
题目中给出的损失函数都是消防车到达时间的线性函数,所以由所给数据进行简 单的计算可知,如果消防站 1 向第 6 个需求点派车(即消防站 1 向火警地点 3 派车但该 消防车是到达火警地点 3 的第二辆车),则由此引起的损失为 72 98 = × 。同理计算,可以得到损失矩阵如表 7 所示(元素分别记为 )。
: o: m# U3 ^6 r( n1 X8 C# ~0 p' [2 S- M9 @+ `: m
: R' t- A' Z3 N
1 ]# o, T0 M* U1 @; \; T* G
4 r3 e% \' H3 `# l% o$ y
: I& ]4 z& b( r: F, ]- ?+ a
1 n5 w% w; A( v5 d) w: f R% u
于是,使总损失最小的决策目标为
# N, o: ~9 j1 Y" i; Q+ N- a* X' C/ F" y: t. g
( 1 )5 v1 A! s# ^! J+ t% b* z
: D8 p5 k D1 ]3 @9 ?
约束条件:
* C" f+ w$ v# a) }% P9 g5 o+ d1 `6 R& @# u& Y
约束条件有两类,一类是消防站拥有的消防车的数量限制,另一类是 各需求点对消防车的需求量限制。 2 h" d: ~* C# B+ [1 E8 |
记 ( i=1,2,3 )为第i个消防站拥有消防车的数量,则消防站拥有的消防车的数量限制可以表示为
* \7 M0 P' u8 t0 I ( 2 )" f9 y& n6 Y5 }4 m- |' L
4 D* Y$ J/ s5 M4 \
各需求点对消防车的需求量限制可以表示为
) S' c S$ B6 m/ H9 G* v+ y9 |9 @0 H; L4 `
( 3 )- s. @7 }' q/ |3 o' I
# @$ N m$ l- c0 y B9 L% I: G+ O
(4)模型求解 的lingo代码9 G# m0 |$ w% }3 X- s
\5 ^ H+ o% w1 s+ `
MODEL:
6 W7 I2 u/ H- PTITLE 消防车问题; 6 w+ c! K/ d4 C; o- n" p
SETS: 9 s8 h( S2 `, v7 Z
supply/1..3/:b;
2 M# o4 ?. z, w4 r1 Fneed/1..7/; 2 ?$ Y3 s/ B2 K* i8 T
links(supply,need):c,x;
% `! l8 w. k) r6 ~6 iENDSETS 8 r8 D" o$ i) Y2 i
[OBJ]Min=@sum(links:c*x); 4 i* F0 p9 b7 `" q9 }
@FOR(supply(i):@sum(need(j):x(i,j))=b(i)); 8 |" A6 q/ F5 g" t0 F. g* Q$ `: }
@FOR(need(j):@sum(supply(i):x(i,j))=1); % ^( y2 j) I9 W2 l2 ?7 i/ c6 P# Q: i
DATA: " U: S% a* M& a/ Z, v
b=3,2,2;
, [# q* f/ g' `8 I j4 b" rc=36,24,49,21,81,72,45 o0 m& U. ~& V/ F$ g( Y
30,20,56,24,99,88,55
8 n' p: Q2 J1 l/ s" Y. t" d 36,24,63,27,90,80,50;
2 \$ p% y2 r- y( fENDDATA
4 A( c0 A/ o' f4 P2 q, E" dEND
% W2 T2 v9 @$ h; l: i求得结果为,消防站 1 应向火警地点 2 派 1 辆车,向火警地点 3 派 2 辆车;消防站 2 应向火警地点 1 派 2 辆车;消防站 3 应向火警地点 2、3 各派 1 辆车。最小总损失 为 329。. }! w E) ?% X; I
- S# D$ L2 h9 x6 k
(5)讨论% L. J( r, ^2 n' w7 H! K# s- w
, E9 m) Q! `) w3 k* F
1)这个问题本质上仍然和经典的运输问题类似,可以把每辆车到达火场看做需求点,消防站看做供应点。在上面模型中,我们虽然假设 为 0− 1变量,但求解时是采用线性规划求解的,也就是说没有加上 为 0− 1 变量或整数变量的限制条件,但求解得到的结果中 正好是 0−1 变量。这一结果不是偶然的,而是运输问题特有的一种性质.
- O( p2 E9 F" l# P x0 E* e t U* ]8 X# T
2 )在上面模型中,没有考虑消防车到达各火警地点的先后次序约束,但得到的结果正好满足所有的先后次序约束,这一结果不是必然的,而只是巧合。如对例题后半部 分的情形,结果就不是这样了。显然,此时只需要修改损失矩阵如表 8 所示(所示(元素仍然分别记为 )
$ Q7 E" W" U: L1 E" F: H4 b' }( I, w6 V
. f4 m' Y3 |+ x! v
$ M+ p* M7 C E: J" C' F此时重新将式( 1 )-( 3 ) 构成的线性规划模型输入 LINGO 求解,可以得到新的最优解 : 其它变量为 0(最小总损失仍为 329)* E3 H) E# T$ \1 R8 @
9 r, Y: |# i, U; L7 b实际上,损失矩阵中只是 1、2 列交换了位置,3、4 列交换了位置,5、7 列 交换了位置,因此不用重新求解就可以直接看出以上新的最优解。
. P3 F- |! B6 A' ]/ t1 C# Y
+ L% r3 N6 ^) h& C但是,以上新的最优解却是不符合实际情况的。例如, 表明火警地点2 的第一辆消防车来自消防站 3,第二辆消防车来自消防站 1,但这是不合理的,因为 火警地点 2 与消费站 3 有 9min 的距离,大于与消防站 1 的 7min 的距离。分配给火警 地点 3 的消防车也有类似的不合理问题。为了解决这一问题,我们必须考虑消防车到达 各火警地点的先后次序约束,也就是说必须在简单的运输问题模型中增加一些新的约 束,以保证以上的不合理问题不再出现。
( t f& z0 N1 v* ?6 ]/ d6 g3 p" R- H6 B9 C
首先考虑火警地点 2。由于消防站 1 的消防车到达所需时间(7min)小于消防站 2 的消防车到达所需时间(8 分钟),并都小于消防站 3 的消防车到达所需时间(9 分钟), 因此火警地点 2 的第二辆消防车如果来自消防站 1,则火警地点 2 的第 1 辆消防车也一 定来自消防站 1;火警地点 2 的第 2 辆消防车如果来自消防站 2,则火警地点 2 的第 1 辆消防车一定来自消防站 1 或 2。因此,必须增加以下约束: ( 4 )8 q2 ]+ e8 c7 y3 B7 E1 L
3 G! d) e/ l2 r+ A# s! r; V7 z同理,对火警地点 1,必须增加以下约束: ( 5 )2 A6 h4 L2 V$ \6 `4 ]
' N! y) m! c9 `7 ~* }8 e- T/ T4 n对火警地点 3,必须增加以下约束: ( 6 ), }- ?" [; K( K$ L) D
. [8 S6 r5 |: R1 W重新将式(1)~(6)构成的整数规划模型( 是 1 0− 变量)输入 LINGO 软件如下:( G3 g) C3 a. c7 Y5 E3 k5 Y3 _
4 T. r2 w3 x* g* l! E; ?MODEL: 7 y! h" W4 j' C1 E# K
TITLE 消防车问题; 9 @9 u5 @7 m6 P& j
SETS: $ `7 B7 `( p w, M4 i
supply/1..3/:b;
/ ^1 h% q+ d3 o! P% l! Oneed/1..7/;
. h' [6 Z3 j \+ q L8 _9 v. T! blinks(supply,need):c,x; + y$ }9 |- P6 Y
ENDSETS ( b1 G5 F1 L0 Y& h
[OBJ]Min=@sum(links:c*x); * t$ _( d& R E% C; d3 p
@FOR(supply(i):@sum(need(j):x(i,j))=b(i)); 0 |0 i( p2 X. |/ ?& _
@FOR(need(j):@sum(supply(i):x(i,j))=1);
* q$ r& m, h" t1 p# \2 d! B. wx(1,4)<x(1,3); * g% j* F' g t( e
x(2,4)<x(1,3)+x(2,3); # E( q9 H; p! l# u" C
x(2,2)<x(2,1);
# a; H! C, Z) f/ O2 }x(1,6)<x(1,5); , ^, v1 H H$ A# x* s
x(1,7)<x(1,6); : {) G: W" `9 h Z8 I5 C9 \: M
x(3,6)<x(1,5)+x(3,5); 0 G# e7 Q F \( o8 ?6 O8 S# x1 D9 J
2*x(3,7)<x(1,5)+x(1,6)+x(3,5)+x(3,6);
9 |" O7 e5 O+ y& O3 }! h( f@for(links:@bin(x)); % N: @# y2 b( I
DATA:4 `; R& y: U) b9 O% o8 Z) M' U
b=3,2,2;
' I1 \6 r6 p/ K/ j6 Fc= 24 36 21 49 45 72 81
* ~1 n" I6 z0 m& z 20 30 24 56 55 88 99
5 l" y" s: T8 C0 T 24 36 27 63 50 80 90; * f6 b9 @4 A$ [0 d, Y
ENDDATA
. N) d3 B; u9 X& n9 Y5 pEND 1 P# x) o% O2 S( s3 M' S* ?
求解可以得到: ,其它变量为 0(最小总损失仍为 335)。也就是说,消防站 1 应向火警地点 2 派 2 辆车,向火警地点 3 派 1 辆车;消防站 2 应向火警地点 1 派 2 辆车;消防站 3 应向火警地点 3 派 2 辆车。经过检 验可以发现,此时的派车方案是合理的。 , @, M8 U) E- k1 {1 ^5 }. v: R
————————————————& j9 G& M* G7 q0 k
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
- f# o( s- d" a4 N P+ Q3 L1 G" w原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89388172
% u0 e6 O" u5 K( X' q& ~( F
, Z N1 [% N$ ~
/ E! i" Z1 C$ P. a2 I1 m. S+ m; D3 u! y' V
|
zan
|