《規(guī)劃計算題整理[共23頁]》由會員分享，可在線閱讀，更多相關(guān)《規(guī)劃計算題整理[共23頁]（22頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第二章 設(shè)施選址10.一家銀行準備在某縣的農(nóng)村地區(qū)投放一批ATM自動取款機，以方便農(nóng)村的用戶取款。該農(nóng)村地區(qū)的村落座落情況和相對距離如圖2.13所示。為了能確保任一村的人都可以在20分鐘之內(nèi)到達自動取款機取款，銀行需要多少臺自動取款機？它們的位置又在哪里?圖2.13 村落座落情況和相對距離要點： 1. 明確N，M，A(j)，B(i)含義；2. A(j)分析正確后，B(i)可參照A(j)直接寫出，無需再看網(wǎng)絡(luò)圖；3. 熟悉最少點覆蓋啟發(fā)式算法的步驟，考慮是否有容量約束。 解：【集合覆蓋模型】區(qū)域中需求點集合N=1,2,3,4,5,6,7；ATM取款機設(shè)施候選點集合M=1,2,3,4,5,6,7；

2、由網(wǎng)絡(luò)圖確定候選設(shè)施點j可覆蓋的需求點集合A(j)和可覆蓋需求點i的設(shè)施節(jié)點的集合B(i)，見表2.10.1。2.10.1 候選點服務(wù)范圍村落號A(j)B(i)11,2,31,2,321,2,4,51,2,4,531,3,41,3,442,3,4,6,72,3,4,6,752,5,62,5,664,5,64,5,674,74,7因為A(4)=2,3,4,6,7，| A(4)|=5為最大，故首先j'=4。因無容量約束，指派2,3,4,6,7歸村落4服務(wù)。此時N=1,5，M=1,2,3,5,6,7；則更新候選點服務(wù)范圍，見表2.10.2。2.10.2 更新后的候選點服務(wù)范圍村落號A(j)B

3、(i)111,2,321,5314552,5,6657因為A(2)=1,5=N，恰好滿足條件。則j'=2。綜上所述，銀行需要2臺自動取款機，分別至于村落號為2和4的位置，2號為1,5村落服務(wù)，4號為 2,3,4,6,7村落服務(wù)。11. 個臨時幫助服務(wù)中心計劃在一個大城市的郊外開設(shè)一個新的辦公室。在經(jīng)過一定的精簡之后，該公司有5個大的合作伙伴。在一個以km為單位的笛卡爾坐標系中，它們的坐標分別為：(4，4)，(4，11)，(7 ，2)，(11，11)， (14，7)。它們的服務(wù)需求量的權(quán)重分別為：wl=3，w2=2，w3=2，w4=4，w5=1。對于該服務(wù)中心來說，主要的日常費用是他們員

4、工完成任務(wù)過程中的運輸費用。因此，用城市距離進行考慮，要求新的辦公室到各個合作伙伴之間運輸?shù)倪\輸費用最小。1）請確定一個新辦公室的地址，用笛卡爾坐標來表達相應(yīng)結(jié)果。2）如果由于該地區(qū)的人口稀少，城市還沒有達到一定的規(guī)模，可以用歐幾米德距離進行計算，新辦公室又得在哪里投建?請比較兩次結(jié)果，分析它們之間的關(guān)系。 要點：1. 補充交叉中值模型知識點 關(guān)鍵句：將n點需求的選址問題轉(zhuǎn)化為i=1nwi點需求的選址問題。 2.笛卡爾距離即直角距離，歐基米德距離即直線距離； 3.重心法：初始化+迭代公式+Excel/C編程/matlab編程迭代+迭代終止條件解：（1）設(shè)新辦公室的地址的坐標為(x,y),給題目

5、已知的5個點編號15。由于笛卡爾距離di=|x-xi|+|y-yi|。則目標函數(shù)為時總運輸距離H最短。H=i=15widi=i=15wix-xi +i=15wi|y-yi|xiwiwi yiwiwi 43343342511257272271141111411141127112wi=12為偶數(shù)，即x,y均在第六個、第七個點之間?？傻脁=7，y7,11。H=81。（2）設(shè)初始點為（x0， y0）有題意得，阿基米德距離為di(0)=(x0-xi)2+(y0-yi)2, 目標函數(shù)H(運輸總費用)=i=15widi,利用不動點算法，取一個初始的迭代點（x0(0),y0(0)）=(8,7),此時H0=62

