2線性規(guī)劃圖解法和單純形法匯總

《2線性規(guī)劃圖解法和單純形法匯總》由會員分享，可在線閱讀，更多相關(guān)《2線性規(guī)劃圖解法和單純形法匯總（91頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,運 籌 帷 幄 之 中,決 勝 千 里 之 外,線 性 規(guī) 劃及單純形法,Linear Programming,第一章,,Chapter1,線性規(guī)劃,(Linear Programming),,LP,的數(shù)學(xué)模型,,圖解法,,單純形法,,單純形法的進一步討論－人工變量法,,,LP,模型的應(yīng)用,本章主要內(nèi)容：,,線性規(guī)劃問

2、題的數(shù)學(xué)模型,,1.,規(guī)劃問題,生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。,線性規(guī)劃通常解決下列兩類問題：,（,1,）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo),（,2,）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多 、利潤最大,.,）,,線性規(guī)劃問題的數(shù)學(xué)模型,,例,1.1,如圖所示，如何截取,x,使鐵皮所圍成的容積最大？,,x,a,,線性規(guī)劃問題的數(shù)學(xué)模型,,例,1.2,某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)

3、品利潤,問：應(yīng)如何安排生產(chǎn)計劃，才能使總利潤最大？,解：,1.,決策變量：設(shè)產(chǎn)品,I,、,II,的產(chǎn)量,,分別為,,x,1,、,x,2,2.,目標(biāo)函數(shù)：設(shè)總利潤為,z,，,則有：,,,,,max,z,= 2,x,1,+,x,2,3.,約束條件：,,,,,,5x,2,≤ 15,,6,x,1,+ 2,x,2,≤ 24,,x,1,+,x,2,≤ 5,,,,x,1,，,x,2,≥0,x,1,=3.8,,x,2,=1.2,,z,=22.8,,線性規(guī)劃問題的數(shù)學(xué)模型,,例,1.3,已知資料如下表所示，問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。,,設(shè) 備,,產(chǎn) 品,A,B,,,,C,,,D

4、,利潤（元）,,Ⅰ,,2,,1,,4,,0,,2,,Ⅱ,,2,,2,,0,,4,,3,有 效 臺 時,12,,8,16,12,,解：,1.,決策變量：設(shè)產(chǎn)品,I,、,II,的產(chǎn)量分別為,,x,1,、,x,2,2.,目標(biāo)函數(shù)：設(shè)總利潤為,z,，,則有：,,max z = 2,x,1,+,x,2,3.,約束條件：,,,,,x,1,≥ 0 ,,x,2,≥ 0,,2,x,1,+ 2,x,2,≤ 12,,,x,1,+ 2,x,2,≤ 8,,4,x,1,≤ 16,,4,x,2,≤ 12,,線性規(guī)劃問題的數(shù)學(xué)模型,,例,1.4,,某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取

5、的藥物量,解：,要求：生產(chǎn),A,種藥物至少,160,單位；,B,種藥物恰好,200,單位，,C,種藥物不超過,180,單位，且使原料總成本最小。,1.,決策變量：設(shè)四種原料的使用,,量分別為：,x,1,、,x,2,、,x,3,,、,x,4,2.,目標(biāo)函數(shù)：設(shè)總成本為,z,,,min,,z = 5 x,1,+ 6 x,2,+ 7 x,3,+ 8 x,4,3.,約束條件：,,,,,,x,1,+ 2,x,2,+,x,3,+,x,4,≥160,,,2,x,1,+4,x,3,+2,x,4,＝200,,,3,x,1,＋,x,2,+,x,3,+2,x,4,,≤180,,,,,,x,1,、x,2,,、x,3,

6、,、x,4,≥0,,,,,,,,例,1.5,,某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航線的貨運量、貨運成本如下表所示：,航線號,船隊,,類型,編隊形式,,,貨運成本,,（千元／隊）,貨運量,,（千噸）,,,拖輪,A,型,,駁船,B,型,,駁船,,,1,1,1,2,—,36,25,,2,1,—,4,36,20,2,3,2,2,4,72,40,,4,1,—,4,27,20,船只種類,船只數(shù),拖 輪,30,A,型駁船,34,B,型駁船,52,航線號,合同貨運量,1,200,2,400,問：應(yīng)如何編隊，才能既完成合同任務(wù)，又使總貨運成本為最??？,線性規(guī)劃問題的數(shù)學(xué)模型,,,,,,解：,設(shè)：,

