第5章線性規(guī)劃

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

2、的尋求子問題的工具，如在可行方向法中可行方向的尋求就是采用線性規(guī)劃方法。當然，對于真正的線性優(yōu)就是采用線性規(guī)劃方法。當然，對于真正的線性優(yōu)化問題，線性規(guī)劃方法就更有用了。化問題，線性規(guī)劃方法就更有用了。*0024261553. .2max21212121xxxxxxtsxxz解：設生產(chǎn)解：設生產(chǎn)A、B兩產(chǎn)品分別兩產(chǎn)品分別為為x1, x2臺，則該問題的優(yōu)化臺，則該問題的優(yōu)化數(shù)學模型為：數(shù)學模型為：例例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天，二車間工天，二車間工作日作日6天；

3、每生產(chǎn)一臺產(chǎn)品天；每生產(chǎn)一臺產(chǎn)品B 可獲產(chǎn)可獲產(chǎn)值值1萬元；需占用一車間工作日萬元；需占用一車間工作日5天，天，二車間工作日二車間工作日2天。現(xiàn)一車間可用于天?，F(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)值。*例例5-2：生產(chǎn)甲種產(chǎn)品每件需使用材料生產(chǎn)甲種產(chǎn)品每件需使用材料9kg9kg、3 3個工時、個工時、4kw4kw電，獲電，獲利潤利潤6060元。生產(chǎn)乙種產(chǎn)品每件需用材料元。生

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

5、gXxx312()45200gXxx*將其化成線性規(guī)劃標準形式：將其化成線性規(guī)劃標準形式：12394360 xxx124310300 xxx12545200 xxx求求T12xxx12min( )60120f xxx 使使且滿足且滿足0(1,2,3,4,5)ixi *例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)能力限制生產(chǎn)能力限制勞動力限制勞動

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

7、？建立該問表所示。試問公司應如何安排調(diào)運計劃，才能獲利最大？建立該問題的數(shù)學模型。題的數(shù)學模型。鋼材鋼材鋁材鋁材銅材銅材甲甲260300400乙乙210250550丙丙180400350物資物資獲利獲利地區(qū)地區(qū)*建模例建模例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元元/件；合同乙為：件；合同乙為：B產(chǎn)品產(chǎn)品500件，單件價格件，單件價格為為400元，違約金為元，違約金為120元

8、元/件；合同丙為：件；合同丙為：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)過程所需工時以及原材料的情況見下表。試以利潤為目標，建立該工廠的生產(chǎn)計劃線性規(guī)劃模型表。試以利潤為目標，建立該工廠的生產(chǎn)計劃線性規(guī)劃模型 。工序工序1工序工序2工序工序3原材料原材料1 原材料原材料2其他成本其他成本產(chǎn)品產(chǎn)品A /件件2323410產(chǎn)品產(chǎn)品B /件件1132310產(chǎn)品產(chǎn)品C /件件2124210總工時或原

9、材料總工時或原材料460040006000100008000工時或原材料成本工時或原材料成本（元）（元）1510102040*建模例建模例3： 成批生產(chǎn)企業(yè)年度生產(chǎn)計劃的按月分配成批生產(chǎn)企業(yè)年度生產(chǎn)計劃的按月分配 。在成批生產(chǎn)的機械制造企業(yè)中，不同產(chǎn)品勞動量的結(jié)構(gòu)上可能在成批生產(chǎn)的機械制造企業(yè)中，不同產(chǎn)品勞動量的結(jié)構(gòu)上可能有很大差別。如：某種產(chǎn)品要求較多的車床加工時間，另一種有很大差別。如：某種產(chǎn)品要求較多的車床加工時間，另一種產(chǎn)品的勞動量可能集中在銑床和其他機床上。因此，企業(yè)在按產(chǎn)品的勞動量可能集中在銑床和其他機床上。因此，企業(yè)在按月分配年度計劃任務時，應考慮到各種設備的均衡且最大負荷。月分

10、配年度計劃任務時，應考慮到各種設備的均衡且最大負荷。 在年度計劃按月分配時一般要考慮在年度計劃按月分配時一般要考慮: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ù)準備等方面原因，）由于生產(chǎn)技術(shù)準備等方面原因，某些產(chǎn)品要在某個月后才能投產(chǎn)；某些產(chǎn)品要在某個月后才能投產(chǎn)；4）根據(jù)合同要求，某些產(chǎn)）根據(jù)合同要求，某些產(chǎn)品要求在年初交貨；品要求在年初交貨；5）批量小的產(chǎn)品盡可能集中在一個月或）批量小的產(chǎn)品盡可能集中在一個月或幾個月內(nèi)生產(chǎn)出來，以

