機(jī)械優(yōu)化設(shè)計(jì)第5章線(xiàn)性規(guī)劃

1、第一節(jié)線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式與基本性質(zhì)第二節(jié)基本可行解的轉(zhuǎn)換第三節(jié)單純形方法第五章線(xiàn)性規(guī)劃第四節(jié)單純形法應(yīng)用舉例第五節(jié)修正單純形法 目標(biāo)函數(shù)和約束條件都是線(xiàn)性的，像這類(lèi)約束函數(shù)和目標(biāo)函數(shù)都是為線(xiàn)性函數(shù)的優(yōu)化問(wèn)題，稱(chēng)作線(xiàn)性規(guī)劃問(wèn)題。它的解法在理論和方法上都很成熟，實(shí)際應(yīng)用也很廣泛。雖然大多數(shù)工程設(shè)計(jì)是非線(xiàn)性的，但是也有采用線(xiàn)性逼近方法求解非線(xiàn)性問(wèn)題的。此外，線(xiàn)性規(guī)劃方法還常被用作解決非線(xiàn)性問(wèn)題的子問(wèn)題的工具，如在可行方向法中可行方向的尋求就是采用線(xiàn)性規(guī)劃方法。當(dāng)然，對(duì)于真正的線(xiàn)性?xún)?yōu)化問(wèn)題，線(xiàn)性規(guī)劃方法就更有用了。第五章線(xiàn)性規(guī)劃解：設(shè)生產(chǎn)A、B兩產(chǎn)品分別為x1, x2臺(tái)，則該問(wèn)題的優(yōu)化數(shù)學(xué)模型為：例5

2、-1： 某工廠要生產(chǎn)A、B兩種產(chǎn)品，每生產(chǎn)一臺(tái)產(chǎn)品A 可獲產(chǎn)值2萬(wàn)元；需占用一車(chē)間工作日3天，二車(chē)間工作日6天；每生產(chǎn)一臺(tái)產(chǎn)品B 可獲產(chǎn)值1萬(wàn)元；需占用一車(chē)間工作日5天，二車(chē)間工作日2天?，F(xiàn)一車(chē)間可用于生產(chǎn)A、B產(chǎn)品的時(shí)間15天，二車(chē)間可用于生產(chǎn)A、B產(chǎn)品的時(shí)間24天。試求出生產(chǎn)組織者安排A、B兩種產(chǎn)品的合理投資產(chǎn)數(shù)，以獲得最大的總產(chǎn)值。第一節(jié) 線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式與基本性質(zhì)一、線(xiàn)性規(guī)劃實(shí)例例5-2：生產(chǎn)甲種產(chǎn)品每件需使用材料9kg、3個(gè)工時(shí)、4kw電，獲利潤(rùn)60元。生產(chǎn)乙種產(chǎn)品每件需用材料4kg、10個(gè)工時(shí)、5kw電，可獲利120元。若每天能供應(yīng)材料360kg，有300個(gè)工時(shí)，能供200kw電

3、。試確定兩種產(chǎn)品每天的產(chǎn)量，使每天可能獲得的利潤(rùn)最大？ 分析：每天生產(chǎn)的甲、乙兩種產(chǎn)品分別為 件 （工時(shí)約束）（電力約束）（材料約束）(利潤(rùn)最大)將其化成線(xiàn)性規(guī)劃標(biāo)準(zhǔn)形式：求使且滿(mǎn)足例5-3：某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：兩種產(chǎn)品分別由兩條生產(chǎn)線(xiàn)生產(chǎn)。第一條生產(chǎn)甲，每天最多生產(chǎn)9件，第二條生產(chǎn)乙，每天最多生產(chǎn)7件；該廠僅有工人24名，生產(chǎn)甲每件用2工日，生產(chǎn)乙每件用3工日；產(chǎn)品甲、乙的單件利潤(rùn)分別為40元和80元。問(wèn)工廠如何組織生產(chǎn)才能獲得最大利潤(rùn)？日利潤(rùn)最大生產(chǎn)能力限制勞動(dòng)力限制變量非負(fù)解: 設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為s.t.建模例1： 某公司有鋼材、鋁材、銅材1200t，800t和6

