（精選）運(yùn)籌學(xué)第五、六、七、八章答案

1、5.2 用元素差額法直接給出表5-53及表5-54下列兩個(gè)運(yùn)輸問題的近似最優(yōu)解表5-53B1B2B3B4B5AiA119161021918A21413524730A3253020112310A478610442Bj152535205表5-54B1B2B3B4AiA1538616A2107121524A31748930Bj20251015【解】表5-53。Z=824表5-54 Z=4955.3 求表5-55及表5-56所示運(yùn)輸問題的最優(yōu)方案（1）用閉回路法求檢驗(yàn)數(shù)（表5-55）表5-55B1B2B3B4AiA11052370A2431280A3564430bj60604020（2）用位勢(shì)法求檢驗(yàn)

2、數(shù)（表5-56）表5-56B1B2B3B4AiA19154810A2317630A321013420A4458343bj20155015【解】（1）(2)5.4 求下列運(yùn)輸問題的最優(yōu)解（1）C1目標(biāo)函數(shù)求最小值；（2）C2目標(biāo)函數(shù)求最大值 15 45 20 40 60 30 50 40 (3)目標(biāo)函數(shù)最小值,B1的需求為30b150, B2的需求為40，B3的需求為20b360,A1不可達(dá)A4 ，B4的需求為30【解】（1）（2）（3）先化為平衡表B11B12B2B31B32B4aiA144977M70A266533220A3885991050A4M0MM0M40bj3020402040301

3、80最優(yōu)解：5.5（1）建立數(shù)學(xué)模型設(shè)xij(I=1,2,3;j=1,2)為甲、乙、丙三種型號(hào)的客車每天發(fā)往B1，B2兩城市的臺(tái)班數(shù)，則(2)寫平衡運(yùn)價(jià)表將第一、二等式兩邊同除以40，加入松馳變量x13,x23和x33將不等式化為等式，則平衡表為：B1B2B3ai甲乙丙80605065504000051015bj10155為了平衡表簡單，故表中運(yùn)價(jià)沒有乘以40，最優(yōu)解不變（3）最優(yōu)調(diào)度方案：即甲第天發(fā)5輛車到B1城市，乙每天發(fā)5輛車到B1城市，5輛車到B2城市，丙每天發(fā)10輛車到B2城市，多余5輛，最大收入為Z=40（5×80+5×60+5×50+10×

4、40）=54000（元）5.6（1）設(shè)xij為第i月生產(chǎn)的產(chǎn)品第j月交貨的臺(tái)數(shù)，則此生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型為（2）化為運(yùn)輸問題后運(yùn)價(jià)表（即生產(chǎn)費(fèi)用加上存儲(chǔ)費(fèi)用）如下，其中第5列是虛設(shè)銷地費(fèi)用為零，需求量為30。12345ai12341MMM1.151.25MM1.31.40.87M1.451.551.020.98000065656565bj5040608030(3)用表上作業(yè)法，最優(yōu)生產(chǎn)方案如下表：12345ai123450152560105653065656565Bi5040608030上表表明：一月份生產(chǎn)65臺(tái)，當(dāng)月交貨50臺(tái)；二月份交貨15臺(tái),二月份生產(chǎn)35臺(tái)，當(dāng)月交貨25臺(tái)，四月份交貨

5、10臺(tái)；三月份生產(chǎn)65臺(tái)，當(dāng)月交貨60臺(tái)，四月份交貨5臺(tái)，4月份生產(chǎn)65臺(tái)當(dāng)月交貨。最小費(fèi)用Z=235萬元。5.7 假設(shè)在例5.15中四種產(chǎn)品的需求量分別是1000、2000、3000和4000件，求最優(yōu)生產(chǎn)配置方案【解】將表5-35所示的單件產(chǎn)品成本乘以需求量，為計(jì)算簡便，從表中提出公因子1000 產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠1581385401040工廠275100450920工廠3651405101000工廠4821106001120用匈牙利法得到最優(yōu)表第一個(gè)工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個(gè)工廠加工產(chǎn)品3，第四個(gè)工廠加工產(chǎn)品2； 總成本Z1000×(589205101

6、10)1598000注：結(jié)果與例5.15的第2個(gè)方案相同，但并不意味著“某列（行）同乘以一個(gè)非負(fù)元素后最優(yōu)解不變”結(jié)論成立。5.8 求解下列最小值的指派問題，其中第（2）題某人要作兩項(xiàng)工作，其余3人每人做一項(xiàng)工作 （1） 【解】最優(yōu)解（2）【解】虛擬一個(gè)人，其效率取4人中最好的，構(gòu)造效率表為12345甲2638415227乙2533445921丙2030475625丁2231455320戊2030415220最優(yōu)解：甲戊完成工作的順序?yàn)?、5、1、2、4，最優(yōu)值Z=165最優(yōu)分配方案：甲完成第3、4兩項(xiàng)工作，乙完成第5項(xiàng)工作，丙完成第1項(xiàng)工作，丁完成第2項(xiàng)工作。5.9 求解下列最大值的指派問題

