1、消防車調度問題消防車調度問題 如果三處火警地點的損失分別為如果三處火警地點的損失分別為:4t11+6t12，3t21+7t22，5t31+8t32+9t33，調度方案是否需要改變？調度方案是否需要改變？消防站到三個火警地點所需要的時間消防站到三個火警地點所需要的時間時間時間(分鐘分鐘) 火警地點火警地點1火警地點火警地點2火警地點火警地點3消防站消防站1679消防站消防站25811消防站消防站36910 問題分析問題分析 本題考慮的是為每個火警地點分配消防車的問本題考慮的是為每個火警地點分配消防車的問題，初步看來與線性規劃中經典的運輸問題有些類似。題，初步看來與線性規劃中經典的運輸問題有些類似

2、。本題的問題可以看成是指派問題和運輸問題的一種變本題的問題可以看成是指派問題和運輸問題的一種變形，我們下面首先把它變成一個運輸問題建模求解。形，我們下面首先把它變成一個運輸問題建模求解。 決策變量決策變量 為了用運輸問題建模求解，很自然地把為了用運輸問題建模求解，很自然地把3個消防個消防站看成供應點。如果直接把站看成供應點。如果直接把3個火警地點看成需求點，個火警地點看成需求點，我們卻不能很方便地描述消防車到達的先后次序，因我們卻不能很方便地描述消防車到達的先后次序，因此難以確定損失的大小。下面我們把此難以確定損失的大小。下面我們把7輛車的需求分輛車的需求分別看成別看成7個需求點個需求點(分別

3、對應于到達時間分別對應于到達時間t11, t12, t21, t22, t31, t32, t33)。用。用xi j表示消防站表示消防站i是否向第是否向第j個需求點派車個需求點派車(1表示派車，表示派車，0表示不派車表示不派車)，則共有，則共有21個個0-1變量。變量。 決策目標決策目標 題目中給出的損失函數都是消防車到達時間的線題目中給出的損失函數都是消防車到達時間的線性函數，所以由所給數據進行簡單的計算可知，如果性函數，所以由所給數據進行簡單的計算可知，如果消防站消防站1向第向第6個需求點派車個需求點派車(即消防站即消防站1向火警地點向火警地點3派車但該消防車是到達火警地點派車但該消防車是

4、到達火警地點3的第二輛車的第二輛車)，則由，則由此引起的損失為此引起的損失為8*9=72。同理計算，可以得到損失矩。同理計算，可以得到損失矩陣陣(元素分別記為元素分別記為ci j)。 ci j火警地點火警地點1火警地點火警地點2火警地點火警地點3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=136244921817245消防站消防站i=230205624998855消防站消防站i=336246327908050于是，使總損失最小的決策目標為于是，使總損失最小的決策目標為 7131minjijiijxcz 約束條件約束條件 約束條件有兩類：一類是消防站擁有約束條件有兩類：一類是消防站

5、擁有的消防車的數量限制，另一類是各需求點對消防車的的消防車的數量限制，另一類是各需求點對消防車的需求量限制。需求量限制。 消防站擁有的消防車的數量限制可以表示為消防站擁有的消防車的數量限制可以表示為 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27 =2 x31+x32+x33+x34+x35+x36+x37=2 各需求點對消防車的需求量限制可以表示為各需求點對消防車的需求量限制可以表示為 . 7 , 6 , 5 , 4 , 3 , 2 , 1, 131 jxiij模型求解模型求解 將如上構成的線性規劃模型輸入將如上構成的線性規

6、劃模型輸入lindo： ! 消防車問題消防車問題min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30 x21+20 x22+56x23+24x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90 x35+80 x36+50 x37 subject to x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x37 = 2 x11+x21+x31 =1 x12+x22+x32 =1 x1

