運(yùn)輸問題模型

精選優(yōu)質(zhì)文檔-----傾情為你奉上精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)專心---專注---專業(yè)精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)§5.2運(yùn)輸問題模型1、運(yùn)輸問題模型概述運(yùn)輸問題是一類特殊的線性規(guī)劃模型，該模型的建立最初用于解決一個(gè)部門的運(yùn)輸網(wǎng)絡(luò)所要求的最經(jīng)濟(jì)的運(yùn)輸路線和產(chǎn)品的調(diào)配問題，并取得了成功。然而，在實(shí)際問題的應(yīng)用中，除運(yùn)輸問題外，許多非運(yùn)輸問題的實(shí)際問題一樣可以建立其相應(yīng)的運(yùn)輸問題模型，并由此而求出其最優(yōu)解。下面以“產(chǎn)銷平衡模型”對(duì)運(yùn)輸問題進(jìn)行一下簡(jiǎn)單的概括和描述：某產(chǎn)品的生產(chǎn)有個(gè)產(chǎn)地，其生產(chǎn)量分別為，而該產(chǎn)品的銷售有個(gè)銷地，其需要量分別為，已知該產(chǎn)品從產(chǎn)地到銷地的單位運(yùn)價(jià)為，試建立該運(yùn)輸問題的線性規(guī)劃模型。解：假設(shè)從產(chǎn)地到銷地的運(yùn)輸量為，因從產(chǎn)地到銷地的單位運(yùn)價(jià)為，我們可把運(yùn)輸量（）匯總于產(chǎn)銷平衡表中，而把單位運(yùn)價(jià)匯總于單位運(yùn)價(jià)表中（見下表）。產(chǎn)銷平衡表產(chǎn)地銷地12……n產(chǎn)量12……銷量………則在該產(chǎn)銷平衡表表中，第列的物理含義為：從各產(chǎn)地發(fā)往銷地的部分運(yùn)輸量的和應(yīng)等于銷量，第行的物理含義類同。單位運(yùn)價(jià)表銷地產(chǎn)地12……12…………由以上的討論，對(duì)產(chǎn)銷平衡的情形，我們可給出其運(yùn)輸問題的數(shù)學(xué)模型如下：當(dāng)然，在實(shí)際問題的應(yīng)用中，常出現(xiàn)產(chǎn)銷不平衡的情形，此時(shí)，需要把產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題來(lái)進(jìn)行討論。例當(dāng)產(chǎn)量大于銷量時(shí)，只需增加一個(gè)虛擬的銷地，而該銷地的需要量為即可。銷量大于產(chǎn)量的情形類同。2.應(yīng)用實(shí)例運(yùn)輸問題模型的應(yīng)用比較廣泛，并不完全局限于運(yùn)輸問題，下面我們舉例說明之。例1.生產(chǎn)時(shí)序的安排1)問題的提出北方飛機(jī)公司為全球各航空公司制造商用飛機(jī)。其生產(chǎn)過程之最后階段為生產(chǎn)噴射引擎，然后裝置于（一極速工作）制妥的機(jī)體，該公司有若干近期必須交付使用的飛機(jī)的合同，現(xiàn)須安排今后四個(gè)月飛機(jī)噴射引擎的生產(chǎn)計(jì)劃，并須于每月末分別提供10、15、25、20臺(tái)引擎。已知該公司各月的生產(chǎn)能力和生產(chǎn)每臺(tái)引擎的成本如下表所示（單位：百萬(wàn)元），又如果生產(chǎn)出來(lái)的引擎當(dāng)月不能交貨的，每臺(tái)引擎每積壓一個(gè)月需存儲(chǔ)和維護(hù)費(fèi)用0.015百萬(wàn)元，試在完成合約的情況下，制定一引擎數(shù)量的生產(chǎn)安排方案，以使該公司今后四個(gè)月的生產(chǎn)費(fèi)用最小。生產(chǎn)成本表月份合約數(shù)生產(chǎn)能力單位成本存儲(chǔ)和維護(hù)費(fèi)110251．080．015215351．110．015325301．100．015420101．132）模型分析與變量的假設(shè)初看之下，這是一個(gè)與運(yùn)輸問題模型毫無(wú)關(guān)系的問題，如何用運(yùn)輸問題模型求出其最優(yōu)解，這種素質(zhì)和能力是因人而異的。用運(yùn)輸問題模型求該問題最優(yōu)解的關(guān)鍵在于怎樣建立該問題的產(chǎn)銷平衡表及元素和單位運(yùn)價(jià)表及元素。為此，我們假設(shè)表示第月生產(chǎn)并用于第月交貨的引擎數(shù)，因公司必須完成合同，則應(yīng)滿足：又每月生產(chǎn)的用于當(dāng)月和以后各月交貨的引擎數(shù)不可能超過該公司的實(shí)際生產(chǎn)能力，故還應(yīng)滿足：下面再構(gòu)造“單位運(yùn)價(jià)表”，它應(yīng)等價(jià)于這里的“成本費(fèi)用表”。因第月生產(chǎn)并用于第月交貨的引擎數(shù)的實(shí)際成本應(yīng)該是其生產(chǎn)單位成本再加上存儲(chǔ)、維護(hù)費(fèi)用，從而我們可得其“成本費(fèi)用表”如下：成本費(fèi)用表123411.081.0951.1101.12521.1101.1251.14031.1001.11541.130由于這是產(chǎn)銷不平衡問題，故增加一虛擬的銷地D，使之能構(gòu)造為產(chǎn)銷平衡模型，并把“產(chǎn)銷平衡表和單位運(yùn)價(jià)表”合二為一（見下表）：1234D產(chǎn)量（）11.081.0951.1101.1250252M1.1101.1251.1400353MM1.1001.1150304MMM1.130010銷量（）1015252030在該表中，表示公司第月的生產(chǎn)能力，表示第月的合同供應(yīng)量，表示相應(yīng)的成本費(fèi)用，因在實(shí)際問題中，當(dāng)時(shí)，，故令相應(yīng)的。3）模型的建立與求解有了如上的討論，我們可給出“生產(chǎn)時(shí)序的安排”所對(duì)應(yīng)的“運(yùn)輸問題模型”：據(jù)此，我們可求出其最優(yōu)解為：。相應(yīng)的最小生產(chǎn)費(fèi)用為：故今后四個(gè)月引擎數(shù)量的生產(chǎn)安排為：月份1234引擎生產(chǎn)數(shù)量2553010例2．航運(yùn)公司的船只配備問題1）問題的提出某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F的四條固定航線的物資運(yùn)輸任務(wù)，已知各條航線的起點(diǎn)、終點(diǎn)城市及每天的航班數(shù)如下表所示：航線起點(diǎn)城市終點(diǎn)城市每天航班數(shù)1ED32BC23AF14DB1假定各條航線使用相同型號(hào)的船只，又各城市間的航程天數(shù)如下表所示：ABCDEFA0121477B1031388C23015557851703F7852030若每條船只每次裝卸貨的時(shí)間各需一天，則該航運(yùn)公司至少應(yīng)配備多少條船只，才能滿足所有航線的運(yùn)營(yíng)要求？2）模型分析與變量的假設(shè)公司所需配備的船只數(shù)分為“在航所需船只數(shù)及調(diào)度所需船只數(shù)”這兩部分，計(jì)算出在航所需船只及調(diào)度所需船只這兩種情況所必需的最少數(shù)量，便可確定該航運(yùn)公司至少應(yīng)配備的船只數(shù)。在航所需船只數(shù)情形可直接進(jìn)行計(jì)算，例如航線1，在起點(diǎn)E裝貨需1天，從E—>D航程需17天，在終點(diǎn)D卸貨需1天，共計(jì)19天，該航線每天發(fā)3班，故該航線在航船只至少需57只船，同理，可求出其它各航線所需的最少在航船只數(shù)如下表所示：航線裝貨天數(shù)航程天數(shù)卸貨天數(shù)小計(jì)航班數(shù)周轉(zhuǎn)數(shù)11171193572131521031719194113115115合計(jì)91但調(diào)度所需船只數(shù)情形就不便直接求出了，因?yàn)橛械母劭冢刻斓竭_(dá)船只數(shù)大于所需船只數(shù)，例如港口D，每天到達(dá)3條船只，需求1條船只；而有的港口，它每天到達(dá)船只數(shù)小于所需船只數(shù)，例如港口B，每天到達(dá)1條船只，需求2條船只。故如何確定公司調(diào)度所需船只數(shù)是解決問題的關(guān)鍵。對(duì)此，我們建立運(yùn)輸問題模型求其最優(yōu)解。這樣一來(lái)，怎樣給出調(diào)度所需船只數(shù)情形所對(duì)應(yīng)的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，以據(jù)此求出其最優(yōu)解，是迫在眉睫的事情了。為建立調(diào)度所需船只數(shù)情形所對(duì)應(yīng)的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，我們以每個(gè)港口城市作為考慮對(duì)象，凡到達(dá)船只數(shù)大于需求船只數(shù)的港口城市，我們將其視為產(chǎn)銷平衡表中產(chǎn)地，而到達(dá)船只數(shù)小于需求船只數(shù)的港口城市，我們將其視為產(chǎn)銷平衡表中銷地，對(duì)管理部門而言，每個(gè)港口城市的到達(dá)船只和需求船只是不難獲知的（見下表）：港口城市每天到達(dá)每天需求余缺數(shù)A01-1B12-1C202D312E03-3F101用表示從港調(diào)撥到港的船只數(shù)，則我們給出該問題的產(chǎn)銷平衡表如下：銷地產(chǎn)地ABE“產(chǎn)量”C2D2F1“銷量”113而該問題的單位運(yùn)價(jià)表的元素視為各港口之間的船只航行