《規(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}； A

2、TM取款機設(shè)施候選點集合M={1,2,3,4,5,6,7}； 由網(wǎng)絡(luò)圖確定候選設(shè)施點j可覆蓋的需求點集合A(j)和可覆蓋需求點i的設(shè)施節(jié)點的集合B(i)，見表2.10.1。 2.10.1 候選點服務(wù)范圍 村落號 A(j) B(i) 1 1,2,3 1,2,3 2 1,2,4,5 1,2,4,5 3 1,3,4 1,3,4 4 2,3,4,6,7 2,3,4,6,7 5 2,5,6 2,5,6 6 4,5,6 4,5,6 7 4,7 4,7 因為A(4)={2,3,4,6,7}，| A(4)|=5為最大，故首先j'=4。因無容量約束，

3、指派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(i) 1 1 1,2,3 2 1,5 3 1 4 5 5 2,5,6 6 5 7 因為A(2)={1,5}=N，恰好滿足條件。則j'=2。 綜上所述，銀行需要2臺自動取款機，分別至于村落號為2和4的位置，2號為1,5村落服務(wù)，4號為 2,3,4,6,7村落服務(wù)。 11. —個臨時幫助服務(wù)中心計劃在一個大城市的郊外開設(shè)一個新

4、的辦公室。在經(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ù)中心來說，主要的日常費用是他們員工完成任務(wù)過程中的運輸費用。因此，用城市距離進行考慮，要求新的辦公室到各個合作伙伴之間運輸?shù)倪\輸費用最小。1）請確定一個新辦公室的地址，用笛卡爾坐標來表達相應(yīng)結(jié)果。2）如果由于該地區(qū)的人口稀少，城市還沒有達到一定的規(guī)模，可以用歐幾米德距離進行計算，新辦公室又得在哪里投建?請比較兩次結(jié)果，分析它

5、們之間的關(guān)系。 要點：1. 補充交叉中值模型知識點 關(guān)鍵句：將n點需求的選址問題轉(zhuǎn)化為i=1nwi點需求的選址問題。 2.笛卡爾距離即直角距離，歐基米德距離即直線距離； 3.重心法：初始化+迭代公式+Excel/C編程/matlab編程迭代+迭代終止條件 解：（1）設(shè)新辦公室的地址的坐標為(x,y),給題目已知的5個點編號1~5。 由于笛卡爾距離di=|x-xi|+|y-yi|。 則目標函數(shù)為時總運輸距離H最短。 H=i=15widi=i=15wix-xi +i=15wi|y-yi| xi wi wi yi wi wi

6、 4 3 3 4 3 3 4 2 5 11 2 5 7 2 7 2 2 7 11 4 11 11 4 11 14 1 12 7 1 12 wi=12為偶數(shù)，即x,y均在第六個、第七個點之間。 可得x=7，y∈7,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.51 令x0(1)=i=15wixidii=1

7、5xidi, y0(1)=i=15wiyidii=15yidi,di(1)=(x0(1)-xi)2+(y0(1)-yi)2 H1=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元，可變成本為140

8、00元/臺；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+13000x 1)若兩地成本相等，則C(A)=C(B) 解得：x=120 2）若A地優(yōu)于B地，則C(A)<C(B),因此得0<x<120 同理，當x>120時，B地優(yōu)于A地。

9、13．利用表2.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。 可知E(A)> E(B)> E(C)。即選擇A點。 14.一個玩具制造商在全國的五個地區(qū)生產(chǎn)玩具，原材料將從一個新的中心倉庫運出，而此倉庫的

10、地點還有待確定。運至各地的原材料數(shù)量相同，已建立一個坐標城，各地的坐標位置如表2.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

11、=151di， y0(1)=i=15yidii=151di，di(1)=(x0(1)-xi)2+(y0(1)-yi)2 直到運費無法減小。 用MATLAB 進行編碼： 運行結(jié)果得，迭代78次得到最優(yōu)解。 其中選址坐標為（5.6235,4.9918），最小運費為H=13.4550。 或由EXCEL迭代得，結(jié)果如圖 費用結(jié)果保留三位小數(shù)得最優(yōu)解為X=5.5767，y=4.010,H=13.456 15.某物流公司擬建一倉庫負責向四個工廠進行物料供應(yīng)配送，各工廠的具體位置與年物料配送量見表2.10，設(shè)擬建物流公司倉庫對各工廠的單位運輸成本相等。利用重心法計算確定物流公司的倉庫坐

12、標位置為多少。 表2.10 各工廠的具體位置與年物料配送量 解：設(shè)倉庫的坐標為（x0，y0)，4個工廠的坐標為(xi,yi),倉庫到各生產(chǎn)地的距離為di=(x0-xi)2+(y0-yi)2,目標函數(shù)運輸總費用H=i=15αicidi=i=15widi，αi為工廠年配送量，ci為單位運輸成本，因單位運輸成本相等，故令ci=1，于是有w1 =2000,w2=1200,w3 =1000,w4=2500 初始解x0=1nxi=37.5, y0=1nyi=42.5 di(0)=(x0-xi)2+(y0-yi)2, 此時H0=192249.4 令x0(1)=i=15wixidii=15

