IE案例分析(一)

1、IE案例分析案例分析王曉光武漢理工大學(xué)機(jī)電工程學(xué)院案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃 某風(fēng)景區(qū)有五個(gè)景點(diǎn)見圖所示，S為景區(qū)入口，T為景區(qū)出口，A，B，C，D，E為五個(gè)景點(diǎn)。其中各個(gè)景點(diǎn)距離見圖標(biāo)。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃有如下問題需要解決：電信公司需要安裝電話線路，聯(lián)通各個(gè)景點(diǎn)和進(jìn)出口，則最小線路安裝是什么？現(xiàn)在，在入口S處有一個(gè)游覽車，一游客有急事需要到出口T，問游覽車如何行使可以使游客盡快到達(dá)出口？1. 現(xiàn)在要在以上各個(gè)地方中的某一處修建一所醫(yī)務(wù)中心，問應(yīng)建在何處，能使各個(gè)景點(diǎn)都離他最近？案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃有如下問題需要解決：現(xiàn)在要在以上各地方中

2、的某一處修建一所會(huì)議中心，已知各個(gè)景點(diǎn)的員工分別是40,25,45,30,20,35,50，那么會(huì)議中心應(yīng)建在何處，能使各個(gè)景點(diǎn)的員工走的總路程最短？4. 為了保護(hù)園區(qū)野生生態(tài)環(huán)境，現(xiàn)在規(guī)定每條線路上觀光旅游車的數(shù)量是一定的，見下圖，其中每條弧上的數(shù)字為通行車輛容量，那么如何在不違背每條線路旅游車輛數(shù)目限制下尋求最多的車輛通行？案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃電信公司需要安裝電話線路，聯(lián)通各個(gè)景點(diǎn)和進(jìn)出口，則最小線路安裝是什么？n顯然，第一個(gè)問題屬于最小樹生成問題，采用避圈法。n任選點(diǎn)S開始，離點(diǎn)S最近未連通是點(diǎn)，連通n離點(diǎn)或者點(diǎn)A最近未連通是點(diǎn)

3、B（和點(diǎn)相連通），連通Bn離點(diǎn)，或點(diǎn)B最近未連通是點(diǎn)C（和點(diǎn)連通），連通n離點(diǎn)S，B或者點(diǎn)C最近未連通是（和點(diǎn)B連通），連通BE案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n離點(diǎn)，A，B，C或者點(diǎn)E最近未連通是點(diǎn)D（和點(diǎn)E連通），連通EDn未連通的只有點(diǎn)（和點(diǎn)最近連通），連通DT。如圖案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)n 在inQSB軟件的“Network Modeling”模塊中，最小樹的生成就采用上面的避圈法。對(duì)于上述問題，在此模塊中新建一個(gè)最小樹的生成文件。如圖所示案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“OK”后可以輸入數(shù)據(jù)

4、。點(diǎn)擊“Solve and Analyze” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃現(xiàn)在，在入口S處有一個(gè)游覽車，一游客有急事需要到出口T，問游覽車如何行使可以使游客盡快到達(dá)出口？n根據(jù)題意知道這是一個(gè)網(wǎng)絡(luò)最短路問題題。下面介紹采用迪克斯托標(biāo)號(hào)法進(jìn)行求解。基本思路是逐點(diǎn)求解。例如如果是從到的最短路徑，那么從到這條線路的任何一點(diǎn)都應(yīng)該是最短的，不然就還存在其他最短路。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n具體解題步驟：首先從始點(diǎn)開始，令P(S)=為永久標(biāo)號(hào)，其余各點(diǎn)賦予標(biāo)號(hào)T(i)（，）n第一次迭代：計(jì)算與接近的各點(diǎn)的臨時(shí)標(biāo)號(hào)nT(A)=minT(A),P(S)+W(SA)=min,

