運籌學(xué)習(xí)題答案(第五章)課件

第五章習(xí)題解答

5.1某地準(zhǔn)備投資D元建民用住宅?？梢越ㄗ≌牡攸c有n處：A1，A2，…，An。在Ai處每幢住宅的造價為dj；，最多可造aj幢。問應(yīng)當(dāng)在哪幾處建住宅，分別建幾幢，才能使建造的住宅總數(shù)最多，試建立問題的數(shù)學(xué)模型。1

5.2要在長度為l的一根圓鋼上截取不同長度的零件毛坯，毛坯長度有n種，分別為aj，(j=1，2，…,n)。問每種毛坯應(yīng)當(dāng)各截取多少根，才能使圓鋼殘料最少，試建立本問題的數(shù)學(xué)模型。第五章習(xí)題解答2第五章習(xí)題解答5.3有一批每根長度為l的圓鋼，需要截取n種不同長度的零件毛坯。長度為aj的毛坯必須有mj段(j＝1，2，…，n)。為了方便，每根圓鋼只截取一種長度的毛坯。應(yīng)當(dāng)怎樣截取，才能使動用的圓鋼數(shù)目最少，要求建立數(shù)學(xué)模型。3(4)2號和8號至少有一個不出場。問應(yīng)當(dāng)選擇哪5名隊員上場，才能使出場隊員平均身高最高，試建立數(shù)學(xué)模型。第五章習(xí)題解答5

5.5一個旅行者要在其背包里裝一些最有用的旅行物品。背包容積為a，攜帶物品總重量最多為b。現(xiàn)有物品m件，第i件物品體積為ai，重量為bi(i＝1，2，…，m)。為了比較物品的有用程度，假設(shè)第j件物品的價值為ci(i＝1，2，…，m)。若每件物品只能整件攜帶，每件物品都能放人背包中，并且不考慮物品放人背包后相互的間隙。問旅行者應(yīng)當(dāng)攜帶哪幾件物品，才能使攜帶物品的總價值最大，要求建立本問題的數(shù)學(xué)模型。第五章習(xí)題解答6第五章習(xí)題解答75.6用割平面法解下列整數(shù)規(guī)劃：第五章習(xí)題解答85.8某公司生產(chǎn)A，B和C3種產(chǎn)品，售價分別為12元、7元和6元。生產(chǎn)每件A產(chǎn)品需要1h技術(shù)服務(wù)、10h直接勞動、3kg材料；生產(chǎn)每件B產(chǎn)品需要2h技術(shù)服務(wù)、4h直接勞動、2kg材料；生產(chǎn)每件C產(chǎn)品需要1h技術(shù)服務(wù)、5h直接勞動、1k8材料?，F(xiàn)在最多能提供100h技術(shù)服務(wù)、700h直接勞動、400kg材料。生產(chǎn)成本是生產(chǎn)量的非線性函數(shù)，如表5-11、表5-12、表5-13所示。要求建立一個總利潤最大的生產(chǎn)計劃的數(shù)學(xué)模型。提示：對每種產(chǎn)品不同成本的產(chǎn)量范圍各設(shè)一個0-1變量。）第五章習(xí)題解答10第五章習(xí)題解答12

5.10有五項設(shè)計任務(wù)可供選擇。各項設(shè)計任務(wù)的預(yù)期完成時間分別為3，8，5，4，10(周)，設(shè)計報酬分別為7，17，11，9，21(萬元)。設(shè)計任務(wù)只能一項一項地進(jìn)行，總的期限是20周。選擇任務(wù)時必須滿足下面要求：1．至少完成3項設(shè)計任務(wù)；2．若選擇任務(wù)1，必須同時選擇任務(wù)2；3．任務(wù)3和任務(wù)4不能同時選擇。應(yīng)當(dāng)選擇哪些設(shè)計任務(wù)，才能使總的設(shè)計報酬最大?第五章習(xí)題解答14第五章習(xí)題解答15

5.11某城市可劃分為11個防火區(qū)，已設(shè)有4個消防站，見下圖所示。第五章習(xí)題解答16上圖中，虛線表示該消防站可以在消防允許時間內(nèi)到達(dá)該地區(qū)進(jìn)行有效的消防滅火。問能否關(guān)閉若干消防站，但仍不影響任何一個防火區(qū)的消防救災(zāi)工作。(提示：對每—個消防站建立一個表示是否將關(guān)閉的0-1變量。)

第五章習(xí)題解答17

