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

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

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

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

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

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

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

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

對(duì)非標(biāo)準(zhǔn)形式的線性規(guī)劃問題首先要化成標(biāo)準(zhǔn)形式。由于我們總可以設(shè)法使約束方程的系數(shù)矩陣中包含一個(gè)單位矩陣[P1,P2,…,Pm]，以此作為基即可求得問題的一個(gè)初始基可行解。必須是標(biāo)準(zhǔn)形式第十四頁(yè)，共七十頁(yè)，編輯于2023年，星期五【解】首先化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為系數(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

第十五頁(yè)，共七十頁(yè)，編輯于2023年，星期五單純形法的計(jì)算步驟：步驟2最優(yōu)性檢驗(yàn)在單純形表中，若所有的檢驗(yàn)數(shù)表中的基可行解即為最優(yōu)解。若存在并且有，則問題無(wú)有界解。計(jì)算結(jié)束。否則轉(zhuǎn)入下一步。步驟3從一個(gè)基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)更大的基可行解，列出新的單純形表。步驟4重復(fù)步驟2和3，一直到計(jì)算結(jié)束。第十六頁(yè)，共七十頁(yè)，編輯于2023年，星期五進(jìn)基列出基行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第十七頁(yè)，共七十頁(yè)，編輯于2023年，星期五單純形算法的計(jì)算步驟①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。②找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)j，若所有j≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個(gè)k所對(duì)應(yīng)的系數(shù)列向量Pk≤0，則此問題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下步。⑤根據(jù)max{j｜j＞0}=k原則，確定xk為換入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=min{bi/aik|aik＞0}=bl/aik確定xl為換出變量。建立新的單純形表，此時(shí)基變量中xk取代了xl的位置。⑥以aik為主元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。

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

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

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

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

第二十一頁(yè)，共七十頁(yè)，編輯于2023年，星期五單純形法的計(jì)算

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

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

第二十三頁(yè)，共七十頁(yè)，編輯于2023年，星期五單純形法的計(jì)算

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

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

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

某個(gè)且aij≤０（i=1，2,…,m）則線性規(guī)劃具有無(wú)界解第二十六頁(yè)，共七十頁(yè)，編輯于2023年，星期五【練習(xí)1】用單純形法求解第二十七頁(yè)，共七十頁(yè)，編輯于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第二十八頁(yè)，共七十頁(yè)，編輯于2023年，星期五【練習(xí)2】求解線性規(guī)劃【解】化為標(biāo)準(zhǔn)型第二十九頁(yè)，共七十頁(yè)，編輯于2023年，星期五初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2為換入變量，而第二列的數(shù)字均小于0，因此線性規(guī)劃的最優(yōu)解無(wú)有界解。由模型可以看出，當(dāng)固定x1使x2→+∞且滿足約束條件，還可以用圖解法看出具有無(wú)界解。第三十頁(yè)，共七十頁(yè)，編輯于2023年，星期五【練習(xí)3】求解線性規(guī)劃【解】:化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如下表所示第三十一頁(yè)，共七十頁(yè)，編輯于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第三十二頁(yè)，共七十頁(yè)，編輯于2023年，星期五表(3)中λj全部非正,則最優(yōu)解為:表(3)表明,非基變量x3的檢驗(yàn)數(shù)λ3=0,

使x3作為換入變量，

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

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

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

為了使加入人工變量后線性規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值不受影響，我們賦予人工變量一個(gè)很大的負(fù)價(jià)值系數(shù)-M(M為任意大的正數(shù))。線性規(guī)劃求解的大M法第四十五頁(yè)，共七十頁(yè)，編輯于2023年，星期五線性規(guī)劃求解的大M法第四十六頁(yè)，共七十頁(yè)，編輯于2023年，星期五由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而找到原問題的一個(gè)可行基。這種方法我們通常稱其為大M法。第四十七頁(yè)，共七十頁(yè)，編輯于2023年，星期五【例6】用大M法解下列線性規(guī)劃線性規(guī)劃求解的大M法舉例第四十八頁(yè)，共七十頁(yè)，編輯于2023年，星期五【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式式中x4為剩余變量，x5為松弛變量，x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x7，目標(biāo)函數(shù)中加入―Mx6―Mx7一項(xiàng)，得到人工變量單純形法數(shù)學(xué)模型用前面介紹的單純形法求解，見下表。第四十九頁(yè)，共七十頁(yè)，編輯于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第五十頁(yè)，共七十頁(yè)，編輯于2023年，星期五最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3注意：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；第五十一頁(yè)，共七十頁(yè)，編輯于2023年，星期五【練習(xí)】第五十二頁(yè)，共七十頁(yè)，編輯于2023年，星期五線性規(guī)劃求解的兩階段法第五十三頁(yè)，共七十頁(yè)，編輯于2023年，星期五線性規(guī)劃求解的兩階段法第二階段，單純形法求解原問題第一階段計(jì)算得到的最終單純形表中除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換成原問題的目標(biāo)函數(shù)后，作為第二階段計(jì)算的初始表，繼續(xù)求解。

第五十四頁(yè)，共七十頁(yè)，編輯于2023年，星期五【例】用兩階段單純形法求解例【6】的線性規(guī)劃。第五十五頁(yè)，共七十頁(yè)，編輯于2023年，星期五【解】標(biāo)準(zhǔn)型為在第一、三約束方程中加入人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計(jì)算表如下：第五十六頁(yè)，共七十頁(yè)，編輯于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

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

用單純形法計(jì)算得到下表最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3第五十九頁(yè)，共七十頁(yè)，編輯于2023年，星期五【練習(xí)】用兩階段法求解線性規(guī)劃。第六十頁(yè)，共七十頁(yè)，編輯于2023年，星期五【解】第一階段問題為用單純形法計(jì)算如下表：第六十一頁(yè)，共七十頁(yè)，編輯于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)目標(biāo)值w=2≠0,x5仍在基變量中,從而原問題無(wú)可行解。第六十二頁(yè)，共七十頁(yè)，編輯于2023年，星期五解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)小于零,則線性規(guī)劃具有唯一最優(yōu)解多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無(wú)界解的判斷:

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