線性規(guī)劃模型-靈敏度分析

第三章線性規(guī)劃模型引言

實例—加工奶制品的生產(chǎn)計劃線性規(guī)劃問題的數(shù)學(xué)模型求解線性規(guī)劃問題的圖解法

用Lingo軟件求解線性規(guī)劃問題

線性規(guī)劃問題的靈敏度分析線性規(guī)劃（LinearProgramming）是數(shù)學(xué)規(guī)劃的一個重要分支,歷史比較悠久,理論比較成熟,方法較為完善。線性規(guī)劃的思想最早可以追溯到1939年,當(dāng)時的蘇聯(lián)數(shù)學(xué)家、經(jīng)濟學(xué)家L.V.Kantorovich（康特羅維奇）在《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中提出了類似線性規(guī)劃的模型,以解決下料問題和運輸問題,并給出了“解決乘數(shù)法”的求解方法。然而,他的工作長期未被人們知道。引言引言由于戰(zhàn)爭的需要,美國的經(jīng)濟學(xué)家T.C.Koopmans(庫普曼斯)重新獨立的研究運輸問題,并很快看到了線性規(guī)劃在經(jīng)濟學(xué)中應(yīng)用的意義.在這之后,線性規(guī)劃也被人們廣泛地用于軍事、經(jīng)濟等各方面。由于Kantorovich和Koopmans在這方面的突出貢獻,他們一起得到1975年諾貝爾經(jīng)濟學(xué)獎。為更好地理解線性規(guī)劃所描述的問題，我們先看一個例子。例1加工奶制品的生產(chǎn)計劃1桶牛奶

3千克A1

12小時

8小時

4千克A2

或獲利24元/千克獲利16元/千克50桶牛奶時間480小時至多加工100千克A1

制訂生產(chǎn)計劃，使每天獲利最大?

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?

A1的獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計劃？每天：1桶牛奶3千克A1

12小時8小時4千克A2

或獲利24元/千克獲利16元/千克x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動時間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負約束

線性規(guī)劃模型(LP)時間480小時至多加工100千克A1

50桶牛奶每天model:max=72*x1+64*x2;x1+x2<=50;12*x1+8*x2<=480;3*x1<=100;end用Lingo軟件求解線性規(guī)劃問題模型Lingo語句模型開始目標(biāo)函數(shù)求極大約束條件（無非負限制）模型結(jié)束Lingo軟件包是由美國LINDO系統(tǒng)公司研制開發(fā)的，是用于求解大型數(shù)學(xué)規(guī)劃問題的軟件包。求解20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。Lingo軟件的計算結(jié)果

Globaloptimalsolutionfoundatstep:2

Objectivevalue:3360.000

VariableValueReducedCost

X120.000000.0000000

X230.000000.0000000RowSlackorSurplusDualPrice13360.0001.00000020.000000048.0000030.00000002.000000440.000000.0000000結(jié)果解釋

Objectivevalue:3360.000VariableValueReducedCostX120.000000.0000000X230.000000.0000000

RowSlackorSurplusDualPrice13360.0001.000000

20.000000048.00000

30.00000002.000000

440.000000.0000000原料無剩余時間無剩余加工能力剩余40三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋

在最優(yōu)解下，“資源”增加1單位時，“效益”的增量原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤影子價格

35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時工人付出的工資最多每小時幾元？2元！Objectivevalue:3360.000VariableValueReducedCostX120.000000.0000000X230.000000.0000000RowSlackorSurplusDualPrice13360.0001.000000

20.000000048.00000

30.00000002.000000

440.000000.0000000Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000最優(yōu)基不變時目標(biāo)函數(shù)系數(shù)允許變化范圍靈敏度分析

x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加53

35元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標(biāo)函數(shù)系數(shù)不變)例2奶制品的生產(chǎn)銷售計劃

在例1基礎(chǔ)上深加工1桶牛奶3千克A1

12小時8小時4千克A2

或獲利24元/千克獲利16元/千克0.8千克B12小時,3元1千克獲利44元/千克0.75千克B22小時,3元1千克獲利32元/千克制訂生產(chǎn)計劃，使每天凈利潤最大

30元可增加1桶牛奶，3元可增加1小時時間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶,480小時至多100公斤A1

B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？生產(chǎn)中通過切割、剪裁、沖壓等手段，將原材料加工成所需大小鋼管下料原料下料問題按照工藝要求，確定下料方案，使所用材料最省，或利潤最大問題1.如何下料最節(jié)省?例1鋼管下料問題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)??？5米10根按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。亢侠砬懈钅Ｊ?.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標(biāo)準1.原料鋼管剩余總余量最小xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27。整數(shù)約束：xi為整數(shù)當(dāng)余料沒有用處時，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問題1約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量

xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型鋼管下料問題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31模式排列順序可任定

鋼管下料問題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米LINGO求解整數(shù)非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.00000