運(yùn)籌學(xué)部分課后習(xí)題解答 1

1、運(yùn)籌學(xué)部分課后習(xí)題解答P47 1.1用圖解法求解線性規(guī)劃問題min z=2 x13x2a4x16x26）2x2st. 4x14x1, x20解：由圖 1 可知，該問題的可行域?yàn)橥辜?MABCN，且可知線段 BA上的點(diǎn)都為最優(yōu)解，即該問題有無窮多最優(yōu)解，這時的最優(yōu)值為3zmin =23 0 32P47 1.3用圖解法和單純形法求解線性規(guī)劃問題max z=10x15x 2a）3x14x29s.t 5x12x28x1, x20解：由圖 1 可知，該問題的可行域?yàn)橥辜疧ABCO，且可知 B 點(diǎn)為最優(yōu)值點(diǎn)，3x14x29x1 1T3 ，即最優(yōu)解為 x*3即2x281,5x1x222這時的最優(yōu)值為 zma

2、x =1015 33522單純形法：原問題化成標(biāo)準(zhǔn)型為max z=10x 15x 23x14x2x39s.t5x12x2x48x1 , x2 , x3 , x40c j10500CBX Bbx1x2x3x40x3934100x485201C jZ j105000x321/5014/51-3/510x18/512/501/5C jZ j010-25x23/2015/14-3/1410x1110-1/72/7C jZ j00-5/14-25/141,3T1015335所以有 x*, zmax222P78 2.4已知線性規(guī)劃問題：maxz2 x14x2x3 x4x13x2x482x1x26x2x3x

3、46x1x2x39x1 , x2 , x3, x40求: (1)寫出其對偶問題；（2）已知原問題最優(yōu)解為 X *( 2,2,4,0) ，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：（ 1）該線性規(guī)劃問題的對偶問題為：minw8y16 y26 y3 9 y4y12 y2y423y1y2y3y44y3y41y1y31y1, y2 , y3 , y40（2）由 原問題最優(yōu)解為 X *(2,2,4,0) ，根據(jù)互補(bǔ)松弛性得：y12 y2y423 y1y2y3y44y3y41把 X *(2,2,4,0)代入原線性規(guī)劃問題的約束中得第四個約束取嚴(yán)格不等號，即22489y40y12 y22從而有3 y1y

4、2y34y31得 y1 4 , y23, y3 1, y4055所以對偶問題的最優(yōu)解為y*( 4 , 3 ,1,0) T ，最優(yōu)值為 wmin 1655P79 2.7考慮如下線性規(guī)劃問題：minz60x140 x280x33x12x2x324x1x23x342x12 x22x33x1, x2 , x30（ 1）寫出其對偶問題；（ 2）用對偶單純形法求解原問題；解：（ 1）該線性規(guī)劃問題的對偶問題為：maxw2 y14 y2 3y33y14 y22 y3602 y1y22y340y13y22y380y1, y2 , y30（2）在原問題加入三個松弛變量x4 , x5 , x6 把該線性規(guī)劃問題化

5、為標(biāo)準(zhǔn)型：max z60x140x280x33x12x2x3x424x1x23x3x542 x12 x22 x3x63x j0, j1,6c j-60-40-80000CBX Bbx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x6-3-2-2-2001C jZ j-60-40-800000x410-5/45/41-1/12080x1111/43/40-1/400x6-10-3/2-1/20-1/21C jZ j0-25-350-1500x411/6005/311/3-5/680x15/6102/30-1/31/640x22/3011/301/3-2/3C j

6、Z j00-80/30-20/3-50/3x*(5,2,0) T , zmax60540280 023063633P81 2.12某廠生產(chǎn) A、B、C 三種產(chǎn)品，其所需勞動力、材料等有關(guān)數(shù)據(jù)見下表。要求：（ a）確定獲利最大的產(chǎn)品生產(chǎn)計劃； （b）產(chǎn)品 A 的利潤在什么范圍內(nèi)變動時，上述最優(yōu)計劃不變； （c）如果設(shè)計一種新產(chǎn)品D，單件勞動力消耗為8 單位，材料消耗為 2 單位，每件可獲利 3 元，問該種產(chǎn)品是否值得生產(chǎn)？（d）如果勞動力數(shù)量不增，材料不足時可從市場購買，每單位0.4 元。問該廠要不要購進(jìn)原材料擴(kuò)大生產(chǎn)，以購多少為宜。消耗產(chǎn)品ABC可用量（單位）定額資源勞動力63545材料345

