1、1第第2章章單純形法單純形法楊曉藝 數學建模（公修）2主要內容主要內容單純形法的引入單純形法的引入2.1單純形法的計算步驟單純形法的計算步驟2.2單純形法的進一步討論單純形法的進一步討論2.3楊曉藝 數學建模（公修）3 先找到一個基可行解（先找到一個基可行解（），），其是否為其是否為最優解，否則，再找到一個使目標函數所改進的基可行解，最優解，否則，再找到一個使目標函數所改進的基可行解，再進行檢驗，反復再進行檢驗，反復，直至找到最優解或判定問題無界。，直至找到最優解或判定問題無界。楊曉藝 數學建模（公修）4 某廠生產兩種產品，下表給某廠生產兩種產品，下表給出了單位產品所需資源及單位產品出了單位產

2、品所需資源及單位產品利潤利潤 問：應如何安排生產計劃，才能使問：應如何安排生產計劃，才能使 總利潤最大？總利潤最大？ max z = 2 x1 + 3 x2x1 + 2x2 8 4x1 16 4x2 12 x1， x20例例 2.1 單純形法的引入單純形法的引入楊曉藝 數學建模（公修）5楊曉藝 數學建模（公修）6楊曉藝 數學建模（公修）7楊曉藝 數學建模（公修）8楊曉藝 數學建模（公修）9令非基變量令非基變量 （ x1 , x2）T=（0，0） T 得基可行解：得基可行解： X(0)=(0,0,8,16,12) T , z0=0經濟含義：經濟含義：不生產產品甲乙，利潤為零不生產產品甲乙，利潤為

3、零。分析：分析：z = 0+ 2x1 + 3x2 （分別增加單位產品甲、乙，目標函數分別增加（分別增加單位產品甲、乙，目標函數分別增加2、3，即利潤分別增加，即利潤分別增加2元、元、 3元。）元。） 增加單位產品對目標函數的貢獻，這就是增加單位產品對目標函數的貢獻，這就是檢驗檢驗數數的概念。的概念。楊曉藝 數學建模（公修）10 增加單位產品乙（增加單位產品乙（x2）比甲對目標函數的貢獻大（檢）比甲對目標函數的貢獻大（檢驗數最大），把非基變量驗數最大），把非基變量x2換成基變量，稱換成基變量，稱x2為為換入變換入變量量，而把基變量，而把基變量x5換成非基變量，稱換成非基變量，稱x5為為換出變量換

4、出變量。（在選擇出基變量時，一定保證所有的變量取值仍非（在選擇出基變量時，一定保證所有的變量取值仍非負）（負）（最小比值原則最小比值原則） 事實上，當事實上，當x1 =0，有，有 x3 = 8- 2x20 x4 = 160 （） x5 = 12 - 4 x2 0 min(8/2,-,12/4)=3, 當當x2=3時，時，x5=0。x5為換出基變量。為換出基變量。楊曉藝 數學建模（公修）11確定了確定了換入變量換入變量x2 ，換出變量換出變量x5 以后，得到新的消以后，得到新的消去系統（用非基變量表示基變量）：去系統（用非基變量表示基變量）： x3+2 x2 = 8- x1 （1） x3 = 2

5、- x1+（1/2） x5 x4 = 16-4x1 （2） x4 = 16-4 x1 4x2 = 12- x5 （3） x2 = 3 - （1/4）x5z= 92 x1 -（3/4）x5 令新的非基變量（令新的非基變量（ x1，x5 ）=（0，0）T,得到新的基得到新的基可行解：可行解：X(1)=(0,3,2, 16 , 0) T z1= 9 經濟含義：生產乙產品經濟含義：生產乙產品3個，獲得利潤個，獲得利潤9元。元。(1)-(1/2)(3)楊曉藝 數學建模（公修）12目標函數值還能否增大？目標函數值還能否增大？所有所有非基變量的非基變量的系數均是負數系數均是負數，目標函數值不能目標函數值不能

