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

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

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

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

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

4、的。下面介紹求解線性規(guī)劃問題的有效方法——單純形方法。單純形法的實質(zhì)是從一個基可行解向另一個基可行解（極點到極點）的迭代方法。以下通過例1的求解過程說明單純形方法的基本步驟。例1：第一步：引進松馳變量x3,x4將原問題化為標準型。標準型第二步：找出初始可行基，建立初始單純形表。見下表1.2。cj4300CBXBbx1x2x3x400x3x4242623103201Z0-4-300表1.2第三步：最優(yōu)性檢驗。第四步：換基迭代。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表中最后一行的所有檢驗數(shù)都已是正數(shù)或零，從而得到基本最優(yōu)解X*=(6,4,0,0)T,Z*=36。由于x3,x4是引進的松弛變量，因此原問題的最優(yōu)解為x1=6,x2=4,最優(yōu)值Z*=36。例2一奶制品加工廠用牛奶生產(chǎn)A1,A2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時加工成3公斤A1,或者在設(shè)備乙上用8小時加工成4公斤A2。根據(jù)市場需求，生產(chǎn)的A1,A2全

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

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