7、30產(chǎn)品利潤（元 / 件）314解：由已知可得，設(shè)xj 表示第 j 種產(chǎn)品，從而模型為：max z3x1x24x36x13x25x345st.3x14x25x330x1 , x2 , x30a) 用單純形法求解上述模型為：31400c jCBXBbx1x2x3x4x504563510x403034501x5C jZ j314000153-101-1x4463/54/5101/5x3C jZ j3/5-11/500-4/5351-1/301/3-1/3x143011-1/52/5x3C jZ j0-20-1/5-3/5得到最優(yōu)解為 x*(5,0,3)T；最優(yōu)值為 zmax35 4 327b ）設(shè)

8、產(chǎn)品 A 的利潤為 3，則上述模型中目標(biāo)函數(shù)x1 的系數(shù)用 3替代并求解得：c j31400CBX Bbx1x2x3x4x53x151-1/301/3-1/34x33011-1/52/5C jZ j-20-1/5-3/5C jZ j0-2+/30-1/5-/3-3/5+/3要最優(yōu)計劃不變，要求有如下的不等式方程組成立2 0310解得：3955533053從而產(chǎn)品 A 的利潤變化范圍為： 33 ,39,即 22,445555C）設(shè)產(chǎn)品 D 用 x6 表示，從已知可得6c6 cB B 1P61/ 51182P6'B 1P6334212555把 x6加入上述模型中求解得：c j314003C

9、BXBbx1x2x3x4x5x63x151-1/301/3-1/324x33011-1/52/5-4/5C jZ j0-20-1/5-3/51/53x65/21/2-1/601/6-1/614x352/513/151-1/154/150C jZ j-1/10-59/300-7/30-17/300從而得最優(yōu)解 x*(0,0,5,0,0,5/2)T ；最優(yōu)值為 zmax453527.5 272所以產(chǎn)品 D 值得生產(chǎn)。d）P101 3.1已知運(yùn)輸問題的產(chǎn)銷量與單位運(yùn)價如下表所示，用表上作業(yè)法求各題的最優(yōu)解及最小運(yùn)費(fèi)。表 3-35銷地B1B 2B3B4產(chǎn)量產(chǎn)地A 1102201115A 2127920

10、25A 321416185銷量5151510解：由已知和最小元素法可得初始方案為銷地B1B2B3B4產(chǎn)量產(chǎn)地A11515A20151025A3505銷量5151510檢驗(yàn)：由于有兩個檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：銷地B1B2B3B4產(chǎn)量產(chǎn)地A11515A20151025A3505銷量5151510檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：銷地B1B2B3B4產(chǎn)量產(chǎn)地A151015A2101525A3505銷量5151510檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為： zmin25257109 1511 1018 0335表 3-36銷地B1B 2B3B4產(chǎn)量產(chǎn)地

11、A 184127A 2694725A 3534326銷量1010201534解：因?yàn)閍i 58bj55 ，即產(chǎn)大于銷，所以需添加一個假想的銷地，銷i 1j 1量為 3，構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運(yùn)費(fèi)都為0。銷地B1B2B3B4B5產(chǎn)量產(chǎn)地A1841207A26947025A35343026銷量101020153由上表和最小元素法可得初始方案為銷地B1B2B3B4B5產(chǎn)量產(chǎn)地A177A2913325A31101526銷量101020153檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為： zmin6 95 13 10174 133 1503193表 3-37銷地B1B2

