運籌學全冊配套完整課件2

1、本章知識結構本章知識結構第第 2 章章 線性規(guī)劃線性規(guī)劃本章教學目標與要求本章教學目標與要求 n n掌握線性規(guī)劃模型基本概念，熟悉線性規(guī)劃的標準型掌握線性規(guī)劃模型基本概念，熟悉線性規(guī)劃的標準型并能將一般線性規(guī)劃問題轉化為標準型；并能將一般線性規(guī)劃問題轉化為標準型； n n理解單純形法的基本原理，掌握應用單純形表求解線性理解單純形法的基本原理，掌握應用單純形表求解線性規(guī)劃的方法；規(guī)劃的方法； n n對給定的線性規(guī)劃問題，能熟練寫出其對偶問題，掌握對給定的線性規(guī)劃問題，能熟練寫出其對偶問題，掌握對偶單純形算法，能對線性規(guī)劃的解進行靈敏度分析；對偶單純形算法，能對線性規(guī)劃的解進行靈敏度分析； n n

2、能熟練地建立實際問題的線性規(guī)劃模型。能熟練地建立實際問題的線性規(guī)劃模型。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1線性規(guī)劃問題及其數學模型線性規(guī)劃問題及其數學模型【例例2.1】（生產計劃問題）某企業(yè)生產（生產計劃問題）某企業(yè)生產I、II和和III三種產品三種產品，每種產品需經過三道工序，每種產品需經過三道工序A、B、C，每件產品在每道工序中，每件產品在每道工序中的工時定額、每道工序在每周可利用的有效工時和每件產品的的工時定額、每道工序在每周可利用的有效工時和每件產品的利潤見下表。問每種產品各生產多少利潤見下表。問每種產品各生產多少,可使這一周內生產的產品可使這一周內生產的產品所獲利潤

3、最大？所獲利潤最大？定額定額( (工時工時/ /件件) )產品型號產品型號每周可利用每周可利用的有效工時的有效工時IIIIII工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03600利潤（元利潤（元/ /件）件）1015122.1.1問題的引入問題的引入2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法設一周內企業(yè)各產品的生產件數為設一周內企業(yè)各產品的生產件數為xj( ( j=1,2,3) ) 生產計劃問題的生產計劃問題的數學模型數學模型： 其中其中s.t.是英文是英文“subjectto”（受約束于）的縮寫。（受約束于）的縮寫。定額定額( (工時工時/ /件件

4、) )產品型號產品型號每周可利用每周可利用的有效工時的有效工時IIIIII工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03600利潤（元利潤（元/ /件）件）101512123123123123max1015121.11.01.154000.70.90.62800. .0.90.81.0360001, 2, 3jzxxxxxxxxxs txxxxj2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.22.2】 （營養(yǎng)配餐問題）假定一個成年人每天需要從（營養(yǎng)配餐問題）假定一個成年人每天需要從食物中獲取食物中獲取30003000卡路里熱量，卡路里熱量，5

5、555克蛋白質和克蛋白質和800800毫克鈣。如果毫克鈣。如果市場上只有四種食品可選，它們每千克所含熱量和營養(yǎng)成份以市場上只有四種食品可選，它們每千克所含熱量和營養(yǎng)成份以及市場價格如下表所示。問如何選擇才能滿足營養(yǎng)的前提下使及市場價格如下表所示。問如何選擇才能滿足營養(yǎng)的前提下使購買食品的費用最?。抠徺I食品的費用最??？ 食品的營養(yǎng)構成表食品的營養(yǎng)構成表序號序號 食品名稱食品名稱 熱量熱量(卡路里卡路里)蛋白質蛋白質(g)鈣鈣(mg)價格價格(元元)1豬肉豬肉100050400102雞蛋雞蛋8006020063大米大米9002030034白菜白菜200105002則該問題的數學模型為：則該問題的數

6、學模型為：2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法設設xj( ( j=1,2,3,4) )為第為第 j 種食品每天的購買量，種食品每天的購買量，1234123412341234min10632100080090020030005060201055.4002003005008000,(1,2,3,4)jzxxxxxxxxxxxxstxxxxxj2.1.2線性規(guī)劃問題及其模型線性規(guī)劃問題及其模型上面所建立的數學模型中有三個要素：上面所建立的數學模型中有三個要素：l）決策變量決策變量 這些決策變量的一組定值代表所給問題的一個這些決策變量的一組定值代表所給問題的一個具體解決方案、措施等。具體解決

7、方案、措施等。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2）目標函數目標函數一個決策問題總有一個試圖達到的目標，數學上一個決策問題總有一個試圖達到的目標，數學上表示為決策變量的函數，稱為目標函數。表示為決策變量的函數，稱為目標函數。3）約束條件約束條件決策變量取值時受到的各種資源限制，通常表決策變量取值時受到的各種資源限制，通常表示成決策變量的等式或不等式。示成決策變量的等式或不等式。由這三個要素組成的問題，在數學上叫作規(guī)劃問題，一般稱由這三個要素組成的問題，在數學上叫作規(guī)劃問題，一般稱為為數學規(guī)劃數學規(guī)劃。如果目標函數及約束條件均為決策變量的如果目標函數及約束條件均為決策變量的線性函線性

