1、運籌學課后習題參考答案（部分）第二章 線性規(guī)劃1、解：模型為： 2.提示：標準問題就是收發(fā)平衡問題。3.解：其標準形式為：4.標準形式為：5.提示：建立直角坐標系，用約束方程把可行域描述出來，在通過目標直線找到最優(yōu)解。6.提示：用凸集的定義。7.提示：（1）用數學歸納法先證明兩個凸集的交集是凸集，再證明任意多個凸集的交仍是凸集。(2)例8略9.不能構成可行基，因為此時對應的基本解為。10.11.略12.解：13.提示：14解：首先求出該問題對應的標準形式：寫出對應的單純形表：X1X2X3X4X5RHSZ210000X32510060X41101018X53100144選取x3x4x5為基變量，

2、此時檢驗數最大的對應x1，做出基入基變換得到下表X1X2X3X4X5RHSZ01/300-2/3-88/3X3013/310-2/332/3X402/301-1/310/3X111/300-/344/3在經過一次出基入基變換得到：X1X2X3X4X5RHSZ000-1/21/2-31X3001-13/23/2-11X20103/2-1/25X11001/21/213所以，原問題的最優(yōu)解為。15.略。16.（1）解原問題的標準形式為：Min S.t. 對應的單純型表為： RHS2 1 -1 0 0 0 03 1 1 1 0 0 -1 2 0 1 01 1 -1 0 0 1601020經過一次旋轉

3、變換之后得到： RHS0 3 5 0 -2 0 -200 4 -5 1 -3 01 -1 2 0 1 00 -3/2 0 -1/2 1/2301010在經過一次旋轉變換得到： RHS0 0 -1/2 0 -1/2 -3/2 -350 0 1 1 -1 -21 0 1/2 0 1/2 1/20 1 -3/2 0 -1/2 1/210155故最優(yōu)解為，最優(yōu)值為。（2）原問題已經是標準形式，其對應的單純形表為：X1X2X3X4RHSZ-3-1-1-10X3-22104X431016由于基變量對應的第零行元素非零，故不是檢驗數，整理得到X1X2X3X4RHSZ-220010X3-22104X43101

4、6進行一次旋轉變換得到： RHS0 0 -1 06-1 1 1/2 04 0 -1 124此時已經是檢驗數都是非正數，故已得到最優(yōu)解和最優(yōu)值。最優(yōu)解為：，最優(yōu)值為。（3）解：原問題已經是標準形式，其對應的單純形表為：X1X2X3X4X5X6X7RHSZ-111-10-1100X500301106X2012-100010X310000-100X400100116由于基變量對應的第零行元素非零，故不是檢驗數，整理得到X1X2X3X4X5X6X7RHSZ-110-31-110-10X500301106X2012-100010X310000-100X400100116由于檢驗數x4所對應的列元素均為非

5、正數，故此問題無界。17（1）解：先將問題標準化，得到：故先求輔助問題：其對應的單純形為X1X2X3X4X5X6X7X8RHSG0000000-10Z-3-4-2000000X51111100030X6361-201000X8010000-114經過計算可得輔助問題的最優(yōu)單純形表為：X1X2X3X4X5X6X7X8RHSG0000000-10Z-10-3/2-4/302/300-12X55/203/2011/24-414X2010000-114X4-3/20-1/210-1/2-3312得到了原問題的一個基本可行解，去掉輔助問題，再去掉添加的人工變量，應用單純形方法得到原問題的最優(yōu)解和最優(yōu)值為

6、：。（2）解：先將原問題標準化，得到：應用兩階段法求解，需要先求解以下輔助問題X1X2X3X4X5X6RHSG0000-1-10Z-2400000X52-1-10102X6-110-1013應用單純形方法，得到輔助問題對應的最優(yōu)單純形表為：X1X2X3X4X5X6RHSG0000-1-10Z0026-2-6-22X110-1-1115X201-1-2128得到了原問題的一個基本可行解，去掉輔助問題，再去掉添加的人工變量，應用單純形方法求解原問題，得到：X1X2X3X4RHSZ0026-22X110-1-15X201-1-28故原問題無解。（3）解：Min S.t. 研究輔助問題：Min S.t

