物流管理8第八章運(yùn)輸合理化1

1、一、不合理運(yùn)輸一、不合理運(yùn)輸 商品不合理運(yùn)輸，是指在組織貨物運(yùn)輸過程中，商品不合理運(yùn)輸，是指在組織貨物運(yùn)輸過程中，違反貨物流通規(guī)律，不按經(jīng)濟(jì)區(qū)域和貨物自然流向違反貨物流通規(guī)律，不按經(jīng)濟(jì)區(qū)域和貨物自然流向組織貨物調(diào)運(yùn)，忽視運(yùn)輸工具的充分利用和合理分組織貨物調(diào)運(yùn)，忽視運(yùn)輸工具的充分利用和合理分工，裝載量低，流轉(zhuǎn)環(huán)節(jié)多，從而浪費(fèi)運(yùn)力和加大工，裝載量低，流轉(zhuǎn)環(huán)節(jié)多，從而浪費(fèi)運(yùn)力和加大運(yùn)輸費(fèi)用的現(xiàn)象。運(yùn)輸費(fèi)用的現(xiàn)象。 返程或起程空駛。返程或起程空駛。 對(duì)流運(yùn)輸對(duì)流運(yùn)輸 迂回運(yùn)輸迂回運(yùn)輸 倒流運(yùn)輸?shù)沽鬟\(yùn)輸 重復(fù)運(yùn)輸重復(fù)運(yùn)輸 過遠(yuǎn)運(yùn)輸過遠(yuǎn)運(yùn)輸 運(yùn)力選擇不當(dāng)運(yùn)力選擇不當(dāng) 托運(yùn)方式選擇不當(dāng)托運(yùn)方式選擇不當(dāng) 2不

2、合理運(yùn)輸?shù)谋憩F(xiàn)不合理運(yùn)輸?shù)谋憩F(xiàn)棄水走路棄水走路鐵路、大型船舶的過近運(yùn)輸鐵路、大型船舶的過近運(yùn)輸運(yùn)輸工具承載能力選擇不當(dāng)運(yùn)輸工具承載能力選擇不當(dāng)二、運(yùn)輸合理化二、運(yùn)輸合理化 運(yùn)輸合理化就是按照貨物流通的規(guī)律，用運(yùn)輸合理化就是按照貨物流通的規(guī)律，用最少的勞動(dòng)消耗，達(dá)到最大的經(jīng)濟(jì)效益，來組最少的勞動(dòng)消耗，達(dá)到最大的經(jīng)濟(jì)效益，來組織貨物調(diào)運(yùn)。即在有利于生產(chǎn)，有利于市場(chǎng)供織貨物調(diào)運(yùn)。即在有利于生產(chǎn)，有利于市場(chǎng)供應(yīng)，有利于節(jié)約流通費(fèi)用和節(jié)約運(yùn)力、勞動(dòng)力應(yīng)，有利于節(jié)約流通費(fèi)用和節(jié)約運(yùn)力、勞動(dòng)力的前提下，使貨物走最短的里程，經(jīng)最少的環(huán)的前提下，使貨物走最短的里程，經(jīng)最少的環(huán)節(jié)，用最快的時(shí)間，以最小的損耗，花最

3、省的節(jié)，用最快的時(shí)間，以最小的損耗，花最省的費(fèi)用，把貨物從生產(chǎn)地運(yùn)到消費(fèi)地。費(fèi)用，把貨物從生產(chǎn)地運(yùn)到消費(fèi)地。 2、運(yùn)輸合理化的影響因素、運(yùn)輸合理化的影響因素 運(yùn)輸距離運(yùn)輸距離 運(yùn)輸環(huán)節(jié)運(yùn)輸環(huán)節(jié) 運(yùn)輸工具運(yùn)輸工具 運(yùn)輸時(shí)間運(yùn)輸時(shí)間 運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用3、運(yùn)輸合理化的措施、運(yùn)輸合理化的措施提高運(yùn)輸工具實(shí)載率提高運(yùn)輸工具實(shí)載率采取減少動(dòng)力投入，增加運(yùn)輸能力采取減少動(dòng)力投入，增加運(yùn)輸能力 的有的有 效措施求得合理化效措施求得合理化發(fā)展社會(huì)化的運(yùn)輸體系發(fā)展社會(huì)化的運(yùn)輸體系開展中短距離鐵路公路分流，開展中短距離鐵路公路分流，“以公代以公代鐵鐵”的運(yùn)輸?shù)倪\(yùn)輸盡量發(fā)展直達(dá)運(yùn)輸盡量發(fā)展直達(dá)運(yùn)輸配載運(yùn)輸配載運(yùn)輸組織

