QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3296|回复: 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的时间,则三处火警地点的损失分别为
    9 N! b/ ^( ^& Y$ [  b4 P# g5 e0 W' v. M' ~" K/ k- W
    0 e+ K6 m# }4 ~" f# f, Z
       ; 。目前可供消防中心调度的消防车正好有 7辆,分别属于三个消防站(可用消防车数量分别为 3 辆、2 辆、2 辆)。消防车从三个消 防站到三个火警地点所需要的时间如表 6 所示。应如何调度消防车,才能使总损失最 小?
      F3 q' [/ v0 p
    # g0 M2 E& |* c8 A0 w( I2 U& ?0 J4 ^8 \1 N2 j
    6 P3 X5 Y3 T5 h% [" X
    问题二:如果三处火警地点的损失分别为 ;,调度方案是否需要改变?
    0 z  L9 T1 x+ O/ o4 }5 G6 A; F, w- O9 Y, r" s

    ; I2 _( U: Z& P0 @/ n4 q6 O" \/ j+ Z- I0 U( u, ?
    (1)问题分析
      J$ c& p/ F- t; K% b7 n8 p  }+ h
    + u8 ^5 [/ d8 ]* I本题考虑的是为每个火警地点分配消防车的问题,初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形,我们下面首先把它变成一个运输问题建模求解。2 w$ z' K8 k) a0 N: r
    9 ?' p' @4 a1 ?
    (2)决策变量0 S; C& l( A  b  a) Y
    ; u- c) o3 M$ \4 I0 _
    为了用运输问题建模求解,我们很自然地把 3 个消防站看成供应点。如果直接把 3 个火警地点看成需求点,我们却不能很方便地描述消防车到达的先后次序,因此难以确 定损失的大小。下面我们把 7 辆车的需求分别看成 7 个需求点(分别对应于到达时间 . 用   表示消防站i是否向第 j 个需求点派车(1 表示派车,0表示不派车),则共有 21 个  0−1 变量.
      r: L# V. C  c# F* R
      {, [, c4 ]8 Z* H" G(3)模型建立9 T$ W% H  U3 u3 \

      c' m; y  a/ W题目中给出的损失函数都是消防车到达时间的线性函数,所以由所给数据进行简 单的计算可知,如果消防站 1 向第 6 个需求点派车(即消防站 1 向火警地点 3 派车但该 消防车是到达火警地点 3 的第二辆车),则由此引起的损失为 72 98 = × 。同理计算,可以得到损失矩阵如表 7 所示(元素分别记为 )。
    ' Y3 {7 R, v* I9 L9 d- {( q: `4 g( l$ s5 L. F
    ( O5 W. @- j6 Y: I

    # ~/ @; b' g, Q
      d/ F) `8 x3 [0 i! h
    , A3 o' f  Y' v% @2 P
    % R* e1 P0 ?. d6 y; C3 W4 W于是,使总损失最小的决策目标为. E  {3 M0 w% Y0 S% W- E* m  m

    0 r0 a4 F+ P: h1 G* O1 T( a: V                     ( 1 )" Q- M9 A! O& i3 `

    & k) L3 m% Q' X2 Q约束条件:8 g# O, @* U3 n

    * _" K& x* E  E约束条件有两类,一类是消防站拥有的消防车的数量限制,另一类是 各需求点对消防车的需求量限制。 9 G+ e2 P) G8 T+ \8 _0 i9 v4 E) g
    记   ( i=1,2,3 )为第i个消防站拥有消防车的数量,则消防站拥有的消防车的数量限制可以表示为
    - }+ {& {* F# L% F' N" J+ J                        (  2 )- c. m& a$ f4 j8 }; r7 ^
    " d  T$ O3 \/ x4 @- m& B3 T7 q4 ~
    各需求点对消防车的需求量限制可以表示为 3 E! O' \2 u3 q6 e- U6 ]$ d; u( \

    ) O# k3 r& b, i6 E1 f           (  3 )
    $ V6 Z( Z) G* ~8 B3 Q9 ?; \) r
    (4)模型求解 的lingo代码
    6 N- p# [( U4 J, t; L& V4 p5 {8 l6 l  N- S& J8 S4 S
    MODEL: 2 ~; E/ ~4 R2 Q! S, \6 ~# Z0 Q
    TITLE 消防车问题; 8 o& ^: ^  r" \: u: v, j  ?
    SETS:
    / ?- H9 G8 S( E- d$ xsupply/1..3/:b;
    $ j1 u" k  ^! bneed/1..7/;
    , n) t) L) D* r6 n7 D" f$ m' dlinks(supply,need):c,x; 9 d' D: F$ E5 e" v
    ENDSETS
    $ G& T: P! O5 q' L1 `[OBJ]Min=@sum(links:c*x);
    5 T, h- B- ~4 {9 |* F@FOR(supply(i):@sum(need(j):x(i,j))=b(i));
    ; n0 {  W! [+ ^0 R0 F- D  o@FOR(need(j):@sum(supply(i):x(i,j))=1); $ R! H  B; @5 F$ {* r6 C
    DATA: 3 C+ @) L2 t" o% Q& j1 j
    b=3,2,2;
    ' I# [/ [% ~) W, L' l5 K. `c=36,24,49,21,81,72,45   
    ) \* `& D, D& u% C    30,20,56,24,99,88,55   0 [0 _* X2 Z9 r
        36,24,63,27,90,80,50; + m5 D8 S# a* p  Q
    ENDDATA
    3 C- |; Z! Y" B4 zEND ' r; `- X1 E) q" ~' G
    求得结果为,消防站 1 应向火警地点 2 派 1 辆车,向火警地点 3 派 2 辆车;消防站 2 应向火警地点 1 派 2 辆车;消防站 3 应向火警地点 2、3 各派 1 辆车。最小总损失 为 329。
    " I" h0 l4 g! G, V1 j- k9 p  ~& M& ]
    (5)讨论* N  K' L0 V  n1 u

    : ~/ W, D' s! e  Q6 x1)这个问题本质上仍然和经典的运输问题类似,可以把每辆车到达火场看做需求点,消防站看做供应点。在上面模型中,我们虽然假设   为 0− 1变量,但求解时是采用线性规划求解的,也就是说没有加上 为 0− 1 变量或整数变量的限制条件,但求解得到的结果中   正好是 0−1 变量。这一结果不是偶然的,而是运输问题特有的一种性质.
    : G6 N; U. C. e' G" T! ]$ m6 X$ R+ ~% l( s1 i
    2 )在上面模型中,没有考虑消防车到达各火警地点的先后次序约束,但得到的结果正好满足所有的先后次序约束,这一结果不是必然的,而只是巧合。如对例题后半部 分的情形,结果就不是这样了。显然,此时只需要修改损失矩阵如表 8 所示(所示(元素仍然分别记为 )- d# |7 B9 _- i( ^  b$ i
    9 B. s+ Z# {* c5 O3 k
    6 i5 @9 I9 @! T- y( N

    6 z6 }# j1 l: q- @; T. ^此时重新将式( 1 )-( 3 ) 构成的线性规划模型输入 LINGO 求解,可以得到新的最优解: 其它变量为 0(最小总损失仍为 329)% Z3 H0 _6 M: k

    6 d0 Q3 Z4 N5 }* r5 r实际上,损失矩阵中只是 1、2 列交换了位置,3、4 列交换了位置,5、7 列 交换了位置,因此不用重新求解就可以直接看出以上新的最优解。 8 Y8 J1 N" J- }6 R/ O# O' C

    - ^+ c/ L' r/ W5 {7 y但是,以上新的最优解却是不符合实际情况的。例如,  表明火警地点2 的第一辆消防车来自消防站 3,第二辆消防车来自消防站 1,但这是不合理的,因为 火警地点 2 与消费站 3 有 9min 的距离,大于与消防站 1 的 7min 的距离。分配给火警 地点 3 的消防车也有类似的不合理问题。为了解决这一问题,我们必须考虑消防车到达 各火警地点的先后次序约束,也就是说必须在简单的运输问题模型中增加一些新的约 束,以保证以上的不合理问题不再出现。
    - z/ {9 _; @" {/ n) |7 R0 n
    + D% f2 g5 Z& f* \9 f首先考虑火警地点 2。由于消防站 1 的消防车到达所需时间(7min)小于消防站 2 的消防车到达所需时间(8 分钟),并都小于消防站 3 的消防车到达所需时间(9 分钟), 因此火警地点 2 的第二辆消防车如果来自消防站 1,则火警地点 2 的第 1 辆消防车也一 定来自消防站 1;火警地点 2 的第 2 辆消防车如果来自消防站 2,则火警地点 2 的第 1 辆消防车一定来自消防站 1 或 2。因此,必须增加以下约束:   (  4 )
    & y) f5 k: Z' o* p
    + H3 X/ K+ r$ C- W2 v同理,对火警地点 1,必须增加以下约束:    (  5 )! R: r& _& O3 J& X5 d7 M

    % a) B' n: {# M! W$ g9 n$ M! R% x对火警地点 3,必须增加以下约束:     ( 6 )# X4 ~, N- V5 V7 ~

    9 [+ h6 n8 d+ }$ L; i' v重新将式(1)~(6)构成的整数规划模型(   是 1 0− 变量)输入 LINGO 软件如下:
    / k' y9 K0 ?4 s1 ]/ k& E3 @: p$ y# @5 m, F
    MODEL: / P& E1 P$ \% p
    TITLE 消防车问题;
    ! G( a* _5 v, t6 h! v3 M' ?5 rSETS:
    - t6 a' ~( J: B) L) }; q, ?  psupply/1..3/:b; ; l5 g9 p! o, P# l& I# k$ y
    need/1..7/;
    5 r4 F' m! y$ L! J6 F: `links(supply,need):c,x;
    . U7 R; a! m3 `% q7 i/ D4 }ENDSETS
    + s# N: ~* j. S; `# u3 A+ Y[OBJ]Min=@sum(links:c*x);
    9 l: s4 O5 G* e@FOR(supply(i):@sum(need(j):x(i,j))=b(i)); + e) ?3 ^0 ]2 b0 ?
    @FOR(need(j):@sum(supply(i):x(i,j))=1); ' A- e4 ?* m9 _' F, X0 `
    x(1,4)<x(1,3); # d0 Y+ G4 p4 I6 k+ j+ C1 p& x3 F
    x(2,4)<x(1,3)+x(2,3);
    4 k- g% d" }, a9 c6 mx(2,2)<x(2,1);
    ( N+ m) {, m; Y1 n$ ~6 O9 k  bx(1,6)<x(1,5);
    8 b6 l# e% c( tx(1,7)<x(1,6); ( G( {* B7 A7 f' i% n$ x
    x(3,6)<x(1,5)+x(3,5);
    % N% p0 `; Q* v; ~/ ~' F, W2*x(3,7)<x(1,5)+x(1,6)+x(3,5)+x(3,6);
    + R0 N* W9 y0 r* S@for(links:@bin(x)); + }8 }" {/ c0 W. Q: u
    DATA:+ W8 v* j# _% i0 K; s+ h, W: n$ L
    b=3,2,2;
    / F# ^' \9 S. B/ X# ]( c% wc=  24    36    21    49    45    72    81     % w, d# @0 D1 e% v2 b
        20    30    24    56    55    88    99     * @" G# n9 U/ X, s
        24    36    27    63    50    80    90;
    8 h8 O7 l! b3 Q- s5 V7 jENDDATA
    / {% o1 @  w! L4 W! ~END
    & S* @# q! _+ F7 r1 |7 H% p求解可以得到: ,其它变量为 0(最小总损失仍为 335)。也就是说,消防站 1 应向火警地点 2 派 2 辆车,向火警地点 3 派 1 辆车;消防站 2 应向火警地点 1 派 2 辆车;消防站 3 应向火警地点 3 派 2 辆车。经过检 验可以发现,此时的派车方案是合理的。 ' q8 y" H* y4 O- S$ D$ s/ }
    ————————————————# d7 Q( t: s7 q# c
    版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    7 N0 t2 k5 E8 x5 V1 r原文链接:https://blog.csdn.net/qq_29831163/java/article/details/89388172/ b6 j# M8 \; d( m! n8 o
    - M" H7 x1 L% r4 z
    9 x2 ^; T6 v: d' w7 ^. e

    % q2 P0 o2 o0 f& |+ q
    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-1 21:00 , Processed in 0.761225 second(s), 50 queries .

    回顶部