規(guī)劃計算題整理

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

2、；由網(wǎng)絡圖確定候選設施點j可覆蓋的需求點集合A(j)和可覆蓋需求點i的設施節(jié)點的集合B(i)，見表2.10.1。2.10.1 候選點服務范圍村落號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服務。此時N=1,5，M=1,2,3,5,6,7；則更新候選點服務范圍，見表2.10.2。2.10.2 更新后的候選點服務范圍村落號A(j)B(i)1

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

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

5、5。由于笛卡爾距離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）設初始點為（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)

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

7、000元/臺；B地的年固定成本為920000元，可變成本為13000元/臺。產品最后售價為17000元/臺。（1） 當產量為多少時，兩地的總成本相等？（2） 當產量處于什么范圍時，A地優(yōu)于B地？當產量處于什么范圍時，B地優(yōu)于A地？解：答：設x為之制造商的年產量 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),因此得0x120時，B地優(yōu)于A地。13利用表2.8所示的因素評分，以最大綜合得分為基礎，建模分析應選擇地點A、B、C中的哪一個? 表2.8 因

8、素評分表解：權重矩陣設為W，則WT=0,15 0.20 0.18 0.27 0.10 0.10三個位置的因素評分作為3行構成因素矩陣S。S=80 72 88 94 98 9670 76 90 86 90 8560 92 90 80 82 75可得綜合加權矩陣E=S*W=87.0282.6280.90。可知E(A) E(B) E(C)。即選擇A點。14.一個玩具制造商在全國的五個地區(qū)生產玩具，原材料將從一個新的中心倉庫運出，而此倉庫的地點還有待確定。運至各地的原材料數(shù)量相同，已建立一個坐標城，各地的坐標位置如表2.9所示。請確定中心倉庫的坐標位置。表2.9 各地的坐標位置解：設倉庫的坐標為（x0

9、，y0)，五個生產地為(xi,yi),倉庫到各生產地的距離為di,因運至各地的原材料數(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直到運費無法減小。用MATLAB 進行編碼：運行結果得，迭代78次得到最優(yōu)解。其中選址坐標為（

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

11、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迭代得，結果如圖結果保留整數(shù)得最優(yōu)解為（42.22076，33.82437）,H=188709或用MA

12、TLAB進行編碼（文件見附件）：運行結果得，迭代59次得到最優(yōu)解。其中選址坐標為（42.2865, 33.6732），最小運費為H= 188707.914。16. 籌建一農副產品流通加工廠，可供選擇的候選廠址有D、E、F三處，因地址不同各廠加工成本亦有區(qū)別，各廠址每年費用如表2.7所示。此外，為決定廠址還考慮了一些重要的非成本因素，如當?shù)馗偁幠芰?、氣候變化和周圍環(huá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，要求用因次分析法評定最佳

13、廠址在何處。表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個不同的主觀因素） 競爭能力（FD=E） 注：D=E，比較記為0.5兩兩相比廠址FED比重SiaD00.50.50.167E00.50.50.167F1120.666 氣候（FDE）兩兩相比廠址FED比重SiaD0110.33E000F1120.67 環(huán)境（EFD）兩兩相比廠址FED比重SiaD0000E1

14、120.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）計算位置量度值LMi，LMi=X*SMi+（1-X）*OMi由于題中沒有給出主觀因素與客觀因素的相互比重，假設兩者相等即同

15、種重要，即主客觀比重值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ī)劃建設若干個農貿市場為將來該區(qū)9個主要居民點提供服務，除第6居民點外，其他各點均有建設市場的條件，如圖26所示。已知市場的最大服務直徑為3km，為保護該區(qū)域的環(huán)境，希望盡可能少地建造農貿市場。問應如何規(guī)劃？3圖26 小區(qū)居民點位置圖解：N1,2,3,4

16、,5,6,7,8,9，M1,2,3,4,5,7,8,9，由圖26兩點間的最短距離，根據(jù)最大服務半徑為3km的約束及第6居民點不適合建市場的要求，可確定集合A(j)和B(i)。如表23所示。表23 候選點服務范圍因為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服務。此時，N2,8,9,M1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如表24所示。表24 候選點服務范圍因為A(8)8,9，|A(8)|A(9)|=2為最大，故選取j8或j9，并且8，9兩

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