8、函數，數，則稱這樣的數學規(guī)劃為則稱這樣的數學規(guī)劃為線性規(guī)劃線性規(guī)劃，否則稱為，否則稱為非線性規(guī)劃非線性規(guī)劃。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法線性規(guī)劃的數學模型的一般形式為：線性規(guī)劃的數學模型的一般形式為： 112211212211212222221222max()( ,)( ,). .( ,)0,1,2,.min nnnnnnmmmnnmjzc xc xc xa xa xaxbaxaxaxbs taxaxaxbxjn或 2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 矩陣形式：矩陣形式： 0XbAX),(. .)max(mintsCXz或向量形式：向量形式： njxxtsCXzj

9、jnj, 2, 10),(. .min)max(1bPj或 其中：其中：C=(=(c1,c2,cn) )是是n 維行向量維行向量，稱為價值系數向量，簡稱為價值系數向量，簡稱為稱為價值向量價值向量；b=(=(b1,b2,bm) )T是是m 維列向量維列向量, ,稱為稱為資源向量資源向量；X=(=(x1,x2,xn) )T稱為稱為決策向量決策向量；A為技術系數矩陣（也稱為消耗為技術系數矩陣（也稱為消耗系數矩陣），簡稱為系數矩陣），簡稱為技術矩陣技術矩陣，)(212222111211n21PPPAmnmmnnaaaaaaaaamiiiaaa21iP2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1

10、.3線性規(guī)劃模型的標準型線性規(guī)劃模型的標準型 為了求解方便，通常規(guī)定線性規(guī)劃的某種形式為標準形。為了求解方便，通常規(guī)定線性規(guī)劃的某種形式為標準形。0XbAXCXzmax 線性規(guī)劃的線性規(guī)劃的標準型的特點標準型的特點：目標函目標函數是最大化；數是最大化；b0；約束條件均由等式；約束條件均由等式組成；組成；決策變量均為非負。決策變量均為非負。 不滿足上述不滿足上述4 4個特點的個特點的LPLP問題，稱為非標準形。對于非標準問題，稱為非標準形。對于非標準形式的線性規(guī)劃，都可以形式的線性規(guī)劃，都可以通過適當的變換轉化為等價的標準型問通過適當的變換轉化為等價的標準型問題。題。njxbxaxaxabxax

11、axabxaxaxatsxcxcxczjmnmnmmnnnnnn,2,1,0.max2211222221211121211122112.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法【例例2.3】將下列線性規(guī)劃問題化成標準型將下列線性規(guī)劃問題化成標準型無約束321321321321321,0,0632442392.32minxxxxxxxxxxxxtsxxxz 解解 1）引入變量）引入變量 33311331, 0,xxxxxxxx ，使0,0,0,063324422392.332min33213321332133213321xxxxxxxxxxxxxxxxtsxxxxz2.1線性規(guī)劃模型與圖解法線

12、性規(guī)劃模型與圖解法2）第一個約束引入松弛變量）第一個約束引入松弛變量x4,第二個約束引入剩余變量第二個約束引入剩余變量x5; ; 0, 0, 0, 0, 0, 063324422392. .00332min54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz3）目標函數）目標函數min變?yōu)楦淖優(yōu)樽優(yōu)楦淖優(yōu)閙ax0, 0, 0, 0, 0, 063324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解

13、法4）將第三個等式約束兩邊同乘以）將第三個等式約束兩邊同乘以1。最后得到該問題的標準形式為：最后得到該問題的標準形式為：0, 0, 0, 0, 0, 063324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz星期所需人數一300二300三350四400五480六600日5507654321minxxxxxxxz7.,2,1,0550600480350300300765436543254321763217652176541jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxj某產品由2件

14、甲零件和3件乙零件組成。2種零件均須在設備A、B上加工，每件甲零件在2種設備上的加工時間分別為5分鐘和9分鐘；每件乙零件在2種設備上加工時間分別為4分鐘和10分鐘?，F有設備A 2臺，設備B 3臺，每臺設備可供加工的時間為每天8小時。為了保持兩種設備負荷均衡，要求一種設備的加工總時間不超過另一種的加工總時間1小時。問每天加工2種零件各多少，能使總產量最大？ 21,xx)31,21min(21xxy 設備加工時間的限制為 96028604521xx1440386010921xx60)109()45(2121xxxx設備負荷均衡約束：寫成線性形式： 60)109()45(2121xxxx60)109

