運輸問題-課件

第三章運輸問題第三章運輸問題產(chǎn)銷不平衡的運輸問題內(nèi)容運輸問題表上作業(yè)法123運輸問題的應(yīng)用4產(chǎn)銷不平衡的運輸問題內(nèi)容運輸問題表上作業(yè)法123運《運籌學(xué)》第三章運輸問題Slide3一、運輸模型（產(chǎn)銷平衡）例1．某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的每件物品的運費如下表所示：問：應(yīng)如何調(diào)運，使得總運輸費最??？設(shè)Xij表示從產(chǎn)地Ai調(diào)運到Bj的運輸量(i＝1，2；j＝1，2，3)，現(xiàn)將安排的運輸量列表如下：《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide4產(chǎn)銷平衡表滿足產(chǎn)地產(chǎn)量的約束條件為：

X11+X12+X13=200X21+X22+X23=300滿足銷地銷量的約束條件為：

X11+X21＝150X12+X22＝150X13+X23＝200《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide5使運輸費最小的目標函數(shù)為：

minz＝6X11+4X12+6X13+6X21+5X22+5X23Xij>=0一般運輸問題的線性規(guī)劃的模型：有m個產(chǎn)地生產(chǎn)某種物資，有n個地區(qū)需要該類物資。Al，A2，…，Am表示某種物資的m個產(chǎn)地；Bl，B2，…，Bn表示某種物資的n個銷地；令a1,a2,…,am表示各產(chǎn)地產(chǎn)量，b1,b2,…,bn表示各銷地的銷量，ai=bj稱為產(chǎn)銷平衡。Cij表示把物資從產(chǎn)地Ai運到銷地Bj的單位運價。同樣設(shè)Xij表示從產(chǎn)地Ai運到銷地Bj的運輸量。《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide6則產(chǎn)銷平衡的運輸問題的線性規(guī)劃模型如下所示：運輸問題有mn個決策變量，m+n個約束條件。由于產(chǎn)銷平衡條件，只有m+n–1個相互獨立，因此，運輸問題的基變量只有m+n–1個?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide7共有2個產(chǎn)地和3個銷地，產(chǎn)銷平衡。基變量的個數(shù)為2+3-1=4Objectivevalue:2500《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide8二、表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質(zhì)是單純形法。(1)給出初始調(diào)運方案——初始基可行解：即在(m×n)產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。用最小元素法或伏格爾法。(2)檢驗方案是否最優(yōu)，若是最優(yōu)解，則停止計算；否則轉(zhuǎn)下一步。求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)。在表上用閉環(huán)回路法或乘數(shù)法。(3)調(diào)整調(diào)運方案，得新的方案?！_定入基和出基變量，找出新的基可行解。在表上用閉環(huán)回路法。(4)重復(fù)(2),(3)直到求出最優(yōu)方案。【定理】：產(chǎn)銷平衡的運輸問題一定有可行解，且一定有最優(yōu)解。《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide9證：記∑ai=∑bj=QXij=aibj/Q就是一個可行解，因為Xij≥0，且滿足∑Xij=ai,∑Xij=bj又因為Cij≥0,Xij≥0,所以目標函數(shù)有下界零。因而運輸問題一定有最優(yōu)解。1、確定初始基可行解最常用的方法是最小元素法。——既簡便，又盡可能接近最優(yōu)解。最小元素法的基本思想是就近供應(yīng)，即從單位運價表中最小的運價開始確定供銷關(guān)系，同時兼顧各產(chǎn)銷地的需求，然后次小，一直到給出初始基可行解為止?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide10P83例2.1：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個加工廠，每日的產(chǎn)量分別為A1－7噸，A2－4噸，A3－9噸。該公司把這些產(chǎn)品分別運往四個銷售點。各銷售點每日銷量為B1－3噸，B2－6噸，B3－5噸，B4－6噸。已知從各工廠到各銷售點的單位產(chǎn)品的運價如下表所示。