7、x,j,為第,j,號類型船隊的隊數(shù)（,j,= 1,，,2,，,3,，,4,），,,,,z,,為總貨運成本,則：,,min,z,= 36,x,1,+ 36,x,2,+ 72,x,3,+ 27,x,4,,,x,1,+,x,2,+ 2,x,3,+,x,4,≤ 30,,2,x,1,+ 2,x,3,≤ 34,,4,x,2,+ 4,x,3,+ 4,x,4,≤ 52,,25,x,1,+20,x,2,,＝,200,,40,x,3,+20,x,4,＝,400,,,x,j,,≥ 0,（,j,= 1,2,3,4,）,,線性規(guī)劃問題的數(shù)學(xué)模型,,,線性規(guī)劃問題的數(shù)學(xué)模型,,2.,線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成,決策

8、變量,Decision variables,,目標(biāo)函數(shù),Objective function,,約束條件,Constraints,其特征是：,,（,1,）問題的目標(biāo)函數(shù)是多個決策變量的,線性,函數(shù)，通常是求最大值或最小值；,,（,2,）問題的約束條件是一組多個決策變量的,線性,不等式或等式。,,怎樣辨別一個模型是線性規(guī)劃模型？,,,線性規(guī)劃問題的數(shù)學(xué)模型,,3.,建模條件,,(1),,優(yōu)化條件,：問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值,,（,max,或,min,）來表示；,(2),,限定條件（約束條件）,：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的,,線性等式或線性不等式表示

9、；,(3),,選擇條件,：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。,,線性規(guī)劃問題的數(shù)學(xué)模型,,4.,建模步驟,,(1),,確定決策變量,：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量；,(2),,找出所有限定條件,：即決策變量受到的所有的約束；,(3),,寫出目標(biāo)函數(shù),：即問題所要達(dá)到的目標(biāo)，并明確是,max,還是,min,。,,線性規(guī)劃問題的數(shù)學(xué)模型,,目標(biāo)函數(shù)：,約束條件：,5.,線性規(guī)劃數(shù)學(xué)模型的一般形式,簡寫為：,,線性規(guī)劃問題的數(shù)學(xué)模型,,向量形式：,其中：,,線性規(guī)劃問題的數(shù)學(xué)模型,,矩陣形式：,其中：,,線性規(guī)劃問題的數(shù)學(xué)模型,,6.,線性規(guī)

10、劃問題的標(biāo)準(zhǔn)形式,,特點：,,(1),目標(biāo)函數(shù)求最大值（有時求最小值）,,(2),約束條件都為等式方程，且右端常數(shù)項,b,i,都大于或等于零,,(3),決策變量,x,j,為非負(fù)。,,線性規(guī)劃問題的數(shù)學(xué)模型,,（,2,）如何化標(biāo)準(zhǔn)形式,目標(biāo)函數(shù)的轉(zhuǎn)換,如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以,,(-1),，可化為求極大值問題。,也就是：令 ，可得到上式。,即,,若存在取值無約束的變量 ，可令,,其中：,變量的變換,,線性規(guī)劃問題的數(shù)學(xué)模型,,約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。,稱為松弛變量,稱為剩余變量,常量,

11、b,i,＜,0,,的變換,:,約束方程兩邊乘以,（－,1,）,,線性規(guī)劃問題的數(shù)學(xué)模型,,例,1.6,,將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式,用 替換 ，且,,解,:,（１）因為,x,3,無符號要求 ，即,x,3,取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以,,線性規(guī)劃問題的數(shù)學(xué)模型,,(2),第一個約束條件是“≤”號，在“≤”左端加入松馳變量,x,4,，,x,4,≥0,,化為等式；,,(3),第二個約束條件是“≥”號，在“≥”左端減去剩余變量,x,5,，,x,5,≥0,；,,(4),第,3,個約束方程右端常數(shù)項為,-5,，方程兩邊同乘以,(-1),,將右端常數(shù)項化為

12、正數(shù)；,,,(5),目標(biāo)函數(shù)是最小值，為了化為求最大值，令,z′=-z,,得到,max z′=-z,，即當(dāng),z,達(dá)到最小值時,z′,達(dá)到最大值，反之亦然,;,,線性規(guī)劃問題的數(shù)學(xué)模型,,標(biāo)準(zhǔn)形式如下：,,,,,,,例,1.7,將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式,為無約束（無非負(fù)限制）,線性規(guī)劃問題的數(shù)學(xué)模型,,,,,,,,解,:,用 替換 ，且 ，,將第,3,個約束方程兩邊乘以（－,1,）,將極小值問題反號，變?yōu)榍髽O大值,標(biāo)準(zhǔn)形式如下：,引入變量,線性規(guī)劃問題的數(shù)學(xué)模型,,,,,,,,例,1.8,將線性規(guī)劃問題化為標(biāo)準(zhǔn)型,解：,線性規(guī)劃問題的數(shù)學(xué)模型,,,,,,,

