數(shù)學(xué)建模課件第四章

第四章數(shù)學(xué)規(guī)劃模型

4.3

汽車生產(chǎn)與原油采購(gòu)4.5

飲料廠的生產(chǎn)與檢修

數(shù)學(xué)模型《數(shù)學(xué)模型》

姜啟源主編數(shù)學(xué)規(guī)劃模型

實(shí)際問題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件多元函數(shù)條件極值決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m較大最優(yōu)解在可行域的邊界上取得數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編

如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例1汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。

小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動(dòng)時(shí)間（小時(shí)）28025040060000利潤(rùn)（萬元）234

制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。4.3

汽車生產(chǎn)與原油采購(gòu)第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編模型求解

3）

模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過比較可能得到更優(yōu)的解。

但必須檢驗(yàn)它們是否滿足約束條件。為什么？第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)“gin3”表示“前3個(gè)變量為整數(shù)”，等價(jià)于：ginx1ginx2ginx3IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車廠生產(chǎn)計(jì)劃

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1,x2,,x3=0或

80

x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編LINDO中對(duì)0-1變量的限定：inty1inty2inty3方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB)，但是其結(jié)果常依賴于初值的選擇。方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡(jiǎn)記NLP）

實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編應(yīng)如何安排原油的采購(gòu)和加工

？

例2原油采購(gòu)與加工市場(chǎng)上可買到不超過1500噸的原油A：購(gòu)買量不超過500噸時(shí)的單價(jià)為10000元/噸；購(gòu)買量超過500噸但不超過1000噸時(shí)，超過500噸的部分8000元/噸；購(gòu)買量超過1000噸時(shí)，超過1000噸的部分6000元/噸。售價(jià)4800元/噸售價(jià)5600元/噸庫(kù)存500噸庫(kù)存1000噸汽油甲(A

50%)原油A原油B汽油乙(A

60%)第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編決策變量

目標(biāo)函數(shù)問題分析

利潤(rùn)：銷售汽油的收入-購(gòu)買原油A的支出難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜甲(A

50%)AB乙(A

60%)購(gòu)買x

x11x12x21x224.8千元/噸5.6千元/噸原油A的購(gòu)買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購(gòu)買原油A的支出利潤(rùn)(千元)c(x)如何表述？第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編原油供應(yīng)

約束條件x

500噸單價(jià)為10千元/噸；

500噸

x

1000噸，超過500噸的8千元/噸；1000噸

x

1500噸，超過1000噸的6千元/噸。目標(biāo)函數(shù)購(gòu)買x

ABx11x12x21x22庫(kù)存500噸庫(kù)存1000噸第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編

目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；對(duì)于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解；想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解。

汽油含原油A的比例限制約束條件甲(A

50%)AB乙(A

60%)x11x12x21x22第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購(gòu)A的噸數(shù)目標(biāo)函數(shù)

只有當(dāng)以10千元/噸的價(jià)格購(gòu)買x1=500(噸)時(shí)，才能以8千元/噸的價(jià)格購(gòu)買x2方法1

非線性規(guī)劃模型，可以用LINGO求解模型求解x=x1+x2+x3,c(x)=10x1+8x2+6x3

500噸

x

1000噸，超過500噸的8千元/噸增加約束x=x1+x2+x3,c(x)=10x1+8x2+6x3

第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編方法1：LINGO求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12<x+500;x21+x22<1000;x11-x21>0;2*x12-3*x22>0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1<500;x2<500;x3<500;x>0;x11>0;x12>0;x21>0;x22>0;x1>0;x2>0;x3>0;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到的是局部最優(yōu)解，還能得到更好的解嗎？

用庫(kù)存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購(gòu)買新的原油A，利潤(rùn)為4,800千元。

第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編y1,y2,y3=1~以價(jià)格10,8,6(千元/噸)采購(gòu)A增加約束方法2

0-1線性規(guī)劃模型，可用LINDO求解y1,y2,y3=0或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLEVALUEREDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000購(gòu)買1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤(rùn)為5,000千元。x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購(gòu)A的噸數(shù)y=0x=0x>0

y=1優(yōu)于方法1的結(jié)果第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編b1b2

b3

b4方法3

b1

x

b2，x=z1b1+z2b2，z1+z2=1，z1,z2

0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2

x

b3，x=z2b2+z3b3，z2+z3=1，z2,z3

0,c(x)=z2c(b2)+z3c(b3).b3

x

b4，x=z3b3+z4b4，z3+z4=1，z3,z4

0,c(x)=z3c(b3)+z4c(b4).

直接處理處理分段線性函數(shù)c(x)第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編IP模型，LINDO求解，得到的結(jié)果與方法2相同.處理分段線性函數(shù)，方法3更具一般性bk

x

bk+1

yk=1,否則,yk=0方法3

bk

x

bk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+1

0,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000050010001500b1b2

b3

b4對(duì)于k=1,2,3第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編4.5

飲料廠的生產(chǎn)與檢修單階段生產(chǎn)計(jì)劃多階段生產(chǎn)計(jì)劃

生產(chǎn)批量問題

企業(yè)生產(chǎn)計(jì)劃考慮與產(chǎn)量無關(guān)的固定費(fèi)用給優(yōu)化模型求解帶來新的困難外部需求和內(nèi)部資源隨時(shí)間變化第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編

安排生產(chǎn)計(jì)劃,滿足每周的需求,使4周總費(fèi)用最小。存貯費(fèi):每周每千箱飲料0.2千元。例1

飲料廠的生產(chǎn)與檢修計(jì)劃

在4周內(nèi)安排一次設(shè)備檢修，占用當(dāng)周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周?

周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計(jì)100135

某種飲料4周的需求量、生產(chǎn)能力和成本第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編問題分析

除第4周外每周的生產(chǎn)能力超過每周的需求；生產(chǎn)成本逐周上升；前幾周應(yīng)多生產(chǎn)一些。周次需求能力11530225403354542520合計(jì)100135成本5.05.15.45.5

飲料廠在第1周開始時(shí)沒有庫(kù)存；從費(fèi)用最小考慮,第4周末不能有庫(kù)存；周末有庫(kù)存時(shí)需支出一周的存貯費(fèi)；每周末的庫(kù)存量等于下周初的庫(kù)存量。模型假設(shè)

第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編目標(biāo)函數(shù)約束條件產(chǎn)量、庫(kù)存與需求平衡決策變量

能力限制非負(fù)限制模型建立x1~x4：第1~4周的生產(chǎn)量y1~y3：第1~3周末庫(kù)存量周次需求能力11530225403354542520成本5.05.15.45.5存貯費(fèi):0.2(千元/周?千箱)第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編模型求解

4周生產(chǎn)計(jì)劃的總費(fèi)用為528(千元)最優(yōu)解：x1~x4：15，40，25，20；

y1~y3：

0，15，5.周次需求能力11530225403354542520成本5.05.15.45.5產(chǎn)量15402520庫(kù)存01550LINDO求解第四章數(shù)學(xué)規(guī)劃模型《數(shù)學(xué)模型》

姜啟源主編檢修計(jì)劃0-1變量wt

：wt=1~檢修安排在第t周(t=