1、機(jī)械優(yōu)化設(shè)計第五章第五章 線性規(guī)劃線性規(guī)劃機(jī)械優(yōu)化設(shè)計* 目標(biāo)函數(shù)和約束條件都是線性的，像這類約束目標(biāo)函數(shù)和約束條件都是線性的，像這類約束函數(shù)和目標(biāo)函數(shù)都是為線性函數(shù)的優(yōu)化問題，稱作函數(shù)和目標(biāo)函數(shù)都是為線性函數(shù)的優(yōu)化問題，稱作線性規(guī)劃問題。它的解法在理論和方法上都很成熟，線性規(guī)劃問題。它的解法在理論和方法上都很成熟，實際應(yīng)用也很廣泛。雖然大多數(shù)工程設(shè)計是非線性實際應(yīng)用也很廣泛。雖然大多數(shù)工程設(shè)計是非線性的，但是也有采用線性逼近方法求解的，但是也有采用線性逼近方法求解非線性問題的。非線性問題的。此外，線性規(guī)劃方法還常被用作解決非線性問題的此外，線性規(guī)劃方法還常被用作解決非線性問題的子問題的工具，

2、如在可行方向法中可行方向的尋求子問題的工具，如在可行方向法中可行方向的尋求就是采用線性規(guī)劃方法。當(dāng)然，對于真正的線性優(yōu)就是采用線性規(guī)劃方法。當(dāng)然，對于真正的線性優(yōu)化問題，線性規(guī)劃方法就更有用了。化問題，線性規(guī)劃方法就更有用了。機(jī)械優(yōu)化設(shè)計*0024261553. .2max21212121xxxxxxtsxxz解：設(shè)生產(chǎn)解：設(shè)生產(chǎn)A、B兩產(chǎn)品分別兩產(chǎn)品分別為為x1, x2臺，則該問題的優(yōu)化臺，則該問題的優(yōu)化數(shù)學(xué)模型為：數(shù)學(xué)模型為：例例5-1： 某工廠要生產(chǎn)某工廠要生產(chǎn)A、B兩種產(chǎn)品，兩種產(chǎn)品，每生產(chǎn)一臺產(chǎn)品每生產(chǎn)一臺產(chǎn)品A 可獲產(chǎn)值可獲產(chǎn)值2萬元；萬元；需占用一車間工作日需占用一車間工作日3天

3、，二車間工天，二車間工作日作日6天；每生產(chǎn)一臺產(chǎn)品天；每生產(chǎn)一臺產(chǎn)品B 可獲產(chǎn)可獲產(chǎn)值值1萬元；需占用一車間工作日萬元；需占用一車間工作日5天，天，二車間工作日二車間工作日2天。現(xiàn)一車間可用于天。現(xiàn)一車間可用于生產(chǎn)生產(chǎn)A、B產(chǎn)品的時間產(chǎn)品的時間15天，二車間天，二車間可用于生產(chǎn)可用于生產(chǎn)A、B產(chǎn)品的時間產(chǎn)品的時間24天。天。試求出生產(chǎn)組織者安排試求出生產(chǎn)組織者安排A、B兩種產(chǎn)兩種產(chǎn)品的合理投資產(chǎn)數(shù)，以獲得最大的總品的合理投資產(chǎn)數(shù)，以獲得最大的總產(chǎn)值。產(chǎn)值。機(jī)械優(yōu)化設(shè)計*例例5-2：生產(chǎn)甲種產(chǎn)品每件需使用材料生產(chǎn)甲種產(chǎn)品每件需使用材料9kg9kg、3 3個工時、個工時、4kw4kw電，獲電，獲利

4、潤利潤6060元。生產(chǎn)乙種產(chǎn)品每件需用材料元。生產(chǎn)乙種產(chǎn)品每件需用材料4kg4kg、1010個工時、個工時、5kw5kw電，電，可獲利可獲利120120元。若每天能供應(yīng)材料元。若每天能供應(yīng)材料360kg360kg，有，有300300個工時，能供個工時，能供200kw200kw電。試確定兩種產(chǎn)品每天的產(chǎn)量，使每天可能獲得的電。試確定兩種產(chǎn)品每天的產(chǎn)量，使每天可能獲得的利潤利潤最大最大？ 12,x x1212( ,)60120maxf x xxx112()94360gXxx分析：分析：每天生產(chǎn)的每天生產(chǎn)的分別為分別為 件件 （工時約束）（工時約束）（電力約束）（電力約束）（材料約束）（材料約束）(

5、 (利潤最大利潤最大) )212()310300gXxx312()45200gXxx機(jī)械優(yōu)化設(shè)計*將其化成線性規(guī)劃標(biāo)準(zhǔn)形式：將其化成線性規(guī)劃標(biāo)準(zhǔn)形式：12394360 xxx124310300 xxx12545200 xxx求求T12xxx12min( )60120f xxx 使使且滿足且滿足0(1,2,3,4,5)ixi 機(jī)械優(yōu)化設(shè)計*例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)才能獲