4、50t，擬調(diào)往物資緊張的地區(qū)甲、乙、丙。已知甲、乙、丙對(duì)上述物資的總需求分別為：900t，800t和1000t。各種物資在各地銷(xiāo)售每噸的獲利如下表所示。試問(wèn)公司應(yīng)如何安排調(diào)運(yùn)計(jì)劃，才能獲利最大？建立該問(wèn)題的數(shù)學(xué)模型。鋼材鋁材銅材甲260300400乙210250550丙180400350物資獲利地區(qū)建模例2： 某工廠生產(chǎn)A、B、C三種產(chǎn)品，現(xiàn)根據(jù)訂貨合同以及生產(chǎn)狀況制定5月份的生產(chǎn)計(jì)劃，已知合同甲為：A產(chǎn)品1000件，單件價(jià)格為500元，違約金為100元/件；合同乙為：B產(chǎn)品500件，單件價(jià)格為400元，違約金為120元/件；合同丙為：B產(chǎn)品600件，單件價(jià)格為420元，違約金為130元/件；

5、C產(chǎn)品600件，單件價(jià)格為400元，違約金為90元/件；有關(guān)各產(chǎn)品生產(chǎn)過(guò)程所需工時(shí)以及原材料的情況見(jiàn)下表。試以利潤(rùn)為目標(biāo)，建立該工廠的生產(chǎn)計(jì)劃線(xiàn)性規(guī)劃模型 。工序1工序2工序3原材料1原材料2其他成本產(chǎn)品A /件2323410產(chǎn)品B /件1132310產(chǎn)品C /件2124210總工時(shí)或原材料460040006000100008000工時(shí)或原材料成本（元）1510102040建模例3： 成批生產(chǎn)企業(yè)年度生產(chǎn)計(jì)劃的按月分配 。在成批生產(chǎn)的機(jī)械制造企業(yè)中，不同產(chǎn)品勞動(dòng)量的結(jié)構(gòu)上可能有很大差別。如：某種產(chǎn)品要求較多的車(chē)床加工時(shí)間，另一種產(chǎn)品的勞動(dòng)量可能集中在銑床和其他機(jī)床上。因此，企業(yè)在按月分配年度計(jì)

6、劃任務(wù)時(shí)，應(yīng)考慮到各種設(shè)備的均衡且最大負(fù)荷。 在年度計(jì)劃按月分配時(shí)一般要考慮:1）從數(shù)量和品種上保證年度計(jì)劃的完成；2）成批的產(chǎn)品盡可能在各個(gè)月內(nèi)均衡生產(chǎn)或集中在幾個(gè)月內(nèi)生產(chǎn)；3）由于生產(chǎn)技術(shù)準(zhǔn)備等方面原因，某些產(chǎn)品要在某個(gè)月后才能投產(chǎn)；4）根據(jù)合同要求，某些產(chǎn)品要求在年初交貨；5）批量小的產(chǎn)品盡可能集中在一個(gè)月或幾個(gè)月內(nèi)生產(chǎn)出來(lái)，以便減少各個(gè)月的品種數(shù)量等等。如何在滿(mǎn)足上述條件的基礎(chǔ)上，使設(shè)備均衡負(fù)荷且最大負(fù)荷。線(xiàn)性規(guī)劃數(shù)學(xué)模型的一般形式：求使且滿(mǎn)足說(shuō)明：1）m=n,唯一解2）mn,無(wú)解3）mm)為轉(zhuǎn)軸元素，此時(shí)xt進(jìn)入基， xs出基。這樣就完成了從一個(gè)基本解到另一個(gè)基本解的轉(zhuǎn)換解：用a11

7、, a22作為軸元素進(jìn)行兩次轉(zhuǎn)軸運(yùn)算：例：給定如下方程組，試進(jìn)行基本解的轉(zhuǎn)換運(yùn)算。得到一組基本解： x1=-12 x2=-20 x3=x4=x5=0用a25作為軸元素進(jìn)行第三次轉(zhuǎn)軸運(yùn)算：又得到一組基本可行解： x1=3 x5=5 x2=x3=x4=0此時(shí)x5進(jìn)入基， x2出基。二、從一個(gè)基本可行解轉(zhuǎn)到另一個(gè)基本可行解當(dāng)已經(jīng)得到一組基本可行解，若要求把xk選進(jìn)基本變量，并使下一組基本解是可行解的話(huà)，則在第k列要選取不為任何負(fù)值的元素作為轉(zhuǎn)軸元素alk作為轉(zhuǎn)軸元素進(jìn)行轉(zhuǎn)軸運(yùn)算：方程組第一行發(fā)生的變化：alk作為軸元素，xk選進(jìn)基本變量后， xk的取值由零變成了一個(gè)正值 ，則原來(lái)各基本變量的取值變?yōu)?/p>