4、組織“四就直撥四就直撥”運(yùn)輸運(yùn)輸合裝整車運(yùn)輸合裝整車運(yùn)輸提高技術(shù)裝載量提高技術(shù)裝載量就廠直拔就廠直拔就站直撥就站直撥就庫直撥就庫直撥就車就車(船船)過載過載 決定運(yùn)輸方式，可以在考慮具體條件的基礎(chǔ)決定運(yùn)輸方式，可以在考慮具體條件的基礎(chǔ)上，對(duì)下述五個(gè)具體項(xiàng)目認(rèn)真研究考慮：上，對(duì)下述五個(gè)具體項(xiàng)目認(rèn)真研究考慮：三、運(yùn)輸方式的選擇三、運(yùn)輸方式的選擇貨物品種貨物品種運(yùn)輸期限運(yùn)輸期限運(yùn)輸成本運(yùn)輸成本運(yùn)輸距離運(yùn)輸距離運(yùn)輸批量運(yùn)輸批量 （一）、成本比較法（一）、成本比較法1 1、運(yùn)輸成本結(jié)構(gòu)、運(yùn)輸成本結(jié)構(gòu)變動(dòng)成本變動(dòng)成本固定成本固定成本聯(lián)合成本聯(lián)合成本公共成本公共成本【例【例2.12.1 】 某企業(yè)欲將其產(chǎn)品

5、從坐落位置某企業(yè)欲將其產(chǎn)品從坐落位置a a的工廠運(yùn)往坐落位置的工廠運(yùn)往坐落位置b b的公司的自有倉庫，年運(yùn)量的公司的自有倉庫，年運(yùn)量d d為為700000700000件，每件產(chǎn)品的價(jià)格件，每件產(chǎn)品的價(jià)格c c為為3030元，每年的存貨成本元，每年的存貨成本i i為產(chǎn)品價(jià)格的為產(chǎn)品價(jià)格的30%30%。q q為年存貨量。為年存貨量。企業(yè)希望選擇總成本最小的運(yùn)輸方式。各種運(yùn)輸方式有關(guān)參企業(yè)希望選擇總成本最小的運(yùn)輸方式。各種運(yùn)輸方式有關(guān)參數(shù)如下。數(shù)如下。 其中，在途運(yùn)輸?shù)哪甑讕齑娉杀緸槠渲?，在途運(yùn)輸?shù)哪甑讕齑娉杀緸閕cdt/365,兩端儲(chǔ)存點(diǎn)兩端儲(chǔ)存點(diǎn)的存貨成本各為的存貨成本各為icq/2，但其中的，

6、但其中的c有差別：工廠端的有差別：工廠端的c為產(chǎn)為產(chǎn)品價(jià)格，購買者端的品價(jià)格，購買者端的c為產(chǎn)品價(jià)格和運(yùn)輸費(fèi)率之和。為產(chǎn)品價(jià)格和運(yùn)輸費(fèi)率之和。 試求總成本最低的運(yùn)輸方式。試求總成本最低的運(yùn)輸方式。運(yùn)輸方式運(yùn)輸方式費(fèi)率費(fèi)率（元（元 /件）件）r運(yùn)達(dá)時(shí)間運(yùn)達(dá)時(shí)間（天）（天）t平均存貨量（件）平均存貨量（件）q/2鐵路鐵路0.1021100000駝背運(yùn)輸駝背運(yùn)輸0.1514500000.93公路公路0.2014500000.84航空航空1.402250000.81【例例2.1 答案答案】成本成本類型類型計(jì)算方法計(jì)算方法運(yùn)輸方式運(yùn)輸方式鐵路鐵路公路公路航空航空運(yùn)輸運(yùn)輸rd0.1700000=70000

7、0.2700000=1400001.4700000=980000在途在途存貨存貨icdt/365(0.33070000021) / 365=362465(0.33070000014) / 365=241644(0.3307000002) / 365=34521工廠工廠存貨存貨icq/20.330100000=9000000.3305000000.84=3780000.3302500000.81=182250倉庫倉庫存貨存貨icq/20.330.1100000=9030000.330.25000000.84=3805200.331.42500000.81=190755總成總成本本22354651