7、. 輔助問題對應的單純型表為： RHS-4 -1 0 0 0 0 00 0 0 0 -1 -103 1 0 04 3 -1 01 2 0 11 00 10 0363計算輔助問題的最優(yōu)值： RHS-4 -1 0 0 0 0 07 4 -1 0 0 093 1 0 04 3 -1 01 2 0 11 00 10 0363經過一次旋轉變換得到： RHS0 1/3 0 0 1/3 0 40 5/3 -1 0 -7/3 021 1/3 0 00 5/3 -1 00 5/3 0 11/3 0-4/3 1-1/3 0122再次進行旋轉變換得到： RHS0 0 1/5 0 3/5 -1/518/50 0 0

8、0 -1 -101 0 1/5 00 1 1/5 00 0 1 13/5 -1/5-4/15 1/51 -13/52/50去掉輔助問題，得到原問題的一個基本可行解，應用單純型方法得： RHS0 0 0 -1/5 18/51 0 0 00 1 0 00 0 1 13/52/50得到原問題的最優(yōu)解為：，最優(yōu)值為：。（4）解：先將原問題標準化，得到：故所求問題的輔助問題為：其對應的單純形表為：X1X2X3X4X5X6RHSG0000-1-10Z2-45-6000X514-28102X6-1234011應用單純形方法求出輔助問題的最優(yōu)單純形表為：X1X2X3X4X5X6RHSG0000-1-10Z0-

9、123/30-1/623/2X510-8/301/3-10X601/21/1211/1201/4得到了原問題的一個基本可行解，去掉輔助問題，再去掉添加的人工變量，應用單純形方法求解原問題，得到原問題的最優(yōu)解和最優(yōu)值為：。18.（1）（2）（3）19.證明：給定一個一般形式的線性規(guī)劃問題：其對應的對偶問題為：則所給規(guī)劃的目標函數是上面兩個規(guī)劃的和，約束條件是上面兩個規(guī)劃的約束條件的交集。故由對偶理論可知當原始問題和對偶問題只有一個有解存在時所給問題無解。當原始問題和對偶問題都有解時所給問題有解，且此時目標函數值為零。20（1）將原問題化為標準型：其對應的單純形表為：X1X2X3X4RHSZ-10

10、-100X312015X101/2103經過計算可得最優(yōu)單純形表為：X1X2X3X4RHSZ-5/400-5/47/4X21/2101/25/2X1-1/401-1/47/4故最優(yōu)解和最優(yōu)值為：（2）對偶問題為：（3）互補松緊條件為，所以。21.解：該問題的對偶問題為：提示：用互補松緊條件證明。22.解：（1）原問題對應的標準型為：故其所對應的單純形表為：X1X2X3X4X5RHSZ-2-3-4000X4-1-2-110-3X5-21-301-4應用對偶單純形方法，得到新的單純形表：X1X2X3X4X5RHSZ0-4-10-14X40-5/21/21-1/2-1X11-1/23/20-1/22

11、再應用一次對偶單純形方法，得到最優(yōu)單純形表：X1X2X3X4X5RHSZ00-9/5-8/5-1/528/5X201-1/5-2/51/52/5X1107/5-1/5-2/511/5a所以原問題對應的最優(yōu)解和最優(yōu)值為：。（2）解：原問題對應的標準形式為：故其所對應的單純形表為：X1X2X3X4X5X6RHSZ-3-2-10000X41111006X5-101010-4X60-11001-3應用對偶單純形方法，得到新的單純形表：X1X2X3X4X5X6RHSZ0-2-40-3012X40121002X110-10-104X60-11001-3再應用一次對偶單純形方法，得到最優(yōu)單純形表：X1X2X

