關(guān)于大學(xué)生數(shù)學(xué)建模競(jìng)賽b題的簡(jiǎn)化研究

關(guān)于大學(xué)生數(shù)學(xué)建模競(jìng)賽b題的簡(jiǎn)化研究

1競(jìng)賽題內(nèi)容的簡(jiǎn)化2000年全國(guó)學(xué)生數(shù)學(xué)建模比賽b期的b問(wèn)題本質(zhì)上是一個(gè)交通問(wèn)題。運(yùn)輸問(wèn)題是社會(huì)經(jīng)濟(jì)生活中經(jīng)常出現(xiàn)的優(yōu)化問(wèn)題.由于實(shí)際問(wèn)題的多樣性,運(yùn)輸問(wèn)題的模型也是各種各樣的.往往涉及到優(yōu)化領(lǐng)域中的網(wǎng)絡(luò)優(yōu)化、線性規(guī)劃、二次規(guī)劃、0—1規(guī)劃等分支.有些運(yùn)輸問(wèn)題還涉及非線性規(guī)劃、隨機(jī)優(yōu)化、排隊(duì)論、時(shí)間表問(wèn)題、庫(kù)存問(wèn)題等運(yùn)籌學(xué)的諸多領(lǐng)域.最簡(jiǎn)單的運(yùn)輸問(wèn)題模型就是線性規(guī)劃中的標(biāo)準(zhǔn)運(yùn)輸問(wèn)題,用單純形法求解此類特殊問(wèn)題的具體實(shí)現(xiàn)就是表上作業(yè)法.它的存儲(chǔ)規(guī)模小、求解步驟簡(jiǎn)單,是實(shí)際中常常遇到的一類模型和方法.B題命題的主要?jiǎng)訖C(jī)是結(jié)合當(dāng)前西氣東輸工程的背景,讓參賽學(xué)生綜合運(yùn)用網(wǎng)絡(luò)優(yōu)化、線性規(guī)劃或二次規(guī)劃和整數(shù)規(guī)劃等方面的知識(shí),在建模與求解過(guò)程中靈活地發(fā)揮自身的能力.因此,題目具有一定的綜合性.但是考慮到競(jìng)賽只有三天,題目敘述不宜過(guò)長(zhǎng),數(shù)據(jù)不宜過(guò)多,競(jìng)賽題目對(duì)現(xiàn)實(shí)的問(wèn)題作了簡(jiǎn)化,主要體現(xiàn)在以下方面.1.輸氣管網(wǎng)簡(jiǎn)化為一條主管道(題目第一小題).這一簡(jiǎn)化使問(wèn)題看起來(lái)更明朗,便于學(xué)生思考.而這樣做又使建模不失代表性,和復(fù)雜的輸氣管網(wǎng)的建模方法與模型是一致的.在第三小題中管道是一個(gè)簡(jiǎn)單的樹形圖,它與第一小題的模型沒(méi)有多大區(qū)別.這一問(wèn)題可使學(xué)生了解到所建模型不僅適用于管道是一條線的情況.2.假定所用管道型號(hào)只有一種.現(xiàn)實(shí)問(wèn)題中管道各段的口徑未必相同,也就是說(shuō)管道網(wǎng)上用到幾種不同型號(hào)的鋼管.不同型號(hào)的鋼管價(jià)格不同、重量不同而引起運(yùn)費(fèi)不同,廠家選擇方面的約束也與鋼管型號(hào)有關(guān).這樣一來(lái)數(shù)據(jù)量變得巨大,模型的表達(dá)也變得復(fù)雜.題目中簡(jiǎn)化為管道是同一型號(hào)的,數(shù)學(xué)模型沒(méi)有本質(zhì)變化,減少了建模與求解中的敘述、表達(dá)、計(jì)算方面的繁瑣工作.3.鐵路只保留了與題目中管道施工最有關(guān)的的線路.聯(lián)結(jié)管道與鐵路的公路應(yīng)該是一個(gè)復(fù)雜的公路網(wǎng),題目盡可能簡(jiǎn)化到幾條直接從車站到管道施工線的公路段,因而鐵路上也只保留了十幾個(gè)車站.這樣,使與網(wǎng)絡(luò)最短路有關(guān)的計(jì)算量盡可能降低,甚至不用計(jì)算機(jī)也可能很快完成這部分工作.4.鐵路運(yùn)價(jià)和公路運(yùn)價(jià)加以簡(jiǎn)化,但保持了現(xiàn)實(shí)生活中的計(jì)價(jià)結(jié)構(gòu).鐵路運(yùn)價(jià)的分段計(jì)價(jià)檔次數(shù)減少很多,把管道長(zhǎng)度換算成噸位再計(jì)價(jià)的工作也省去(規(guī)定每km鋼管為一個(gè)單位).這樣簡(jiǎn)化雖然與現(xiàn)實(shí)相差較大,但保留了計(jì)價(jià)結(jié)構(gòu)的特征.由于作了上述簡(jiǎn)化,構(gòu)成了大學(xué)生能夠在三天內(nèi)完成的數(shù)學(xué)建模競(jìng)賽題.在命題過(guò)程中韓繼業(yè)先生和姜啟源先生等提出了寶貴的意見(jiàn),包括第二小題的增加,使得從競(jìng)賽中更能比較各參賽隊(duì)的水平、能力和發(fā)揮情況.2最短路優(yōu)化算法假設(shè)題目中鐵路、公路構(gòu)成的圖為G(V,E),V是所有火車站(含鋼廠)及管道結(jié)點(diǎn)A1,A2,…,An的集合,E是直接聯(lián)結(jié)這些結(jié)點(diǎn)的鐵路段和公路段的集合.鐵路部分構(gòu)成子圖G1(V1,E1),沿管道的公路構(gòu)成子圖G2(V2,E2),G2也是管道網(wǎng)的圖.題目中作為目標(biāo)函數(shù)的費(fèi)用包括購(gòu)買鋼管的費(fèi)用與運(yùn)輸費(fèi)用.其中購(gòu)買費(fèi)用只與向各鋼廠訂購(gòu)的數(shù)量有關(guān),與運(yùn)輸路線無(wú)關(guān).這一部分很容易處理,關(guān)鍵是運(yùn)費(fèi).要把鋼管從生產(chǎn)廠運(yùn)到施工沿線,根據(jù)鐵路網(wǎng)情況,必然要經(jīng)過(guò)管道上的結(jié)點(diǎn).例如在[Ai,Ai+1]之間的一段上,鋼管或者經(jīng)Ai或者經(jīng)Ai+1運(yùn)到施工處.因此,我們可以把運(yùn)費(fèi)分為從鋼廠到管道結(jié)點(diǎn)的運(yùn)費(fèi)和沿管道一段[Ai,Ai+1]內(nèi)的運(yùn)費(fèi)兩部分.我們就問(wèn)題3這種較一般的情形來(lái)敘述,問(wèn)題1只是問(wèn)題3的特例.引入以下記號(hào):m——鋼廠數(shù)n——G2的結(jié)點(diǎn)數(shù)cij——一個(gè)單位鋼管從Si到Aj的最小運(yùn)價(jià)tjk——圖G2中兩相鄰結(jié)點(diǎn)Aj與Ak之間的邊AjAk的邊長(zhǎng)(里程數(shù))Nj——圖G2中與Aj相鄰的結(jié)點(diǎn)Ak的下標(biāo)k的集合xij——從Si運(yùn)到Aj的運(yùn)量yik——Aj得到的鋼管沿邊AjAk向Ak方向運(yùn)送的里程數(shù)其中xjj,yjk是問(wèn)題的決策變量.首先要解決的問(wèn)題是確定cij,由于從Si到Aj可能既包括一段鐵路運(yùn)輸又包括一段公路運(yùn)輸,而兩種運(yùn)輸計(jì)價(jià)方式是不同的,因此需要分開處理.首先求各鋼廠到各火車站的最短里程,這是子圖G1(V1,E1)的里程網(wǎng)絡(luò)的典型的最短路問(wèn)題,可以用求最短路的Dijkstra算法或其它算法求解.對(duì)于象本題這樣的簡(jiǎn)單情況,直接就看出最短路.求出這一最短路程就可以根據(jù)鐵路運(yùn)價(jià)表得到每單位鋼管由各鋼廠到各火車站的最低運(yùn)費(fèi).如果公路網(wǎng)較復(fù)雜,利用公路網(wǎng)絡(luò)的最短路算法結(jié)合鋼廠到各火車站的最低運(yùn)費(fèi)就能算出由各鋼廠到管網(wǎng)結(jié)點(diǎn)Ai的單位運(yùn)費(fèi)cij.對(duì)于本題只有少量公路聯(lián)結(jié)鐵路網(wǎng)G1與公路網(wǎng)G2的情況,計(jì)算cij是直接而簡(jiǎn)單的.對(duì)于由管網(wǎng)結(jié)點(diǎn)Aj沿邊AjAk向Ak方向運(yùn)送yjkkm鋼管這一部分運(yùn)費(fèi),由于不足1km部分按1km計(jì)價(jià),yjk應(yīng)作為整數(shù)看待,這部分運(yùn)費(fèi)應(yīng)為0.1(1+2+?+yjk)=0.12yik(yik+1).0.1(1+2+?+yjk)=0.12yik(yik+1).根據(jù)以上分析,我們就很容易得到總費(fèi)用的表達(dá)式,即優(yōu)化問(wèn)題的目標(biāo)函數(shù).根據(jù)在邊AjAk上,從兩端運(yùn)送到沿線的鋼管數(shù)之和應(yīng)為AjAk的邊長(zhǎng)tjk,從G2的一個(gè)結(jié)點(diǎn)Aj向各邊運(yùn)送鋼管數(shù)量之和∑k∈Νjykj∑k∈Njykj應(yīng)等于Aj得到的鋼管數(shù)m∑i=1xij∑i=1mxij,再考慮到對(duì)鋼廠供貨的約束,我們得到優(yōu)化模型Ⅰ:minm∑i=1n∑j=1(cij+pi)xij+0.12n∑j=1∑k∈Νjyjk(yjk+1)(1)s.t.m∑i=1xij=∑k∈Ljyjkj=1,2,?,n(2)yjk+ykj=tjkk∈Νj,k<j,j=1,2,?,n(3)xij≥0i=1,2,?,m;j=1,2,?,n(4)yjk≥0k∈Νj;j=1,2,?,n(5)n∑j=1xij∈{0}∪[500,si]i=1,2,?,m(6)mins.t.∑i=1m∑j=1n(cij+pi)xij+0.12∑j=1n∑k∈Njyjk(yjk+1)∑i=1mxij=∑k∈Ljyjkj=1,2,?,nyjk+ykj=tjkk∈Nj,k<j,j=1,2,?,nxij≥0i=1,2,?,m;j=1,2,?,nyjk≥0k∈Nj;j=1,2,?,n∑j=1nxij∈{0}∪[500,si]i=1,2,?,m(1)(2)(3)(4)(5)(6)在模型Ⅰ中,求解的主要困難在約束條件(6).如果將(6)換成0≤n∑j=1xij≤si(7)n∑j=1xij=0(8)500≤n∑j=1xij≤si(9)0≤∑j=1nxij≤si∑j=1nxij=0500≤∑j=1nxij≤si(7)(8)(9)這三種條件中的任何一種,問(wèn)題就是標(biāo)準(zhǔn)的二次規(guī)劃問(wèn)題,可以直接用二次規(guī)劃的程序求解.約束條件(6)實(shí)質(zhì)上每一個(gè)式子包含(8)、(9)所表示的兩種情形.為此,可以用分支定界法來(lái)處理.首先用(7)取代約束(6)中的關(guān)系式,實(shí)際上是擴(kuò)大了模型Ⅰ的可行集,形成模型Ⅰ的松弛問(wèn)題.這是一個(gè)標(biāo)準(zhǔn)的二次規(guī)劃問(wèn)題,求解之.得出的解如果滿足(6),則已是模型Ⅰ的解.如果(6)中的m個(gè)條件不全滿足,選擇一個(gè)使0＜n∑j=1xij＜si0＜∑j=1nxij＜si的i對(duì)問(wèn)題(1)—(6)進(jìn)行分裂,就這個(gè)i分別用(8)和(9)取代(6)中的相應(yīng)關(guān)系式得到兩個(gè)子問(wèn)題.這兩個(gè)子問(wèn)題的解中最優(yōu)值小的一個(gè)就是模型Ⅰ的解.求解模型Ⅰ就歸結(jié)為求解這兩個(gè)子問(wèn)題.在求解子問(wèn)題時(shí)對(duì)剩下的形如(6)中關(guān)系式的約束仍然按以上方法進(jìn)行松弛求解,有必要時(shí)再進(jìn)行分裂,并在過(guò)程中不斷舍棄不可能產(chǎn)生比現(xiàn)有可行解更好的解的子問(wèn)題.最終得到模型Ⅰ的最優(yōu)解.從理論上來(lái)說(shuō),分支定界法的子問(wèn)題形成一個(gè)樹形圖,最壞的情況可有2m個(gè)子問(wèn)題.但就本題而言,模型Ⅰ的松弛問(wèn)題的解中只有i=6和i=7不滿足約束(6),因此只需要一兩次分裂過(guò)程即可完成.模型Ⅰ還可以有等價(jià)的表達(dá)方式,引入0—1變量wi,用wi=1表示從鋼廠Si購(gòu)買鋼管,wi=0表示不從鋼廠Si購(gòu)買鋼管.則問(wèn)題表示為混合0—1問(wèn)題.用分支定界法來(lái)求解,和前面所述方法實(shí)質(zhì)上是一致的.3不足1km按1km主體l的最優(yōu)值的計(jì)算1.對(duì)于賽題的問(wèn)題2可以采用對(duì)銷價(jià)和產(chǎn)量上限進(jìn)行數(shù)據(jù)擾動(dòng)來(lái)求解的辦法來(lái)進(jìn)行分析,也可以對(duì)模型Ⅰ的求解結(jié)果直接結(jié)合已知數(shù)據(jù)來(lái)進(jìn)行分析.有些鋼廠銷價(jià)的變化達(dá)到一定程度(并不一定太大)時(shí)可能使問(wèn)題的最優(yōu)解發(fā)生本質(zhì)的變化,甚至影響到訂購(gòu)哪些鋼廠的鋼管,對(duì)這種情況的分析是很有價(jià)值的.2.由于問(wèn)題中所有路段的里程數(shù)均為整數(shù),計(jì)價(jià)的里程檔次也是以整km劃分的.我們?cè)谀Ｐ廷裰幸舱J(rèn)為所有yjk均為整數(shù),當(dāng)然xik也是整數(shù).但我們?cè)谀Ｐ偷谋磉_(dá)(1)—(6)及求解中并未強(qiáng)調(diào)yjk為整數(shù).實(shí)際上,在AjAk段如果取yjk=l和yjk=l+1達(dá)到同樣的效果,這時(shí)在l到l+1這1km中無(wú)論從Aj還是Ak運(yùn)來(lái)鋼管的代價(jià)都是一樣的.這1km中一部分從Aj一部分從Ak運(yùn)來(lái)鋼管的代價(jià)也是一樣的.這是由于不足1km按1km計(jì)價(jià)所引起的.所以,我們求解中不必強(qiáng)調(diào)yjk為整數(shù).具體分析一下這種情況.先看從距Aj第l到l+1km這1km中的情況.設(shè)鋼管運(yùn)達(dá)Aj和Ak的代價(jià)分別為uj和uk.則從Aj和Ak往這1km運(yùn)送所需的總代價(jià)分別為uj+0.1(l+1)和uk+0.1(t-l),因此uj+0.1(l+1)=uk+0.1(t-l)于是uj-uk=0.1(t-2l-1)因此uj+0.1(l+1)=uk+0.1(t?l)于是uj?uk=0.1(t?2l?1)若從Aj運(yùn)送l+ε(km)(0≤ε≤1),則與AjAk有關(guān)的這部分費(fèi)用為uj(l+ε)+0.12l(l+1)+0.1(l+1)ε+uk(t-l-ε)+0.12(t-l)(t-l+1)-0.1(t-l)ε=ujl+0.12l(l+1)+uk(t-l)+0.12(t-l)(t-l+1)+ε(uj-uk)+0.1(2l-t+1)ε=ujl+0.12l(l+1)+uk(t-l)+0.12(t-l)(t-l+1)明顯與ε無(wú)關(guān).在這種情況下,取yjk=l或yjk=l+1都是最優(yōu)解,最優(yōu)解不唯一.如果算出yjk不是整數(shù),例如yjk=l+ε,0<ε<1,從嚴(yán)格意義上來(lái)說(shuō)目標(biāo)函數(shù)值是有誤差的.這時(shí)按(1)中的表達(dá)式計(jì)算這一部分的費(fèi)用為uj(l+ε)+0.12(l+ε)(l+1+ε)+uk(t-l-ε)+0.12(t-l-ε)(t-l-ε+1)=ujl+0.12l(l+1)+uk(t-l)+0.12(t-l)(t-l+1)-0.1ε(1-ε)比實(shí)際費(fèi)用低了0.1ε(1-ε),因此遇見(jiàn)這種情況時(shí)會(huì)算出最優(yōu)解中yjk=l+12,這也是問(wèn)題的最優(yōu)解,但目標(biāo)函數(shù)值比實(shí)際費(fèi)用低了0.025萬(wàn)元,這相對(duì)來(lái)說(shuō)是微不足道的,不影響解的最優(yōu)性.3.在管網(wǎng)的某些段上,從不同的鋼廠運(yùn)來(lái)的總代價(jià)一樣,這也可以引起最優(yōu)解不唯一.4.若忽略運(yùn)價(jià)不足1km按1km計(jì)價(jià)這一因素,公路運(yùn)費(fèi)是里程y的連續(xù)函數(shù),則(1)的第二個(gè)和式中的0.12yjk(yjk+1)將變成0.1∫yjk0xdx=0.12y2jk這時(shí)AjAk這一段的運(yùn)費(fèi)為0.12[y2jk+(tjk-yjk)2]與(1)中相鄰部分的差為0.12[yjk+(tjk-yjk)]=0.05tjk各段之總費(fèi)用差為0.05L,其中L=∑AjAk∈E2tjk是管道總長(zhǎng).因此目標(biāo)函數(shù)中用y2jk代替yjk(yjk+1)不影響最優(yōu)解,但是算出的最優(yōu)值比按(1)算出的最優(yōu)值少0.05L.4模型a:11如果把管網(wǎng)分成每km一段,共r段,編號(hào)為k=1,2,…r.則從cij很容易算出鋼廠Si到編號(hào)為h這一段的最低費(fèi)用eih.設(shè)編號(hào)為h的一段在G2中的邊AjAk上從Aj算起的第q段,則ejh=min{pi+cij+0.1q,pi+cik+0.1(tjk-q+1)}在每一段AjAk是依次編號(hào)的,特別是在問(wèn)題1中是沿管道從A0向A15依次按里程編號(hào)的,eih表現(xiàn)為h的分段線性函數(shù).我們?nèi)Q策變量為Zih(i=1,2,..m;h=1,2,...,r),用Zih=1表示第h段用Si廠的鋼管,Zih=0表示第h段不用Si廠的鋼管.則可建立線性模型Ⅱminn∑i=1r∑h=1eihΖih(10)s.t.n∑i=1Ζih=1h=1,2,?,r(11)r∑h=1Ζih∈{0}∪[500,si]i=1,2,?,m(12)Ζih∈{0,1}i=1,2,?,m;h=1,2,?,r(13)對(duì)約束(12)可按對(duì)二次規(guī)劃模型采用的分支定界法處理.如果將(13)換成Zih≥0,每次需要求解的松弛子問(wèn)題具有標(biāo)準(zhǔn)線性運(yùn)輸問(wèn)題的形狀,可用運(yùn)輸問(wèn)題的表上作業(yè)法求解.由于所有系數(shù)都是整數(shù),用表上作業(yè)法可得整數(shù)最優(yōu)解.再由約束(11)及Zih≥0,可保證Zih∈{0,1}.雖然看起來(lái)模型的規(guī)模較大(r大),但由于表上作業(yè)法的特點(diǎn),存儲(chǔ)量和計(jì)算量還是可以