7、3+x23+x33 = 1 x14+x24+x34 =1 x15+x25+x35 =1 x16+x26+x36 = 1 x17+x27+x37 = 1 end 求解得到如下結果：求解得到如下結果： objective function value 1) 329.0000variable value reduced cost x11 0.000000 10.000000 x12 0.000000 8.000000 x13 1.000000 0.000000 x14 0.000000 2.000000 x15 1.000000 0.000000 x16 1.000000 0.000000 x17

8、0.000000 3.000000 x21 1.000000 0.000000 x22 1.000000 0.000000 x23 0.000000 3.000000 x24 0.000000 1.000000 x25 0.000000 14.000000 x26 0.000000 12.000000 x27 0.000000 9.000000 variable value reduced cost x31 0.000000 2.000000 x32 0.000000 0.000000 x33 0.000000 6.000000 x34 1.000000 0.000000 x35 0.0000

9、00 1.000000 x36 0.000000 0.000000 x37 1.000000 0.000000 也就是說，消防站也就是說，消防站1應向火警地點應向火警地點2派派1輛車，向輛車，向火警地點火警地點3派派2輛車；消防站輛車；消防站2應向火警地點應向火警地點1派派2輛車；輛車；消防站消防站3應向火警地點應向火警地點2、3各派各派1輛車。最小總損失為輛車。最小總損失為329。 討論討論 1) 這個問題本質上仍然和經典的運輸問題類似，這個問題本質上仍然和經典的運輸問題類似，可以把每輛車到達火場看作需求點，消防站可作供應可以把每輛車到達火場看作需求點，消防站可作供應點。在上面模型中，我們雖

10、然假設點。在上面模型中，我們雖然假設xij為為0-1變量，但變量，但求解時是采用線性規劃求解的，也就是說沒有加上求解時是采用線性規劃求解的，也就是說沒有加上xij為為0-1變量或整數變量的限制條件，但求解得到的結變量或整數變量的限制條件，但求解得到的結果中果中xij正好是正好是0-1變量。這一結果不是偶然的，而是變量。這一結果不是偶然的，而是運輸問題特有的一種性質。運輸問題特有的一種性質。 2) 在上面模型中，我們沒有考慮消防車到達各火在上面模型中，我們沒有考慮消防車到達各火警地點的先后次序約束，但得到的結果正好滿足所有警地點的先后次序約束，但得到的結果正好滿足所有的先后次序約束。這一結果卻并

11、不總是必然的，而只的先后次序約束。這一結果卻并不總是必然的，而只是巧合。是巧合。 如對例題后半部分的情形，結果就不是這樣了。如對例題后半部分的情形，結果就不是這樣了。顯然，此時只需要修改損失矩陣顯然，此時只需要修改損失矩陣(元素仍然分別記為元素仍然分別記為cij)ci j火警地點火警地點1火警地點火警地點2火警地點火警地點3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=124362149457281消防站消防站i=220302456558899消防站消防站i=324362763508090 此時將重新構成的線性規劃模型輸入此時將重新構成的線性規劃模型輸入lindo求求解解, 可以得

12、到新的最優解可以得到新的最優解: x14=x16=x17=x21=x22=x33=x35=1其他變量為其他變量為0(最小總損失仍為最小總損失仍為329)。實際上。實際上, 損失矩損失矩陣中只是陣中只是1、2列交換了位置，列交換了位置，3、4列交換了位置，列交換了位置，5、7列交換了位置，因此不用重新求解就可以直接看出列交換了位置，因此不用重新求解就可以直接看出以上新的最優解。以上新的最優解。 但是，以上新的最優解卻是不符合實際情況的。但是，以上新的最優解卻是不符合實際情況的。例如，例如，x14=x33=1表明火警地點表明火警地點2的第一輛消防車來自的第一輛消防車來自消防站消防站3，第二輛消防車