產(chǎn)銷平衡表《運籌學(xué)》1）找出最小運價為1，先將A2的產(chǎn)品供應(yīng)給B1，因a2>b1，A2除滿足B1的全部需要外，還可多余1噸產(chǎn)品。在(A2,B1)的交叉格處填上3。并將B1列運價劃去。2）在未劃去的元素中再找出最小運價2，確定A2多余的1噸供應(yīng)B3。在(A2,B3)的交叉格處填上1。并將A2行運價劃去3）在未劃去的元素中再找出最小的運價3，這樣一步步進行下去，直到運價表上的所有元素劃去為止。最后在(A1,B4)的交叉格處填上3，將A1行和B4列運價同時劃去，得到一個初始調(diào)運方案。這方案的總運費為86元。3146331）找出最小運價為1，先將A2的產(chǎn)品供應(yīng)給B1，因a2>b1《運籌學(xué)》第三章運輸問題Slide12最小元素法中的退化情況第一次劃去第1列B1，第二次最小運價為2，對應(yīng)的銷地B2銷量和產(chǎn)地A3的產(chǎn)量未分配量皆為6，故同時劃去B2列和A3行。非零的數(shù)字格小于(m+n-1)個。出現(xiàn)退化時，要在同時被劃去的行列中選一個空格填0，此格作為有數(shù)字格。345602《運籌學(xué)》伏格爾法(Vogel)——差額法：最小元素法的缺點是：為了節(jié)省一處的費用，有時會造成在其他處要多花幾倍的運費。伏格爾法考慮到：一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就應(yīng)考慮次小運費。這就有一個差額，差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應(yīng)當采用最小運費調(diào)運。315632伏格爾法(Vogel)——差額法：315632運輸問題-課件《運籌學(xué)》第三章運輸問題Slide151）分別計算出各行和各列的最小運費和次最小運費的差額，填入表格的最右列和最下行。2）從行或列差額中選出最大者，選擇它所在行或列中的最小元素。B2列中的最小元素是4，可確定A3的產(chǎn)品先滿足B2的需要，同時將B2列運價劃去。3）對未劃去的元素再分別計算出各行、各列的最小運費和次最小運費的差額，重新填入表格的最右列和最下行。重復(fù)1）2），直到找到初始調(diào)運方案?？傔\費為85元。伏格爾法給出的初始解比用最小元素法給出的更接近最優(yōu)解。本例用伏格爾法給出的初始解就是最優(yōu)解?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide162、調(diào)運方案的檢驗判別的方法是計算空格（非基變量）的檢驗數(shù)，若所有的檢驗數(shù)都大于等于0，為最優(yōu)解。1）閉環(huán)回路法：在給出的初始調(diào)運方案表上，從每一空格出發(fā)找一條閉環(huán)回路，它是以某空格為起點，用水平或垂直線向前劃，每碰到一數(shù)字格轉(zhuǎn)90°后（回路的轉(zhuǎn)角點必須是一個基變量），繼續(xù)前進，直到回到起始空格為止。從每一空格出發(fā)一定存在且只有唯一的閉環(huán)回路。從空格開始加減閉環(huán)各個頂點的運輸單價，可得每個空格對應(yīng)的檢驗數(shù)。《運籌學(xué)》314633314633《運籌學(xué)》第三章運輸問題Slide18閉環(huán)回路計算檢驗數(shù)的經(jīng)濟解釋為：從任一空格出發(fā)，如(A1,B1)，若讓A1的產(chǎn)品調(diào)運1噸給B1，為了保持產(chǎn)銷平衡，就要依次作調(diào)整：在(A2,B1)處減少1噸，在(A2,B3)處增加1噸，在(A1,B3)處減少1噸，即構(gòu)成了以空格(A1,B1)為起點的閉環(huán)回路。調(diào)整后的方案使運費變成(+1)×3＋(－1)×1＋(+1)×2＋(－1)×3＝1（元）這就是(A1,B1)的檢驗數(shù)。當檢驗數(shù)還存在負數(shù)時，說明原方案還不是最優(yōu)解。用閉環(huán)回路求檢驗數(shù),當產(chǎn)銷點很多時,這種計算很繁瑣。2）乘數(shù)法（位勢法）：乘數(shù)法的原理是對偶理論?！哆\籌學(xué)》運輸問題對偶問題σij與原問題有什么關(guān)系？

由對偶性質(zhì)，σij是原問題變量xij的檢驗數(shù)。