13、xidi, y0(1)=i=15wiyidii=15yidi,di(1)=(x0(1)-xi)2+(y0(1)-yi)2 H1=i=15widi(1)=190400.4 由EXCEL迭代得，結(jié)果如圖 結(jié)果保留整數(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所

14、示。此外，為決定廠址還考慮了一些重要的非成本因素，如當?shù)馗偁幠芰?、氣候變化和周圍環(huán)境是否適合農(nóng)副產(chǎn)品流通加工等。對于競爭能力而言，F(xiàn)地最強，D、E兩地相平；就氣候來說，D比E好，F(xiàn)地最好；至于環(huán)境，E地最優(yōu)，其次為F地、D地。如果各主觀因素的重要性指數(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=

15、0.3223。 （2）計算主觀評比值Sik（有3個不同的主觀因素） ① 競爭能力（F>D=E） 注：D=E，比較記為0.5 兩兩相比 廠址 F E D 比重 Sia D 0 0.5 0.5 0.167 E 0 0.5 0.5 0.167 F 1 1 2 0.666 ② 氣候（F>D>E） 兩兩相比 廠址 F E D 比重 Sia D 0 1 1 0.33 E 0 0 0 F 1 1 2 0.67 ③ 環(huán)境（E>F>D） 兩兩相比

16、 廠址 F E D 比重 Sia D 0 0 0 0 E 1 1 2 0.67 F 0 1 1 0.33 （3）計算主觀量度值SMi， SMi=k=13IkSik，其中Ik為各主觀因素的重要性指數(shù)。 因素k D E F 重要性指數(shù)Ik Sia 0.167 0.167 0.666 0.6 Sib 0.33 0 0.67 0.3 Sic 0 0.67 0.33 0.1 計算可得 SMD=0.167*0.6+0.33*0.3+0*0.1=0.1992 SME=0.167*0.6+0*0.

17、3+0.67*0.1=0.1672 SMF=0.666*0.6+0.67*0.3+0.33*0.1=0.6336 （4）計算位置量度值LMi，LMi=X*SMi+（1-X）*OMi 由于題中沒有給出主觀因素與客觀因素的相互比重，假設(shè)兩者相等即同種重要，即主客觀比重值X=0.5。 LMD=0.5*0.3395+0.5*0.1992=0.26935 LME=0.5*0.3382+0.5*0.1672=0.2527 LMF=0.5*0.3223+0.5*0.6336=0.47795 （5）決策 根據(jù)各位置量度值LMi的大小，F(xiàn)廠址所得位置量度值在3個候選地址中最高，故選F為建

18、廠廠址。 17.在某區(qū)域需規(guī)劃建設(shè)若干個農(nóng)貿(mào)市場為將來該區(qū)9個主要居民點提供服務(wù)，除第6居民點外，其他各點均有建設(shè)市場的條件，如圖2－6所示。已知市場的最大服務(wù)直徑為3km，為保護該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場。問應(yīng)如何規(guī)劃？ 3 圖2－6 小區(qū)居民點位置圖 解：N＝{1,2,3,4,5,6,7,8,9}，M＝{1,2,3,4,5,7,8,9}，由圖2－6兩點間的最短距離，根據(jù)最大服務(wù)半徑為3km的約束及第6居民點不適合建市場的要求，可確定集合A(j)和B(i)。如表2－3所示。 表2－3 候選點服務(wù)范圍 因為A(4)={1,3,4,5,6,7}，A(3

19、)={1,2,3,4,5,6},|A(4)|= |A(3)|=6為最大,隨機選取j’＝4。由于無容量約束故依次指派5,7,1,6,3,4點歸節(jié)點4服務(wù)。此時，N＝{2,8,9},M＝{1,2,3,5,7,8,9},更新集合A(j)和集合B(i)后如表2－4所示。 表2－4 候選點服務(wù)范圍 因為A(8)＝{8,9}，|A(8)|＝|A(9)|=2為最大，故選取j’＝8或j’＝9，并且8，9兩點歸節(jié)點8或9服務(wù)。同理，再迭代一次，得j’＝2，居民點2歸節(jié)點2服務(wù)。 因此，計算結(jié)果為（4,8,2）或（4,9,2）。 若選擇j’＝3，故依次指派1,2,3,4,5,6點歸節(jié)點3服務(wù)。

20、此時，N＝{7,8,9},M＝{1,2,4,5,7,8,9},更新集合A(j)和集合B(i)后如表2－5所示。 表2－5 候選點服務(wù)范圍 由于|A(8)|＝3最大，選擇j’＝8。因此計算結(jié)果為（3,8）。 第三章 設(shè)施規(guī)劃 11. 某生產(chǎn)線共有8項作業(yè)，其工作周期為8分鐘。已知各項作業(yè)的裝配順序和時間如表3.30所示。請根據(jù)周期時間和作業(yè)順序限制，確定最少工作站數(shù)和各項作業(yè)的安排，并算出此安排下生產(chǎn)線的效率。 表3.30 周期時間和作業(yè)順序表 解：由題意得網(wǎng)絡(luò)活動圖（Job on nodes）： A B C D E F G H 由題意各作業(yè)所需

21、時間之和=5+3+4+3+6+1+4+2=28 最小工作數(shù)=28/8=3.5,因此需要4個工作臺 根據(jù)作業(yè)的相關(guān)情況進行安排，結(jié)果如下表 工作站序號 作業(yè)單元 工作時間 空閑時間 1 H,G,F 7 1 2 E 6 2 3 D，C 7 1 4 B，A 8 0 生產(chǎn)線效率=完成作業(yè)所需時間總和/(實際工作站總數(shù)*時間周期)=284×8=0.875。 12.某流水線有17項作業(yè)需要平衡，其中最長的作業(yè)為2.4分鐘，所有作業(yè)的總時間為18分鐘。該流水線每天工作450分鐘。試求： （1）最大和最小的周期時間各是多少？ （

22、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)能為[25,187.5]。 （3）依題意有需要18/2.4

