運(yùn)輸問題-課件

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

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

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

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

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

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

當(dāng)xij是基變量時(shí)，σij=0，此時(shí)有由此求出Ui和Vj，再代回（*）式求非基變量的σij（空格檢驗(yàn)數(shù)）P93-94運(yùn)輸問題對偶問題σ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)整改進(jìn)的閉環(huán)回路方法——迭代若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選其中最小的負(fù)檢驗(yàn)數(shù)。以(24)格為調(diào)入格，以此格為出發(fā)點(diǎn)，作一閉環(huán)回路。在閉回路上進(jìn)行運(yùn)量調(diào)整，使選定空格處的運(yùn)量盡可能地增加（即取相鄰兩數(shù)字格中較小的）。運(yùn)量調(diào)整后，必然使某個(gè)數(shù)字格變成零。把一個(gè)變成零的數(shù)字格抹去，得新的調(diào)運(yùn)方案。經(jīng)檢驗(yàn)，所有檢驗(yàn)數(shù)都非負(fù)，故達(dá)到最優(yōu)，最優(yōu)方案總運(yùn)費(fèi)最小是85元。3、調(diào)整改進(jìn)的閉環(huán)回路方法——迭代若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide22課堂作業(yè)：1、用表上作業(yè)法求出最優(yōu)解。（最小元素法）2、用伏格爾法直接給出近似最優(yōu)解?！哆\(yùn)籌學(xué)》《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide231、這是一個(gè)產(chǎn)銷平衡的問題。1）初始調(diào)運(yùn)方案（最小元素法）401520251025初始調(diào)運(yùn)方案的總運(yùn)費(fèi)為420元。2）最優(yōu)解的判別（閉環(huán)回路法）《運(yù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ù)法）：《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide263)調(diào)整調(diào)運(yùn)方案，得新的方案。以(22)格為調(diào)入格，以此格為出發(fā)點(diǎn)，作一閉環(huán)回路。經(jīng)檢驗(yàn)，所有檢驗(yàn)數(shù)都大于0，該調(diào)運(yùn)方案是最優(yōu)的方案?？傔\(yùn)費(fèi)為395元。401520251025151520253525《運(yùn)籌學(xué)》2、用伏格爾法直接給出近似最優(yōu)解。52020252010002、用伏格爾法直接給出近似最優(yōu)解。5202025201000運(yùn)輸問題-課件《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide29用伏格爾法直接找到了近似最優(yōu)方案，總運(yùn)價(jià)為305元?！哆\(yùn)籌學(xué)》《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide30第二種算法：用伏格爾法直接找到了近似最優(yōu)方案，總運(yùn)價(jià)為345元。用伏格爾法求解，是否一定要轉(zhuǎn)化為產(chǎn)銷平衡表？《運(yùn)籌學(xué)》三、產(chǎn)銷不平衡的運(yùn)輸問題

產(chǎn)銷平衡表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)xij是基變量時(shí)，σij=0，此時(shí)有由此求出Ui和Vj，再代回（*）式求非基變量的σij（空格檢驗(yàn)數(shù)）P93-94運(yùn)輸問題對偶問題σ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)整改進(jìn)的閉環(huán)回路方法——迭代若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選其中最小的負(fù)檢驗(yàn)數(shù)。以(24)格為調(diào)入格，以此格為出發(fā)點(diǎn)，作一閉環(huán)回路。在閉回路上進(jìn)行運(yùn)量調(diào)整，使選定空格處的運(yùn)量盡可能地增加（即取相鄰兩數(shù)字格中較小的）。運(yùn)量調(diào)整后，必然使某個(gè)數(shù)字格變成零。把一個(gè)變成零的數(shù)字格抹去，得新的調(diào)運(yùn)方案。經(jīng)檢驗(yàn)，所有檢驗(yàn)數(shù)都非負(fù)，故達(dá)到最優(yōu)，最優(yōu)方案總運(yùn)費(fèi)最小是85元。3、調(diào)整改進(jìn)的閉環(huán)回路方法——迭代若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide78課堂作業(yè)：1、用表上作業(yè)法求出最優(yōu)解。（最小元素法）2、用伏格爾法直接給出近似最優(yōu)解?！哆\(yùn)籌學(xué)》《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide791、這是一個(gè)產(chǎn)銷平衡的問題。1）初始調(diào)運(yùn)方案（最小元素法）401520251025初始調(diào)運(yùn)方案的總運(yùn)費(fèi)為420元。2）最優(yōu)解的判別（閉環(huán)回路法）《運(yù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ù)法）：《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide823)調(diào)整調(diào)運(yùn)方案，得新的方案。以(22)格為調(diào)入格，以此格為出發(fā)點(diǎn)，作一閉環(huán)回路。經(jīng)檢驗(yàn)，所有檢驗(yàn)數(shù)都大于0，該調(diào)運(yùn)方案是最優(yōu)的方案?？傔\(yùn)費(fèi)為395元。401520251025151520253525《運(yùn)籌學(xué)》2、用伏格爾法直接給出近似最優(yōu)解。52020252010002、用伏格爾法直接給出近似最優(yōu)解。5202025201000運(yùn)輸問題-課件《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide85用伏格爾法直接找到了近似最優(yōu)方案，總運(yùn)價(jià)為305元。《運(yùn)籌學(xué)》《運(yùn)籌學(xué)》第三章運(yùn)輸問題Slide86第二種算法：用伏格爾法直接找到了近似最優(yōu)方案，總運(yùn)價(jià)為345元。用伏格爾法求解，是否一定要轉(zhuǎn)化為產(chǎn)銷平衡表？《運(yùn)籌學(xué)》三、產(chǎn)銷不平衡的運(yùn)輸問題

產(chǎn)銷平衡表

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

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

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

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

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