當xij是基變量時，σij=0，此時有由此求出Ui和Vj，再代回（*）式求非基變量的σij（空格檢驗數(shù)）P93-94運輸問題對偶問題σij與原問題有什么關(guān)系？P93-94基變量：X13U1+V3=C13=3X14U1+V4=C14=10X21U2+V1=C21=1X23U2+V3=C23=2X32U3+V2=C32=4X34U3+V4=C34=5設(shè)U1＝0，則V3=3,U2=-1,V1=2,V4=10,U3=-5,V2=9非基變量：C11－U1－V1=3－0－2＝1C12－U1－V2＝11－0－9＝2C22－U2－V2=9＋1－9＝1C24－U2－V4＝8＋1－10＝－1C31－U3－V1=7+5－2＝10C33－U3－V3=10＋5－3＝12基變量：3、調(diào)整改進的閉環(huán)回路方法——迭代若有兩個或兩個以上的負檢驗數(shù)時，一般選其中最小的負檢驗數(shù)。以(24)格為調(diào)入格，以此格為出發(fā)點，作一閉環(huán)回路。在閉回路上進行運量調(diào)整，使選定空格處的運量盡可能地增加（即取相鄰兩數(shù)字格中較小的）。運量調(diào)整后，必然使某個數(shù)字格變成零。把一個變成零的數(shù)字格抹去，得新的調(diào)運方案。經(jīng)檢驗，所有檢驗數(shù)都非負，故達到最優(yōu)，最優(yōu)方案總運費最小是85元。3、調(diào)整改進的閉環(huán)回路方法——迭代若有兩個或兩個以上的負檢驗《運籌學(xué)》第三章運輸問題Slide22課堂作業(yè)：1、用表上作業(yè)法求出最優(yōu)解。（最小元素法）2、用伏格爾法直接給出近似最優(yōu)解?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide231、這是一個產(chǎn)銷平衡的問題。1）初始調(diào)運方案（最小元素法）401520251025初始調(diào)運方案的總運費為420元。2）最優(yōu)解的判別（閉環(huán)回路法）《運籌學(xué)》401520251025401520251025（乘數(shù)法）：基變量：X11U1+V1=C11=3X12U1+V2=C12=2X21U2+V1=C21=7X23U2+V3=C23=2X24U2+V4=C24=3X31U3+V1=C31=2設(shè)U1＝0，則V1=3,V2=2,U2=4,V3=-2,V4=-1,U3=-1非基變量：C13－U1－V3=7－0+2＝9C14－U1－V4＝6－0+1＝7C22－U2－V2=5－4－2＝-１C32－U3－V2＝5＋1－2＝4C33－U3－V3=4+1+2＝7C34－U3－V4=5+1+1＝7（乘數(shù)法）：《運籌學(xué)》第三章運輸問題Slide263)調(diào)整調(diào)運方案，得新的方案。以(22)格為調(diào)入格，以此格為出發(fā)點，作一閉環(huán)回路。經(jīng)檢驗，所有檢驗數(shù)都大于0，該調(diào)運方案是最優(yōu)的方案?？傔\費為395元。401520251025151520253525《運籌學(xué)》2、用伏格爾法直接給出近似最優(yōu)解。52020252010002、用伏格爾法直接給出近似最優(yōu)解。5202025201000運輸問題-課件《運籌學(xué)》第三章運輸問題Slide29用伏格爾法直接找到了近似最優(yōu)方案，總運價為305元?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide30第二種算法：用伏格爾法直接找到了近似最優(yōu)方案，總運價為345元。用伏格爾法求解，是否一定要轉(zhuǎn)化為產(chǎn)銷平衡表？《運籌學(xué)》三、產(chǎn)銷不平衡的運輸問題

產(chǎn)銷平衡表

P96例2.3：假設(shè)產(chǎn)地A1的產(chǎn)品必須全部調(diào)運出去,產(chǎn)地A2、A3的商品調(diào)運不出的單位存儲費為2百元和1百元產(chǎn)大于銷三、產(chǎn)銷不平衡的運輸問題產(chǎn)銷平衡表P96例2.3：假設(shè)產(chǎn)運輸費用：2×2+5×4+3×3+4×1+1×2=39(百元)

存儲費用：2×2+2×1=6(百元)總成本：39+6=45(百元)P98例2.4銷大于產(chǎn)運輸費用：2×2+5×4+3×3+4×1+1×2=39(百銷地B1、B2的需求必須全部滿足，銷地B3、B4每短缺1噸，發(fā)生損失費1百元、0?？偝杀臼?2百元，其中2百元是銷地B3發(fā)生缺貨的損失費。銷地B1、B2的需求必須全部滿足，銷地B3、B4每短缺1噸，《運籌學(xué)》第三章運輸問題Slide34例3．石家莊北方研究院有三個區(qū)，即一區(qū)、二區(qū)、三區(qū)，每年分別需要生活用煤和取暖用煤3000、1000、2000噸，由河北臨城，山西孟縣兩處煤礦負責(zé)供應(yīng)，這兩處煤礦的價格相同，煤的質(zhì)量也基本相同。兩處煤礦能供應(yīng)北方研究院的煤的數(shù)量，山西盂縣為4000噸，河北臨城為l500噸，由煤礦至北方研究院的單位運價(百元／噸)見下表。由于需求大于供給，經(jīng)院研究平衡決定一區(qū)供應(yīng)量可減少0～200噸，二區(qū)需要量應(yīng)全部滿足，三區(qū)供應(yīng)量不少于1700噸。試求總運費最低的調(diào)運方案?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide35河北臨城，山西孟縣兩處煤礦可以供應(yīng)煤5500噸。一區(qū)、二區(qū)、三區(qū)至少需要煤5500噸。至多需要煤6000噸。一區(qū)和三區(qū)必須供應(yīng)的煤分別為2800噸和1700噸?？梢圆还?yīng)的煤分別為200噸和300噸。產(chǎn)銷平衡表《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide36例4．設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如下表所示，試求出總的運費最節(jié)省的化肥調(diào)運方案。《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide37三個化肥廠共可供應(yīng)化肥160噸。問：根據(jù)現(xiàn)有三個化肥廠的產(chǎn)量，地區(qū)IV

最高需求是否可以不限？最高需求是多少？160－30－70－0＝60噸四個地區(qū)對化肥的最高需求為50＋70＋30＋60＝210噸《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide38四、運輸問題的應(yīng)用（一）生產(chǎn)與儲存的問題

