第二章圖解法與單純形法改

第二章圖解法與單純形法改第一頁，共七十頁，編輯于2023年，星期五2.1線性規(guī)劃問題的圖解法圖解法是用作圖的方法求解線性規(guī)劃問題，一般只適用于具有兩個決策變量的線性規(guī)劃問題。步驟1畫直角坐標系步驟2根據(jù)約束條件畫出可行域步驟3畫過坐標原點的目標函數(shù)線步驟4確定目標函數(shù)的增大方向步驟5讓目標函數(shù)沿著增大方向平行移動，與可行域相交且有最大目標函數(shù)值的頂點，即為線性規(guī)劃問題的最優(yōu)解。第二頁，共七十頁，編輯于2023年，星期五x1x2O1020304010203040(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85例題第三頁，共七十頁，編輯于2023年，星期五2.1線性規(guī)劃問題的圖解法

用圖解法求解如下線性規(guī)劃問題：

例1第四頁，共七十頁，編輯于2023年，星期五2.1線性規(guī)劃問題的圖解法求解Q3點為（3，3），此時z=15第五頁，共七十頁，編輯于2023年，星期五2.1線性規(guī)劃問題的圖解法本例中我們用圖解法得到的問題的最優(yōu)解是惟一的。但在線性規(guī)劃問題的計算中,解的情況還可能出現(xiàn)下列幾種:1無窮最優(yōu)解。如將本例的目標函數(shù)改變?yōu)閯t目標函數(shù)的圖形恰好與(1)平行。因此該線性規(guī)劃問題有無窮多個最優(yōu)解,也稱具有多重最優(yōu)解。第六頁，共七十頁，編輯于2023年，星期五2.1線性規(guī)劃問題的圖解法2.無界解(有可行解但無有界最優(yōu)解)。如果本例中約束條件只剩下(2)和(4),其他條件(1)、(3)不再考慮。用圖解法求解時,可以看到變量的取值可以無限增大,因而目標函數(shù)的值也可以一直增大到無窮。這種情況下稱問題具有無界解或無最優(yōu)解。其原因是由于在建立實際問題的數(shù)學模型時遺漏了某些必要的資源約束。第七頁，共七十頁，編輯于2023年，星期五2.1線性規(guī)劃問題的圖解法3.無可行解。如下述線性規(guī)劃模型：用圖解法求解時找不到滿足所有約束條件的公共范圍，這時問題無可行解。其原因是模型本身有錯誤,約束條件之間相互矛盾,應檢查修正。

第八頁，共七十頁，編輯于2023年，星期五圖解法雖然只能用來求解只具有兩個變量的線性規(guī)劃問題,但它的解題思路和幾何上直觀得到的一些概念判斷,對下面要講的求解一般線性規(guī)劃問題的單純形法有很大啟示:線性規(guī)劃問題求解的基本依據(jù)是：線性規(guī)劃問題的最優(yōu)解總可在可行域的頂點中尋找，尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個頂點處的目標函數(shù)值。線性規(guī)劃問題求解時可能出現(xiàn)四種結局：唯一最優(yōu)解無窮多個最優(yōu)解無有界解無解或無可行解如果某一線性規(guī)劃問題有最優(yōu)解，可以按照以下思路求解：先找可行域中的一個頂點，計算頂點處的目標函數(shù)值，然后判別是否有其他頂點處的目標函數(shù)值比這個頂點處的目標函數(shù)值更大，如有，轉到新的頂點，重復上述過程，直到找不到使目標函數(shù)值更大的新頂點為止。第九頁，共七十頁，編輯于2023年，星期五線性規(guī)劃的基本性質凸集對集合C中任意兩個點其連線上的所有點都是集合C中的點，則C為凸集。由于的連線可以表示為，因此凸集的數(shù)學表達為：對任意的，有則稱C為凸集。第十頁，共七十頁，編輯于2023年，星期五