13、,例,1.9,將線性規(guī)劃問題化為標(biāo)準(zhǔn)型,解：,Min,f,= -3,x,1,,+ 5,x,2,+ 8,x,3,,- 7,x,4,,s.t. 2,x,1,,- 3,x,2,+ 5,x,3,+ 6,x,4,,≤ 28,,4,x,1,,+ 2,x,2,+ 3,x,3,- 9,x,4,,≥ 39,,6,x,2,+ 2,x,3,+ 3,x,4,≤ - 58,,,x,1,, x,3,, x,4,,≥ 0,；,x,2,無約束,,,Max,z,= 3,x,1,–5,x,2,’+5,x,2,”–8,x,3,+7,x,4,,s.t. 2,x,1,–3,x,2,’+3,x,2,”+5,x,3,+6,x,4,+,x

14、,5,= 28,,4,x,1,+2,x,2,’-2,x,2,”+3,x,3,-9,x,4,-,x,6,= 39,,-6,x,2,’+6,x,2,”-2,x,3,-3,x,4,-,x,7,,= 58,,,x,1,,x,2,’,x,2,”,x,3,,x,4,,x,5,,x,6,,x,7,,≥ 0,線性規(guī)劃問題的數(shù)學(xué)模型,,,線性規(guī)劃問題的數(shù)學(xué)模型,,7.,線性規(guī)劃問題的解,,線性規(guī)劃問題,求解線性規(guī)劃問題，就是從滿足約束條件,(2),、,(3),的方程組中找出一個解，使目標(biāo)函數(shù),(1),達(dá)到最大值。,,線性規(guī)劃問題的數(shù)學(xué)模型,,,可行解,：滿足,約束條件,②,、③,的解為可行解。所有可行解的集合為

15、可行域。,,,最優(yōu)解,：使目標(biāo)函數(shù)達(dá)到最大值的可行解。,,,基：,設(shè),A,為,約束條件,②的,m,×,n,階系數(shù)矩陣,(,m,<,n,),，其秩為,m,，,B,是矩陣,A,中,m,階滿秩子方陣（∣,B,∣≠0,），稱,B,是規(guī)劃問題的一個基。設(shè)：,稱,B,中每個列向量,P,j,,(,j =,1,2, … ,,m,),為基向量。與基向量,P,j,,,對應(yīng)的變量,x,j,,為,基變量,。除基變量以外的變量為,非基變量,。,,線性規(guī)劃問題的數(shù)學(xué)模型,,,基解：,某一確定的基,B,，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非零值的個數(shù)不大于方程數(shù),m,，基解的總數(shù)不

16、超過,,,基可行解：,滿足變量非負(fù)約束條件的基本解，簡稱基可行解。,,可行基：,對應(yīng)于基可行解的基稱為可行基。,,非可行解,可,,行,,解,基解,基可行解,,線性規(guī)劃問題的數(shù)學(xué)模型,,例,1.10,,求線性規(guī)劃問題的所有基矩陣。,解,:,約束方程的系數(shù)矩陣為,2×5,矩陣,r(A,)=2,，,2,階子矩陣有,10,個，其中基矩陣只有,9,個，即,,圖解法,,線性規(guī)劃問題的求解方法,一 般 有,,兩種方法,圖 解 法,,,單純形法,兩個變量、直角坐標(biāo),,三個變量、立體坐標(biāo),適用于任意變量、但必需將,,一般形式變成標(biāo)準(zhǔn)形式,下面我們分析一下簡單的情況,——,只有兩個決策變量的線性規(guī)劃問題，這時可以

17、通過圖解的方法來求解。圖解法具有簡單、直觀的優(yōu)點，便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義。,,解題步驟,4,將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。,1,在直角平面坐標(biāo)系中畫出所有的,約束等式,，并找出所有約束條件的公共部分，稱為可行域，可行域中的點即為可行解。,,2,標(biāo)出,目標(biāo)函數(shù),值增加或者減小的方向。,3,若求最大（?。┲担瑒t令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向,平行移動,，找與可行域最后相交的點，該點就是最優(yōu)解。,圖解法,,,圖解法,,max Z = 2X,1,+ X,2,,,X,1,+ 1.9X,2,≥ 3.8,,X,1,- 1.9X,2,≤ 3.8,,s.t,.