8、14016413875262、考慮競(jìng)爭(zhēng)因素法、考慮競(jìng)爭(zhēng)因素法【例【例2.2 】 某制造商分別從兩個(gè)供應(yīng)商處購買了共某制造商分別從兩個(gè)供應(yīng)商處購買了共3000個(gè)零件，每個(gè)個(gè)零件，每個(gè)零件單價(jià)零件單價(jià)100元。目前這元。目前這3000個(gè)零件由兩個(gè)供應(yīng)商提供，如供應(yīng)個(gè)零件由兩個(gè)供應(yīng)商提供，如供應(yīng)商縮短運(yùn)輸時(shí)間，則可以多得到交易份額，每縮短一天，便可商縮短運(yùn)輸時(shí)間，則可以多得到交易份額，每縮短一天，便可以從總交易中多得以從總交易中多得5%的份額，即的份額，即150個(gè)零件。供應(yīng)商從每個(gè)零個(gè)零件。供應(yīng)商從每個(gè)零件可賺得占零件價(jià)格（不包括運(yùn)輸費(fèi)用）件可賺得占零件價(jià)格（不包括運(yùn)輸費(fèi)用）20%的利潤(rùn)。于是供的利

9、潤(rùn)。于是供應(yīng)商應(yīng)商a考慮，如將運(yùn)輸方式從鐵路轉(zhuǎn)為公路或航空運(yùn)輸是否有利考慮，如將運(yùn)輸方式從鐵路轉(zhuǎn)為公路或航空運(yùn)輸是否有利可圖。各種運(yùn)輸方式的運(yùn)輸費(fèi)率和運(yùn)輸時(shí)間如下?？蓤D。各種運(yùn)輸方式的運(yùn)輸費(fèi)率和運(yùn)輸時(shí)間如下。運(yùn)輸方式費(fèi)率（元/件）運(yùn)輸時(shí)間（天）鐵路2.507公路6.004航空10.352運(yùn)輸方式零件銷售量（個(gè)）毛利（元）運(yùn)輸成本（元）凈利潤(rùn)（元）鐵路15001500*100*0.2=30000375026250公路1200+150*3=19501950*100*0.2=390001170027300航空1500+150*5=22502250*100*0.2=4500023287.521712.

10、5【例【例2.2 答案】答案】故，如果制造商對(duì)能提供更好運(yùn)輸服務(wù)多得供應(yīng)商給予故，如果制造商對(duì)能提供更好運(yùn)輸服務(wù)多得供應(yīng)商給予更多的交易份額的承諾兌現(xiàn)，則供應(yīng)商更多的交易份額的承諾兌現(xiàn)，則供應(yīng)商a應(yīng)當(dāng)選擇公路運(yùn)輸。應(yīng)當(dāng)選擇公路運(yùn)輸。 第三節(jié)第三節(jié) 運(yùn)運(yùn) 輸輸 優(yōu)優(yōu) 化化一、運(yùn)輸?shù)膬?yōu)化模型一、運(yùn)輸?shù)膬?yōu)化模型 1、運(yùn)輸數(shù)學(xué)模型、運(yùn)輸數(shù)學(xué)模型 運(yùn)輸問題可以描述為：將物品由運(yùn)輸問題可以描述為：將物品由m個(gè)起始地運(yùn)個(gè)起始地運(yùn)到到n個(gè)目的地。已知由第個(gè)目的地。已知由第i個(gè)起運(yùn)地到第個(gè)起運(yùn)地到第j個(gè)目的地的個(gè)目的地的單位運(yùn)費(fèi)是單位運(yùn)費(fèi)是 ，并假定運(yùn)費(fèi)與兩地間的運(yùn)量成正，并假定運(yùn)費(fèi)與兩地間的運(yùn)量成正比。設(shè)比。