6、得最大利潤？機(jī)械優(yōu)化設(shè)計*日利潤最大日利潤最大生產(chǎn)能力限制生產(chǎn)能力限制勞動力限制勞動力限制變量非負(fù)變量非負(fù).,21xx解解: 設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為0,2432798040)(max212121221xxxxxxRDXxxXFs.t.機(jī)械優(yōu)化設(shè)計*建模例建模例1： 某公司有鋼材、鋁材、銅材某公司有鋼材、鋁材、銅材1200t，800t和和650t，擬調(diào)往，擬調(diào)往物資緊張的地區(qū)甲、乙、丙。已知甲、乙、丙對上述物資的總需求物資緊張的地區(qū)甲、乙、丙。已知甲、乙、丙對上述物資的總需求分別為：分別為：900t，800t和和1000t。各種物資在各地銷售每噸的獲利如

7、下。各種物資在各地銷售每噸的獲利如下表所示。試問公司應(yīng)如何安排調(diào)運計劃，才能獲利最大？建立該問表所示。試問公司應(yīng)如何安排調(diào)運計劃，才能獲利最大？建立該問題的數(shù)學(xué)模型。題的數(shù)學(xué)模型。鋼材鋼材鋁材鋁材銅材銅材甲甲260300400乙乙210250550丙丙180400350物資物資獲利獲利地區(qū)地區(qū)機(jī)械優(yōu)化設(shè)計*建模例建模例2： 某工廠生產(chǎn)某工廠生產(chǎn)A、B、C三種產(chǎn)品，現(xiàn)根據(jù)訂貨合同以及生產(chǎn)三種產(chǎn)品，現(xiàn)根據(jù)訂貨合同以及生產(chǎn)狀況制定狀況制定5月份的生產(chǎn)計劃，已知合同甲為：月份的生產(chǎn)計劃，已知合同甲為：A產(chǎn)品產(chǎn)品1000件，單件價件，單件價格為格為500元，違約金為元，違約金為100元元/件；合同乙為：

8、件；合同乙為：B產(chǎn)品產(chǎn)品500件，單件價格件，單件價格為為400元，違約金為元，違約金為120元元/件；合同丙為：件；合同丙為：B產(chǎn)品產(chǎn)品600件，單件價格為件，單件價格為420元，違約金為元，違約金為130元元/件；件；C產(chǎn)品產(chǎn)品600件，單件價格為件，單件價格為400元，違約元，違約金為金為90元元/件；有關(guān)各產(chǎn)品生產(chǎn)過程所需工時以及原材料的情況見下件；有關(guān)各產(chǎn)品生產(chǎn)過程所需工時以及原材料的情況見下表。試以利潤為目標(biāo)，建立該工廠的生產(chǎn)計劃線性規(guī)劃模型表。試以利潤為目標(biāo)，建立該工廠的生產(chǎn)計劃線性規(guī)劃模型 。工序工序1工序工序2工序工序3原材料原材料1 原材料原材料2其他成本其他成本產(chǎn)品產(chǎn)品A

9、 /件件2323410產(chǎn)品產(chǎn)品B /件件1132310產(chǎn)品產(chǎn)品C /件件2124210總工時或原材料總工時或原材料460040006000100008000工時或原材料成本工時或原材料成本（元）（元）1510102040機(jī)械優(yōu)化設(shè)計*建模例建模例3： 成批生產(chǎn)企業(yè)年度生產(chǎn)計劃的按月分配成批生產(chǎn)企業(yè)年度生產(chǎn)計劃的按月分配 。在成批生產(chǎn)的機(jī)械制造企業(yè)中，不同產(chǎn)品勞動量的結(jié)構(gòu)上可能在成批生產(chǎn)的機(jī)械制造企業(yè)中，不同產(chǎn)品勞動量的結(jié)構(gòu)上可能有很大差別。如：某種產(chǎn)品要求較多的車床加工時間，另一種有很大差別。如：某種產(chǎn)品要求較多的車床加工時間，另一種產(chǎn)品的勞動量可能集中在銑床和其他機(jī)床上。因此，企業(yè)在按產(chǎn)品的

10、勞動量可能集中在銑床和其他機(jī)床上。因此，企業(yè)在按月分配年度計劃任務(wù)時，應(yīng)考慮到各種設(shè)備的均衡且最大負(fù)荷。月分配年度計劃任務(wù)時，應(yīng)考慮到各種設(shè)備的均衡且最大負(fù)荷。 在年度計劃按月分配時一般要考慮在年度計劃按月分配時一般要考慮:1）從數(shù)量和品種上保從數(shù)量和品種上保證年度計劃的完成；證年度計劃的完成；2）成批的產(chǎn)品盡可能在各個月內(nèi)均衡生）成批的產(chǎn)品盡可能在各個月內(nèi)均衡生產(chǎn)或集中在幾個月內(nèi)生產(chǎn)；產(chǎn)或集中在幾個月內(nèi)生產(chǎn)；3）由于生產(chǎn)技術(shù)準(zhǔn)備等方面原因，）由于生產(chǎn)技術(shù)準(zhǔn)備等方面原因，某些產(chǎn)品要在某個月后才能投產(chǎn)；某些產(chǎn)品要在某個月后才能投產(chǎn)；4）根據(jù)合同要求，某些產(chǎn)）根據(jù)合同要求，某些產(chǎn)品要求在年初交貨；

11、品要求在年初交貨；5）批量小的產(chǎn)品盡可能集中在一個月或）批量小的產(chǎn)品盡可能集中在一個月或幾個月內(nèi)生產(chǎn)出來，以便減少各個月的品種數(shù)量等等。如何在幾個月內(nèi)生產(chǎn)出來，以便減少各個月的品種數(shù)量等等。如何在滿足上述條件的基礎(chǔ)上，使設(shè)備均衡負(fù)荷且最大負(fù)荷。滿足上述條件的基礎(chǔ)上，使設(shè)備均衡負(fù)荷且最大負(fù)荷。機(jī)械優(yōu)化設(shè)計*線性規(guī)劃數(shù)學(xué)模型的一般形式：線性規(guī)劃數(shù)學(xué)模型的一般形式：11 11221121 1222221 122nnnnmmmnnma xa xa xba xa xa xba xaxaxb求求T12nxx xx1122( )minnnfxc xc xc x使使且滿足且滿足0(1,2, )ixin 0(1

12、,2,)jbjm 說明：說明：1 1）m=n,m=n,唯一解唯一解2 2）mn,mn,無解無解3 3）mn,mm)為轉(zhuǎn)軸元素，此時為轉(zhuǎn)軸元素，此時xt進(jìn)入進(jìn)入基，基， xs出基。這樣就完成了從一個基本解到另一個基本出基。這樣就完成了從一個基本解到另一個基本解的轉(zhuǎn)換解的轉(zhuǎn)換sta機(jī)械優(yōu)化設(shè)計*1234512345541322058xxxxxxxxxx解：用解：用a11, a22作為軸元素進(jìn)行兩次轉(zhuǎn)軸運算：作為軸元素進(jìn)行兩次轉(zhuǎn)軸運算：例：給定如下方程組，試進(jìn)行基本解的轉(zhuǎn)換運算。例：給定如下方程組，試進(jìn)行基本解的轉(zhuǎn)換運算。134523450723120123420 xxxxxxxx 得到一組得到一組

