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

浅夏110

问题描述： 某市消防中心同时接到了三处火警电话。根据当前的火势，三处火警地点分 别需要 2 辆、2 辆和 3 辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记  为第 j 辆消防车到达火警地点i的时间，则三处火警地点的损失分别为


7 K/ W7 B7 y- X$ V0 i, O0 M3 [   ; 。目前可供消防中心调度的消防车正好有 7辆，分别属于三个消防站（可用消防车数量分别为 3 辆、2 辆、2 辆）。消防车从三个消 防站到三个火警地点所需要的时间如表 6 所示。应如何调度消防车，才能使总损失最 小？

7 |2 ]7 B3 `4 t5 I
) u# P1 v' B! _8 {+ A4 b; {
问题二：如果三处火警地点的损失分别为 ；，调度方案是否需要改变？
6 S& |- j" Y- a, G- W" y# I
+ y& w' P8 K- o/ _" f- N2 b  \

- R( S' S" b" ?  s（1）问题分析
# _4 n: G) s3 z  v6 c
0 n0 T; j0 F4 L: ]5 k2 H1 w/ ?- ~本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。

  X3 `9 a  A& b4 G（2）决策变量
/ L$ l3 I6 `: c8 g8 T
为了用运输问题建模求解，我们很自然地把 3 个消防站看成供应点。如果直接把 3 个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因此难以确 定损失的大小。下面我们把 7 辆车的需求分别看成 7 个需求点（分别对应于到达时间 . 用   表示消防站i是否向第 j 个需求点派车（1 表示派车，0表示不派车），则共有 21 个  0−1 变量.

（3）模型建立
8 H5 \  P6 j. D1 P
题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简 单的计算可知，如果消防站 1 向第 6 个需求点派车（即消防站 1 向火警地点 3 派车但该 消防车是到达火警地点 3 的第二辆车），则由此引起的损失为 72 98 = × 。同理计算，可以得到损失矩阵如表 7 所示（元素分别记为 ）。
* ?  O, _& }/ M, o- V0 ^+ V




% Y& S5 J0 G! h- _: T
  Q0 d! N* L9 N/ h于是，使总损失最小的决策目标为
9 O: z# {. ^9 o4 q* {
/ I6 P, y  n0 c( J5 G; n2 u                     ( 1 )
9 w; ?/ d0 r  Y6 s
' S& }9 B" G8 ~3 `约束条件：
5 V6 w9 }* B/ R/ ^- S( ^
约束条件有两类，一类是消防站拥有的消防车的数量限制，另一类是 各需求点对消防车的需求量限制。
记   （ i=1,2,3 ）为第i个消防站拥有消防车的数量，则消防站拥有的消防车的数量限制可以表示为
3 \0 M4 U+ X: V* n% s4 g                        (  2 )

6 \' C, o# {4 E3 E9 O各需求点对消防车的需求量限制可以表示为

9 H; I- f5 w8 v/ O! O0 [9 `  w0 U           (  3 )
( ]6 ^* a: U) }1 c) ]
（4）模型求解 的lingo代码
% F5 `7 c$ [- r) X/ ^# F
6 K8 S( X" \/ I2 d0 e* k  SMODEL:
TITLE 消防车问题;
SETS:
supply/1..3/:b;
$ [9 x; d* Q9 s; Gneed/1..7/;
% Q$ Y  m& @+ q8 \: [& rlinks(supply,need):c,x;
) G- S. K, P4 r) |# z/ IENDSETS
( ]" g1 G9 P4 b. |" i[OBJ]Min=@sum(links:c*x);
@FOR(supply(i):@sum(need(j):x(i,j))=b(i));
@FOR(need(j):@sum(supply(i):x(i,j))=1);
  i. X/ z) b7 T# s5 ~1 @" eDATA:
+ Z# Y) g% ?, \$ J1 Ib=3,2,2;
, s$ v- v8 ], P4 ?c=36,24,49,21,81,72,45   
& }; s# a. X5 a0 j! t" k    30,20,56,24,99,88,55   
5 N1 `' g: w- J    36,24,63,27,90,80,50;
- V: @1 k: g2 W0 P0 rENDDATA
END
+ `! ?, Q  d$ k求得结果为，消防站 1 应向火警地点 2 派 1 辆车，向火警地点 3 派 2 辆车；消防站 2 应向火警地点 1 派 2 辆车；消防站 3 应向火警地点 2、3 各派 1 辆车。最小总损失 为 329。

, x8 W1 d1 T- T# X* P7 r) s8 g. B* Z（5）讨论

