1、模型實(shí)例-紅綠燈調(diào)節(jié)問題問題的背景及提出在車輛擁擠的交叉路口，需要合理地調(diào)節(jié)各車道安置的紅綠燈，使車輛能夠順利、有效地通過。首先應(yīng)使各道都的車輛互不沖突地順利駛過路口，其次希望效能盡量地高，試制定合適的方案。假設(shè)1 我們以一個(gè)十字路口為例，含有六個(gè)交通流，見圖7-1。2 車輛在經(jīng)過路口時(shí)勻速，在先后兩個(gè)綠燈交替時(shí)，兩個(gè)交通流不互相沖突。3 盡量使多個(gè)交通流同時(shí)使用綠燈，和同時(shí)使用地交通流稱為相容的。4 六個(gè)交通流的紅綠燈的調(diào)節(jié)是周期性的，譬如60秒。5 直行和轉(zhuǎn)彎車輛的數(shù)量比為1：2。6 每個(gè)交通流至少使用綠燈時(shí)間10秒。7 以各交通流總的綠燈時(shí)間作為衡量紅綠燈調(diào)節(jié)優(yōu)劣的指標(biāo)。模型建立設(shè)圖g，

2、f：v實(shí)軸上的開區(qū)間集，令f(v)j(v)。若v和u相鄰當(dāng)且僅當(dāng)j(v)和j(u)相交，則稱g是區(qū)間圖。由假設(shè)4，我們先在一個(gè)周期時(shí)間段上解決問題。取時(shí)間軸上0到60秒這段區(qū)間，記為i，i上的子區(qū)間稱為時(shí)段。我們進(jìn)行紅綠燈調(diào)節(jié)實(shí)際上是建立一個(gè)交通流到i上時(shí)段的函數(shù)j，即把i分成若干時(shí)段，將這些時(shí)段作為綠燈時(shí)間分配給各交通流，使之滿足假設(shè)3、5、6、7。故我們可以利用圖論中的區(qū)間圖來解決。下面把此問題用圖來表示。我們研究的主要問題是交通流的紅綠燈的使用問題，即交通流之間是否可以同時(shí)使用綠燈(相容)。故我們按下面準(zhǔn)則建立圖：每個(gè)交通流用一個(gè)頂表示，v=a，b，c，d，e，f；當(dāng)兩個(gè)交通流是相容的，

3、它們對(duì)應(yīng)的頂之間連一條邊，這樣得到的圖稱為交通流的相容圖，見圖7-2。發(fā)現(xiàn)圖7-2交通流相容圖不是區(qū)間圖，即c和d、d和e、e和f、f和c同時(shí)使用綠燈，c和e、d和f不同時(shí)使用綠燈是做不到的。又由于相容的交通流可以不必同時(shí)使用綠燈，為此，可刪除某一條邊，使之子圖為一個(gè)區(qū)間圖，例如刪除邊cf。得到圖7-3：子圖hef及其 對(duì)應(yīng)函數(shù)j。為使在子圖hef條件下，得到總的最長(zhǎng)綠燈時(shí)間方案，將60秒時(shí)間段i劃分為d1，d2，d3，d44個(gè)時(shí)段，設(shè)定函數(shù)j：j(a)，j(b)，j(c)，j(d)，j(e)，j(f)，如圖7-4：與子圖hcf相應(yīng)的方案。下面的問題時(shí)確定d1，d2，d3，d4使之滿足假設(shè)7。問題轉(zhuǎn)化為線性規(guī)劃問題。maxr1(2 d1+2d2+d3)+2( d3+2d4)s.t. d1+d2+d3+d4=60 d110 d210 d310 d410此規(guī)劃的解是對(duì)應(yīng)子圖hcf的最有效方案。最后分別打開其它邊得到所有