15、()45(2121xxxxyz max121xy 231xy ， 于是得到本問題的數學模型為： yz max0,606460641440109960453121.212121212121xxyxxxxxxxxxyxyts11221 121 22112 122 22221222m ax ()(,)(,). .(,)0,1, 2,.m in nnnnnnmmm nnmjzc xc xc xaxaxaxbaxaxaxbs taxaxaxbxjn 或0XbAX),(. .)max(mintsCXz或njxxtsCXzjjnj, 2, 10),(. .min)max(1bPj或0XbAXCXzmax 線

16、性規(guī)劃的線性規(guī)劃的標準型的特點標準型的特點：目標函目標函數是最大化；數是最大化；b0；約束條件均由等式約束條件均由等式組成；組成；決策變量均為非負。決策變量均為非負。 njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,2, 1,0.max2211222221211121211122112.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1.4線性規(guī)劃的圖解法線性規(guī)劃的圖解法 對于只有兩個變量的線性規(guī)劃問題，可以直接使用圖解法對于只有兩個變量的線性規(guī)劃問題，可以直接使用圖解法求解。圖解法簡單直觀，對一般線性規(guī)劃問題的求解富有啟發(fā)求解。圖解法簡單直觀，對一

17、般線性規(guī)劃問題的求解富有啟發(fā)作用。作用。 圖解法可分三步進行：圖解法可分三步進行：1）在平面上建立直角坐標系；在平面上建立直角坐標系；2）根據約束條件畫出相應的半平面，由這些半平面共同確根據約束條件畫出相應的半平面，由這些半平面共同確定的區(qū)域即為定的區(qū)域即為可行域可行域；3）畫出目標函數的等值線，然后沿目標函數要求的方向平畫出目標函數的等值線，然后沿目標函數要求的方向平移至與可行域邊界相切的點，該點就是最優(yōu)解，相應的坐標即為移至與可行域邊界相切的點，該點就是最優(yōu)解，相應的坐標即為最優(yōu)解。最優(yōu)解。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.42.4】 求解線性規(guī)劃問題求解線性規(guī)劃問

18、題 0, 02426023302. .5040max212212121xxxxxxxtsxxz解解應用圖解法求解線性規(guī)劃，應用圖解法求解線性規(guī)劃，分下面三步求解。分下面三步求解。1）建立直角坐標系）建立直角坐標系1x2xo2）確定可行域）確定可行域令令3個約束條件為等式，得到個約束條件為等式，得到3條直線，畫條直線，畫出第一象限的三個不等式區(qū)域，他們的交集出第一象限的三個不等式區(qū)域，他們的交集就是可行域，亦即區(qū)域就是可行域，亦即區(qū)域OABCD，其內部及，其內部及邊界上的每一個點都是線性規(guī)劃的解。邊界上的每一個點都是線性規(guī)劃的解。301530221 xx3020602321 xx122422xA

19、BCD3）確定最優(yōu)解）確定最優(yōu)解目標函數的等值線目標函數的等值線z=40 x1+50 x2( (z z取定某取定某一個常值一個常值) ) 。沿著函數的梯度方向移動，。沿著函數的梯度方向移動，函數值會增大，當移動到點頂點函數值會增大，當移動到點頂點( (15,15/2) ) ，再繼續(xù)移動就離開區(qū)域了。于是點再繼續(xù)移動就離開區(qū)域了。于是點C就就是最優(yōu)解，最優(yōu)值為是最優(yōu)解，最優(yōu)值為z=40z=4015+5015+5015/2=97515/2=975 2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.52.5】 求解線性規(guī)劃問題求解線性規(guī)劃問題 0

20、, 02426023302. .8040max212212121xxxxxxxtsxxz解解該題將例該題將例2.4中的目標中的目標函數變?yōu)楹瘮底優(yōu)閦=40 x1+80 x2,可行域不可行域不變。變。由于目標函數等直線由于目標函數等直線z=40 x1+80 x2與直線與直線x1+2x2=30平行，平行， 當目標函數的等值線與直線當目標函數的等值線與直線x1+2x2=30重合時，重合時，目標函數目標函數z=40 x1+80 x2z=40 x1+80 x2達到最大值達到最大值12001200。于是線段。于是線段BCBC上的每一個點均為上的每一個點均為該問題的最優(yōu)解。該問題的最優(yōu)解。 1x2xo301

21、530221 xx3020602321 xx2422xABCD2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.62.6】 求解線性規(guī)劃問題求解線性規(guī)劃問題 0,2282. .42max21212121xxxxxxtsxxz1x2xo88221 xx42221xx2解解 由于可行域無界由于可行域無界, , 目標函目標函數數z=2x1+4x2z=2x1+4x2沿著它的法線方沿著它的法線方向向(2,4)(2,4)移動，移動可以無限移動，移動可以無限制下去，而目標函數值一直制下去，而目標函數值一直增加。增加。 所以該線性規(guī)劃問所以該線性規(guī)劃問題無有限最優(yōu)解，有題無有限最優(yōu)解，有無界解無界解。

22、2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.72.7】 求解線性規(guī)劃問題求解線性規(guī)劃問題 0,22. .24max212121xxxxtsxxz 解解 約束條件互不相容，沒有約束條件互不相容，沒有公共交點，可行域是一個空集，不存在滿足條件的公共交點，可行域是一個空集，不存在滿足條件的解，說明線性規(guī)劃問題無解，當然更沒有最優(yōu)解，如圖所示。解，說明線性規(guī)劃問題無解，當然更沒有最優(yōu)解，如圖所示。 1x2xo12221xx22）有無窮多最優(yōu)解3）有無界解4）無可行解幾點啟示：幾點啟示： 1）線性規(guī)劃若存在可行解，則其的可行域是若干個半平面）線性規(guī)劃若存在可行解，則其的可行域是若干個半平面