6、繼續增大了。繼續增大了。 故故X(3)是最優解，是最優解，最優值是最優值是14。楊曉藝 數學建模（公修）13 x2310 x1Q1Q2 X（3） X（1） Q4X（0） OX（2） Q3X（0） （0，0）X（1） （0，3）X（2） （2，3） X（3） （4，2）迭代過程與圖解法對比迭代過程與圖解法對比楊曉藝 數學建模（公修）14 2.2 單純形法的計算步驟單純形法的計算步驟確定初始基礎可行解確定初始基礎可行解求最優解的目標函數值求最優解的目標函數值確定改善方向確定改善方向求新的基礎可行解求新的基礎可行解檢查是否為檢查是否為最優解？最優解？是是否否楊曉藝 數學建模（公修）15l (1) (

7、1) 按數學模型確定初始可行基和初始基可行解按數學模型確定初始可行基和初始基可行解 l (2) (2) 計算各非基變量計算各非基變量xj的檢驗數，的檢驗數， 檢查檢驗數，若所有檢驗數檢查檢驗數，若所有檢驗數 則已得到最優解，可停止計算。否則轉入下一步。則已得到最優解，可停止計算。否則轉入下一步。 miijijjacc1,njj, 2 , 1, 02.2.1 單純形法的計算步驟單純形法的計算步驟楊曉藝 數學建模（公修）16l (3) 在在j0, j=m+1,n中，若有某個中，若有某個k對應對應xk的系數列向量的系數列向量Pk0，則此問題是無界，停止計，則此問題是無界，停止計算。算。l 否則，轉入

8、下一步。否則，轉入下一步。l (4) 根據根據max(j0)=k，確定，確定xk為換入變量為換入變量（進基，所在列稱主元列）（進基，所在列稱主元列）l （5）按）按規則（最小比值原則）計算，確定規則（最小比值原則）計算，確定xl為換出變量（出基，所在行稱主元行）為換出變量（出基，所在行稱主元行）lklikikiabaab0min楊曉藝 數學建模（公修）17l (6) 以以alk為主元進行迭代為主元進行迭代(即用高斯消去法或稱為旋轉運算即用高斯消去法或稱為旋轉運算)，把把xk所對應的列向量所對應的列向量l 將將XB列中的列中的xl換為換為xk，得到新的基可行解。重復，得到新的基可行解。重復(2)

9、(6)，直到終止。直到終止。行第變換laaaaPmklkkkk010021楊曉藝 數學建模（公修）18 換基迭代過程：換基迭代過程： 現考慮以下形式的約束方程組現考慮以下形式的約束方程組11,1111122,11222,11n,11mmkknnmmkknnll mmlkklnlmm mmmkkmnmxaxa xa xbxaxa xa xbxaxa xa xbxaxaxa xb 楊曉藝 數學建模（公修）19為了使為了使xk與與xl進行對換，須把進行對換，須把Pk變為單位向量變為單位向量，這可，這可以通過上述方程式系數矩陣的增廣矩陣進行初等變換以通過上述方程式系數矩陣的增廣矩陣進行初等變換來實現。

10、來實現。 111,1111,1ln,1111lmmknmknl mlklm mmkmnmxxxxxxbaabaaaabaaab楊曉藝 數學建模（公修）201111,111,1ln,11001001010lmmknkmnlkl mllkmkm mmnmlkxxxxxxbaaabaaabaaaaba變換后新的增廣矩陣為變換后新的增廣矩陣為 楊曉藝 數學建模（公修）21由此可得到變換后系數矩陣各元素的變換關系式：由此可得到變換后系數矩陣各元素的變換關系式：;ljikijikillklkijiljllklkaaaailbbilaaababililaa 是變換后的新元素。是變換后的新元素。 ,iijba

11、例例楊曉藝 數學建模（公修）221216810040010040012154321bxxxxx例例 試用上述方法計算例試用上述方法計算例1所示所示LP問題的兩問題的兩個基變換個基變換,并求解這個問題的最優解。并求解這個問題的最優解。31624/10010010042/1010154321bxxxxx2 3 0 0 00002 3 0 0 043楊曉藝 數學建模（公修）2331624/10010010042/1010154321bxxxxx2 3 0 0 00032 0 0 0 -3/424 -1234510101/ 2 200412801001/ 43xxxxxb楊曉藝 數學建模（公修）242

