zt線性規(guī)劃的運(yùn)輸問(wèn)題(PPT 32)作業(yè)講解

1、課題：線性規(guī)劃的運(yùn)輸問(wèn)題13.2 用表上作業(yè)法求解運(yùn)輸問(wèn)題作業(yè)講解1 求解初始調(diào)運(yùn)方案（最小元素法）50210010300初始運(yùn)費(fèi)3*3+4*1+4*2+2*531(元)023.3 運(yùn)輸問(wèn)題的進(jìn)一步討論作業(yè)講解1 求解初始調(diào)運(yùn)方案（西北角法）1221221005初始運(yùn)費(fèi)9*1+3*2+9*1+4*2+2*542(元)033.3 運(yùn)輸問(wèn)題的進(jìn)一步討論供大于求的運(yùn)輸問(wèn)題1 求解初始調(diào)運(yùn)方案（沃格爾法）04初始運(yùn)費(fèi)3*3+4*1+4*2+2*531(元)hi vj 324133110500021100041 運(yùn)輸問(wèn)題的類型；運(yùn)輸問(wèn)題課堂內(nèi)容一 知識(shí)點(diǎn)回顧二 新知識(shí)點(diǎn)1 產(chǎn)銷不平衡運(yùn)輸問(wèn)題的類型；2

2、產(chǎn)銷不平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型；3 產(chǎn)銷不平衡運(yùn)輸問(wèn)題最優(yōu)解的計(jì)算；(1) 編制初始調(diào)運(yùn)方案最小元素法、(2) 解的最優(yōu)性檢驗(yàn)(3) 解的改進(jìn)閉回路法、確定換入的非基變量；確定換出的基變量；GO TO 2對(duì)偶變量法（位勢(shì)法）西北角法、沃格爾法2 產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法;4 運(yùn)輸問(wèn)題的應(yīng)用；53.3 運(yùn)輸問(wèn)題的進(jìn)一步討論運(yùn)輸表產(chǎn)銷不平衡問(wèn)題一 產(chǎn)銷不平衡問(wèn)題的類型63.3 運(yùn)輸問(wèn)題的進(jìn)一步討論一、產(chǎn)銷不平衡問(wèn)題的類型產(chǎn)銷不平衡問(wèn)題1 產(chǎn)量大于銷量目標(biāo)函數(shù)：st.73.3 運(yùn)輸問(wèn)題的進(jìn)一步討論2 銷量大于產(chǎn)量目標(biāo)函數(shù)：st.一、產(chǎn)銷不平衡問(wèn)題的類型產(chǎn)銷不平衡問(wèn)題8產(chǎn)銷不平衡問(wèn)題3.3 運(yùn)輸問(wèn)題

3、的進(jìn)一步討論1 產(chǎn)銷不平衡轉(zhuǎn)化為產(chǎn)銷平衡的模型求解；2 方法：增加一個(gè)虛擬的產(chǎn)地或銷地，從而變成標(biāo)準(zhǔn)型產(chǎn)銷平衡問(wèn)題。3 運(yùn)輸問(wèn)題產(chǎn)銷平衡模型，實(shí)質(zhì)上就是一個(gè)求解運(yùn)輸問(wèn)題的標(biāo)準(zhǔn)型。二、解題思路93.3 運(yùn)輸問(wèn)題的進(jìn)一步討論 1 產(chǎn)量大于銷量增加一個(gè)假想的銷地Bn+1，其銷量為bn+1 ；從Ai 運(yùn)到Bn+1的物品數(shù)量xi,n+1 ；（3） ci,n+1 =0 ； 因?yàn)锽n+1實(shí)際上不存在，所以xi,n+1 實(shí)際上就是就地存儲(chǔ)在產(chǎn)地Ai 的物品數(shù)量。因?yàn)榫偷卮尜A的物品無(wú)需運(yùn)輸，所以上式結(jié)果為三 不平衡模型轉(zhuǎn)化為平衡模型（1）（2）產(chǎn)銷不平衡問(wèn)題103.3 運(yùn)輸問(wèn)題的進(jìn)一步討論st.產(chǎn)量大于銷量的：

