運籌學 線性規(guī)劃在管理中的應用案例

1、第五章 線性規(guī)劃在管理中的應用5.1 某企業(yè)停止了生產(chǎn)一些已經(jīng)不再獲利的產(chǎn)品，這樣就產(chǎn)生了一部分剩余生產(chǎn)力。管理層考慮將這些剩余生產(chǎn)力用于新產(chǎn)品、的生產(chǎn)?？捎玫臋C器設備是限制新產(chǎn)品產(chǎn)量的主要因素，具體數(shù)據(jù)如下表：機器設備類型每周可用機器臺時數(shù)銑床500車床350磨床150每生產(chǎn)一件各種新產(chǎn)品需要的機器臺時數(shù)如下表： 機器設備類型新產(chǎn)品新產(chǎn)品新產(chǎn)品銑床846車床430磨床301三種新產(chǎn)品的單位利潤分別為0.5元、0.2元、0.25元。目標是要確定每種新產(chǎn)品的產(chǎn)量，使得公司的利潤最大化。1、判別問題的線性規(guī)劃數(shù)學模型類型。2、描述該問題要作出決策的目標、決策的限制條件以及決策的總績效測度。3、建立

2、該問題的線性規(guī)劃數(shù)學模型。4、用線性規(guī)劃求解模型進行求解。5、對求得的結(jié)果進行靈敏度分析（分別對最優(yōu)解、最優(yōu)值、相差值、松馳/剩余量、對偶價格、目標函數(shù)變量系數(shù)和常數(shù)項的變化范圍進行詳細分析）。6、若銷售部門表示，新產(chǎn)品、生產(chǎn)多少就能銷售多少，而產(chǎn)品最少銷售18件，請重新完成本題的1-5。解：1、本問題是資源分配型的線性規(guī)劃數(shù)學模型。2、該問題的決策目標是公司總的利潤最大化，總利潤為： 0.5x1+ 0.2x2+ 0.25x3 決策的限制條件： 8x1+ 4x2+ 6x3500 銑床限制條件4x1+ 3x2 350 車床限制條件3x1 + x3150 磨床限制條件 即總績效測試（目標函數(shù)）為：

3、 max z= 0.5x1+ 0.2x2+ 0.25x33、本問題的線性規(guī)劃數(shù)學模型 max z= 0.5x1+ 0.2x2+ 0.25x3 ST 8x1+ 4x2+ 6x3500 4x1+ 3x2 350 3x1 + x3150 x10、x20、x304、用Excel線性規(guī)劃求解模板求解結(jié)果：最優(yōu)解（50，25，0），最優(yōu)值：30元。5、靈敏度分析目標函數(shù)最優(yōu)值為 : 30 變量 最優(yōu)解 相差值 x1 50 0 x2 25 0 x3 0 .083 約束 松弛/剩余變量 對偶價格 1 0 .05 2 75 0 3 0 .033 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 x1 .4 .5

4、無上限 x2 .1 .2 .25 x3 無下限 .25 .333 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 1 400 500 600 2 275 350 無上限 3 37.5 150 187.5（1） 最優(yōu)生產(chǎn)方案： 新產(chǎn)品生產(chǎn)50件、新產(chǎn)品生產(chǎn)25件、新產(chǎn)品不安排。最大利潤值為30元。（2）x3 的相差值是0.083意味著，目前新產(chǎn)品不安排生產(chǎn)，是因為新產(chǎn)品的利潤太低，若要使新產(chǎn)品值得生產(chǎn)，需要將當前新產(chǎn)品利潤0.25元/件，提高到0.333元/件。（3）三個約束的松弛/剩余變量0，75，0，表明銑床和磨床的可用工時已經(jīng)用完，而車床的可用工時還剩余75個工時； 三個對偶價格0.05，0，

