QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3352|回复: 0
打印 上一主题 下一主题

[建模教程] 消防车调度问题 :用数学建模优化生产与服务运作中的管理问题

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-6-17 09:20 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    问题描述: 某市消防中心同时接到了三处火警电话。根据当前的火势,三处火警地点分 别需要 2 辆、2 辆和 3 辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度:记  为第 j 辆消防车到达火警地点i的时间,则三处火警地点的损失分别为
    ) p% d* D! V) Y6 h6 p& h, N0 F; q, x% ^" E9 t3 p! o, J" w

    0 I- ^- f% u' V( t6 A. {6 U   ; 。目前可供消防中心调度的消防车正好有 7辆,分别属于三个消防站(可用消防车数量分别为 3 辆、2 辆、2 辆)。消防车从三个消 防站到三个火警地点所需要的时间如表 6 所示。应如何调度消防车,才能使总损失最 小?
    % L6 x( N0 N; {8 Q5 w. E( k( d. A/ K+ a0 q
    8 |# X7 {( H3 A

    : |/ D0 ~) v1 W+ a! ?( S( W7 }问题二:如果三处火警地点的损失分别为 ;,调度方案是否需要改变?
    . a- s. y; m. O: Y& ]% w" H
    ) R. C3 l: c$ C9 R2 n: K" W2 S4 V$ o3 B! K$ e' o8 m

    ! V2 _: L) ^, R" p* ?' [(1)问题分析
    9 z, h2 F6 d& B2 C1 z9 Z# ~1 O+ {! ^( N  X
    本题考虑的是为每个火警地点分配消防车的问题,初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形,我们下面首先把它变成一个运输问题建模求解。' |) \; E6 _( B: S  Y( q
    ' `. w1 P7 Y/ c6 n! y1 o1 o
    (2)决策变量0 j  H  ?5 ?' S% t/ B/ S4 [

    , \7 Q: p( c1 m* @1 `' v为了用运输问题建模求解,我们很自然地把 3 个消防站看成供应点。如果直接把 3 个火警地点看成需求点,我们却不能很方便地描述消防车到达的先后次序,因此难以确 定损失的大小。下面我们把 7 辆车的需求分别看成 7 个需求点(分别对应于到达时间 . 用   表示消防站i是否向第 j 个需求点派车(1 表示派车,0表示不派车),则共有 21 个  0−1 变量.
      X/ U" o/ [& E3 u
    7 L4 `/ ~' m1 V' j(3)模型建立
    7 B+ D! U9 J2 Z5 e5 p8 s0 ?. U; |, T4 G+ L$ M, L8 i, n
    题目中给出的损失函数都是消防车到达时间的线性函数,所以由所给数据进行简 单的计算可知,如果消防站 1 向第 6 个需求点派车(即消防站 1 向火警地点 3 派车但该 消防车是到达火警地点 3 的第二辆车),则由此引起的损失为 72 98 = × 。同理计算,可以得到损失矩阵如表 7 所示(元素分别记为 )。 ) C/ `8 |% s+ V
    $ U- P+ n* j) s2 ?: }1 @& M
    5 S; F% V' P0 h9 g7 O

    + u6 e$ g; D, S/ f2 P
    % T9 W/ B" E. O3 ^0 U* i$ B  k0 d5 Y# y+ m0 K3 u
    , r: E- m) ~5 ^3 D2 F) k
    于是,使总损失最小的决策目标为
    % d+ G7 D& U4 K5 ]
    ) t" O! |/ V. Q, x( \9 H+ X* c                     ( 1 )
      N3 |* W/ G( @% ^% X; w6 {4 M) w! h- ?; M0 g
    约束条件:
    7 `/ f0 x2 c& D4 A0 M
    1 C; B8 J2 n9 V) T. r约束条件有两类,一类是消防站拥有的消防车的数量限制,另一类是 各需求点对消防车的需求量限制。
    3 j0 {* u: S4 @# b, ~" A* D记   ( i=1,2,3 )为第i个消防站拥有消防车的数量,则消防站拥有的消防车的数量限制可以表示为 $ e; D& a- d8 Q: {$ t; n
                            (  2 )
    ! t3 H) T7 Z. c9 n2 w/ [( c! }. ~' e- _& M! |* g% I0 z) |$ y, H
    各需求点对消防车的需求量限制可以表示为
    4 n) P+ ?4 c1 v5 K7 c" P; Y( T3 J
               (  3 )- j# \/ n# N1 z. E. Q9 P/ s+ y
    : R+ I% h& s# _0 h( [4 M8 q6 A& A
    (4)模型求解 的lingo代码
    8 H5 {* y* ?0 r
    ( K! w2 L8 c& O! g0 H9 tMODEL: * r" n1 y, G: ~: {) J
    TITLE 消防车问题;
    ' U& ^6 I: |7 Q. B9 o, ASETS: ) f2 x9 v  ]1 _- Q
    supply/1..3/:b; 4 {- X' t8 B' D/ Y  S, C
    need/1..7/; : l7 F2 U7 _) Q, I
    links(supply,need):c,x; " `2 d0 h0 ^. `; U
    ENDSETS 1 j7 i; `( I2 _3 b
    [OBJ]Min=@sum(links:c*x);
    1 Q/ g/ n# u8 j( `9 Q' r@FOR(supply(i):@sum(need(j):x(i,j))=b(i)); - A" d) E' K+ R3 v( H
    @FOR(need(j):@sum(supply(i):x(i,j))=1);
    ; O# ~9 C9 f: I/ Y9 {8 e/ cDATA:
    " T* d# r. Y- Z6 {+ \" Ob=3,2,2; ; b1 X, V( c. i5 M3 w
    c=36,24,49,21,81,72,45   ) w2 C3 P! G. x, z  o
        30,20,56,24,99,88,55   6 V" a$ i# j' j0 n2 L
        36,24,63,27,90,80,50; , z3 o; i$ j) W) E2 |- z& [2 e( q
    ENDDATA
    * f6 Y5 k! V' N7 }6 ^END
    7 l" `* M2 s# j求得结果为,消防站 1 应向火警地点 2 派 1 辆车,向火警地点 3 派 2 辆车;消防站 2 应向火警地点 1 派 2 辆车;消防站 3 应向火警地点 2、3 各派 1 辆车。最小总损失 为 329。4 K, C4 A, C; G) f8 S

    9 n: r& k3 v4 }: X/ f(5)讨论3 ^; t' p& e: g/ @

    ; M3 s) P6 }& Y8 v: C1)这个问题本质上仍然和经典的运输问题类似,可以把每辆车到达火场看做需求点,消防站看做供应点。在上面模型中,我们虽然假设   为 0− 1变量,但求解时是采用线性规划求解的,也就是说没有加上 为 0− 1 变量或整数变量的限制条件,但求解得到的结果中   正好是 0−1 变量。这一结果不是偶然的,而是运输问题特有的一种性质.
    8 u5 I: m+ Y+ X5 E4 F4 `9 V5 A5 w7 y0 `+ b
    2 )在上面模型中,没有考虑消防车到达各火警地点的先后次序约束,但得到的结果正好满足所有的先后次序约束,这一结果不是必然的,而只是巧合。如对例题后半部 分的情形,结果就不是这样了。显然,此时只需要修改损失矩阵如表 8 所示(所示(元素仍然分别记为 )/ p) t* i- h' W7 b+ e
    - ?3 H- B& s" X  S1 f9 k( a
    3 b- ]; M" }$ A' a. E

    $ ]. T! n6 h0 ^8 c9 @7 w此时重新将式( 1 )-( 3 ) 构成的线性规划模型输入 LINGO 求解,可以得到新的最优解: 其它变量为 0(最小总损失仍为 329)
    + Y- {+ T5 @5 T' }4 q6 B3 w% k- ]' `* }! H& e) R
    实际上,损失矩阵中只是 1、2 列交换了位置,3、4 列交换了位置,5、7 列 交换了位置,因此不用重新求解就可以直接看出以上新的最优解。 4 V0 _% l* ?$ A0 ?

    6 ~- G# v; N0 E9 g) \" W- p: o但是,以上新的最优解却是不符合实际情况的。例如,  表明火警地点2 的第一辆消防车来自消防站 3,第二辆消防车来自消防站 1,但这是不合理的,因为 火警地点 2 与消费站 3 有 9min 的距离,大于与消防站 1 的 7min 的距离。分配给火警 地点 3 的消防车也有类似的不合理问题。为了解决这一问题,我们必须考虑消防车到达 各火警地点的先后次序约束,也就是说必须在简单的运输问题模型中增加一些新的约 束,以保证以上的不合理问题不再出现。
    1 J4 q3 M& }! f* l+ j- M. W, K+ K- D
    首先考虑火警地点 2。由于消防站 1 的消防车到达所需时间(7min)小于消防站 2 的消防车到达所需时间(8 分钟),并都小于消防站 3 的消防车到达所需时间(9 分钟), 因此火警地点 2 的第二辆消防车如果来自消防站 1,则火警地点 2 的第 1 辆消防车也一 定来自消防站 1;火警地点 2 的第 2 辆消防车如果来自消防站 2,则火警地点 2 的第 1 辆消防车一定来自消防站 1 或 2。因此,必须增加以下约束:   (  4 ): Q. S$ W+ ]9 y+ m* h" j
    ; \/ E/ G; j  X1 f
    同理,对火警地点 1,必须增加以下约束:    (  5 )
    ' @0 S1 A$ J+ A& m/ K5 K% S! F9 e) ?! x9 |$ M2 ]
    对火警地点 3,必须增加以下约束:     ( 6 )+ _% \, N0 F9 m) q5 L
    $ ~( h- i% y8 {2 u
    重新将式(1)~(6)构成的整数规划模型(   是 1 0− 变量)输入 LINGO 软件如下:3 W0 ~1 E+ o9 c! e9 C

    % h. [4 H. Q% RMODEL: 3 j* {1 l) h8 q! R+ R0 Z
    TITLE 消防车问题; 0 U( \$ |+ B& }0 I
    SETS: ( J/ B9 v2 f. ]. t
    supply/1..3/:b; ; U% R* _7 w! M: R' t
    need/1..7/;
    6 F, [1 L: G/ q1 U1 K2 z- \links(supply,need):c,x;
    & H4 E; L3 w! n7 W" e$ n; ?& oENDSETS $ r. W! [% n7 w5 S9 R, V' n
    [OBJ]Min=@sum(links:c*x); , H% C* P* {+ }% E6 b
    @FOR(supply(i):@sum(need(j):x(i,j))=b(i)); - q$ s! ], ]' q* L0 l) x
    @FOR(need(j):@sum(supply(i):x(i,j))=1);
    - M- i" N' f9 E1 ]& \x(1,4)<x(1,3); + T. ]1 c( J' |; z# `
    x(2,4)<x(1,3)+x(2,3); 4 i& h8 W3 A, W" y; }9 Z
    x(2,2)<x(2,1); $ H: r5 b* H" j+ d; W8 ?
    x(1,6)<x(1,5);
    - X+ P/ \' F& H, |. Tx(1,7)<x(1,6);
    7 ^! O% d1 ^+ \/ h4 vx(3,6)<x(1,5)+x(3,5); 1 l# C+ Y4 a! F3 ~5 S# O! R2 u
    2*x(3,7)<x(1,5)+x(1,6)+x(3,5)+x(3,6);
    " j9 j: ?9 ]: P. T8 z@for(links:@bin(x));
    6 L. x+ U! m$ {" V( uDATA:
    5 ?- n$ E0 l& j% q3 A/ ]b=3,2,2;
    . z1 T; ^% M# Z( j  }" p8 j9 U) c$ I- cc=  24    36    21    49    45    72    81     ) i7 [# J2 D7 U* d- d$ s
        20    30    24    56    55    88    99     + h2 `) M7 D9 [7 h9 j
        24    36    27    63    50    80    90; ! N( R, H8 E3 s
    ENDDATA
      ~7 f1 }3 v6 K% O' O# N2 CEND . d$ b  d5 h( V5 z1 i
    求解可以得到: ,其它变量为 0(最小总损失仍为 335)。也就是说,消防站 1 应向火警地点 2 派 2 辆车,向火警地点 3 派 1 辆车;消防站 2 应向火警地点 1 派 2 辆车;消防站 3 应向火警地点 3 派 2 辆车。经过检 验可以发现,此时的派车方案是合理的。
    % [! F- y1 S2 Z7 p9 C————————————————
    . U/ B" r3 c2 b  N5 j$ m版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。6 z6 ~+ C5 b+ s+ I
    原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89388172
      u; Q0 j/ n/ P6 ~& l' a6 K' O; N0 Z- b- {7 K4 w
    2 n% P  a# K. P: O
    / F  L( j+ n7 b6 ~# v( n, n: c( C
    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-8-18 05:23 , Processed in 0.631035 second(s), 51 queries .

    回顶部