23、的相交形成的一個多面凸集（可能是空集的相交形成的一個多面凸集（可能是空集）。）。 2）線性規(guī)劃問題若存在最優(yōu)解，則其最優(yōu)解（或最優(yōu)解）線性規(guī)劃問題若存在最優(yōu)解，則其最優(yōu)解（或最優(yōu)解之一）總可以之一）總可以在可行域的某個頂點上達到在可行域的某個頂點上達到。2.2單純形法單純形法 單純形法是解決線性規(guī)劃問題的基本方法。單純形法是解決線性規(guī)劃問題的基本方法。2.2.1線性規(guī)劃的解的基本概念線性規(guī)劃的解的基本概念 設線性規(guī)劃的標準型為設線性規(guī)劃的標準型為 ）（2) 1 (max0XbAXCXz 其中其中A是是mn矩陣矩陣( (n m ，？，？),),設設A A的秩的秩r( (A)=)=m，亦即，亦即A

24、中至少有中至少有一個滿秩一個滿秩mm子矩陣。子矩陣。 解解 滿足系統(tǒng)約束條件（滿足系統(tǒng)約束條件（1 1）的決策向量）的決策向量X=(=(x1,x2,xn) )T稱稱為線性規(guī)劃的解為線性規(guī)劃的解。 可行解可行解 滿足符號約束條件（滿足符號約束條件（2 2）的解）的解X=(=(x1,x2,xn) )T稱為稱為線性規(guī)劃的線性規(guī)劃的可行解可行解。 2.2單純形法單純形法可行域可行域全體可行解的集合稱為線性規(guī)劃的全體可行解的集合稱為線性規(guī)劃的可行域可行域，一般，一般記作記作D=X|AX=b,X0。最優(yōu)解最優(yōu)解使目標函數達到最小值（或最大值）的可行解使目標函數達到最小值（或最大值）的可行解X*=(=(x1

25、*,x2*,xn*) )T稱為線性規(guī)劃的最優(yōu)解。稱為線性規(guī)劃的最優(yōu)解。 最優(yōu)值最優(yōu)值 最優(yōu)解的目標函數值稱為線性規(guī)劃的最優(yōu)值。最優(yōu)解的目標函數值稱為線性規(guī)劃的最優(yōu)值。 基基若若B為為A的滿秩子方陣，即的滿秩子方陣，即r(B)=m,則，稱則，稱B是線性規(guī)劃是線性規(guī)劃問題的一個基。也就是說，矩陣問題的一個基。也就是說，矩陣B是由是由A的的m個線性無關列向量個線性無關列向量所構成，不妨設為：所構成，不妨設為：mmmmmmmPPPaaaaaaaaaB21212222111211稱稱Pj( (j=1,2,m) )為為基向量基向量。 2.2單純形法單純形法 基變量、非基變量基變量、非基變量 與其基向量與其

26、基向量Pj( (j=1,2,m) )相對應的變相對應的變量量xj( (j=1,2,m) )為為基變量基變量，其他決策變量稱為，其他決策變量稱為非基變量非基變量。 基解基解 記基變量為記基變量為XB=(=(x1,x2,xn) )T ，非基變量為，非基變量為XN= =( (xm+1,xm+2,xn) )T ，稱滿足方程，稱滿足方程(1)(1)的解的解X（XB，XN）為）為LPLP的基解，其中的基解，其中XB=B-1-1b，XN= =0。 基可行解基可行解 若基解滿足非負約若基解滿足非負約束（束（2 2），即），即XB=B-1-1b0 ，則稱該，則稱該其解為基可行解。稱相應的基其解為基可行解。稱相應

27、的基B為為可行基可行基。 解基解可行解基可行解【例例2.8】求出下面線性規(guī)劃的所有基解求出下面線性規(guī)劃的所有基解,并指出那些是基可行解并指出那些是基可行解.2.2單純形法單純形法04102532max515242131321xxxxxxxxxxxz解解 其系數矩陣為：其系數矩陣為： 521,.,100100102100101PPPA易知，其易知，其3 3階子方陣共有階子方陣共有1010個?？梢则炞C：其中有個?？梢则炞C：其中有2 2個子方個子方陣為奇異的即：陣為奇異的即：0,00010101194319BPPPB0,1010120001054210BPPPB而另外的而另外的8 8個個3 3階子方

28、陣均為非奇異的，即該階子方陣均為非奇異的，即該LPLP問題共有問題共有8 8個個基?；?。2.2單純形法單純形法分別將這分別將這8 8個基對應的基解求出，例如：個基對應的基解求出，例如： ,1000100015431PPPB則基變量為則基變量為x3,x4,x5，令非基變量，令非基變量x1=x2=0，代入原約束方程，代入原約束方程，x1x2x3x4x5是否基可行解005104是04520是50054是05501否100504否55/2003/2是54030否24300是04102532max515242131321xxxxxxxxxxxz立即可得基解立即可得基解 X1 1（0,0,5,10,4)T