P109習(xí)題2-16某廠按合同規(guī)定須于當年每個季度末分別提供10,15,25,20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及市場每臺柴油機的成本如下表所示。又如果生產(chǎn)出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護費用0.2萬元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲存、維護）費用最小的決策。《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide39設(shè)Xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機數(shù)實際的成本為該季度生產(chǎn)成本加上儲存和維護費用。四個季度的生產(chǎn)能力為100臺。而四個季度末共須提供柴油機70臺?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide40例6．光明儀器廠生產(chǎn)電腦繡花機是以銷定產(chǎn)的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機平均生產(chǎn)費用見下表。又已知上年末庫存103臺繡花機。加班生產(chǎn)機器每臺增加成本1萬元?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide41又如果當月生產(chǎn)出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元，每臺機器每月的平均倉儲費、維護費為0.2萬元。在7、8月份銷售淡季，全廠停產(chǎn)1個月，因此在6月份完成銷售合同后還要留出庫存80臺。問應(yīng)如何安排1~6月份的生產(chǎn)使總的生產(chǎn)(包括運輸、倉儲、維護)費用最少?設(shè)Xij為第i個月生產(chǎn)的用于第j個月交貨的機器數(shù)實際的成本為該月生產(chǎn)成本加上運輸、儲存和維護費用將正常生產(chǎn)和加班生產(chǎn)分成兩種不同的生產(chǎn)月來進行安排。六個月的生產(chǎn)能力為743臺。而六個月末共須提供機器707臺。上年末庫存的103臺繡花機，作為第0個月的生產(chǎn)供給?！哆\籌學(xué)》運輸問題-課件《運籌學(xué)》第三章運輸問題Slide43（二）調(diào)度問題例7：某航運公司承擔(dān)六個港口初始A、B、C、D、E、F的四條固定航線的物資運輸任務(wù)。已知各條航線的起點、終點城市及每天航班數(shù)見下表7－1。假定各條航線使用相同型號的船只，又各城市間的航程天數(shù)見表7－2。又知每條船只每次裝卸貨的時間各需1天，則該航運公司至少應(yīng)配備多少條船，才能滿足所有航線的運貨需求？

表7－1《運籌學(xué)》表7－2(1)載貨航程需要的周轉(zhuǎn)船只數(shù)：表7－2(1)載貨航程需要的周轉(zhuǎn)船只數(shù)：《運籌學(xué)》第三章運輸問題Slide45

例如：航線1，在港口E裝貨1天，E－D航程17天，在D卸貨1天，總計19天。每天3航班。故該航線需周轉(zhuǎn)船57條以上共需周轉(zhuǎn)船只數(shù)91條。(2)各港口間調(diào)度所需船只數(shù)。有些港口每天到達船數(shù)多于需要船數(shù)。例如，港口D，每天到達3條，需求1條?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide46

為使各港口間調(diào)度周轉(zhuǎn)所需的空船數(shù)最少，其產(chǎn)銷平衡表如下。單位運價應(yīng)為相應(yīng)各港口之間的船只航程天數(shù)。可求出空船的最優(yōu)調(diào)度方案如下：《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide47

由上表可計算得知最少周轉(zhuǎn)的空船數(shù)為40條。所以，在不考慮維修、儲備等情況下，該公司至少應(yīng)配備131條船。（三）轉(zhuǎn)運問題例8．騰飛電子儀器公司在大連和廣州有兩個分廠，大連分廠每月生產(chǎn)400臺某種儀器，廣州分廠每月生產(chǎn)600臺某種儀器。該公司在上海與天津有兩個銷售公司負責(zé)對南京、濟南、南昌與青島四個城市的儀器供應(yīng)，又因為大連與青島相距較近，公司同意大連分廠也可以向青島直接供貨。這些城市間的每臺儀器的運輸費用我們標在兩個城市間的弧上，單位為百元。問應(yīng)該如何調(diào)運儀器，使得總的運輸費最低?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide48思路:將轉(zhuǎn)運問題化為無轉(zhuǎn)運問題。中轉(zhuǎn)地3、4既可作為產(chǎn)地，也可作為銷地?！哆\籌學(xué)》

例9：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個加工廠，每日的產(chǎn)量分別為A1－7噸，A2－4噸，A3－9噸。該公司把這些產(chǎn)品分別運往四個銷售點。各銷售點每日銷量為B1－3噸，B2－6噸，B3－5噸，B4－6噸。已知從各工廠到各銷售點的單位產(chǎn)品的運價如下表所示。課本P100例2.5