7、： （1）【解】最優(yōu)解（2）【解】最優(yōu)解第5人不安排工作。表5-58 成績表(分鐘)游泳自行車長跑登山甲20433329乙15332826丙18423829丁19443227戊173430285.10 學(xué)校舉行游泳、自行車、長跑和登山四項(xiàng)接力賽，已知五名運(yùn)動(dòng)員完成各項(xiàng)目的成績（分鐘）如表5-58所示如何從中選拔一個(gè)接力隊(duì)，使預(yù)期的比賽成績最好【解】設(shè)xij為第i人參加第j項(xiàng)目的狀態(tài)，則數(shù)學(xué)模型為接力隊(duì)最優(yōu)組合乙長跑丙游泳丁登山戊自行車甲淘汰。預(yù)期時(shí)間為107分鐘。習(xí)題六圖6396.1如圖639所示，建立求最小部分樹的01整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻窟卛，j的長度記為cij，設(shè)數(shù)學(xué)模型為：圖6406

8、.2如圖640所示，建立求v1到v6的最短路問題的01整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻炕?i，j)的長度記為cij，設(shè)數(shù)學(xué)模型為：6.3如圖640所示，建立求v1到v6的最大流問題的線性規(guī)劃數(shù)學(xué)模型?！窘狻?設(shè)xij為弧（i,j）的流量，數(shù)學(xué)模型為6.4求圖641的最小部分樹。圖6-41（a）用破圈法,圖6-41（b）用加邊法。圖641【解】圖6-41（a），該題有4個(gè)解，最小樹長為21，其中一個(gè)解如下圖所示。圖6-41（b），最小樹長為20。最小樹如下圖所示。6.5 某鄉(xiāng)政府計(jì)劃未來3年內(nèi)，對(duì)所管轄的10個(gè)村要達(dá)到村與村之間都有水泥公路相通的目標(biāo)。根據(jù)勘測(cè)，10個(gè)村之間修建公路的費(fèi)用如表6-20所示

9、。鄉(xiāng)鎮(zhèn)府如何選擇修建公路的路線使總成本最低。表6-20兩村莊之間修建公路的費(fèi)用(萬元)123456789101234567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.211.713.69.78.910.513.414.69.110.512.68.98.8【解】屬于最小樹問題。用加邊法，得到下圖所示的方案。最低總成本74.3萬元。6.6在圖642中，求A到H、I的最短路及最短路長，并對(duì)圖(a)和(b)

10、的結(jié)果進(jìn)行比較。 圖642【解】圖642(a):A到H的最短路PAH=A,B,F,H,A,C,F,H最短路長22；A到I的最短路PAI=A,B,F,I,A,C,F,I最短路長21。對(duì)于圖642(b)：A到H的最短路PAH=A,C,G,F,H,最短路長21；A到I的最短路PAI=A,C,G,F,I,最短路長20；結(jié)果顯示有向圖與無向圖的結(jié)果可能不一樣。6.7已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣掉重新購置新設(shè)備。已知5年年初購置新設(shè)備的價(jià)格分別為3.5、3.8、4.0、4.2和4.5萬元。使用時(shí)間在15年內(nèi)的維護(hù)費(fèi)用分別為0.4、0.9、1.4、2.3和3萬元。試確定一個(gè)設(shè)備更新策略，使5

