第3章-運(yùn)輸問題

第三章運(yùn)輸問題§1運(yùn)輸問題的典例和數(shù)學(xué)模型§2表上作業(yè)法§3產(chǎn)銷不平衡的運(yùn)輸問題及其應(yīng)用§1運(yùn)輸問題的典例和數(shù)學(xué)模型1.1問題的提出例1：某公司從兩個(gè)產(chǎn)地A1，A2將物品運(yùn)往三個(gè)銷地B1，B2，B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地的每件物品的運(yùn)費(fèi)如下表所示。問如何調(diào)運(yùn)，使得總運(yùn)輸費(fèi)最?。慨a(chǎn)銷平衡及單位運(yùn)價(jià)表（運(yùn)輸表）：銷地產(chǎn)地B1B2B3產(chǎn)量A1646200A2655300銷量150150200··646655運(yùn)輸問題網(wǎng)絡(luò)圖：s3=300s1=200供應(yīng)量供應(yīng)地運(yùn)價(jià)需求地d1=150d2=150d3=200需求量設(shè)xij表示從產(chǎn)地Ai調(diào)運(yùn)到Bj的運(yùn)輸量。則安排的運(yùn)量列表如下：銷地產(chǎn)地B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200建立數(shù)學(xué)模型如下：1.2產(chǎn)銷平衡運(yùn)輸問題的一般數(shù)學(xué)模型：符號(hào)約定：A1，A2，…Am表示某種物資的m個(gè)產(chǎn)地；B1，B2，…Bn表示某種物資的n個(gè)銷地；si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)到Bj的單位運(yùn)價(jià)。一般運(yùn)輸問題的產(chǎn)銷平衡表運(yùn)價(jià)表：產(chǎn)銷平衡表§2表上作業(yè)法表上作業(yè)法是求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單純形法，所以也稱運(yùn)輸單純形法。表上作業(yè)法的步驟：找出初始基本可行解。求各非基變量的檢驗(yàn)數(shù)，判斷是否最優(yōu)。如最優(yōu)，停止計(jì)算，否則轉(zhuǎn)到下一步。確定入基變量與出基變量，找出新的基本可行解。重復(fù)2、3步驟直到得到最優(yōu)解。一、確定初始基本可行解運(yùn)輸問題的基變量個(gè)數(shù)為m+n-1。在產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格，其相應(yīng)數(shù)字表示調(diào)運(yùn)量。有數(shù)字格對(duì)應(yīng)基變量；空格對(duì)應(yīng)非基變量。銷地產(chǎn)地B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200銷地產(chǎn)地B1B2B3產(chǎn)量A150150200A2100200300銷量150150200方法：最小元素法Vogle法（最大差額法）1、最小元素法最小元素法的基本思想是就近供應(yīng)。即從單位運(yùn)價(jià)最小的變量開始分配運(yùn)輸量,依次類推,直到給出初始方案為止。

B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36562020314633注意事項(xiàng)：有兩個(gè)最小運(yùn)價(jià)時(shí)任選其一。在計(jì)算中（最后一步除外），當(dāng)選出最小元素后，如果所在行未分配產(chǎn)量剛好等于所在列尚未滿足的需求量，則在產(chǎn)銷平衡表上填上一個(gè)數(shù)后，需要?jiǎng)澣ヒ恍泻鸵涣校瑸槭褂袛?shù)字格仍為m+n-1，需要在同時(shí)劃去的該行或列的任一空格位置補(bǔ)填一個(gè)“0”。補(bǔ)“0”的原則：盡量先選運(yùn)費(fèi)小的實(shí)變量；補(bǔ)充后不能有某個(gè)基變量獨(dú)占一行一列B1B2B3B4產(chǎn)量A1311457A277384A3121069銷量3656202036例：0416判斷是否為基本可行解：表中填數(shù)字的格有m+n-1個(gè)。不存在有數(shù)字的格為頂點(diǎn)組成的閉回路。--存在有數(shù)字的格為頂點(diǎn)組成的閉回路，是指從調(diào)運(yùn)方案的任一有數(shù)字格出發(fā)，沿水平或垂直方向前進(jìn)，只有并且也只有碰到另一有數(shù)字的格才允許前進(jìn)方向轉(zhuǎn)90°，依次進(jìn)行下去，最后總能找到一條回到原出發(fā)點(diǎn)的數(shù)字格的回路。第一種閉回路：頂點(diǎn){x12、x13、x23、x22}構(gòu)成了閉回路。