18、 X,1,+ 1.9X,2,≤10.2,,X,1,- 1.9X,2,≥ -3.8,,X,1,，,X,2,≥ 0,例,1.11,用圖解法求解線性規(guī)劃問題,,圖解法,,x,1,x,2,o,X,1,- 1.9X,2,= 3.8,(≤),,X,1,+ 1.9X,2,= 3.8(,≥),X,1,- 1.9X,2,= -3.8 (,≥),X,1,+ 1.9X,2,= 10.2,(≤),4 = 2,X,1,+ X,2,,20 = 2,X,1,+ X,2,,17.2 = 2,X,1,+ X,2,,,Lo,：,0 = 2X,1,+ X,2,,（,7.6,，,2,）,D,max Z,min Z,,此點是唯一最優(yōu)解

19、，,,且最優(yōu)目標(biāo)函數(shù)值,,,max Z=17.2,可行域,max Z = 2X,1,+ X,2,,圖解法,,max Z=3X,1,+5.7X,2,x,1,x,2,o,X,1,- 1.9X,2,= 3.8,(≤),X,1,+ 1.9X,2,= 3.8(,≥),X,1,- 1.9X,2,= -3.8(,≥),X,1,+ 1.9X,2,= 10.2,(≤),（,7.6,，,2,）,D,,L,0,： 0=3X,1,+5.7X,2,,,,max Z,（,3.8,，,4,）,34.2,= 3,X,1,+5.7X,2,,藍(lán)色線段上的所有點都是最,,優(yōu)解這種情形為有無窮多最,,優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值,,m

20、ax Z=34.2,是唯一的。,可行域,,圖解法,,min Z=5X,1,+4X,2,x,1,x,2,o,X,1,- 1.9X,2,= 3.8,(≤),X,1,+ 1.9X,2,= 3.8(,≥),X,1,+ 1.9X,2,= 10.2,(≤),D,,L,0,： 0=5X,1,+4X,2,,max Z,min Z,8=5X,1,+4X,2,,43=5X,1,+4X,2,,（,0,，,2,）,,可行域,此點是唯一最優(yōu)解,,圖解法,,2,4,6,x,1,x,2,2,4,6,無界解,(,無最優(yōu)解,),max,Z,=,x,1,+2,x,2,例,1.6,x,1+,x,2=4(≥),x,1+3,x,2=6

21、(≥),3,x,1+,x,2=6(≥),max,Z,min,Z,,,x,1,x,2,O,10,20,30,40,10,20,30,40,50,50,無可行解,(,即無最優(yōu)解,),max Z=3,x,1,+4,x,2,例,1.7,,由圖解法得到的幾種情況,根據(jù)以上例題，進一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況：,,,1.,可行域為封閉的有界區(qū)域,,,(a),有唯一的最優(yōu)解；,(b),有無窮多個最優(yōu)解；,,,2.,可行域為封閉的無界區(qū)域,,,(c),有唯一的最優(yōu)解；,(d),有無窮多個最優(yōu)解；,,,(e),目標(biāo)函數(shù)無界,(,即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無

22、限減少,),，因而沒有有限最優(yōu)解。,,,3.,可行域為空集,,,(f),沒有可行解，原問題無最優(yōu)解,圖解法,,,由圖解法得到的啟示,線性規(guī)劃問題解的情況：,,,唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解,(2),線性規(guī)劃問題的可行域是凸集（凸多邊形）,圖解法,,,圖解法,,x,1,x,2,o,X,1,- 1.9X,2,= 3.8,(≤),,X,1,+ 1.9X,2,= 3.8(,≥),X,1,- 1.9X,2,= -3.8 (,≥),X,1,+ 1.9X,2,= 10.2,(≤),17.2 = 2,X,1,+ X,2,,,Lo,：,0 = 2X,1,+ X,2,,（,7.6,，,2,）,D,m

23、ax Z,min Z,,可行域,max Z = 2X,1,+ X,2,,(3),最優(yōu)解一定是在凸集的某個頂點,,,解題思路,,先找出凸集的任一頂點，計算其目標(biāo)函數(shù)值，再與周圍頂點的目標(biāo)函數(shù)值比較，如不是最大（或最?。?，繼續(xù)比較，直到找出最大（或最小）為止。,圖解法,,,圖解法,,學(xué)習(xí)要點：,,,1.,通過圖解法了解線性規(guī)劃有幾種解的形式,,（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）,,,2.,作圖的關(guān)鍵有三點：,,,(1),可行解區(qū)域要畫正確,,,(2),目標(biāo)函數(shù)增加的方向不能畫錯,,,(3),目標(biāo)函數(shù)的直線怎樣平行移動,,連接幾何形體中任意兩點的線段仍完全在該幾何形體之中。,,有限個凸

