運輸問題薛迪復(fù)旦大學(xué)公共衛(wèi)生學(xué)院醫(yī)院管理學(xué)教研室TransportationProblem管理計劃組織生產(chǎn)1生產(chǎn)2生產(chǎn)3銷售1銷售4銷售2銷售3原材料1原材料2原材料3原材料4物流第一節(jié)運輸問題的數(shù)學(xué)模型例1：某制藥公司在全國設(shè)有3個生產(chǎn)基地，其中某品種藥的日產(chǎn)量為：A1廠700箱，A2廠400箱，A3廠900箱。這些生產(chǎn)基地每天將這些藥分別運往四個地區(qū)的經(jīng)銷部門，各經(jīng)銷部門每天的需求量為：B1部門300箱，B2部門600箱，B3部門500箱，B4部門600箱。已知從每個生產(chǎn)基地到各銷售部門每箱藥品的運價如表所示，問該制藥公司應(yīng)如何調(diào)運，使在滿足各銷售部門需要的情況下，總的運輸費用最少？表1各生產(chǎn)基地到各銷售部門每箱藥品的運費（單位：元）生產(chǎn)基地銷售部門B1B2B3B4A10.31.10.31.0A20.10.90.20.8A30.70.41.00.5

表2運輸表運輸問題數(shù)學(xué)模型的特點（1）約束條件系數(shù)矩陣中元素等于0或1；（2）約束條件系數(shù)矩陣的每一列有兩個非0元素，于每個變量在前m個約束方程和后n個約束方程中各出現(xiàn)一次相對應(yīng)。對于產(chǎn)銷平衡的運輸問題，還有以下兩個特點：（3）所有的結(jié)構(gòu)約束方程都是等式；（4）各產(chǎn)地的產(chǎn)量之和等于各銷地的銷量之和。例1問題的運輸表設(shè)X=（xij）為運輸問題的一個解，則要求每步得到的X都必須是基本可行解，這就要求：（1）X必須滿足模型中的所有約束條件；（2）基變量對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān)；（3）解中非0變量xij的個數(shù)不能多于（m+n-1）個；（4）基變量的個數(shù)在迭代過程中應(yīng)該保持為（m+n-1）個。例1問題的一個基本可行解對于產(chǎn)銷平衡的運輸問題，我們有以下3條結(jié)論：（1）基變量有m+n-1個；（2）一定有最優(yōu)解；（3）如果ai和bj都是整數(shù)，則一定有整數(shù)最優(yōu)解。第二節(jié)表上作業(yè)法一、初始基本可行解的求法——最小元素法二、解的最優(yōu)性檢驗——閉回路法11=c11-c21+c23-c13=0.3-0.1+0.2-0.3=0.131=c31-c21+c23-c13+c14-c34=0.7-0.1+0.2-0.3+1.0-0.5=1.0找出每一個空格(非基變量)的閉回路(只有一個頂點為空格，其他頂點均為填有數(shù)字的格)。

12=c12-c32+c34-c14=1.1-0.4+0.5-1.0=0.2

22=c22-c32+c34-c14+c13-c23=0.9-0.4+0.5-1.0+0.3-0.2=0.1

24=c24-c14+c13-c23=0.8-1.0+0.3-0.2=-0.1

33=c33-c34+c14-c13=1.0-0.5+1.0-0.3=1.2

注意：在運輸問題中通常目標(biāo)函數(shù)是求最小值，所以這時要求所有的檢驗數(shù)為正值。對于每一個非基變量，在運輸表中唯一對應(yīng)一條這樣的閉回路。不能出現(xiàn)全部頂點由填有數(shù)字的格構(gòu)成的閉回路。三、解的改進找出檢驗數(shù)ij為最小負值的格子的閉回路→在滿足所有約束條件的情況下，盡可能增大這個格子的xij值→調(diào)整此閉回路上其他頂點的值→檢驗新解的最優(yōu)性→重復(fù)上步驟直至得到最優(yōu)解為止

改進的解和檢驗數(shù)注意1.退化問題：如果基本變量中至少有一個為零，則該問題為退化問題。2.結(jié)果應(yīng)用文字表達，即寫出運輸方案。第三節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法一、不平衡運輸問題的數(shù)學(xué)模型在實際工作中經(jīng)常有的情況，有時總產(chǎn)量大于總銷量，有時總產(chǎn)量小于總銷量，這類問題稱為不平衡的運輸問題。當(dāng)總產(chǎn)量大于總銷量時，其數(shù)學(xué)模型為：當(dāng)總產(chǎn)量小于總銷量時，其數(shù)學(xué)模型為：二、不平衡運輸問題的求解方法[例2]設(shè)有三所社區(qū)醫(yī)院，醫(yī)生數(shù)分別為14、10和16人，在為4個居民區(qū)居民進行體檢時，所需的醫(yī)生數(shù)分別為6、12、8和4人，從各醫(yī)院到各居民區(qū)每名醫(yī)生的平均勞動成本見表4-12，問如何分配醫(yī)生可以使總的勞動成本最低？表3各醫(yī)院到各居民區(qū)每名醫(yī)生的平均勞動成本（單位：元）醫(yī)院居民區(qū)B1B2B3B4A140602080A250304060A370906040銷地產(chǎn)地B1B2B3B4產(chǎn)量11x12x13x14A25030406010x21x22x23x24A37090604016x31x32x33x34銷量61284表4各醫(yī)院到各居民區(qū)的醫(yī)生分配表銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A140602080014x11x12x13x14x15A250304060010x21x22x23x24x25A370906040016x31x32x33x34x35銷量612841040表5各醫(yī)院到各居民區(qū)的醫(yī)生分配表對于總產(chǎn)量大于總銷量的運輸問題，我們可以增加一個假設(shè)的銷地Bn+1，且該地的銷量為：OBJECTIVEFUNCTIONVALUE1)1040.000VARIABLEVALUEX114.000000X122.000000X138.000000X140.000000X210.000000X2210.000000X230.000000X240.000000X312.000000X320.000000X330.000000X344.000000X150.000000X250.000000X3510.000000數(shù)學(xué)模型變?yōu)椋?/p>