5、0.033表明三種機床每增加一個工時可使公司增加的總利潤額。（4）目標函數(shù)系數(shù)范圍 表明新產(chǎn)品的利潤在0.4元/件以上，新產(chǎn)品的利潤在0.1到0.25之間，新產(chǎn)品的利潤在0.333以下，上述的最佳方案不變。（5）常數(shù)項范圍 表明銑床的可用條件在400到600工時之間、車銑床的可用條件在275工時以上、磨銑床的可用條件在37.5到187.5工時之間。各自每增加一個工時對總利潤的貢獻0.05元，0元，0.033元不變。6、若產(chǎn)品最少銷售18件，修改后的的數(shù)學模型是：max z= 0.5x1+ 0.2x2+ 0.25x3 ST 8x1+ 4x2+ 6x3500 4x1+ 3x2 350 3x1 +

6、x3150x318 x10、x20、x30這是一個混合型的線性規(guī)劃問題。代入求解模板得結(jié)果如下：最優(yōu)解（44，10，18），最優(yōu)值：28.5元。靈敏度報告：目標函數(shù)最優(yōu)值為 : 28.5 變量 最優(yōu)解 相差值 x1 44 0 x2 10 0 x3 18 0 約束 松弛/剩余變量 對偶價格 1 0 .05 2 144 0 3 0 .033 4 0 -.083 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 x1 .4 .5 無上限 x2 .1 .2 .25 x3 無下限 .25 .333 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 1 460 500 692 2 206 350 無上限 3 18

7、 150 165 4 0 18 30（1） 最優(yōu)生產(chǎn)方案：新產(chǎn)品生產(chǎn)44件、新產(chǎn)品生產(chǎn)10件、新產(chǎn)品生產(chǎn)18件。最大利潤值為28.5元。（2）因為最優(yōu)解的三個變量都不為0，所以三個相關(guān)值都為0。（3）四個約束的松弛/剩余變量0，144，0，0，表明銑床和磨床的可用工時已經(jīng)用完，新產(chǎn)品的產(chǎn)量也剛好達到最低限制18件，而車床的可用工時還剩余144個工時；四個對偶價格0.05，0，0.033，-0.083表明三種機床每增加一個工時可使公司增加的總利潤額，第四個對偶價格-0.083表明新產(chǎn)品的產(chǎn)量最低限再多規(guī)定一件，總的利潤將減少0.083元。（4）目標函數(shù)系數(shù)范圍表明新產(chǎn)品的利潤在0.4元/件以上，

8、新產(chǎn)品的利潤在0.1到0.25之間，新產(chǎn)品的利潤在0.333以下，上述的最佳方案不變。（5）常數(shù)項范圍表明銑床的可用條件在460到692工時之間、車銑床的可用條件在206工時以上、磨銑床的可用條件在18到165工時之間、新產(chǎn)品產(chǎn)量限制在30件以內(nèi)。各自每增加一個工時對總利潤的貢獻0.05元，0元，0.033元，-.083元不變。5.2 某銅廠軋制的薄銅板每卷寬度為100cm，現(xiàn)在要在寬度上進行切割以完成以下訂貨任務：32cm的75卷，28cm的50卷，22cm的110卷，其長度都是一樣的。問應如何切割可使所用的原銅板為最少？解：本問題是一個套材下料問題，用窮舉法找到所有可能切割的方式并建立數(shù)學

9、模型：min f=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10 S.T. 3x1+2x2+2x3+x4+x5+x675 x2+2x4+x6+3x7+2x8+x950 x3+3x5+x6+2x8+3x9+4x10 110 xi0 （i=1，2.10） 用Excel線性規(guī)劃求解模型板求解： 最優(yōu)解：（18.33 ,0,0,0,20,0,0.25,0,0,0），最優(yōu)值：63.3333 因為銅板切割時必須整卷切割所以需要做整數(shù)近似。即其結(jié)果為： 即最優(yōu)解：（19 ,0,0,0,20,0,0.25,0,0,0），最優(yōu)值：64靈敏度分析報告：目標函數(shù)最優(yōu)值為 : 63.333 變量 最優(yōu)解