24、集的交集仍然是凸集。,單純形法基本原理,,凸集,,單純形法基本原理,,凸集：如果集合,C,中任意兩個點,X,1,、,X,2,，其連線上的所有點也都是集合,C,中的點，稱,C,為凸集。,凸集,凸集,不是凸集,,單純形法基本原理,,凸集,凸集,頂 點,頂點：如果凸集,C,中不存在任何兩個不同的點,X,1,，,X,2,，使,X,成為這兩個點連線上的一個點,,單純形法基本原理,,定理,1,：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。,,定理,2,：線性規(guī)劃問題的基可行解,X,對應(yīng)可行域,(,凸集,),的頂點。,,定理,3,：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（即在某個頂點取得）,

25、,幾個基本定理的證明,定理,1,,若線性規(guī)劃問題存在可行解，則問題的可行域是凸集,。,,思路：若滿足線性規(guī)劃約束條件 的所有點組成的幾何圖形,C,是凸集，根據(jù)凸集的定義，,C,內(nèi)任意兩點,X,1,,,X,2,連線上的點也必然在,C,內(nèi) 。,,【,證,】,設(shè) 為,C,內(nèi)任意兩點，即,,，將,X,1,,,X,2,代入約束條件有,,,X,1,,,X,2,連線上任意一點可以表示為：,,,將,(1.9),代入約束條件并由式,(1.8)

26、,得：,,,,,,所以 。由于集合內(nèi)任意兩點連線上的點均在集合內(nèi)，所以,C,,為凸集。,,,一個引理,引理,,線性規(guī)劃問題的可行解 為基可行解的的充要條件是,X,的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。,,【,證,】,必要性由基可行解的定義是顯然的。,,充分性：若向量,P,1,,,P,2,, …,,P,k,是線性獨立的，則必有,k,≤,m,。,,1),當(dāng),k,=,m,時，它們恰好構(gòu)成一個基，從而相應(yīng)的基可行解為,,,2),當(dāng),k,<,m,時，則一定可以從其余列向量中

27、找出,(,m,-,k,),個向量與,P,1,,,P,2,, …,,P,k,構(gòu)成一個基，其對應(yīng)的解恰為,X,，根據(jù)定義它是基可行解。,,,定理,2,線性規(guī)劃問題的基可行解,X,對應(yīng)于線性規(guī)劃問題可行域（凸集）的頂點,。,,本定理需要證明：,X,是可行域頂點,?,X,是基可行解。采用的是反證法，即證明,X,不是可行域的頂點?,X,不是基可行解。,,【,證,】,（,1,）,X,不是基可行解?,X,不是可行域的頂點。,,不失一般性，假設(shè),X,的前,m,個分量為正，故有,,,根據(jù)假設(shè),X,不是基可行解，由引理知 線性相關(guān)，即存在一組不全為零的數(shù)

28、 使得有,,,上式乘上一個不為零的數(shù),?,得：,,,±,,,,,令,,,,,,即,X,不是可行域的頂點。,,,（,2,）,X,不是可行域的頂點,?,X,不是基可行解。,,不失一般性，設(shè) 不是可行域的頂點，因而可以找到可行域內(nèi)另外兩個不同點,Y,和,Z,，有：,,,,或可寫為：,,,因 ，故當(dāng) 時，必有,,因有,,,故有,,,,,兩式相減得,,,,因 不全為零，故 線性相關(guān)，由引理知

29、,X,不是基可行解。,,,定理,3,,若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。,,【,證,】,設(shè) 是線性規(guī)劃的一個最優(yōu)解，,,是目標(biāo)函數(shù)的最大值。,,若 不是基可行解，由定理,2,知 不是頂點，一定能在可行域內(nèi)找到通過 的直線上的另外兩個點,,,將這兩個點代入目標(biāo)函數(shù)有,,,因 為目標(biāo)函數(shù)的最大值，故有,,,由此 ，即有,,,如果 仍不是基可行解，按上面的方法繼續(xù)做下去，最后一定可