11、設(shè) 表示表示 i 地的供應(yīng)量，地的供應(yīng)量， 表示表示 j 地的需求地的需求量。引進(jìn)決策變量量。引進(jìn)決策變量 表示從表示從 i 地到地到 j 地的運(yùn)輸?shù)氐倪\(yùn)輸量。問題是如何調(diào)運(yùn)該物品才能使總費(fèi)用最少。量。問題是如何調(diào)運(yùn)該物品才能使總費(fèi)用最少。ijciajbjixminjijijxcz11min), 2 , 1;, 2 , 1(0), 2 , 1(), 2 , 1(11njmixnjbxmiaxijjmiijinjij該題數(shù)學(xué)模型：該題數(shù)學(xué)模型：求求滿足滿足約束約束條件條件 供銷平衡運(yùn)輸問題。供銷平衡運(yùn)輸問題。 即各地供應(yīng)量等于各地的需求量。即各地供應(yīng)量等于各地的需求量。 數(shù)學(xué)公式表示為：數(shù)學(xué)公式

12、表示為：minjjiba11【例【例2.3 2.3 】某公司經(jīng)銷甲產(chǎn)品?！磕彻窘?jīng)銷甲產(chǎn)品。它下設(shè)三個(gè)加工廠。每日的產(chǎn)量它下設(shè)三個(gè)加工廠。每日的產(chǎn)量分別是：分別是：a1a1為為7 7噸，噸，a2a2為為4 4噸，噸，a3a3為為9 9噸。該公司把這噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各銷售點(diǎn)每日銷量為：些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各銷售點(diǎn)每日銷量為：b1b1為為3 3噸，噸，b2b2為為6 6噸，噸，b3b3為為5 5噸，噸，b4b4為為6 6噸。已知從各噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如下表所示。問工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如下表所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需

13、要量的該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。前提下，使總運(yùn)費(fèi)為最少。 供銷不平衡運(yùn)輸問題。供銷不平衡運(yùn)輸問題。 即各地供應(yīng)量不等于各地的需求量。即各地供應(yīng)量不等于各地的需求量。 數(shù)學(xué)公式表示為：數(shù)學(xué)公式表示為：供大于需：供大于需：供小于需：供小于需：minjjiba11minjjiba11【例【例2.4 】設(shè)有三個(gè)化肥廠】設(shè)有三個(gè)化肥廠(a，b，c)供應(yīng)四供應(yīng)四個(gè)地區(qū)個(gè)地區(qū)(，)的農(nóng)用化肥。假定等的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到

14、各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如表各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如表3-25所示。試所示。試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。 增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為02、最小元素法。、最小元素法。 此方法的基本此方法的基本思想是就近供應(yīng)，思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后定供銷關(guān)系，然后次小。一直到給出次小。一直到給出初始基可行解為止。初始基可行解為止。此案例的總運(yùn)費(fèi)為此案例的總運(yùn)費(fèi)為86元元3、伏格爾法、伏格爾法 最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，

15、有時(shí)造成在其他處要多花幾倍的運(yùn)費(fèi)。伏用，有時(shí)造成在其他處要多花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。用最小運(yùn)費(fèi)調(diào)運(yùn)。 伏格爾法的步驟是：伏格爾法的步驟是：n 分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額。由以上可見：伏格爾法同最小元素法除在由以上可見：伏格爾法同最小元素法除在確定

16、供求關(guān)系的原則上不同外，其余步驟確定供求關(guān)系的原則上不同外，其余步驟相同。伏格爾法給出的初始解比用最小元相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。素法給出的初始解更接近最優(yōu)解。4、最優(yōu)解的判別、最優(yōu)解的判別 判別的方法是計(jì)算空格判別的方法是計(jì)算空格(非基變量非基變量)的的檢驗(yàn)數(shù)。因運(yùn)輸問題的目標(biāo)函數(shù)是要求實(shí)檢驗(yàn)數(shù)。因運(yùn)輸問題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，故當(dāng)所有的非基變量大于零時(shí)，現(xiàn)最小化，故當(dāng)所有的非基變量大于零時(shí)，為最優(yōu)解。下面介紹一種求空格檢驗(yàn)數(shù)的為最優(yōu)解。下面介紹一種求空格檢驗(yàn)數(shù)的方法。方法。 閉回路法閉回路法 如果已確定了某一調(diào)運(yùn)方案，我們從某如果已確定了某一調(diào)

17、運(yùn)方案，我們從某一空格出發(fā)（無調(diào)運(yùn)量的格子），沿水平方一空格出發(fā)（無調(diào)運(yùn)量的格子），沿水平方向或垂直方向前進(jìn)，遇到某一個(gè)適當(dāng)有調(diào)運(yùn)向或垂直方向前進(jìn)，遇到某一個(gè)適當(dāng)有調(diào)運(yùn)量的格子就轉(zhuǎn)向量的格子就轉(zhuǎn)向 繼續(xù)前進(jìn)。如此繼續(xù)下去，繼續(xù)前進(jìn)。如此繼續(xù)下去，經(jīng)過若干次，就一定回到原來出發(fā)的空格。經(jīng)過若干次，就一定回到原來出發(fā)的空格。這樣形成的一條由水平和垂直線段組成的封這樣形成的一條由水平和垂直線段組成的封閉折線稱為閉折線稱為閉回路法閉回路法。 閉回路法閉回路法n在給出調(diào)運(yùn)方案的計(jì)算表上，如表3-13，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時(shí)可以轉(zhuǎn)90后，繼續(xù)

