物流運(yùn)籌學(xué)第四章課件

1、第四章 運(yùn)輸問題運(yùn)輸問題的數(shù)學(xué)模型 運(yùn)輸問題求解表上作業(yè)法物流配送應(yīng)用實(shí)例知識目標(biāo)掌握運(yùn)輸問題的基本形式（數(shù)學(xué)模型）掌握表上作業(yè)法的求解過程 技能目標(biāo)能夠結(jié)合實(shí)際情況建立運(yùn)輸問題的模型，并可利用表上作業(yè)法求解能夠利用所學(xué)方法指導(dǎo)實(shí)際工作，解決實(shí)際問題第一節(jié) 運(yùn)輸問題的數(shù)學(xué)模型建立運(yùn)輸問題的數(shù)學(xué)模型介紹閉回路和孤立點(diǎn)的概念給出運(yùn)輸問題數(shù)學(xué)模型的特性 運(yùn)輸問題的數(shù)學(xué)模型s.t.(4-1)其中閉回路和孤立點(diǎn)的概念設(shè)E是運(yùn)輸問題的一組變量。如果對E中變量作適當(dāng)?shù)呐帕泻竽艿玫较铝行问剑?其中 互不相同， 互不相同，則稱E為運(yùn)輸問題的一個(gè)閉回路。閉回路中的相應(yīng)變量稱為閉回路的頂點(diǎn)。設(shè)Q是運(yùn)輸問題一組變量，

2、若xij為Q中的一個(gè)變量，且xij是第i行或第j列中屬于Q的唯一變量，則稱xij為Q的一個(gè)孤立點(diǎn)。 運(yùn)輸問題數(shù)學(xué)模型的特性（1）在運(yùn)輸問題的m+n個(gè)等式約束方程中只有m+n-1個(gè)方程是相互獨(dú)立的，而且其中任意一組m+n-1個(gè)約束方程都是相互獨(dú)立的。（2）在運(yùn)輸問題的mn個(gè)變量中，選取m+n-1個(gè)變量構(gòu)成變量組Q，則Q能成為基變量組的充要條件是：Q中不存在閉回路。（3）設(shè)Q是運(yùn)輸問題的一組基變量，xst為非基變量，則xst必對應(yīng)一條唯一的閉回路E。E除頂點(diǎn)xst外，其余頂點(diǎn)都為基變量。（4）如果在運(yùn)輸問題中ai (i=1,m)和bj(j=1, ,n)都為整數(shù)，則任一基解中各變量的取值亦均為整數(shù)。

3、【例4-1】現(xiàn)有m個(gè)發(fā)點(diǎn) ， 可供應(yīng)某種物資給n個(gè)收點(diǎn) 。 發(fā)點(diǎn)Ai的物資供應(yīng)量（發(fā)量）為ai，收點(diǎn)Bj 對物資的需求量（收量）為bj，且收發(fā)平衡， 即 。又設(shè)單位物資從Ai運(yùn)往Bj的單 位運(yùn)價(jià)為cij。問怎樣運(yùn)輸這些物資，以使總運(yùn) 費(fèi)最??？第二節(jié) 表上作業(yè)法初始基可行解的確定 位勢法求解初始基可行解的確定西北角法：西北角法按以下規(guī)則在mn個(gè)變量中選擇m+n-1個(gè)基變量構(gòu)成變量組Q：從運(yùn)輸表格的西北角x11開始，優(yōu)先安排編號小的發(fā)點(diǎn)和收點(diǎn)之間的運(yùn)輸任務(wù)。最小元素法：最小元素法按以下規(guī)則選取m+n-1個(gè)基變量，優(yōu)先安排單位運(yùn)價(jià)cij小的發(fā)點(diǎn)Ai與收點(diǎn)Bj之間的運(yùn)輸任務(wù)。位勢法求解位勢法的算法步驟

4、：（1）應(yīng)用西北角法或最小元素法求得初始基本可行解xij和相應(yīng)的基本變量組Q。（2）由方程組（4-3），求得位勢ui和vj。（3）計(jì)算檢驗(yàn)數(shù)ij=cij-ui-vj，取st=minst 。（4）判斷st是否為零。若為零，則xij即為最優(yōu)解，算法終止。若不為零，則確定 中的閉回路E以及E+和E-（5）取 。（6）取 轉(zhuǎn)步驟（2）。 【例4-2】給出運(yùn)輸問題，如表4-6所示。使用西北角法確定它的一個(gè)基可行解。表4-6 例4-2運(yùn)需平衡表 Bj AiB1B2B3B4aiA115A220A310bj1215108【例4-4】運(yùn)輸問題見表4-11，用最小元素法求初始基可行解。表4-11 例4-4運(yùn)量及運(yùn)

5、價(jià)表 Bj AiB1B2B3B4aiA14731020A2252610A3938425bj12161413【例4-7】求解表4-17所給的運(yùn)輸問題（用最小元素法求初始基可行解）。 Bj AiB1B2B3B4aiA14731025A2252610A3938425bj12161418表4-17 例4-7運(yùn)輸表第三節(jié) 物流配送應(yīng)用實(shí)例【例4-8】運(yùn)輸問題如表4-21所示，試建立該問題的運(yùn)輸模型。表4-21 例4-8運(yùn)輸表 Bj AiB1B2B3aiA145210A268315bj876【例4-9】（不平衡運(yùn)輸問題）若發(fā)點(diǎn)的發(fā)量必須運(yùn)走，具體信息如表4-24，試建立運(yùn)輸模型。 表4-24 例4-9運(yùn)量