11、年的設(shè)備購置和維護(hù)總費(fèi)用最小。【解】設(shè)點(diǎn)vj為第j年年初購置新設(shè)備的狀態(tài)，（i，j）為第i年年初購置新設(shè)備使用到第j年年初，弧的權(quán)為對(duì)應(yīng)的費(fèi)用（購置費(fèi)維護(hù)費(fèi)），繪制網(wǎng)絡(luò)圖并計(jì)算，結(jié)果見下圖所示?？傎M(fèi)用最小的設(shè)備更新方案為：第一種方案，第1年購置一臺(tái)設(shè)備使用到第5年年末；第二種方案，第1年購置一臺(tái)設(shè)備使用到第2年年末，第3年年初更新后使用到第5年年末?？傎M(fèi)用為11.5萬元。圖6436.8圖643是世界某6大城市之間的航線，邊上的數(shù)字為票價(jià)（百美元），用Floyd算法設(shè)計(jì)任意兩城市之間票價(jià)最便宜的路線表?！窘狻拷處熆衫媚０迩蠼猓篸atachpt6ch6.xlsL1v1v2v3v4v5v6v108

12、.895.686v28.801051004v3910034.814v45.653012100v581004.81209v6641410090L2v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.814v45.65307.89v58134.87.809v66414990L3v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.812v45.65307.89v58134.87.809v66412990最優(yōu)票價(jià)表：v1v2v3v4v5v6v108.88.65.686v2085134v3034.812v407.89v5

13、09v60v1、v2、v6到各點(diǎn)的最優(yōu)路線圖分別為： 6.9 設(shè)圖643是某汽車公司的6個(gè)零配件加工廠，邊上的數(shù)字為兩點(diǎn)間的距離(km)?，F(xiàn)要在6個(gè)工廠中選一個(gè)建裝配車間。（1）應(yīng)選那個(gè)工廠使零配件的運(yùn)輸最方便。（2）裝配一輛汽車6個(gè)零配件加工廠所提供零件重量分別是0.5、0.6、0.8、1.3、1.6和1.7噸，運(yùn)價(jià)為2元/噸公里。應(yīng)選那個(gè)工廠使總運(yùn)費(fèi)最小。【解】(1)利用習(xí)題6.8表L3的結(jié)果v1v2v3v4v5v6Maxv108.88.65.6868.8v28.808513412.8v38.68034.81212v45.65307.899v58134.87.80912.8v6641299

14、012選第1個(gè)工廠最好。(2)計(jì)算單件產(chǎn)品的運(yùn)價(jià)，見下表最后一行。計(jì)算單件產(chǎn)品的運(yùn)費(fèi)，見下表最后一列。v1v2v3v4v5v6單件產(chǎn)品運(yùn)費(fèi)v108.88.65.68684.88v28.808513489.16v38.68034.81282.16v45.65307.8971.96v58134.87.80981.92v6641299082.2運(yùn)價(jià)11.21.62.63.23.4選第4個(gè)工廠最好。圖6446.10 如圖644，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量?！窘狻拷o出初始流如下第一輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于5，如下圖所示調(diào)整流量。第二輪標(biāo)號(hào)：得到一條增廣鏈

15、，調(diào)整量等于2，如下圖所示調(diào)整流量。第三輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于3，如下圖所示調(diào)整流量。第四輪標(biāo)號(hào)：不存在增廣鏈，最大流量等于45，如下圖所示取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。6.11 將3個(gè)天然氣田A1、A2、A3的天然氣輸送到2個(gè)地區(qū)C1、C2，中途有2個(gè)加壓站B1、B2，天然氣管線如圖645所示。輸氣管道單位時(shí)間的最大通過量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。圖645【解】虛擬一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)T6.111得到流量v22的最小費(fèi)用流，最小費(fèi)用為271。求解

16、過程參看第4章PPT文檔習(xí)題答案。T6.1113最小費(fèi)用最大流如下圖，最大流量等于27，總費(fèi)用等于351。6.12如圖643所示，（1）求解旅行售貨員問題；（2）求解中國郵路問題。圖6-43【解】（1）旅行售貨員問題。距離表C12345618.895.68628.81054391034.81445.65312584.8129664149在C中行列分別減除對(duì)應(yīng)行列中的最小數(shù)，得到距離表C1。距離表C112345613.23.400.60.422.8610347001140.6207.251.207.29600103.2由距離表C1，v1到v4， H1= v1, v4 ,v3 ,v5 ,v6 ,v

