第3章、第5章復(fù)習(xí)

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

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

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

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

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

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

，增加一個虛收點Dn+1，bn+1=ai

-bj

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

，增加一個虛發(fā)點Wm+1，am+1=bj-ai

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

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

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

①需求大于供給的運輸問題石家莊北方研究院供應(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)點M0MM0500需求量(噸)280020010001600400銷地產(chǎn)地單位運價600060001300100016001500200300100運用舉例

①需求大于供給的運輸問題石家莊北方研究院一區(qū)1一區(qū)2二區(qū)三區(qū)1三區(qū)2山西1.651.651.701.751.75河北1.601.601.651.701.70假想生產(chǎn)點M0MM0銷地產(chǎn)地單位運價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)點M0MM01300100016001500200300100運用舉例一區(qū)二區(qū)三區(qū)供應(yīng)量山西1.651.701.754000河北1.601.651.701500需求量2900100016005500銷地產(chǎn)地運輸單價14001500100016005500最優(yōu)供應(yīng)方案：判斷按最小元素法（或沃格爾法）給出的初始基可行解，從每一空格找出的閉回路不唯一。 如果運輸問題單位運價表的某一行（或某一列）元素分別加上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化。 已知運輸問題的調(diào)運和運價表如下，求最優(yōu)調(diào)運方案和最小總費用。已知運輸問題的調(diào)運和運價表如下，求最優(yōu)調(diào)運方案和最小總費用。第五章整數(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) 任何求最大目標函數(shù)值的整數(shù)規(guī)劃的最大目標函數(shù)值小于或等于相應(yīng)的線性規(guī)劃（松弛問題）的最大目標函數(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ù)解，則逐次增加一個新約束（即割平面），它能割去松弛問題可行域中不含整數(shù)解的區(qū)域.逐次切割，直到得到一個整數(shù)最優(yōu)極點（即整數(shù)解）為止.割平面法如何構(gòu)造割平面？

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

解：將對應(yīng)的LP問題化為標準形，用單純形法求解.X0=(7/6,8/3)T.

割平面法割平面尋找方法：在最終單純形表中選擇具有最大小數(shù)部分的非整分量所在的行構(gòu)造割平面：整數(shù)＝非負真分數(shù)-正數(shù)若在對某整數(shù)規(guī)劃問題的松馳問題進行求解時，得到最優(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)目標函數(shù)值上下界的距離，當上下界的值相等時，整數(shù)規(guī)劃的解就被求出(BranchandBoundMethod)分枝定界法在分枝定界法中，若選X1=4／3進行分支，則構(gòu)造的約束條件應(yīng)為？用分枝定界法求極小化的整數(shù)規(guī)劃問題時，任何一個可行解的目標函數(shù)值是該問題目標函數(shù)值的？第四節(jié)0—1規(guī)劃

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

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

隱枚舉法

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

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

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