運籌學部分課后習題解答

1、.妙單純形法:原問題化成標準型為max z=10X+5x23xt + 4x2 +x3 =9s.t.0Cjf10500qXpbEA：心兀0X3934100X4852015-Zj105000X321/5014/51-3/5108/512/501/55-z)010-25X23/2015/14-3/1410xl110-1/72/7335= 10xl+5x- = 2 2C廠Z、00-5/14-25/14所以有/=h |YP78已知線性規(guī)劃問題:max z = 2州 + 4x2 +x3+x4x, +3x2+x4 82州 +x2 6x2+x3 + x4 6x+x2 + x30求：寫出其對偶問題；(2)已知原

2、問題最優(yōu)解為=(224,0),試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：(1)該線性規(guī)劃問題的對偶問題為：min w = 8” + 6y2 + 6y3 + 9y43 j+2y2+y4 23)1+兒+兒+兒4兒+兒1開 +兒 1.兒,兒(2)由原問題最優(yōu)解為X=(2,2,4,0),根據(jù)互補松弛性得：必+2兒 +兒=2 3)1 + 比 + )3 + )4 = 4兒+九=1把x=(2,2,4,0)代入原線性規(guī)劃問題的約束中得第四個約束取嚴格不 等號，即 2 + 2 + 4 = 8y4=0X + 2兒=2從而有 24Xj +x2 + 3x3 4 3xpx2,Xj 0（1）寫出其對偶問題；（2）用對

3、偶單純形法求解原問題；解：（1）該線性規(guī)劃問題的對偶問題為：max w = 2y + 4y2 + 3兒3y +4y2 + 2兒 60、2y1+y2 + 2y3y+3y2+2兒 S80_（2）在原問題加入三個松弛變量勺,“，把該線性規(guī)劃問題化為標準型：max z = 一60片 一 40x2 一 80x33| 2x1 Aj + 耳=_2Xj x, 3Xj + 忑 =_40,; = !,6勺T-60-40-800005Xrb兀2V50V4-2-3-2-11000V5-4-4-1-30100忑-3-2-2-2001CjJ-60-40-800000V410-5/45/41-1/12080111/43/4

4、0-1/400-10-3/21-1/20-1/21CjJ0-25-350-150011/6005/311/3-5/6805/6102/30-1/31/640V22/3011/301/3-2/3700-80/30-20/3-50/3氣少5?730/=(|,f,0)z_=60x| + 40x + 80x0 = -o 3o33P81某廠生產(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) 品是否值得

5、生產(chǎn)（d）如果勞動力數(shù)量不增，材料不足時可從市場購買, 每單位 元。問該廠要不要購進原材料擴大生產(chǎn)，以購多少為宜。xrrr勞動力63545材料34530產(chǎn)品利潤（元/件）314解：由已知可得，設(shè)表示第丿種產(chǎn)品，從而模型為:max z = 3x+x2 + 4x36. +3x2 +5x3 453x + 4x2 + 5x3 0a）用單純形法求解上述模型為:勺-31400CbXrb州A：屯駐%04563510023034501C廠Z）314000153：-101-1463/54/5101/5C廠Z）3/5-11/500-4/53A151-1/301/3-1/343011-1/52/55-Zj0-20-

6、1/5-3/5得到最優(yōu)解為F =（5,0,3八 最優(yōu)值為z喚=3x5 + 4x3 = 27b）設(shè)產(chǎn)品A的利潤為3+幾，則上述模型中目標函數(shù)“的系數(shù)用3+2替代并求解得:C嚴3+久1400qXrbJ心勺X、351-1/301/3-1/343011-1/52/5c廠Z)2-20-1/5-3/5(q-zj0-2+2/30-1/5-2/3-3/5+2/3要最優(yōu)計劃不變，要求有如下的不等式方程組成立-2 + - 272所以產(chǎn)品D值得生產(chǎn)。d)P101已知運輸問題的產(chǎn)銷量與單位運價如下表所示，用表上作業(yè)法求各 題的最優(yōu)解及最小運費。表 3-35解：由已知和最小元素法可得初始方案為A3銷量 5151510檢

7、驗：BlB2B3別行位勢ALA2A31 2 Im 1 O | 4| 7 | 20迥O1613列位勢-111314由于有兩個檢驗數(shù)小于零，所以需調(diào)整，調(diào)整一:檢驗:進BlB2B3 M行位勢A1A2A3訓丘詛15門毎1 咚015 辿io訶 0164列位勢-21314由于還有檢驗數(shù)小于零，所以需調(diào)整，調(diào)整二:檢驗:進B1B2B3S4行位勢A15巴馬 101A210 915 21(+4)6A314爐08列位勢_611310從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：7 in =2x5 + 2x5 + 7x10 + 9x15 + 11x10 + 18x0 = 335表 3-36解：因為巧

