規(guī)劃計算題整理

共享知識分享快樂共享知識分享快樂卑微如螻蟻、堅強似大象卑微如螻蟻、堅強似大象第二章設(shè)施選址一—家銀行準備在某縣的農(nóng)村地區(qū)投放一批 自動取款機，以方便農(nóng)村的用戶取款。該農(nóng)村地區(qū)的村落座落情況和相對距離如圖1所3示。為了能確保任一村的人都可以在20分鐘之內(nèi)到達自動取款機取款，銀行需要多少臺自動取款機？它們的位置又在哪里要點：1.明確N,M,4444444含義；2.444分析正確后，444可參照444直接寫出，無需再看網(wǎng)絡(luò)圖;3.熟悉最少點覆蓋啟發(fā)式算法的步驟，考慮是否有容量約束。解：【集合覆蓋模型】區(qū)域中需求點集合N={1,2,3,4,5,6,7}；ATM取款機設(shè)施候選點集合M={1,2,3,4,5,6,7}；由網(wǎng)絡(luò)圖確定候選設(shè)施點J可覆蓋的需求點集合A44和可覆蓋需求點，的設(shè)施節(jié)點的集合 ，見表2.10.1。2.10.1候選點服務范圍村落號AAAAAAAA11,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因為={2,3,4,6,7}，| |=5為最大，故首先=4。因無容量約束，指派2,3,4,6,7歸村落4服務。此時N={1,5}，M={1,2,3,5,6,7}；則更新候選點服務范圍，見表2.10.2。2.10.2更新后的候選點服務范圍

村落號AAAAAAAA111,2,321,5314552,5,6657因為工2={1,5}=N,恰好滿足條件。則A=2O綜上所述，銀行需要2臺自動取款機，分別至于村落號為2和4的位置，2號為1,5村落服務，4號為2,3,4,6,7村落服務。11.—個臨時幫助服務中心計劃在一個大城市的郊外開設(shè)一個新的辦公室。在經(jīng)過一定的精簡之后，該公司有5個大的合作伙伴。在一個以km為單位的笛卡爾坐標系中，它們的坐標分別為：（4,4），（4，11），（7，2），（11，11），（14，7）。它們的服務需求量的權(quán)重分別為：wl=3，w2=2，w3=2，w4=4，w5=1。對于該服務中心來說，主要的日常費用是他們員工完成任務過程中的運輸費用。因此，用城市距離進行考慮，要求新的辦公室到各個合作伙伴之間運輸?shù)倪\輸費用最小。1）請確定一個新辦公室的地址，用笛卡爾坐標來表達相應結(jié)果。2）如果由于該地區(qū)的人口稀少，城市還沒有達到一定的規(guī)模，可以用歐幾米德距離進行計算，新辦公室又得在哪里投建?請比較兩次結(jié)果，分析它們之間的關(guān)系。要點：1.補充交叉中值模型知識點上述原理可以推廣到多個需求點時的情形.給定片介點的坐標g,為〕，町…),斑定設(shè)施的坐標(芭、”.使該點至所有會定點的總折線距離最值，目標函數(shù)為F打三川==,一/卜二|了一仇| an-Z-1 2-1求署方法如七-將修、斗「…、/生行排序，找出中間值.當H為奇數(shù)時，則最忙的工就零于三豐同值.當W為偶數(shù)時，記兩個中間值為5和三十］,貝1J最優(yōu)的，為三工工二工1+一例如，若■定(3,8).(14,5),(7,9)三個點，將，里標排序后為3、114,則最優(yōu)的士坐標為L如果給定咨4)、［6,2).(1b打：、＜4,25)四個點，將左坐標排序后為4、6、1L23,則改施最優(yōu)的x坐標為6三m￡1入對于最優(yōu)的y坐標的騎定，與二述方法完全一岸。*TOC\o"1-5"\h\z考慮圣戢點的物沛量的不同，假設(shè)需求點］的物流量為陰，則目標函數(shù)為中陀 n/(x.y)=VwJr-xJ+VwJy-yJ 0-3)?—1 3-1如果W為整數(shù)，則可以認為轆標點(鼻片)處有當公需求，將加點費求的選址問題轉(zhuǎn)換成工;1%點戢的選址問題，然后利用前面的方法獲得設(shè)熊的最優(yōu)的坐標值?如果叫為小數(shù)，可先將其處理為螺形式.例如，假設(shè)叫等于也丸我們可以取嗎=丸然后將目標函數(shù)縮個1門0,這樣就可以延用前面的方法求解：V關(guān)鍵句：將n點需求的選址問題轉(zhuǎn)化為2&?￡點需求的選址問題。.笛卡爾距離即直角距離，歐基米德距離即直線距離；.重心法：初始化+迭代公式+Excel/C編程/matlab編程迭代+迭代終止條件