18、前進(jìn)，直到回到起始空格為止。閉回路如圖3-1的(a),(b),(c)等所示。 銷 地 加工廠 b1 b2 b3 b4 產(chǎn)量 a1 a2 a3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 可見這調(diào)整的方案使運(yùn)費(fèi)增加可見這調(diào)整的方案使運(yùn)費(fèi)增加(+1)(+1)3+(-1)3+(-1)3+(+1)3+(+1)2+(-1)2+(-1)=1(=1(元元) )這表明若這樣調(diào)整運(yùn)量將增加運(yùn)費(fèi)。這表明若這樣調(diào)整運(yùn)量將增加運(yùn)費(fèi)。將將“1”1”這個(gè)數(shù)填入這個(gè)數(shù)填入(a1(a1，b1)b1)格，這就是格，這就是檢驗(yàn)數(shù)。按以上所述，可找出所有空格的檢驗(yàn)數(shù)，檢驗(yàn)數(shù)。按以上所述，可找出所有空格的檢驗(yàn)數(shù)，見表見

19、表3-153-15空格 閉 回 路 檢驗(yàn)數(shù) (11) (12) (22) (24) (31) (33) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(12) (22)-(23)-(13)-(14)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24) (31)-(34)-(14)-(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1 10 12 當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)，當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)，n 當(dāng)在表中空

20、格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得最優(yōu)解。若有兩個(gè)和兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格為調(diào)入格。即以它對(duì)應(yīng)的非基變量為換入變量。以此格為出發(fā)點(diǎn)，作一閉回路，如表2-19所示。表 2-19銷 地 加工廠 b1 b2 b3 b4 產(chǎn)量 a1 a2 a3 3 6 4(+1) 1(-1) 3(-1) (+1) 3 7 4 9 銷量 3 6 5 6 (2(2，4)4)格的調(diào)入量格的調(diào)入量是選擇閉回路上具有是選擇閉回路上具有(-1)(-1)的數(shù)字格中的數(shù)字格中的最小者。即的最小者。即=min(1,3)=1(=min(1,3)=1(其原理與單純形法中按其原理與單純形法中按規(guī)規(guī)劃來確定換

21、出變量相同劃來確定換出變量相同) )。然后按閉回路上的正、負(fù)號(hào)，加。然后按閉回路上的正、負(fù)號(hào)，加入和減去此值，得到調(diào)整方案，如表入和減去此值，得到調(diào)整方案，如表3-203-20所示。所示。銷 地 加工廠 b1 b2 b3 b4 產(chǎn)量 a1 a2 a3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 對(duì)表3-20給出的解，再用閉回路法或位勢(shì)法求各空格的檢驗(yàn)數(shù)，見表3-21。表中的所有檢驗(yàn)數(shù)都非負(fù)，故表3-20中的解為最優(yōu)解。這時(shí)得到的總運(yùn)費(fèi)最小是85元。 銷 地 加工廠 b1 b2 b3 b4 a1 a2 a3 0 9 2 2 1 12 4、圖上作業(yè)法。、圖上作業(yè)法?；舅悸罚夯舅悸?/p>

22、：1. 破圈法編制初始方案。打破每一回路中距離破圈法編制初始方案。打破每一回路中距離最長(zhǎng)的一段，并在交通圖上，從破開的線段端最長(zhǎng)的一段，并在交通圖上，從破開的線段端點(diǎn)開始，依照右手原則，用符號(hào)點(diǎn)開始，依照右手原則，用符號(hào)標(biāo)出物資流標(biāo)出物資流向：即符號(hào)向：即符號(hào)始終在以輸出地為起點(diǎn)、以輸入始終在以輸出地為起點(diǎn)、以輸入地為終點(diǎn)的交通路線的右邊。以圓圈加數(shù)字的地為終點(diǎn)的交通路線的右邊。以圓圈加數(shù)字的形式將運(yùn)輸量標(biāo)注在符號(hào)形式將運(yùn)輸量標(biāo)注在符號(hào)旁邊。旁邊。2. 檢驗(yàn)：每一回路的內(nèi)外圈長(zhǎng)如果均不大于該檢驗(yàn)：每一回路的內(nèi)外圈長(zhǎng)如果均不大于該回路的半圈長(zhǎng)，該回路的半圈長(zhǎng)，該 方案已經(jīng)最優(yōu)；否則進(jìn)方案已經(jīng)最優(yōu)