11、便減少各個月的品種數(shù)量等等。如何在幾個月內(nèi)生產(chǎn)出來，以便減少各個月的品種數(shù)量等等。如何在滿足上述條件的基礎上，使設備均衡負荷且最大負荷。滿足上述條件的基礎上，使設備均衡負荷且最大負荷。*線性規(guī)劃數(shù)學模型的一般形式：線性規(guī)劃數(shù)學模型的一般形式：11 11221121 1222221 122nnnnmmmnnma xa xa xba xa xa xba xaxaxb求求T12nxx xx1122( )minnnfxc xc xc x使使且滿足且滿足0(1,2, )ixin 0(1,2,)jbjm 說明：說明：1 1）m=n,m=n,唯一解唯一解2 2）mn,mn,無解無解3 3）mn,mm)為轉(zhuǎn)軸

12、元素，此時為轉(zhuǎn)軸元素，此時xt進入進入基，基， xs出基。這樣就完成了從一個基本解到另一個基本出基。這樣就完成了從一個基本解到另一個基本解的轉(zhuǎn)換解的轉(zhuǎn)換sta*1234512345541322058xxxxxxxxxx解：用解：用a11, a22作為軸元素進行兩次轉(zhuǎn)軸運算：作為軸元素進行兩次轉(zhuǎn)軸運算：例：給定如下方程組，試進行基本解的轉(zhuǎn)換運算。例：給定如下方程組，試進行基本解的轉(zhuǎn)換運算。134523450723120123420 xxxxxxxx 得到一組得到一組基本解：基本解： x1=-12 x2=-20 x3=x4=x5=0*用用a25作為軸元素進行第三次轉(zhuǎn)軸運算：作為軸元素進行第三次轉(zhuǎn)軸

13、運算：1234234531203441303544xxxxxxxx又得到一組又得到一組基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0此時此時x5進入基，進入基， x2出基。出基。*二、從一個基本可行解轉(zhuǎn)到另一個基本可行解二、從一個基本可行解轉(zhuǎn)到另一個基本可行解121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx111211001lnmnlmmlkknlmmmmmkknmaxa xa xbxxxaxaxa xb當已經(jīng)得到一組基本可行解，若要求把當已經(jīng)得到一組基本可行解，若要求把xk選進基本變

14、量，選進基本變量，并使下一組基本解是可行解的話，并使下一組基本解是可行解的話，則在第則在第k k列要選取不為列要選取不為任何負值的元素作為轉(zhuǎn)軸元素任何負值的元素作為轉(zhuǎn)軸元素*alk作為轉(zhuǎn)軸元素進行轉(zhuǎn)軸運算：作為轉(zhuǎn)軸元素進行轉(zhuǎn)軸運算：121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx1112110101lnmnlmlmnlklklkmmmmmkkknmaabxxaaaxxxaxaxa xxb*1121111111211000100nlnmmmkknlmlmmnlklklkkxxxaxa xa xbaabxxx

15、xaaaxx1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x*方程組第一行發(fā)生的變化：方程組第一行發(fā)生的變化：1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x1112111111121111111100()0()000lnnlnlmmmkmkknlklklmlmkmkkknklkllklklkkbbaaaaxxxaaxxaaxaaaabxxxaxa xaxaaaa*alk作為軸元素，作

16、為軸元素，xk選進基本變量后，選進基本變量后， xk的取值由零變成了的取值由零變成了一個正值一個正值 ，則原來各基本變量的取值變?yōu)?，則原來各基本變量的取值變?yōu)? :llkba11111222220000lllkkllkkkkkkkkmmmkkmmkxxba xbaxba xbaxbaxbaxba xba 若是基本可行解若是基本可行解, 應該應該保證保證各差值最小者為零各差值最小者為零 :min ()0iikibaminikiikbxa 決定了離基變量為決定了離基變量為xi*若想用若想用xk取代取代xl成為可行解中的基本變量，就應該選成為可行解中的基本變量，就應該選 所對應的行成為轉(zhuǎn)軸行，即所選

17、取的行要滿所對應的行成為轉(zhuǎn)軸行，即所選取的行要滿足條件足條件: :0llkba0lka min ()lkllkbxa規(guī)則規(guī)則*例：例：1234234531203441303544xxxxxxxx基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0基本變量基本變量x1、x5 基本可行解的轉(zhuǎn)換：基本可行解的轉(zhuǎn)換： 1）x2、x4系數(shù)全部為負，只能選取系數(shù)全部為負，只能選取x3所在的第所在的第3列為轉(zhuǎn)軸行列為轉(zhuǎn)軸行 2） , 由于由于 ，則取第一行為轉(zhuǎn)軸行，則取第一行為轉(zhuǎn)軸行, 于是取于是取a13=2為轉(zhuǎn)軸元素，使為轉(zhuǎn)軸元素，使x3取代取代x1成為基本變量。成為基本變量。3523min

