1、Page 22022年年7月月4日日10時時19分分 目標函數和約束條件都是線性的，像這類約束目標函數和約束條件都是線性的，像這類約束函數和目標函數都是為線性函數的優化問題，稱作函數和目標函數都是為線性函數的優化問題，稱作線性規劃問題。它的解法在理論和方法上都很成熟，線性規劃問題。它的解法在理論和方法上都很成熟，實際應用也很廣泛。雖然大多數工程設計是非線性實際應用也很廣泛。雖然大多數工程設計是非線性的，但是也有采用線性逼近方法求解的，但是也有采用線性逼近方法求解非線性問題的。非線性問題的。此外，線性規劃方法還常被用作解決非線性問題的此外，線性規劃方法還常被用作解決非線性問題的子問題的工具，如在

2、可行方向法中可行方向的尋求子問題的工具，如在可行方向法中可行方向的尋求就是采用線性規劃方法。當然，對于真正的線性優就是采用線性規劃方法。當然，對于真正的線性優化問題，線性規劃方法就更有用了。化問題，線性規劃方法就更有用了。Page 32022年年7月月4日日10時時19分分0024261553. .2max21212121xxxxxxt sxxz解：設生產解：設生產A、B兩產品分別兩產品分別為為x1, x2臺，則該問題的優化臺，則該問題的優化數學模型為：數學模型為：例例5-1： 某工廠要生產某工廠要生產A、B兩種產品，兩種產品，每生產一臺產品每生產一臺產品A 可獲產值可獲產值2萬元；萬元；需占

3、用一車間工作日需占用一車間工作日3天，二車間工天，二車間工作日作日6天；每生產一臺產品天；每生產一臺產品B 可獲產可獲產值值1萬元；需占用一車間工作日萬元；需占用一車間工作日5天，天，二車間工作日二車間工作日2天。現一車間可用于天。現一車間可用于生產生產A、B產品的時間產品的時間15天，二車間天，二車間可用于生產可用于生產A、B產品的時間產品的時間24天。天。試求出生產組織者安排試求出生產組織者安排A、B兩種產兩種產品的合理投資產數，以獲得最大的總品的合理投資產數，以獲得最大的總產值。產值。Page 42022年年7月月4日日10時時19分分例例5-2：生產甲種產品每件需使用材料生產甲種產品每

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

5、（工時約束）（工時約束）（電力約束）（電力約束）（材料約束）（材料約束）( (利潤最大利潤最大) )212()310300gXxx312()45200gXxxPage 52022年年7月月4日日10時時19分分例5-3：某廠生產甲、乙兩種產品，已知：兩種產品分別由兩條生產線生產。第一條生產甲，每天最多生產9件，第二條生產乙，每天最多生產7件；該廠僅有工人24名，生產甲每件用2工日，生產乙每件用3工日；產品甲、乙的單件利潤分別為40元和80元。問工廠如何組織生產才能獲得最大利潤？日利潤最大日利潤最大生產能力限制生產能力限制勞動力限制勞動力限制變量非負變量非負12121212max()408097

6、2324,0F Xxxxxxxx xs.t.Page 62022年年7月月4日日10時時19分分線性規劃數學模型的一般形式：線性規劃數學模型的一般形式：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)為轉軸元素，此時為轉軸元素，此時xt進入進入基，基， xs出基。這樣就完成了從一個基本解到另一個

7、基本出基。這樣就完成了從一個基本解到另一個基本解的轉換解的轉換staPage 262022年年7月月4日日10時時19分分1234512345541322058xxxxxxxxxx解：用解：用a11, a22作為軸元素進行兩次轉軸運算：作為軸元素進行兩次轉軸運算：例：給定如下方程組，試進行基本解的轉換運算。例：給定如下方程組，試進行基本解的轉換運算。134523450723120123420 xxxxxxxx 得到一組得到一組基本解：基本解： x1=-12 x2=-20 x3=x4=x5=0Page 272022年年7月月4日日10時時19分分用用a25作為軸元素進行第三次轉軸運算：作為軸元素

8、進行第三次轉軸運算：1234234531203441303544xxxxxxxx又得到一組又得到一組基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0此時此時x5進入基，進入基， x2出基。出基。Page 282022年年7月月4日日10時時19分分二、基本可行解到基本可行解的轉換二、基本可行解到基本可行解的轉換121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx111211001lnmnlmmlkknlmmmmmkknmaxa xa xbxxxaxaxa xb當已經得到一組基本可行解，若要求

9、把當已經得到一組基本可行解，若要求把xk選進基本變量，選進基本變量，并使下一組基本解是可行解的話并使下一組基本解是可行解的話Page 292022年年7月月4日日10時時19分分alk作為轉軸元素進行轉軸運算：作為轉軸元素進行轉軸運算：121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx1112110101lnmnlmlmnlklklkmmmmmkkknmaabxxaaaxxxaxaxa xxbPage 302022年年7月月4日日10時時19分分1121111111211000100nlnmmmkknlml