1）这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看做需求点，消防站看做供应点。在上面模型中，我们虽然假设   为 0− 1变量，但求解时是采用线性规划求解的，也就是说没有加上 为 0− 1 变量或整数变量的限制条件，但求解得到的结果中   正好是 0−1 变量。这一结果不是偶然的，而是运输问题特有的一种性质.
% T+ a: B. m& L
" w) h2 h* f( G) w/ D+ L; R2 ）在上面模型中，没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束，这一结果不是必然的，而只是巧合。如对例题后半部 分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵如表 8 所示（所示（元素仍然分别记为 )
" U( u- v8 Q: B* e3 o


此时重新将式（ 1 )-( 3 ) 构成的线性规划模型输入 LINGO 求解，可以得到新的最优解： 其它变量为 0（最小总损失仍为 329）
8 ^7 u) Q/ F/ I! P! y$ K
实际上，损失矩阵中只是 1、2 列交换了位置，3、4 列交换了位置，5、7 列 交换了位置，因此不用重新求解就可以直接看出以上新的最优解。

- V1 `# b. t8 O# y但是，以上新的最优解却是不符合实际情况的。例如，  表明火警地点2 的第一辆消防车来自消防站 3，第二辆消防车来自消防站 1，但这是不合理的，因为 火警地点 2 与消费站 3 有 9min 的距离，大于与消防站 1 的 7min 的距离。分配给火警 地点 3 的消防车也有类似的不合理问题。为了解决这一问题，我们必须考虑消防车到达 各火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约 束，以保证以上的不合理问题不再出现。

首先考虑火警地点 2。由于消防站 1 的消防车到达所需时间（7min）小于消防站 2 的消防车到达所需时间（8 分钟），并都小于消防站 3 的消防车到达所需时间（9 分钟）， 因此火警地点 2 的第二辆消防车如果来自消防站 1，则火警地点 2 的第 1 辆消防车也一 定来自消防站 1；火警地点 2 的第 2 辆消防车如果来自消防站 2，则火警地点 2 的第 1 辆消防车一定来自消防站 1 或 2。因此，必须增加以下约束：   (  4 )
( ]* v" E3 C) V) \+ v7 e
- A6 x6 c$ k& w同理，对火警地点 1，必须增加以下约束:    (  5 )
* ^" Q8 L/ X- ?! ], `
: y6 b) K- h, ]( r) b4 t- m7 K  K对火警地点 3，必须增加以下约束:     ( 6 )
6 Y' M6 X1 I# Y4 U) q$ j# e" t$ u
0 l4 S8 _- p2 r5 ?重新将式（1）～（6）构成的整数规划模型（   是 1 0− 变量）输入 LINGO 软件如下:
( }0 L0 c: ^$ {$ H2 ?
MODEL:
3 A2 |/ N1 Z* s( `" HTITLE 消防车问题;
' P  z# I- u* n7 y2 i/ I7 _SETS:
# Z; M4 z  n  u, }) Jsupply/1..3/:b;
need/1..7/;
9 L! x7 X* G6 ~0 B  v0 O" \: nlinks(supply,need):c,x;
( f) e- v0 \' Z& p* M+ |ENDSETS
[OBJ]Min=@sum(links:c*x);
@FOR(supply(i):@sum(need(j):x(i,j))=b(i));
. F7 e6 i9 B7 f* |! r" ~" s@FOR(need(j):@sum(supply(i):x(i,j))=1);
- x( s+ R& B+ Wx(1,4)<x(1,3);
x(2,4)<x(1,3)+x(2,3);
) I% d& i5 ]! X. \! u, _$ lx(2,2)<x(2,1);
x(1,6)<x(1,5);
) l- l& I2 a' N0 b7 fx(1,7)<x(1,6);
: S: B! @3 l* m  _x(3,6)<x(1,5)+x(3,5);
, D- `# h; q; P) U$ x  g8 f2*x(3,7)<x(1,5)+x(1,6)+x(3,5)+x(3,6);
! p3 E  t$ U- b- g@for(links:@bin(x));
! V' j+ w' G/ ZDATA:
b=3,2,2;
c=  24    36    21    49    45    72    81     
    20    30    24    56    55    88    99     
% V; E( E+ L; ]+ h' M+ t    24    36    27    63    50    80    90;
9 n; Y1 X5 L' a, `8 K7 uENDDATA
END
7 s) z+ f: l# O- x1 z( G6 x求解可以得到： ，其它变量为 0（最小总损失仍为 335）。也就是说，消防站 1 应向火警地点 2 派 2 辆车，向火警地点 3 派 1 辆车；消防站 2 应向火警地点 1 派 2 辆车；消防站 3 应向火警地点 3 派 2 辆车。经过检 验可以发现，此时的派车方案是合理的。
————————————————
9 N9 ^# I/ O% t* V版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, w+ u$ {! q: l+ F2 H+ Y* t原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89388172
3 V3 c4 k7 {) ]2 V
* {- T, {: T) `
% n4 H6 E" A" Q. v  ^