8、=55,即產(chǎn)大于銷，所以需添加一個假想的銷地, 銷量為3,構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運費都為0。BlB2B3B4B5產(chǎn)量Al7793A2101315251A326銷量101020153檢驗:進BlB2 B3B4B5行位勢A17能1血創(chuàng)9創(chuàng)哲13B 155 34A31 2J10 -%3列位勢2 000-4從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：zmin = 6x9 + 5x1 + 3x10 + 1x7 + 4x13 + 3x15 + 0x3 = 193表 3-37解：因為巧=100,即銷大于產(chǎn)，所以需添加一個假想的產(chǎn)地, r-i；-1產(chǎn)量為20,構(gòu)成產(chǎn)銷平衡問題，其

9、對應(yīng)各銷地的單位運費都為0。立 hhB1B2B3B4B5產(chǎn)量A18637520A25M84730A36396830A40000020銷量2525201020檢驗:BlB2 B3 MB5行位勢A1A2A3A48j6 3J 20目 5勾 10 刃 15125 9包創(chuàng)電）創(chuàng)5 020 510創(chuàng)包）134-2列位勢2-1214由于有兩個檢驗數(shù)小于零，所以需調(diào)整，調(diào)整一:之wB1B2B3B4B5產(chǎn)量A120202010A225530A3501530A420銷量2525201020檢驗:進B1B2B3B4B5行位勢A18_3 201A25J20皿迪%3A36辭25創(chuàng)y6A40匕21。Oj 15-2列位勢2

10、-3212由于還有檢驗數(shù)小于零，所以需調(diào)整，調(diào)整二：Bl B2 B3 B4 B5 產(chǎn)量亦 llh、A1A2A3A4202030302020525010020銷量2525201020檢驗:逬11B2B3B4B5行位勢1如320勺同4A25 208折6 599A40201列位勢36-14-1從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：zmin = 3x20 + 5x20 + 4x10 + 6x5 + 3x25 + 8x0 + 0x20 + 0x0 = 305P127用割平面法求解整數(shù)規(guī)劃問題。max z = 7| +9x2 -x + S 6a)7X| +x2 0,且為整數(shù)解：該問題

11、的松弛問題為：max z = 7. +9x2 一召 + 3x2 6 7州 +x2 0則單純形法求解該松弛問題得最后一單純形表為:勺1790005Xrb為V2X、心X、9X27/2017/221/2207V19/210-1/223/2200-1/00-7/22-1/2212c廠Z)00-28/1-15/10119X23010017V132/1001/7-1/77011/0011/7-22/77= x.-3 x3 + 22 3 22 4 5從而有勺T7900qXpbxi*2心9X27/2017/221/227x9/210-1/223/22C廠Zj00-28/1-15/111割平面 1 為:(3 +

12、 1/2)=勺+( + 7/22)兀 + (0+1/22)耳1 71 .V, XA2 22 -22 4C廠Z,000-1-8割平面 2 為:(4 + 4/7) =召+(0 + 1/7)“+(-1+6/7)禺CL790003qXrbV2V3q七兀9X230100107xx32/1001/7-1/707011/0011/7-22/0770應(yīng)-4/000-1/-6/7177000-1-809*23010010741000-11010010-410400016-7C廠Z）0000-2-7由上表可知該問題已經(jīng)達到整數(shù)解了，所以該整數(shù)解就是原問題的最優(yōu) 解,即/=（4,3）最優(yōu)值為仏=7x4 + 9x3

13、= 55P144用圖解分析法求目標規(guī)劃模型min Z = Px 4+ P2 g+ Ps （2苗+ldT）c）廠Xi + X2 + d； - d；= 40Xi + X2 + 血- = 40+10=50.X1 + 苗-&= 24X2 + & - &二 30x,、X2、d：、&、底、&、（t、&、広 N 0解：由下圖可知，滿足目標函數(shù)的滿意解為圖中的A點。P170求下圖中的最小樹解：避圈法為:(1) = % = (A,幼耳= (C,D,E,F,G,咼(4) = (A,B,Gfa) = (D,Er FtH(5) % = CtD) y2 = F, H)(6) 眄工4R,G,U, DE,眄二兄丹 %=幾及

14、G,C,D,E,H)% = (F(8) HG6D,艮玖咼耳=得到最小樹為:P171用標號法求下圖中點兒到各點的最短路。P 173用Ford-Fulkerson的標號算法求下圖中所示各容量網(wǎng)絡(luò)中從人到 兒的最大流，并標出其最小割集。圖中各弧旁數(shù)字為容量括弧中為流 量人B)/5(4) X1CD5(5)r 3(2) V32(2) 5(2) /V5(5)1(1)解：對上有向圖進行2F標號得到(055(5)2(2)5G)也仏1)%,1)5C2J1(1)2(2)4 43(3)由于所有點都被標號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整由圖可知，標號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量, 最小割為與直線KK相交的弧的集合，即為（匕必），（兒），（匕*5）心）“2沱）,“巴）所以從兒到的最大流為：/： =1 + 2 + 5 + 3 + 2 + 1 = 14C)解：對上有向圖進行2F標號得到由于所有點都被標號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整由圖可知，標號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量, 最小割為與直線KK相交的弧的集合，即為（匕,U）,（f）（卩2*5），所以從兒到氣的最大流為：/： =5 + 3 + 5 =