8、: 若是基本可行解, 應(yīng)該保證各差值最小者為零 : 決定了離基變量為xi若想用xk取代xl成為可行解中的基本變量，就應(yīng)該選 所對(duì)應(yīng)的行成為轉(zhuǎn)軸行，即所選取的行要滿(mǎ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)軸運(yùn)算得：得基本可行解： 結(jié)論：可把松馳變量作為初始基本可行解中的一部分基本 變量。三、初始基本可行解的求法原始約束條件:引入松馳變量:可得一組基本可行解：一、單純形

9、法的基本思想從一個(gè)初始基本可行解X0出發(fā)，尋找目標(biāo)函數(shù)有較大下降的一個(gè)新的基本可行解X1,代替原來(lái)的基本可行解X0，如此完成一次迭代。隨后作出判斷，如果未達(dá)到最優(yōu)解，則繼續(xù)迭代下去。因?yàn)榛究尚薪獾臄?shù)目有限，所以經(jīng)過(guò)有限次迭代一定能達(dá)到最優(yōu)解。第三節(jié) 單純形方法采用單純形法求解線(xiàn)性規(guī)劃問(wèn)題，主要應(yīng)解決以下三個(gè)問(wèn)題：（1）如何確定初始基本可行解；（2）如何由一個(gè)基本可行解迭代出另一個(gè)基本可行解，同時(shí)保證目標(biāo)函數(shù)的下降性；（3）如何判斷一個(gè)基本可行解是否為最優(yōu)解。二.最優(yōu)解規(guī)則 對(duì)應(yīng)一組基本可行解： 前m個(gè)變量組成基本可行解的基本變量相應(yīng)的目標(biāo)函數(shù)值為:經(jīng)過(guò)轉(zhuǎn)軸運(yùn)算得到另一組基本可行解為:其中：進(jìn)

10、基變量xk出基變量xs對(duì)應(yīng)的目標(biāo)函數(shù)為:由于要求結(jié)論:一旦所有的 , 即可停止 轉(zhuǎn)軸運(yùn)算,對(duì)應(yīng)的可行解就是最優(yōu)解。r是 對(duì)線(xiàn)性規(guī)劃問(wèn)題的解進(jìn)行最優(yōu)性檢驗(yàn)的標(biāo) 志，稱(chēng)之為檢驗(yàn)數(shù)。具體計(jì)算時(shí)應(yīng)選取:由于有可能同時(shí)有幾組 都為負(fù)值最速變化規(guī)則1）最速變化規(guī)則決定進(jìn)基的非基本變量結(jié)論：2） 規(guī)則決定了出基的基本變量3）若對(duì)基本可行解X，所有檢驗(yàn)數(shù)rk 0，則X 為最優(yōu)解。 例5-3某建筑單位擬蓋一批二人、三人和四人的宿舍單元，要確定每一種宿舍單元的數(shù)目，以獲得最大利潤(rùn)。其限制條件如下：1）預(yù)算不能超過(guò)9000千元。2）宿舍單元總數(shù)不得少于350套。3）每類(lèi)宿舍單元的百分比為：二人的不超過(guò)總數(shù)的20%，三人的不超過(guò)總數(shù)的60%，四人的不超過(guò)總數(shù)的40%（百分比總和超過(guò)100，這是上限）。4）建造價(jià)格為：二人的宿舍單元是20千元，三人的宿舍單元是25千元，四人的宿舍單元是30千元。5）凈利潤(rùn)為：二人的宿舍單元是2千元，三人的宿舍單元是3千元，四人的宿舍單元是4千元。解：略第四節(jié) 單純形法應(yīng)用舉例修正單純形法的迭代過(guò)程如下：第五節(jié) 修正單純形法（1）根據(jù)問(wèn)題的需要，加入松弛變量或人工變量，寫(xiě)出初始基方陣E，求E-1和基本解（2）計(jì)算 和 ，對(duì)應(yīng)于非基本變量計(jì)算相應(yīng)的 。若所有 （對(duì)極小化問(wèn)題），則x為最優(yōu)解；否則轉(zhuǎn)至步驟（3）。（3）選取進(jìn)入