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

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