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

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

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

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

3千克A1

12小時(shí)

8小時(shí)

4千克A2

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

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

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

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

12小時(shí)8小時(shí)4千克A2

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

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

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

每天獲利約束條件非負(fù)約束

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

50桶牛奶每天model:max=72*x1+64*x2;x1+x2<=50;12*x1+8*x2<=480;3*x1<=100;end用Lingo軟件求解線性規(guī)劃問(wèn)題模型Lingo語(yǔ)句模型開始目標(biāo)函數(shù)求極大約束條件（無(wú)非負(fù)限制）模型結(jié)束Lingo軟件包是由美國(guó)LINDO系統(tǒng)公司研制開發(fā)的，是用于求解大型數(shù)學(xué)規(guī)劃問(wèn)題的軟件包。求解20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元。Lingo軟件的計(jì)算結(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原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋

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

35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？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)基不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍靈敏度分析

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

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

A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃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影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加53

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

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

12小時(shí)8小時(shí)4千克A2

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

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

B1，B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？生產(chǎn)中通過(guò)切割、剪裁、沖壓等手段，將原材料加工成所需大小鋼管下料原料下料問(wèn)題按照工藝要求，確定下料方案，使所用材料最省，或利潤(rùn)最大問(wèn)題1.如何下料最節(jié)省?例1鋼管下料問(wèn)題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(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鋼管下料問(wèn)題1兩種標(biāo)準(zhǔn)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í)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問(wèn)題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米”相比鋼管下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量

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

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

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