.,2000網(wǎng)易杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目,B題鋼管訂購(gòu)和運(yùn)輸,西北大學(xué)數(shù)學(xué)系,竇霽虹,.,信息（語(yǔ)言、數(shù)據(jù)）,問(wèn)題（第一問(wèn)，,）,問(wèn)題所屬類(lèi)型,做題思路和關(guān)鍵點(diǎn),結(jié)果表示形式,讀題,.,要鋪設(shè)一條輸送天然氣的主管道,如圖一所示。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠(chǎng)有,。圖中粗線(xiàn)表示鐵路，單細(xì)線(xiàn)表示公路，雙細(xì),線(xiàn)表示要鋪設(shè)的管道（假設(shè)沿管道或者原來(lái)有公路，或者,和管道旁的阿拉伯?dāng)?shù)字表示里程（單位：Km）。,或者建有施工公路)，圓圈表示火車(chē)站，每段鐵路、公路,為方便計(jì)，1Km主管道鋼管稱(chēng)為1單位鋼管。,.,.,一個(gè)鋼廠(chǎng)如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè),單位。鋼廠(chǎng),在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為,個(gè)單位，鋼管出廠(chǎng)銷(xiāo)價(jià)1單位鋼管為,萬(wàn)元，如下表：,.,1單位鋼管的鐵路運(yùn)價(jià)如下表：,1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元。,公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬(wàn)元（不足整公里部分按整公里計(jì)算）。,鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只運(yùn)到點(diǎn),，而是管道全線(xiàn)）。,.,問(wèn)題：（1）請(qǐng)制定一個(gè)主管道鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最小（給出總費(fèi)用)。,（2）請(qǐng)就（1）的模型分析：哪個(gè)鋼廠(chǎng)鋼管的銷(xiāo)價(jià)的變化,對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠(chǎng)鋼管的產(chǎn)量的上限,的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)字,結(jié)果。,（3）如果要鋪設(shè)的管道不是一條線(xiàn)，而是一個(gè)樹(shù)形圖，,鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出,一種解決辦法，并對(duì)圖二按（1）的要求給出模型和結(jié)果。,.,.,問(wèn)題所屬類(lèi)型,做題思路和關(guān)鍵點(diǎn),結(jié)果表示形式,優(yōu)化模型,.,1、問(wèn)題的分析,優(yōu)化問(wèn)題,1）優(yōu)化模型的數(shù)學(xué)描述,求函數(shù),在約束條件,下的最大值或最小值，其中,和,設(shè)計(jì)變量（決策變量）,目標(biāo)函數(shù),可行域,.,“受約束于”之意,.,線(xiàn)性規(guī)劃（LP）,目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線(xiàn)性函數(shù)。,西北大學(xué)數(shù)學(xué)系,.,二次規(guī)劃問(wèn)題,目標(biāo)函數(shù)為二次函數(shù)，約束條件為線(xiàn)性約束,.,2）建立優(yōu)化模型的一般步驟,1.確定設(shè)計(jì)變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；3.尋找約束條件。,.,設(shè)有某物資從m個(gè)發(fā)點(diǎn)輸送到n個(gè)收點(diǎn)其中每個(gè)發(fā)點(diǎn)發(fā)出量分別為每個(gè)收點(diǎn)輸入量分別為，并且滿(mǎn)足從發(fā)點(diǎn)A到收點(diǎn)B的距離（或單位運(yùn)費(fèi)）是已知的，設(shè)為。問(wèn)題：尋求一個(gè)調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用達(dá)到最小。,例運(yùn)輸問(wèn)題,.,B1B2.Bn,A1,A2,Am,a1,a2,am,b1b2.bn,.,.,x11x12.x1n,x21x22.x2n,xm1xm2.xmn,收點(diǎn),發(fā)點(diǎn),一個(gè)調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn)到收點(diǎn)的輸送量來(lái)描述。,.,總的費(fèi)用,A1的總費(fèi)用,A2的總費(fèi)用,.,s.t.,數(shù)學(xué)模型,求解：?jiǎn)渭冃畏椒ā?.,問(wèn)題：（1）請(qǐng)制定一個(gè)主管道鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最小（給出總費(fèi)用)。,（2）請(qǐng)就（1）的模型分析：哪個(gè)鋼廠(chǎng)鋼管的銷(xiāo)價(jià)的變化,對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠(chǎng)鋼管的產(chǎn)量的上限,的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)字,結(jié)果。,（3）如果要鋪設(shè)的管道不是一條線(xiàn)，而是一個(gè)樹(shù)形圖，,鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出,一種解決辦法，并對(duì)圖二按（1）的要求給出模型和結(jié)果。,.,B1B2.Bn,S1,S2,S7,a1,a2,am,b1b2.bn,.,.,x11x12.x1n,x21x22.x2n,xm1xm2.xmn,收點(diǎn),發(fā)點(diǎn),訂購(gòu)與運(yùn)輸方案,n=5171,.,s.t.,數(shù)學(xué)模型,注1：表示單位鋼管從運(yùn)到的最小費(fèi)用（含訂購(gòu)費(fèi)用）,注2：適合第三問(wèn)，只是n=5903.,.,目標(biāo)變量：,總費(fèi)用=訂購(gòu)費(fèi)用+運(yùn)輸費(fèi)用,總費(fèi)用W,運(yùn)輸費(fèi)用=從鋼廠(chǎng)到管道關(guān)節(jié)點(diǎn),的運(yùn)輸費(fèi)用P+,從管道的關(guān)節(jié)點(diǎn)到鋪設(shè)點(diǎn)的運(yùn)輸費(fèi)用T,即：,.,鋼管的訂購(gòu)計(jì)劃：,每個(gè)鋼廠(chǎng)的定貨數(shù)量。,鋼管的運(yùn)輸方案：,從每個(gè)鋼廠(chǎng)運(yùn)送到每個(gè)管道,區(qū)間的鋼管量。,.,1）基本假設(shè)：,要鋪設(shè)的管道側(cè)有公路，可運(yùn)送所需鋼管；,鋼管在運(yùn)輸中由鐵路運(yùn)轉(zhuǎn)為公路運(yùn)時(shí)不計(jì)換車(chē)費(fèi)；,所需鋼管均由鋼廠(chǎng)提供；,在具體鋪設(shè)每一公里時(shí)，只把鋼管運(yùn)輸?shù)矫恳还镩_(kāi)始的地方，沿運(yùn)輸方向向前鋪設(shè)的費(fèi)用不予考慮。,2、模型假設(shè)與符號(hào)說(shuō)明,.,：1單位鋼管從鋼廠(chǎng)運(yùn)到的最小費(fèi)用（單位：萬(wàn)元）；,2）符號(hào)說(shuō)明：,：從到之間的距離（單位：千米）；,：鋼廠(chǎng)的最大生產(chǎn)能力；,：鋼廠(chǎng)的出廠(chǎng)鋼管單位價(jià)格（單位：萬(wàn)元）；,：公路上1單位鋼管的每公里運(yùn)費(fèi)（d=0.1萬(wàn)元）；,：鐵路上1單位鋼管的運(yùn)費(fèi)（分段函數(shù)見(jiàn)表一）；,.,：運(yùn)到地的鋼管向左鋪設(shè)的數(shù)目；,鋼廠(chǎng)提供鋼管,鋼廠(chǎng)不提供鋼管,：所求鋼管訂購(gòu)、運(yùn)輸?shù)目傎M(fèi)用（單位：萬(wàn)元）。,：運(yùn)到地的鋼管向右鋪設(shè)的數(shù)目；,：鋼廠(chǎng)運(yùn)到的鋼管數(shù)；,.,目標(biāo)函數(shù)是總費(fèi)用：鋼管出廠(chǎng)總價(jià),運(yùn),，,3、模型的建立,(1)決策變量,(2)目標(biāo)函數(shù),輸費(fèi),及鋪設(shè)費(fèi),即其中,：1單位鋼管從鋼廠(chǎng)運(yùn)到的最小費(fèi)用（單位：萬(wàn)元）,.,從開(kāi)始向左右兩個(gè)方向鋪設(shè)，鋪設(shè)的數(shù)量分別用與來(lái)表示。,鋪設(shè)費(fèi)可以如下確定：,單位長(zhǎng)鋼管的費(fèi)用為,故,.,（3）約束條件,與,的鋼管：,生產(chǎn)能力的限制:,運(yùn)到的鋼管用完：,變量非負(fù)性限制：,端點(diǎn)限制：,.,s.t.,(4)數(shù)學(xué)模型,.,其中每一表示單位鋼管從到的,最小運(yùn)輸費(fèi)用，因而，求解實(shí)際上是一個(gè)求最短,“最短路經(jīng)”問(wèn)題是圖論中最基本的問(wèn)題之一。,4、模型的求解,關(guān)鍵1求出目標(biāo)函數(shù)中的系數(shù),關(guān)鍵2確定約束條件中的,路徑的問(wèn)題。,“最短路經(jīng)”問(wèn)題的標(biāo)準(zhǔn)算法-弗洛伊德算法。,.,.,其中表示從到的最短路程，若不能相連，,求出鐵路和公路的最短路徑矩陣,用表示。,運(yùn)用Floyd算法，得出局部最短路徑矩陣。,鐵路和公路自身分別構(gòu)成權(quán)矩陣，記為和。,鐵路和公路的最短路徑矩陣的統(tǒng)一,對(duì)公路，將為公路局部最小運(yùn)費(fèi)矩陣。,.,對(duì)鐵路，用鐵路的費(fèi)用進(jìn)行轉(zhuǎn)換，得局部鐵路,最小運(yùn)費(fèi)矩陣。,令,對(duì)得到的A,再使用一次Floyd算法，得到全局的最短,每?jī)牲c(diǎn)間最小運(yùn)費(fèi)矩陣，從中抽取出到之間,的子矩陣即為所需的。,求最小費(fèi)用矩陣,.,最小費(fèi)用矩陣,注：表中的數(shù)據(jù)乘以0.1為對(duì)應(yīng)的最小費(fèi)用矩陣的元素。,.,最小費(fèi)用矩陣,注：表中的數(shù)據(jù)乘以0.1為對(duì)應(yīng)的最小費(fèi)用矩陣的元素。,.,模型就轉(zhuǎn)化為典型的二次規(guī)劃問(wèn)題。,如果其最優(yōu)解符合原有的約束條件，則便是原問(wèn)題的最優(yōu)解。,如果存在i使那么,針對(duì)這些i分兩種情況,找出其中的最優(yōu)的結(jié)果。,.,s.t.,根據(jù)二次規(guī)劃軟件求解模型,或者運(yùn)用數(shù)學(xué)軟件Lingo5.0,編程求解,.,將從供應(yīng)商中除去，再將第7家工廠(chǎng)的供貨量,最優(yōu)解中,改為0以及不小于500兩種情況重做。相比之下，,取0的情況總費(fèi)用較小，從而也把刪除。,.,鋼管的訂購(gòu)計(jì)劃：,億元,5、結(jié)果表示,.,鋼管的運(yùn)輸方案：,.,1）確定哪個(gè)鋼廠(chǎng)的銷(xiāo)價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大,6、靈敏度分析,s.t.,.,假設(shè)該鋼廠(chǎng)的銷(xiāo)價(jià)變化在萬(wàn)元以?xún)?nèi)，,結(jié)論：或的銷(xiāo)價(jià)的變化影響最大。,.,鋼管的訂購(gòu)計(jì)劃：,億元,.,2）確定哪個(gè)鋼廠(chǎng)的生產(chǎn)上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大,在變化的情況下目標(biāo)函數(shù)減小量及減小的比率,結(jié)論：的生產(chǎn)上限的變化影響最大。,.,最小費(fèi)用矩陣,注：表中的數(shù)據(jù)乘以0.1為對(duì)應(yīng)的最小費(fèi)用矩陣的元素。,.,若要鋪設(shè)的道路不是一條線(xiàn)，而是一個(gè)樹(shù)形圖，,7、關(guān)于問(wèn)題（3）,.,s.t.,數(shù)學(xué)模型,.,運(yùn)用數(shù)學(xué)軟件Lingo5.0編程求出：,億元,.,課后練習(xí)：,（1）求出最小費(fèi)用矩陣,（2）求解問(wèn)題1的二次規(guī)