10、 相差值 x1 18.333 0 x2 0 .056 x3 0 .111 x4 0 .111 x5 20 0 x6 0 .167 x7 0 .167 x8 25 0 x9 0 .056 x10 0 .111 約束 松弛/剩余變量 對偶價格 1 0 -.333 2 0 -.278 3 0 -.222 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 x1 .75 1 1.071 x2 .944 1 無上限 x3 .889 1 無上限 x4 .889 1 無上限 x5 .833 1 1.083 x6 .833 1 無上限 x7 .833 1 無上限 x8 .444 1 1.111 x9 .944 1

11、 無上限 x10 .889 1 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 1 20 75 無上限 2 0 50 110 3 50 110 275這是一個統(tǒng)計型的線性規(guī)劃問題，所以分析價值系數(shù)的取值范圍和相差都沒有意義。松弛/剩余變量都為0，表示最優(yōu)方案已達到三種規(guī)格薄銅板數(shù)量的最低限。三個約束條件的對偶價格-.333、-.278、-.222分別表示三種規(guī)格薄銅板數(shù)量的最低限再增加一個，將增加原銅板.333cm、.278cm、.222cm。這個數(shù)字實際跟薄銅板長度規(guī)格相一致。常數(shù)項數(shù)范圍表示三種規(guī)格薄銅板數(shù)量的最低限在這些范圍內(nèi)，每增一個限額所原原銅板.333cm、.278cm、.22

12、2cm不變。這里需要特別指出的是，第一種規(guī)格的薄銅板32cm寬，已使三塊組合就能比較恰當?shù)赜猛暝~板，所以這種規(guī)格的薄銅板無論增加多少，都不改變用原銅板的比例。5.3 某醫(yī)院對醫(yī)生工作的安排為4小時一個工作班次，每人要連續(xù)工作二個班次。各班次需要醫(yī)生人數(shù)如下表：班次時間人數(shù)10:00-4:00424:00-8:00738:00-12:009412:00-16:0012516:00-20:008620:00-24:006其中，第6班報到的醫(yī)生要連續(xù)上班到第二天的第1班。問在各班開始時應該分別有幾位醫(yī)生報到。若參加1、2、6班的醫(yī)生需要支付夜班津貼，為了使支付總的夜班津貼為最少，應如何安排各班開始

13、時醫(yī)生的報到人數(shù)。解：第一步：不考慮夜班津貼。線性規(guī)劃數(shù)學模型為： min f=x1+x2+x3+x4+x5+x6 S.T. x6+x14 x1+x27 x2+x39 x3+x412 x4+x58 x5+x66 xi0（i=1，2，3，4，5，6）用Excel線性規(guī)劃求解模板求解得：第一班安排7人，第三班安排10人，第四班安排2人，第五班安排6人，第二、第六班不安排人?？?cè)藬?shù)為25人。靈敏度分析報告：目標函數(shù)最優(yōu)值為 : 25 變量 最優(yōu)解 相差值 x1 7 0 x2 0 0 x3 10 0 x4 2 0 x5 6 0 x6 0 0 約束 松弛/剩余變量 對偶價格 1 3 .0 2 0 -1

14、3 1 .0 4 0 -1 5 0 . 0 6 0 -1 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 x1 0 .1 1 x2 1 1 無上限. x3 0 . 1 1x4 1 . 1 2 x5 0 1 1 x6 1 1 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 1 無下限 4 7 2 4 7 無上限 3 無下限 9 10 4 11 12 無上限5 6 8 9 6 5 6 8 這是一統(tǒng)計型線性規(guī)劃規(guī)劃問題，所以相差值的價值系數(shù)的變化范圍沒有必要分析。班次時間所需人數(shù)本段安排人數(shù)上段安排人數(shù)本段實際人數(shù)多余人數(shù)10:00-4:004707324:00-8:007077038:00-1