17、2 ,v1, C(H1)=5.6+3+4.8+9+4+8.8=35.2去掉第1行第四列，d41=，得到距離表C2。得到距離表C21235622.8603470114207.251.209600103.2距離表C2的每行每列都有零，H2= H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1就是總距離最小的Hamilton回路，C(H1) =35.2。(2)中國郵路問題。虛擬一條邊取回路H1v1，v3，v4，C(H1)=9+5+3=17,C(v1，v3)=9> C(H1)/2，調(diào)整回路。所有回路滿足最短回路的準(zhǔn)則，上圖是最短的歐拉回路，其中邊(v1, v4)和(v4, v3)各重復(fù)

18、一次。習(xí)題七7.2(1)分別用節(jié)點(diǎn)法和箭線法繪制表7-16的項(xiàng)目網(wǎng)絡(luò)圖，并填寫表中的緊前工序。(2) 用箭線法繪制表7-17的項(xiàng)目網(wǎng)絡(luò)圖，并填寫表中的緊后工序表7-16工序ABCDEFG緊前工序ACAF、D、B、E緊后工序D,EGEGGG表7-17工序ABCDEFGHIJKLM緊前工序-BBA,BBD,GC,E,F,HD,GC,EIJ,K,L緊后工序FE,D,F,GI,KH,JI,KIH,JILMMM【解】（1）箭線圖：節(jié)點(diǎn)圖：（2）箭線圖：7.3根據(jù)項(xiàng)目工序明細(xì)表7-18：（1）畫出網(wǎng)絡(luò)圖。（2）計(jì)算工序的最早開始、最遲開始時(shí)間和總時(shí)差。（3）找出關(guān)鍵路線和關(guān)鍵工序。表7-18工序ABCDE

19、FG緊前工序-AAB,CCD,ED,E工序時(shí)間（周） 961219678【解】(1)網(wǎng)絡(luò)圖(2)網(wǎng)絡(luò)參數(shù)工序ABCDEFG最早開始09921214040最遲開始015921344140總時(shí)差06001310(3)關(guān)鍵路線：；關(guān)鍵工序：A、C、D、G；完工期：48周。7.4 表7-19給出了項(xiàng)目的工序明細(xì)表。表7-19工序ABCDEFGHIJKLMN緊前工序-A,BBB,CED,GEEHF,JI,K,LF,J,L工序時(shí)間(天) 8571281716814510231512（1）繪制項(xiàng)目網(wǎng)絡(luò)圖。（2）在網(wǎng)絡(luò)圖上求工序的最早開始、最遲開始時(shí)間。（3）用表格表示工序的最早最遲開始和完成時(shí)間、總時(shí)差和自

20、由時(shí)差。（4）找出所有關(guān)鍵路線及對(duì)應(yīng)的關(guān)鍵工序。（5）求項(xiàng)目的完工期?！窘狻?1)網(wǎng)絡(luò)圖（2）工序最早開始、最遲開始時(shí)間（3）用表格表示工序的最早最遲開始和完成時(shí)間、總時(shí)差和自由時(shí)差工序tTESTEFTLSTLF總時(shí)差S自由時(shí)差FA80891790B5050500C7077700D12820172999E851351300F1772472400G161329132900H82937293700I14132733472020J51318192466K103747374700L232447244700M154762476200N124759506233(4)關(guān)鍵路線及對(duì)應(yīng)的關(guān)鍵工序關(guān)鍵路線有兩條，

21、第一條：；關(guān)鍵工序：B,E,G,H,K,M第二條：；關(guān)鍵工序：C,F,L,M（5）項(xiàng)目的完工期為62天。7.5已知項(xiàng)目各工序的三種估計(jì)時(shí)間如表7-20所示。求： 表7-20工序緊前工序工序的三種時(shí)間（小時(shí)）ambA91012BA6810CA131516DB8911EB,C151720FD,E91214（1）繪制網(wǎng)絡(luò)圖并計(jì)算各工序的期望時(shí)間和方差。（2）關(guān)鍵工序和關(guān)鍵路線。（3）項(xiàng)目完工時(shí)間的期望值。（4）假設(shè)完工期服從正態(tài)分布，項(xiàng)目在56小時(shí)內(nèi)完工的概率是多少。（5）使完工的概率為0.98，最少需要多長時(shí)間?！窘狻浚?）網(wǎng)絡(luò)圖工序緊前工序工序的三種時(shí)間（小時(shí)）期望值方差ambA9101210.