5、2=2nT(B)=minT(B),P(S)+W(SB)=min,5=5nT(C)=minT(C),P(S)+W(SC)=min,4=4案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n在以上T標(biāo)號(hào)中T(A)=2為最小，故將A的P標(biāo)號(hào)改為2即P(A)=2;n第二次迭代：計(jì)算與A接近的各個(gè)點(diǎn)的臨時(shí)標(biāo)號(hào)nT(D)=minT(D),P(A)+W(AD)=min,9=9nT(B)=minT(B),P(A)+W(AB)=min5,4=4案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n在以上T標(biāo)號(hào)中，T(B)=4為最小，故將B的永久標(biāo)號(hào)改為P(B)=4 n第三次迭代：計(jì)算與B接近的各個(gè)點(diǎn)的臨時(shí)標(biāo)號(hào)nT(D)=minT(D

6、),P(B)+W(BD)=min9,8=8nT(E)=minT(E),P(B)+W(BE)=min,7=7nT(C)=minT(C),P(S)+W(BC)=min4,5=4案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n在以上T標(biāo)號(hào)中，T(C)=4為最小，故P(C)=4；n第四次迭代：計(jì)算與C想接近的E的臨時(shí)標(biāo)號(hào)nT(E)=minT(E),P(C)+W(CE)=min7,8=7n所以E的永久標(biāo)號(hào)為P(E)=7；案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n第五次迭代：計(jì)算與E接近的各點(diǎn)的臨時(shí)標(biāo)號(hào)nT(D)=minT(D),P(E)+W(ED)=min8,8=8nT(T)=minT(T),P(E)+W(E

7、T)=min,14=14n故以上T標(biāo)號(hào)中T(D)=8為最小，故P(D)=8案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃n第六次迭代：計(jì)算出口點(diǎn)T的標(biāo)號(hào)nT(T)= minT(T),P(D)+W(DT)=min14,13=13n根據(jù)以上步驟，我們便可以知道最短路徑為：nSABEDT 或者nSABDT案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)n 在inQSB軟件的“Net Problem Specification”模塊中，新建一個(gè)最短路模型：案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“OK”后可以輸入數(shù)據(jù)。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)

8、劃點(diǎn)擊“Solve and Analyze” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃以上過程是一個(gè)迭代過程，也可以用程序?qū)崿F(xiàn)。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃現(xiàn)在要在風(fēng)景區(qū)中的某一處修建一所醫(yī)務(wù)中心，問應(yīng)建在何處，能使各個(gè)景點(diǎn)都離他最近？n第三個(gè)問題屬于一個(gè)中心布點(diǎn)問題。一般思路是要求距離網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)距離盡可能小。分別求個(gè)點(diǎn)的最短路： 案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve and Analyze” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve” 求解。案例一：旅游線路

9、規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve and Analyze” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve and Analyze” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃D=(dij)dij=maxSABCDETS 0244871313A2023651111B42014399C4310541010D86450158E75341067(min)T131191056013案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃現(xiàn)在要在風(fēng)景區(qū)中的某一處

10、修建一所會(huì)議中心，已知各個(gè)景點(diǎn)的員工分別是40,25,45,30,20,35,50，那么會(huì)議中心應(yīng)建在何處，能使各個(gè)景點(diǎn)的員工走的總路程最短？n該問題屬于求解網(wǎng)絡(luò)的重心問題。設(shè)qi為vi的權(quán)重（i=1 , 2,-n）令h(vj)= （j=1 , 2, -n）n若minh（vj）=h(vr)，則稱點(diǎn)vr為網(wǎng)絡(luò)的重心。ni 1qidij案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃qidijSABCDETS080160160320280520A5005075150125275B18090045180135405C12090300150120300D16012080100020100E2451751051

11、40350210T6505504505002503000H(Vj)14051105875102010859801810案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃利用“Microsoft Eecel” 計(jì)算?？梢姇?huì)議中心建在B點(diǎn)，所有員工走的的總距離最短。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃為了保護(hù)園區(qū)生態(tài)環(huán)境，規(guī)定每條線路上觀光旅游車的數(shù)量是一定的，見下圖，其中每條弧上的數(shù)字為容許通行車輛的數(shù)量。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)n 在inQSB軟件的“Net Problem Specification”模塊中，新建一個(gè)最大流模型：這是一個(gè)最大流的問題。案例一：旅游線路

12、規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Solve and Analyze” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“OK”后可以輸入數(shù)據(jù)。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃點(diǎn)擊“Graphic Solution” 求解。案例一：旅游線路規(guī)劃案例一：旅游線路規(guī)劃容許通行量與計(jì)算結(jié)果對(duì)比。案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)一：問題提出n某齒輪廠1996年生產(chǎn)齒輪57.6萬只，完成產(chǎn)值507.9萬元，上繳利潤67.4萬元，在編制1997年生產(chǎn)作業(yè)計(jì)劃時(shí)，按傳統(tǒng)的做法考慮齒輪的用戶：汽車制造廠、拖拉機(jī)廠市場(chǎng)銷量增加比例確定齒輪生產(chǎn)計(jì)劃，目標(biāo)擬定比1996

