第3章-運輸問題

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

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

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

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

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

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

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

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

和n個vj

，所以可令任一個ui

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

和n個vj

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

或vj

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

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

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

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

0310-12-59運價

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

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

或vj

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

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

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

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