例9：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個加工廠，每日的產(chǎn)量分別為《運籌學(xué)》第三章運輸問題Slide50如果假定1）每個工廠生產(chǎn)的產(chǎn)品不一定直接發(fā)運到銷售點，可以其中幾個產(chǎn)地集中一起運；2）運往各銷售點的產(chǎn)品可以先運給其中幾個銷售點，再轉(zhuǎn)運給其它銷售點；3）除產(chǎn)地、銷售點之外，中間還可以有幾個轉(zhuǎn)運站，在產(chǎn)地之間、銷售點之間或產(chǎn)地與銷售點之間轉(zhuǎn)運。已知各產(chǎn)地、銷售點、中間轉(zhuǎn)運站及相互之間每噸產(chǎn)品的運價如下表所示，問在考慮到產(chǎn)銷地之間直接運輸和非直接運輸?shù)母鞣N可能方案的情況下，如何將三個廠每天生產(chǎn)的產(chǎn)品運往各個銷售點，使總的運費最少。《運籌學(xué)》運輸問題-課件《運籌學(xué)》第三章運輸問題Slide52從A1到B2的單位運價為11元，如從A1經(jīng)A3運往B2，運價為3＋4＝7元，從A1經(jīng)T2運往B2，運價為1＋5＝6元。運費最少的路經(jīng)是從A1經(jīng)A2、B1運往B2，運價為1+1+1＝3元1)所有的產(chǎn)地、中轉(zhuǎn)地和銷地都可以看作產(chǎn)地，也可以看作銷地。因此整個問題被當作有11個產(chǎn)地和11個銷地的擴大運輸問題。2)中轉(zhuǎn)站的產(chǎn)量等于銷量。每個中轉(zhuǎn)站的轉(zhuǎn)運量不大于20噸?？梢砸?guī)定四個中轉(zhuǎn)站的產(chǎn)量和銷量均為20噸。實際的轉(zhuǎn)運量小于20噸，可以加入一個松弛量Xii，對應(yīng)的運價為0。(20－Xii)為實際的轉(zhuǎn)運量。3)原來的產(chǎn)地和銷地也有轉(zhuǎn)運站的作用，故三個廠產(chǎn)量為27、24、29噸，銷量均為20噸，四個銷售點的銷量為23、26、25、26噸，產(chǎn)量均為20噸。同時引進Xii作為松弛變量?！哆\籌學(xué)》運輸問題-課件《運籌學(xué)》第三章運輸問題Slide54例10：某廠在A、B、C三處設(shè)倉庫供應(yīng)①～⑧點的各零售商，詳見下圖。圖中各邊數(shù)字為沿該線路運送一單位物資所需的費用（元）。已知A、B、C三倉庫內(nèi)現(xiàn)庫存物資數(shù)分別為200、170、160單位。①～⑧點各零售商所需物資數(shù)列于下表。且對零售商供應(yīng)短缺一單位時的罰款也列于表中。應(yīng)如何確立各倉庫對各零售點的分配量，使總的運輸費和罰款之和最小?！哆\籌學(xué)》①②③④⑤⑥⑦⑧ABC①②③④⑤⑥⑦⑧ABC《運籌學(xué)》第三章運輸問題Slide56總供給量530，總需求量550。

《運籌學(xué)》第三章運輸問題第三章運輸問題產(chǎn)銷不平衡的運輸問題內(nèi)容運輸問題表上作業(yè)法123運輸問題的應(yīng)用4產(chǎn)銷不平衡的運輸問題內(nèi)容運輸問題表上作業(yè)法123運《運籌學(xué)》第三章運輸問題Slide59一、運輸模型（產(chǎn)銷平衡）例1．某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的每件物品的運費如下表所示：問：應(yīng)如何調(diào)運，使得總運輸費最??？設(shè)Xij表示從產(chǎn)地Ai調(diào)運到Bj的運輸量(i＝1，2；j＝1，2，3)，現(xiàn)將安排的運輸量列表如下：《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide60產(chǎn)銷平衡表滿足產(chǎn)地產(chǎn)量的約束條件為：

X11+X12+X13=200X21+X22+X23=300滿足銷地銷量的約束條件為：

X11+X21＝150X12+X22＝150X13+X23＝200《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide61使運輸費最小的目標函數(shù)為：