13、年產(chǎn)量增加38.8%即生產(chǎn)齒輪70萬只，產(chǎn)值增加38%，利潤增加18.7%（80萬元）。對(duì)此企業(yè)內(nèi)部有兩種不同的認(rèn)識(shí)，一種認(rèn)為人員、設(shè)備、生產(chǎn)能力沒有增加，遞增速度太快，完成可能性不大；另一種認(rèn)為可以完成，但關(guān)鍵產(chǎn)品與工序能力潛力多大，缺乏科學(xué)分析依據(jù)。n針對(duì)以上情況，企業(yè)經(jīng)濟(jì)分析人員提出運(yùn)用運(yùn)籌學(xué)相關(guān)理論來研究和進(jìn)行討論。案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)一：相關(guān)數(shù)據(jù) n該廠生產(chǎn)五種機(jī)型100多個(gè)品種的齒輪，為簡化計(jì)算，歸為五類生產(chǎn)。分別是：n（1）195柴油機(jī)齒輪n（2）泰山12型拖拉機(jī)齒輪n（3）6160型齒輪n（4）6102QA型齒輪n（5）CCQ95型齒輪案例二：齒輪生產(chǎn)案例二：齒輪生

14、產(chǎn)一：相關(guān)數(shù)據(jù) n齒輪生產(chǎn)過程當(dāng)中，原材料供應(yīng)、勞動(dòng)人數(shù)等約束條件可以充分滿足，主要的約束因素是需要經(jīng)過的10道加工工序。分別是： 序號(hào)12345678910工序鍛造車床鉆床拉床滾齒剃齒花鍵銑磨調(diào)質(zhì)共滲案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)1996年關(guān)鍵工序工時(shí) 鍛造車工 鉆床拉床滾齒剃齒花鍵銑磨床調(diào)質(zhì)共滲總計(jì)9825223893126796893275922156318932379611786426796案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)機(jī)型利潤產(chǎn)值總工時(shí)鍛造車鉆床拉床滾齒剃齒花鍵磨調(diào)質(zhì)共滲1953.5333.64.980.461.660.120.080.720.18000.2920泰山12109.

15、62250.928.914.19.490.3930.343.6100.3590.98302.19616050.6139.319.941.926.940.2730.2823.742000.7390.35906102QA8669.30.812.730.12301.4840.2300.5230.320CCQ9513.4159.6516.850.516.180.2120.1331.620.350.850.7750.150案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)依據(jù)1996年的基本數(shù)據(jù)，編制1997年計(jì)劃n制定不考慮國家指令性計(jì)劃利用現(xiàn)有生產(chǎn)條件取得最大經(jīng)濟(jì)效益的方案。n后來國家指令性計(jì)劃出臺(tái)，那么考慮國家計(jì)劃

16、指令性要求和產(chǎn)品配套要求，利用現(xiàn)有生產(chǎn)能力重新編制了生產(chǎn)方案。 案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)分析：該問題可以用線性規(guī)劃進(jìn)行求解。n設(shè)：nX1：表示195柴油機(jī)齒輪產(chǎn)量nX2：表示泰山12型拖拉機(jī)齒輪產(chǎn)量nX3：表示6160型齒輪產(chǎn)量nX4：表示6102QA型齒輪產(chǎn)量nX5：表示CCQ95型齒輪產(chǎn)量案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)nY1表示鍛造工序生產(chǎn)能力（小時(shí)）nY2表示車工工序生產(chǎn)能力nY3表示鉆床工序生產(chǎn)能力nY4表示拉床工序生產(chǎn)能力nY5表示滾齒工序生產(chǎn)能力nY6表示剃齒工序生產(chǎn)能力nY7表示花鍵銑削生產(chǎn)能力nY8表示磨床工序生產(chǎn)能力nY9表示調(diào)制工序生產(chǎn)能力nY10表示共滲工序生產(chǎn)

17、能力案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n設(shè)該廠最大利潤S為目標(biāo)函數(shù)，建立線性規(guī)劃模型。nMax S =3.53X1+109.62X2+50.6X3+8X4+13.4X5案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)ns.tn 0.46X1+4.1X2+1.92X3+0.81X4+0.51X598252n 1.66X1+9.49X2+6.94X3+2.73X4+6.18X5238931n 0.12X1+0.393X2+0.273X3+0.123X4+0.212X526796n 0.08X1+0.34X2+0.282X3+0+0.133X58932n 0.72X1+3.61X2+3.742X3+1.484X4+1