29、。類似地求出其它基解，見下表類似地求出其它基解，見下表2.2單純形法單純形法2.2.2單純形法的基本原理單純形法的基本原理 基本概念基本概念凸集凸集設設D是是n維空間的一個點集，若對任意兩點維空間的一個點集，若對任意兩點均有均有；則稱；則稱D為凸集。為凸集。 ,) 1 (DxDx)2( 1 , 0,)1 ()2() 1 (Dxx幾何意義：幾何意義：凸集凸集D中的任意兩點間的連線仍然在中的任意兩點間的連線仍然在D中。中。頂點頂點設設D是凸集，若是凸集，若且且x 不能用不能用D中不同的兩點中不同的兩點的凸組合表示為的凸組合表示為，則稱，則稱x為為D的的一個頂點（或極點）。一個頂點（或極點）。 Dx

30、)2()1(,xx) 10( ,)1 ()2() 1 (DxxxS1S2S32.2單純形法單純形法 基本定理基本定理定理定理2.1若線性規(guī)劃問題存在可行域，則可行域是凸集。若線性規(guī)劃問題存在可行域，則可行域是凸集。定理定理2.2線性規(guī)劃可行域線性規(guī)劃可行域D中的點中的點X是頂點的充要條件為是頂點的充要條件為X是基可行解。是基可行解。定理定理2.3若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點上得到。域的頂點上得到。 引理引理線性規(guī)劃可行解線性規(guī)劃可行解X（x1,x2, xn ）為基可行解的充分）為基可行解的充分必要條件為必要條件為X的正分量對應的系

31、數列向量線性無關。的正分量對應的系數列向量線性無關。 11221 121 22112 122 22221222m ax ()(,)(,). .(,)0,1, 2,.m in nnnnnnmmm nnmjzc xc xc xaxaxaxbaxaxaxbs taxaxaxbxjn 或0XbAX),(. .)max(mintsCXz或njxxtsCXzjjnj, 2, 10),(. .min)max(1bPj或0XbAXCXzmax 線性規(guī)劃的線性規(guī)劃的標準型的特點標準型的特點：目標函目標函數是最大化；數是最大化；b0；約束條件均由等式約束條件均由等式組成；組成；決策變量均為非負。決策變量均為非負。

32、 njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,2, 1,0.max2211222221211121211122112.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1.4線性規(guī)劃的圖解法線性規(guī)劃的圖解法 對于只有兩個變量的線性規(guī)劃問題，可以直接使用圖解法對于只有兩個變量的線性規(guī)劃問題，可以直接使用圖解法求解。圖解法簡單直觀，對一般線性規(guī)劃問題的求解富有啟發(fā)求解。圖解法簡單直觀，對一般線性規(guī)劃問題的求解富有啟發(fā)作用。作用。 圖解法可分三步進行：圖解法可分三步進行：1）在平面上建立直角坐標系；在平面上建立直角坐標系；2）根據約束條件畫出相應的半平面

33、，由這些半平面共同確根據約束條件畫出相應的半平面，由這些半平面共同確定的區(qū)域即為定的區(qū)域即為可行域可行域；3）畫出目標函數的等值線，然后沿目標函數要求的方向平畫出目標函數的等值線，然后沿目標函數要求的方向平移至與可行域邊界相切的點，該點就是最優(yōu)解，相應的坐標即為移至與可行域邊界相切的點，該點就是最優(yōu)解，相應的坐標即為最優(yōu)解。最優(yōu)解。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.42.4】 求解線性規(guī)劃問題求解線性規(guī)劃問題 0, 02426023302. .5040max212212121xxxxxxxtsxxz解解應用圖解法求解線性規(guī)劃，應用圖解法求解線性規(guī)劃，分下面三步求解。分下

34、面三步求解。1）建立直角坐標系）建立直角坐標系1x2xo2）確定可行域）確定可行域令令3個約束條件為等式，得到個約束條件為等式，得到3條直線，畫條直線，畫出第一象限的三個不等式區(qū)域，他們的交集出第一象限的三個不等式區(qū)域，他們的交集就是可行域，亦即區(qū)域就是可行域，亦即區(qū)域OABCD，其內部及，其內部及邊界上的每一個點都是線性規(guī)劃的解。邊界上的每一個點都是線性規(guī)劃的解。301530221 xx3020602321 xx122422xABCD3）確定最優(yōu)解）確定最優(yōu)解目標函數的等值線目標函數的等值線z=40 x1+50 x2( (z z取定某取定某一個常值一個常值) ) 。沿著函數的梯度方向移動，。

35、沿著函數的梯度方向移動，函數值會增大，當移動到點頂點函數值會增大，當移動到點頂點( (15,15/2) ) ，再繼續(xù)移動就離開區(qū)域了。于是點再繼續(xù)移動就離開區(qū)域了。于是點C就就是最優(yōu)解，最優(yōu)值為是最優(yōu)解，最優(yōu)值為z=40z=4015+5015+5015/2=97515/2=975 2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.52.5】 求解線性規(guī)劃問題求解線性規(guī)劃問題 0, 02426023302. .8040max212212121xxxxxxxtsxxz解解該題將例該題將例2.4中的目標中的目標函數變?yōu)楹瘮底優(yōu)閦=40 x1+80

36、 x2,可行域不可行域不變。變。由于目標函數等直線由于目標函數等直線z=40 x1+80 x2與直線與直線x1+2x2=30平行，平行， 當目標函數的等值線與直線當目標函數的等值線與直線x1+2x2=30重合時，重合時，目標函數目標函數z=40 x1+80 x2z=40 x1+80 x2達到最大值達到最大值12001200。于是線段。于是線段BCBC上的每一個點均為上的每一個點均為該問題的最優(yōu)解。該問題的最優(yōu)解。 1x2xo301530221 xx3020602321 xx2422xABCD2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.62.6】 求解線性規(guī)劃問題求解線性規(guī)劃問題

37、0,2282. .42max21212121xxxxxxtsxxz1x2xo88221 xx42221xx2解解 由于可行域無界由于可行域無界, , 目標函目標函數數z=2x1+4x2z=2x1+4x2沿著它的法線方沿著它的法線方向向(2,4)(2,4)移動，移動可以無限移動，移動可以無限制下去，而目標函數值一直制下去，而目標函數值一直增加。增加。 所以該線性規(guī)劃問所以該線性規(guī)劃問題無有限最優(yōu)解，有題無有限最優(yōu)解，有無界解無界解。2.1線性規(guī)劃模型與圖解法線性規(guī)劃模型與圖解法 【例例2.72.7】 求解線性規(guī)劃問題求解線性規(guī)劃問題 0,22. .24max212121xxxxtsxxz 解解

38、約束條件互不相容，沒有約束條件互不相容，沒有公共交點，可行域是一個空集，不存在滿足條件的公共交點，可行域是一個空集，不存在滿足條件的解，說明線性規(guī)劃問題無解，當然更沒有最優(yōu)解，如圖所示。解，說明線性規(guī)劃問題無解，當然更沒有最優(yōu)解，如圖所示。 1x2xo12221xx22）有無窮多最優(yōu)解3）有無界解4）無可行解幾點啟示：幾點啟示： 1）線性規(guī)劃若存在可行解，則其的可行域是若干個半平面）線性規(guī)劃若存在可行解，則其的可行域是若干個半平面的相交形成的一個多面凸集（可能是空集的相交形成的一個多面凸集（可能是空集）。）。 2）線性規(guī)劃問題若存在最優(yōu)解，則其最優(yōu)解（或最優(yōu)解）線性規(guī)劃問題若存在最優(yōu)解，則其最

