12五月2024運(yùn)輸問題2.1運(yùn)輸問題及其模型例某公司經(jīng)銷一種產(chǎn)品，它下設(shè)三個(gè)工廠、四個(gè)銷售部。三個(gè)工廠的日產(chǎn)量分別為：A1—7噸，A2—4噸，A3—9噸；各銷售部的日銷量分別為：B1—3噸，B2—6噸，B3—5噸，B4—6噸。各廠到各銷售部的單位產(chǎn)品的運(yùn)價(jià)如右表。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，才能完成運(yùn)輸任務(wù)而使運(yùn)費(fèi)最省。用線性規(guī)劃法處理此問題。設(shè)由產(chǎn)地i到銷地j的運(yùn)量為xij，模型為：minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)運(yùn)輸問題一般用表上作業(yè)法求解，需建立表格模型：單位運(yùn)價(jià)表產(chǎn)銷平衡表2.2表上作業(yè)法表上作業(yè)法的步驟類似于單純形法:(1)給出初始調(diào)運(yùn)方案。(2)檢驗(yàn)方案是否最優(yōu),若是最優(yōu)解,則停止計(jì)算;否則轉(zhuǎn)下一步。(3)調(diào)整調(diào)運(yùn)方案，得新的方案。(4)重復(fù)(2),(3)直到求出最優(yōu)方案。2.2.1給出初始調(diào)運(yùn)方案最常用的方法——最小元素法表上作業(yè)法要求，調(diào)運(yùn)方案的數(shù)字格必須為m+n-1個(gè)，且有數(shù)字格不構(gòu)成閉回路。一般，用最小元素法給出的方案符合這一要求。314633最小元素法中的退化情況360542出現(xiàn)退化時(shí)，要在同時(shí)被劃去的行列中任選一個(gè)空格填0，此格作為有數(shù)字格。位勢表10219-48（2）（9）（8）（9）（-3）（-2）檢驗(yàn)數(shù)表若所有檢驗(yàn)數(shù)非負(fù)則是最優(yōu)解2.2.2最優(yōu)性檢驗(yàn)的方法——位勢法（1）從一個(gè)檢驗(yàn)數(shù)為負(fù)數(shù)且最小的空格出發(fā)，和其它數(shù)字格構(gòu)成閉回路?？勺C，此閉回路存在且唯一。（2）在閉回路上進(jìn)行運(yùn)量調(diào)整，使選定空格處的運(yùn)量盡可能地增加。（3）運(yùn)量調(diào)整后，必然使某個(gè)數(shù)字格變成零。把一個(gè)變成零的數(shù)字格抹去，得新的調(diào)運(yùn)方案。2.2.3方案調(diào)整的方法閉回路法位勢表10219-48（2）（9）（8）（9）（-3）（-2）檢驗(yàn)數(shù)表有檢驗(yàn)數(shù)為負(fù),不是最優(yōu)解。2.2.4表上作業(yè)法舉例位勢表10128-37（3）（9）（7）（1）（-2）（-2）檢驗(yàn)數(shù)表表上作業(yè)法舉例(續(xù))檢驗(yàn)數(shù)都非負(fù)，得最優(yōu)解。表上作業(yè)法是以產(chǎn)銷平衡為前提的，即當(dāng)實(shí)際問題產(chǎn)銷不平衡時(shí)，需要轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題，具體來說有兩種情況：（1）產(chǎn)大于銷，即此時(shí)增加一個(gè)假想的銷地n+1，該銷地的銷量為，而各產(chǎn)地到假想銷地的單位運(yùn)價(jià)定為0，就轉(zhuǎn)化成產(chǎn)銷平衡的運(yùn)輸問題。（2）銷大于產(chǎn)，即此時(shí)增加一個(gè)假想的產(chǎn)地m+1，該產(chǎn)地的產(chǎn)量為，而假想產(chǎn)地到各銷地的單位運(yùn)價(jià)定為0，就轉(zhuǎn)化成產(chǎn)銷平衡的運(yùn)輸問題。2.3產(chǎn)銷不平衡的運(yùn)輸問題產(chǎn)銷不平衡的運(yùn)輸問題舉例設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送化肥的單位運(yùn)價(jià)如又表：試求出總運(yùn)費(fèi)最省的花費(fèi)調(diào)運(yùn)方案。解：三個(gè)廠的總產(chǎn)量為160萬噸，四個(gè)地區(qū)的最低需求為110萬噸，最高需求為無限。地區(qū)Ⅳ每年最多能分配到60萬噸，這樣四個(gè)地區(qū)最高需求為210萬噸，銷大于產(chǎn)。于是，增加虛產(chǎn)地D，產(chǎn)量為50萬噸。還要把地區(qū)Ⅰ和Ⅳ的產(chǎn)量分為兩部分。建立如下表格模型：

50201030302003020例某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。又知如果生產(chǎn)出來的柴油機(jī)當(dāng)季度不交貨，每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)為0.15萬元。試安排全年生產(chǎn)計(jì)劃，使總費(fèi)用最低。2.4應(yīng)用舉例解：各季度都產(chǎn)出產(chǎn)品，都可看作產(chǎn)地；各季度都有定貨，都可看作銷地。這是一個(gè)產(chǎn)大于銷的運(yùn)輸問題，需增加虛銷地D。表格模型如下：產(chǎn)銷平衡表10.810.9511.1011.250M11.1011.2511.400MM11.0011.150MMM11.300單位運(yùn)價(jià)表101505302010