數(shù)學(xué)建模 2000B題

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