4、n+1n+1n+1三 不平衡模型轉(zhuǎn)化為平衡模型產(chǎn)銷不平衡問(wèn)題113.3 運(yùn)輸問(wèn)題的進(jìn)一步討論 2 銷量大于產(chǎn)量增加一個(gè)假想的產(chǎn)地Am+1，其產(chǎn)量為am+1 ；從Am+1 運(yùn)到Bj的物品數(shù)量xm+1,j ；（3） ci,n+1 =0 ； 因?yàn)锳m+1實(shí)際上不存在，所以xm+1,j實(shí)際上是各銷地Bj所需物品的欠缺額。因?yàn)閤m+1,j實(shí)際上并沒(méi)有被運(yùn)輸，所以上式結(jié)果為xm+1,j（1）（2）三 不平衡模型轉(zhuǎn)化為平衡模型產(chǎn)銷不平衡問(wèn)題123.3 運(yùn)輸問(wèn)題的進(jìn)一步討論st.銷量大于產(chǎn)量的：三 不平衡模型轉(zhuǎn)化為平衡模型產(chǎn)銷不平衡問(wèn)題m+1m+1m+1m+1133.3 運(yùn)輸問(wèn)題的進(jìn)一步討論供大于求的運(yùn)輸問(wèn)題

5、143.3 運(yùn)輸問(wèn)題的進(jìn)一步討論引入虛擬銷地B4 ，（或理解為倉(cāng)庫(kù)），就地“銷售”，運(yùn)費(fèi)為零000080180供大于求的運(yùn)輸問(wèn)題B4153.3 運(yùn)輸問(wèn)題的進(jìn)一步討論1 求解初始調(diào)運(yùn)方案（運(yùn)用最小元素法）供大于求的運(yùn)輸問(wèn)題2030201030601010303050105016解的改進(jìn)3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論0-306-1034-3-2-3-1-1-1-2-3-2供大于求的運(yùn)輸問(wèn)題ui vj 2 解的最優(yōu)性檢驗(yàn)（運(yùn)用位勢(shì)法）3 所有非基變量的檢驗(yàn)數(shù)都小于零，所以該解已經(jīng)是最優(yōu)解。173.3 運(yùn)輸問(wèn)題的進(jìn)一步討論彈性需求問(wèn)題運(yùn)價(jià) 地區(qū)煤礦甲乙丙丁產(chǎn)量 A B C1614191313202219

6、23171525506050最低需求最高需求3050707003010不限設(shè)有三煤礦供應(yīng)四地區(qū)，資料如下：183.3 運(yùn)輸問(wèn)題的進(jìn)一步討論對(duì)問(wèn)題進(jìn)行分析：虛擬產(chǎn)量的運(yùn)輸費(fèi)用為零,但它對(duì)于基本需求來(lái)講,運(yùn)費(fèi)為無(wú)窮大。本題產(chǎn)量160萬(wàn)噸，最低需求110萬(wàn)噸，最高需求無(wú)限。實(shí)質(zhì)上比較現(xiàn)實(shí)的最高需求210萬(wàn)噸;(?)1產(chǎn)量大于最小需求；小于最大需求。而標(biāo)準(zhǔn)型是：產(chǎn)量=銷量；2處理辦法：設(shè)想一個(gè)虛擬煤礦D，生產(chǎn)50萬(wàn)噸,但這個(gè)產(chǎn)量只能供應(yīng)可有可無(wú)的最高需求部分,于是各地的需求也應(yīng)分為兩個(gè)部分：基本需求、機(jī)動(dòng)需求；34彈性需求問(wèn)題19D 甲2 丁2 11MMM00030205010307050191416

7、251217 設(shè)想一個(gè)虛擬煤礦D,生產(chǎn)50萬(wàn)噸, 這個(gè)產(chǎn)量只能供應(yīng)可有可無(wú)的最高需求部分,于是各地的需求分為基本需求和機(jī)動(dòng)需求；16011021060203.3 運(yùn)輸問(wèn)題的進(jìn)一步討論求初始調(diào)運(yùn)方案1（使用最小元素法）105050050203020202003030000彈性需求問(wèn)題213.3 運(yùn)輸問(wèn)題的進(jìn)一步討論解的最優(yōu)性檢驗(yàn)2（使用位勢(shì)法）013M-13M-16+M13-M13-M13-M13-M13-M-3-M-3-M-9-M-4-M-4-M-2-2M-1-7M-1-4-6-6-M-M有大于零的檢驗(yàn)數(shù),所以原初始調(diào)運(yùn)方案不是最優(yōu)方案3解的改進(jìn)302020GO TO 2彈性需求問(wèn)題223.3

