數(shù)學(xué)建模優(yōu)化理論與方法

《數(shù)學(xué)建模優(yōu)化理論與方法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)學(xué)規(guī)劃的理論與方法1.線性規(guī)劃理論與方法2.目標(biāo)規(guī)劃的理論與方法3.整數(shù)規(guī)劃的理論與方法非線性規(guī)劃的理論與方法5.動(dòng)態(tài)規(guī)劃6.最優(yōu)控制理論y一.線性規(guī)劃的理論與方法線性規(guī)劃是指目標(biāo)函數(shù)是由線性函數(shù)給出，約束條件由線性等式或者不等式給出的優(yōu)化問題。最早提出線性規(guī)劃問題并進(jìn)行專門研究的學(xué)者—康托洛維奇?？低新寰S奇在20世紀(jì)30年代就提出了求解線性規(guī)劃問題的“解乘數(shù)法”。自從1947年美國學(xué)者丹青格提出求解線性規(guī)劃問題的一般方法—單純形方法后，才使線性規(guī)劃的理論和方法日臻成熟。（1）由決策變量構(gòu)成，反映決策的目標(biāo)是線性函數(shù)。（2）一組由決策變量的線性等式或不等式構(gòu)成約束條件。（3）對(duì)

2、決策變量取值范圍加以限制的非負(fù)約束。1.1線性規(guī)劃模型的特征例1：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的利潤、所消耗的材料、工時(shí)及每天的材料限額和工時(shí)限額，如表1.1所示。試問如何安排生產(chǎn)，使每天所得的利潤為最大？表1.1甲乙限額材料2324工時(shí)3226利潤(元/件)43設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為x1,x2則該問題可描述為由如下數(shù)學(xué)模型：1.2線性規(guī)劃問題的標(biāo)準(zhǔn)型如下形式的線性規(guī)劃模型被稱作標(biāo)準(zhǔn)型:也可用矩陣形式描述:A:資源消耗系數(shù)矩陣b:資源限量向量C:價(jià)格向量X:決策變量向量同時(shí)我們對(duì)標(biāo)準(zhǔn)型作如下假定:一般的線性規(guī)劃問題通過變換可化成標(biāo)準(zhǔn)型,變換方式可以歸結(jié)為:1.3線性

3、規(guī)劃問題解的概念對(duì)于線性規(guī)劃問題可行解基解基可行解1.4線性規(guī)劃問題的圖解法下面結(jié)合例1的求解來說明圖解法步驟。例1第一步：在直角坐標(biāo)系中分別作出各種約束條件，求出可行域（圖中陰影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)第二步：作出一條目標(biāo)函數(shù)等值線，并確定Z值增大的方向。第三步：沿Z值增大方向移動(dòng)，當(dāng)移至Q2(6,4)點(diǎn)時(shí)，Z值為最大，Z*=36.1.5基本定理從理論上來講,采用“枚舉法”找出所有基可行解,并1.6求解線性規(guī)劃問題的單純形方法一一比較,一定會(huì)找到最優(yōu)解。但當(dāng)m,n較大時(shí),這種方法是不經(jīng)濟(jì)和不可取

4、的。下面介紹求解線性規(guī)劃問題的有效方法——單純形方法。單純形法的實(shí)質(zhì)是從一個(gè)基可行解向另一個(gè)基可行解（極點(diǎn)到極點(diǎn)）的迭代方法。以下通過例1的求解過程說明單純形方法的基本步驟。例1：第一步：引進(jìn)松馳變量x3,x4將原問題化為標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型第二步：找出初始可行基，建立初始單純形表。見下表1.2。cj4300CBXBbx1x2x3x400x3x4242623103201Z0-4-300表1.2第三步：最優(yōu)性檢驗(yàn)。第四步：換基迭代。cj4300CBXBbx1x2x3x400x3x424262310[3]2011226/3Z0-4-30004x3x120/326/30[5/3]1-2/31

5、2/301/3413Z104/30-1/304/3表1.3同理，確定x2換入，x3換出，繼續(xù)迭代得表1.3cj4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5表1.3表中最后一行的所有檢驗(yàn)數(shù)都已是正數(shù)或零，從而得到基本最優(yōu)解X*=(6,4,0,0)T,Z*=36。由于x3,x4是引進(jìn)的松弛變量，因此原問題的最優(yōu)解為x1=6,x2=4,最優(yōu)值Z*=36。例2一奶制品加工廠用牛奶生產(chǎn)A1,A2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時(shí)加工成3公斤A1,或者在設(shè)備乙上用8小時(shí)加工成4公斤A2。根據(jù)市場(chǎng)需求，生產(chǎn)的A1,A2全

6、部能售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為480小時(shí)，并且設(shè)備甲每天至多能加工100公斤A1,設(shè)備乙的加工能力沒有限制。試為該廠制定一個(gè)我們無意過深涉及線性規(guī)劃的具體計(jì)算方法，而著重介紹的是如何建立若干實(shí)際的線性規(guī)劃模型，如何使用現(xiàn)成的數(shù)學(xué)軟件進(jìn)行求解，以及如何對(duì)結(jié)果進(jìn)行深入的分析。下面以奶制品加工生產(chǎn)計(jì)劃為例，進(jìn)行詳細(xì)的討論。生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下3個(gè)附加問題：若用35元可買到1桶牛奶，買嗎？若買，每天最多買多少?若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元

7、?由于市場(chǎng)需求的變化，A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？1桶牛奶3公斤A112小時(shí)8小時(shí)4公斤A2或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1每天：分析x1桶牛奶生產(chǎn)A1x2桶牛奶生產(chǎn)A2獲利24×3x1獲利16×4x2決策變量數(shù)學(xué)模型原料供應(yīng)勞動(dòng)時(shí)間加工能力非負(fù)約束解法1：圖解法。x1x20ABCDl1l2l3l4l5約束條件Z=0Z=2400Z=3360c從圖中可以看出，在B(20,30)點(diǎn)得到最優(yōu)解。解法2：軟件實(shí)現(xiàn)。求解線