第3章、第5章復(fù)習(xí)_第1頁
第3章、第5章復(fù)習(xí)_第2頁
第3章、第5章復(fù)習(xí)_第3頁
第3章、第5章復(fù)習(xí)_第4頁
第3章、第5章復(fù)習(xí)_第5頁
已閱讀5頁,還剩77頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

第三章運(yùn)輸問題復(fù)習(xí)目錄一、運(yùn)輸問題及其數(shù)學(xué)模型

網(wǎng)絡(luò)圖、線性規(guī)劃模型、運(yùn)輸表二、用表上作業(yè)法求解運(yùn)輸問題初始解、解的檢驗(yàn)、解的改進(jìn)三、運(yùn)輸問題的進(jìn)一步討論

產(chǎn)銷不平衡一、運(yùn)輸問題及其數(shù)學(xué)模型設(shè)某種物品有m個(gè)產(chǎn)地A1,A2,...,Am,各產(chǎn)地的產(chǎn)量分別是a1,a2,...,am;有n個(gè)銷地B1,B2,...,Bn,各銷地的銷量分別為b1,b2,....bn。假定從產(chǎn)地Ai(i=1,2,…,m)向銷地出Bj(j=l,2,….n)運(yùn)輸單位物品的運(yùn)價(jià)是cij,問怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最小。運(yùn)輸問題的描述:運(yùn)輸問題運(yùn)輸表

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1c11c12c1na1x11x12x1nA1c21c22c2na1x21x22x2n……A1cm1cm2cmnamxm1xm2xmn銷地b1b2…bnxij:Ai到Bj的物品數(shù)量Cij:Ai到Bj的單位運(yùn)價(jià)bj:所有產(chǎn)地運(yùn)到銷地Bj的物品數(shù)量ai:產(chǎn)地Ai運(yùn)到所有銷地的物品數(shù)量產(chǎn)銷平衡:運(yùn)輸問題線性規(guī)劃模型產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型表示:某一產(chǎn)地運(yùn)往各個(gè)銷地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量各個(gè)產(chǎn)地運(yùn)往某一銷地的物品數(shù)量之和等于該銷地的銷量二、表上作業(yè)法表上作業(yè)法是一種迭代法,迭代步驟為:1、先按某種規(guī)則找出一個(gè)初始解(初始調(diào)運(yùn)方案);2、再對現(xiàn)行解作最優(yōu)性判別;3、若這個(gè)解不是最優(yōu)解,就在運(yùn)輸表上對它進(jìn)行調(diào)整改進(jìn),得出—個(gè)新解;4、再判別,再改進(jìn);5、直至得到運(yùn)輸問題的最優(yōu)解為止。迭代過程中得出的所有解都要求是運(yùn)輸問題的基可行解。1、找出初始基可行解最小元素法西北角法沃格爾法813131466練習(xí)題練習(xí)西北角法:在滿足約束條件下盡可能的給最左上角的變量最大值.最小元素法:思路:為了減少運(yùn)費(fèi),應(yīng)優(yōu)先考慮單位運(yùn)價(jià)最小(或運(yùn)距最短)的供銷業(yè)務(wù),最大限度地滿足其供銷量。在可供物品已用完的產(chǎn)地或需求已全部滿足的銷地,以后將不再考慮。然后,在余下的供、銷點(diǎn)的供銷關(guān)系中,繼續(xù)按上述方法安排調(diào)運(yùn),直至安排完所有供銷任務(wù),得到一個(gè)完整的調(diào)運(yùn)方案(完整的解)為止。這樣就得到了運(yùn)輸問題的一個(gè)初始基可行解(初始調(diào)運(yùn)方案)。由于該方法基于優(yōu)先滿足單位運(yùn)價(jià)(或運(yùn)距)最小的供銷業(yè)務(wù),故稱為最小元素法。銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量81412144882101486所以,初始基可行解為:……目標(biāo)函數(shù)值Z=2462108600000060沃格爾法: 對每一個(gè)供應(yīng)地或銷售地,均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)價(jià)中找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià),并稱這兩個(gè)單位運(yùn)價(jià)之差為該供應(yīng)地或銷售地的罰數(shù)?;舅枷耄涸诹P數(shù)最大處采用最小運(yùn)費(fèi)調(diào)運(yùn)。沃格爾法:計(jì)算步驟:1)分別算出各行、各列的罰數(shù)。2)從行、列中選出差額最大者,選擇它所在行、列中的最小元素,進(jìn)行運(yùn)量調(diào)整。3)對剩余行、列再分別計(jì)算各行、列的差額。返回1)、2)。481412148銷量2261158A31093102A216114124A1產(chǎn)量B4B3B2B1銷地產(chǎn)地54321列罰數(shù)54321行罰數(shù)0112513銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量81412144814目標(biāo)函數(shù)值Z=244881224思路:要判定運(yùn)輸問題的某個(gè)解是否為最優(yōu)解,可仿照一般單純形法,檢驗(yàn)這個(gè)解的各非基變量(對應(yīng)于運(yùn)輸表中的空格)的檢驗(yàn)數(shù),若所有空格的檢驗(yàn)數(shù)全非負(fù),這個(gè)解就是最優(yōu)解。2、解的最優(yōu)性檢驗(yàn)閉回路法對偶變量法(位勢法)2、解的最優(yōu)性檢驗(yàn)從每一個(gè)空格出發(fā)找一條閉回路,它是以某一個(gè)空格為起點(diǎn),用水平或垂直線向前劃,每碰到一個(gè)數(shù)字格轉(zhuǎn)90度,繼續(xù)前進(jìn),直到回到起始空格為止。解的最優(yōu)性檢驗(yàn)——閉回路法:求某個(gè)空格(非基變量)的檢驗(yàn)數(shù),先找出它在運(yùn)輸表上的閉回路。B1B2B3B4A1A2A3閉回路的特征:1.每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn).2.每一邊都是水平或垂直的.3.每一行(或列)若有閉回路的頂點(diǎn),則必有兩個(gè).4.閉回路的頂點(diǎn),除這個(gè)空格外,其它均為填有數(shù)字的格。5.每個(gè)空格都唯一存在這樣的一條閉回路。6.某空格的檢驗(yàn)數(shù)是以該空格為第一個(gè)頂點(diǎn),回路的奇數(shù)頂點(diǎn)運(yùn)價(jià)和減去其偶數(shù)頂點(diǎn)運(yùn)價(jià)和。

