4模型與算法數(shù)學(xué)模型課件北郵

1、9.3 紅綠燈調(diào)節(jié)問(wèn)題：圖1所示的十字路口共有六條車道，其中是4條直道，是2條左轉(zhuǎn)彎道，每條車道設(shè)有紅綠燈，制定其調(diào)節(jié)方案。相容圖與區(qū)間圖相容圖：用圖中的頂點(diǎn)表示交通流，當(dāng)兩條交通流相容時(shí)將代表交通流的兩頂點(diǎn)連接而得到的圖。區(qū)間圖：稱圖G=（V，E）為區(qū)間圖，若存在從頂點(diǎn)到區(qū)間的對(duì)應(yīng)關(guān)系，使得對(duì)于任意的，有?？尚姓{(diào)節(jié)：通過(guò)刪除（非）區(qū)間圖某些邊，構(gòu)造一個(gè)區(qū)間圖子圖。有效性調(diào)節(jié)：對(duì)于給定的子圖所對(duì)應(yīng)的交通流，設(shè)計(jì)有效的紅綠燈調(diào)節(jié)程序（比方使在一個(gè)紅綠燈調(diào)節(jié)周期中總的綠燈時(shí)間最長(zhǎng)），盡可能利于路口的車輛通行。在要求滿足條件1）一個(gè)紅綠燈調(diào)節(jié)周期=60秒；2） 四個(gè)時(shí)段；3） 六個(gè)車流流量；4）每一

2、車流連續(xù)通行時(shí)間不少于10秒，可得如下線性規(guī)劃模型：滿足約束條件的任一均為其解；改進(jìn)的線性規(guī)劃模型：一個(gè)合理的調(diào)節(jié)方案應(yīng)當(dāng)使為每一車流分配的有效通行時(shí)間與它的實(shí)際流量相適應(yīng)，簡(jiǎn)言之，那些相對(duì)繁忙的車流應(yīng)當(dāng)有更為充足的通行時(shí)間，不妨設(shè)表示六個(gè)車流在單位時(shí)間內(nèi)的車流量，則得如下的改進(jìn)模型：適當(dāng)選取，使得，不難得到是相應(yīng)的最優(yōu)解；但若進(jìn)一步設(shè)想，適當(dāng)選取的另外一組值，使得，不難得到依舊是改變了的問(wèn)題的解這一現(xiàn)象事實(shí)上暴露了線性模型在處理紅綠燈調(diào)節(jié)問(wèn)題的缺陷，即盡管在改進(jìn)模型是在考慮了各個(gè)交通流流量的差異，但由于線性模型的特點(diǎn)使得這一改進(jìn)模型更為周全的考慮幾乎沒(méi)有發(fā)揮任何作用。它是在以滿足大多數(shù)車流最低通行時(shí)間要求為代價(jià)，將剩余的時(shí)間極端的滿足車流最繁忙的某一車流，而不管這種相對(duì)繁忙的具體程度。構(gòu)造一個(gè)合理的目標(biāo)函數(shù)：前面的論述說(shuō)明，用最優(yōu)化方法解決一個(gè)實(shí)際應(yīng)用問(wèn)題時(shí)，目標(biāo)函數(shù)的選擇是需要仔細(xì)推敲的。下面就紅綠燈調(diào)節(jié)問(wèn)題給出可供選擇的幾個(gè)目標(biāo)函數(shù)形式，當(dāng)然我們?nèi)糇屑?xì)分析，還會(huì)發(fā)現(xiàn)其中第一個(gè)目標(biāo)函數(shù)