超速行駛問題
摘要
本文主要研究的是探討驅車從始發地至目的地的最短時間路徑問題和最少花費問題，以及在超速情況下的最短時間和最少花費問題。
首先，從整個題目的兩個問題入手，發現兩個問題都是優化問題，具有一定
的聯系。然后針對第一問， 本文建立了 0-1 規劃的優化模型， 根據模型的約束條
件及矩陣的含義進行編程，找出所有可能出現的路徑，每種路徑對應兩個 0-1 矩陣，分別表示橫向路線和縱向路線， 再將兩個矩陣分別點乘橫向路線與縱向路
9
9
線所表示的時間矩陣， 從而由目標函數 Z
min
( X ij
Yij ) 利用計算機得出最
i
0 i 0
優解 17.78
小時，并找出時間最短的路線為：
a00
a01
a02
a03
a13
a14a15
a25
a35a45
a55a56 a57
a58
a68
a78
a88
a89
a99
然后，對于花費最少問題，本文建立了在每段公路上費用與速度的關系式，根據求極小值， 找出每段公路花費最少時的速度， 從而可計算每段公路的花費最少的金額，再根據時間最短路線的算法，給每段公路賦值(最少花費) ，可得最優解為 274.64 元，其中一條花費最少的路線為：
a00
a01
a11a21
a31
a41a51
a52
a62
a72
a82
a92
a93
a94
a95
a96
a97
a98
a99
最后，考慮到罰款問題， 本文建立了汽車超速百分比分別與被探測可能性和罰款金額的線性關系式， 以及每段公路超速罰款金額的期望值與超速百分比的線
性關系式，并假設在整個路線中的速度保持不變，
即可計算得出每段公路在最小
速度的條件下的花費(包括罰款)，再利用問題一的 0-1
規劃模型算出汽車在
0.8T
時間內到達 B 城最少的花費為 524.99
元，找出該路線為：
a00
a01
a11
a12
a22
a32
a42a52
a53
a54a55 a56
a57
a58
a68
a78
a88
a89
a99
在所得結果的基礎上， 我們再次進行模型的修改與優化， 并能將此題的解法應用于車輛監控導航系統中。
關鍵詞： 0-1 規劃最優化線性關系極小值概率期望
一、問題重述
你驅車從 A 城趕往 B 城。 A 城和 B 城間的道路如下圖所示， A 在左下角， B 在右上角，橫向縱向各有 10 條公路，任意兩個相鄰的十字路口距離為 100 公里，所以 A 城到 B 城相距 1800 公里。任意相鄰的十字路口間的一段公路 ( 以下簡稱路
段 ) 都有限速，標注在圖上， 單位為公里每小時。 標注為 130 的路段是高速路段，每段收費 3 元。
整個旅途上的費用有如下兩類。 第一類與花費時間相關， 如住店和飲食， 由公式 c1=5t; 給出， t 單位為小時。 第二類是汽車的油費， 每百公里油量 ( 升) 由公
式 c2=av+b; 給出，其中 a=0.0625，b=1.875,v 的單位為公里 / 每小時。汽油價格為每升 1.3 元。
請建立數學模型，解決以下問題：
若你遵守所有的限速規定，那么時間最短的路線和花費最少的路線分別
是哪一條？
為了防止超速行駛， 交警放置了一些固定雷達在某些路段上， 如圖上紅色的路段。另外，他們放置了 20 個移動雷達。 這些雷達等概率地出現在各個路段，
你可能在一個路段同時發現多個雷達，也可能在裝有固定雷達的路段發現移動雷
達。每個雷達都監控了自身所在的整個路段。如果你超速 10%，則你有 70%的可能被雷達探測到，且會被罰款 100 元；如果你超速 50%，你有 90%的可能被雷達
探測到，且會被罰款200 元。
假設 T 是遵守所有限速規定所花的最少時間，但你有急事想在0.8T 時間內
趕往 B 城，那么包括罰款在內最少花費多少？路線又是哪一條？
二、問題分析
本題是一個對選擇路線的優化問題， 需要對每段路線的最短時間及最少費用的最佳速度進行分析，并找出它們的聯系。
對于問題一，若要找出時間最短的路線， 必須知道車在每段公路不超速的前提下的最少時間， 將每段公路行駛的最短時間作為此公路的權值， 并且必須限定車的行駛方向為向右或向上，因此車最少需經過 18 條公路，在此基礎上，我們建立 0-1 規劃模型，建立以路線的最少時間為目標函數， 以汽車行駛方向和經過的公路總數建立約束條件， 然后設計可行程序， 尋找時間最短路線， 并依據目標函數計算出最短時間。 對于第一問中的花費最少的路徑， 我們只需計算在每條公路上的最少花費， 而花費與時間和油量相關， 而時間和油量都與速度相關， 因此我們只需建立一個以速度為自變量和以花費為因變量的函數關系式， 利用求極小值的方法求出每段路上最少花費對應的速度，再計算出每段路對應的最少