7.閉回路可以是簡單的矩形,也可以是復(fù)雜的多邊形。5練習(xí)題5557559575-115795-3579-115-3579-11解的最優(yōu)性檢驗(yàn)--對偶變量法(位勢法)位勢法計(jì)算步驟:1.在表中添加位一勢列ui和位勢行vj2.計(jì)算位勢3.計(jì)算檢驗(yàn)數(shù)例:銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA141241116A22103910A38511622銷量814121448vj82101486位勢法計(jì)算步驟1.在表中添加位一勢列ui和位勢行vj2.計(jì)算位勢3.計(jì)算檢驗(yàn)數(shù)銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA141241116A22103910A38511622銷量814121448vj821014860411-13-510位勢法計(jì)算步驟1.在表中添加位一勢列ui和位勢行vj2.計(jì)算位勢3.計(jì)算檢驗(yàn)數(shù)銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA141241116A22103910A38511622銷量814121448vj821014860411-13-510121-110123、解的改進(jìn)-閉回路調(diào)整法改進(jìn)的方法是在運(yùn)輸表中找出檢驗(yàn)數(shù)為負(fù)的空格對應(yīng)的閉回路,在滿足所有約束條件的前提下,使xij盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點(diǎn)的運(yùn)輸量,以得到另一個(gè)更好的基可行解。解改進(jìn)的具體步驟:(1)以xij為換入變量,找出它在運(yùn)輸表中的閉回路;(2)以空格(Ai,Bj)為第一個(gè)奇數(shù)頂點(diǎn),沿閉回路的順(或逆)時(shí)針方向前進(jìn),對閉回路上的頂點(diǎn)依次編號;(3)在閉回路上的所有偶數(shù)頂點(diǎn)中,找出運(yùn)輸量最小的頂點(diǎn)(格子),以該格中的變量為換出變量;(4)以換出變量的運(yùn)輸量為調(diào)整量,將該閉回路上所有奇數(shù)頂點(diǎn)處的運(yùn)輸量都增加這一數(shù)值,所有偶數(shù)頂點(diǎn)處的運(yùn)輸量都減去這一數(shù)值,從而得出一新的運(yùn)輸方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例:1211012-182101486銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例:-182101486(2)(-2)(2)(-2)銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例:81214842銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例:821214840229121由于所有非基變量的檢驗(yàn)數(shù)全非負(fù),故這個(gè)解為最優(yōu)解。解為:Minz=244選擇進(jìn)基變量,確定離基變量x31進(jìn)基,min{x21,x33}=min{8,6}=6,x33離基-35579-11練習(xí)題(6)(-6)(6)(-6)6212調(diào)整運(yùn)量,重新計(jì)算檢驗(yàn)數(shù),確定進(jìn)基、離基變量x14進(jìn)基,min{x11,x34}=min{14,13}=13,x34離基1155-4-28調(diào)整運(yùn)量,重新計(jì)算檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)非負(fù),得到最優(yōu)解。Minz=6×1+3×13+8×2+4×13+2×12+5×19=1421155482練習(xí):用位勢法檢驗(yàn)下表給出的解是否是最優(yōu)解,若不是請對其進(jìn)行改進(jìn)例:銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36563614334、需要說明的幾個(gè)問題1.若運(yùn)輸問題的某一基可行解有幾個(gè)非基變量的檢驗(yàn)數(shù)均為負(fù),取小于零的檢驗(yàn)數(shù)中最小者對應(yīng)的變量為換入變量。2.當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時(shí),如果有某非基變量的檢驗(yàn)數(shù)等于零,則說明該運(yùn)輸問題有多重(無窮多)最優(yōu)解。初始解退化——即初始基變量的個(gè)數(shù)少于m+n1。在確定初始解的供需關(guān)系時(shí),同時(shí)劃去一行一列。調(diào)整后出現(xiàn)退化解——閉回路中有(-)標(biāo)記中有兩個(gè)或以上相等的最小數(shù)。必須在一數(shù)字格中填入0,以表明其為基變量,以保證在迭代過程中基變量的個(gè)數(shù)恰好為m+n-1個(gè)。3.(二)退化某一基變量的值為0例:退化解例:銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311457A277384A3121069銷量3656366√√√√三、運(yùn)輸問題的進(jìn)一步討論產(chǎn)銷不平衡的運(yùn)輸問題應(yīng)用問題舉例產(chǎn)銷不平衡的運(yùn)輸問題(Ⅰ)產(chǎn)銷平衡問題:產(chǎn)大于銷產(chǎn)銷不平衡產(chǎn)銷平衡產(chǎn)>銷的不平衡問題模型:運(yùn)價(jià)表為:

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1c11c12c1na1x11x12x1nA1c21c22c2na2x21x22x2n……A1cm1cm2cmnamxm1xm2xmn銷地b1b2…bn00…0Bn+1(貯存)x1,n+1x2,n+1xm,n+1產(chǎn)銷不平衡供過于求,即ai>bj