線性規(guī)劃的基本性質定理1

若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。引理線性規(guī)劃問題的可行解X=(x1,x2,…,xn)T為基可行解的充要條件是X的正分量對應的系數(shù)列向量是線性獨立的。定理2線性規(guī)劃問題的基可行解對應可行域的頂點。定理3

若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。第十一頁，共七十頁，編輯于2023年，星期五從可行域中的一個基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如果不是，尋找下一個基可行解，并且同時努力使目標函數(shù)得到改進，如此迭代下去，直到找到最優(yōu)解或判定問題無解為止?；舅枷耄?.2線性規(guī)劃單純形法的原理與計算步驟3尋找改進的基可行解2最優(yōu)性檢驗和解的判別1確定初始基可行解第十二頁，共七十頁，編輯于2023年，星期五【例2】用單純形法求下列線性規(guī)劃的最優(yōu)解第十三頁，共七十頁，編輯于2023年，星期五單純形法的計算步驟：步驟1：求初始基可行解，列出初始單純形表。

對非標準形式的線性規(guī)劃問題首先要化成標準形式。由于我們總可以設法使約束方程的系數(shù)矩陣中包含一個單位矩陣[P1,P2,…,Pm]，以此作為基即可求得問題的一個初始基可行解。必須是標準形式第十四頁，共七十頁，編輯于2023年，星期五【解】首先化為標準型，加入松馳變量x3、x4則標準型為系數(shù)矩陣A及可行基B1r(B1)=2，B1是單位矩陣作為初始基,x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0由約束方程知x3=40、x4=30得到初始基可行解X(1)=(0,0,40,30)T

第十五頁，共七十頁，編輯于2023年，星期五單純形法的計算步驟：步驟2最優(yōu)性檢驗在單純形表中，若所有的檢驗數(shù)表中的基可行解即為最優(yōu)解。若存在并且有，則問題無有界解。計算結束。否則轉入下一步。步驟3從一個基可行解轉換到相鄰的目標函數(shù)更大的基可行解，列出新的單純形表。步驟4重復步驟2和3，一直到計算結束。第十六頁，共七十頁，編輯于2023年，星期五進基列出基行bi/ai2，ai2>0θi表1-4(1)XBx1x2x3x4bx3211040x4130130σ

j3400

(2)x3x2σ

j

(3)x1

x2

σ

j

基變量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/5

2/5400-1-1將3化為1乘以1/3后得到3018第十七頁，共七十頁，編輯于2023年，星期五單純形算法的計算步驟①將線性規(guī)劃問題化成標準型。②找出或構造一個m階單位矩陣作為初始可行基，建立初始單純形表。③計算各非基變量xj的檢驗數(shù)j，若所有j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步。④在大于0的檢驗數(shù)中，若某個k所對應的系數(shù)列向量Pk≤0，則此問題是無界解，停止計算，否則轉入下步。⑤根據(jù)max{j｜j＞0}=k原則，確定xk為換入變量(進基變量)，再按規(guī)則計算：=min{bi/aik|aik＞0}=bl/aik確定xl為換出變量。建立新的單純形表，此時基變量中xk取代了xl的位置。⑥以aik為主元素進行迭代，把xk所對應的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?，同列中其它元素為0，轉第③步。

第十八頁，共七十頁，編輯于2023年，星期五2.2線性規(guī)劃單純形法的原理與計算步驟單純形法計算中可能出現(xiàn)以下兩種情況：出現(xiàn)兩個以上，原則上可任取一個對應的為換入基的變量；相持。即計算值出現(xiàn)兩個以上相同的最小值。則可任選其中一個基變量作為換出變量。但是為防止出現(xiàn)循環(huán)現(xiàn)象，先后有人提出了一些方法。如：勃蘭特法；字典序法；攝動法。（1選取檢驗數(shù)中下標最小的非基變量為換入變量（2按規(guī)則計算時，若出現(xiàn)兩個和兩個以上的最小比值時，選取下標最小的基變量為換出變量。第十九頁，共七十頁，編輯于2023年，星期五單純形法的計算