39、優(yōu)解（或最優(yōu)解之一）總可以之一）總可以在可行域的某個頂點上達到在可行域的某個頂點上達到。2.2單純形法單純形法 單純形法是解決線性規(guī)劃問題的基本方法。單純形法是解決線性規(guī)劃問題的基本方法。2.2.1線性規(guī)劃的解的基本概念線性規(guī)劃的解的基本概念 設線性規(guī)劃的標準型為設線性規(guī)劃的標準型為 ）（2) 1 (max0XbAXCXz 其中其中A是是mn矩陣矩陣( (n m ，？，？),),設設A A的秩的秩r( (A)=)=m，亦即，亦即A中至少有中至少有一個滿秩一個滿秩mm子矩陣。子矩陣。 解解 滿足系統(tǒng)約束條件（滿足系統(tǒng)約束條件（1 1）的決策向量）的決策向量X=(=(x1,x2,xn) )T稱稱為

40、線性規(guī)劃的解為線性規(guī)劃的解。 可行解可行解 滿足符號約束條件（滿足符號約束條件（2 2）的解）的解X=(=(x1,x2,xn) )T稱為稱為線性規(guī)劃的線性規(guī)劃的可行解可行解。 2.2單純形法單純形法可行域可行域全體可行解的集合稱為線性規(guī)劃的全體可行解的集合稱為線性規(guī)劃的可行域可行域，一般，一般記作記作D=X|AX=b,X0。最優(yōu)解最優(yōu)解使目標函數達到最小值（或最大值）的可行解使目標函數達到最小值（或最大值）的可行解X*=(=(x1*,x2*,xn*) )T稱為線性規(guī)劃的最優(yōu)解。稱為線性規(guī)劃的最優(yōu)解。 最優(yōu)值最優(yōu)值 最優(yōu)解的目標函數值稱為線性規(guī)劃的最優(yōu)值。最優(yōu)解的目標函數值稱為線性規(guī)劃的最優(yōu)值。

41、 基基若若B為為A的滿秩子方陣，即的滿秩子方陣，即r(B)=m,則，稱則，稱B是線性規(guī)劃是線性規(guī)劃問題的一個基。也就是說，矩陣問題的一個基。也就是說，矩陣B是由是由A的的m個線性無關列向量個線性無關列向量所構成，不妨設為：所構成，不妨設為：mmmmmmmPPPaaaaaaaaaB21212222111211稱稱Pj( (j=1,2,m) )為為基向量基向量。 2.2單純形法單純形法 基變量、非基變量基變量、非基變量 與其基向量與其基向量Pj( (j=1,2,m) )相對應的變相對應的變量量xj( (j=1,2,m) )為為基變量基變量，其他決策變量稱為，其他決策變量稱為非基變量非基變量。 基解

42、基解 記基變量為記基變量為XB=(=(x1,x2,xn) )T ，非基變量為，非基變量為XN= =( (xm+1,xm+2,xn) )T ，稱滿足方程，稱滿足方程(1)(1)的解的解X（XB，XN）為）為LPLP的基解，其中的基解，其中XB=B-1-1b，XN= =0。 基可行解基可行解 若基解滿足非負約若基解滿足非負約束（束（2 2），即），即XB=B-1-1b0 ，則稱該，則稱該其解為基可行解。稱相應的基其解為基可行解。稱相應的基B為為可行基可行基。 解基解可行解基可行解【例例2.8】求出下面線性規(guī)劃的所有基解求出下面線性規(guī)劃的所有基解,并指出那些是基可行解并指出那些是基可行解.2.2單純

43、形法單純形法04102532max515242131321xxxxxxxxxxxz解解 其系數矩陣為：其系數矩陣為： 521,.,100100102100101PPPA易知，其易知，其3 3階子方陣共有階子方陣共有1010個?？梢则炞C：其中有個?？梢则炞C：其中有2 2個子方個子方陣為奇異的即：陣為奇異的即：0,00010101194319BPPPB0,1010120001054210BPPPB而另外的而另外的8 8個個3 3階子方陣均為非奇異的，即該階子方陣均為非奇異的，即該LPLP問題共有問題共有8 8個個基?；?。2.2單純形法單純形法分別將這分別將這8 8個基對應的基解求出，例如：個基對應

44、的基解求出，例如： ,1000100015431PPPB則基變量為則基變量為x3,x4,x5，令非基變量，令非基變量x1=x2=0，代入原約束方程，代入原約束方程，x1x2x3x4x5是否基可行解005104是04520是50054是05501否100504否55/2003/2是54030否24300是04102532max515242131321xxxxxxxxxxxz立即可得基解立即可得基解 X1 1（0,0,5,10,4)T。類似地求出其它基解，見下表類似地求出其它基解，見下表2.2單純形法單純形法2.2.2單純形法的基本原理單純形法的基本原理 基本概念基本概念凸集凸集設設D是是n維空間