6、.51令x0(1)=i=15wixidii=15xidi, y0(1)=i=15wiyidii=15yidi,di(1)=(x0(1)-xi)2+(y0(1)-yi)2H1=i=15widi(1)=62.14由EXCEL迭代得，結(jié)果如圖費用結(jié)果保留四位小數(shù)得最優(yōu)解為x=7.6257,y=7.6047,此時費用最小為H=62.1020（3）比較兩次結(jié)果可知歐基米德中的費用小于笛卡爾距離，因直線距離是直角距離，因此用歐基米德距離更為精確。直角距離比較適合于城區(qū)范圍內(nèi)的選址，歐基米德距離比較適合于遠距離的選址。12.一臺機器工具小制造商要遷址，并確定了兩個地區(qū)以供選擇。A地的年固定成本為800000

7、元，可變成本為14000元/臺；B地的年固定成本為920000元，可變成本為13000元/臺。產(chǎn)品最后售價為17000元/臺。（1） 當產(chǎn)量為多少時，兩地的總成本相等？（2） 當產(chǎn)量處于什么范圍時，A地優(yōu)于B地？當產(chǎn)量處于什么范圍時，B地優(yōu)于A地？解：答：設(shè)x為之制造商的年產(chǎn)量 A地，總成本C(A)=800000+14000x B地，總成本C(B)=920000+13000x1)若兩地成本相等，則C(A)=C(B)解得：x=120 2）若A地優(yōu)于B地，則C(A)<C(B),因此得0<x<120 同理，當x>120時，B地優(yōu)于A地。13利用表2.8所示的因素評分，以最大綜

8、合得分為基礎(chǔ)，建模分析應(yīng)選擇地點A、B、C中的哪一個? 表2.8 因素評分表解：權(quán)重矩陣設(shè)為W，則WT=0,15 0.20 0.18 0.27 0.10 0.10三個位置的因素評分作為3行構(gòu)成因素矩陣S。S=80 72 88 94 98 9670 76 90 86 90 8560 92 90 80 82 75可得綜合加權(quán)矩陣E=S*W=87.0282.6280.90?？芍狤(A)> E(B)> E(C)。即選擇A點。14.一個玩具制造商在全國的五個地區(qū)生產(chǎn)玩具，原材料將從一個新的中心倉庫運出，而此倉庫的地點還有待確定。運至各地的原材料數(shù)量相同，已建立一個坐標城，各地的坐標位置如表2

9、.9所示。請確定中心倉庫的坐標位置。表2.9 各地的坐標位置解：設(shè)倉庫的坐標為（x0，y0)，五個生產(chǎn)地為(xi,yi),倉庫到各生產(chǎn)地的距離為di,因運至各地的原材料數(shù)量相同，故可設(shè)wi=1(i=1,2,5）;初始解：，即x0(0)=5，y0(0)=4。直線距離為di(0)=(x0-xi)2+(y0-yi)2目標函數(shù)運輸總費用H=i=15widi ，其中 wi=1(i=1,2,5）H(0)=j=15dj=13.6094根據(jù)下列進行迭代：x0(1)=i=15xidii=151di， y0(1)=i=15yidii=151di，di(1)=(x0(1)-xi)2+(y0(1)-yi)2直到運費無

10、法減小。用MATLAB 進行編碼：運行結(jié)果得，迭代78次得到最優(yōu)解。其中選址坐標為（5.6235,4.9918），最小運費為H=13.4550?；蛴蒃XCEL迭代得，結(jié)果如圖費用結(jié)果保留三位小數(shù)得最優(yōu)解為X=5.5767，y=4.010,H=13.45615.某物流公司擬建一倉庫負責向四個工廠進行物料供應(yīng)配送，各工廠的具體位置與年物料配送量見表2.10，設(shè)擬建物流公司倉庫對各工廠的單位運輸成本相等。利用重心法計算確定物流公司的倉庫坐標位置為多少。 表2.10 各工廠的具體位置與年物料配送量解：設(shè)倉庫的坐標為（x0，y0)，4個工廠的坐標為(xi,yi),倉庫到各生產(chǎn)地的距離為di=(x0-xi

11、)2+(y0-yi)2,目標函數(shù)運輸總費用H=i=15icidi=i=15widi，i為工廠年配送量，ci為單位運輸成本，因單位運輸成本相等，故令ci=1，于是有w1 =2000,w2=1200,w3 =1000,w4=2500初始解x0=1nxi=37.5, y0=1nyi=42.5di(0)=(x0-xi)2+(y0-yi)2, 此時H0=192249.4令x0(1)=i=15wixidii=15xidi, y0(1)=i=15wiyidii=15yidi,di(1)=(x0(1)-xi)2+(y0(1)-yi)2H1=i=15widi(1)=190400.4由EXCEL迭代得，結(jié)果如圖結(jié)

12、果保留整數(shù)得最優(yōu)解為（42.22076，33.82437）,H=188709或用MATLAB進行編碼（文件見附件）：運行結(jié)果得，迭代59次得到最優(yōu)解。其中選址坐標為（42.2865, 33.6732），最小運費為H= 188707.914。16. 籌建一農(nóng)副產(chǎn)品流通加工廠，可供選擇的候選廠址有D、E、F三處，因地址不同各廠加工成本亦有區(qū)別，各廠址每年費用如表2.7所示。此外，為決定廠址還考慮了一些重要的非成本因素，如當?shù)馗偁幠芰Α夂蜃兓椭車h(huán)境是否適合農(nóng)副產(chǎn)品流通加工等。對于競爭能力而言，F(xiàn)地最強，D、E兩地相平；就氣候來說，D比E好，F(xiàn)地最好；至于環(huán)境，E地最優(yōu)，其次為F地、D地。如果各