15、2:009100101412:00-16:0012210120516:00-20:0086280620:00-24:0060660合計4625504松弛/剩余變量一欄就是上表的“多余人數(shù)”一列是各時間段安排所剩余的人數(shù)。“對偶價格”一欄。第一個常數(shù)項由4增加到5，因為還剩下2人，所以不會改變最優(yōu)值；第二個常數(shù)項由7增加到8，因為再沒有剩余的人，所以本班必須再多安排一個人最優(yōu)值解也必須增加1，因為是求最小化問題，所以對偶價格為1；第三個常數(shù)項由9增加到10，剛好將原來剩余的人用上，所以不會改變最優(yōu)值；第四個、第六個常數(shù)項與第二個常數(shù)項一樣；第五個常數(shù)項由2增加到3，因為再沒有剩余的人，所以本班必

16、須再多安排一個人，但下個班就可以再少安排一個人，所以不會改變最優(yōu)值；本題的這種情況是每一個變量都會影響到兩個時段的結(jié)果，所以在進行靈敏度分析時也必定要考慮這個因素，這里第一個時段是特殊情況（有資源剩余），其余的時段分析時相鄰兩個是相互影響的。因此，第2時段為-1，第3時段為0，后面的依次相反。若第2時段為0，則第3時段就為-1。第二步：考慮夜班津貼。線性規(guī)劃數(shù)學模型為：min f=x1+x2+x3+x5+x6 S.T. x6+x14 x1+x27 x2+x39 x3+x412 x4+x58 x5+x66 xi0（i=1，2，3，4，5，6）用Excel線性規(guī)劃求解模板求解得：即：總?cè)藬?shù)還是25

17、人，但每班安排人數(shù)有所調(diào)整：第一班不安排人，第二班安排7人，第三班安排2人，第四班安排10人，第五班安排0人，第六班安排6人。靈敏度分析報告：目標函數(shù)最優(yōu)值為 : 15 變量 最優(yōu)解 相差值 x1 0 1 x2 7 0 x3 2 0 x4 10 0 x5 0 0 x6 6 0 約束 松弛/剩余變量 對偶價格 1 2 0 2 0 0 3 0 -1 4 0 0 5 2 0 6 0 -1 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 x1 0 1 無上限 x2 1 1 2 x3 0 1 1 x4 0 0 1 x5 1 1 無上限 x6 0 1 1 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 1 無

18、下限 4 6 2 5 7 9 3 7 9 11 4 10 12 無上限 5 無下限 8 10 6 4 6 無上限 這是一統(tǒng)計型線性規(guī)劃規(guī)劃問題，所以相差值的價值系數(shù)的變化范圍沒有必要分析。班次時間所需人數(shù)本段安排人數(shù)上段安排人數(shù)本段實際人數(shù)多余人數(shù)10:00-4:004066224:00-8:007707038:00-12:0092790412:00-16:0012102120516:00-20:008010102620:00-24:0066060合計4625504“對偶價格”一欄。第一個常數(shù)項由4增加到5，因為還剩下2人，所以不會改變最優(yōu)值；第二個常數(shù)項由7增加到8，由于上段時間已增一個人，

19、這個人本班還上班，所以本也不需要增加人。第三個常數(shù)項由9增加到10，前面安排的人都已下班，本班剛好只朋9人，若需求再增加一人，就需要新安排一人所以對偶價格-1；第四個、第五個、第六個常數(shù)項與前三個常數(shù)項一樣；5.4 某塑料廠要用四種化學配料生產(chǎn)一種塑料產(chǎn)品，這四種配料分別由A、B、C三種化學原料配制，三種化學原料的配方及原料價格如下表：配料1234價格（元/公斤）含原料A（%）3040201511含原料B（%）2030604013含原料C（%）4025153012要配制的塑料產(chǎn)品中，要求含有20%的原料A，不少于30%的材料B和不少于20%的原料C。由于技術(shù)原因，配料1的用量不能超過30%，配

20、料2的用量不能少于40%。第一次配制的塑料產(chǎn)品不能少于5公斤。請設計一套配料方案，使總的成本為最低。解：線性規(guī)劃數(shù)學模型：min f =10.7x1+11.3x2+11.8x3+9.45x4S.T. 0.1x1+0.2x2 -0.05x4=0 -0.1x1 +0.3x3+0.1x40 0.2x1+0.05x2-0.05x3+0.1x40 0.7x1-0.3x2-0.3x3-0.3x40 -0.4x1+0.6x2-0.4x3-0.4x40 x1+x2+x3+x45 xi0（i=1，2，3，4，）將模型代入到線性規(guī)劃求解模板，得結(jié)果：用配料1，1.5公斤；用配料2，0.1公斤；用配料3，0公斤；用

