運(yùn)籌學(xué)第七講運(yùn)輸問題

教案要點(diǎn)復(fù)習(xí)可行解、基可行解，基及非基變量。本節(jié)重點(diǎn)：運(yùn)輸問題表上作業(yè)法步驟：⑴平衡產(chǎn)銷；⑵找出初始基可行解[西北角法、最小元素法]；⑶判別基可行解是否最優(yōu)[閉回路法、位勢法]；⑷非最優(yōu)的基可行解的迭代[閉回路調(diào)整法].

難點(diǎn)：計(jì)算步驟，基與非基，位勢計(jì)算。注意：細(xì)心，步驟，好的初始解通常能減少迭代次數(shù)。帶《數(shù)學(xué)模型》，《線性規(guī)劃理論及其應(yīng)用》兩書。第一頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題紹興文理學(xué)院工學(xué)院計(jì)算機(jī)系運(yùn)籌學(xué)第二頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題第七章運(yùn)輸問題一類特殊類型的LP問題——運(yùn)輸問題；模型、表上作業(yè)法應(yīng)用、用Excel求解討論第三頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題運(yùn)輸問題某種產(chǎn)品從若干個(gè)產(chǎn)地(產(chǎn)量已知)運(yùn)往若干個(gè)銷地(銷量已知)，已知各地間運(yùn)輸單價(jià)，求總運(yùn)費(fèi)最小的運(yùn)輸方案。此問題是我國科學(xué)家(王元,越民義等)在1959年前率先研究討論的，并獲得了：表上作業(yè)法和圖上作業(yè)法等重要結(jié)果。第四頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題運(yùn)輸問題產(chǎn)地?cái)?shù)m=2,銷地?cái)?shù)n=3,產(chǎn)銷平衡，決策變量個(gè)數(shù)m*n,等式約束數(shù)m+n，不等式約束數(shù)0,目標(biāo)函數(shù)是總運(yùn)價(jià),要求最小。第五頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題運(yùn)輸問題目標(biāo)函數(shù)：s.t.第六頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題運(yùn)輸問題它是典型的LP問題，但若用單純形法，[等式約束數(shù)m+n(但當(dāng)產(chǎn)銷平衡的時(shí)候其中有一個(gè)是多余的，),不等式約束數(shù)0]初始基可行解就顯得很難求，決策變量個(gè)數(shù)也較大，我國科學(xué)家在上世紀(jì)五十年代提出了解運(yùn)輸問題的圖上作業(yè)法和表上作業(yè)法。第七頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題表上作業(yè)法運(yùn)輸問題的表上作業(yè)法：平衡產(chǎn)銷；找出初始基可行解(西北角法、最小元素法、Vogel法)；基可行解是否最優(yōu)的判別(閉回路法、位勢法*)；非最優(yōu)的基可行解的改進(jìn)(閉回路調(diào)整法).

第八頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題平衡產(chǎn)銷運(yùn)輸問題中產(chǎn)銷不平衡時(shí)：產(chǎn)>銷：增加一個(gè)假想的倉庫，運(yùn)費(fèi)為0，當(dāng)新銷地。產(chǎn)<銷：增加一個(gè)假想的產(chǎn)地，運(yùn)費(fèi)為0。總可以調(diào)整為產(chǎn)銷平衡。

第九頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題找出初始基可行解運(yùn)輸問題的獨(dú)立的等式約束數(shù)=系數(shù)矩陣的秩=基變量個(gè)數(shù)=m+n-1，非基變量個(gè)數(shù)=m*n-m-n+1。找出初始基可行解(m+n-1格)：西北角法；最小元素法;伏格爾(Vogel)法*等.

第十頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題西北角法最后得的初始基可行解。34422223366第十一頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題找初始基可行解的西北角法盡量用下標(biāo)小的（左上角——西北角優(yōu)先安排）：x11=min(s1,d1)=d1=3,劃去第一列（B1已滿足）,s1←s1-x11；x12=min(s1-x11,d2)=4,劃去第一行（A1已滿足）；……劃去m+n-1行(列)大功告成。第十二頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題最小元素法最后得的初始基可行解(不同于西北角法)。31144363333第十三頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題找初始基可行解的最小元素法盡量先用運(yùn)價(jià)小的（就近優(yōu)先安排，可能“因小失大”）：c21=min(cij)=1,x21=min(s2,d1)=3劃去第一列（B1已滿足）s2←s2-x21；c23=min,x23=min(s2-x21,d3)=1劃去第二行（A2已滿足）d3←d3-x23；……劃去m+n-1行(列)大功告成。第十四頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題基可行解是否最優(yōu)的判別基可行解是否最優(yōu)的判別(閉回路法、位勢法*)；閉回路法求檢驗(yàn)數(shù),因?yàn)榉亲顑?yōu)的基可行解改進(jìn)時(shí)用閉回路調(diào)整,所以優(yōu)先介紹“閉回路法”位勢法求檢驗(yàn)數(shù)*.

第十五頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題閉回路法對每個(gè)非基變量(如x11)求它的閉回路;121求它的檢驗(yàn)數(shù)：3-1+2-3=1>0。檢驗(yàn)數(shù)無負(fù)是最優(yōu)解，否則可調(diào)整。314633-11012第十六頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題閉回路法調(diào)優(yōu)非基變量如x24檢驗(yàn)數(shù)負(fù),不是最優(yōu)解;利用它的閉回路調(diào)整:min(1,3)=1;調(diào)整:奇加偶減，新方案再檢驗(yàn)……。314633121-110121052第十七頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題位勢法判優(yōu)新方案再檢驗(yàn),逐個(gè)非基變量求檢驗(yàn)數(shù)太繁，可用位勢法求檢驗(yàn)數(shù)；檢驗(yàn)數(shù)全部非負(fù),找到最優(yōu)解(不唯一)。3132560310-23-590221912第十八頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題用Excel求解可以利用電子表格“Excel”中的“規(guī)劃求解”來解運(yùn)輸問題：先產(chǎn)銷平衡；找一個(gè)預(yù)解，求出行、列和；求出目標(biāo)函數(shù)的值；用“工具”下的“規(guī)劃求解”……。作業(yè)P.150№1a;P.152№6ab第十九頁，共二十頁。8/11/2023運(yùn)籌學(xué)第七講運(yùn)輸問題內(nèi)容總結(jié)教案要點(diǎn)。復(fù)習(xí)可行解、基可行解，基及非基變量。本節(jié)重點(diǎn)：運(yùn)輸問題表上作業(yè)法步驟：⑴平衡產(chǎn)銷。⑵找出初始基可行解[西北角法、最小元素法]。⑶判別基可行解是否最優(yōu)[閉回路法、位勢法]。⑷非最優(yōu)的基可行解的迭代[閉回路調(diào)整法].。注意：細(xì)心，步驟，。8/9/2023。運(yùn)籌學(xué)第七講運(yùn)輸問題。一類特殊類型的LP問題——運(yùn)輸問題。某種產(chǎn)品從若干個(gè)產(chǎn)地(產(chǎn)量已知)運(yùn)往若干個(gè)銷地(銷量