12、3X4X5X6RHSZ00-60-3-2-18X4003101-1X110-10-104X201-100-13此時，由于第一行的前n個數都是非負數，故原問題無解。（3）原問題對應的標準型為：故其所對應的單純形表為：X1X2X3X4X5X6RHSZ-2-3-5-6000X4-1-2-3-110-2X5-21-1301-3應用對偶單純形方法，得到新的單純形表：X1X2X3X4X5X6RHSZ0-4-4-90-13X40-5/2-5/2-5/21-1/2-1/2X11-1/21/2-3/20-1/23/2再應用一次對偶單純形方法，得到最優(yōu)單純形表：X1X2X3X4X5X6RHSZ000-5-8/5-

13、1/519/5X20111-2/51/51/5X1101-1-1/5-2/58/5所以原問題對應的最優(yōu)解和最優(yōu)值為：。23.解：（1）在20題的最優(yōu)單純形表中，由于是非基變量，故需要計算出新的檢驗數向量為：，將其代入20題的最優(yōu)單純形表中，得到：X1X2X3X4RHSZ100-5/47/4X21/2101/25/2X1-1/401-1/47/4再應用單純形方法，得到最優(yōu)單純形表如下：X1X2X3X4RHSZ0-20-9/4-13/4X112015X301/211/43故此時的最優(yōu)解和最優(yōu)值為：。（2）此時新的檢驗數向量為：，所以此時的最優(yōu)解不變，最優(yōu)值變?yōu)椋?。?）新的右端向量變?yōu)椋?4.（1

14、）最優(yōu)解和最優(yōu)值為：（2）25.略。第三章 整數線性規(guī)劃1.設A、B產品的生產量非別為件，該問題的數學模型為：2.設0-1變量表示其數學模型為：3.可行解集合為，最優(yōu)解，最優(yōu)值為。割平面法：先求出松弛問題的最優(yōu)單純形表如下表：4.5.證明：由3.2.9式得到：，又由于，兩式相減得到：由于，所以令結論成立。第四章 非線性規(guī)劃1.2.設產品A生產（百箱），產品B生產（百箱），則模型為：最優(yōu)解為。3.（1）整體最優(yōu)解為，最優(yōu)值為；（2）整體最優(yōu)解為，最優(yōu)值為；（3）整體最優(yōu)解為，最優(yōu)值為；4.提示：必要性：二次函數的Hesse矩陣為A，故由定理4.2.4可知，當A為正定矩陣時，二次函數為嚴格凸函數；

15、充分性：由于二次函數是嚴格凸函數，則由定理4.2.3可知：5.（1）函數的Hesse矩陣為正定矩陣，故此函數為嚴格凸函數。（2）函數的Hesse矩陣為負定矩陣，故此函數為嚴格凹函數。（3）函數的Hesse矩陣為正定矩陣，故此函數為嚴格凸函數。6.證明：設為任意可行解，對滿足條件的，對任意正數，為可行解。因為，且由于為可微凸函數，則又，所以故為可行解。而目標函數為，而，所以，當足夠大時，目標函數可以無限小。7.（1）目標函數的Hesse矩陣，由于，所以此矩陣為正定矩陣，又約束方程為凸函數方程，所以此規(guī)劃為凸規(guī)劃。存在最優(yōu)解，最優(yōu)解為。（2）目標函數為，所以其Hesse矩陣為，由于，所以正定，故目

16、標函數是嚴格凸函數，又約束方程為凸函數方程，所以此規(guī)劃為凸規(guī)劃。8.解：，則，所以當時取得最小值。9.解：01234a0.51.6461.6461.646b3.53.52.79182.3541.6462.3542.08372.3542.79182.354-0.7834-0.9609-0.96092.6497-1.938-0.9609換a換b換a換b換b此時，故此時已達到停止條件，所以。10.解：16 34427624.735685.4592145.074234.164514.8196.168744.01050.886084.757354.000311.12.解：我們有，并且，因為，令，選取新的