23、；否則進(jìn)行調(diào)整。行調(diào)整。3. 調(diào)整：找出有問題圈中的最小運(yùn)量邊，該圈調(diào)整：找出有問題圈中的最小運(yùn)量邊，該圈各邊減去此最小運(yùn)量，該回路剩余各邊加上此各邊減去此最小運(yùn)量，該回路剩余各邊加上此最小運(yùn)量。最小運(yùn)量。4. 重復(fù)步驟重復(fù)步驟23，直到每一回路都達(dá)到最優(yōu)。，直到每一回路都達(dá)到最優(yōu)。該調(diào)運(yùn)方案即為最優(yōu)。該調(diào)運(yùn)方案即為最優(yōu)?！纠纠?.6】：某制造企業(yè)有專門為產(chǎn)品生產(chǎn)工：某制造企業(yè)有專門為產(chǎn)品生產(chǎn)工廠提供零部件和半成品的零部件制造廠，共廠提供零部件和半成品的零部件制造廠，共有有s1、s2、s3、s4、s5、s6、s7七個(gè)零部件七個(gè)零部件制造廠和制造廠和d1、d2、d3、d4、d5、d6、d7七個(gè)

24、產(chǎn)品生產(chǎn)工廠。各零部件制造廠的產(chǎn)量七個(gè)產(chǎn)品生產(chǎn)工廠。各零部件制造廠的產(chǎn)量（橢圓框內(nèi)數(shù)字）、各生產(chǎn)工廠的零部件需（橢圓框內(nèi)數(shù)字）、各生產(chǎn)工廠的零部件需求量（矩形框內(nèi)數(shù)字）以及他們的位置和相求量（矩形框內(nèi)數(shù)字）以及他們的位置和相互距離如圖互距離如圖1所示。其中產(chǎn)量和需求量單位所示。其中產(chǎn)量和需求量單位為噸，距離單位為公里，請(qǐng)利用圖上作業(yè)法為噸，距離單位為公里，請(qǐng)利用圖上作業(yè)法確定最佳的零部件調(diào)運(yùn)方案。確定最佳的零部件調(diào)運(yùn)方案。解：解：1.在唯一的回路中，距離為在唯一的回路中，距離為85的一段的一段最長(zhǎng)，斷開此段。并以供方最長(zhǎng)，斷開此段。并以供方190開始編制開始編制初始調(diào)運(yùn)方案，初始調(diào)運(yùn)方案，標(biāo)注

25、如圖標(biāo)注如圖22.對(duì)該回路進(jìn)行檢驗(yàn)：對(duì)該回路進(jìn)行檢驗(yàn)：內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)=0，外圈長(zhǎng)外圈長(zhǎng)=70+80+70+75+60=355，該回路總長(zhǎng)該回路總長(zhǎng)=355+85=440，半圈長(zhǎng)半圈長(zhǎng)=440/2=220內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)半圈長(zhǎng)，半圈長(zhǎng)，需要對(duì)外圈進(jìn)行調(diào)整。需要對(duì)外圈進(jìn)行調(diào)整。3 . 在初始方案中，外圈的最小運(yùn)量為在初始方案中，外圈的最小運(yùn)量為10，外，外圈各邊調(diào)運(yùn)量都減去圈各邊調(diào)運(yùn)量都減去10，回路剩余各邊加上，回路剩余各邊加上10。第一次調(diào)整后的調(diào)運(yùn)方案如圖。第一次調(diào)整后的調(diào)運(yùn)方案如圖3所示：所示： 4.對(duì)新方案進(jìn)行檢驗(yàn)：對(duì)新方案進(jìn)行檢驗(yàn)：內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)=85，外圈長(zhǎng)外圈長(zhǎng)=70+80+70+60=2