13、主觀因素的重要性指數(shù)a、b、c依次為0.6、0.3和0.1，要求用因次分析法評定最佳廠址在何處。表2.11 各候選廠址每年加工成本費用要點：P中值法分5個步驟進行。解: （1）計算客觀量度值OMi ，OMi=Ci1Ci-1 OMD=523*(1523+1525+1551)-1=0.3395同理可得：OME=0.3382,OMF=0.3223。（2）計算主觀評比值Sik（有3個不同的主觀因素） 競爭能力（F>D=E） 注：D=E，比較記為0.5兩兩相比廠址FED比重SiaD00.50.50.167E00.50.50.167F1120.666 氣候（F>D>E）兩兩相比廠址FED

14、比重SiaD0110.33E000F1120.67 環(huán)境（E>F>D）兩兩相比廠址FED比重SiaD0000E1120.67F0110.33（3）計算主觀量度值SMi， SMi=k=13IkSik，其中Ik為各主觀因素的重要性指數(shù)。因素kDEF重要性指數(shù)IkSia0.1670.1670.6660.6Sib0.3300.670.3Sic00.670.330.1計算可得SMD=0.167*0.6+0.33*0.3+0*0.1=0.1992SME=0.167*0.6+0*0.3+0.67*0.1=0.1672SMF=0.666*0.6+0.67*0.3+0.33*0.1=0.6336（4

15、）計算位置量度值LMi，LMi=X*SMi+（1-X）*OMi由于題中沒有給出主觀因素與客觀因素的相互比重，假設(shè)兩者相等即同種重要，即主客觀比重值X=0.5。LMD=0.5*0.3395+0.5*0.1992=0.26935LME=0.5*0.3382+0.5*0.1672=0.2527LMF=0.5*0.3223+0.5*0.6336=0.47795（5）決策根據(jù)各位置量度值LMi的大小，F(xiàn)廠址所得位置量度值在3個候選地址中最高，故選F為建廠廠址。17.在某區(qū)域需規(guī)劃建設(shè)若干個農(nóng)貿(mào)市場為將來該區(qū)9個主要居民點提供服務(wù)，除第6居民點外，其他各點均有建設(shè)市場的條件，如圖26所示。已知市場的最大服