22、170.25BA681080.4444CA13151614.830.25DB89119.1670.25EB,C15172017.170.6944FD,E9121411.830.6944(2)關(guān)鍵工序：A,C,E,F；關(guān)鍵路線：(3) 項(xiàng)目完工時(shí)間的期望值：10.17+14.83+17.17+11.8354(小時(shí)) 完工期的方差為0.25+0.25+0.6944+0.69441.8889(4)X0=56，56天內(nèi)完工的概率為0.927(5) p=0.98，要使完工期的概率達(dá)到0.98，則至少需要56.82小時(shí)。7.6 表7-21給出了工序的正常、應(yīng)急的時(shí)間和成本。表7-21工序緊前工序時(shí)間(天)

23、成本時(shí)間的最大縮量(天)應(yīng)急增加成本（萬元/天）正常應(yīng)急正常應(yīng)急A1512506535BA1210100120210CA74808933DB,D1410405243FC1613456035GE,F1086084212（1）繪制項(xiàng)目網(wǎng)絡(luò)圖，按正常時(shí)間計(jì)算完成項(xiàng)目的總成本和工期。（2）按應(yīng)急時(shí)間計(jì)算完成項(xiàng)目的總成本和工期。（3）按應(yīng)急時(shí)間的項(xiàng)目完工期，調(diào)整計(jì)劃使總成本最低。（4）已知項(xiàng)目縮短1天額外獲得獎(jiǎng)金4萬元，減少間接費(fèi)用2.5萬元，求總成本最低的項(xiàng)目完工期。(1) 正常時(shí)間項(xiàng)目網(wǎng)絡(luò)圖項(xiàng)目網(wǎng)絡(luò)圖總成本為435，工期為64。(2)應(yīng)急時(shí)間項(xiàng)目網(wǎng)絡(luò)圖總成本為560，工期為

24、51。(3)應(yīng)急時(shí)間調(diào)整工序C、F按正常時(shí)間施工，總成本為560-9-15536，完工期為51。(4) 總成本最低的項(xiàng)目完工期工序A、E分別縮短3天，總成本為435+15+12-6.5×7416.5，完工期為57。7.7繼續(xù)討論表7-21。假設(shè)各工序在正常時(shí)間條件下需要的人員數(shù)分別為9、12、12、6、8、17、14人。（1）畫出時(shí)間坐標(biāo)網(wǎng)絡(luò)圖（2）按正常時(shí)間計(jì)算項(xiàng)目完工期，按期完工需要多少人。（3）保證按期完工，怎樣采取應(yīng)急措施，使總成本最小又使得總?cè)藬?shù)最少，對(duì)計(jì)劃進(jìn)行系統(tǒng)優(yōu)化分析?！窘狻浚?）正常時(shí)間的時(shí)間坐標(biāo)網(wǎng)絡(luò)圖(2) 按正常時(shí)間調(diào)整非關(guān)鍵工序的開工時(shí)間(3)略，參看教材。7

25、.8用WinQSB軟件求解7.5。7.9用WinQSB軟件求解7.6。習(xí)題八8.1 在設(shè)備負(fù)荷分配問題中，n=10，a=0.7，b=0.85，g=15，h=10，期初有設(shè)備1000臺(tái)。試?yán)霉?8.7)確定10期的設(shè)備最優(yōu)負(fù)荷方案?！窘狻繉⒔滩闹衋的下標(biāo)i去掉。由公式得(g-h)/g(b-a)0.2222，a0a1a21+0.70.492.192.222a0+a1a2a32.533，nt12，t=7，則16年低負(fù)荷運(yùn)行，710年為高負(fù)荷運(yùn)行。各年年初投入設(shè)備數(shù)如下表。年份12345678910設(shè)備臺(tái)數(shù)1000850723614522444377264184.81298.2如圖84，求A到F的