13、來自消防站，第二輛消防車來自消防站1，但這是不合理，但這是不合理的，因為火警地點的，因為火警地點2與消防站與消防站3有有9分鐘的距離，大于分鐘的距離，大于與消防站與消防站1的的7分鐘的距離。分配給火警地點分鐘的距離。分配給火警地點3的消防的消防車也有類似的不合理問題。車也有類似的不合理問題。 為了解決這一問題，我們必須考慮消防車到達各為了解決這一問題，我們必須考慮消防車到達各火警地點的先后次序約束，也就是說必須在簡單的運火警地點的先后次序約束，也就是說必須在簡單的運輸問題模型中增加一些新的約束，以保證以上的不合輸問題模型中增加一些新的約束，以保證以上的不合理問題不再出現。理問題不再出現。 首先

14、考慮火警地點首先考慮火警地點2。由于消防站。由于消防站1的消防車到的消防車到達所需時間達所需時間(7分鐘分鐘)小于消防站小于消防站2的消防車到達所需時的消防車到達所需時間間(8分鐘分鐘)，并都小于消防站，并都小于消防站3的消防車到達所需時間的消防車到達所需時間(9分鐘分鐘)，因此火警地點，因此火警地點2的第的第2輛消防車如果來自消輛消防車如果來自消防站防站1，則火警地點，則火警地點2的第的第1輛消防車也一定來自消防輛消防車也一定來自消防站站1；火警地點；火警地點2的第的第2輛消防車如果來自消防站輛消防車如果來自消防站2，則，則火警地點火警地點2的第的第1輛消防車一定來自消防站輛消防車一定來自消

15、防站1或或2。因此，。因此，必須增加以下約束：必須增加以下約束：x14 x13x24 x13 +x23x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，對火警地點同理，對火警地點1，必須增加以下約束：，必須增加以下約束：x22 x21對火警地點對火警地點3，必須增加以下約束：，必須增加以下約束： 此時將重新構成的線性規劃模型輸入此時將重新構成的線性規劃模型輸入lindo軟軟件如下：件如下： ! 消防車調度消防車調度min 36x12+24x11+49x14+21x13+81x17+72x16+45x15 +30 x22+20 x21+56x24+

16、24x23+99x27+88x26+55x25 +36x32+24x31+63x34+27x33+90 x37+80 x36+50 x35 subject to x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x37 = 2 x11+x21+x31 = 1 x12+x22+x32 = 1 x13+x23+x33 = 1 x14+x24+x34 = 1 x15+x25+x35 = 1 x16+x26+x36 = 1 x17+x27+x37 = 1 x22 - x21 =

17、 0x14 - x13 =0x24 - x23 - x13 =0x16 - x15 = 0x17 - x16 =0x36 - x15 - x35 =02x37 -x15 -x16 -x35 -x36 =0end ! int 21 求解，可以得到新的解為：求解，可以得到新的解為： objective function value 1) 32.6667variable value reduced cost x12 0.000000 9.333333 x11 0.000000 7.333333 x14 1.000000 0.000000 x13 1.000000 0.000000 x17 0.333

18、333 0.000000 x16 0.333333 0.000000 x15 0.333333 0.000000 x22 1.000000 0.000000 x21 1.000000 0.000000 x24 0.000000 2.333333 x23 0.000000 1.000000 variable value reduced cost x27 0.000000 13.000000 x26 0.000000 12.000000 x25 0.000000 9.000000 x32 0.000000 2.000000 x31 0.000000 0.000000 x34 0.000000 5.333333 x33 0.000000 0.000000 x37 0.666667 0.000000 x36 0.666667 0.000000 x35 0.666667 0.000000 但是我們發現此時的解中但是我們發現此時的解中xij并不都是并不都是01變量或變量或整數變量，因此還是不符合題意。這是因為此時的模整數變量，因此還是不符合題意。這是因為此時的模型已經不再是型已經不再是“標準標準”的運輸模型，所以得到的解不的運輸模型，所以得到的解不一定自然地為正數解的緣故。所以我們還必須顯式地一定自然地為正數解