13、基本解：基本解： x1=-12 x2=-20 x3=x4=x5=0機(jī)械優(yōu)化設(shè)計*用用a25作為軸元素進(jìn)行第三次轉(zhuǎn)軸運算：作為軸元素進(jìn)行第三次轉(zhuǎn)軸運算：1234234531203441303544xxxxxxxx又得到一組又得到一組基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0此時此時x5進(jìn)入基，進(jìn)入基， x2出基。出基。機(jī)械優(yōu)化設(shè)計*二、從一個基本可行解轉(zhuǎn)到另一個基本可行解二、從一個基本可行解轉(zhuǎn)到另一個基本可行解121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx111211001lnmn

14、lmmlkknlmmmmmkknmaxa xa xbxxxaxaxa xb當(dāng)已經(jīng)得到一組基本可行解，若要求把當(dāng)已經(jīng)得到一組基本可行解，若要求把xk選進(jìn)基本變量，選進(jìn)基本變量，并使下一組基本解是可行解的話，并使下一組基本解是可行解的話，則在第則在第k k列要選取不為列要選取不為任何負(fù)值的元素作為轉(zhuǎn)軸元素任何負(fù)值的元素作為轉(zhuǎn)軸元素機(jī)械優(yōu)化設(shè)計*alk作為轉(zhuǎn)軸元素進(jìn)行轉(zhuǎn)軸運算：作為轉(zhuǎn)軸元素進(jìn)行轉(zhuǎn)軸運算：121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx1112110101lnmnlmlmnlklklkmmmmmk

