數(shù)學(xué)建模2000B題鋼管訂購和運(yùn)輸

1、2000網(wǎng)易杯全國大學(xué)生 數(shù)學(xué)建模競賽題目,B題 鋼管訂購和運(yùn)輸,信息 （語言、數(shù)據(jù)）,問題 （第一問，,）,問題 所屬類型,做題 思路和關(guān)鍵點(diǎn),結(jié)果 表示形式,讀 題,要鋪設(shè)一條 輸送天然氣的主管道,如圖一所示。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有,。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì),線表示要鋪設(shè)的管道（假設(shè)沿管道或者原來有公路，或者,和管道旁的阿拉伯?dāng)?shù)字表示里程（單位：Km）。,或者建有施工公路 )，圓圈表示火車站，每段鐵路、公路,為方便計(jì)，1 Km主管道鋼管稱為1單位鋼管。,一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè),單位。鋼廠,在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為,個(gè)單

2、位，鋼管出廠銷價(jià)1單位鋼管為,萬元，如下表：,1單位鋼管的鐵路運(yùn)價(jià)如下表：,1000km以上每增加1至100km運(yùn)價(jià)增加5萬元。,公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）。,鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只運(yùn)到點(diǎn),，而是管道全線）。,問題： （1）請制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用)。,（2）請就（1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化,對購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管的產(chǎn)量的上限,的變化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)字,結(jié)果。,（3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖，,鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請

3、就這種更一般的情形給出,一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。,問題 所屬類型,做題 思路和關(guān)鍵點(diǎn),結(jié)果 表示形式,優(yōu)化模型,1、問題的分析,優(yōu)化問題,1）優(yōu)化模型的數(shù)學(xué)描述,求函數(shù),在約束條件,下的最大值或最小值，其中,和,設(shè)計(jì)變量（決策變量）,目標(biāo)函數(shù),可行域,“受約束于”之意,線性規(guī)劃（LP）,目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)。,西北大學(xué)數(shù)學(xué)系,二次規(guī)劃問題,目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束,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ā)出量分

4、別為 每個(gè)收 點(diǎn)輸入量分別為 ，并且滿足 從發(fā)點(diǎn)A到收點(diǎn)B的距離（或單位運(yùn)費(fèi)）是已知的，設(shè)為 。 問題：尋求一個(gè)調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用達(dá)到最小。,例 運(yùn)輸問題,B1 B2 . Bn,A1,A2,Am,a1,a2,am,b1 b2 . bn,.,.,x11 x12 . x1n,x21 x22 . x2n,xm1 xm2 . xmn,收點(diǎn),發(fā)點(diǎn),一個(gè)調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn) 到收點(diǎn) 的輸送量來描述。,總的費(fèi)用,A1的總費(fèi)用,A2的總費(fèi)用,s.t.,數(shù)學(xué)模型,求解：單純形方法。,問題： （1）請制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用)。,（2）請就（1）的模型分析：哪個(gè)鋼廠鋼管

5、的銷價(jià)的變化,對購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管的產(chǎn)量的上限,的變化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)字,結(jié)果。,（3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖，,鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出,一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。,B1 B2 . Bn,S1,S2,S7,a1,a2,am,b1 b2 . bn,.,.,x11 x12 . x1n,x21 x22 . x2n,xm1 xm2 . xmn,收點(diǎn),發(fā)點(diǎn),訂購與運(yùn)輸方案,n=5171,s.t.,數(shù)學(xué)模型,注1： 表示單位鋼管從 運(yùn)到 的最小費(fèi)用（含訂購費(fèi)用）,注2：適合第三問，只是

6、 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,即：,鋼管的訂購計(jì)劃：,每個(gè)鋼廠的定貨數(shù)量。,鋼管的運(yùn)輸方案：,從每個(gè)鋼廠運(yùn)送到每個(gè)管道,區(qū)間的鋼管量。,1）基本假設(shè)：,要鋪設(shè)的管道側(cè)有公路，可運(yùn)送所需鋼管；,鋼管在運(yùn)輸中由鐵路運(yùn)轉(zhuǎn)為公路運(yùn)時(shí)不計(jì)換車費(fèi)；,所需鋼管均由 鋼廠提供；,在具體鋪設(shè)每一公里時(shí)，只把鋼管運(yùn)輸?shù)矫恳还镩_始的地方，沿運(yùn)輸方向向前鋪設(shè)的費(fèi)用不予考慮。,2、模型假設(shè)與符號說明,：1單位鋼管從鋼廠 運(yùn)到 的最小費(fèi)用（單位： 萬元）；,2）符號說明：,：從 到 之間的距

7、離（單位：千米）；,：鋼廠 的最大生產(chǎn)能力；,：鋼廠 的出廠鋼管單位價(jià)格（單位：萬元）；,：公路上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)用 ：鋼管出廠總價(jià) ,運(yùn),，,3、模型的建立,(1)決策變量,(2)目標(biāo)函數(shù),輸費(fèi) ,及鋪設(shè)費(fèi) ,即 其中,：1單位鋼管從鋼廠 運(yùn)到 的最小費(fèi)用（單位：萬元）,從 開始向左右兩個(gè)方向鋪設(shè)，鋪設(shè)的數(shù)量分 別用 與 來表示。,

8、鋪設(shè)費(fèi) 可以如下確定：,單位長鋼管的費(fèi)用為,故,（3）約束條件,與,的鋼管：,生產(chǎn)能力的限制:,運(yùn)到 的鋼管用完：, 變量非負(fù)性限制：,端點(diǎn)限制：,s.t.,(4)數(shù)學(xué)模型,其中每一 表示單位鋼管從 到 的,最小運(yùn)輸費(fèi)用，因而，求解 實(shí)際上是一個(gè)求最短,“最短路經(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)矩陣，記為 和 。

9、,鐵路和公路的最短路徑矩陣的統(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ī)劃軟

10、件求解模型,或者運(yùn)用數(shù)學(xué)軟件Lingo5.0,編程求解,將 從供應(yīng)商中除去，再將第7家工廠的供貨量,最優(yōu)解中,改為0以及不小于500兩種情況重做。相比之下，,取0的情況總費(fèi)用較小，從而也把 刪除。,鋼管的訂購計(jì)劃：,億元,5、結(jié)果表示,鋼管的運(yùn)輸方案：,1）確定哪個(gè)鋼廠的銷價(jià)的變化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大,6、靈敏度分析,s.t.,假設(shè)該鋼廠的銷價(jià)變化在 萬元以內(nèi)，,結(jié)論： 或 的銷價(jià)的變化影響最大。,鋼管的訂購計(jì)劃：,億元,2）確定哪個(gè)鋼廠的生產(chǎn)上限的變化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大,在變化 的情況下目標(biāo)函數(shù)減小量及減小的比率,結(jié)論： 的生產(chǎn)上限的變化影響最大。,最小費(fèi)用矩陣,注：表中的數(shù)據(jù)乘以0.1為對應(yīng)的最小費(fèi)用矩陣的元素。,若要鋪設(shè)的道路不是一條線，而是一個(gè)樹形圖，,7、關(guān)于問題（3）,s.t.,數(shù)學(xué)模型,運(yùn)用數(shù)學(xué)軟件Lingo5