21、配料4，3.4公斤； 花費總的最低成本49.31元。靈敏度分析報告：目標函數(shù)最優(yōu)值為 : 49.31 變量 最優(yōu)解 相差值 x1 1.5 0 x2 .1 0 x3 0 1.98 x4 3.4 0 約束 松弛/剩余變量 對偶價格 1 0 -7.4 2 .19 0 3 .645 0 4 0 -.14 5 1.9 0 6 0 -9.862 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 x1 10.56 10.7 無上限 x2 -481.8 11.3 11.533 x3 9.82 11.8 無上限 x4 -5.053 9.45 9.8 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 1 -.025 0

22、.475 2 無下限 0 .19 3 無下限 0 .645 4 -1.5 0 .167 5 -1.9 0 無上限 6 0 5 無上限本問題的相差值欄，x3的相差值為1.98，表示目前配料3的成本11.8太高，無法選用，若該配料的成本再降低1.98元就可以選取用。松弛/剩余變量欄：前五個給條件都表示的是配料或原料的配比關(guān)系。松弛/剩余變量為0 關(guān)系表示已完全按要求配比，不為0 的表示沒有達到配比要求。第五個約束是總產(chǎn)品的產(chǎn)量最低限，松弛/剩余變量為0 表示已達到產(chǎn)量要求。關(guān)五個約束的對偶價格表示配料或者說原料不匹配時，對總費用的影響。不為0的對偶價格表示配比每差一個單位都會使總費用的增加量。第五

23、個對偶價格是每增加一公斤的產(chǎn)品，需要增加的費用值。在學數(shù)項取值范圍欄：前五個約束在常數(shù)項在這個范圍內(nèi)，保持上述的對偶價格，而此時的上限都不高，說明這個最優(yōu)方案中的匹配關(guān)系失衡并不嚴重，若比例失衡將會導致費用的增加比例更大。對五個對偶價格實際上說明了該產(chǎn)品的絕對成本，在這個方案下，生產(chǎn)多少的產(chǎn)品都是這個成本構(gòu)成。5.5 某工廠生產(chǎn)、四種產(chǎn)品，產(chǎn)品需經(jīng)過A、B兩種機器加工，產(chǎn)品需經(jīng)過A、C兩種機器加工，產(chǎn)品需經(jīng)過B、C兩種機器加工，產(chǎn)品需經(jīng)過A、B兩種機器加工。有關(guān)數(shù)據(jù)見下表所示：產(chǎn)品機器生產(chǎn)率（件/小時）原料成本（元/件）產(chǎn)品價格（元/件）ABC1020166520102580101512502

24、0101870機器成本（元/小時）200150225每周可用機時數(shù)15012070請為該廠制定一個最優(yōu)生產(chǎn)計劃。解：線性規(guī)劃數(shù)學模型： max Z=21.5 x1+22.5 x2+8 x3+27 x4S.T. 2x1+x2+x43000 x1+2x3+2x42400 3x2+4x34200 xi0（i=1，2,.4）用Excel線性規(guī)劃求解模板求解得：最優(yōu)生產(chǎn)方案：產(chǎn)品生產(chǎn)267件； 產(chǎn)品生產(chǎn)1400件； 產(chǎn)品不安排生產(chǎn)； 產(chǎn)品生產(chǎn)1067件?？色@得的最高利潤：66033.3元。靈敏度分析報告：即：目標函數(shù)最優(yōu)值為 : 66033.3495 變量 最優(yōu)解 相差值 - - - x1 266.66