16、務(wù)直徑為3km，為保護該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場。問應(yīng)如何規(guī)劃？3圖26 小區(qū)居民點位置圖解：N1,2,3,4,5,6,7,8,9，M1,2,3,4,5,7,8,9，由圖26兩點間的最短距離，根據(jù)最大服務(wù)半徑為3km的約束及第6居民點不適合建市場的要求，可確定集合A(j)和B(i)。如表23所示。表23 候選點服務(wù)范圍因為A(4)=1,3,4,5,6,7，A(3)=1,2,3,4,5,6,|A(4)|= |A(3)|=6為最大,隨機選取j4。由于無容量約束故依次指派5,7,1,6,3,4點歸節(jié)點4服務(wù)。此時，N2,8,9,M1,2,3,5,7,8,9,更新集合A(j)和集合B(i

17、)后如表24所示。表24 候選點服務(wù)范圍因為A(8)8,9，|A(8)|A(9)|=2為最大，故選取j8或j9，并且8，9兩點歸節(jié)點8或9服務(wù)。同理，再迭代一次，得j2，居民點2歸節(jié)點2服務(wù)。 因此，計算結(jié)果為（4,8,2）或（4,9,2）。若選擇j3，故依次指派1,2,3,4,5,6點歸節(jié)點3服務(wù)。此時，N7,8,9,M1,2,4,5,7,8,9,更新集合A(j)和集合B(i)后如表25所示。表25 候選點服務(wù)范圍由于|A(8)|3最大，選擇j8。因此計算結(jié)果為（3,8）。第三章 設(shè)施規(guī)劃11. 某生產(chǎn)線共有8項作業(yè)，其工作周期為8分鐘。已知各項作業(yè)的裝配順序和時間如表3.30所示。請根據(jù)周

18、期時間和作業(yè)順序限制，確定最少工作站數(shù)和各項作業(yè)的安排，并算出此安排下生產(chǎn)線的效率。表3.30 周期時間和作業(yè)順序表解：由題意得網(wǎng)絡(luò)活動圖（Job on nodes）：ABCDEFGH由題意各作業(yè)所需時間之和=5+3+4+3+6+1+4+2=28最小工作數(shù)=28/8=3.5,因此需要4個工作臺根據(jù)作業(yè)的相關(guān)情況進行安排，結(jié)果如下表工作站序號作業(yè)單元工作時間空閑時間1H,G,F 712E 6 23D，C 7 14B，A 8 0生產(chǎn)線效率=完成作業(yè)所需時間總和/(實際工作站總數(shù)*時間周期)=284×8=0.875。12.某流水線有17項作業(yè)需要平衡，其中最長的作業(yè)為2.4分鐘，所有作業(yè)的

19、總時間為18分鐘。該流水線每天工作450分鐘。試求：（1）最大和最小的周期時間各是多少？（2）該流水線理論上可能達到的每日產(chǎn)能是多少？（3）按最大產(chǎn)能來算，最少需要幾個工作站？（4）若每天產(chǎn)能為125分鐘，則周期時間應(yīng)為多長？（5）若周期時間分別是9分鐘和15分鐘，則產(chǎn)能分別是多少？ 解：（1）當17項作業(yè)只能串行依次進行時，可得最大周期為18min。當17項作業(yè)均并行進行時，可得最小周期為2.4min。（2）產(chǎn)能為單位時間生產(chǎn)的產(chǎn)品數(shù)量。以最大周期計算，得最小產(chǎn)能為1/18min=0.056/min；以最小周期計算，得最大產(chǎn)能為1/2.4min=0.417/min；綜上所述，每日可能產(chǎn)能為2

20、5,187.5。（3）依題意有需要18/2.4=7.58，所以最少需要8個工作站。（4）周期時間為450/125=3.6min。（5）當周期時間為9min時，產(chǎn)能為450/9=50/天；當周期時間為15min，產(chǎn)能為450/15=30/天。13. 某學院注冊有四道手續(xù)：領(lǐng)取表格、咨詢、領(lǐng)取班級卡和確認交費，分別安排在A、B、C、D四個連續(xù)相鄰的同樣大小的房間，因為同時有新老學生，如果450名新學生領(lǐng)表后去咨詢，550名老學生領(lǐng)表后直接去領(lǐng)班級卡，而畢業(yè)班學生已經(jīng)注冊過，領(lǐng)表后直接去繳費，詳細學生流向如表3.31所示。試問已有布置是否可以改進，若能，該如何改進？表3.31 學生流向表要點：1.解

21、題思路：單向物流從至表 雙向物流從至表 作業(yè)對按雙向物流從至表中強度值排序，劃分物流等級確定物流路線比例 參考相關(guān)圖得接近程度排序表 按接近程度得作業(yè)單位位置相關(guān)圖 按接近程度排序得作業(yè)單位面積相關(guān)圖 2.參考相關(guān)圖：物流強度等級A E I O U X物流路線比例10% 20% 30% 40% 0 0承擔的物流量比例40% 30% 20% 10% 0 0接近程度4 3 2 1 0 0 3.路線比例設(shè)計=線路條數(shù)/總線路條數(shù)解：由學生流向表得到雙向物流表如下：雙向物流表領(lǐng)表（A）咨詢(B)領(lǐng)班級卡(C)繳費(D)領(lǐng)表（A）700（2）550（3）50（5）咨詢(B)200（4）領(lǐng)班級卡(C)75