5.12現(xiàn)有P個約束條件

第五章習(xí)題解答需要從中選擇q個約束條件，試借助0-1變量列出表達(dá)式。18

5.14需要分派5人去做5項工作，每人做各項工作的能力評分見表5-14。應(yīng)如何分派，才能使總的得分最大?第五章習(xí)題解答表5-14業(yè)務(wù)人員B1B2B3B4B5A11.30.8001.0A201.21.31.30A31.0001.20A401.0500.21.4A51.00.90.601.120第五章習(xí)題解答21

(2)如果在目標(biāo)函數(shù)中，用3x2來代替3x，請相應(yīng)地修改(1)的答案。第五章習(xí)題解答235.16卡車送貨問題(覆蓋問題)。龍運公司目前必須向五家用戶送貨，在用戶A處卸下1單位重量的貨物，在用戶B處卸下2單位重量的貨物，在用戶C處卸下3單位重量的貨物，在用戶D處卸下4單位重量的貨物，在用戶E處卸下8單位重量的貨物。公司有各種卡車四輛。1號車載重能力為2單位重量，2號車載重能力為6，3號車載重能力為8，4號車載重能力為11?？ㄜ噅的運費為cj。假定一輛卡車不能同時給用戶A和C二者送貨；同樣，也不能同時給用戶B和D二者送貨。(1)請列出一個整數(shù)規(guī)劃模型表達(dá)式，以確定裝運全部貨物應(yīng)如何配置卡車，使其運費為最小。第五章習(xí)題解答24(2)如果卡車j給用戶i運貨時須收附加費cij，試敘述應(yīng)如何修改這一表達(dá)式。答：在目標(biāo)函數(shù)中增加cijxij。(3)如果每輛卡車在一天內(nèi)的送貨次數(shù)不能超過兩次，試說明應(yīng)如何修改表達(dá)式。答：將每輛卡車的運量增加一倍。(4)請說明如果在卡車的運貨路線上增加一些約束條件時，對模型的表達(dá)式有何影響。答：如果某輛車不能到達(dá)某用戶，可以通過將附加費cij設(shè)為無窮大來實現(xiàn)。第五章習(xí)題解答265.17東方公司必須為其五臺主要設(shè)備擬訂預(yù)防性維修計劃，這個計劃將持續(xù)八周。假定每臺設(shè)備的編號為1、2、3、4、5。維修設(shè)備1時，在第一周內(nèi)需要4單位的勞動量(比如說為人-周)，在第二周內(nèi)需要6單位，在第三周內(nèi)需要3單位。維修工作最早可以在第一周開始，最晚在第四周開始。其余各臺設(shè)備的數(shù)據(jù)列在表5-15中。請對下列各小題列出最優(yōu)化模型表達(dá)式。(1)假定在第i周內(nèi)可供使用的最大勞動量為Li單位。請列出一個可行的速度計劃(即確定每臺設(shè)備從哪一周開始維修)。第五章習(xí)題解答27第五章習(xí)題解答表5-15設(shè)備編號第一周第二周第三周最早開工周最遲開工周14631423251337112541362658923528第五章習(xí)題解答(2)假定該公司要求每周使用的勞動量波動幅度之和為最小。[例如，若每臺設(shè)備都盡可能的早開始維修，則每周所需的勞動量為7、16、20、16、2、0、0、0，結(jié)果，周與周之間的波動幅度之和為(16-7)+(20-16)+(20-16)+(16-2)+(2-0)+(0-0)+(0-0)＝33。解：增加目標(biāo)函數(shù)minZ=|wi+1-wi|30(3)假設(shè)該公司要求在八周內(nèi)的任何一周所需的最大勞動量為最小。解：增加minZ=w,w>wi,i=1,2,3,4,5,6,7,8(4)假設(shè)該公司要求將最大的每周勞動量波動幅度減至最小。(如果每臺設(shè)備都盡可能早的開始維修，則在第四周至第五周之間的最大波動幅度為16-2＝14。)解：增加minZ=w,w>|wi+1-wi|,i=1,2,…7(5)如果設(shè)備3不能在設(shè)備1開始維修前開工，試說明應(yīng)如何修改(1)的答案。解：增加 p11+p12>p32;p11+p12+p13>p33;第五章習(xí)題解答31

如果設(shè)備4必須與設(shè)備3同時開始維修(因此，設(shè)備4的最晚開工時間是在第五周而不是第六周)。解：增加 p3i