26、最短路線及最短距離?！窘狻緼到F的最短距離為13；最短路線 A B2 C3 D2 E2 F及AC2 D2 E2 F8.3求解下列非線性規(guī)劃(1) (2) （3） (4) (5) （6）【解】（1）設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=C 則有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，從后向前依次有k3， 及最優(yōu)解 x3*=s3k2， 由 故 為極大值點(diǎn)。 所以 及最優(yōu)解x2*=s2k=1時(shí)， ，由，得故已知知x1 + x2+ x3 = C，因而按計(jì)算的順序推算，可得各階段的最優(yōu)決策和最優(yōu)解如下， 由s2=s1x1*=2C/3， 由s3=s2x2*=C/3，最優(yōu)解為

27、：【解】（2）設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=C 則有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，從后向前依次有k3， 及最優(yōu)解 x3*=s3k2， 由 =4>0,故 x2=為極小值點(diǎn)。 因而有k1時(shí)， 由知 得到最優(yōu)解【解】(3) 設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=10 則有 x3= s3 ，0x2s2，0x1s1=10 用逆推法，從后向前依次有 k3時(shí)， 及最優(yōu)解 x3=s3 k2時(shí)， 而 。討論端點(diǎn)：當(dāng) x2=0時(shí), x2= s2時(shí) 如果s2>3時(shí), k1時(shí)， 同理有, x1=0, f1（s1）= s12= 100，x1=

28、 s1, f1（s1）= 2s1= 20 (舍去)得到最優(yōu)解【解】(4) 設(shè)s3=x3 ,2s3+4x2=s2，s2+x1=s1=10 則有 x3= s3 ，0x2s2/4，0x1s1=10 用逆推法，從后向前依次有 k1， 及最優(yōu)解 x3*=s3 k2， 由=s2-4x2=0,則 x2=s2 ,故 為極大值點(diǎn)。 則 及最優(yōu)解x2*=s2/8 k1， ，故 得到最優(yōu)解【解】(5) 按問題中變量的個(gè)數(shù)分為三個(gè)階段s1 ，s2 ，s3 ，且s310，x1，x2，x3為各階段的決策變量，各階段指標(biāo)函數(shù)相乘。設(shè)s1=2x1 , s1+4x2=s2，s2+x3=s310，則有 x1= s1/2 ，0x2

29、s2/4，0x3s3=10 用順推法，從前向后依次有 k1， 及最優(yōu)化解 x1*=s1/2 k2， 由,則 ,故 為極大值點(diǎn)。則 k3， 由故，由于s310，則s3=10時(shí)取最大值，x310/3，s2=s3x320/3，x25/6，s1=s24x210/3，x15/3 得到最優(yōu)解【解】（6）設(shè)s1=x1, s1+x2=s2，s2+x3=s3=8 k1， 及最優(yōu)化解 x1*=s1 k2，x2*=0時(shí)，f2（s2）=s22+2s2, x2*= s2時(shí)，f2（s2）=2s22故 k3，當(dāng)x2*=0時(shí)， 同樣得x3*=0時(shí) ，f3（s3）=s32+2s3 x3*=s3時(shí)，f3（s3）=s3 所以， f

30、3（s3）= s32+2s3=80 當(dāng)x2*= s2時(shí)，f3（s3）=x3+2（s3-x3）2同樣得x3*=0時(shí) ，f3（s3）=2s32 =128 x3*=s3時(shí)，f3（s3）=s3 =8 所以， f3（s3）= 2s32=128最優(yōu)解為8.4用動(dòng)態(tài)規(guī)劃求解下列線性規(guī)劃問題。【解】設(shè)s2=x2 ,s2+2x1=s16 則有 0x2=s24，0x1s1/2 用逆推法，從后向前依次有 及最優(yōu)解 x2*=s2 由 s2=s12x14， s16，取s16，又1x12，取x11， 最優(yōu)解 8.5 10噸集裝箱最多只能裝9噸，現(xiàn)有3種貨物供裝載，每種貨物的單位重量及相應(yīng)單位價(jià)值如表8.24所示。應(yīng)該如何