30、以到到一個基可行解，其目標(biāo)函數(shù)值等于 ，問題得證。,,,單純形法的計算步驟,,單純形法的思路,找出一個初始可行解,是否最優(yōu),轉(zhuǎn)移到另一個基本可行解,,（找出更大的目標(biāo)函數(shù)值）,最優(yōu)解,是,否,循,,環(huán),核心是：變量迭代,結(jié)束,,STEP1,確定初始基可行解,,當(dāng)線性規(guī)劃的約束條件全部為“≤”時，,,,,,,在第,i,個約束條件上加上松弛變量,x,si,(,i,=1,…,,m,),，化為標(biāo)準(zhǔn)形式,,,那么約束方程滿足的系數(shù)矩陣為,,,,,,該矩陣中含一個單位矩陣，只要以此作為基，就可以立即解出基變量的值,x,si,=,b,i,(,i,=1,…,,m,),。因為有,b,i,≥

31、0(,i,=1,…,,m,),，由此得到,X,=(0,…,0,,b,1,,…,,b,m,),T,就是一個基可行解。,,,當(dāng)線性規(guī)劃約束條件為“＝”或者“≥”時，化為標(biāo)準(zhǔn)形后，一般約束條件的系數(shù)矩陣也不含有單位矩陣。,人工基,→,初始可行解,人工變量法,,,STEP2,從初始基可行解轉(zhuǎn)化為另一基可行解,,,設(shè)初始基可行解為 ，其中非零坐標(biāo)有,m,個。不失一般性，假定前,m,個坐標(biāo)為非零，即,,,可行基為：,[,P,1,,P,2,…,P,m,],,因 ，故有,,,寫出其系數(shù)矩陣的增廣矩陣，用構(gòu)造人工基的方法

32、可以使基矩陣是單位矩陣形式。,,,因為 是一個基，其他向量可用這個基的線性組合來表示,,,,將（,1.16,）式乘上一個正的數(shù),?,>0,得,,,式,(1.15)+,式,(1.17),，并經(jīng)過整理后有,,,由上式找到滿足約束方程組 的另外一個點：,,,其中,?,是 的第,j,,個坐標(biāo)的值。,,要使 是一個基可行解，因,?,> 0,，故應(yīng)對所有,i,=1,..,,m,存在,,,且這,m,個不等式中至少有一個等號成立，因為當(dāng) 時，上式顯然成立。,,,,,,,這樣 中正分量最多有,m

33、,個，容易證明,m,個向量,,,線性無關(guān)，故只需按式,(1.20),來確定,?,的值， 就是一個新的基可行解。,令,,,基本可行解和可行基的變換,基本可行解：,可行基：,換出基,換入基,,,STEP3,最優(yōu)性檢驗和解的判別,,將基可行解 分別代入目標(biāo)函數(shù)得,,,,,,因,?,,>0,為給定，所以只要有,,,通常簡寫為 ，它是對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標(biāo)志。,,,當(dāng)所有的 時，表明現(xiàn)有頂點（基可行解）的目標(biāo)函數(shù)值比起相鄰各頂點（基可行解）的目標(biāo)函數(shù)值都大，現(xiàn)有頂點對應(yīng)的基可行解

34、即為,最優(yōu)解,。,,當(dāng)所有 時，對某個非基變量,x,j,,有 ，且按公式,(1.20),可找到,?,>0,，這表明可以找到另一頂點（基可行解）目標(biāo)函數(shù)也達(dá)到最大。由于該兩點連線上的點也屬可行域內(nèi)的點，且目標(biāo)函數(shù)值相等，即該線性規(guī)劃問題,有無窮多最優(yōu)解,。,,如果存在某個 又,P,j,向量的所有分量,a,ij,≤0,。換基時對任意,?,,>0,,恒有 因,?,取值可無限大，在由,X,(0),換到,X,(1),時目標(biāo)函數(shù)值也可無限大，則線性規(guī)劃問題,存在無界解,。,,,引例：,

35、求解線性規(guī)劃問題,LP,規(guī)劃問題的最優(yōu)解可從基可行解（頂點）中找到,,,?,圖解法有局限性；,,,?,枚舉法計算量大；,,,解：,第一,:,將該問題化成標(biāo)準(zhǔn)形,第二,:,,找初始可行解,(,即一個頂點,),。,,系數(shù)矩陣,A,=(,P,1,,P,2,,P,3,,P,4,,P,5,),矩陣形式,,,,因為,P,3,，,P,4,，,,P,5,線性獨立，故,B,=(,P,3,,,P,4,,,P,5,),構(gòu)成一個基，其對應(yīng)的基變量,x,3,，,x,4,，,x,5,，,解出來為（,用非基變量表示基變量,）,,,,,x,3,=8-,x,1,-2,x,2,,,x,4,=16-4,x,1,(1),,,x,5,