由于各產(chǎn)地調(diào)運到這個假設(shè)的銷地的物品數(shù)量xi,n+1實際上是各產(chǎn)地存儲的物品的數(shù)量，所以各產(chǎn)地到該銷地的單位運輸費用ci,n+1=0。銷地產(chǎn)地B1B2…BnBn+1(存儲)產(chǎn)量A1c11c12c1n0a1x11x12x1nx1,n+1A2c21c22C2n0a2x21x22x2nx2,n+1Amcm1cm2cmn0amxm1xm2xmnxm,n+1銷量b1b2…bn表6總產(chǎn)量大于總銷量的運輸問題的運輸表

類似地，對于總銷量大于總產(chǎn)量的運輸問題，我們可以假設(shè)有一個產(chǎn)地Am+1，它的產(chǎn)量等于：這個產(chǎn)地發(fā)往各個銷地的物品數(shù)量xm+1,j實際上是各個銷地所欠缺的物品數(shù)量。當(dāng)然這個假設(shè)產(chǎn)地到各銷地的單位運價cm+1,j都是等于0，數(shù)學(xué)模型變?yōu)椋轰N地產(chǎn)地B1B2…Bn產(chǎn)量A1c11c12c1na1x11x12x1nA2c21c22c2na2x21x22x2nAmcm1cm2cmnamxm1xm2xmnAm＋1(欠缺)000xm+1,1xm+1,2xm+1,n銷量b1b2…bn表7總銷量大于總產(chǎn)量的運輸問題的運輸表第四節(jié)應(yīng)用實例[例3]某藥廠和藥品銷售公司簽訂了供貨合同，已知該藥廠各季度的生產(chǎn)能力、每件產(chǎn)品的生產(chǎn)成本和每季度末應(yīng)該提供的產(chǎn)品件數(shù)（見下表），若藥廠當(dāng)季度末完成供給量，每件產(chǎn)品需支付保管費用100元，試問在遵守合同的情況下，該藥廠該如何安排生產(chǎn)才能使年消耗成本最低？季度藥廠生產(chǎn)能力(件)供貨量(件)每件產(chǎn)品的成本(元)一30020012000二40025011000三35030011500四25025012500表8某藥廠的生產(chǎn)能力及供貨量表9生產(chǎn)成本Cij表生產(chǎn)季度供貨季度一二三四一12000121001220012300二M110001110011200三MM1150011600四MMM12500

第i季度生產(chǎn)第j季度交貨的每件產(chǎn)品的生產(chǎn)成本cij實際上是生產(chǎn)成本加上保管費用之和

第i季度生產(chǎn)第j季度交貨的每件產(chǎn)品的生產(chǎn)成本cij實際上是生產(chǎn)成本加上保管費用之和解：用xij表示第i季度生產(chǎn)第j季度交貨的藥品件數(shù)則數(shù)學(xué)模型為：

交貨季生產(chǎn)季一二三四t生產(chǎn)量一1200012100122001230003000x11x12x13x14x15二M110001110011200040000x22x23x24x25三MM11500116000350000x33x34x35四MMM1250002500000x44x45供貨量20002500300025003000表10藥廠供貨問題的運輸表OBJECTIVEFUNCTIONVALUE1)0.3355000E+08VARIABLEVALUEVARIABLEVALUEX110.000000X120.000000X130.000000X140.000000MX210.000000X220.000000X23500.000000X242500.000000MX310.000000MX320.000000X330.000000X340.000000MX410.000000MX420.000000MX430.000000X440.000000X153000.000000X211000.000000X250.000000X311000.000000X322500.000000X350.000000X410.000000X420.000000X432500.000000X450.000000[例4]某種產(chǎn)品有A1、A2、A3和A4三個產(chǎn)地，銷售地為B1、B2、B3和B4，各產(chǎn)地到銷售地間的單位運價如表4-19。四個銷售地的需求量分別為40、60、90和70件。現(xiàn)要求產(chǎn)地A1必須供給70件產(chǎn)品；A2至少供給70件產(chǎn)品，但不能多于100件；A3至少供給60件產(chǎn)品；A4供給的產(chǎn)品不能多于90件。問應(yīng)該如何在產(chǎn)銷平衡的情況下調(diào)運產(chǎn)品，使總運費最少？表11某產(chǎn)品的單位運價表銷地產(chǎn)地B1B2B3B4供給量A13352a1＝70A2443170a2100A33543a360A45262a490需求量40609070解：當(dāng)A2、A4的供給量為最小值時，總供給量為140，而總需求量是260，故在產(chǎn)銷平衡的條件下A3最大的供給量是120。如果產(chǎn)地A2、A3和A4的供給量都取最大值，總的供給量是380，大于總需求量，這時應(yīng)該增加一個假設(shè)的銷售地B5，其需求量是120。銷地產(chǎn)地B1B2B3B4B5供給量A13352M70A24431M70A’24431030A33543M60A’33543060A45262090需求量40609070120表12例4的改進運輸表OBJECTIVEFUNCTIONVALUE1)640.0000VARIABLEVALUEVARIABLEVALUEX110.000000X120.000000X130.000000X140.000000MX150.000000X210.000000X220.000000