




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、線性規(guī)劃模型及其舉例摘要:在日常生活中,我們常常對一個問題有諸多解決辦法,如何尋找最優(yōu)方案,成為關(guān)鍵,本文提出了線性規(guī)劃數(shù)學(xué)模型及其舉例,在一定約束條件下尋求最優(yōu)解的過程,目的是想說明線性規(guī)劃模型在生產(chǎn)中的巨大應(yīng)用。 關(guān)鍵詞:資源規(guī)劃;約束條件;優(yōu)化模型;最優(yōu)解在工農(nóng)業(yè)生產(chǎn)與經(jīng)營過程中,人們總想用有限的資源投入,獲得盡可能多的使用價值或經(jīng)濟利益。如:當(dāng)任務(wù)或目標(biāo)確定后,如何統(tǒng)籌兼顧,合理安排,用最少的資源(如資金、設(shè)備、原材料、人工、時間等)去完成確定的任務(wù)或目標(biāo);企業(yè)在一定的資源條件限制下,如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益(如產(chǎn)品量最多,利潤最大)。一.背景介紹如果產(chǎn)出量與投入量存在(或近
2、似存在)比例關(guān)系,則可以寫出投入產(chǎn)品的線性函數(shù)式:, (1)若將(1)式中第()個線性方程作為待求的目標(biāo)函數(shù),其余個線性方程作為資源投入的限制條件(或約束條件),則(1)式變?yōu)椋篛PT. ST. > ( =, < ), . (2) (2)式特點是有個待求的變量();有1個待求的線性目標(biāo)函數(shù),有個線性約束等式或不等式,其中()為有限的資源投入常量。將客觀實際問題經(jīng)過系統(tǒng)分析后,構(gòu)建線性規(guī)劃模型,有決策變量,目標(biāo)函數(shù)和約束條件等構(gòu)成。1決策變量(Decision Variable,DV)在約束條件范圍內(nèi)變化且能影響(或限定)目標(biāo)函數(shù)大小的變量。決策變量表示一種活動,變量的一組數(shù)據(jù)代表一
3、個解決方案,通常這些變量取非負值。2約束條件(Subject To,ST)在資源有限與競爭激烈的環(huán)境中進行有目的性的一切活動,都應(yīng)考慮是否符合實際,有沒有可行性,因而要構(gòu)造基于科學(xué)預(yù)測的綜合性約束(或限定)條件。3目標(biāo)函數(shù)(Objective Function,OF)人們有目的活動,總是希望獲得最滿意的目標(biāo)值,該目標(biāo)值可以表達成決策變量的一個函數(shù),即目標(biāo)函數(shù)。根據(jù)需要,目標(biāo)函數(shù)可以取極大化,極小化兩種類型,即求最優(yōu)解。4影子價格(Shadow Price),用線性規(guī)劃方法計算出來的反映資源最優(yōu)使用效果的價格。用線性規(guī)劃方法求解資源最優(yōu)利用時,即在解決如何使有限資源的總產(chǎn)出最大的過程中,得出相應(yīng)
4、的極小值,其解就是對偶解,極小值作為資源的經(jīng)濟評價,表現(xiàn)為影子價格。二建模的基本步驟1. 確定目標(biāo)函數(shù)(按照模型所需要解決的問題,用數(shù)學(xué)函數(shù)來描述目標(biāo))2. 確定決策變量(目標(biāo)的實現(xiàn)與那些變量有關(guān),這里有主要變量和次要變量,在建模的初期可以進考慮主要變量對目標(biāo)的影響,隨后可以逐步增加變量的個數(shù))3. 確定約束條件(這是優(yōu)化模型建模過程中最重要,也是最難的,在很多情況下,是否能夠得到最優(yōu)解,最優(yōu)解是否合理,都是取決于約束條件的建立)4. 模型求解(使用數(shù)學(xué)工具或數(shù)學(xué)軟件求解)5. 結(jié)果分析(分析結(jié)果的合理性、穩(wěn)定性、敏感程度等)三線性規(guī)劃的一般模型一般地,假設(shè)線性規(guī)劃數(shù)學(xué)模型,有個約束,有個決策
5、變量(),目標(biāo)函數(shù)的變量系數(shù)用表示,稱為價值系數(shù)。約束條件的變量系數(shù)用表示,稱為工藝系數(shù)。約束條件右端的常數(shù)用表示,稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成:ST. , , 四線性規(guī)劃模型處理1. 圖解法就是在平面直角坐標(biāo)系上畫出各個約束條件所容許變化的范圍,通過圖上作業(yè)法求到最優(yōu)解和目標(biāo)函數(shù)極值。圖解法只適用于求解兩個決策變量的Lp(線性規(guī)劃)問題。2. 單純形法 給定一般的Lp問題:。 建立Lp問題的典式: 。 計算檢驗數(shù):。利用進行基可行解的最優(yōu)性檢驗(i),人工變量,判定,為最優(yōu)解,輸出最優(yōu)解,。(ii)>0 (至少有一個>0,且>0)轉(zhuǎn)下步。 選擇進基變量
6、>0=,列的為進基變量。 選擇退基變量>0=,行的退基。 確定主元>0,根據(jù)主元進行行換基:(意為初等變換)。利用新基對,進行基變換:;,再轉(zhuǎn)第三步。3. 對偶單純形法(為求影子價格作準(zhǔn)備) 確定為Lp問題的一個初始基,其對應(yīng)的變量為。 判斷的可行性:若,則是Lp問題的最優(yōu)解,這時計算停止,輸出最優(yōu)解。否則進行第步。 若存在,使得<0,且在單純形表中與對應(yīng)行的非基變量的系數(shù)全部非負,則Lp問題無可行解;否則進行第步。確定基變量:令<0,對應(yīng)的基變量為為出基變量。 確定進基變量:計算<0=。選擇對應(yīng)的非基變量為進基變量。行列交叉的元素為主元。以為主元,按單純形
7、法換基迭代運算,得到一個新的基可行解,仍記為,返回到五線性規(guī)劃舉例例1(圖形解)這個問題的圖解如圖1所示。引進松弛變量x3,x4³0,問題變成為標(biāo)準(zhǔn)形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3x4³0OABCDx1x23210123x3=0x4=0x1=0x2=0 其解如陰影部分所示例2.求線性規(guī)劃 (對偶單純形求解)引入多余變量x5、x6把約束化為等式,然后再給兩邊同乘以(-1)后約束變?yōu)椋?-x1 -2x2 -3x3 -x4 + x5 =-2 -2x1 +x2 - x3 + 3x4 +x6 =-3
8、 得對偶單純形表: Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 -2 -1 -2 -3 -1 1 0 0 x6 -3 -2 1 -1 3 0 1 Zj 0 0 0 0 0 0 Zj -Cj -2 -3 -5 -6 0 0 此時基本解為X=(0,0,0,0,-2,-3),不可行。所以進行第二步。 因為min-3,-2=-3,所以x6為換出變量;又因為min-2/-2 ,-5/-1=1,所以x1為換入變量,就是要將x1下的系數(shù)列向量由 變換成 形式(和以前學(xué)過的單純形法中的線性變換完全一致)。做行線性變換, 行(2)×
9、;(-1/2);行(1)+行(2)后得出另一個基本解為:X=(3/2,0,0,0,-1/2)此時單純形表如下:Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 -1/2 0 -5/2 -5/2 -5/2 1 -1/2 2 x1 3/2 1 -1/2 1/2 -3/2 0 -1/2 Zj 2 -1 1 -3 0 -1 Zj -Cj 0 -4 -4 -9 0 -1 仍然不是可行解,還要繼續(xù)求解。 因為-1/2 < 0,所以x5為換出變量;由因為=8/5,所以x2和x3都可以作為換入變量,任選其中一個x2 ,做線性變換: 行(1)×(-2/5
10、);行(2)+行(1)×(1/2) 得到一個基本解為X=(8/5,1/5,0,0,0),因解是可行的,所以是滿足最優(yōu)檢驗下的基本可行解因而也是最優(yōu)解。此時單純形表如下 Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 3 x2 1/5 0 1 1 1 -2/5 1/5 2 x1 8/5 1 0 1 -1 -1/5 -2/5 Zj 2 3 5 1 -8/5 -1/5 為了實現(xiàn)縮短作出最優(yōu)方案的時間,運用MATLAB編程,運用計算機模擬計算處理。MATLAB是MATrix LABoratory的縮寫,它將計算可視化和編程功能集成在非常便于使用的環(huán)境中,是一個交互式的,以距陣計算為基礎(chǔ)的科學(xué)和工程計算軟件
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國腹腔鏡壓榨機行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2025至2030中國脫水冷凍水果行業(yè)發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報告
- 2025至2030中國膠合板行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2025至2030中國聚醚消泡劑行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2025至2030中國聚光鏡行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 基于大數(shù)據(jù)的營銷活動分析報告
- 2025至2030中國美甲行業(yè)市場發(fā)展現(xiàn)狀及發(fā)展趨勢與投資發(fā)展報告
- 2025至2030中國羊奶粉行業(yè)市場深度研究及發(fā)展前景投資可行性分析報告
- 2025至2030中國網(wǎng)絡(luò)動漫行業(yè)營銷模式與投資契機深度評估報告
- 2025至2030中國罐式集裝箱行業(yè)發(fā)展研究與產(chǎn)業(yè)戰(zhàn)略規(guī)劃分析評估報告
- 預(yù)防艾滋病、梅毒和乙肝母嬰傳播相關(guān)報表、上報流程和要求
- 《鐵路技術(shù)管理規(guī)程》(普速鐵路部分)-14年新版
- 食用油儲存期品質(zhì)變化的太赫茲光譜無損識別
- 胎盤早剝預(yù)案演練腳本
- 五山文學(xué)全集第一卷
- 聚磷腈功能高分子材料的合成及應(yīng)用
- 中國鐵路總公司《鐵路技術(shù)管理規(guī)程》(高速鐵路部分)2014年7月
- 鈣加維生素Dppt課件(PPT 14頁)
- TRD深基坑止水帷幕施工方案(22頁)
- 八少八素初試甄別試題
- 企業(yè)組織架構(gòu)圖模板
評論
0/150
提交評論