,增加一個(gè)虛收點(diǎn)Dn+1,bn+1=ai

-bj

,令wi,n+1=0,i=1,2,…,m供小于求,即ai<bj

,增加一個(gè)虛發(fā)點(diǎn)Wm+1,am+1=bj-ai

,令wm+1,j=0,j=1,2,…,n運(yùn)用舉例例1、石家莊北方研究院有三個(gè)區(qū),即一區(qū)、二區(qū)、三區(qū),每年分別需要生活用煤和取暖用煤3000、1000、2000噸,由河北,山西兩處煤礦負(fù)責(zé)供應(yīng),這兩處煤礦的價(jià)格相同,煤的質(zhì)量也基本相同,兩處煤礦能供應(yīng)北方研究院的煤的數(shù)量,山西為4000噸,河北為1500噸,由煤礦至北方研究院的單位運(yùn)價(jià)(百元/噸)見下表:

①需求大于供給的運(yùn)輸問題一區(qū)二區(qū)三區(qū)山西1.651.701.75河北1.601.651.70銷地產(chǎn)地運(yùn)輸單價(jià)產(chǎn)量40001500需求量300010002000應(yīng)用舉例

①需求大于供給的運(yùn)輸問題三區(qū)2三區(qū)1二區(qū)一區(qū)2一區(qū)11500河北需求量(噸)4000山西供應(yīng)量(噸)石家莊北方研究院銷地產(chǎn)地單位運(yùn)價(jià)60006000由于需大于供,經(jīng)院研究平衡決定一區(qū)供應(yīng)量可減少0~200噸,二區(qū)需要量應(yīng)全部滿足,三區(qū)供應(yīng)量不少于1600噸。試求總運(yùn)費(fèi)為最低的調(diào)運(yùn)方案。280020010001600400M0MM0500假想生產(chǎn)點(diǎn)1.651.601.701.651.751.701.751.701.651.60運(yùn)用舉例