銷地產(chǎn)地B1B2B3B4A1x12x13A2x22x23A3銷地產(chǎn)地B1B2B3B4A1x11x12A2x22x24A3x31x34第二種閉回路：頂點(diǎn){x11、x12、x22、x24、x34、x31、x11}構(gòu)成閉回路。

第三種閉回路：銷地產(chǎn)地B1B2B3B4A1x11x12A2x21x24A3x32x34x11、x12、x32、x34、x24、x21構(gòu)成一個(gè)閉回路2、Vogle法（最大差額法）

基本思想：考慮到一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。

2、Vogle法（最大差額法）基本步驟：（結(jié)合例題講）1、畫出作業(yè)表2、在運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行3、從行或列差額中選出最大者，選擇它所在行或列中的最小元素，確定該行的產(chǎn)量首先要保證最小元素的需求量，同時(shí)將運(yùn)價(jià)表中的列數(shù)字劃去。4、對(duì)運(yùn)價(jià)表中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。重復(fù)1、2步。直到給出初始解為止。2、Vogle法（最大差額法）對(duì)Vogel法的幾點(diǎn)說明：A、最大差額法得到的表中數(shù)字格也為m+n-1個(gè)；且滿足所有約束方程；且滿足無閉回路的條件；B、一般來說最大差額法給出的方案要比最小元素法要好。當(dāng)產(chǎn)銷地的數(shù)量不多時(shí)，Vogel法給出的初始方案有時(shí)就是最優(yōu)方案，所以，Vogel法有時(shí)就用作求運(yùn)輸問題最優(yōu)方案的近似解，但不一定對(duì)所有平衡問題都能給出最優(yōu)方案。

二、最優(yōu)解的判別檢驗(yàn)數(shù)的含義：假設(shè)在非基變量處增加一個(gè)運(yùn)量，形成的新運(yùn)輸方案與被檢驗(yàn)的運(yùn)輸方案的總運(yùn)費(fèi)之差。如果所有空格（非基變量）的檢驗(yàn)數(shù)均大于等于零，即，則達(dá)到最優(yōu)解。求檢驗(yàn)數(shù)的方法有兩種：閉回路法位勢法1、閉回路法從代表非基變量的空格出發(fā)，尋找一條除這個(gè)空格外，其余均由有數(shù)字格為頂點(diǎn)組成的閉回路。按“加奇減偶”方法計(jì)算運(yùn)費(fèi)的增加值，作為檢驗(yàn)數(shù)填入空格中。一個(gè)空格存在唯一閉回路。3146331非基變量x11檢驗(yàn)數(shù)的計(jì)算：B1B2B3B4產(chǎn)量A13113107（+1）（-1）A219284（-1）（+1）A3741059銷量36562020314633121-11012非基變量的檢驗(yàn)數(shù)表：B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36562020空格閉回路檢驗(yàn)數(shù)(A1,B1)(1,1)(1,3)(2,3)(2,1)(1,1)1(A1,B2)(1,2)(1,4)(3,4)(3,2)(1,2)2(A2,B2)(2,2)(2,3)(1,3)(1,4)(3,4)(3,2)(2,2)1(A2,B4)(2,4)(2,3)(3,3)(1,4)(2,4)-1(A3,B1)(3,1)(3,4)(1,4)(1,3)(2,3)(2,1)(3,1)10(A3,B3)(3,3)(3,4)(1,4)(1,3)(3,3)122、位勢法運(yùn)輸問題的對(duì)偶問題：如：2個(gè)產(chǎn)地，3個(gè)銷地的運(yùn)輸問題的對(duì)偶問題位勢法的基本原理：由線性規(guī)劃公式：σij=cij-CBB-1Pij=cij-(ui+vj)對(duì)于基變量，cij=ui+vj

。由m+n-1個(gè)基變量，可以列出m+n-1個(gè)等式。而共有m個(gè)ui

和n個(gè)vj

，所以可令任一個(gè)ui

或vj=0，從而解出其它m+n1個(gè)的值。（所以m個(gè)ui

和n個(gè)vj

的值不唯一。）對(duì)于非基變量，由σij=cij-（ui+vj）求得其檢驗(yàn)數(shù)。位勢法的操作：對(duì)運(yùn)輸表上每一行賦予一個(gè)數(shù)值ui，對(duì)每一列賦予一個(gè)數(shù)值vj，它們的數(shù)值由基變量（有數(shù)字格）xij的檢驗(yàn)數(shù)σij=cij-（ui+vj）=0即cij=ui+vj求得。在位勢法中只能令一個(gè)ui