36、=12- 4,x,2,X,B,=,B,-1,,b,,,–,B,-1,NX,N,將,(1),代入目標(biāo)函數(shù)中得,z,=0+2,x,1,+3,x,2,,,令非基變量,x,1,=,x,2,=0,，,則有,z,=0,。,這時得到一個基可行解：,,,X,(0),=(0,0,8,16,12),T,---,原點,,,第三,:,判別,,從目標(biāo)函數(shù),z,=0+2,x,1,+3,x,2,中得知，非基變量,x,1,和,x,2,的系數(shù)為正，因此，將非基變量換入基后可使目標(biāo)函數(shù)增大，轉(zhuǎn)入第四步,第四：,換基,(,旋轉(zhuǎn)迭代,),,,確定換入變量：由于非基變量,x,2,的系數(shù)（正）貢獻最大，故需換入的基變量為,x,2,。,,

37、,換入變量已定，必須從,x,3,，,x,4,，,x,5,換出一個，并且要保證其余均是非負(fù)的，即,x,3,，,x,4,，,x,5,?0,。,當(dāng),x,1,=0,時，有,x,3,=8- 2,x,2,,?0,,,,x,4,=16,?0,,,,x,5,=12- 4,x,2,?0,x,2,換入基，,x,1,未換入，還是非基變量,,,只要選擇,x,2,=min (8/2,，,-,，,12/4)=3,，,對應(yīng)基變量,x,5,=0,，,從而確定用,x,2,和,x,5,對換,，即將,x,5,,換出，（,用非基變量表示基變量,）,,2,x,2,+,,x,3,=8-,x,1,,x,4,=16-,,4,x,1,4,x,

38、2,=12-,x,5,,,用高斯消去法（行變換），得,,,,x,3,=2-,x,1,+ 1/2,x,5,,x,4,=16-,,4,x,1,,x,2,,,=3- 1/4,x,5,,（,2,）,將上式代入原目標(biāo)函數(shù)中得,,z,=9+2,x,1,-3/4,x,5,（,1,）,,,返回第三步： 從,z,=9+2,x,1,-3/4,x,5,，非基變量,x,1,的系數(shù)是正的，還可增大。重復(fù)上述步驟。由于,x,1,的系數(shù)是正的，則,x,1,為轉(zhuǎn)入變量，再由當(dāng),x,5,=0,時,,,x,3,=2-,x,1,,?0,,,,x,4,=16-,,4,x,1,?0,,,,x,2,=3,?0,,只要選,,x,1,=mi

39、n{2,，,16/4,，,-}=2,,上式就成立，因為,x,1,= 2,時，基變量,x,3,=0,，,從而,由,x,1,換出,x,3,令非基變量,x,1,和,x,5,為零有,z,=9,，又得到另一個基可行解,,,X,(1),=(0,3,2,16,0),T,–,頂點,Q,4,,,,x,1,+2,x,2,=8-,x,3,,,4,x,1,+,x,4,=16,,(3),,4,x,2,=12-,x,5,,高斯消去法（行變換）得,,,x,1,=2-,x,3,+1/2,x,5,?0,,,,x,4,=8-2,x,5,+4,x,3,?0,,,,x,2,=3- 1/4,x,5,,?0,,代入目標(biāo)函數(shù)中，得,,,z

40、,=13-2,x,3,+1/4,x,5,,令非基變量,x,3,=,x,5,=0,有,z,=13,，又得到另一個基可行解,,,X,(2),=(2,3,0,8,0),T,–,頂點,Q,3,;,（,2,）,用非基變量表示基變量,,,同理，返回第三步，再迭代，,x,5,作為轉(zhuǎn)入變量,只要取,,x,5,=min{-,，,8/2,，,12}=4,,就有上式成立。,x,5,=4,時，,x,4,=0,，,故用,x,5,換,x,4,,,x,1,=4- 1/4,x,4,,,,x,5,=4-1/2,x,4,+2,x,3,,,x,2,=2+1/8,x,4,–1/2,x,3,,令,x,3,=0，有,x,1,=2+1/2

