運輸問題-課件

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

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

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

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

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

由對偶性質，σij是原問題變量xij的檢驗數。

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

產銷平衡表

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

存儲費用：2×2+2×1=6(百元)總成本：39+6=45(百元)P98例2.4銷大于產運輸費用：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噸，《運籌學》第三章運輸問題Slide34例3．石家莊北方研究院有三個區(qū)，即一區(qū)、二區(qū)、三區(qū)，每年分別需要生活用煤和取暖用煤3000、1000、2000噸，由河北臨城，山西孟縣兩處煤礦負責供應，這兩處煤礦的價格相同，煤的質量也基本相同。兩處煤礦能供應北方研究院的煤的數量，山西盂縣為4000噸，河北臨城為l500噸，由煤礦至北方研究院的單位運價(百元／噸)見下表。由于需求大于供給，經院研究平衡決定一區(qū)供應量可減少0～200噸，二區(qū)需要量應全部滿足，三區(qū)供應量不少于1700噸。試求總運費最低的調運方案?！哆\籌學》《運籌學》第三章運輸問題Slide35河北臨城，山西孟縣兩處煤礦可以供應煤5500噸。一區(qū)、二區(qū)、三區(qū)至少需要煤5500噸。至多需要煤6000噸。一區(qū)和三區(qū)必須供應的煤分別為2800噸和1700噸。可以不供應的煤分別為200噸和300噸。產銷平衡表《運籌學》《運籌學》第三章運輸問題Slide36例4．設有三個化肥廠供應四個地區(qū)的農用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如下表所示，試求出總的運費最節(jié)省的化肥調運方案?！哆\籌學》《運籌學》第三章運輸問題Slide37三個化肥廠共可供應化肥160噸。問：根據現有三個化肥廠的產量，地區(qū)IV

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

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

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

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

為使各港口間調度周轉所需的空船數最少，其產銷平衡表如下。單位運價應為相應各港口之間的船只航程天數?？汕蟪隹沾淖顑?yōu)調度方案如下：《運籌學》《運籌學》第三章運輸問題Slide47

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

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

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

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

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

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

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

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

由對偶性質，σij是原問題變量xij的檢驗數。

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

產銷平衡表

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

存儲費用：2×2+2×1=6(百元)總成本：39+6=45(百元)P98例2.4銷大于產運輸費用：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噸，《運籌學》第三章運輸問題Slide90例3．石家莊北方研究院有三個區(qū)，即一區(qū)、二區(qū)、三區(qū)，每年分別需要生活用煤和取暖用煤3000、1000、2000噸，由河北臨城，山西孟縣兩處煤礦負責供應，這兩處煤礦的價格相同，煤的質量也基本相同。兩處煤礦能供應北方研究院的煤的數量，山西盂縣為4000噸，河北臨城為l500噸，由煤礦至北方研究院的單位運價(百元／噸)見下表。由于需求大于供給，經院研究平衡決定一區(qū)供應量可減少0～200噸，二區(qū)需要量應全部滿足，三區(qū)供應量不少于1700噸。試求總運費最低的調運方案?！哆\籌學》《運籌學》第三章運輸問題Slide91河北臨城，山西孟縣兩處煤礦可以供應煤5500噸。一區(qū)、二區(qū)、三區(qū)至少需要煤5500噸。至多需要煤6000噸。一區(qū)和三區(qū)必須供應的煤分別為2800噸和1700噸?？梢圆还拿悍謩e為200噸和300噸。產銷平衡表《運籌學》《運籌學》第三章運輸問題Slide92例4．設有三個化肥廠供應四個地區(qū)的農用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如下表所示，試求出總的運費最節(jié)省的化肥調運方案?！哆\籌學》《運籌學》第三章運輸問題Slide93三個化肥廠共可供應化肥160噸。問：根據現有三個化肥廠的產量，地區(qū)IV

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

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

表7－1《運籌學》表7－2(1)載貨航程需要的周轉船只數：表7－2(1)載貨航程需要的周轉船只數：《運籌學》