12、 3 0 0 02030 0 2 0 1/44 121234510101/ 2 200412801001/ 43xxxxxb123451001/ 40 40021/ 21 4011/ 21/80 2xxxxx b楊曉藝 數學建模（公修）252 3 0 0 02030 0 3/2 -1/8 0123451001/ 40 40021/ 21 4011/ 21/80 2xxxxx b楊曉藝 數學建模（公修）26 2.2.2 單純形表單純形表 單純形法的表格形式是把用單純形法求出基可單純形法的表格形式是把用單純形法求出基可行解、檢驗其最優性、迭代過程都用表格的方式來行解、檢驗其最優性、迭代過程都用表格

13、的方式來計算求出，以下用單純形表表示線性規劃模型。計算求出，以下用單純形表表示線性規劃模型。楊曉藝 數學建模（公修）27jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Ziibc 0 0 ijijjacc min(0)iikiikbaa單純形表單純形表(表表21)價值系數價值系數基變量的基變量的價值系數價值系數基變量基變量方程右端方程右端常數常數檢驗數檢驗數目標函數的目標函數的相反數相反數楊曉藝 數學建模（公修）28 1.計算檢驗數，由它確定為換人變量計算檢驗數，由它確定為換人變量2.計算計算，由它確定為換出變

14、量，由它確定為換出變量3.確定主元素確定主元素例例 用單純形法求解例用單純形法求解例1。基變量基變量目標函數中各變量的價值系數目標函數中各變量的價值系數楊曉藝 數學建模（公修）29 楊曉藝 數學建模（公修）30 楊曉藝 數學建模（公修）31 楊曉藝 數學建模（公修）32練習練習 用單純形法求解下述線性規劃問題用單純形法求解下述線性規劃問題Ex.123123123123max( )40452423100. .332120,0f xxxxxxxstxxxx x x楊曉藝 數學建模（公修）33 2.3 單純形法的進一步討論單純形法的進一步討論2.3.1 人工變量法人工變量法2.3.2 退化退化楊曉藝

15、 數學建模（公修）342.4.1 人工變量法人工變量法 設線性規劃問題的約束條件設線性規劃問題的約束條件 若沒有作為若沒有作為初始基初始基的的單位矩陣單位矩陣，則分別給每一個約束方程，則分別給每一個約束方程加入人工變量加入人工變量xn+1,xn+m，得到，得到njjjbxP10,; 0,112211222222121111212111mnmnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxa楊曉藝 數學建模（公修）35人工變量在目標函數中的系數如何取？人工變量在目標函數中的系數如何取？初始基可行解是什么？初始基可行解是什么？是不是必須加入是不是必須加入m個人工

16、變量？個人工變量？人工變量能否取值非零？人工變量能否取值非零？如何求解帶有人工變量的線性規劃問題？如何求解帶有人工變量的線性規劃問題？1、2、3、4、5、楊曉藝 數學建模（公修）362.4.1.1 2.4.1.1 大大M M法法v 在一個線性規劃問題的約束條件中加進人工變量后，在一個線性規劃問題的約束條件中加進人工變量后，要求人工變量對目標函數取值不受影響；為此假定人要求人工變量對目標函數取值不受影響；為此假定人工變量在目標函數中的系數為工變量在目標函數中的系數為(-M)(M(-M)(M為任意大的正數為任意大的正數) )，若為最小化問題，系數取為若為最小化問題，系數取為M M。v 目標函數要實

17、現最大化時，必須把人工變量從基變量目標函數要實現最大化時，必須把人工變量從基變量換出。否則目標函數不可能實現最大化。換出。否則目標函數不可能實現最大化。楊曉藝 數學建模（公修）370,123241123min32131321321321xxxxxxxxxxxxxxz例例 試用大試用大M法求解如下線性規劃問題。法求解如下線性規劃問題。楊曉藝 數學建模（公修）380,12324112003min76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxz這里這里M是一個任意大的正數是一個任意大的正數。 解解 在上述問題的約束條件中加入松弛變量在上述