minz＝6X11+4X12+6X13+6X21+5X22+5X23Xij>=0一般運輸問題的線性規(guī)劃的模型：有m個產(chǎn)地生產(chǎn)某種物資，有n個地區(qū)需要該類物資。Al，A2，…，Am表示某種物資的m個產(chǎn)地；Bl，B2，…，Bn表示某種物資的n個銷地；令a1,a2,…,am表示各產(chǎn)地產(chǎn)量，b1,b2,…,bn表示各銷地的銷量，ai=bj稱為產(chǎn)銷平衡。Cij表示把物資從產(chǎn)地Ai運到銷地Bj的單位運價。同樣設(shè)Xij表示從產(chǎn)地Ai運到銷地Bj的運輸量?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide62則產(chǎn)銷平衡的運輸問題的線性規(guī)劃模型如下所示：運輸問題有mn個決策變量，m+n個約束條件。由于產(chǎn)銷平衡條件，只有m+n–1個相互獨立，因此，運輸問題的基變量只有m+n–1個。《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide63共有2個產(chǎn)地和3個銷地，產(chǎn)銷平衡?；兞康膫€數(shù)為2+3-1=4Objectivevalue:2500《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide64二、表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質(zhì)是單純形法。(1)給出初始調(diào)運方案——初始基可行解：即在(m×n)產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。用最小元素法或伏格爾法。(2)檢驗方案是否最優(yōu)，若是最優(yōu)解，則停止計算；否則轉(zhuǎn)下一步。求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)。在表上用閉環(huán)回路法或乘數(shù)法。(3)調(diào)整調(diào)運方案，得新的方案?！_定入基和出基變量，找出新的基可行解。在表上用閉環(huán)回路法。(4)重復(fù)(2),(3)直到求出最優(yōu)方案?！径ɡ怼浚寒a(chǎn)銷平衡的運輸問題一定有可行解，且一定有最優(yōu)解?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide65證：記∑ai=∑bj=QXij=aibj/Q就是一個可行解，因為Xij≥0，且滿足∑Xij=ai,∑Xij=bj又因為Cij≥0,Xij≥0,所以目標函數(shù)有下界零。因而運輸問題一定有最優(yōu)解。1、確定初始基可行解最常用的方法是最小元素法?！群啽?，又盡可能接近最優(yōu)解。最小元素法的基本思想是就近供應(yīng)，即從單位運價表中最小的運價開始確定供銷關(guān)系，同時兼顧各產(chǎn)銷地的需求，然后次小，一直到給出初始基可行解為止?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide66P83例2.1：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個加工廠，每日的產(chǎn)量分別為A1－7噸，A2－4噸，A3－9噸。該公司把這些產(chǎn)品分別運往四個銷售點。各銷售點每日銷量為B1－3噸，B2－6噸，B3－5噸，B4－6噸。已知從各工廠到各銷售點的單位產(chǎn)品的運價如下表所示。

產(chǎn)銷平衡表《運籌學(xué)》1）找出最小運價為1，先將A2的產(chǎn)品供應(yīng)給B1，因a2>b1，A2除滿足B1的全部需要外，還可多余1噸產(chǎn)品。在(A2,B1)的交叉格處填上3。并將B1列運價劃去。2）在未劃去的元素中再找出最小運價2，確定A2多余的1噸供應(yīng)B3。在(A2,B3)的交叉格處填上1。并將A2行運價劃去3）在未劃去的元素中再找出最小的運價3，這樣一步步進行下去，直到運價表上的所有元素劃去為止。最后在(A1,B4)的交叉格處填上3，將A1行和B4列運價同時劃去，得到一個初始調(diào)運方案。這方案的總運費為86元。3146331）找出最小運價為1，先將A2的產(chǎn)品供應(yīng)給B1，因a2>b1《運籌學(xué)》第三章運輸問題Slide68最小元素法中的退化情況第一次劃去第1列B1，第二次最小運價為2，對應(yīng)的銷地B2銷量和產(chǎn)地A3的產(chǎn)量未分配量皆為6，故同時劃去B2列和A3行。非零的數(shù)字格小于(m+n-1)個。出現(xiàn)退化時，要在同時被劃去的行列中選一個空格填0，此格作為有數(shù)字格。345602《運籌學(xué)》伏格爾法(Vogel)——差額法：最小元素法的缺點是：為了節(jié)省一處的費用，有時會造成在其他處要多花幾倍的運費。伏格爾法考慮到：一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就應(yīng)考慮次小運費。這就有一個差額，差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應(yīng)當采用最小運費調(diào)運。315632伏格爾法(Vogel)——差額法：315632運輸問題-課件《運籌學(xué)》第三章運輸問題Slide711）分別計算出各行和各列的最小運費和次最小運費的差額，填入表格的最右列和最下行。2）從行或列差額中選出最大者，選擇它所在行或列中的最小元素。B2列中的最小元素是4，可確定A3的產(chǎn)品先滿足B2的需要，同時將B2列運價劃去。3）對未劃去的元素再分別計算出各行、各列的最小運費和次最小運費的差額，重新填入表格的最右列和最下行。重復(fù)1）2），直到找到初始調(diào)運方案?？傔\費為85元。伏格爾法給出的初始解比用最小元素法給出的更接近最優(yōu)解。本例用伏格爾法給出的初始解就是最優(yōu)解?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide722、調(diào)運方案的檢驗判別的方法是計算空格（非基變量）的檢驗數(shù)，若所有的檢驗數(shù)都大于等于0，為最優(yōu)解。1）閉環(huán)回路法：在給出的初始調(diào)運方案表上，從每一空格出發(fā)找一條閉環(huán)回路，它是以某空格為起點，用水平或垂直線向前劃，每碰到一數(shù)字格轉(zhuǎn)90°后（回路的轉(zhuǎn)角點必須是一個基變量），繼續(xù)前進，直到回到起始空格為止。從每一空格出發(fā)一定存在且只有唯一的閉環(huán)回路。從空格開始加減閉環(huán)各個頂點的運輸單價，可得每個空格對應(yīng)的檢驗數(shù)?！哆\籌學(xué)》314633314633《運籌學(xué)》第三章運輸問題Slide74閉環(huán)回路計算檢驗數(shù)的經(jīng)濟解釋為：從任一空格出發(fā)，如(A1,B1)，若讓A1的產(chǎn)品調(diào)運1噸給B1，為了保持產(chǎn)銷平衡，就要依次作調(diào)整：在(A2,B1)處減少1噸，在(A2,B3)處增加1噸，在(A1,B3)處減少1噸，即構(gòu)成了以空格(A1,B1)為起點的閉環(huán)回路。調(diào)整后的方案使運費變成(+1)×3＋(－1)×1＋(+1)×2＋(－1)×3＝1（元）這就是(A1,B1)的檢驗數(shù)。當檢驗數(shù)還存在負數(shù)時，說明原方案還不是最優(yōu)解。用閉環(huán)回路求檢驗數(shù),當產(chǎn)銷點很多時,這種計算很繁瑣。2）乘數(shù)法（位勢法）：乘數(shù)法的原理是對偶理論?！哆\籌學(xué)》運輸問題對偶問題σij與原問題有什么關(guān)系？