23、=7.5≈8，所以最少需要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.解題思路：單向物流從至

24、表 → 雙向物流從至表 → 作業(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.

25、路線比例設(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) 750（1） 繳費(D) 根據(jù)學生流量劃分物流等級確定物流路線比例如下： 序號 作業(yè)單位對 強度值 路線比例設(shè)計 路線條數(shù) 物流強度比例 強度等級 1 C-D 750 20% 1 33.3% E 2 A-B 700 20% 1 31.1% E

26、3 A-C 550 20% 1 24.4% E 4 B-C 200 40% 2 11.1% O 5 A-D 50 O 合計 2250 由以上關(guān)系圖得接近程度排序表 領(lǐng)表A 咨詢B 領(lǐng)班級卡C 繳費D 領(lǐng)表A 3/E 3/E 1/O 咨詢B 3/E 1/O 0/U 領(lǐng)班級卡C 3/E 1/O 3/E 繳費D 1/O 0/U 3/E 合計 7 4 7 4 排序 2 4 1 3 作業(yè)單位位置相關(guān)圖和作業(yè)單位面積相關(guān)圖 領(lǐng) 表 繳 費 領(lǐng)班級卡

27、咨 詢 領(lǐng)班級卡 繳 費 領(lǐng) 表 咨 詢 現(xiàn)四道手續(xù)：領(lǐng)取表格、咨詢、領(lǐng)取班級卡和確認交費，分別安排在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)圖可得接近程度排序表如下： A B C D E A 4/A 2/I 0/U 0/U B 4/A 2/I 3/E 3/E C 2/I 2/

28、I 0/U 0/U D 0/U 3/E 0/U 1/O E 0/U 3/E 0/U 1/O 合計 6 12 4 4 4 排序 2 1 5 3 4 可得作業(yè)單位位置相關(guān)圖如下： B A D E C 15. 某工廠有ABCDE五個車間，布置圖如下，其中＋為各車間距心。該廠生產(chǎn)四種產(chǎn)品，各產(chǎn)品的工藝路線和每月產(chǎn)量如表3.4所示，而且每種產(chǎn)品的生產(chǎn)批量為50件。 （1）試以直角距離計算兩兩車間的距離從至表； （2）計算物流搬運量從至表F； （3）計算搬運工作量，并以之作為物流強度表示從至表。假設(shè)每批次搬運移動1米的成本

29、是2元/米·批，試將上述物流強度從至表轉(zhuǎn)化為物流成本從至表。 解：（1）車間直角距離從至表 A B C D E A 27 54 75 39 B 27 27 48 66 C 54 27 39 69 D 75 48 39 48 E 39 66 69 48 (2) 物流搬運量從至表 A B C D E A 600 650 900 0 B 600 0 0 C 850 400 D 1750 E (3

30、)物流強度從至表（物流強度=距離*物流量） A B C D E A 16200 35100 67500 0 B 16200 0 0 C 33150 27600 D 84000 E 因為每批次搬運移動1米的成本是2元/米·批，所以每件搬運成本為2/50=0.04元/米*件，得到物流成本從至表如圖。 物流成本從至表 A B C D E A 648 1404 2700 0 B 648 0 0 C 1326 1104

31、D 3360 E 16. 已知某工廠的各作業(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布置在平面圖中部，其它按A→E→I→O→U級關(guān)系從多到少的順序依次放到平面圖中，可得放置順序為Y→X→Z→U→W→T→V,在布置的過程中應(yīng)保持關(guān)系強度大的樣板盡量靠近放。 第二階段，據(jù)各作業(yè)單位面積，以20 m2為一個面積單位得帶面積的平面圖如下：