超速行駛問題

摘要

本文主要研究的是探討驅(qū)車從始發(fā)地至目的地的最短時(shí)間路徑問題和最少花費(fèi)問題，以及在超速情況下的最短時(shí)間和最少花費(fèi)問題。

首先，從整個(gè)題目的兩個(gè)問題入手，發(fā)現(xiàn)兩個(gè)問題都是優(yōu)化問題，具有一定

的聯(lián)系。然后針對(duì)第一問， 本文建立了 0-1 規(guī)劃的優(yōu)化模型， 根據(jù)模型的約束條

件及矩陣的含義進(jìn)行編程，找出所有可能出現(xiàn)的路徑，每種路徑對(duì)應(yīng)兩個(gè) 0-1 矩陣，分別表示橫向路線和縱向路線， 再將兩個(gè)矩陣分別點(diǎn)乘橫向路線與縱向路

9

9

線所表示的時(shí)間矩陣， 從而由目標(biāo)函數(shù) Z

min

( X ij

Yij ) 利用計(jì)算機(jī)得出最

i

0 i 0

優(yōu)解 17.78

小時(shí)，并找出時(shí)間最短的路線為：

a00

a01

a02

a03

a13

a14a15

a25

a35a45

a55a56 a57

a58

a68

a78

a88

a89

a99

然后，對(duì)于花費(fèi)最少問題，本文建立了在每段公路上費(fèi)用與速度的關(guān)系式，根據(jù)求極小值， 找出每段公路花費(fèi)最少時(shí)的速度， 從而可計(jì)算每段公路的花費(fèi)最少的金額，再根據(jù)時(shí)間最短路線的算法，給每段公路賦值(最少花費(fèi)) ，可得最優(yōu)解為 274.64 元，其中一條花費(fèi)最少的路線為：

a00

a01

a11a21

a31

a41a51

a52

a62

a72

a82

a92

a93

a94

a95

a96

a97

a98

a99

最后，考慮到罰款問題， 本文建立了汽車超速百分比分別與被探測(cè)可能性和罰款金額的線性關(guān)系式， 以及每段公路超速罰款金額的期望值與超速百分比的線

性關(guān)系式，并假設(shè)在整個(gè)路線中的速度保持不變，

即可計(jì)算得出每段公路在最小

速度的條件下的花費(fèi)(包括罰款)，再利用問題一的 0-1

規(guī)劃模型算出汽車在

0.8T

時(shí)間內(nèi)到達(dá) B 城最少的花費(fèi)為 524.99

元，找出該路線為：

a00

a01

a11

a12

a22

a32

a42a52

a53

a54a55 a56

a57

a58

a68

a78

a88

a89

a99

在所得結(jié)果的基礎(chǔ)上， 我們?cè)俅芜M(jìn)行模型的修改與優(yōu)化， 并能將此題的解法應(yīng)用于車輛監(jiān)控導(dǎo)航系統(tǒng)中。

關(guān)鍵詞： 0-1 規(guī)劃最優(yōu)化線性關(guān)系極小值概率期望

一、問題重述

你驅(qū)車從 A 城趕往 B 城。 A 城和 B 城間的道路如下圖所示， A 在左下角， B 在右上角，橫向縱向各有 10 條公路，任意兩個(gè)相鄰的十字路口距離為 100 公里，所以 A 城到 B 城相距 1800 公里。任意相鄰的十字路口間的一段公路 ( 以下簡(jiǎn)稱路

段 ) 都有限速，標(biāo)注在圖上， 單位為公里每小時(shí)。 標(biāo)注為 130 的路段是高速路段，每段收費(fèi) 3 元。

整個(gè)旅途上的費(fèi)用有如下兩類。 第一類與花費(fèi)時(shí)間相關(guān)， 如住店和飲食， 由公式 c1=5t; 給出， t 單位為小時(shí)。 第二類是汽車的油費(fèi)， 每百公里油量 ( 升) 由公

式 c2=av+b; 給出，其中 a=0.0625，b=1.875,v 的單位為公里 / 每小時(shí)。汽油價(jià)格為每升 1.3 元。

請(qǐng)建立數(shù)學(xué)模型，解決以下問題：

若你遵守所有的限速規(guī)定，那么時(shí)間最短的路線和花費(fèi)最少的路線分別

是哪一條？

為了防止超速行駛， 交警放置了一些固定雷達(dá)在某些路段上， 如圖上紅色的路段。另外，他們放置了 20 個(gè)移動(dòng)雷達(dá)。 這些雷達(dá)等概率地出現(xiàn)在各個(gè)路段，

你可能在一個(gè)路段同時(shí)發(fā)現(xiàn)多個(gè)雷達(dá)，也可能在裝有固定雷達(dá)的路段發(fā)現(xiàn)移動(dòng)雷

達(dá)。每個(gè)雷達(dá)都監(jiān)控了自身所在的整個(gè)路段。如果你超速 10%，則你有 70%的可能被雷達(dá)探測(cè)到，且會(huì)被罰款 100 元；如果你超速 50%，你有 90%的可能被雷達(dá)

探測(cè)到，且會(huì)被罰款200 元。

假設(shè) T 是遵守所有限速規(guī)定所花的最少時(shí)間，但你有急事想在0.8T 時(shí)間內(nèi)

趕往 B 城，那么包括罰款在內(nèi)最少花費(fèi)多少？路線又是哪一條？

二、問題分析

本題是一個(gè)對(duì)選擇路線的優(yōu)化問題， 需要對(duì)每段路線的最短時(shí)間及最少費(fèi)用的最佳速度進(jìn)行分析，并找出它們的聯(lián)系。

對(duì)于問題一，若要找出時(shí)間最短的路線， 必須知道車在每段公路不超速的前提下的最少時(shí)間， 將每段公路行駛的最短時(shí)間作為此公路的權(quán)值， 并且必須限定車的行駛方向?yàn)橄蛴一蛳蛏?#xff0c;因此車最少需經(jīng)過 18 條公路，在此基礎(chǔ)上，我們建立 0-1 規(guī)劃模型，建立以路線的最少時(shí)間為目標(biāo)函數(shù)， 以汽車行駛方向和經(jīng)過的公路總數(shù)建立約束條件， 然后設(shè)計(jì)可行程序， 尋找時(shí)間最短路線， 并依據(jù)目標(biāo)函數(shù)計(jì)算出最短時(shí)間。 對(duì)于第一問中的花費(fèi)最少的路徑， 我們只需計(jì)算在每條公路上的最少花費(fèi)， 而花費(fèi)與時(shí)間和油量相關(guān)， 而時(shí)間和油量都與速度相關(guān)， 因此我們只需建立一個(gè)以速度為自變量和以花費(fèi)為因變量的函數(shù)關(guān)系式， 利用求極小值的方法求出每段路上最少花費(fèi)對(duì)應(yīng)的速度，再計(jì)算出每段路對(duì)應(yīng)的最少

總結(jié)

以上是生活随笔為你收集整理的超速问题的c语言编程,超速行驶问题--精选.doc的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。