26、80，該回路總長(zhǎng)該回路總長(zhǎng)=355+85=440，半圈長(zhǎng)半圈長(zhǎng)=440/2=220內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)半圈長(zhǎng)，需要對(duì)半圈長(zhǎng)，需要對(duì)外圈進(jìn)行第二次調(diào)整。外圈進(jìn)行第二次調(diào)整。5.當(dāng)前，外圈的最小運(yùn)量為當(dāng)前，外圈的最小運(yùn)量為40。第二次調(diào)整后。第二次調(diào)整后的調(diào)運(yùn)方案如圖的調(diào)運(yùn)方案如圖4所示：所示： 6.對(duì)第二次調(diào)整后的新方案進(jìn)行檢驗(yàn)：對(duì)第二次調(diào)整后的新方案進(jìn)行檢驗(yàn)：內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)=85+75=160，外圈長(zhǎng)外圈長(zhǎng)=70+70+60=200，該回路總長(zhǎng)該回路總長(zhǎng)=355+85=440，半圈長(zhǎng)半圈長(zhǎng)=440/2=220內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)半圈長(zhǎng)，外圈長(zhǎng)半圈長(zhǎng)，外圈長(zhǎng)半圈長(zhǎng)。半圈長(zhǎng)。該方案達(dá)到最優(yōu)。該方案達(dá)到最優(yōu)。 案例案

27、例1:甲公司要從位于甲公司要從位于s市的工廠直接裝運(yùn)市的工廠直接裝運(yùn)500臺(tái)電視機(jī)送往位于臺(tái)電視機(jī)送往位于t市市的一個(gè)批發(fā)心這票貨物價(jià)值為的一個(gè)批發(fā)心這票貨物價(jià)值為150萬元。萬元。t市的批發(fā)中心確定這批貨市的批發(fā)中心確定這批貨物的標(biāo)準(zhǔn)運(yùn)輸時(shí)間為物的標(biāo)準(zhǔn)運(yùn)輸時(shí)間為2.5天，如果天，如果 超出標(biāo)準(zhǔn)時(shí)間，每臺(tái)電視機(jī)的每超出標(biāo)準(zhǔn)時(shí)間，每臺(tái)電視機(jī)的每天的機(jī)會(huì)成本是天的機(jī)會(huì)成本是30元。甲公司的物流經(jīng)理設(shè)計(jì)了下述三個(gè)物流方案，元。甲公司的物流經(jīng)理設(shè)計(jì)了下述三個(gè)物流方案，請(qǐng)從成本角度評(píng)價(jià)這些運(yùn)輸方案的優(yōu)劣。請(qǐng)從成本角度評(píng)價(jià)這些運(yùn)輸方案的優(yōu)劣。 （1）a公司是一家長(zhǎng)途貨物運(yùn)輸企業(yè)，可以按照優(yōu)惠費(fèi)率每公里公司

28、是一家長(zhǎng)途貨物運(yùn)輸企業(yè)，可以按照優(yōu)惠費(fèi)率每公里0.05元元/臺(tái)來運(yùn)送這批電視機(jī)，裝卸費(fèi)為每臺(tái)臺(tái)來運(yùn)送這批電視機(jī)，裝卸費(fèi)為每臺(tái)0.10元。已知元。已知s市到市到t市的市的公路運(yùn)輸里程為公路運(yùn)輸里程為1100公里，估計(jì)需要公里，估計(jì)需要3天的時(shí)間才可以運(yùn)到天的時(shí)間才可以運(yùn)到(因?yàn)樨浺驗(yàn)樨浳镅b卸也需要時(shí)間物裝卸也需要時(shí)間)。（2）b公司是一家水運(yùn)企業(yè)，可以提供水陸聯(lián)運(yùn)服務(wù)，即先用汽車公司是一家水運(yùn)企業(yè)，可以提供水陸聯(lián)運(yùn)服務(wù)，即先用汽車從甲公司的倉庫將貨物運(yùn)至從甲公司的倉庫將貨物運(yùn)至s市的碼頭市的碼頭(20公里公里)，再用船運(yùn)至，再用船運(yùn)至t市的碼市的碼頭頭(1200公里公里)，然后再用汽車從碼頭，然

29、后再用汽車從碼頭 運(yùn)至批發(fā)中心運(yùn)至批發(fā)中心(17公里公里)。由于中。由于中 轉(zhuǎn)的過程中需要多次裝卸，因此整個(gè)運(yùn)輸時(shí)間大約為轉(zhuǎn)的過程中需要多次裝卸，因此整個(gè)運(yùn)輸時(shí)間大約為5 天。詢價(jià)后天。詢價(jià)后得知，陸運(yùn)運(yùn)費(fèi)為每公里得知，陸運(yùn)運(yùn)費(fèi)為每公里0.06元元/臺(tái)，裝卸費(fèi)為每臺(tái)臺(tái)，裝卸費(fèi)為每臺(tái)0.10元，水運(yùn)運(yùn)元，水運(yùn)運(yùn)費(fèi)為每百臺(tái)費(fèi)為每百臺(tái)0.6元。元。 (3)c公司是一家物流企業(yè)，可以提供全方位的物流服務(wù)，報(bào)價(jià)為公司是一家物流企業(yè)，可以提供全方位的物流服務(wù)，報(bào)價(jià)為22800元。它承諾在標(biāo)準(zhǔn)時(shí)間內(nèi)運(yùn)到，但是準(zhǔn)點(diǎn)的百分率為元。它承諾在標(biāo)準(zhǔn)時(shí)間內(nèi)運(yùn)到，但是準(zhǔn)點(diǎn)的百分率為80。 5、 最短路問題 最短路問題是重