45、的一個點集，若對任意兩點維空間的一個點集，若對任意兩點均有均有；則稱；則稱D為凸集。為凸集。 ,) 1 (DxDx)2( 1 , 0,)1 ()2() 1 (Dxx幾何意義：幾何意義：凸集凸集D中的任意兩點間的連線仍然在中的任意兩點間的連線仍然在D中。中。頂點頂點設設D是凸集，若是凸集，若且且x 不能用不能用D中不同的兩點中不同的兩點的凸組合表示為的凸組合表示為，則稱，則稱x為為D的的一個頂點（或極點）。一個頂點（或極點）。 Dx)2()1(,xx) 10( ,)1 ()2() 1 (DxxxS1S2S32.2單純形法單純形法 基本定理基本定理定理定理2.1若線性規(guī)劃問題存在可行域，則可行域是

46、凸集。若線性規(guī)劃問題存在可行域，則可行域是凸集。定理定理2.2線性規(guī)劃可行域線性規(guī)劃可行域D中的點中的點X是頂點的充要條件為是頂點的充要條件為X是基可行解。是基可行解。定理定理2.3若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點上得到。域的頂點上得到。 引理引理線性規(guī)劃可行解線性規(guī)劃可行解X（x1,x2, xn ）為基可行解的充分）為基可行解的充分必要條件為必要條件為X的正分量對應的系數列向量線性無關。的正分量對應的系數列向量線性無關。 線性規(guī)劃的線性規(guī)劃的解的四種可能情況解的四種可能情況：有唯一最優(yōu)解；有無窮多最優(yōu)解；有唯一最優(yōu)解；有無窮多最優(yōu)解

47、；有無界解；無可行解有無界解；無可行解基：基：系數矩陣系數矩陣A A的的m m階非奇異子方陣階非奇異子方陣基解：基解：令非基變量為令非基變量為0 0，求解由基變量構成的線性方，求解由基變量構成的線性方程組所得的解，該解與非基變量一起構成的約束方程程組所得的解，該解與非基變量一起構成的約束方程組的解組的解基可行解：基可行解：可行的基解，滿足變量非負約束的基解?？尚械幕?，滿足變量非負約束的基解。幾個幾個基本定理基本定理定理定理2.1若線性規(guī)劃問題存在可行域，則可行域是凸集。若線性規(guī)劃問題存在可行域，則可行域是凸集。定理定理2.2線性規(guī)劃可行域線性規(guī)劃可行域D中頂點的對應于中頂點的對應于LP的基可

48、行解。的基可行解。定理定理2.3若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點上得到。域的頂點上得到。 引理引理線性規(guī)劃可行解線性規(guī)劃可行解X（x1,x2,xn）為基可行解的充分）為基可行解的充分必要條件為必要條件為X的的正分量正分量對應的系數列向量對應的系數列向量線性無關線性無關。TmxxxX)0.0,0,.,(002001只考察基可行解。對于某一個基可行解，只需考察與其相鄰的基可行解， 看是否比它們均優(yōu)。（圖示說明）設有基可行解TllmxxxxxX)0,.,0 , 0 ,., 0,.,(1111112111則它們是相鄰的。)2(,.2 , 1,

49、 0) 1 (max11njxxaxczjnjjijnjjjb2.2.4 2.2.4 單純形法的迭代原理單純形法的迭代原理單純形法的基本思想：單純形法的基本思想：考察考察LPLP的基可行解，判斷其是否的基可行解，判斷其是否為最優(yōu)解，若不是，則轉到與其相鄰的可使目標函數增為最優(yōu)解，若不是，則轉到與其相鄰的可使目標函數增大的基可行解，直到找到最優(yōu)解。大的基可行解，直到找到最優(yōu)解。1.1.初始基可行解的確定初始基可行解的確定考察標準形的考察標準形的LPLP問題：問題：通常在方程（通常在方程（1 1）的系數）的系數矩陣矩陣A A中，總存在中，總存在1 1個單位個單位矩陣，不妨設為：矩陣，不妨設為：10

50、0010001).,(21mPPPB則則x1 1, ,x2 2,xm m為基變量，而為基變量，而xm+1,xm+2,xn為非基變量，令為非基變量，令非基變量非基變量0 0，則很容易得到一個基可行解：（，則很容易得到一個基可行解：（？）TmTnbbbxxxX)0.0 , 0 ,.,(),.,(21212.2.從一個基可行解轉到相鄰的另一個基可行解從一個基可行解轉到相鄰的另一個基可行解 按單純形法的思想，找到一個基可行解后，進行檢驗，看按單純形法的思想，找到一個基可行解后，進行檢驗，看它是否為最優(yōu)解，用什么辦法呢？就是將它和與其相鄰的基可它是否為最優(yōu)解，用什么辦法呢？就是將它和與其相鄰的基可行解比

51、較，為此須找到與它相鄰的基可行解。行解比較，為此須找到與它相鄰的基可行解。定義：定義：如果兩個基可行解只有一個基變量不相同，則稱這兩個基如果兩個基可行解只有一個基變量不相同，則稱這兩個基可行解相鄰可行解相鄰設已得到一個基可行解為設已得到一個基可行解為將其代入約束方程（將其代入約束方程（1），則得到：），則得到：TmxxxX)0.0 , 0 ,.,(002010) 3(10miiixPb因為因為P1,P2,Pm線性無關（？），則其它系數列向量線性無關（？），則其它系數列向量Pj可由它可由它們線性表示為們線性表示為:miiijjPaP1或寫成：或寫成：)4(01miiijjPaP將（將（4）兩端同

52、時乘以）兩端同時乘以0，則得到：，則得到：)5(0)(1miiijjPaP（3 3）+ +（5 5）整理后得到：）整理后得到：則得到了約束方程（則得到了約束方程（1）的另一個解。）的另一個解。取取則則X1的所有分量均的所有分量均0 0！這樣！這樣X1就是就是LPLP的一個的一個可行解可行解。j jTmjmjjaxaxaxX)0,.0 , 0.0 , 0 ,.,(02021011（6）系數矩陣為：）系數矩陣為：)6()(10bjmiiijiPPax)7(0|min00ljlijijiaxaax10000010100001000001, 1, 121mjjlljjljjaaaaaa容易看出，它是非

53、奇異的，所容易看出，它是非奇異的，所以以X1為基可行解。為基可行解。注意到注意到X0與與X1只有一個分量只有一個分量不同，則它們是不同，則它們是相鄰相鄰的基可的基可行解。行解。3.3.最優(yōu)性檢驗和解的叛別最優(yōu)性檢驗和解的叛別當當稱為稱為xj的檢驗數。的檢驗數。miiixcz100)8()()()(10110101miijijmimiijijiijmiijiiacczaccxccaxcz0)(1miijijacc時，就有時，就有01zz jjmiijijjzcacc1記記解的判別解的判別（1）若所有）若所有，則表明，則表明z0比各相鄰的基可行解均優(yōu)，則比各相鄰的基可行解均優(yōu)，則z0即為即為LP的

54、最優(yōu)值，的最優(yōu)值，X0即為即為LP的最優(yōu)解。的最優(yōu)解。0j（2）若所有）若所有，且有某個，且有某個j,同時可按同時可按規(guī)則找到規(guī)則找到00，則存在，則存在X1 1，也為最優(yōu)解，且，也為最優(yōu)解，且 而對于而對于X0 0和和X1的凸的凸組合組合X，有，有0j0j01zz 00010)1 ()1 (zzzXXCCXz即即X亦為亦為LP的最優(yōu)解，此時的最優(yōu)解，此時LP有有無窮多無窮多最優(yōu)解最優(yōu)解（3）若有）若有且且，則由，則由知，對任意的知，對任意的0，均有均有 , ,即即X1 1為可行解，而為可行解，而z1 1可以無限增大?？梢詿o限增大。此此時，時，LP有有無界解無界解。0j0jPijiiaxx01

55、001ijiiaxx2 2）容易看出其一個基為：）容易看出其一個基為： 0,24261553. .002max43214213214321xxxxxxxxxxtsxxxxz4.單純形法求解LP問題的步驟例2.10 求解LP問題0,24261553.2max21212121xxxxxxtsxxzStep1 確定初始基可行解，列初始單純形表10260153A1001B則得到初始基可行解：則得到初始基可行解： 1）標準化TX)24,15, 0, 0(03 3）列初始單純形表）列初始單純形表 cj x1 x2 x3 x4 3 5 1 0 2 1 0 0 C B X B B-1b 0 x3 15 0 x

56、4 24 6 2 0 1 Step2檢驗檢驗 cj x1 x2 x3 x4 3 5 1 0 2 1 0 0 C B X B B-1b 0 x3 15 0 x4 24 6 2 0 1 j 2 1 0 0 1)計算計算檢驗數檢驗數jjmiijijjzcacc12)解的判別解的判別Step3基可行解的轉換基可行解的轉換1）入基變量的確定）入基變量的確定 2）出基變量的確定）出基變量的確定 5 4 6 ljlijijiaxaax000|min3）列新單純形表）列新單純形表 0 x3 2 x1 j 4 1 1/3 0 1/6 0 1 1/4 -1/8 1 x2 3/4 2 x1 15/4 1 0 -1/