41、,x,5,,?0,,,,x,4,=8-2,x,5,?0,,,,x,2,=3- 1/4,x,5,,?0,,（,3,）,+,高斯,,,0,Q,4,Q,3,Q,2,Q,1,1,1,2,3,2,3,4,X,1,X,2,x,1,+2,x,2,=8,4,x,1,=16,4,x,2,=12,代入得,z,=14-3/2,x,3,-1/8,x,4,,，令,x,3,=,x,4,=0,得,z,=14,。,新的基可行解為,,,,X,(3),=(4,2,0,0,4),T,–,頂點,Q,2,(,最優(yōu)解,),,最優(yōu)目標(biāo)值,z,=14,,。,(0,3,2,16,0),(0,0,8,16,12),(2,3,0,8,0),(4,

42、2,0,0,4),,,單純形法的計算步驟,,單純形表,確定換出基,確定換入基,,單純形法的計算步驟,,例,1.12,用單純形法求下列線性規(guī)劃的最優(yōu)解,解：,1,）,將問題化為標(biāo)準(zhǔn)型，加入松馳變量,x,3,、,x,4,則標(biāo)準(zhǔn)型為,:,,單純形法的計算步驟,,2,）求出線性規(guī)劃的初始基可行解，列出初始單純形表。,c,j,,,3,4,0,0,θ,i,c,B,基,b,x,1,x,2,x,3,x,4,,0,x,3,40,2,1,1,0,,0,x,4,30,1,3,0,1,,,,,3,4,0,0,,,,檢驗數(shù),,單純形法的計算步驟,,3,）進行最優(yōu)性檢驗,如果表中所有檢驗數(shù) ，

43、則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。,4,）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表,確定換入基的變量。選擇 ，對應(yīng)的變量,x,j,作為換入變量，當(dāng)有一個以上檢驗數(shù)大于,0,時，一般選擇最大的一個檢驗數(shù)，即： ，其對應(yīng)的,x,k,作為,換入變量,。,,確定換出變量。根據(jù)下式計算并選擇,θ,,，,選最小的,θ,對應(yīng)基變量作為,換出變量,。,,主元素,,單純形法的計算步驟,,用換入變量,x,k,替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新

44、的基可行解，并相應(yīng)地可以畫出一個新的單純形表。,,,,,,,5,）重復(fù),3,）、,4,）步直到計算結(jié)束為止。,在新表中的基仍應(yīng)該是單位矩陣,，則應(yīng)將主元素所對應(yīng)的列,(,換入基,),變成單位向量，包括約束條件的系數(shù)矩陣，基對應(yīng)的值，檢驗數(shù)等,,換入變量,x,k,的檢驗數(shù)應(yīng)為,0,高斯變換,,單純形法的計算步驟,,c,j,,,3,4,0,0,θ,i,C,B,基變量,b,x,1,x,2,x,3,x,4,,0,x,3,40,2,1,1,0,,0,x,4,30,1,3,0,1,,,,,3,4,0,0,,0,x,3,,,,,,,4,x,2,,,,,,,,,,,,,,,3,x,1,,,,,,,4,x,2,

45、,,,,,,,,,,,,,,換入列,b,i,/a,i2,，,a,i2,>0,40,10,換出行,將,3,化為,1,5/3,1,18,0,1/3,0,1/3,10,1,-1/3,30,30,0,5/3,0,-4/3,乘以,1/3,后得到,1,0,3/5,-1/5,18,0,1,-1/5,2/5,4,0,0,-1,-1,,單純形法的計算步驟,,例,1.13,,用單純形法求解,解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：,不難看出,x,4,、,x,5,可作為初始基變量，列單純形表計算。,,單純形法的計算步驟,,c,j,,,1,2,1,0,0,θ,i,C,B,基變量,b,x,1,x,2,x,3,x,4,x,5,,0,

46、x,4,15,2,-3,2,1,0,,0,x,5,20,1/3,1,5,0,1,,,,,1,2,1,0,0,,0,x,4,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2,x,2,,,,,,,,,,,,,,,,,20,－,x,2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,－,9,0,－,2,25,60,x,1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,,變成標(biāo)準(zhǔn)型,單純形法的計算步驟,,例,1.14,用單純形法求解,,約束方程的系數(shù)矩陣,為基變量,為非基變量,I,為單位矩陣且線性獨立,單純形法的計算步驟,,,,,,單純形法的計算步驟,,學(xué)習(xí)要點：,,,1.,線性規(guī)劃解的概念以及,3,個基本定理,,,2.,熟練掌握線性規(guī)劃問題的標(biāo)準(zhǔn)化,,,3.,熟練掌握單純形法的解題思路及求解步驟,,作業(yè),,P47,,1.1,用圖解法求解下列線性規(guī)劃問題，并指出問題解的類型,,,,,,,,,,作業(yè),,P47,,1.2,對下述線性規(guī)劃問題找出所有基解，指出那些是基可行解，并確定最優(yōu)解,,,作業(yè),,P47,,1.3,分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中的各基可行解分別對應(yīng)圖解法中可行域的哪一頂點。,,,