18、.62X575922n 0.18X1+0+0+0.23X4+0.35X515631n 0+0.359X2+0+0+0.85X58932n 0+0.983X2+0.739X3+0.523X4+0.775X537961n 0.292X1+0+0.359X3+0.32X4+0.15X517864n 0+2.19X2+0+0+026796軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)n 在inQSB軟件的“Linear and Integer Programming”模塊中，建立線性規(guī)劃模型：案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪

19、生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)nX1=0： 195柴油機(jī)齒輪產(chǎn)量nX2=12240 ： 泰山12型拖拉機(jī)齒輪產(chǎn)量nX3=8485 ： 6160型齒輪產(chǎn)量nX4=0 ： 6102QA型齒輪產(chǎn)量nX5=0 ： CCQ95型齒輪產(chǎn)量nS=1770617元： 最大利潤 案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n什么原因?qū)е逻@個(gè)結(jié)果？n企業(yè)內(nèi)部人員認(rèn)為肯定某一些工序生產(chǎn)能力的制約導(dǎo)致這個(gè)結(jié)果。n但是在十個(gè)工序里面哪一個(gè)工序或者哪一些工序是關(guān)鍵制約因素呢？ 案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n什么原因約束了生產(chǎn)能力 案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n當(dāng)影子價(jià)格為0時(shí)，說明該工序加工能力的變化對(duì)

20、利潤沒有影響，也就是該工序加工能力有富余。n當(dāng)影子價(jià)格大于0時(shí)，說明該工序加工能力的變化能增加利潤，也就是該工序加工能力不足。n本例中與影子價(jià)格相等的數(shù)值就是該工序每增加一個(gè)單位（工時(shí)）帶來的經(jīng)濟(jì)效益（利潤）。案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)nY5（滾齒）Y10（共滲）兩道工序的影子價(jià)格均大于0。說明這兩到工序是關(guān)鍵工序，它們加工能力的變化會(huì)直接導(dǎo)致利潤的變化。n其直接經(jīng)濟(jì)效益是：滾齒工序每增加一個(gè)工時(shí)，能增加13.552元的利潤，共滲工序每增加一個(gè)工時(shí)，能增加27.76元的利潤。n為什么結(jié)論和上圖顯示的不一樣呢？案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n通過以上計(jì)算和分析，如果要增加利潤就必須增加滾

21、齒、共滲兩道工序的生產(chǎn)能力，針對(duì)這兩種情況，企業(yè)做出如下調(diào)整：n把新買的滾齒機(jī)迅速安裝調(diào)試，爭取早日投產(chǎn)；n增加上述工序的部分班次；n購進(jìn)一臺(tái)新的共滲爐，盡快交付使用案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n齒輪生產(chǎn)只能是整數(shù)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n滾齒C5、共滲C10各增加1000生產(chǎn)能力案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)nX1=0： 195柴油機(jī)齒輪產(chǎn)量nX2=12692（12240） ： 泰山12型拖拉機(jī)齒輪產(chǎn)量nX3=8312（8485） ： 6160型齒輪產(chǎn)量nX4=0 ： 6102QA型齒輪產(chǎn)量nX5=0 ： CCQ9

22、5型齒輪產(chǎn)量nS=1811884（1770559）萬元： 最大利潤 n1811884-1770559 =4132513522+27764案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n考慮到國家計(jì)劃指令的出臺(tái)，國家指令量是必須完成的，即195柴油機(jī)齒輪安排6.4萬臺(tái)。那么這個(gè)時(shí)候的關(guān)鍵工序又是怎么樣的呢？采用同樣的方法是建立模型進(jìn)行分析。案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n同樣重新建立模型后采用其對(duì)偶解得到要滿足國家計(jì)劃指令時(shí)，拉床、車床和調(diào)質(zhì)是關(guān)鍵工序。企業(yè)采用以下措施：案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn) 企業(yè)采用以下措施：n將一臺(tái)舊拉床（多年不用）修復(fù)投入使用，將拉床兩班生產(chǎn)改為三班生產(chǎn)；n調(diào)質(zhì)工序再增加一臺(tái)中頻電爐以減輕壓力，同時(shí)擴(kuò)大作業(yè)面積；n把新進(jìn)廠的車床及時(shí)安裝使用。案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n采取了以上措施，使得企業(yè)生產(chǎn)工序生產(chǎn)能力基本平衡。調(diào)整后的工序能力見表。n與生產(chǎn)線平衡方法有什么不同？案例二：齒輪生產(chǎn)案例二：齒輪生產(chǎn)n調(diào)整后的工序能力見表 工序名稱原有能力新增能力車工