解：（1）設(shè)新辦公室的地址的坐標為?y），給題目已知的5個點編號1?5。由于笛卡爾距離=|-|+|-|。為偶數(shù)，即均在第六個、第七個點之間。則目標函數(shù)為時總運輸距離H最短。為偶數(shù)，即均在第六個、第七個點之間。dddddddd(idddddddddddddddddddddd出dd/dddddddddddd|d可得， 。 。（2）設(shè)初始點為（，）有題意得，阿基米德距離為dddd=dd』dd/ddddddd」ddd aa aa目標函數(shù)運輸總費用la目標函數(shù)運輸總費用ladladlalalala利用不動點算法，取一個初始的迭代點(, )=(8,7),此時 =62.51令dddc=ddd電ddddd ddd 電dddc=dd逑dd dddddWdd 也出dddddd dd dddddj, dddj.lalalalaladladlalalalaladABCDEFGHx y dl d2 d3 d4 d5 H28 7 55.6568545.09902 5 662.5117537.6512597.3688954.9680135.1494295.408254.9395336.35944962.1369847.585267.4860795.0006845.0201335.5172094.8998056.4331362.1090857.582447.5344875.0325414.9843415.565054.8671866.43977962.1049367.5922267.5600375.0574654.9736745.5914884.8421356.43220162.1034677.6025627.5760535.0760824.9700975.6085164.8234846.42332162.1027387.6109897.5870335.0897984.968665.6203424.8097556.41592362.1023497.6173947.5948595.0998584.967955.6288214.7996886.41026662.102131017.622157.6005255.1072254.9675345.6349764.7923176.4060662.10202117.625657.6046525.1126174.9672665.6394654.7869226.40296362.10195迭代得，結(jié)果如圖由費用結(jié)果保留四位小數(shù)得最優(yōu)解為此時費用最小為()比較兩次結(jié)果可知歐基米德中的費用小于笛卡爾距離，因直線距離是(直角距離，因此用歐基米德距離更為精確。直角距離比較適合于城區(qū)范圍內(nèi)的選址，歐基米德距離比較適合于遠距離的選址。12.一臺機器工具小制造商要遷址，并確定了兩個地區(qū)以供選擇。A地的年固定成本為800000元，可變成本為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+14000xB地，總成本C(B)=920000+13000x1)若兩地成本相等，則C(A)=C(B)解得：x=1202)若A地優(yōu)于B地，則C(A)<C(B),因此得0<x<120同理，當x>120時，B地優(yōu)于A地。.利用表2.8所示的因素評分，以最大綜合得分為基礎(chǔ)，建模分析應選擇地點A、B、C中的哪一個？表2.8因素評分表因素(每項總分1仆仆分)權(quán)重位置ABC便利設(shè)施也15卻7060停車場0J0727692顯示區(qū)域0.18889090顧客交逋0.27948680運營成本0,109S9082臨近也1096?575100

解：權(quán)重矩陣設(shè)為W,則勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿勿加三個位置的因素評分作為3行構(gòu)成因素矩陣S。WWWWWWWWWWWWWWWWWWWVWWWWWWWWXWWWWWWWW

WWWWWWWWWWWWWWWWWWWWWW可得綜合加權(quán)矩陣E=S*W=VWWV^WWWWWWW可知E(A)>E(B)>E(C)。即選擇A點。.一個玩具制造商在全國的五個地區(qū)生產(chǎn)玩具，原材料將從一個新的中心倉庫運出，而此倉庫的地點還有待確定。運至各地的原材料數(shù)量相同，已建立一個坐標城，各地的坐標位置如表2.9所示。請確定中心倉庫的坐標位置。表2.9各地的坐標位置表2.9各地的坐標位置解：設(shè)倉庫的坐標為(，，五個生產(chǎn)地為,倉庫到各生產(chǎn)地的距離為,因運至各地的原材料數(shù)量相同，故可設(shè) )初始解：”71初始解：”71' 1'=——x,y（o）二一乙0nj=1nj=1y.,即喀WWW,14WVWWW4直線距離為W^Www1^1ylyWW愀目標函數(shù)運輸總費用=目標函數(shù)運輸總費用=，其中 )wWwwWWWWWWWWWWW