用單純形法求解線性規(guī)劃問題：

例3第二十頁，共七十頁，編輯于2023年，星期五最優(yōu)解的判別定理定理1最優(yōu)解的判別定理

定理2有無窮多最優(yōu)解的判別定理

第二十一頁，共七十頁，編輯于2023年，星期五單純形法的計算

用單純形法求解線性規(guī)劃問題：

例4第二十二頁，共七十頁，編輯于2023年，星期五最優(yōu)解的判別定理定理3有無界解的判別定理

第二十三頁，共七十頁，編輯于2023年，星期五單純形法的計算

用單純形法求解線性規(guī)劃問題：

例題5第二十四頁，共七十頁，編輯于2023年，星期五XBx1x2x3x3401λj230第二十五頁，共七十頁，編輯于2023年，星期五唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)小于零,則線規(guī)劃具有唯一最優(yōu)解

。多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無界解的判斷:

某個且aij≤０（i=1，2,…,m）則線性規(guī)劃具有無界解第二十六頁，共七十頁，編輯于2023年，星期五【練習1】用單純形法求解第二十七頁，共七十頁，編輯于2023年，星期五Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表1－51/3150120301713751/30－90－2M2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值Z=145/3第二十八頁，共七十頁，編輯于2023年，星期五【練習2】求解線性規(guī)劃【解】化為標準型第二十九頁，共七十頁，編輯于2023年，星期五初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2為換入變量，而第二列的數(shù)字均小于0，因此線性規(guī)劃的最優(yōu)解無有界解。由模型可以看出，當固定x1使x2→+∞且滿足約束條件，還可以用圖解法看出具有無界解。第三十頁，共七十頁，編輯于2023年，星期五【練習3】求解線性規(guī)劃【解】:化為標準型后用單純形法計算如下表所示第三十一頁，共七十頁，編輯于2023年，星期五XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－20第三十二頁，共七十頁，編輯于2023年，星期五表(3)中λj全部非正,則最優(yōu)解為:表(3)表明,非基變量x3的檢驗數(shù)λ3=0,

使x3作為換入變量，

x5為換入變量繼續(xù)迭代,得到表(4)的另一基本最優(yōu)解

X(1),X(2)是線性規(guī)劃的兩個最優(yōu)解，它的凸組合仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。第三十三頁，共七十頁，編輯于2023年，星期五單純形法計算的矩陣描述第三十四頁，共七十頁，編輯于2023年，星期五單純形法計算的矩陣描述第三十五頁，共七十頁，編輯于2023年，星期五單純形法計算的矩陣描述第三十六頁，共七十頁，編輯于2023年，星期五單純形法計算的矩陣描述第三十七頁，共七十頁，編輯于2023年，星期五單純形法計算的矩陣描述第三十八頁，共七十頁，編輯于2023年，星期五單純形法計算的矩陣描述第三十九頁，共七十頁，編輯于2023年，星期五人工變量法人工變量法的基本思路是：若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量，則在每個約束方程中加入一個人工變量便可在系數(shù)矩陣中形成一個單位向量。

2.3線性規(guī)劃單純形法的進一步討論第四十頁，共七十頁，編輯于2023年，星期五線性規(guī)劃求解的人工變量法第四十一頁，共七十頁，編輯于2023年，星期五線性規(guī)劃求解的人工變量法第四十二頁，共七十頁，編輯于2023年，星期五由于單位陣作為基陣，因此，選加入的人工變量為基變量。然后，再通過基變換，使得基變量中不含非零的人工變量。如果在最終單純形表中還存在非零的人工變量，這表示無可行解。大M法兩階段法第四十三頁，共七十頁，編輯于2023年，星期五第四十四頁，共七十頁，編輯于2023年，星期五