①需求大于供給的運(yùn)輸問題石家莊北方研究院供應(yīng)量(噸)一區(qū)1一區(qū)2二區(qū)三區(qū)1三區(qū)2山西1.651.651.701.751.754000河北1.601.601.651.701.701500假想生產(chǎn)點(diǎn)M0MM0500需求量(噸)280020010001600400銷地產(chǎn)地單位運(yùn)價(jià)600060001300100016001500200300100運(yùn)用舉例

①需求大于供給的運(yùn)輸問題石家莊北方研究院一區(qū)1一區(qū)2二區(qū)三區(qū)1三區(qū)2山西1.651.651.701.751.75河北1.601.601.651.701.70假想生產(chǎn)點(diǎn)M0MM0銷地產(chǎn)地單位運(yùn)價(jià)uv00.050.11.601.650.10.1-0.1石家莊北方研究院一區(qū)1一區(qū)2二區(qū)三區(qū)1三區(qū)2山西1.651.651.701.751.75河北1.601.601.651.701.70假想生產(chǎn)點(diǎn)M0MM01300100016001500200300100運(yùn)用舉例一區(qū)二區(qū)三區(qū)供應(yīng)量山西1.651.701.754000河北1.601.651.701500需求量2900100016005500銷地產(chǎn)地運(yùn)輸單價(jià)14001500100016005500最優(yōu)供應(yīng)方案:判斷按最小元素法(或沃格爾法)給出的初始基可行解,從每一空格找出的閉回路不唯一。 如果運(yùn)輸問題單位運(yùn)價(jià)表的某一行(或某一列)元素分別加上一個(gè)常數(shù)k,最優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化。 已知運(yùn)輸問題的調(diào)運(yùn)和運(yùn)價(jià)表如下,求最優(yōu)調(diào)運(yùn)方案和最小總費(fèi)用。已知運(yùn)輸問題的調(diào)運(yùn)和運(yùn)價(jià)表如下,求最優(yōu)調(diào)運(yùn)方案和最小總費(fèi)用。第五章整數(shù)規(guī)劃復(fù)習(xí)如果所有的變量都為整數(shù),則該線性規(guī)劃稱為純整數(shù)線性規(guī)劃;如果有一部分變量必須取整數(shù),另一部分可以不取整數(shù)值的線性規(guī)劃,則稱之為混合整數(shù)線性規(guī)劃。如果所有的變量只能取0或1,則稱之為0-1規(guī)劃。maxz=Cxmaxz=CxLP:s.tAx=bLIP:s.tAx=bx≥0x≥0,x各分量部分或全體取整數(shù)整數(shù)線性規(guī)劃

(Integerprogramming) 任何求最大目標(biāo)函數(shù)值的整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃(松弛問題)的最大目標(biāo)函數(shù)值。maxz=Cxmaxz=CxLP:s.tAx=bLIP:s.tAx=bx≥0x≥0,x各分量部分或全體取整數(shù)目前求解整數(shù)規(guī)劃常用的方法有:

割平面法 分枝定界法對于特別的0-1規(guī)劃問題采用:隱枚舉法匈牙利法該方法的基本思想是首先求解整數(shù)規(guī)劃(IP)對應(yīng)的松弛問題(LP),如果(LP)的最優(yōu)解不是整數(shù)解,則逐次增加一個(gè)新約束(即割平面),它能割去松弛問題可行域中不含整數(shù)解的區(qū)域.逐次切割,直到得到一個(gè)整數(shù)最優(yōu)極點(diǎn)(即整數(shù)解)為止.割平面法如何構(gòu)造割平面?

例1:用割平面法求解下面的IP.maxz=x1+x2s.t.

解:將對應(yīng)的LP問題化為標(biāo)準(zhǔn)形,用單純形法求解.X0=(7/6,8/3)T.

割平面法割平面尋找方法:在最終單純形表中選擇具有最大小數(shù)部分的非整分量所在的行構(gòu)造割平面:整數(shù)=非負(fù)真分?jǐn)?shù)-正數(shù)若在對某整數(shù)規(guī)劃問題的松馳問題進(jìn)行求解時(shí),得到最優(yōu)單純形表中,x1為基變量,所在行方程為則以X1行構(gòu)造的割平面方程為分枝定界法分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效方法,它不僅能針對純整數(shù)規(guī)劃問題求解,也能對混合整數(shù)規(guī)劃問題求解.分枝定界法由“分枝”和“定界”兩部分組成.(BranchandBoundMethod)分枝定界法求解步驟求解整數(shù)規(guī)劃相應(yīng)的線性規(guī)劃問題;如果其最優(yōu)解符合整數(shù)條件,則線性規(guī)劃問題的最優(yōu)解就是整數(shù)規(guī)劃問題的解.如果其最優(yōu)解不符合整數(shù)條件,則求出整數(shù)規(guī)劃的上下界用增加約束條件的方法,并把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域(稱為分枝),再求解這些子區(qū)域上的線性規(guī)劃問題.不斷縮小最優(yōu)目標(biāo)函數(shù)值上下界的距離,當(dāng)上下界的值相等時(shí),整數(shù)規(guī)劃的解就被求出(BranchandBoundMethod)分枝定界法在分枝定界法中,若選X1=4/3進(jìn)行分支,則構(gòu)造的約束條件應(yīng)為?用分枝定界法求極小化的整數(shù)規(guī)劃問題時(shí),任何一個(gè)可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的?第四節(jié)0—1規(guī)劃

如果線性規(guī)劃中的所有變量的取值只能取0、1,則這類線性規(guī)劃問題是一種特殊的整數(shù)規(guī)劃問題,我們把它稱為0—1規(guī)劃,把只取0或1值的變量稱為0—1變量.求解0—1規(guī)劃常用隱枚舉法.

首先將全部變量取0或1的所有組合(解)列出,然后在逐個(gè)檢查這些組合(解)是否可行的過程中,利用增加并不斷修改過濾條件的辦法,減少計(jì)算量,達(dá)到求出最優(yōu)解的目的.例:求解0-1整數(shù)規(guī)劃s.t.

隱枚舉法

-23316在生活中經(jīng)常遇到這樣的問題,某單位需完成n項(xiàng)任務(wù),恰好有n個(gè)人可承擔(dān)這些任務(wù)。由于每人的專長不同,各人完成任務(wù)不同(或所費(fèi)時(shí)間),效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù),使完成n項(xiàng)任務(wù)的總效率最高(或所需總時(shí)間最小)。這類問題稱為指派問題或分派問題(assignmentproblem)。第五節(jié)指派問題

例有一份中文說明書,需譯成英、日、德、俄四種文字。分別記作E、J、G、R?,F(xiàn)有甲、乙、丙、丁四人。他們將中文說明書翻譯成不同語種的說明書所需時(shí)間如表5-7所示。問應(yīng)指派何人去完成何工作,使所需總時(shí)間最少?

指派問題的最優(yōu)解有這樣性質(zhì),

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論