運(yùn)籌學(xué)課后習(xí)題

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

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

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在經(jīng)過(guò)一次旋轉(zhuǎn)變換得到： 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）原問(wèn)題已經(jīng)是標(biāo)準(zhǔn)形式，其對(duì)應(yīng)的單純形表為：X1X2X3X4RHSZ-3-1-1-10X3-22104X431016由于基變量對(duì)應(yīng)的第零行元素非零，故不是檢驗(yàn)數(shù)，整理得到X1X2X3X4RHSZ-220010X3-22104X43101

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

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

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

7、. 輔助問(wèn)題對(duì)應(yīng)的單純型表為： 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計(jì)算輔助問(wèn)題的最優(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經(jīng)過(guò)一次旋轉(zhuǎn)變換得到： 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再次進(jìn)行旋轉(zhuǎn)變換得到： 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去掉輔助問(wèn)題，得到原問(wèn)題的一個(gè)基本可行解，應(yīng)用單純型方法得： RHS0 0 0 -1/5 18/51 0 0 00 1 0 00 0 1 13/52/50得到原問(wèn)題的最優(yōu)解為：，最優(yōu)值為：。（4）解：先將原問(wèn)題標(biāo)準(zhǔn)化，得到：故所求問(wèn)題的輔助問(wèn)題為：其對(duì)應(yīng)的單純形表為：X1X2X3X4X5X6RHSG0000-1-10Z2-45-6000X514-28102X6-1234011應(yīng)用單純形方法求出輔助問(wèn)題的最優(yōu)單純形表為：X1X2X3X4X5X6RHSG0000-1-10Z0-

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

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

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

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

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

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

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

16、標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，又約束方程為凸函數(shù)方程，所以此規(guī)劃為凸規(guī)劃。8.解：，則，所以當(dāng)時(shí)取得最小值。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此時(shí)，故此時(shí)已達(dá)到停止條件，所以。10.解：16 34427624.735685.4592145.074234.164514.8196.168744.01050.886084.757354.000311.12.解：我們有，并且，因?yàn)?，令，選取新的

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

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

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

20、反證法）假設(shè)圖中次為奇數(shù)的頂點(diǎn)為奇數(shù)個(gè)，則在該圖中必有某一條邊只有一個(gè)頂點(diǎn)，這和邊的定義不符，故次為奇數(shù)的頂點(diǎn)個(gè)數(shù)不能為奇數(shù)個(gè)。3.證明：設(shè)任意點(diǎn)集是完全圖G的一個(gè)非空點(diǎn)集，由于圖G是完全圖，則在圖G中任意兩點(diǎn)之間都有邊連接。由點(diǎn)導(dǎo)出子圖定義可知在中任意兩點(diǎn)之間都有邊連接，故該子圖一定是完全圖。4.證明：（反證法）假設(shè)圖中不存在回路，那么在圖中必定存在5.提示：6.證明：設(shè)次為1的頂點(diǎn)為s個(gè)，則此樹(shù)各頂點(diǎn)次的和，其中N為頂點(diǎn)個(gè)數(shù)，如果，則，這與樹(shù)的性質(zhì)矛盾，故，也就是次為1的頂點(diǎn)至少有k個(gè)。7.最小樹(shù)如下：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.最小費(fèi)用流為。第七章 網(wǎng)絡(luò)計(jì)劃技術(shù)1.02648102.參見(jiàn)教科書(shū)P349.3.1234567891011最早時(shí)間2最晚時(shí)間12關(guān)鍵線路為：4.123456789最早時(shí)間20最晚時(shí)間20關(guān)鍵線路為：第八章 排隊(duì)論1.解：密度函數(shù)為：，所以：，。2.解：，3.提示：用條件概率分布公式。4.解：即，所以有（人/小時(shí)）。5.解：，。6.解：7.解： 8.解:系統(tǒng)的空閑概率、等待概率、等待隊(duì)長(zhǎng)、隊(duì)長(zhǎng)、等待時(shí)間、逗留時(shí)間都不小于系統(tǒng)。9.解：方案一的費(fèi)用為萬(wàn)，方案二的費(fèi)用為萬(wàn)，所以用方案二好。10.略。第九章 決策分析1.解：最大可能法：選擇一般加固。期望值法：， ，所以選擇一般加固。 效用函數(shù)法：，故選擇常規(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所以選擇方