31、裝載貨物使總價(jià)值最大。表8.24貨物編號(hào)123單位加工時(shí)間234單位價(jià)值345【解】設(shè)裝載第I種貨物的件數(shù)為xi（ i =1,2,3）則問題可表為： 利用背包問題的前向動(dòng)態(tài)規(guī)劃計(jì)算，建立動(dòng)態(tài)規(guī)劃模型。由于決策變量離散型值，所以可用列表法求解。當(dāng)R=1時(shí)， 。計(jì)算結(jié)果如下：s20123456789f1（s2）003366991212x1*0011223344當(dāng)R=2時(shí)，f2（s3）=4x2+f1（s3-3x2）計(jì)算結(jié)果如下：s30123456789x20000101010120120120123C2+f2003346467978910812101112131112f2（s3）0034679101

32、213x2*0001010101當(dāng)R=3時(shí)，f3（9）=5x3+f2（9-4x3） （x3為整數(shù)）=f2（9），5+f2（5），10+f2（1）=max13，12，10=138.6 有一輛貨車載重量為10噸 ，用來裝載貨物A、B時(shí)成本分別為5元/噸和4元/噸?，F(xiàn)在已知每噸貨物的運(yùn)價(jià)與該貨物的重量有如下線性關(guān)系：A：P1=10-2x1 ，B：P2=12-3x2其中x1 、x2 分別為貨物A、B的重量。如果要求貨物滿載，A和B各裝載多少，才能使總利潤最大【解】將原題改為A：P1=15-x1 ，B：P2=18-2x2由題意可得各種貨物利潤函數(shù)為 原問題的數(shù)學(xué)模型歸結(jié)為最優(yōu)解：x1 =6，x2 =4；

33、z488.7 現(xiàn)有一面粉加工廠，每星期上五天班。生產(chǎn)成本和需求量見表8-25。表8-25星期(k)12345需求量(dk) 單位：袋1020253030每袋生產(chǎn)成本(ck)8691210面粉加工沒有生產(chǎn)準(zhǔn)備成本，每袋面粉的存儲(chǔ)費(fèi)為hk0.5元/袋，按天交貨，分別比較下列兩種方案的最優(yōu)性，求成本最小的方案。（1）星期一早上和星期五晚的存儲(chǔ)量為零，不允許缺貨，倉庫容量為S=40袋；（2）其它條件不變，星期一初存量為8?！窘狻縿?dòng)態(tài)規(guī)劃求解過程如下：階段k：日期，k=1,2,6狀態(tài)變量sk：第k天早上（發(fā)貨以前）的冷庫存量決策變量xk：第k天的生產(chǎn)量狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xkdk；決策允許集合

34、：階段指標(biāo)： vk(sk，xk)=ckxk+0.5sk終端條件：f6(s6)=0,s6=0；遞推方程：當(dāng)k=5時(shí)，因?yàn)閟6=0，有由于s515，k=4時(shí)， k=3時(shí)，當(dāng)0s430時(shí)，得 有當(dāng)30s440時(shí)，有顯然此決策不可行。當(dāng)k=2時(shí)，由x2的決策允許集合為當(dāng)k=1時(shí)，由，則x1的決策允許集合為因?yàn)?2)期初存儲(chǔ)量s1=8, 與前面計(jì)算相似，x1=2. Min Z=772.5+2.5x1-5s1=737.5 則總成本最小的方案是第二種。8.8 某企業(yè)計(jì)劃委派10個(gè)推銷員到4個(gè)地區(qū)推銷產(chǎn)品，每個(gè)地區(qū)分配14個(gè)推銷員。各地區(qū)月收益（單位：10萬元）與推銷員人數(shù)的關(guān)系如表826所示。表8-26 地

35、區(qū)人數(shù)ABCD1456727122024318232326424242730企業(yè)如何分配4個(gè)地區(qū)的推銷人員使月總收益最大?！窘狻吭O(shè)xk為第k種貨物的運(yùn)載重量，該問題的靜態(tài)規(guī)劃模型為利用圖表法：X1X2X3X4X5000830002632020631008027080024006230026028022435040436004444024232044032042225200630206027260027220433202434224029204231242022240223400431404027440019420219402220422018600225602024620023800024故最優(yōu)解為則 max Z=448.9 有一個(gè)車隊(duì)總共有車輛100輛，分別送兩批貨物去A