由對偶性質(zhì)，σij是原問題變量xij的檢驗數(shù)。

當xij是基變量時，σij=0，此時有由此求出Ui和Vj，再代回（*）式求非基變量的σij（空格檢驗數(shù)）P93-94運輸問題對偶問題σij與原問題有什么關(guān)系？P93-94基變量：X13U1+V3=C13=3X14U1+V4=C14=10X21U2+V1=C21=1X23U2+V3=C23=2X32U3+V2=C32=4X34U3+V4=C34=5設(shè)U1＝0，則V3=3,U2=-1,V1=2,V4=10,U3=-5,V2=9非基變量：C11－U1－V1=3－0－2＝1C12－U1－V2＝11－0－9＝2C22－U2－V2=9＋1－9＝1C24－U2－V4＝8＋1－10＝－1C31－U3－V1=7+5－2＝10C33－U3－V3=10＋5－3＝12基變量：3、調(diào)整改進的閉環(huán)回路方法——迭代若有兩個或兩個以上的負檢驗數(shù)時，一般選其中最小的負檢驗數(shù)。以(24)格為調(diào)入格，以此格為出發(fā)點，作一閉環(huán)回路。在閉回路上進行運量調(diào)整，使選定空格處的運量盡可能地增加（即取相鄰兩數(shù)字格中較小的）。運量調(diào)整后，必然使某個數(shù)字格變成零。把一個變成零的數(shù)字格抹去，得新的調(diào)運方案。經(jīng)檢驗，所有檢驗數(shù)都非負，故達到最優(yōu)，最優(yōu)方案總運費最小是85元。3、調(diào)整改進的閉環(huán)回路方法——迭代若有兩個或兩個以上的負檢驗《運籌學(xué)》第三章運輸問題Slide78課堂作業(yè)：1、用表上作業(yè)法求出最優(yōu)解。（最小元素法）2、用伏格爾法直接給出近似最優(yōu)解?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide791、這是一個產(chǎn)銷平衡的問題。1）初始調(diào)運方案（最小元素法）401520251025初始調(diào)運方案的總運費為420元。2）最優(yōu)解的判別（閉環(huán)回路法）《運籌學(xué)》401520251025401520251025（乘數(shù)法）：基變量：X11U1+V1=C11=3X12U1+V2=C12=2X21U2+V1=C21=7X23U2+V3=C23=2X24U2+V4=C24=3X31U3+V1=C31=2設(shè)U1＝0，則V1=3,V2=2,U2=4,V3=-2,V4=-1,U3=-1非基變量：C13－U1－V3=7－0+2＝9C14－U1－V4＝6－0+1＝7C22－U2－V2=5－4－2＝-１C32－U3－V2＝5＋1－2＝4C33－U3－V3=4+1+2＝7C34－U3－V4=5+1+1＝7（乘數(shù)法）：《運籌學(xué)》第三章運輸問題Slide823)調(diào)整調(diào)運方案，得新的方案。以(22)格為調(diào)入格，以此格為出發(fā)點，作一閉環(huán)回路。經(jīng)檢驗，所有檢驗數(shù)都大于0，該調(diào)運方案是最優(yōu)的方案?？傔\費為395元。401520251025151520253525《運籌學(xué)》2、用伏格爾法直接給出近似最優(yōu)解。52020252010002、用伏格爾法直接給出近似最優(yōu)解。5202025201000運輸問題-課件《運籌學(xué)》第三章運輸問題Slide85用伏格爾法直接找到了近似最優(yōu)方案，總運價為305元?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide86第二種算法：用伏格爾法直接找到了近似最優(yōu)方案，總運價為345元。用伏格爾法求解，是否一定要轉(zhuǎn)化為產(chǎn)銷平衡表？《運籌學(xué)》三、產(chǎn)銷不平衡的運輸問題

產(chǎn)銷平衡表

P96例2.3：假設(shè)產(chǎn)地A1的產(chǎn)品必須全部調(diào)運出去,產(chǎn)地A2、A3的商品調(diào)運不出的單位存儲費為2百元和1百元產(chǎn)大于銷三、產(chǎn)銷不平衡的運輸問題產(chǎn)銷平衡表P96例2.3：假設(shè)產(chǎn)運輸費用：2×2+5×4+3×3+4×1+1×2=39(百元)