15、kknmaabxxaaaxxxaxaxa xxb機(jī)械優(yōu)化設(shè)計*1121111111211000100nlnmmmkknlmlmmnlklklkkxxxaxa xa xbaabxxxxaaaxx1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x機(jī)械優(yōu)化設(shè)計*方程組第一行發(fā)生的變化：方程組第一行發(fā)生的變化：1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x1112111111121111111

16、100()0()000lnnlnlmmmkmkknlklklmlmkmkkknklkllklklkkbbaaaaxxxaaxxaaxaaaabxxxaxa xaxaaaa機(jī)械優(yōu)化設(shè)計*alk作為軸元素，作為軸元素，xk選進(jìn)基本變量后，選進(jìn)基本變量后， xk的取值由零變成了的取值由零變成了一個正值一個正值 ，則原來各基本變量的取值變?yōu)椋瑒t原來各基本變量的取值變?yōu)? :llkba11111222220000lllkkllkkkkkkkkmmmkkmmkxxba xbaxba xbaxbaxbaxba xba 若是基本可行解若是基本可行解, 應(yīng)該應(yīng)該保證保證各差值最小者為零各差值最小者為零 :min

17、 ()0iikibaminikiikbxa 決定了離基變量為決定了離基變量為xi機(jī)械優(yōu)化設(shè)計*若想用若想用xk取代取代xl成為可行解中的基本變量，就應(yīng)該選成為可行解中的基本變量，就應(yīng)該選 所對應(yīng)的行成為轉(zhuǎn)軸行，即所選取的行要滿所對應(yīng)的行成為轉(zhuǎn)軸行，即所選取的行要滿足條件足條件: :0llkba0lka min ()lkllkbxa規(guī)則規(guī)則機(jī)械優(yōu)化設(shè)計*例：例：1234234531203441303544xxxxxxxx基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0基本變量基本變量x1、x5 基本可行解的轉(zhuǎn)換：基本可行解的轉(zhuǎn)換： 1）x2、x4系數(shù)全部為負(fù)，只能選取系數(shù)全部為

18、負(fù)，只能選取x3所在的第所在的第3列為轉(zhuǎn)軸行列為轉(zhuǎn)軸行 2） , 由于由于 ，則取第一行為轉(zhuǎn)軸行，則取第一行為轉(zhuǎn)軸行, 于是取于是取a13=2為轉(zhuǎn)軸元素，使為轉(zhuǎn)軸元素，使x3取代取代x1成為基本變量。成為基本變量。3523minikiikbxa機(jī)械優(yōu)化設(shè)計*經(jīng)轉(zhuǎn)軸運算得：經(jīng)轉(zhuǎn)軸運算得：12341245131302882373102882xxxxxxxx得基本可行解：得基本可行解： 351243122xxxxx 機(jī)械優(yōu)化設(shè)計*結(jié)論結(jié)論：可把松馳變量作為初始基本可行解中的一部分基本可把松馳變量作為初始基本可行解中的一部分基本 變量。變量。12312352100,1,2,3ixxxxxxxi 123

19、412350520100,1,2,3,4,5ixxxxxxxxxi 451235,10,0 xxxxx三、初始基本可行解的求法三、初始基本可行解的求法原始約束條件原始約束條件:引入松馳變量引入松馳變量:可得一組基本可行解：可得一組基本可行解：機(jī)械優(yōu)化設(shè)計*一、單純形法的基本思想從一個初始基本可行解X0出發(fā)，尋找目標(biāo)函數(shù)有較大下降的一個新的基本可行解X1,代替原來的基本可行解X0，如此完成一次迭代。隨后作出判斷，如果未達(dá)到最優(yōu)解，則繼續(xù)迭代下去。因為基本可行解的數(shù)目有限，所以經(jīng)過有限次迭代一定能達(dá)到最優(yōu)解。采用單純形法求解線性規(guī)劃問題，主要應(yīng)解決以下三個問題：采用單純形法求解線性規(guī)劃問題，主要應(yīng)