57、12 5/24 j 0 0 -1/12 -7/24 3 0 4 1 -1/2 Step4重復重復step2-step3 0 1/3 0 -1/3 3 / 4 12 4 jjmiijijjzcacc1（1）若所有）若所有，X0即為即為LP的最優(yōu)解。的最優(yōu)解。0j（2）若所有）若所有，且有某個，且有某個j,同時可按同時可按規(guī)則找到規(guī)則找到00，0j0j此時此時LP有有無窮多無窮多最優(yōu)解最優(yōu)解（3）若有）若有且且，則，則LP有有無界解無界解。0j0jPStep3基可行解的轉換基可行解的轉換1）入基變量的確定）入基變量的確定2）出基變量的確定）出基變量的確定ljlijijiaxaax000|min3）

58、列新單純形表）列新單純形表Step4重復重復step2-step32.2單純形法單純形法【例例2.13】用單純形法求解線性規(guī)劃用單純形法求解線性規(guī)劃0,21024242max2121212121xxxxxxxxxxz解解將線性規(guī)劃標準化，得將線性規(guī)劃標準化，得0,21024200042max5432152142132154321xxxxxxxxxxxxxxxxxxxz容易看出，其初始基可行容易看出，其初始基可行解為：解為：TX)2 ,10, 4 , 0 , 0(02.2單純形法單純形法初始基單純形表為：初始基單純形表為： 2 4 0 0 0 2 5 4 4 0 -2 0 0 4 3 8 0 0

59、 0 -2 0 至此，所有非基變量的檢驗數均至此，所有非基變量的檢驗數均不大于不大于0，于是得到最優(yōu)解為：，于是得到最優(yōu)解為：TX)2/5 , 0 , 0 , 2/7 , 3(*20*z注意：注意：在最終單純形表中，在最終單純形表中，非基變量非基變量x3的檢驗數的檢驗數0，而，而它的系數列向量中有它的系數列向量中有00的系的系數，因此，迭代仍可繼續(xù)。數，因此，迭代仍可繼續(xù)。 0 14 10/30/3 0 0 0 -2 0 得到另一最優(yōu)解得到另一最優(yōu)解TX) , 0 , 0 , 3/10, 3/8 , 3/14(*120*1z2.2.4單純形法的進一步討論（大單純形法的進一步討論（大M法）法）【

60、例例2.14】用單純形法求解線性規(guī)劃用單純形法求解線性規(guī)劃) 1 (0,2314242max21212121xxxxxxxxz解解將線性規(guī)劃標準化，得將線性規(guī)劃標準化，得與前兩例不同，本例中不存在明顯的與前兩例不同，本例中不存在明顯的2階單位子方陣，則初始基可行解的階單位子方陣，則初始基可行解的確定成問題了！確定成問題了！0,2314242max432142132121xxxxxxxxxxxxz引入引入人工變量人工變量x50,0,構造輔助構造輔助LPLP問題問題)2(0,2314242max43215421321521xxxxxxxxxxxMxxxz這樣初始基可行解就很容易確定了。這樣初始基可