為了使加入人工變量后線性規(guī)劃問題的最優(yōu)目標函數(shù)值不受影響，我們賦予人工變量一個很大的負價值系數(shù)-M(M為任意大的正數(shù))。線性規(guī)劃求解的大M法第四十五頁，共七十頁，編輯于2023年，星期五線性規(guī)劃求解的大M法第四十六頁，共七十頁，編輯于2023年，星期五由于人工變量對目標函數(shù)有很大的負影響，單純形法的尋優(yōu)機制會自動將人工變量趕到基外，從而找到原問題的一個可行基。這種方法我們通常稱其為大M法。第四十七頁，共七十頁，編輯于2023年，星期五【例6】用大M法解下列線性規(guī)劃線性規(guī)劃求解的大M法舉例第四十八頁，共七十頁，編輯于2023年，星期五【解】首先將數(shù)學模型化為標準形式式中x4為剩余變量，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量x6、x7，目標函數(shù)中加入―Mx6―Mx7一項，得到人工變量單純形法數(shù)學模型用前面介紹的單純形法求解，見下表。第四十九頁，共七十頁，編輯于2023年，星期五Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3第五十頁，共七十頁，編輯于2023年，星期五最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3注意：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；第五十一頁，共七十頁，編輯于2023年，星期五【練習】第五十二頁，共七十頁，編輯于2023年，星期五線性規(guī)劃求解的兩階段法第五十三頁，共七十頁，編輯于2023年，星期五線性規(guī)劃求解的兩階段法第二階段，單純形法求解原問題第一階段計算得到的最終單純形表中除去人工變量，將目標函數(shù)行的系數(shù)，換成原問題的目標函數(shù)后，作為第二階段計算的初始表，繼續(xù)求解。

第五十四頁，共七十頁，編輯于2023年，星期五【例】用兩階段單純形法求解例【6】的線性規(guī)劃。第五十五頁，共七十頁，編輯于2023年，星期五【解】標準型為在第一、三約束方程中加入人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計算表如下：第五十六頁，共七十頁，編輯于2023年，星期五Cj00000-1-1

bCBXBx1x2x3x4x5x6x7-10-1x6x5x7－4123－1－212[1]－1000101000014101→λj-212↑-1000

-100x6x5x3－6－32[5]3－2001－100010100

3→81λj-65↑0-100

000x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/511/5λj00000

第五十七頁，共七十頁，編輯于2023年，星期五最優(yōu)解為最優(yōu)值w=0。第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為第五十八頁，共七十頁，編輯于2023年，星期五Cj32-100bCBXBx1x2x3x4x5

2

0

－1

x2

x5

x3

1

0

0

0

0

1

0

1

0λj5↑0000

2

3

－1x2

x1

x30

1

01

0

0

0

0

11

1

0213λj000－5

Cj32－100bCBXBx1x2x3x4x520－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑0000

23－1x2x1x301010000111025/32/31331/319/3λj000－5－25/3

用單純形法計算得到下表最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3第五十九頁，共七十頁，編輯于2023年，星期五【練習】用兩階段法求解線性規(guī)劃。第六十頁，共七十頁，編輯于2023年，星期五【解】第一階段問題為用單純形法計算如下表：第六十一頁，共七十頁，編輯于2023年，星期五Cj0000-1bCBXBx1x2x3x4x50-1x3x5[3]11－2100－1016→4λj

1↑-20-10

0-1x1x5101/3－7/31/3－1/30－10122λj

0-7/3-1/3-10

λj≥0,得到第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標值w=2≠0,x5仍在基變量中,從而原問題無可行解。第六十二頁，共七十頁，編輯于2023年，星期五解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)小于零,則線性規(guī)劃具有唯一最優(yōu)解多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無界解的判斷:

某個λk>0且aik≤０（i=1，2,…,m）則線性