6、及運(yùn)價(jià)表 Bj AiB1B2B3aiA142310A256415A334520101010最低需求量本章小結(jié)本章首先介紹了一般平衡物資運(yùn)輸問題及其模型，依據(jù)單純形法的基本原理，給出了求解平衡運(yùn)輸問題的直觀方法表上作業(yè)法。討論了非平衡運(yùn)輸問題向平衡運(yùn)輸問題的轉(zhuǎn)換。最后，介紹了運(yùn)輸模型在物流配送領(lǐng)域中的應(yīng)用。本章的重點(diǎn)是求解平衡運(yùn)輸問題的表上作業(yè)法原理及其具體計(jì)算方法。其中，初試調(diào)運(yùn)方案的確定、調(diào)運(yùn)方案優(yōu)劣性檢驗(yàn)、調(diào)運(yùn)方法的改進(jìn)是掌握該方法的難點(diǎn)。 案例分析案例 加拿大太平洋鐵路公司：完善鐵路運(yùn)量規(guī)劃的方法1 問題描述 加拿大太平洋鐵路公司是一個(gè)完全一體化運(yùn)作且技術(shù)領(lǐng)先的一級鐵路網(wǎng)絡(luò)，為加拿大、美

7、國東部和中西部提供鐵路運(yùn)輸和多式聯(lián)運(yùn)服務(wù)。北美貨運(yùn)鐵路基本采用“以噸位為基礎(chǔ)的批運(yùn)”方式，即在貨物積累到一定量時(shí)列車才能發(fā)車。這一方式試圖通過最大限度地利用列車的裝載量來使發(fā)車總數(shù)最小。但實(shí)踐表明，這一方式妨礙了高效率地利用車組人員、機(jī)車和設(shè)備，并且它還使得運(yùn)輸周期不確定，在當(dāng)前運(yùn)輸業(yè)競爭日益激烈、服務(wù)水平提高很快的情況下，這種不可靠性成為鐵路運(yùn)輸服務(wù)爭奪市場份額的一大弱點(diǎn)。要找到一個(gè)更好的替代方法，需要利用到運(yùn)籌學(xué)中的時(shí)序安排的約束條件等具體技術(shù)。2 解決方案 加拿大太平洋鐵路公司轉(zhuǎn)而采取為鐵路所有作業(yè)都確定一個(gè)固定時(shí)間表的方法。該公司利用Multi Modal應(yīng)用軟件系統(tǒng)，開發(fā)出一個(gè)非常適

8、合于交通行業(yè)的運(yùn)作計(jì)劃。 （1）運(yùn)籌團(tuán)隊(duì)建立了一個(gè)模型，對每一個(gè)車皮的行程和編組計(jì)劃進(jìn)行優(yōu)化，并決定將其放在哪個(gè)車次中。 （2）團(tuán)隊(duì)成員細(xì)致地審查該計(jì)劃，找出日發(fā)車批量的波動(dòng)規(guī)律，并為最大量和最小量的時(shí)間制定應(yīng)急計(jì)劃。 （3）利用基于最短路徑技術(shù)的算法，Multi Modal獨(dú)有的Multi Rail程序可以找到減少裝備運(yùn)行里程數(shù)、列車運(yùn)行里程數(shù)和列車運(yùn)行時(shí)間的方法，從而降低運(yùn)作成本，減少在途中時(shí)間，是托運(yùn)人獲得更加可靠的運(yùn)輸服務(wù)。3 成效評價(jià) 加拿大太平洋鐵路公司的運(yùn)作理念和方式的轉(zhuǎn)變，成本降低了2.85億美元以上，使其服務(wù)更加可靠，大大增加了其收益率。 加拿大太平洋鐵路公司的總裁Rober

9、t Ritchie說：“我們開出了這個(gè)行業(yè)中最好的鐵路行程計(jì)劃模型最終為我們的客戶帶來了效能和生產(chǎn)率的提高以及更好的服務(wù)。然而，我們的工作不會(huì)就此止步從中，我們認(rèn)識到：在收益管理和合同談判等領(lǐng)域，我們還有那么多機(jī)會(huì)，我們將不斷地尋找新的改進(jìn)方法，對我們未來的成功，運(yùn)籌學(xué)和管理科學(xué)將發(fā)揮至關(guān)重要的作用。”問題 利用你所學(xué)運(yùn)籌學(xué)知識，提出自己的合理化建議與改進(jìn)方法，以增加管理效益。 實(shí)訓(xùn)設(shè)計(jì)【實(shí)訓(xùn)目標(biāo)】 掌握運(yùn)輸問題模型的建立和表上作業(yè)法解法。【實(shí)訓(xùn)內(nèi)容與要求】 在企業(yè)內(nèi)部根據(jù)歷史數(shù)據(jù)和調(diào)研獲得運(yùn)輸平衡表和單位運(yùn)價(jià)表。在安排工作時(shí)，能用數(shù)學(xué)語言描述完成運(yùn)輸任務(wù)的各種限制條件。建立相應(yīng)的產(chǎn)銷平衡運(yùn)輸問題模型，并利用表上