




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、第一節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式與基本性質(zhì)第二節(jié)基本可行解的轉(zhuǎn)換第三節(jié)單純形方法第五章線性規(guī)劃第四節(jié)單純形法應(yīng)用舉例第五節(jié)修正單純形法 目標(biāo)函數(shù)和約束條件都是線性的,像這類約束函數(shù)和目標(biāo)函數(shù)都是為線性函數(shù)的優(yōu)化問題,稱作線性規(guī)劃問題。它的解法在理論和方法上都很成熟,實際應(yīng)用也很廣泛。雖然大多數(shù)工程設(shè)計是非線性的,但是也有采用線性逼近方法求解非線性問題的。此外,線性規(guī)劃方法還常被用作解決非線性問題的子問題的工具,如在可行方向法中可行方向的尋求就是采用線性規(guī)劃方法。當(dāng)然,對于真正的線性優(yōu)化問題,線性規(guī)劃方法就更有用了。第五章線性規(guī)劃解:設(shè)生產(chǎn)A、B兩產(chǎn)品分別為x1, x2臺,則該問題的優(yōu)化數(shù)學(xué)模型為:例5
2、-1: 某工廠要生產(chǎn)A、B兩種產(chǎn)品,每生產(chǎn)一臺產(chǎn)品A 可獲產(chǎn)值2萬元;需占用一車間工作日3天,二車間工作日6天;每生產(chǎn)一臺產(chǎn)品B 可獲產(chǎn)值1萬元;需占用一車間工作日5天,二車間工作日2天?,F(xiàn)一車間可用于生產(chǎn)A、B產(chǎn)品的時間15天,二車間可用于生產(chǎn)A、B產(chǎn)品的時間24天。試求出生產(chǎn)組織者安排A、B兩種產(chǎn)品的合理投資產(chǎn)數(shù),以獲得最大的總產(chǎn)值。第一節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)形式與基本性質(zhì)一、線性規(guī)劃實例例5-2:生產(chǎn)甲種產(chǎn)品每件需使用材料9kg、3個工時、4kw電,獲利潤60元。生產(chǎn)乙種產(chǎn)品每件需用材料4kg、10個工時、5kw電,可獲利120元。若每天能供應(yīng)材料360kg,有300個工時,能供200kw電
3、。試確定兩種產(chǎn)品每天的產(chǎn)量,使每天可能獲得的利潤最大? 分析:每天生產(chǎn)的甲、乙兩種產(chǎn)品分別為 件 (工時約束)(電力約束)(材料約束)(利潤最大)將其化成線性規(guī)劃標(biāo)準(zhǔn)形式:求使且滿足例5-3:某廠生產(chǎn)甲、乙兩種產(chǎn)品,已知:兩種產(chǎn)品分別由兩條生產(chǎn)線生產(chǎn)。第一條生產(chǎn)甲,每天最多生產(chǎn)9件,第二條生產(chǎn)乙,每天最多生產(chǎn)7件;該廠僅有工人24名,生產(chǎn)甲每件用2工日,生產(chǎn)乙每件用3工日;產(chǎn)品甲、乙的單件利潤分別為40元和80元。問工廠如何組織生產(chǎn)才能獲得最大利潤?日利潤最大生產(chǎn)能力限制勞動力限制變量非負(fù)解: 設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為s.t.建模例1: 某公司有鋼材、鋁材、銅材1200t,800t和6
4、50t,擬調(diào)往物資緊張的地區(qū)甲、乙、丙。已知甲、乙、丙對上述物資的總需求分別為:900t,800t和1000t。各種物資在各地銷售每噸的獲利如下表所示。試問公司應(yīng)如何安排調(diào)運計劃,才能獲利最大?建立該問題的數(shù)學(xué)模型。鋼材鋁材銅材甲260300400乙210250550丙180400350物資獲利地區(qū)建模例2: 某工廠生產(chǎn)A、B、C三種產(chǎn)品,現(xiàn)根據(jù)訂貨合同以及生產(chǎn)狀況制定5月份的生產(chǎn)計劃,已知合同甲為:A產(chǎn)品1000件,單件價格為500元,違約金為100元/件;合同乙為:B產(chǎn)品500件,單件價格為400元,違約金為120元/件;合同丙為:B產(chǎn)品600件,單件價格為420元,違約金為130元/件;
5、C產(chǎn)品600件,單件價格為400元,違約金為90元/件;有關(guān)各產(chǎn)品生產(chǎn)過程所需工時以及原材料的情況見下表。試以利潤為目標(biāo),建立該工廠的生產(chǎn)計劃線性規(guī)劃模型 。工序1工序2工序3原材料1原材料2其他成本產(chǎn)品A /件2323410產(chǎn)品B /件1132310產(chǎn)品C /件2124210總工時或原材料460040006000100008000工時或原材料成本(元)1510102040建模例3: 成批生產(chǎn)企業(yè)年度生產(chǎn)計劃的按月分配 。在成批生產(chǎn)的機械制造企業(yè)中,不同產(chǎn)品勞動量的結(jié)構(gòu)上可能有很大差別。如:某種產(chǎn)品要求較多的車床加工時間,另一種產(chǎn)品的勞動量可能集中在銑床和其他機床上。因此,企業(yè)在按月分配年度計
6、劃任務(wù)時,應(yīng)考慮到各種設(shè)備的均衡且最大負(fù)荷。 在年度計劃按月分配時一般要考慮:1)從數(shù)量和品種上保證年度計劃的完成;2)成批的產(chǎn)品盡可能在各個月內(nèi)均衡生產(chǎn)或集中在幾個月內(nèi)生產(chǎn);3)由于生產(chǎn)技術(shù)準(zhǔn)備等方面原因,某些產(chǎn)品要在某個月后才能投產(chǎn);4)根據(jù)合同要求,某些產(chǎn)品要求在年初交貨;5)批量小的產(chǎn)品盡可能集中在一個月或幾個月內(nèi)生產(chǎn)出來,以便減少各個月的品種數(shù)量等等。如何在滿足上述條件的基礎(chǔ)上,使設(shè)備均衡負(fù)荷且最大負(fù)荷。線性規(guī)劃數(shù)學(xué)模型的一般形式:求使且滿足說明:1)m=n,唯一解2)mn,無解3)mm)為轉(zhuǎn)軸元素,此時xt進入基, xs出基。這樣就完成了從一個基本解到另一個基本解的轉(zhuǎn)換解:用a11
7、, a22作為軸元素進行兩次轉(zhuǎn)軸運算:例:給定如下方程組,試進行基本解的轉(zhuǎn)換運算。得到一組基本解: x1=-12 x2=-20 x3=x4=x5=0用a25作為軸元素進行第三次轉(zhuǎn)軸運算:又得到一組基本可行解: x1=3 x5=5 x2=x3=x4=0此時x5進入基, x2出基。二、從一個基本可行解轉(zhuǎn)到另一個基本可行解當(dāng)已經(jīng)得到一組基本可行解,若要求把xk選進基本變量,并使下一組基本解是可行解的話,則在第k列要選取不為任何負(fù)值的元素作為轉(zhuǎn)軸元素alk作為轉(zhuǎn)軸元素進行轉(zhuǎn)軸運算:方程組第一行發(fā)生的變化:alk作為軸元素,xk選進基本變量后, xk的取值由零變成了一個正值 ,則原來各基本變量的取值變?yōu)?/p>
8、: 若是基本可行解, 應(yīng)該保證各差值最小者為零 : 決定了離基變量為xi若想用xk取代xl成為可行解中的基本變量,就應(yīng)該選 所對應(yīng)的行成為轉(zhuǎn)軸行,即所選取的行要滿足條件:規(guī)則例:基本可行解: x1=3 x5=5 x2=x3=x4=0基本變量x1、x5 基本可行解的轉(zhuǎn)換: 1)x2、x4系數(shù)全部為負(fù),只能選取x3所在的第3列為轉(zhuǎn)軸行 2) , 由于 ,則取第一行為轉(zhuǎn)軸行, 于是取a13=2為轉(zhuǎn)軸元素,使x3取代x1成為基本變量。經(jīng)轉(zhuǎn)軸運算得:得基本可行解: 結(jié)論:可把松馳變量作為初始基本可行解中的一部分基本 變量。三、初始基本可行解的求法原始約束條件:引入松馳變量:可得一組基本可行解:一、單純形
9、法的基本思想從一個初始基本可行解X0出發(fā),尋找目標(biāo)函數(shù)有較大下降的一個新的基本可行解X1,代替原來的基本可行解X0,如此完成一次迭代。隨后作出判斷,如果未達到最優(yōu)解,則繼續(xù)迭代下去。因為基本可行解的數(shù)目有限,所以經(jīng)過有限次迭代一定能達到最優(yōu)解。第三節(jié) 單純形方法采用單純形法求解線性規(guī)劃問題,主要應(yīng)解決以下三個問題:(1)如何確定初始基本可行解;(2)如何由一個基本可行解迭代出另一個基本可行解,同時保證目標(biāo)函數(shù)的下降性;(3)如何判斷一個基本可行解是否為最優(yōu)解。二.最優(yōu)解規(guī)則 對應(yīng)一組基本可行解: 前m個變量組成基本可行解的基本變量相應(yīng)的目標(biāo)函數(shù)值為:經(jīng)過轉(zhuǎn)軸運算得到另一組基本可行解為:其中:進
10、基變量xk出基變量xs對應(yīng)的目標(biāo)函數(shù)為:由于要求結(jié)論:一旦所有的 , 即可停止 轉(zhuǎn)軸運算,對應(yīng)的可行解就是最優(yōu)解。r是 對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標(biāo) 志,稱之為檢驗數(shù)。具體計算時應(yīng)選取:由于有可能同時有幾組 都為負(fù)值最速變化規(guī)則1)最速變化規(guī)則決定進基的非基本變量結(jié)論:2) 規(guī)則決定了出基的基本變量3)若對基本可行解X,所有檢驗數(shù)rk 0,則X 為最優(yōu)解。 例5-3某建筑單位擬蓋一批二人、三人和四人的宿舍單元,要確定每一種宿舍單元的數(shù)目,以獲得最大利潤。其限制條件如下:1)預(yù)算不能超過9000千元。2)宿舍單元總數(shù)不得少于350套。3)每類宿舍單元的百分比為:二人的不超過總數(shù)的20%,三人的不超過總數(shù)的60%,四人的不超過總數(shù)的40%(百分比總和超過100,這是上限)。4)建造價格為:二人的宿舍單元是20千元,三人的宿舍單元是25千元,四人的宿舍單元是30千元。5)凈利潤為:二人的宿舍單元是2千元,三人的宿舍單元是3千元,四人的宿舍單元是4千元。解:略第四節(jié) 單純形法應(yīng)用舉例修正單純形法的迭代過程如下:第五節(jié) 修正單純形法(1)根據(jù)問題的需要,加入松弛變量或人工變量,寫出初始基方陣E,求E-1和基本解(2)計算 和 ,對應(yīng)于非基本變量計算相應(yīng)的 。若所有 (對極小化問題),則x為最優(yōu)解;否則轉(zhuǎn)至步驟(3)。(3)選取進入
溫馨提示
- 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)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025-2030年中國鋁擠壓行業(yè)市場運營狀況及發(fā)展趨勢分析報告
- 2025-2030年中國金屬波紋補償器市場發(fā)展?fàn)顩r及前景趨勢分析報告
- 2025天津市安全員《B證》考試題庫及答案
- 2025-2030年中國聚對苯二甲酸丁行業(yè)投資戰(zhàn)略決策研究報告
- 2025-2030年中國紡織機械制造產(chǎn)業(yè)十三五規(guī)劃及投資戰(zhàn)略研究報告
- 2025-2030年中國石斑魚市場運行狀況與十三五規(guī)劃研究報告
- 2025-2030年中國電熱水器行業(yè)競爭格局及投資戰(zhàn)略研究報告
- 2025年江西省建筑安全員A證考試題庫附答案
- 欽州幼兒師范高等??茖W(xué)校《新能源汽車結(jié)構(gòu)與原理》2023-2024學(xué)年第二學(xué)期期末試卷
- 2025浙江省安全員考試題庫
- 借哪吒精神燃開學(xué)斗志 開學(xué)主題班會課件
- 學(xué)校教職工代表大會全套會議會務(wù)資料匯編
- 新部編版小學(xué)六年級下冊語文第二單元測試卷及答案
- GB/T 45107-2024表土剝離及其再利用技術(shù)要求
- 一年級家長會課件2024-2025學(xué)年
- 2024年海南省??谑行∩鯏?shù)學(xué)試卷(含答案)
- 廣東省五年一貫制語文試卷
- 新版北師大版小學(xué)3三年級數(shù)學(xué)下冊全冊教案完整(新教材)
- 房地產(chǎn)項目盈虧平衡分析
- 中興網(wǎng)管日常操作
- 《綜采工作面綜合防塵技術(shù)規(guī)范》
評論
0/150
提交評論