20、解決以下三個問題：（1）如何確定初始基本可行解；）如何確定初始基本可行解；（2）如何由一個基本可行解迭代出另一個基本可行解，）如何由一個基本可行解迭代出另一個基本可行解，同同時保證目標(biāo)函數(shù)的下降性時保證目標(biāo)函數(shù)的下降性；（3）如何判斷一個基本可行解是否為最優(yōu)解。）如何判斷一個基本可行解是否為最優(yōu)解。機(jī)械優(yōu)化設(shè)計*二二. .最優(yōu)解規(guī)則最優(yōu)解規(guī)則 對應(yīng)一組基本可行解：對應(yīng)一組基本可行解： 前前m個變量組成基本可行解的基本變量個變量組成基本可行解的基本變量相應(yīng)的目標(biāo)函數(shù)值為相應(yīng)的目標(biāo)函數(shù)值為: :1 122( )00mmf xcbc bc b12 ,0,0TmXb bb1mlllcb機(jī)械優(yōu)化設(shè)計*經(jīng)

21、過轉(zhuǎn)軸運算得到另經(jīng)過轉(zhuǎn)軸運算得到另一組基本可行解為一組基本可行解為:111222kkssskmmmkkxbaxbaxXbaxbax其中：其中：0 ()ssskxbasm 進(jìn)基變量進(jìn)基變量xk出基變量出基變量xs機(jī)械優(yōu)化設(shè)計*對應(yīng)的目標(biāo)函數(shù)為對應(yīng)的目標(biāo)函數(shù)為: :111222( )()()()()00kkssskmmmkkf xc bac bac bacbac11mmllllkkllcbc ac1( )mkllklf xcc a( )kf xr機(jī)械優(yōu)化設(shè)計*由于要求由于要求( )( )( )kf xf xrf x0kr結(jié)論結(jié)論: :一旦所有的一旦所有的 , , 即可停止即可停止 轉(zhuǎn)軸運算轉(zhuǎn)軸運算

22、, ,對應(yīng)的可行解就是對應(yīng)的可行解就是最優(yōu)解。最優(yōu)解。r是是 對線性規(guī)劃問題的解進(jìn)行最優(yōu)性檢驗的標(biāo)對線性規(guī)劃問題的解進(jìn)行最優(yōu)性檢驗的標(biāo) 志，稱之為檢驗數(shù)。志，稱之為檢驗數(shù)。10mkkllklrcc a010mkkllklrcc a機(jī)械優(yōu)化設(shè)計*1minmkllkklcc a具體計算時應(yīng)選取具體計算時應(yīng)選取: :由于有可能同時有幾組由于有可能同時有幾組 都為負(fù)值都為負(fù)值1mkkllklrcc a最速變化規(guī)則最速變化規(guī)則( )( )( )kf xf xrf x機(jī)械優(yōu)化設(shè)計*1minmkllkklcc a1）最速變化規(guī)則決定）最速變化規(guī)則決定進(jìn)基的進(jìn)基的非基本變量非基本變量結(jié)論結(jié)論：min ()ll

23、lkba2） 規(guī)則決定了規(guī)則決定了出基的出基的基本變量基本變量3）若對基本可行解）若對基本可行解X，所有檢驗數(shù)，所有檢驗數(shù)rk 0，則，則X 為最優(yōu)解。為最優(yōu)解。 機(jī)械優(yōu)化設(shè)計*例例5-35-3某建筑單位擬蓋一批二人、三人和四人的宿舍單元，要某建筑單位擬蓋一批二人、三人和四人的宿舍單元，要確定每一種宿舍單元的數(shù)目，以獲得最大利潤。其限制條確定每一種宿舍單元的數(shù)目，以獲得最大利潤。其限制條件如下：件如下：1 1）預(yù)算不能超過）預(yù)算不能超過90009000千元。千元。2 2）宿舍單元總數(shù)不）宿舍單元總數(shù)不得少于得少于350350套。套。3 3）每類宿舍單元的百分比為：二人的不超）每類宿舍單元的百分比為：二人的不超過總數(shù)的過總數(shù)的20%20%，三人的不超過總數(shù)的，三人的不超過總數(shù)的60%60%，四人的不超過總，四人的不超過總數(shù)的數(shù)的40%40%（百分比總和超過（百分比總和超過100100，這是上限）。，這是上限）。4 4）建造價格）建造價格為：二人的宿