10、mmnlklklkkxxxaxa xa xbaabxxxxaaaxx1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa xPage 312022年年7月月4日日10時時19分分方程組第一行發生的變化：方程組第一行發生的變化：1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x1112111111121111111100()0()000lnnlnlmmmkmkknlklklmlmkmkkknklk

11、llklklkkbbaaaaxxxaaxxaaxaaaabxxxaxa xaxaaaaPage 322022年年7月月4日日10時時19分分若想用若想用xk取代取代xl成為可行解中的基本變量，成為可行解中的基本變量，即所選取的行即所選取的行要滿足條件要滿足條件: :0lka min ()lkllkbxa規則規則Page 332022年年7月月4日日10時時19分分例：例：1234234531203441303544xxxxxxxx基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0基本變量基本變量x1、x5 基本可行解的轉換：基本可行解的轉換： 1）x2、x4系數全部為負，只能選

12、取系數全部為負，只能選取x3所在的第所在的第3列為轉軸列列為轉軸列 2） , 由于由于 ，則取第一行為轉軸行，則取第一行為轉軸行, 于是取于是取a13=2為轉軸元素，使為轉軸元素，使x3取代取代x1成為基本變量。成為基本變量。3523minikiikbxaPage 342022年年7月月4日日10時時19分分經轉軸運算得：經轉軸運算得：12341245131302882373102882xxxxxxxx得基本可行解：得基本可行解： 351243122xxxxx Page 352022年年7月月4日日10時時19分分結論結論：可把松馳變量作為初始基本可行解中的基本變量。可把松馳變量作為初始基本可

13、行解中的基本變量。12312352100,1,2,3ixxxxxxxi 123412350520100,1,2,3,4,5ixxxxxxxxxi 451235,10,0 xxxxx三、初始基本可行解的求法三、初始基本可行解的求法原始約束條件原始約束條件:引入松馳變量引入松馳變量:可得一組基本可行解：可得一組基本可行解：Page 362022年年7月月4日日10時時19分分一、單純形法的基本思想一、單純形法的基本思想從一個初始基本可行解從一個初始基本可行解X X0 0出發，尋找目標函數有較出發，尋找目標函數有較大下降的一個新的基本可行解大下降的一個新的基本可行解X X1 1, ,代替原來的基本可

14、行代替原來的基本可行解解X X0 0，如此完成一次迭代。隨后作出判斷，如果未達到，如此完成一次迭代。隨后作出判斷，如果未達到最優解，則繼續迭代下去。因為基本可行解的數目有限，最優解，則繼續迭代下去。因為基本可行解的數目有限，所以經過有限次迭代一定能達到最優解。所以經過有限次迭代一定能達到最優解。采用單純形法求解線性規劃問題，主要應解決以下三個問題：采用單純形法求解線性規劃問題，主要應解決以下三個問題：（1）如何確定初始基本可行解；）如何確定初始基本可行解；（2）如何由一個基本可行解迭代出另一個基本可行解，）如何由一個基本可行解迭代出另一個基本可行解，同同時保證目標函數的下降性時保證目標函數的下

15、降性；（3）如何判斷一個基本可行解是否為最優解。）如何判斷一個基本可行解是否為最優解。Page 372022年年7月月4日日10時時19分分二二. .最優解規則最優解規則 對應一組基本可行解：對應一組基本可行解： 前前m個變量組成基本可行解的基本變量個變量組成基本可行解的基本變量相應的目標函數值為相應的目標函數值為: :1 122( )00mmf xc bc bc b12 ,0,0TmXb bb1mlllcbPage 382022年年7月月4日日10時時19分分經過轉軸運算得到另經過轉軸運算得到另一組基本可行解為一組基本可行解為:111222kkssskmmmkkxbaxbaxXbaxbax其

16、中：其中：0 ()ssskxbasm 進基變量進基變量xk出基變量出基變量xsPage 392022年年7月月4日日10時時19分分對應的目標函數為對應的目標函數為: :111222( )()()()()00kkssskmmmkkf xc bac bac bacbac11mmllllkkllcbc ac1( )mkllklf xcc a( )kf xrPage 402022年年7月月4日日10時時19分分由于要求由于要求( )( )( )kf xf xrf x0kr結論結論: :一旦所有的一旦所有的 , ,即可停止即可停止 轉軸運算轉軸運算, ,對應的可行解就是對應的可行解就是最優解。最優解。r是是 對線性規劃問題的解進行最優性檢驗的標對線性規劃問題的解進行最優性檢驗的標 志，稱之為檢驗數。志，稱之為檢驗數。10mkkllklrcc a010mkkllklrcc aPage 412022年年7月月4日日10時時19分分1minmkllkklcc a具體計算時應選取具體計算時應選取: :由于有可能同時有幾組由于