存儲費用：2×2+2×1=6(百元)總成本：39+6=45(百元)P98例2.4銷大于產(chǎn)運輸費用：2×2+5×4+3×3+4×1+1×2=39(百銷地B1、B2的需求必須全部滿足，銷地B3、B4每短缺1噸，發(fā)生損失費1百元、0?？偝杀臼?2百元，其中2百元是銷地B3發(fā)生缺貨的損失費。銷地B1、B2的需求必須全部滿足，銷地B3、B4每短缺1噸，《運籌學(xué)》第三章運輸問題Slide90例3．石家莊北方研究院有三個區(qū)，即一區(qū)、二區(qū)、三區(qū)，每年分別需要生活用煤和取暖用煤3000、1000、2000噸，由河北臨城，山西孟縣兩處煤礦負責(zé)供應(yīng)，這兩處煤礦的價格相同，煤的質(zhì)量也基本相同。兩處煤礦能供應(yīng)北方研究院的煤的數(shù)量，山西盂縣為4000噸，河北臨城為l500噸，由煤礦至北方研究院的單位運價(百元／噸)見下表。由于需求大于供給，經(jīng)院研究平衡決定一區(qū)供應(yīng)量可減少0～200噸，二區(qū)需要量應(yīng)全部滿足，三區(qū)供應(yīng)量不少于1700噸。試求總運費最低的調(diào)運方案?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide91河北臨城，山西孟縣兩處煤礦可以供應(yīng)煤5500噸。一區(qū)、二區(qū)、三區(qū)至少需要煤5500噸。至多需要煤6000噸。一區(qū)和三區(qū)必須供應(yīng)的煤分別為2800噸和1700噸?？梢圆还?yīng)的煤分別為200噸和300噸。產(chǎn)銷平衡表《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide92例4．設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如下表所示，試求出總的運費最節(jié)省的化肥調(diào)運方案?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide93三個化肥廠共可供應(yīng)化肥160噸。問：根據(jù)現(xiàn)有三個化肥廠的產(chǎn)量，地區(qū)IV

最高需求是否可以不限？最高需求是多少？160－30－70－0＝60噸四個地區(qū)對化肥的最高需求為50＋70＋30＋60＝210噸《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide94四、運輸問題的應(yīng)用（一）生產(chǎn)與儲存的問題

P109習(xí)題2-16某廠按合同規(guī)定須于當年每個季度末分別提供10,15,25,20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及市場每臺柴油機的成本如下表所示。又如果生產(chǎn)出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護費用0.2萬元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲存、維護）費用最小的決策?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide95設(shè)Xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機數(shù)實際的成本為該季度生產(chǎn)成本加上儲存和維護費用。四個季度的生產(chǎn)能力為100臺。而四個季度末共須提供柴油機70臺?！哆\籌學(xué)》《運籌學(xué)》第三章運輸問題Slide96例6．光明儀器廠生產(chǎn)電腦繡花機是以銷定產(chǎn)的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機平均生產(chǎn)費用見下表。又已知上年末庫存103臺繡花機。加班生產(chǎn)機器每臺增加成本1萬元。《運籌學(xué)》《運籌學(xué)》第三章運輸問題Slide97又如果當月生產(chǎn)出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元，每臺機器每月的平均倉儲費、維護費為0.2萬元。在7、8月份銷售淡季，全廠停產(chǎn)1個月，因此在6月份完成銷售合同后還要留出庫存80臺。問應(yīng)如何安排1~6月份的生產(chǎn)使總的生產(chǎn)(包括運輸、倉儲、維護)費用最少?設(shè)Xij為第i個月生產(chǎn)的用于第j個月交貨的機器數(shù)實際的成本為該月生產(chǎn)成本加上運輸、儲存和維護費用將正常生產(chǎn)和加班生產(chǎn)分成兩種不同的生產(chǎn)月來進行安排。六個月的生產(chǎn)能力為743臺。而六個月末共須提供機器707臺。上年末庫存的103臺繡花機，作為第0個月的生產(chǎn)供給?！哆\籌學(xué)》運輸問題-課件《運籌學(xué)》第三章運輸問題Slide99（二）調(diào)度問題例7：某航運公司承擔(dān)六個港口初始A、B、C、D、E、F的四條固定航線的物資運輸任務(wù)。已知各條航線的起點、終點城市及每天航班數(shù)見下表7－1。假定各條航線使用相同型號的船只，又各城市間的航程天數(shù)見表7－2。又知每條船只每次裝卸貨的時間各需1天，則該航運公司至少應(yīng)配備多少條船，才能滿足所有航線的運貨需求？

表7－1《運籌學(xué)》表7－2(1)載貨航程需要的周轉(zhuǎn)船只數(shù)：表7－2(1)載貨航程需要的周轉(zhuǎn)船只數(shù)：《運籌學(xué)》