第2章 單純形法(2013使用版)

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

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

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

4、出變量。（在選擇出基變量時，一定保證所有的變量取值仍非（在選擇出基變量時，一定保證所有的變量取值仍非負）（負）（最小比值原則最小比值原則） 事實上，當(dāng)事實上，當(dāng)x1 =0，有，有 x3 = 8- 2x20 x4 = 160 （） x5 = 12 - 4 x2 0 min(8/2,-,12/4)=3, 當(dāng)當(dāng)x2=3時，時，x5=0。x5為換出基變量。為換出基變量。楊曉藝 數(shù)學(xué)建模（公修）11確定了確定了換入變量換入變量x2 ，換出變量換出變量x5 以后，得到新的消以后，得到新的消去系統(tǒng)（用非基變量表示基變量）：去系統(tǒng)（用非基變量表示基變量）： 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 經(jīng)濟含義：生產(chǎn)乙產(chǎn)品經(jīng)濟含義：生產(chǎn)乙產(chǎn)品3個，獲得利潤個，獲得利潤9元。元。(1)-(1/2)(3)楊曉藝 數(shù)學(xué)建模（公修）12目標函數(shù)值還能否增大？目標函數(shù)值還能否增大？所有所有非基變量的非基變量的系數(shù)均是負數(shù)系數(shù)均是負數(shù)，目標函數(shù)值不能目標函數(shù)值不能

6、繼續(xù)增大了。繼續(xù)增大了。 故故X(3)是最優(yōu)解，是最優(yōu)解，最優(yōu)值是最優(yōu)值是14。楊曉藝 數(shù)學(xué)建模（公修）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）迭代過程與圖解法對比迭代過程與圖解法對比楊曉藝 數(shù)學(xué)建模（公修）14 2.2 單純形法的計算步驟單純形法的計算步驟確定初始基礎(chǔ)可行解確定初始基礎(chǔ)可行解求最優(yōu)解的目標函數(shù)值求最優(yōu)解的目標函數(shù)值確定改善方向確定改善方向求新的基礎(chǔ)可行解求新的基礎(chǔ)可行解檢查是否為檢查是否為最優(yōu)解？最優(yōu)解？是是否否楊曉藝 數(shù)學(xué)建模（公修）15l (1) (

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

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

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

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

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

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

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

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

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

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

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

18、問題的約束條件中加入松弛變量x4，剩余變，剩余變量量x5，人工變量，人工變量x6,x7，得到，得到楊曉藝 數(shù)學(xué)建模（公修）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 楊曉藝 數(shù)學(xué)建模（公修）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、 數(shù)學(xué)建模（公修）41人工變量出基后能否刪去該人工變量在系數(shù)矩陣人工變量出基后能否刪去該人工變量在系數(shù)矩陣中所在的列？中所在的列？編程時，編程時，M如何賦值？如何賦值？能否考慮把問題分步解決？能否考慮把問題分步解決？1、2、3、楊曉藝 數(shù)學(xué)建模（公修）422.4.1.22.4.1.2兩階段法兩階段法第一階段第一階段 不考慮原問題是否存在基可行解；給原線不考慮原問題是否存在基可行解；給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量的目標函數(shù)和要求實現(xiàn)最小化。量的目標函數(shù)和要求實現(xiàn)最小化。目的：目的： 判斷原問題是否存在可行解；判斷原問題是否存在可行解； 得

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

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

23、xxxxxxxxx約束條件目標函數(shù)楊曉藝 數(shù)學(xué)建模（公修）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 第一階段第一階段楊曉藝 數(shù)學(xué)建模（公修）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 楊曉藝 數(shù)學(xué)建模（公修）49練習(xí)練習(xí) 用大用大M法和兩階段法求解下述線性法和兩階段法求解下述線性規(guī)劃問題規(guī)劃問題Ex.123123123123max2357. .2510,0zxxxxxxstxxxx x x楊曉藝 數(shù)學(xué)建模（公修）502.4.2 退化退化