《管理運籌學》習題2解答

《管理運籌學》習題2一、分別用圖解法和單純形法（用大M法和兩階段法都可以）求解下列線性規(guī)劃問題：二、以下各模型目標函數(shù)都是求最大值，根據(jù)各自的最優(yōu)表下結(jié)論（要判斷解的類型）：（1）cj→-2-3-100-M-MCBXBB-1bx1x2x3x4x5x6x7-3-2x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5σj=cj-zj000-1/21/2-M+1/2-M+1/2（2）cj→101512000-MCBXBB-1bx1x2x3x4x5x6x7100-Mx1x3x73/23/31/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001σj=cj-zj0-43M/80+31/80-30/16-7M/16-3M/80+1/8-M0（3）cj→2-120-M0-M0-MCBXBB-1bx1x2x3x4x5x6x7x8x922-1x1x3x23/47/27/4100001010-1/4-1/2-1/41/41/21/43/8-1/4-1/8-3/81/41/81/81/4-3/8-1/8-1/43/8σj=cj-zj0005/4-M-3/4-3/8-M+3/8-9/8-M+9/8三、有三個發(fā)電站產(chǎn)地B1，B2，B3需要從兩個煤礦A1，A2購買煤炭，各自的產(chǎn)量、需求量以及每萬噸煤炭的運價（千元）如表1所示。問如何調(diào)運煤炭，使得總運輸費用最小？表1產(chǎn)銷平衡表和單位運價表發(fā)電站Bj煤礦AiB1B2B3產(chǎn)量（萬噸）A12362236A21577212每月對煤的需求量（萬噸）315要求：（1）請建立該問題的線性規(guī)劃模型，如果有必要再化為標準問題。（2）用表上作業(yè)法求解：用最小元素法確定初始方案；用閉回路法或者位勢法驗證初始方案是否最優(yōu)？如果非最優(yōu)，請用閉回路法調(diào)整，直至求出最優(yōu)方案。四、某工廠生產(chǎn)兩種產(chǎn)品。甲、乙兩種產(chǎn)品每件生產(chǎn)工時分別為6小時，2小時，總生產(chǎn)工時計劃定為24小時。甲產(chǎn)品和乙產(chǎn)品每生產(chǎn)一件對A原料消耗量都為1單位，原料A計劃購買量為5單位。乙產(chǎn)品每生產(chǎn)品一件對B原料的消耗為5單位，甲產(chǎn)品生產(chǎn)不需要B原料，該原料計劃購買量為5單位。要求依次滿足下列目標：（1）計劃工時數(shù)盡可能充分利用但最好不要超過；（2）原料A購買量最好不超過計劃規(guī)定量；（3）原料B購買量最好也不要超過計劃購買量。請建立該問題的線性目標規(guī)劃模型并用圖解法或單純型法求解?！豆芾磉\籌學》習題2解答一.分別用圖解法和單純形法求解下列線性規(guī)劃問題：x1≤2x1≤2x24321-1解：（一）用圖解法求解，過程如下：4321-11.各種約束條件如圖1所示，其中線段AB為x1-x2=1可行域。A點和B點坐標分別為(4/3,1/3)x1-x2=12.畫出目標函數(shù)的一條等值線：-2x1+4x2=0,如圖-2x1+4x2=0所示。它沿法線向下平移-2x1+4x2=0B3.當目標函數(shù)平移到A(4/3,1/3)點時，z→minz。BA所以本題有唯一最優(yōu)解X*＝(4/3,1/3)T，最優(yōu)目標Ax101234函數(shù)值z*=-2×4/3+4×1/3=-4/3。x101234(二)用單純形法求解（用大M法和兩階段法都可）4x14x1+2x2≥6[大M法求解]1.將原模型化為標準型（1）令y1=2-x1≥0，………③x2=y2-y3(其中y2,y3≥0)………③………④則x1＝2-y1………④將①、②代入原約束條件，并化簡整理得到：（2）在③式左邊加入松弛變量y4,化為：2y1-y2+y3+y4=1④式不用標準化,已經(jīng)是標準形式。（3）將①、②代入目標函數(shù)得：minz=-4+2y1+4y2-4y3+0·y4令w＝-z，則目標函數(shù)化為：maxw=4-2y1-4y2+4y3+0·y4所以，標準型即：………⑤………⑤2.在⑤式左邊加入人工變量y5，并在目標函數(shù)中加入罰因子M(M為很大的正數(shù))，則標準型化為規(guī)范型，如下所示：3.列單純形表求解，過程如下：cj→-2-440-MθiCBXBB-1by1y2y3y4y50-My4y511[2]1-111-110011/21σj=cj-zj-M-2+M-4+M4-M00-2-My1y51/21/210-1/2[3/2]1/2-3/21/2-1/201—1/3σj=cj-zj-1-1/2M0-5+3/2M5-3/2M1-1/2M0-2-4y1y22/31/310010-11/3-1/31/32/3——σj=cj-zj-8/3000-2/3-M+11/34.結(jié)論：因為所有非基變量檢驗數(shù)σj≤0(j=3,4,5)，且σ3=0,人工變量y5=0，所以上述規(guī)范型模型有無窮多最優(yōu)解，當前基可行解(2/3,1/3,0,0,0)T為最優(yōu)解（其他最優(yōu)解不能通過單純形法求出，∵）。相應的x*1＝2-y*1=2-2/3=4/3；x*2=y*2-y*3=1/3-0=1/3；minz=-maxw=-(-8/3+4)=-4/3。[用兩階段法求解]（接大M法第2步以后）第一階段：先列單純形表求解如下模型：cj→0000-1θiCBXBB-1by1y2y3y4y50-1y4y511[2]1-111-110011/21σj=cj-zj11-1000-1y1y51/21/210-1/2[3/2]1/2-3/21/2-1/201—1/3σj=cj-zj03/2-3/2-1/2000y1y22/31/310010-11/3-1/31/32/3——σj=cj-zj00000-1因為所有非基變量檢驗數(shù)σj≤0(j=3,4,5)，所以停止迭代，w=0，進入第二階段繼續(xù)求解。第二階段，去掉人工變量y5，恢復非人工變量目標系數(shù)，在以上最后一步基礎上繼續(xù)求解：cj→-2-440θiCBXBB-1by1y2y3y4-2-4y1y22/31/310010-11/3-1/3——σj=cj-zj-8/3000-2/34.結(jié)論同大M法第4步。二.以下各模型目標函數(shù)都是求最大值，根據(jù)各自的最優(yōu)表下結(jié)論（要判斷解的類型）：（1）cj→-2-3-100-M-MCBXBB-1bx1x2x3x4x5x6x7-3-2x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5σj=cj-zj000-1/21/2-M+1/2-M+1/2（2）cj→101512000-MCBXBB-1bx1x2x3x4x5x6x7100-Mx1x3x73/23/31/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001σj=cj-zj0-43M/80+31/80-30/16-7M/16-3M/80+1/8-M0（3）cj→2-120-M0-M0-MCBXBB-1bx1x2x3x4x5x6x7x8x922-1x1x3x23/47/27/4100001010-1/4-1/2-1/41/41/21/43/8-1/4-1/8-3/81/41/81/81/4-3/8-1/8-1/43/8σj=cj-zj0005/4-M-3/4-3/8-M+3/8-9/8-M+9/8解：（1）結(jié)論：因為所有非基變量檢驗數(shù)σj≤0(j=3,4,5,6,7)，σ3＝0且、人工變量x6＝x7＝0，所以有無窮多最優(yōu)解。以x3為進基變量繼續(xù)迭代，可求出另外一個最優(yōu)解。cj→-2-3-100-M-MθiCBXBB-1bx1x2x3x4x5x6x7-3-2x2x19/54/50110[3/5]-2/5-3/101/51/10-2/53/10-1/5-1/102/53—σj=cj-zj000-1/21/2-M+1/2-M+1/2-1-2x3x132015/32/310-1/201/6-1/31/20-1/61/3σj=cj-zj000-1/2-1/2-M+1/2-M+1/2所以，本題最優(yōu)解其中一個為：X1*=(4/5,9/5,0,0,0,0,0)T；另一個最優(yōu)解為：X2*=(2,3,0,0,0,0,0)T；maxz=-3×9/5-2×4/5=-1×3-2×2=-7（2）結(jié)論：因為所有非基變量檢驗數(shù)σj≤0(j=2,4,5,6)但人工變量x7=1/2≠0，所以此問題無可行解。（3）結(jié)論：非基變量檢驗數(shù)σ4＝5/4>0，而a/i4≤0(i=1,2,3)，故此問題無有限最優(yōu)解（或為無界解）。三、有三個發(fā)電站產(chǎn)地B1，B2，B3需要從兩個煤礦A1，A2購買煤炭，各自的產(chǎn)量、需求量以及每萬噸煤炭的運價（千元）如表1所示。問如何調(diào)運煤炭，使得總運輸費用最??？表1產(chǎn)銷平衡表和單位運價表發(fā)電站Bj煤礦AiB1B2B3產(chǎn)量（萬噸）A12362236A21577212每月對煤的需求量（萬噸）315要求：（1）請建立該問題的線性規(guī)劃模型，如果有必要再化為標準問題。（2）用表上作業(yè)法求解：用最小元素法確定初始方案；用閉回路法或者位勢法驗證初始方案是否最優(yōu)？如果非最優(yōu)，請用閉回路法調(diào)整，直至求出最優(yōu)方案。解：（1）設產(chǎn)地Ai（i=1,2）調(diào)運到銷地Bj（j=1,2,3）的煤炭為xij萬噸，可建立以下模型：（2）因為總產(chǎn)量8萬噸（=6+2）小于總需求量9萬噸（=3+1+5），所以本問題不是標準運輸問題。增加一個虛擬產(chǎn)地A3，它的單位運價c31=c32=c33=0，產(chǎn)量為9-8=1（萬噸）。（3）第一步：用最小元素法確定初始方案（方案可能有以下三種，隨著添加0位置不同而不同）?；蚧蚍椒ǘ悍駹柗ǎū绢}用此法求出的初始基可行解就是最優(yōu)解）方法三：西北角法第二步：求非基變量檢驗數(shù)，驗證初始方案(最小元素法求得的第一種初始方案)是否最優(yōu)。法一：用位勢法求檢驗數(shù)。求解見下表所示：銷地產(chǎn)地B1B2B3UiA10230620230A20152377621-8A300-39000-23Vj236223因為min(σ22,σ23,σ32,σ33|σij<0)=σ32=-39<0，所以初始方案并非最優(yōu)方案，需進一步調(diào)整，x32為進基變量。法二：用閉回路法求檢驗數(shù)σ22=77-15+23-62=23;σ23=21-15+23-23=6;σ33=0-0+23-23=0；σ32=0-0+23-62=-39（注：圖中畫出了非基變量x32的閉回路）；因為min(σ22,σ23,σ32,σ33|σij<0)＝σ32=-39<0，，所以初始方案并非最優(yōu)方案，需進一步調(diào)整，x32為進基變量。第三步：求θ值，調(diào)整初始方案。過程如下：以X32作為進基變量。調(diào)整量θ＝min(1,1)=1，按照左圖所示進行調(diào)整，選擇x31作為出基變量。方案調(diào)整后為方案二（注：另一個基可行解），如下：用位勢法可求出方案二非基變量檢驗數(shù)：銷地產(chǎn)地B1B2B3UiA10230620230A20152377621-8A339000390-62Vj236223因為非基變量檢驗數(shù)σ22,σ23,σ31,σ33>0，所以方案二就是唯一最優(yōu)方案。決策結(jié)論：產(chǎn)地A1向銷地B1調(diào)運煤炭1萬噸，向銷地B3調(diào)運煤炭5萬噸；產(chǎn)地A2向銷地B1調(diào)運煤炭2萬噸；銷地B2的需求量由虛擬產(chǎn)地A3來滿足，實際上它的需求量1萬噸完全未得到滿足。最小總運費=23×1+0×62+23×5+15×2+0×1=168（千元）。四、某工廠生產(chǎn)兩種產(chǎn)品。甲、乙兩種產(chǎn)品每件生產(chǎn)工時分別為6小時，2小時，總生產(chǎn)工時計劃定為24小時。甲產(chǎn)品和乙產(chǎn)品每生產(chǎn)一件對A原料消耗量都為1單位，原料A計劃購買量為5單位。乙產(chǎn)品每生產(chǎn)品一件對B原料的消耗為5單位，甲產(chǎn)品生產(chǎn)不需要B原料，該原料計劃購買量為5單位。要求依次滿足下列目標：（1）計劃工時數(shù)盡可能充分利用但最好不要超過；（2）原料A購買量最好不超過計劃規(guī)定量；（3）原料B購買量最好也不要超過計劃購買量。請建立該問題的線性目標規(guī)劃模型并用圖解法或單純型法求解。解：首先，建立該問題的線性目標規(guī)劃模型，如下：設甲、乙兩種產(chǎn)品的產(chǎn)量分別為x1、x2件。圖解法求解，如下圖所示：6x1+2x2=24D012345d+36x1+2x2=24D012345d+3d-3Cd-1d+1d-2d+2BA12108642x1x2x1+x2=55x2=5x2取值范圍、各約束條件表示在坐標系中，并用箭頭標出正負偏差變量增大方向。在各級目標實現(xiàn)之前，可行域為第一象限及及x1、x2的非負半軸。(2)對于第一級目標P1，要求min(d1-+d1+)，在線段AD上任一點都可滿足。(3)第二級目標P2，要求mind2+，可行域由線段AD縮小為線段BD。(4)第三級目標P3，要求mind3+，可行域由線段BD縮小為線段CD。即線段CD上任一點的坐標都可以全部滿足三級目標。C、D兩點坐標分別為（11/3,1）、（4,0）。但C點兩種原料的利用率最高，都盡可能接近計劃規(guī)定量（14/3,5）。因此，最優(yōu)解X*=λ(11/3,1)T+(1-λ)(4,0)T（注解：所有級別的目標都完全實現(xiàn)時，可以稱為最