18、意得網(wǎng)絡活動圖（Job on nodes）：ABCDEFGH由題意各作業(yè)所需時間之和=5+3+4+3+6+1+4+2=28最小工作數(shù)=28/8=3.5,因此需要4個工作臺根據(jù)作業(yè)的相關情況進行安排，結果如下表工作站序號作業(yè)單元工作時間空閑時間1H,G,F 712E 6 23D，C 7 14B，A 8 0生產線效率=完成作業(yè)所需時間總和/(實際工作站總數(shù)*時間周期)=2848=0.875。12.某流水線有17項作業(yè)需要平衡，其中最長的作業(yè)為2.4分鐘，所有作業(yè)的總時間為18分鐘。該流水線每天工作450分鐘。試求：（1）最大和最小的周期時間各是多少？（2）該流水線理論上可能達到的每日產能是多少？（

19、3）按最大產能來算，最少需要幾個工作站？（4）若每天產能為125分鐘，則周期時間應為多長？（5）若周期時間分別是9分鐘和15分鐘，則產能分別是多少？ 解：（1）當17項作業(yè)只能串行依次進行時，可得最大周期為18min。當17項作業(yè)均并行進行時，可得最小周期為2.4min。（2）產能為單位時間生產的產品數(shù)量。以最大周期計算，得最小產能為1/18min=0.056/min；以最小周期計算，得最大產能為1/2.4min=0.417/min；綜上所述，每日可能產能為25,187.5。（3）依題意有需要18/2.4=7.58，所以最少需要8個工作站。（4）周期時間為450/125=3.6min。（5）當

20、周期時間為9min時，產能為450/9=50/天；當周期時間為15min，產能為450/15=30/天。13. 某學院注冊有四道手續(xù)：領取表格、咨詢、領取班級卡和確認交費，分別安排在A、B、C、D四個連續(xù)相鄰的同樣大小的房間，因為同時有新老學生，如果450名新學生領表后去咨詢，550名老學生領表后直接去領班級卡，而畢業(yè)班學生已經注冊過，領表后直接去繳費，詳細學生流向如表3.31所示。試問已有布置是否可以改進，若能，該如何改進？表3.31 學生流向表要點：1.解題思路：單向物流從至表 雙向物流從至表 作業(yè)對按雙向物流從至表中強度值排序，劃分物流等級確定物流路線比例 參考相關圖得接近程度排序表 按

21、接近程度得作業(yè)單位位置相關圖 按接近程度排序得作業(yè)單位面積相關圖 2.參考相關圖：物流強度等級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ù)解：由學生流向表得到雙向物流表如下：雙向物流表領表（A）咨詢(B)領班級卡(C)繳費(D)領表（A）700（2）550（3）50（5）咨詢(B)200（4）領班級卡(C)750（1）繳費(D)根據(jù)學生流量劃分物流等級確定物流路線比例如下：序號作業(yè)單位對強度值路線比例設計路線條數(shù)物流強度比例強度等級1C-D75

22、020%133.3%E2A-B70020%131.1%E3A-C55020%124.4%E4B-C20040%211.1%O5A-D50O合計2250由以上關系圖得接近程度排序表領表A咨詢B領班級卡C繳費D領表A3/E3/E1/O咨詢B3/E1/O0/U領班級卡C3/E1/O3/E繳費D1/O0/U3/E合計7474排序2413作業(yè)單位位置相關圖和作業(yè)單位面積相關圖領 表繳 費領班級卡咨 詢領班級卡繳 費領 表咨 詢現(xiàn)四道手續(xù)：領取表格、咨詢、領取班級卡和確認交費，分別安排在A、B、C、D四個連續(xù)相鄰的同樣大小的房間，即位置為下圖關系領班級卡繳 費領表咨詢該布置可得到改進，改進方案為領班級卡繳 費領 表咨 詢14. 根據(jù)作業(yè)相關圖，繪制作業(yè)單位位置相關圖。 圖3.28 習題14作業(yè)相關圖解：由該作業(yè)相關圖可得接近程度排序表如下：ABCDEA4/A2/I0/U0/UB4/A2/I3/E3/EC2/I2/I0/U0/UD0/U3/E0/U1/OE0/U3/E0/U1/O合計612444排序21534可得作業(yè)單位位置相關圖如下：BADEC15. 某工廠有ABCDE五個車間，布置圖如下，其