【正文】 51運(yùn)籌學(xué)(第2版) 習(xí)題答案運(yùn)籌學(xué)（第2版）習(xí)題答案2第1章 線性規(guī)劃 P36~40 第2章 線性規(guī)劃的對(duì)偶理論 P68~69第3章 整數(shù)規(guī)劃 P82~84第4章 目標(biāo)規(guī)劃 P98~100第5章 運(yùn)輸與指派問題 P134~136第6章 網(wǎng)絡(luò)模型 P164~165第7章 網(wǎng)絡(luò)計(jì)劃 P185~187第8章 動(dòng)態(tài)規(guī)劃 P208~210第9章 排隊(duì)論 P239~240第10章 存儲(chǔ)論 P269~270第11章 決策論 Pp297－298第12章 博弈論 P325~326全書360頁由于大小限制，此文檔只顯示第6章到第12章，第1章至第5章見《運(yùn)籌學(xué)課后答案1》習(xí)題六圖6－42－42所示，建立求最小部分樹的0－1整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻窟匸i，j]的長度記為cij，設(shè)數(shù)學(xué)模型為：圖6－43－43所示，建立求v1到v6的最短路問題的0－1整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻炕?i，j)的長度記為cij，設(shè)數(shù)學(xué)模型為：－43所示，建立求v1到v6的最大流問題的線性規(guī)劃數(shù)學(xué)模型?！窘狻?設(shè)xij為?。╥,j）的流量，數(shù)學(xué)模型為－41的最小部分樹。圖641（a）用破圈法,圖641（b）用加邊法。圖6－44【解】圖644（a），該題有4個(gè)解，最小樹長為22，其中一個(gè)解如下圖所示。圖644（b），最小樹長為20。最小樹如下圖所示。 某鄉(xiāng)政府計(jì)劃未來3年內(nèi)，對(duì)所管轄的10個(gè)村要達(dá)到村與村之間都有水泥公路相通的目標(biāo)。根據(jù)勘測(cè)，10個(gè)村之間修建公路的費(fèi)用如表620所示。鄉(xiāng)鎮(zhèn)府如何選擇修建公路的路線使總成本最低。表620兩村莊之間修建公路的費(fèi)用(萬元)1234567891012345678910【解】屬于最小樹問題。用加邊法，得到下圖所示的方案。－45中，求A到H、I的最短路及最短路長，并對(duì)圖(a)和(b)的結(jié)果進(jìn)行比較。 圖6－45【解】圖6－45(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ì)于圖6－45(b)：A到H的最短路PAH={A,C,G,F,H},最短路長21；A到I的最短路PAI={A,C,G,F,I},最短路長20；結(jié)果顯示有向圖與無向圖的結(jié)果可能不一樣。，也可以在每年年末賣掉重新購置新設(shè)備。、。使用時(shí)間在1～、。試確定一個(gè)設(shè)備更新策略，使5年的設(shè)備購置和維護(hù)總費(fèi)用最小?！窘狻吭O(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年年末。圖6－46－46是世界某6大城市之間的航線，邊上的數(shù)字為票價(jià)（百美元），用Floyd算法設(shè)計(jì)任意兩城市之間票價(jià)最便宜的路線表?！窘狻拷處熆衫媚０迩蠼猓篸ata\chpt6\L1　v1v2v3v4v5v6v10986v201051004v39100314v453012100v581001209v6641410090L2　v1v2v3v4v5v6v1086v2085134v380314v45309v581309v66414990L3　v1v2v3v4v5v6v1086v2085134v380312v45309v581309v66412990最優(yōu)票價(jià)表：　v1v2v3v4v5v6v1086v2085134v30312v409v509v60vv…、v6到各點(diǎn)的最優(yōu)路線圖分別為： 設(shè)圖6－46是某汽車公司的6個(gè)零配件加工廠，邊上的數(shù)字為兩點(diǎn)間的距離(km)?，F(xiàn)要在6個(gè)工廠中選一個(gè)建裝配車間。（1）應(yīng)選那個(gè)工廠使零配件的運(yùn)輸最方便。（2）、運(yùn)價(jià)為2元/噸公里。應(yīng)選那個(gè)工廠使總運(yùn)費(fèi)最小。【解】(1)　v1v2v3v4v5v6Maxv1086v2085134v38031212v453099v581309v6641299012選第1個(gè)工廠最好。(2)計(jì)算單件產(chǎn)品的運(yùn)價(jià)，見下表最后一行。計(jì)算單件產(chǎn)品的運(yùn)費(fèi)，見下表最后一列。　v1v2v3v4v5v6單件產(chǎn)品運(yùn)費(fèi)v1086v2085134v380312v45309v581309v66412990運(yùn)價(jià)1選第4個(gè)工廠最好。圖6－47 如圖6－47，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量?！窘狻拷o出初始流如下第一輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于5，如下圖所示調(diào)整流量。第二輪標(biāo)號(hào)：得到一條增廣鏈，調(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。 將3個(gè)天然氣田AAA3的天然氣輸送到2個(gè)地區(qū)CC2，中途有2個(gè)加壓站BB2，天然氣管線如圖6－48所示。輸氣管道單位時(shí)間的最大通過量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。圖6－48【解】虛擬一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)－1得到流量v＝22的最小費(fèi)用流，最小費(fèi)用為271。求解過程參看習(xí)題部分答案PPT文檔。－13最小費(fèi)用最大流如下圖，最大流量等于27，總費(fèi)用等于351。－46所示，（1）求解旅行售貨員問題；（2）求解中國郵路問題。圖646【解】（1）旅行售貨員問題。距離表C　1234561∞9862∞105∞43910∞314453∞12∞58∞12∞966414∞9∞在C中行列分別減除對(duì)應(yīng)行列中的最小數(shù)，得到距離表C1。距離表C1　1234561∞02∞61∞0347∞0011420∞∞5∞0∞960010∞∞由距離表C1，v1到v4， H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}, C(H1)=+3++9+4+=去掉第1行第四列，d41=∞，得到距離表C2。得到距離表C2　123562∞6∞0347∞0114∞20∞5∞0∞960010∞距離表C2的每行每列都有零，H2= H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}就是總距離最小的Hamilton回路，C(H1) =。(2)中國郵路問題。虛擬一條邊取回路H1＝{v1，v3，v4}，C(H1)=9+5+3=17,C(v1，v3)=9 C(H1)/2，調(diào)整回路。所有回路滿足最短回路的準(zhǔn)則，上圖是最短的歐拉回路，其中邊(v1, v4)和(v4, v3)各重復(fù)一次。習(xí)題七(1)分別用節(jié)點(diǎn)法和箭線法繪制表716的項(xiàng)目網(wǎng)絡(luò)圖，并填寫表中的緊前工序。(2) 用箭線法繪制表717的項(xiàng)目網(wǎng)絡(luò)圖，并填寫表中的緊后工序表716工序ABCDEFG緊前工序－－－AA、C－B、D、E、F緊后工序D,EGEGGG－表717工序ABCDEFGHIJKLM緊前工序BBA,BBD,GC,E,F,HD,GC,EIJ,K,L緊后工序FE,D,F,GI,KH,JI,KIH,JILMMM－【解】（1）節(jié)點(diǎn)圖：箭線圖：（2）節(jié)點(diǎn)圖：箭線圖：：（1）畫出網(wǎng)絡(luò)圖。（2）計(jì)算工序的最早開始、最遲開始時(shí)間和總時(shí)差。（3）找出關(guān)鍵路線和關(guān)鍵工序。表718工序ABCDEFG緊前工序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周。 表719給出了項(xiàng)目的工序明細(xì)表。表719工序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í)差和自由時(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í)差FA80891790B505