22、0（1）繳費(D)根據(jù)學生流量劃分物流等級確定物流路線比例如下：序號作業(yè)單位對強度值路線比例設(shè)計路線條數(shù)物流強度比例強度等級1C-D75020%133.3%E2A-B70020%131.1%E3A-C55020%124.4%E4B-C20040%211.1%O5A-D50O合計2250由以上關(guān)系圖得接近程度排序表領(lǐng)表A咨詢B領(lǐng)班級卡C繳費D領(lǐng)表A3/E3/E1/O咨詢B3/E1/O0/U領(lǐng)班級卡C3/E1/O3/E繳費D1/O0/U3/E合計7474排序2413作業(yè)單位位置相關(guān)圖和作業(yè)單位面積相關(guān)圖領(lǐng) 表繳 費領(lǐng)班級卡咨 詢領(lǐng)班級卡繳 費領(lǐng) 表咨 詢現(xiàn)四道手續(xù)：領(lǐng)取表格、咨詢、領(lǐng)取班級卡和確認

23、交費，分別安排在A、B、C、D四個連續(xù)相鄰的同樣大小的房間，即位置為下圖關(guān)系領(lǐng)班級卡繳 費領(lǐng)表咨詢該布置可得到改進，改進方案為領(lǐng)班級卡繳 費領(lǐng) 表咨 詢14. 根據(jù)作業(yè)相關(guān)圖，繪制作業(yè)單位位置相關(guān)圖。 圖3.28 習題14作業(yè)相關(guān)圖解：由該作業(yè)相關(guān)圖可得接近程度排序表如下：ABCDEA4/A2/I0/U0/UB4/A2/I3/E3/EC2/I2/I0/U0/UD0/U3/E0/U1/OE0/U3/E0/U1/O合計612444排序21534可得作業(yè)單位位置相關(guān)圖如下：BADEC15. 某工廠有ABCDE五個車間，布置圖如下，其中為各車間距心。該廠生產(chǎn)四種產(chǎn)品，各產(chǎn)品的工藝路線和每月產(chǎn)量如表3.

24、4所示，而且每種產(chǎn)品的生產(chǎn)批量為50件。（1）試以直角距離計算兩兩車間的距離從至表；（2）計算物流搬運量從至表F；（3）計算搬運工作量，并以之作為物流強度表示從至表。假設(shè)每批次搬運移動1米的成本是2元/米·批，試將上述物流強度從至表轉(zhuǎn)化為物流成本從至表。解：（1）車間直角距離從至表ABCDEA27547539B27274866C54273969D75483948E39666948(2) 物流搬運量從至表ABCDEA6006509000B60000C850400D1750E(3)物流強度從至表（物流強度=距離*物流量）ABCDEA1620035100675000B1620000C331

25、5027600D84000E因為每批次搬運移動1米的成本是2元/米·批，所以每件搬運成本為2/50=0.04元/米*件，得到物流成本從至表如圖。物流成本從至表ABCDEA648140427000B64800C13261104D3360E16. 已知某工廠的各作業(yè)單位原始數(shù)據(jù)如表3.23、表3.24所示。試用作業(yè)單位關(guān)系圖法布置平面圖。表3.23 各作業(yè)單位及面積表3.24 作業(yè)單位關(guān)系要點：1.選出的第一個作業(yè)至少有三面被其它作業(yè)包圍； 2.不帶面積的平面圖與帶面積的平面圖沒有完全的對應(yīng)關(guān)系。 3.此題多解。解：第一階段，確定各作業(yè)單位的相對位置。畫出樣板，包括作業(yè)單位的名稱代碼及相關(guān)代碼。選出A級關(guān)系最多的樣板Y，將Y布置在平面圖中部，其它按AEIOU級關(guān)系從多到少的順序依次放到平面圖中，可得放置順序為YXZUWTV,在布置的過程中應(yīng)保持關(guān)系強度大的樣板盡量靠近放。第二階段，據(jù)各作業(yè)單位面積，以20 m2為一個面積單位得帶面積的平面圖如下：