18、ikiikbxa*經(jīng)轉(zhuǎn)軸運算得：經(jīng)轉(zhuǎn)軸運算得：12341245131302882373102882xxxxxxxx得基本可行解：得基本可行解： 351243122xxxxx *結(jié)論結(jié)論：可把松馳變量作為初始基本可行解中的一部分基本可把松馳變量作為初始基本可行解中的一部分基本 變量。變量。12312352100,1,2,3ixxxxxxxi 123412350520100,1,2,3,4,5ixxxxxxxxxi 451235,10,0 xxxxx三、初始基本可行解的求法三、初始基本可行解的求法原始約束條件原始約束條件:引入松馳變量引入松馳變量:可得一組基本可行解：可得一組基本可行解：*一、單純

19、形法的基本思想從一個初始基本可行解X0出發(fā)，尋找目標函數(shù)有較大下降的一個新的基本可行解X1,代替原來的基本可行解X0，如此完成一次迭代。隨后作出判斷，如果未達到最優(yōu)解，則繼續(xù)迭代下去。因為基本可行解的數(shù)目有限，所以經(jīng)過有限次迭代一定能達到最優(yōu)解。采用單純形法求解線性規(guī)劃問題，主要應解決以下三個問題：采用單純形法求解線性規(guī)劃問題，主要應解決以下三個問題：（1）如何確定初始基本可行解；）如何確定初始基本可行解；（2）如何由一個基本可行解迭代出另一個基本可行解，）如何由一個基本可行解迭代出另一個基本可行解，同同時保證目標函數(shù)的下降性時保證目標函數(shù)的下降性；（3）如何判斷一個基本可行解是否為最優(yōu)解。）

20、如何判斷一個基本可行解是否為最優(yōu)解。*二二. .最優(yōu)解規(guī)則最優(yōu)解規(guī)則 對應一組基本可行解：對應一組基本可行解： 前前m個變量組成基本可行解的基本變量個變量組成基本可行解的基本變量相應的目標函數(shù)值為相應的目標函數(shù)值為: :1 122( )00mmf xcbc bc b12 ,0,0TmXb bb1mlllcb*經(jīng)過轉(zhuǎn)軸運算得到另經(jīng)過轉(zhuǎn)軸運算得到另一組基本可行解為一組基本可行解為:111222kkssskmmmkkxbaxbaxXbaxbax其中：其中：0 ()ssskxbasm 進基變量進基變量xk出基變量出基變量xs*對應的目標函數(shù)為對應的目標函數(shù)為: :111222( )()()()()00

21、kkssskmmmkkf xc bac bac bacbac11mmllllkkllcbc ac1( )mkllklf xcc a( )kf xr*由于要求由于要求( )( )( )kf xf xrf x0kr結(jié)論結(jié)論: :一旦所有的一旦所有的 , , 即可停止即可停止 轉(zhuǎn)軸運算轉(zhuǎn)軸運算, ,對應的可行解就是對應的可行解就是最優(yōu)解。最優(yōu)解。r是是 對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標 志，稱之為檢驗數(shù)。志，稱之為檢驗數(shù)。10mkkllklrcc a010mkkllklrcc a*1minmkllkklcc a具體計算時應選取具體計算時應選取: :由于有可能同

22、時有幾組由于有可能同時有幾組 都為負值都為負值1mkkllklrcc a最速變化規(guī)則最速變化規(guī)則( )( )( )kf xf xrf x*1minmkllkklcc a1）最速變化規(guī)則決定）最速變化規(guī)則決定進基的進基的非基本變量非基本變量結(jié)論結(jié)論：min ()lllkba2） 規(guī)則決定了規(guī)則決定了出基的出基的基本變量基本變量3）若對基本可行解）若對基本可行解X，所有檢驗數(shù)，所有檢驗數(shù)rk 0，則，則X 為最優(yōu)解。為最優(yōu)解。 *例例5-35-3某建筑單位擬蓋一批二人、三人和四人的宿舍單元，要某建筑單位擬蓋一批二人、三人和四人的宿舍單元，要確定每一種宿舍單元的數(shù)目，以獲得最大利潤。其限制條確定每一種宿舍單元的數(shù)目，以獲得最大利潤。其限制條件如下：件如下：1 1）預算不能超過）預算不能超過90009000千元。千元。2 2）宿舍單元總數(shù)不）宿舍單元總數(shù)不得少于得少于350350套。套。3 3）每類宿舍單元的百分比為：二人的不超）每類宿舍單元的百分比為：二人的不超過總數(shù)的過總數(shù)的20%20%，三人的不超過總數(shù)的，三人的不超過總數(shù)的60%60%，四人的不超過總，四人的不超過總數(shù)的數(shù)的40%40%（百分比總和超過（百分比總和超過100100，這是上限）。，這是上限）。4 4）建造價格）建造價格為：二人的宿舍單