25、7 0 x2 1400 0 x3 0 30.8333 x4 1066.667 0 約束 松弛/剩余變量 對偶價格 - - - 1 0 5.333 2 0 10.833 3 0 5.722 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 - - - - x1 13.5 21.5 45 x2 5.333 22.5 無上限 x3 無下限 8 38.333 x4 10.75 27 43 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 - - - - 1 2600 3000 6200 2 800 2400 3200 3 0 4200 5400 此模型的最優(yōu)解中，四個變量有三個變量不為0，即需要安排生產(chǎn)，另一

26、個為0 的變量表示產(chǎn)品由于成本高或價格低，使所獲的利潤太低，不值得生產(chǎn)。從相差值欄可見，該產(chǎn)品的單位利潤需要再增加30.8333元才值得生產(chǎn)。松弛/剩余變量欄中三個數(shù)據(jù)都為0，表示該決策中所提供三種設備的機時都已全部利用，沒有剩余；從對偶價格欄還可以看到三種設備的機時雖然都已用盡，但此時對三種設備增加機時，則設備B所帶來的總利潤為最多。因此設備B是瓶徑。從約束條件的取值范圍也可以看到這一點，因為設備B的機時取值范圍最小，因此該設備是關(guān)鍵。5.6 某企業(yè)生產(chǎn)、兩種產(chǎn)品，市場兩種產(chǎn)品的需求量為：產(chǎn)品在1-4月份每月需1萬件，5-9月份每月需3萬件，10-12月份每月需10萬件；產(chǎn)品在3-9月份每月

27、需1.5萬件，其他月份每月需5萬件。該企業(yè)生產(chǎn)這兩種產(chǎn)品的成本為：產(chǎn)品在1-5月份生產(chǎn)時每件5元，6-12月份生產(chǎn)時每件4.5元；產(chǎn)品在1-5月份生產(chǎn)時每件8元，6-12月份生產(chǎn)時每件7元；該企業(yè)每月生產(chǎn)兩種產(chǎn)品的能力總和不超過12萬件。產(chǎn)品容積為每件0.2立方米，產(chǎn)品容積為每件0.4立方米。該企業(yè)倉庫容積為1.5萬立方米。要求：1、問該企業(yè)應如何安排生產(chǎn)，使總的生產(chǎn)加工儲存費用為最少，建立線性規(guī)劃數(shù)學模型并求解，若無解請說明原因。2、若該企業(yè)的倉庫容積不足時，可從外廠租借。若占用本企業(yè)的倉庫每月每立方米需1萬元的儲存費，而租用外廠倉庫時其儲存費用為每月每立方米1.5萬元，試問在滿足市場需求情

28、況下，該企業(yè)又應如何安排生產(chǎn)，使總的生產(chǎn)加儲存費用為最少。解：1、這是一個72個變量、60個約束條件的線性規(guī)劃問題，若不考慮外廠租借倉庫，則無法求解（無解），只有考慮外廠租借倉庫才能解決本問題。分析及解決過程和結(jié)果可見下表：月份123456789101112倉容外存產(chǎn)品銷售量（千件）10101010303030303010010010015000（m3）1元/m3容量不限1.5元/m3成本（元、件）555554.54.54.54.54.54.54.5產(chǎn)量（件）x1=10x2=10x3=10x4=10x5=30x6=30x7=30x8=45x9=105x10=70x11=70x12=70總?cè)莘e（

29、千m3）0.2x10.2x20.2x30.2x40.2x50.2x60.2x70.2x80.2x90.2x100.2x110.2x12庫存數(shù)x25=0x26=0x27=0x28=0x29=0x30=0x31=0x32=15x33=90x34=60x35=30x36=0產(chǎn)品銷售量（千件）505015151515151515505050成本（元、件）888887777777產(chǎn)量（件）x13=50x14=50x15=15x16=15x17=15x18=15x19=15x20=15x21=15x22=50x23=50x24=50總?cè)莘e（千m3）0.4x130.4x140.4x150.4x160.4x170.4x180.4x190.4x200.4x210.4x220.4x230.4x24庫存數(shù)x37=0x38=0x39=0x40=0x41=0x42=0x43=0x44=0x45=0x46=0x47=0x