18、問題的約束條件中加入松弛變量x4，剩余變，剩余變量量x5，人工變量，人工變量x6,x7，得到，得到楊曉藝 數學建模（公修）39cj -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 M M x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj-zj -3+6M 1-M 1-3M 0 M 0 0 楊曉藝 數學建模（公修）40cj -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 M 1 x4 x6 x3 10 1

19、 1 3 0 -2 -2 1 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 1 cj-zj -1 1-M 1-3M 0 M 0 3M-1 0 1 1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 4 cj-zj -1 0 0 0 1 M-1 M+1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 2/3 1 4/3 -5/3 -2 -7/3 cj-zj 2 0 0 0 1/3 1/3 M-1/3 M-2/3 楊曉藝

20、 數學建模（公修）41人工變量出基后能否刪去該人工變量在系數矩陣人工變量出基后能否刪去該人工變量在系數矩陣中所在的列？中所在的列？編程時，編程時，M如何賦值？如何賦值？能否考慮把問題分步解決？能否考慮把問題分步解決？1、2、3、楊曉藝 數學建模（公修）422.4.1.22.4.1.2兩階段法兩階段法第一階段第一階段 不考慮原問題是否存在基可行解；給原線不考慮原問題是否存在基可行解；給原線性規劃問題加入人工變量，并構造僅含人工變性規劃問題加入人工變量，并構造僅含人工變量的目標函數和要求實現最小化。量的目標函數和要求實現最小化。目的：目的： 判斷原問題是否存在可行解；判斷原問題是否存在可行解； 得

21、到一個初始基可行解。得到一個初始基可行解。楊曉藝 數學建模（公修）430,000min1212211222222121111212111211mnnnmmnnmmmnnnnnnnmnnxxxxxbxxaxaxabxxaxaxabxxaxaxaxxxxx約束條件目標函數 用單純形法求解上述模型，若得到用單純形法求解上述模型，若得到=0=0，這說明原問題存在基可行解，可以進行第二段這說明原問題存在基可行解，可以進行第二段計算。否則原問題無可行解，應停止計算。計算。否則原問題無可行解，應停止計算。楊曉藝 數學建模（公修）442.4.1.22.4.1.2兩階段法兩階段法第二階段第二階段 將第一階段計算

22、得到的最終表，除去人工將第一階段計算得到的最終表，除去人工變量。將目標函數行的系數，換原問題的目標變量。將目標函數行的系數，換原問題的目標函數系數，作為第二階段計算的初始表。各階函數系數，作為第二階段計算的初始表。各階段的計算方法及步驟與單純形法相同。段的計算方法及步驟與單純形法相同。楊曉藝 數學建模（公修）45例例 試用兩階段法求解線性規劃問題試用兩階段法求解線性規劃問題 0,123241123min32131321321321xxxxxxxxxxxxxxz約束條件目標函數楊曉藝 數學建模（公修）460,12324112min765432173165321432176xxxxxxxxxxxx

23、xxxxxxxxx約束條件目標函數楊曉藝 數學建模（公修）47cj 0 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 1 1 x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj-zj 0 -1 -1 0 1 0 0 0 M 1 x4 x6 x3 10 1 1 3 0 -2 -2 1 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 - 1 - cj-zj 0 -1 0 0 1 0 3 0 1 1 x4 x2 x3 12 1 1 3 0

24、-2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 cj-zj 0 0 0 0 0 1 1 第一階段第一階段楊曉藝 數學建模（公修）48第二階段第二階段cj -3 1 1 0 0 CB XB b x1 x2 x3 x4 x5 i 0 1 1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 4 - - cj-zj -1 0 0 0 1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 cj-zj 2 0 0 0 1/3 1/3 楊曉藝 數學建模（公修）49練習練習 用大用大M法和兩階段法求解下述線性法和兩階段法求解下述線性規劃問題規劃問題Ex.123123123123max2357. .2510,0zxxxxxxstxxxx x x楊曉藝 數學建模（公修）502.4.2 退化退化