30、要的最優(yōu)化問題之一，最短路問題是重要的最優(yōu)化問題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題，如管道鋪設(shè)、線路選擇，設(shè)備更多問題，如管道鋪設(shè)、線路選擇，設(shè)備更新、投資等問題，而且經(jīng)常被作為一個(gè)基新、投資等問題，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它的優(yōu)化問題本工具，用于解決其它的優(yōu)化問題。 給定一個(gè)賦權(quán)有向圖給定一個(gè)賦權(quán)有向圖d = (v,a)，記，記d中中每一條弧每一條弧 上的權(quán)為上的權(quán)為 。給定給定d中一個(gè)起點(diǎn)中一個(gè)起點(diǎn) 和和 終點(diǎn)，設(shè)終點(diǎn)，設(shè)p是是d中從中從vs 到到 vt的一條路。則定義路的一條路。則定義路p的權(quán)是的權(quán)是p中所有弧中所有弧的權(quán)之

31、和。記為的權(quán)之和。記為 ，即，即 ),(jiijvvaijijijwaw)(.)(),(jivvijwpw .)(),(jivvijwpw又若又若p*是是d圖中圖中 到到 的一條路，且滿足的一條路，且滿足.| )(min)(*的路到為tsvvppwpw 式中對(duì)式中對(duì)d的所有從的所有從 到到 的路的路p取最小，則稱取最小，則稱p*為從為從vs到到 vt的最短路，的最短路， 為從為從vs到到vt的最短的最短距離。距離。 在一個(gè)圖在一個(gè)圖d=（v，a）中，求從）中，求從vs 到到vt的的最短路和最短距離的問題就稱為最短路和最短距離的問題就稱為最短路問題最短路問題。最短路的算法最短路的算法dijkst

32、ra算法算法 dijkstra算法是算法是e.w. dijkstra于于1959年提出的，是目前公認(rèn)的對(duì)所有權(quán)非負(fù)的年提出的，是目前公認(rèn)的對(duì)所有權(quán)非負(fù)的情況的最好算法。情況的最好算法。 設(shè)設(shè)d=(v,a,d=(v,a,w w) )滿足上述定理?xiàng)l件，則有以下算滿足上述定理?xiàng)l件，則有以下算法：法： 令令u u1 1=0,=0,u uj jw wijij( (若不存在點(diǎn)若不存在點(diǎn)1 1到點(diǎn)到點(diǎn)j j的路則的路則記記w w1j1j=),p=1,t=2,3,=),p=1,t=2,3,n(p,n(p為以確定的為以確定的點(diǎn)之集，點(diǎn)之集，t t為未確定的點(diǎn)之集為未確定的點(diǎn)之集) )； （指出永久標(biāo)號(hào)）在（指出

33、永久標(biāo)號(hào)）在t t中找出一點(diǎn)中找出一點(diǎn)k k使得使得u uk k=u uj j 。令。令p:=pk,t=tk,p:=pk,t=tk,若若t=t=空集算空集算法結(jié)束，并令法結(jié)束，并令d di i= =u ui i(i=1,2,(i=1,2,n),n),否則進(jìn)入否則進(jìn)入(3)(3)； （修改臨時(shí)標(biāo)號(hào)）對(duì)（修改臨時(shí)標(biāo)號(hào)）對(duì)t t中每一個(gè)點(diǎn)中每一個(gè)點(diǎn)j j，令，令u uj j=min=minu uj j, ,u uk k+ +w wijij ，然后返回，然后返回。 例例6.2.16.2.1求圖求圖6-2-16-2-1中點(diǎn)中點(diǎn)v v1 1到其它各點(diǎn)的最短到其它各點(diǎn)的最短路（弧旁的數(shù)字表示距離）。路（弧旁的數(shù)字表示距離）。 解解 用用dijkstra