wWWW根據(jù)下列進行迭代：mW咻 uWWWW&wwwww上^泗吧WWWWWWWWWWWWWW

加楸〃勿收皿/WWwW直到運費無法減小。用進行編碼:clearelcai1)-5.biI,.-i.x-[j8446]:3-C26:4]：“]￡gij=：；5'h(i)-y(j))"2)"0.5er.dE'iJ-d：l>d(2j+d(3)+d(4)+d：5).N=I：.).whileH(i)<M|A=0B=0;C=O;□forj=l;5B=E+l/d(j);名稱▼值 最小值—值y [7.2,6,14]1 7C=C4y(j)/d(j);——x [3.B,4,4,6] 3 8end—M13.4550 13.455013.4550N=H(l);1j 5 5 5i=i+L;——i 79 79 79臬=A/E;mH 1x79do...13.455013.6094md [3,9S3^3...0.3765 3.9835□forj=ls5i-i-iC 15.&476 15.647615.64764(i'=(U(i?-KGD"2Mb(ii-F(j))2>~0.E;mE 3.9101 3.9101 3.9101endi—i—1b 1x79da...4 4,0962H.L.-d(l)+d(2)-hd(3)4c；(4)4d(6J；A 21,S885 21.988521.9835endrr-\a\ 1x79dorrr5 5.6235運行結(jié)果得，迭代78次得到最優(yōu)解。其中選址坐標為(5.6235,4.9918),最小運費為H=13.4550?；蛴?迭代得，結(jié)果如圖RIAEcDEFGHx y dl d2 d3 d4 d5 H5 4 3.605551 3.605551 2.23606B 3.16227B 1 13.609455.22169 4.096238 3.656192 3. 480405 2.262042 3.32B546 0.784237 13.511425.328709 4.088713 3.728067 3. 390946 2.327765 3.362382 0.677127 13.4B6295.396B46 4.065729 3.788775 3. 323198 2.385913 3.36B957 0.606725 13.473575.446264 4.047031 3.83461 3. 272904 2.430179 3.372844 0.555729 13.466275.483617 4.034095 3.B68455 3. 235695 2.462905 3.377403 0.51750B 13.461975.5123 4.025356 3.B93604 3. 207915 2.487221 3.382282 0.48B359 13.4593B5.534554 4.019364 3.912564 3. 186B88 2.505549 3.38694B 0.465849 13.457B5.551977 4.015149 3.927075 3. 170748 2.519576 3.391129 0.44B279 13.456815.565728 4.012107 3.938333 3. 158204 2.530459 3.394745 0.434441 13.4561B5.576659 4.00986 3.947165 3. 148352 2.53B99B 3.39781 0.423455 13.4557B234：567B9101112費用結(jié)果保留三位小數(shù)得最優(yōu)解為X=5.5767,y=4.010,H=13.456.某物流公司擬建一倉庫負責向四個工廠進行物料供應配送，各工廠的具體位置與年物料配送量見表2.10，設(shè)擬建物流公司倉庫對各工廠的單位運輸成本相等。利用重心法計算確定物流公司的倉庫坐標位置為多少。

表2.10各工廠的具體位置與年物料配送量工廠及其位置坐標P1P2P3P4XIY1X2Y2X3Y3Y42070606020205020年配送最2000120010002500解：設(shè)倉庫的坐標為(， ，個工廠的坐標為 ,倉庫到各生產(chǎn)XX XXTOC\o"1-5"\h\z地的距離為X"XXXXXXXxXXXXXXx,目標函數(shù)運輸總費用X XX XXH= ，為工廠年配送量，為單位運輸成本，因單位XXXXXX XXXXXX X運輸成本相等，故令=1，于是有XXXX初始解XxxXxXX=37.5,XXXXXV42.5XXXxxxxXXXxXXXXXXxx XX XX此時=192249.4xxx xxx令XXXX=xxxXx%x4XXXXXXXxm,xxxx=xxXXXXXXXxXXXxxxXXXxxXxJX xxJX XX X XXXXV XXXVAx Axx x190400.4XXXXXx由 迭代得，結(jié)果如圖ABCDEG1戈ydld2d3d4:H237.542.532,5960128,504392S,5043925.7390B192249.4333.505784:0.1632535.64:9162B.519222B.056BB22.728B7190400.4440.38.4083137.6259429.1360127.505320.74402189580.45鈍,9500M37,137513S,9723929,7589527,0665519.3S0311S9172.S641.28564：36.2232839.9242430.2582126.7632918.41562188960.7741.5274&35.56S0240.6120330.6333326.5638717.71981188847.40il.708735.0S23541,1158130,9105326.4337S17,211131SS7S5.99il.必629■72934：41.4：8B3131.1153326.3479416.B3557188751.91041.^510834.46841.7656931.2673426.2901616.55621188732.911區(qū)引27323il.9733731.3S0S26,2504516,347211SS722.21242.09174：弘.12734：2.1295131.465926.2226116.19015188716.11342.1380834.017542.2473131.5299726.2027616.071721SS712.614432.1733833.934:62432.3363931.5783526.1B8415.9B217188710.61542.2002733.S719142.40M931.6149926.1778915.914331BB709.516-1nr4Z.ZZ07&33.8243742.4551331.6427726.1701315.S62S41SS70S.S結(jié)果保留整數(shù)得最優(yōu)解為(42.22076,33.82437),H=188709

或用MATLAB進行編碼(文件見附件):clear;eLeb(l)=J2.5,z=[20BB2050：.j?=[706口2020：.■j=[2000120010002500].i-1；Eat:j=1d4(j )J (j))"2)"*5：-jhile 小:i)==J｛口：A^O;B=O,C=O; 三--fj=i：i 出a 1x60do...37.500042.2865依什川)神用此⑴. izoA 1.1935e...1.1935...1,1935^+04E二E一⑴那用； 110b 1x60do...33.673342.5000匕二,⑶呼⑴上⑴. mb 2S2.2385 282.23B5282.23B521 二二C 5,5O39e...9.5039...9.5O39eW3ltHCi：- lod [42,6183,...15.698942.6183”"I lJh: 1x60do...1.3871...1.9225e-bO5三哀W* mi 60 60 60產(chǎn)嗎 田j 4 4 4f=ri=l：1 中」.f. t.：, 「wn-匕-W 1.8871s... 1.S871...LS871e4-O5d-J,-' 2+ib(n-y(ji)f,0.i1-1-1… mw[2000,12...1000 2500Hti);E])*i1U1+h⑵*⑶短⑶+H⑷*d⑷；田X [20,60.20...20 60一end田y [70,60,20...20 70-end日l：i)=wil)xd(l)-Hj(2)Xd⑵f(3)Xd⑶I(I)xd(1)end LUJ運行結(jié)果得，迭代59次得到最優(yōu)解。其中選址坐標為(42.2865,33.6732),最小運費為H=188707.914。16.籌建一農(nóng)副產(chǎn)品流通加工廠，可供選擇的候選廠址有D、E、F三處，因地址不同各廠加工成本亦有區(qū)別，各廠址每年費用如表2.7所示。此外，為決定廠址還考慮了一些重要的非成本因素，如當?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各候選廠址每年加工成本費用

選址成本成本因素成本/千元DE尸工資250230248運輸費用181203190租金758391其他費用17922523525551要點：P中值法分5個步驟進行。解：(1)計算客觀量度值oon,00onoonO^tf0UO0 0 00000OOOGDQ—-0—-0—-OOo0000000

0 000000000同理可得： 。（2）計算主觀評比值oo（（（有3個不同的主觀因素）競爭能力（F>D=E） 注：D=E，比較記為0.5兩兩相比廠址FED比重。00D067E067F1120.666氣候（F>D>E）兩兩相比廠址FED比重。00D0110.33E000F1120.67環(huán)境（E>F>D）兩兩相比廠址FED比重SssD0000E1120.67F0110.33（3）計算主觀量度值 ， ，其中為各主觀因素的重要性指數(shù)。因素kDEF重要性指數(shù)ssSss0.1670.1670.6660.6Sss0.3300.670.3Sss00.670.330.1計算可得SSsssssssssssssssssssssssssssssssssSSsssssssssssssssssssssssssssssssssSSssssssssssssssssssssssssssssssssssss（4）計算位置量度值， （ ）由于題中沒有給出主觀因素與客觀因素的相互比重，假設(shè)兩者相等即同種重要，即主客觀比重值。SSsssssssssssssssssssssssssssssssSSssssssssssssssssssssssssssssssSSsssssssssssssssssssssssssssssss（5）決策根據(jù)各位置量度值SSs的大小，F(xiàn)廠址所得位置量度值在3個候選地址中最高，故選F為建廠廠址。

17.在某區(qū)域需規(guī)劃建設(shè)若干個農(nóng)貿(mào)市場為將來該區(qū)9個主要居民點提供服務，除第6居民點外，其他各點均有建設(shè)市場的條件，如圖2—6所示。已知市場的最大服務直徑為3km,為保護該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場。問應如何規(guī)劃？圖2—圖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ù)最大服務半徑為3km的約束及第6居民點不適合建市場的要求，可確定集合A(j)和B(i)。如表2—3所示。表2—3 候選點服務范圍居民點號A⑴B⑴1ua123,4212312331,2"次41345,6/73X753,4,5,664,5,7,8746,7,84,7,8g67&97,&99&98己因為A(4)={1,3,4,5,6,7},A(3)={1,2,3,4,5,6},IA(4)I=A⑶1=6為最大，隨機選取j'=4。由于無容量約束故依次指派5,7,1,6,3,4點歸節(jié)點4服務。此時，N={2,8,9},M

={1,2,3,5,7,8,9},更新集合A(j)和集合B(i)后如表2—4所示。表2－4候選點服務范圍8兩點歸節(jié)點或服務。同理，再迭代一次，得j'=2居民點歸節(jié)點2服務。因此，計算結(jié)果為(4,8),或2(4,9),。2若選擇j'=，故依次指派 點歸節(jié)點服務。此時，=更新集合 和集合 后如表一所示。由于IA(8)I=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è)順序表作業(yè)ABCDEFGH完敢時間53436142累后作業(yè)無ABBCCdEFG解：由題意得網(wǎng)絡(luò)活動圖(Jobonnodes)：由題意各作業(yè)所需時間之和=5+3+4+最小工作數(shù)=28/8因=3此需.5要,4個工作臺根據(jù)作業(yè)的相關(guān)情況進行安排，結(jié)果如下表工作站序號作業(yè)單元工作時間空閑時間DB生產(chǎn)線效率=完成作業(yè)所需時間總和/(實際工作站總數(shù)*時間周期)二衛(wèi)2222。12.某流水線有17項作業(yè)需要平衡，其中最長的作業(yè)為2.4分鐘，所有作業(yè)的總時間為18分鐘。該流水線每天工作450分鐘。試求：（1）最大和最小的周期時間各是多少？（2）該流水線理論上可能達到的每日產(chǎn)能是多少？（3）按最大產(chǎn)能來算，最少需要幾個工作站？（4）若每天產(chǎn)能為125分鐘，則周期時間應為多長？（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=7.5，所以最少需要8個工作站。（4）周期時間為450/125=3.6min。（5）當周期時間為9min時，產(chǎn)能為450/9=50/天；當周期時間為15min，產(chǎn)能為450/15=30/天。.某學院注冊有四道手續(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學生流向表

程度排序表一孩接近程度得作業(yè)單位位置相關(guān)圖一按接近程度排序得作業(yè)單位面積相關(guān)圖2.參考相關(guān)圖:物流強度等級AEIOUX物流路線比例10%20%30%40%00承擔的物流量比例40%30%20%10%00接近程度4321003.路線比例設(shè)計=線路條數(shù)/總線路條數(shù)解：由學生流向表得到雙向物流表如下：雙向物流表領(lǐng)表（）咨詢領(lǐng)班級卡繳費領(lǐng)表（）（）（）（）咨詢（）領(lǐng)班級卡（）繳費根據(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/