12、B3B4B5產(chǎn)量產(chǎn)地A18637520A25M84730A36396830銷量252520102035解：因?yàn)閍i80bj100 ，即銷大于產(chǎn)，所以需添加一個假想的產(chǎn)地，產(chǎn)i1j1量為 20，構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運(yùn)費(fèi)都為0。銷地B1B2B3B4B5產(chǎn)量產(chǎn)地A18637520A25M84730A36396830A40000020銷量2525201020由上表和最小元素法可得初始方案為銷地B1B2B3B4B5產(chǎn)量產(chǎn)地A12020A25101530A325530A420020銷量2525201020檢驗(yàn)：由于有兩個檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：銷地B1B2B3B4B5產(chǎn)量產(chǎn)地A1

13、2020A2201030A325530A4501520銷量2525201020檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：銷地B1B2B3B4B5產(chǎn)量產(chǎn)地A12020A2201030A3525030A402020銷量2525201020檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為： zmin3 205 204 1065325800200 0305P127 4.8用割平面法求解整數(shù)規(guī)劃問題。max z7x19x2a）x13x267 x1x235x1, x20, 且為整數(shù)解：該問題的松弛問題為：max z7x19x2x13x267x1x235x1, x20則單純形法求解該松

14、弛問題得最后一單純形表為：c j7900CBX Bbx1x2x3x49x27/2017/221/227x19/210-1/223/22C jZ j00-28/11-15/11割平面 1 為： (31/ 2)x2(07/ 22)x3(0 1/ 22) x41 7 x31 x4x23 07 x31 x4 x512222222222c jCB970C j970C j從而有79000X Bbx1x2x3x4x5x27/2017/221/220x19/210-1/223/220x5-1/200-7/22-1/221Z j00-28/11-15/110x2301001x132/71001/7-1/7x31

15、1/70011/7-22/7Z j000-1-8割平面 2 為： (44/ 7)x1 (01/ 7) x4( 1 6/ 7) x541616477 x47 x5x1x54 07 x47 x5x67c j790003CBX Bbx1x2x3x4x5x693010010x2732/71001/7-1/70x1011/70011/7-22/70x30-4/7000-1/7-6/71x6C jZ j000-1-8093010010x2741000-11x1010010-41x30400016-7x4C jZ j0000-2-7由上表可知該問題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問題的最優(yōu)解，即x*T4

16、,3 ，最優(yōu)值為 zmax 7 4 9 3 55P144 5.3用圖解分析法求目標(biāo)規(guī)劃模型min Z = P1 d 1-+ P2d 2+ P3（ 2d 3- +1d4-）c）- d1+x1 + x 2 + d 1= 40x1 + x 2 + d 2- - d2+= 40+10=50s.t.x1-+ d 3- d 3 = 24x 2 + d 4- - d4+= 30x1 、 x2 、 d1 +、 d 1-、 d2+、 d 2- 、d 3+、d 3 - 、 d4+、 d 4- 0解 : 由下圖可知，滿足目標(biāo)函數(shù)的滿意解為圖中的A 點(diǎn)。P170 6.4求下圖中的最小樹解：避圈法為：得到最小樹為：P1

17、71 6.7用標(biāo)號法求下圖中點(diǎn)v1 到各點(diǎn)的最短路。解：如下圖所示：P 173 6.14 用 Ford-Fulkerson 的標(biāo)號算法求下圖中所示各容量網(wǎng)絡(luò)中從 vs 到 vt 的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量 cij ，括弧中為流量 fij .B)解：對上有向圖進(jìn)行2F 標(biāo)號得到由于所有點(diǎn)都被標(biāo)號了， 即可以找到增廣鏈， 所以流量還可以調(diào)整， 調(diào)整量為 1，得由圖可知，標(biāo)號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小割為與直線 KK 相交的弧的集合，即為(vs, v3 ),( vs , v4 ),( vs , v5 ),( v1 ,vt ),( v2 ,vt ),( v2, v3 )所以從 vs 到 vt 的最大流為：fst*12532114C)解：對上有向圖進(jìn)行2F 標(biāo)號得到由于所有點(diǎn)都被標(biāo)號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整量為1，得由圖可知， 標(biāo)號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小割為與直線KK相交的弧的集合，即為(vs ,v1 ), (vs ,v3 ),v(2 v,5