8、 運(yùn)輸問(wèn)題的進(jìn)一步討論013-12071212121212-4-4-10-5-5-2-2-7-4-6-6-M-M1-M0因?yàn)樗蟹腔兞康臋z驗(yàn)數(shù)都已經(jīng)小于等于零，所以該方案就是最優(yōu)調(diào)運(yùn)方案。彈性需求問(wèn)題4進(jìn)行解的最優(yōu)性檢驗(yàn)；523X44X423.3 運(yùn)輸問(wèn)題的進(jìn)一步討論三 轉(zhuǎn)運(yùn)與平衡的關(guān)聯(lián)假定m個(gè)產(chǎn)地A1,A2,Am和n個(gè)銷地B1,B2,Bn都可以作為中間轉(zhuǎn)運(yùn)站使用，從而發(fā)送物品的地點(diǎn)和接收物品的地點(diǎn)都有m+n個(gè)。A1 A2 B1 B2 B3 例令：ai第i個(gè)產(chǎn)地的產(chǎn)量（凈供應(yīng)量）；bj第j個(gè)銷地的銷量（凈需要量）；xij由第i個(gè)發(fā)送地運(yùn)到第j個(gè)接收地的物品數(shù)量；cij由第i個(gè)發(fā)送地到第j個(gè)接

9、收地的單位運(yùn)價(jià)；ci第i個(gè)地點(diǎn)轉(zhuǎn)運(yùn)單位物品的費(fèi)用；Q有轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題243.3 運(yùn)輸問(wèn)題的進(jìn)一步討論產(chǎn)銷表轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題25轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論運(yùn)價(jià)表263.3 運(yùn)輸問(wèn)題的進(jìn)一步討論st.m+nm+n轉(zhuǎn)運(yùn)模型：m+nm+nQ+Q+Qm+nm+n轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題27轉(zhuǎn)運(yùn)例題3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論左圖顯示出了一個(gè)運(yùn)輸系統(tǒng),它包括二個(gè)產(chǎn)地(和)二個(gè)銷地(和)及一個(gè)中間轉(zhuǎn)運(yùn)站(),各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應(yīng)節(jié)點(diǎn)處箭線旁的數(shù)字表示，節(jié)點(diǎn)連線上的數(shù)字為該地的轉(zhuǎn)運(yùn)單價(jià),試確定最優(yōu)運(yùn)輸方案。 32145311045403203052325645運(yùn)價(jià)表-4-1-3-5-3352M

10、5235425M2M65M54610+5040+5050505050505030+5030+5028表上作業(yè)法求解步驟3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論502050105030020405010205020125430687209一、初始調(diào)運(yùn)方案解初始調(diào)運(yùn)方案：x12,x22x24x25x33x34x14，,x44x55=相應(yīng)運(yùn)價(jià)為：c12,c22c24c25c33c34c14，,c44c5550,50202050010，,5050=-4,-1M4-352，,-3-529二、解的最優(yōu)性檢驗(yàn)和改進(jìn)3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論0M-23-5-11+M-41-M6-M-62-4-2M2-M-4-M-14-15-M-11-4M-116-2M-22+M-16M-10-94-M-5-M-15+M203020解新總運(yùn)費(fèi)=+=300（元）2*10+4*20+2*205*203*20+表上作業(yè)法求解步驟303.3 運(yùn)輸問(wèn)題的進(jìn)一步討論083-5-1-4-9-4-62-14-M-8-14-14-5-M-11-4-1-4-M-12-16-9-6-15-5解10-M空格檢驗(yàn)數(shù)都小余零，所以是最優(yōu)解.=300最小運(yùn)費(fèi)三、解的最優(yōu)性檢驗(yàn)表上作業(yè)法求解步驟x14,x23x25x34,=10,20202020,x34,31知識(shí)點(diǎn)回顧產(chǎn)銷不平衡運(yùn)輸問(wèn)題求解最優(yōu)運(yùn)輸