或vj

為0；若不能求出全部ui和vj

，說明基變量未選夠或未選對(duì)。非基變量（空格）的檢驗(yàn)數(shù)由公式：

σij=cij-（ui+vj）求得。

B1B2B3B4A1310A212A345銷地產(chǎn)地B1B2B3B4行位勢uiA1310A212A345列位勢vj

0310-12-59運(yùn)價(jià)

B1B2B3B4A1310A212A345銷地產(chǎn)地B1B2B3B4行位勢uiA1310A212A345列位勢vj

10219-48B1B2B3B4uiA1311310A21928A374105vj2020314633121-11012前例的檢驗(yàn)數(shù)：（注意用“運(yùn)價(jià)”算）0310-12-59B1B2B3B4uiA1311310A21928A374105vj2020314633前例的檢驗(yàn)數(shù)：（注意用“運(yùn)價(jià)”算）01128-37121-11012求解過程中常出現(xiàn)的錯(cuò)誤：錯(cuò)誤地將運(yùn)輸表中基變量的解（即運(yùn)輸量）當(dāng)作運(yùn)價(jià)參與計(jì)算；不能正確畫閉合回路；初始解退化，未能補(bǔ)足基變量的個(gè)數(shù)。因此在位勢法中多次令某個(gè)ui

或vj

為0。三、改進(jìn)運(yùn)輸方案的辦法—閉回路調(diào)整法1、找入基變量（檢驗(yàn)數(shù)最小的空格對(duì)應(yīng)的變量）2、以xij為起點(diǎn)，尋找由原基變量構(gòu)成的閉合回路3、迭代計(jì)算。從xij出發(fā)，標(biāo)“+”，然后沿任一個(gè)方向?qū)芈讽旤c(diǎn)處的基變量依次標(biāo)“”和“+”，表示“”和“+”xij，從而使迭代后仍滿足分配的平衡。標(biāo)有“”的變量中最小值就是調(diào)整量，也是入基變量xij的值。標(biāo)有“”的變量減去調(diào)整量，標(biāo)有“+”的變量加上調(diào)整量。（加奇減偶）

4、用閉回路法或位勢法求新基變量的檢驗(yàn)數(shù)。若所有檢驗(yàn)數(shù)

≥0，則達(dá)到最優(yōu)，算法停止；否則返回第1步。迭代：（注意用“調(diào)運(yùn)量”算）B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36562020314633121-11012++--1250調(diào)整并求非基變量的檢驗(yàn)數(shù)：B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量365620203563210221912如何找多個(gè)最優(yōu)方案：如果某個(gè)非基變量（空格）的檢驗(yàn)數(shù)為0，說明有多個(gè)最優(yōu)解。把檢驗(yàn)數(shù)為0的變量作為入基變量，調(diào)整運(yùn)輸方案，即得到另一個(gè)最優(yōu)解。X11的檢驗(yàn)數(shù)為零，作為入基變量B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量365620203563210221912++--調(diào)整及用閉回路法求檢驗(yàn)數(shù)：：B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量365620205632312021912B1B2B3B4uiA13113100A21928-2A374105-5vj39310202013563用位勢法求檢驗(yàn)數(shù)：22021912

思路：產(chǎn)銷不平衡問題化為產(chǎn)銷平衡問題，再用表上作業(yè)法求解。產(chǎn)>銷時(shí)，假想一個(gè)銷地（實(shí)為庫存），該銷地需要量為總產(chǎn)量與總銷量之差，并在單位運(yùn)價(jià)表中將從各產(chǎn)地到假想銷地的單位運(yùn)價(jià)設(shè)為0。產(chǎn)<銷時(shí)，假想一個(gè)產(chǎn)地，該產(chǎn)地產(chǎn)量為總銷量與總產(chǎn)量之差，并在單位運(yùn)價(jià)表中將該假想產(chǎn)地到各銷地的單位運(yùn)價(jià)設(shè)為M?！?產(chǎn)銷不平衡的運(yùn)輸問題及其應(yīng)用例1：設(shè)有A1、A2、A3三個(gè)產(chǎn)地生產(chǎn)某種物資，其產(chǎn)量分別為7、5、7t，B1、B2、B3、B4