17、探索點：，并計算，故已同時滿足規(guī)則的兩個要求，停止迭代，得到非精確解。13.（反證法）證明：假設，不妨取，則：由于，所以，當t足夠小時成立，這與為局部最小點矛盾（因為）。14.（1）解：，令，得到：，由于Hesse矩陣為正定矩陣，故整體最優(yōu)解為。（2）解：，令，得到：，由于Hesse矩陣只有當時為正定矩陣，故該函數具有局部最優(yōu)解。15.解：由于函數的Hesse矩陣為，由定理4.4.4可知在點處Hesse矩陣，故當時正定。所以的取值范圍是。16.（1）解：，第一輪：，用一維搜索得到，第二輪：，用一維搜索得到，第三輪：，用一維搜索得到，。（2）解：，第一輪：，用一維搜索得到，第二輪：，用一維搜索得

18、到，第三輪：，用一維搜索得到，。17.提示：因為，所以，對任意點y0應用最速下降法第一輪都要取下降方向，用解析法計算出此時，故為最優(yōu)點。18.19.提示：沿著與共軛的方向前進。20.21.解：K-T條件為：22. 解：K-T條件為：經過討論可知最優(yōu)解為最優(yōu)值為。23. （1）解：該問題的lagrange函數是：故K-T條件為：作為K-T點，除了滿足上述條件，還要滿足。經過討論可知K-T點為，故該問題的最優(yōu)解為：（2）該問題的lagrange函數是：故K-T條件為：作為K-T點，除了滿足上述條件，還要滿足。經過討論可知K-T點為；。24.（1）解：和當時，。（2）解：當時，和當時，。（3）解：當

19、時，和當時，。第五章 動態(tài)規(guī)劃1.解：，；，；，；。所以最短路線為，最短路程為8.2.解：設則：3.解：4.解：。應用公式：得到最優(yōu)路線為：，最短路程為37。5.解：（方法同1題）應用以上遞推公式，可得：解得最短路線為：,最短路程為11.6.解：由題意可知，顯然都是凸函數 所以最優(yōu)決策為，總收益為2680。7.解：函數空間迭代法：首先構造函數：，即：，所以最短路線及路程為：函數空間迭代法：略。第六章 圖與網絡分析1.證明：充分性：由于G是簡單圖，則G沒有重邊和環(huán)，又完全圖任意兩個頂點之間都有邊連接，故邊數為。必要性：圖的邊數為,由于圖G是簡單圖，故G沒有重邊和環(huán)，所以圖G是完全圖。2.證明：（

20、反證法）假設圖中次為奇數的頂點為奇數個，則在該圖中必有某一條邊只有一個頂點，這和邊的定義不符，故次為奇數的頂點個數不能為奇數個。3.證明：設任意點集是完全圖G的一個非空點集，由于圖G是完全圖，則在圖G中任意兩點之間都有邊連接。由點導出子圖定義可知在中任意兩點之間都有邊連接，故該子圖一定是完全圖。4.證明：（反證法）假設圖中不存在回路，那么在圖中必定存在5.提示：6.證明：設次為1的頂點為s個，則此樹各頂點次的和，其中N為頂點個數，如果，則，這與樹的性質矛盾，故，也就是次為1的頂點至少有k個。7.最小樹如下：134528.提示：9. 2 4 3 1 3 2 2 4 1 6 3 5 2 4 510

21、. 2 4 3 1 3 2 2 4 1 6 3 5 2 4 511.最小費用流為。第七章 網絡計劃技術1.02648102.參見教科書P349.3.1234567891011最早時間2最晚時間12關鍵線路為：4.123456789最早時間20最晚時間20關鍵線路為：第八章 排隊論1.解：密度函數為：，所以：，。2.解：，3.提示：用條件概率分布公式。4.解：即，所以有（人/小時）。5.解：，。6.解：7.解： 8.解:系統的空閑概率、等待概率、等待隊長、隊長、等待時間、逗留時間都不小于系統。9.解：方案一的費用為萬，方案二的費用為萬，所以用方案二好。10.略。第九章 決策分析1.解：最大可能法：選擇一般加固。期望值法：， ，所以選擇一般加固。 效用函數法：，故選擇常規(guī)加固。2. 0.25 2000 3000 0.73 2000 0.02 52000 0.25 4000 4000 0.73 4000 0.02 4000 0.25 1500 2700 0.73 1500 0.02 61500 0.25 10000 3700 0.73 0 0.02 60000所以選擇方