《運(yùn)籌學(xué)》線性規(guī)劃.ppt

《《運(yùn)籌學(xué)》線性規(guī)劃.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《運(yùn)籌學(xué)》線性規(guī)劃.ppt（70頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第2章 線性規(guī)劃,例1 穗羊公司的例子,問該公司每周應(yīng)生產(chǎn)產(chǎn)品I與產(chǎn)品II各多少單位，才能使每周的獲利達(dá)到最大？,假設(shè)產(chǎn)品I、II每周的產(chǎn)量分別是x1和x2，得到如下的數(shù)學(xué)模型,其中s.t.是英文詞組subject to的縮寫，表示“受限制于”的意思，有時(shí)也約去不寫出來。,該問題常稱為生產(chǎn)計(jì)劃問題或產(chǎn)品組合（product mix）問題。,例2 設(shè)有一批規(guī)格為10米長(zhǎng)的圓鋼筋，將它截成分別為3米，4米長(zhǎng)的預(yù)制構(gòu)件的短鋼筋各100根，問怎樣截取最省料？,因?yàn)椋?0米長(zhǎng)的鋼筋截為3米或4米長(zhǎng)，共有三種截法： 截法Ⅰ：3 3 3 1 米 截法Ⅱ：3 3 4 0 米 截法Ⅲ：4 4 0 2 米 假設(shè)按截法Ⅰ，Ⅱ，Ⅲ各截取10米長(zhǎng)的鋼筋分別為x1, x2, x3根,則可以獲得3米長(zhǎng)的短鋼筋的根數(shù)是3x1+2x2,,4米長(zhǎng)短鋼筋的根數(shù)是x2+2x3,,按問題要求它們應(yīng)該不小于100根。,總共用料是x1 + x2 + x3,,要達(dá)到最省料的目的，就必須使總用料最小。,,,,例2的模型就是,,例2 中的問題常稱為下料問題。,線性規(guī)劃的三個(gè)要素： 決策變量 目標(biāo)函數(shù) 約束條件,其次線性規(guī)劃模型必須滿足如下兩個(gè)要求： 目標(biāo)函數(shù)必須是決策變量的線性函數(shù)； 約束條件必須是含決策變量的線性等式或不等式。,運(yùn)籌學(xué)建模步驟: 識(shí)別問題 定義決策變量 建立約束條件 建立目標(biāo)函數(shù),,,,2.2 線性規(guī)劃模型的一般形式和標(biāo)準(zhǔn)形式,為了討論一般的線性規(guī)劃問題的求解。我們先給出線性規(guī)劃模型的一般形式如下：,,2.2.1 線性規(guī)劃的一般模型,這里一共包含有n個(gè)決策變量，m個(gè)約束條件； 對(duì)目標(biāo)函數(shù)既可以求最大的也可以求最小； 約束條件有?, ?, =型； 決策變量通常非負(fù)，但也可以有其它情況； cj: 稱為價(jià)值系數(shù)； bi: 資源常數(shù)（右端常數(shù)） aij稱為技術(shù)系數(shù)、工藝系數(shù),在今后的討論中，為方便起見，還將用到線性規(guī)劃模型一般形式的各種簡(jiǎn)寫的形式。 利用和號(hào)“ ”，線性規(guī)劃模型的一般形式可寫為：,,利用向量，可以將一般形式表示為：,,,其中,在今后的討論，常將矩陣 稱為線性規(guī)劃問題的（約束條件）系數(shù)矩陣。明顯地系數(shù)矩陣 與矩陣 之間存在關(guān)系：,用矩陣的記號(hào)可以將線性規(guī)劃模型一般形式寫成：,,其中 同上，而矩陣 是由各約束條件的系數(shù)（技術(shù)系數(shù)）構(gòu)成的 矩陣：,,,,,,2.2.2 線性規(guī)劃的標(biāo)準(zhǔn)形式,,它具有如下四個(gè)特征： 目標(biāo)函數(shù)求max； 約束條件兩端用“=”連結(jié) ； bi非負(fù)； 所有決策變量xj非負(fù)。,2.2.3 將線性規(guī)劃的模型化為標(biāo)準(zhǔn)形式,1、目標(biāo)函數(shù)求最小值的情形 取原目標(biāo)函數(shù)的相反數(shù)為新的目標(biāo)函數(shù)，對(duì)原目標(biāo)函數(shù)求最小值的問題就等價(jià)于對(duì)這一新的目標(biāo)函數(shù)求最大值的問題。,例如：,等價(jià)于,,2、約束條件為不等式 (a),,轉(zhuǎn)化為,,xs表示決策中尚未使用的那部分資源，因此稱這一變量為松弛變量。,（b）,轉(zhuǎn)化為：,它表示決策結(jié)果超過了實(shí)際需要的部分，因此常稱它為剩余變量。 無論是松弛變量還是剩余變量在決策中都不產(chǎn)生實(shí)際價(jià)值，因此它們?cè)谀繕?biāo)函數(shù)中的系數(shù)都應(yīng)該為零。在后面的討論中，有時(shí)也將松弛變量和剩余變量統(tǒng)稱為松弛變量。,,3、約束條件右端常數(shù)為負(fù)數(shù) 只需將這一約束條件兩端同乘“-1”就可化為一個(gè)等價(jià)的約束條件，其右端常數(shù)滿足標(biāo)準(zhǔn)形式的要求。,4、決策變量不滿足非負(fù)約束 （a）,,,,,,（b） 如x3無約束，則令,,,,,,,,例如，將例1中的線性規(guī)劃模型化為標(biāo)準(zhǔn)形式就是：,其中 就是分別對(duì)第一、第二、第三個(gè)約束條件中添加的松弛變量。,例3 化如下的線性規(guī)劃問題模型,為標(biāo)準(zhǔn)形式。,,(1 )變量,是非正的，所以要將模型中的所有,都用,代替，其中,(2) 變量,無約束，因此取兩個(gè)變量,使得,。在模型中，所有的,都用,代替。,。在模型中，所有的,(5)約束條件2是“,”型的，因此需要在左邊加上一個(gè)松弛變量,化為等式，即,”型的，并且右端的常數(shù)小于零。,(3)目標(biāo)函數(shù)是求最小值的，因此令,，即,,(4)約束條件1是“,然后在兩端乘以-1得,也就是,因此先將其左邊減取一個(gè)剩余變量,使它化為等式：,也就是,。,從而得到模型的標(biāo)準(zhǔn)形式為,課堂練習(xí),某蓄場(chǎng)每日要為每頭牲畜購(gòu)買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場(chǎng)上出售的M、N兩種飼料中選擇，試決定總花費(fèi)最小的購(gòu)買方案。（列出模型）,養(yǎng)分,飼料,課堂練習(xí),某蓄場(chǎng)每日要為每頭牲畜購(gòu)買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場(chǎng)上出售的M、N兩種飼料中選擇，試決定總花費(fèi)最小的購(gòu)買方案。（列出模型）,養(yǎng)分,飼料,答案：設(shè)購(gòu)買M飼料x1，N飼料x2,0.5 x1 +0.1x2≥10 0.2x1 +0.3x2 ≥5 0.3x1 +0.4x2 ≥8 0.2x2 ≥7 x1 , x2≥0,s.t.,,Min Z=300 x1 +200x2,2.3 線性規(guī)劃的圖解法,對(duì)只包含兩個(gè)決策變量的線性規(guī)劃問題，可以用圖解法來求解。圖解法顧名思義就是通過作圖來求解的方法，它簡(jiǎn)單直觀、并有助于說明一般線性規(guī)劃問題求解的基本原理。,,有關(guān)概念 可行解： 我們將滿足線性規(guī)劃問題的所有約束條件的變量x1和x2的一組取值稱為線性規(guī)劃問題的一個(gè)可行解。通常用X表示。 可行域： 我們將可行解的集合稱為可行域。 最優(yōu)解： 因此我們求解線性規(guī)劃問題，就是要求使得目標(biāo)函數(shù)取最優(yōu)值（對(duì)例1，就是取最大值）的可行解，這樣的可行解就稱為線性規(guī)劃問題的最優(yōu)解。 通常用X*表示。 最優(yōu)值： 即最優(yōu)的目標(biāo)函數(shù)值, 通常用z*表示,圖解法步驟: 建立平面直角坐標(biāo)系 圖示約束條件,求可行域 圖示目標(biāo)函數(shù) 求最優(yōu)解,,,,,建立直角坐標(biāo)系,圖示約束條件，求可行域,x1,x2,,,,,,,,,,,,圖示目標(biāo)函數(shù),求最優(yōu)解,x1,x2,,,,,,,,,最優(yōu)解,等值線向右上方移動(dòng)，函數(shù)值變大。在其即將離開可行域時(shí)達(dá)到B（3/2,1）點(diǎn)。所以最優(yōu)解為：,此時(shí)最優(yōu)值為：,2.2.2 線性規(guī)劃求解的可能結(jié)局,1、有唯一的最優(yōu)解,2、有無窮多個(gè)最優(yōu)解 （將目標(biāo)函數(shù)改為 z=4x1+3x2 ）,,,,max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 ≥ 3.8 x1 - 1.9x2≤ 3.8 x1 + 1.9x2 ≤11.4 x1 - 1.9x2 ≥ -3.8 x1 ，x2 ≥ 0,,,,,,,x1,x2,o,x1 - 1.9 x2 = 3.8,x1 + 1.9 x2= 3.8,x1 + 1.9 x2 = 11.4,（7.6,2）,D,,,0=3 x1 +5.7 x2,,,,,max Z,min Z,（3.8,4）,34.2 = 3 x1 +5.7 x2,可行域,,,x1 - 1.9 x2 = -3.8,(0,2),(3.8,0),綠色線段上的所有點(diǎn) 都是最優(yōu)解,即有無窮多最優(yōu)解。Zman=34.2,,3、無界解,指線性規(guī)劃問題有可行解，但是在可行域，目標(biāo)函數(shù)值是無界的，因而達(dá)不到有限最優(yōu)值。因此線性規(guī)劃問題不存在最優(yōu)解。,,4、無可行解,指找不到一組變量能滿足線性規(guī)劃的所有約束條件的情況，也就是線性規(guī)劃問題不存在可行解，或者說可行域是空集。例如線性規(guī)劃問題：,,,,LP 解的幾種情況,注：出現(xiàn)（3）、（4）情況時(shí)，建模有問題,另外兩個(gè)重要的結(jié)論： 線性規(guī)劃問題可行域若不是空集，則它是一個(gè)凸集； 線性規(guī)劃問題的最優(yōu)解若存在，則一定可以在其可行域的一個(gè)頂點(diǎn)上達(dá)到。,最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標(biāo)值 z = 3,,課堂練習(xí) 圖解法求解線性規(guī)劃,例 某工廠經(jīng)市場(chǎng)調(diào)研，決定生產(chǎn)甲、乙兩種產(chǎn)品，其單臺(tái)利潤(rùn)分別為60元和30元，兩種產(chǎn)品共用一種鋼材、一臺(tái)設(shè)備，其資源及獲利情況如下：,求利潤(rùn)最大的產(chǎn)品結(jié)構(gòu)決策。,作業(yè)練習(xí),② 確定目標(biāo)函數(shù)及約束條件——建立數(shù)學(xué)模型,目標(biāo)函數(shù)：,③ 將不等式變?yōu)榈仁讲⒃趚1－x2坐標(biāo)圖中作出直線,④ 最優(yōu)點(diǎn)在凸邊形的頂點(diǎn)，代入（1）式可得maxP,解：,① 設(shè)變量：設(shè)甲生產(chǎn)x1臺(tái)，乙生產(chǎn)x2臺(tái)，可得最大利潤(rùn),2.4 線性規(guī)劃解的基本概念與性質(zhì),在本節(jié)，我們主要考慮模型具有標(biāo)準(zhǔn)形式的線性規(guī)劃問題,,（2.6）,線性規(guī)劃問題解的概念及性質(zhì),對(duì)于線性規(guī)劃問題（2.6）來說，可行解實(shí)際上是由約束條件構(gòu)成的線性方程組（常稱為約束方程組）,,的解，并且還滿足非負(fù)約束條件，即各個(gè)決策變量都取非負(fù)值： 。,,對(duì)于線性規(guī)劃問題（2.6），可以證明如下的結(jié)論： 定理2.1 線性規(guī)劃問題的可行域如果不是空集，就一定是凸集。 凸集:指一個(gè)非空集，并且以其中任意兩個(gè)點(diǎn)為端點(diǎn)的直線段上的所有點(diǎn)都屬于該集合。,頂點(diǎn)：在凸集中，如果一個(gè)點(diǎn)不位于其他兩點(diǎn)為端點(diǎn)的線段的內(nèi)部，則稱其為該凸集的頂點(diǎn)。例如上圖中第一個(gè)凸集的A點(diǎn)，或第二個(gè)凸集的B點(diǎn)，分別是相應(yīng)的凸集的頂點(diǎn)。,哪個(gè)是凸集呢？,今后我們將A的任一個(gè)具有這樣的特征的子矩陣B稱為線性規(guī)劃問題（2.6）的一個(gè)基。也就是說線性規(guī)劃問題的基就是矩陣A的一個(gè) 且行列式不為零的子矩陣。,我們將約束方程組的系數(shù)矩陣,稱為線性規(guī)劃問題的系數(shù)矩陣，并且總假定其秩等于其行數(shù)：,。這意味著系數(shù)矩陣,的各行是線性無關(guān)的，,這也表明約束方程中的各個(gè)方程是相互獨(dú)立的。,由于矩陣A的秩為m, 故至少存在一個(gè) 的子矩陣B，其行列式不為零。,例如，對(duì)于線性規(guī)劃問題,,其系數(shù)矩陣為,,則下面兩個(gè)矩陣都是該線性規(guī)劃問題的基。,,和,還能找出其它基嗎？,例如，對(duì)上面的線性規(guī)劃問題，若我們考慮基 則線性規(guī)劃問題的基變量就是x2和x4，而x1和x3就是非基變量。但如果我們考慮的基是 則基變量是x1和x2，非基變量是x3和x4。 可見在線性規(guī)劃問題中所謂基變量就是由m個(gè)變量構(gòu)成的一組變量，其系數(shù)構(gòu)成的行列式不等于零；反之滿足系數(shù)行列式不等于零的一組m個(gè)變量，就是基變量。,基解：在約束方程組中，令非基變量等于0的解。 基可行解：基解 + 可行解,例如，對(duì)于上面的線性規(guī)劃問題，如果取x1，x2為基變量，則令非基變量x3，x4為零，約束方程組為,,解之得 。故我們得到基解 注意到這個(gè)基解還是一個(gè)可行解。,,,是否所有的基解都是基可行解？（選x1,x3作為基變量）,定理2.2： 線性規(guī)劃問題的基可行解是其可行域的頂點(diǎn)。 定理2.3： 線性規(guī)劃問題的最優(yōu)解如果存在，則一定有一個(gè)基可行解是最優(yōu)解。,2.6 單純形法計(jì)算,基本思路： 首先將線性規(guī)劃問題化成標(biāo)準(zhǔn)形式 求出初始基本可行解 判斷其是否為最優(yōu)解 如果不是最優(yōu)，則迭代到其相鄰的基本可行解，并再次檢驗(yàn),旦茨基教授在一次演說中，形象而風(fēng)趣地說明了單純形解法的奇效：設(shè)給70個(gè)人分配70項(xiàng)任務(wù)，每人一項(xiàng)。如果每人完成各項(xiàng)任務(wù)所需要付出的代價(jià)（時(shí)間、工資）都知道，要尋求代價(jià)最小的方案。所有的可行方案共有70！種。70！比 還要大。 不僅如此，還能預(yù)測(cè)當(dāng)方案中某因素發(fā)生變化，對(duì)決策目標(biāo)的影響。,神奇的單純形法,線性規(guī)劃問題的可行解有無窮多個(gè)，與某一凸集上的無窮多個(gè)點(diǎn)一一對(duì)應(yīng)。要從無窮多個(gè)可行解中尋找最優(yōu)解，幾乎不可能。 可以證明，最優(yōu)解必定能取在凸集的頂點(diǎn)（極點(diǎn)、基本可行解）上，而極點(diǎn)的個(gè)數(shù)是有限的。當(dāng)然，這個(gè)“有限”，數(shù)字往往相當(dāng)可觀，如前面的70！，要逐個(gè)比較的話，也不現(xiàn)實(shí)。而單純形解法，用跨躍的方式，高速地優(yōu)化基本可行解，迅速達(dá)到最優(yōu)。,單純形法—跨躍式地尋求最優(yōu)解,,max S,S=o,,,A,B,C,D,E,,初始可行解,為了便于求解，并使得整個(gè)求解過程程序化，我們通常是從求一個(gè)特殊的基可行解出發(fā)進(jìn)行求解。這個(gè)特殊的基可行解稱為初始基可行解。 要求初始基可行解需先確定初始基變量。我們稱基矩陣為單位矩陣（或單位矩陣交換了列以后得到的矩陣）的基變量為初始基變量。 因此初始基變量具有特征：它們是一組變量，個(gè)數(shù)等于約束方程的個(gè)數(shù)，每個(gè)變量?jī)H出現(xiàn)在一個(gè)約束方程中且系數(shù)為1。 初始基變量對(duì)應(yīng)的基解一定是可行解稱為初始基可行解。,解：數(shù)學(xué)模型 max S = 6x1 + 4x2 s.t. 2x1+3x2 ? 100 4x1+2x2 ? 120 x1,x2 ? 0,引進(jìn)松弛變量x3,x4 ? 0 數(shù)學(xué)模型標(biāo)準(zhǔn)形式： max S = 6x1 + 4x2 s.t. 2x1+3x2 +x3 = 100 4x1+2x2 +x4 = 120 x1 , x2 , x3 , x4 ? 0,A=（P1，P2，P3，P4） = 2 3 1 0 4 2 0 1 X=（x1, x2, x3, x4) B=(P3，P4 ）= 1 0 0 1 P3，P4線性無關(guān)，x3, x4是基變量，x1, x2,是非基變量。,,,令A(yù)=（P1，P2，P3，P4） = 2 3 1 0 4 2 0 1 X=（x1, x2, x3, x4),,,,用非基變量表示的方程： x3 = 100 - 2x1 - 3x2 x4 = 120 - 4x1 - 2x2 (I) S = 6x1 +4x2,,令非基變量 （ x1 , x2）t=（0，0） t 得基礎(chǔ)可行解： x(1) = (0,0,100,120) t S1 = 0 經(jīng)濟(jì)含義：不生產(chǎn)產(chǎn)品甲乙，利潤(rùn)為零。 分析：S = 6x1 + 4x2 （分別增加單位產(chǎn)品甲、乙，目標(biāo)函數(shù)分別增加6、4，即利潤(rùn)分別增加6百元、 4百元。） 增加單位產(chǎn)品對(duì)目標(biāo)函數(shù)的貢獻(xiàn)，這就是檢驗(yàn)數(shù)的概念。,,,增加單位產(chǎn)品甲（x1）比乙對(duì)目標(biāo)函數(shù)的貢獻(xiàn)大（檢驗(yàn)數(shù)最大），把非基變量x1換成基變量，稱x1為進(jìn)基變量，而把基變量x4換成非基變量，稱x4為出基變量。,確定了進(jìn)基變量x1 ，出基變量x4 以后，得到新的系統(tǒng)： x3 = 40 - 2x2 + （1/2） x4 x1 = 30 -（1/2）x2 -（1/4）x4 (II) S = 180 + x2 -（3/2）x4 令新的非基變量（ x2，x4 ）=（0，0）t 得到新的基礎(chǔ)可行解： x(2)=(30,0,40, 0) t S2=180 經(jīng)濟(jì)含義：生產(chǎn)甲產(chǎn)品30個(gè)，獲得利潤(rùn)18000元。,,,,這個(gè)方案比前方案，但是否是最優(yōu)？ 分析：S=180+x2-（3/2）x4 非基變量x2系數(shù)仍為正數(shù)，確定x2為進(jìn)基變量。在保證常數(shù)項(xiàng)非負(fù)的情況下，確定x3為出基變量。得到新的系統(tǒng)： x1 = 20 +（1/4）x3- （3/8） x4 x2 = 20 -（1/2）x3 +（1/4）x4 (III) S = 200 -（1/2）x3 -（5/4）x4,,,,令新的非基變量（x3 , x4 ）t=（0 , 0） t 得到新的基礎(chǔ)可行解： x(3)= (20,20, 0, 0) t S3= 200 經(jīng)濟(jì)含義：分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得利潤(rùn)20000元。 分析：S = 200 -（1/2）x3 -（5/4）x4 目標(biāo)函數(shù)中的非基變量的系數(shù)無正數(shù)， S3 = 200 是最優(yōu)值， x(3)=(20,20, 0, 0) t 是最優(yōu)解。 該企業(yè)分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得最大利潤(rùn)20000元。,利用單純形表進(jìn)行計(jì)算,從前面的單純形法的計(jì)算過程可見，所有計(jì)算其實(shí)都?xì)w結(jié)為對(duì)標(biāo)準(zhǔn)形式的模型的系數(shù)的計(jì)算。因此可以通過將線性規(guī)劃的系數(shù)矩陣及目標(biāo)函數(shù)系數(shù)列成表格的方式進(jìn)行計(jì)算。,max z = 3x1 + 2x2,x1 + 2x2 + x3 = 5,2x1 + x2 + x4 = 4,4x1 + 3x2 + x5 = 9,x1, x2 ,…, x5 ? 0,,,3 2,,,1 2 1 0 0 5,,2 1 0 1 0 4,,4 3 0 0 1 9,3 2 0 0 0,單純形表,檢驗(yàn)數(shù),以x3,x4,x5作為初始基變量得到初始單純形表如下所示：,該初始單純形表對(duì)應(yīng)的初始解為X = (0，0，5，4，9)T。對(duì)應(yīng)目標(biāo)函數(shù)值為0. 因?yàn)閤1的檢驗(yàn)數(shù),,我們選擇x1作為換入變量。這樣可以使目標(biāo)函數(shù)增加得更快。 然后用b列的數(shù)除以換入變量列的正的系數(shù)，所得最小商對(duì)應(yīng)的變量x4為換出變量。,以x3,x1,x5作為基變量得到第二張單純形表按如下方式計(jì)算：,,,該元素稱為主元。下面開始迭代，迭代的目標(biāo)就是把主元化為1，然后把主元所在列其他系數(shù)化為0。,x1,3,3,2,1/2,0,1/2,1,0,0,0,3/2,1,-1/2,0,0,0,1,0,-2,1,1,0,1/2,0,-3/2,6,0,該單純形表對(duì)應(yīng)的基可行解為X=（2，0，3，0，1）T，對(duì)應(yīng)目標(biāo)函數(shù)值為6。 現(xiàn)在x2的檢驗(yàn)數(shù)為1/20，且最大，所以我們選擇x2為換入變量。 因?yàn)閙in{3/(3/2), 2/(1/2), 1/1}=1,所以選擇x5作為換出變量。,以x3,x1,x2作為基變量得到第三張單純形表如下所示：,,2,x2,0,1,0,-2,1,1,0,0,0,1,5/2,-3/2,3/2,3,1,0,0,3/2,-1/2,3/2,0,0,0,-1/2,-1/2,13/2,現(xiàn)在所有的檢驗(yàn)數(shù)都小于或者等于0，所以得到最優(yōu)解為：,最優(yōu)目標(biāo)函數(shù)值為13/2。,該表稱為最終單純形表，其具有什么特征？,合并的單純形表,單純形法計(jì)算過程,構(gòu)造初始單純形表 對(duì)標(biāo)準(zhǔn)化后的線性規(guī)劃問題，首先找出初始基變量，構(gòu)造初始單純形表。相應(yīng)地可以得到初始基可行解，基可行解的目標(biāo)函數(shù)值。 最優(yōu)性檢驗(yàn) 若得到單純形表中所有的檢驗(yàn)數(shù)都小于或等于零，則該單純形表給出的基可行解就是最優(yōu)解，終止計(jì)算。否則進(jìn)行下一步。 確定換入變量 選擇最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量。 確定換出變量 若換入變量（更一般地，若某個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的變量）所作列的系數(shù)均小于或等于零，則線性規(guī)劃問題為無界解，終止計(jì)算。否則用換入變量所作列的系數(shù)去除b列的對(duì)應(yīng)數(shù)，在除得的商中選擇最小者對(duì)應(yīng)的基變量為換出變量。 旋轉(zhuǎn)運(yùn)算 確定換入和換出變量后得到新的基變量，然后以換入變量所在列、換出變量所在行交叉處的元素為主元，通過矩陣的初等行變換（一般不使用交換兩行的運(yùn)算）將約束方程組增廣矩陣中主元變換為1，主元列的其它元素變換為零。從而得到一個(gè)新的單純形表。然后回到第2步。,唯一最優(yōu)解與無窮多個(gè)最優(yōu)解,若最終單純形表的非基變量的檢驗(yàn)數(shù)都小于零,則線性規(guī)劃問題有唯一的最優(yōu)解 若最終單純形表中存在某個(gè)非基變量, 其檢驗(yàn)數(shù)等于零, 則該線性規(guī)劃問題有無窮多個(gè)最優(yōu)解.,例2.4 利用單純形法求解下列線性規(guī)劃問題,,,首先將線性規(guī)劃標(biāo)準(zhǔn)化,,很明顯可以以x4、x5作為初始基變量，得到初始單純形如下：,此時(shí)，x2的檢驗(yàn)數(shù)大于0，還沒有得到最優(yōu)解。但是我們以x2作為換入變量，但是x2所在列所有系數(shù)都小于0 ，此時(shí)該線性規(guī)劃存在無界解。,課堂作業(yè): 用單純形法求解,解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：,不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。,單純形法的計(jì)算步驟,,20,－,,x2,2,,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,－9,0,－2,,25,60,,,x1,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,,單純形法小結(jié),2、某求極大值LP問題的初始及經(jīng)過一次迭代后的單純形表，表如下，x4、x5為松馳變量，試求表中a-l及m-t的值。,［解］（1）因?yàn)槌跏急碇衳4、x5為基變量，所以， m＝4；n＝5；,（2）迭代后的表中，基變量為： x1、x5，因此： g＝1 ； h＝0； s＝1；t＝5；,（3） x5為基變量， l＝0； （4）p4由第一個(gè)表的［1,0］T變?yōu)榈诙€(gè)表中的［1/2,1/2］T， 即① /2＝ ④ ，因此， f＝3； b＝2； c＝4； d＝－2；,（5）同理，行②＋行 ④ ＝行⑤ i＝5； e＝2； （6） σ2 ＝1－2a＝-7，所以，a＝4； （7）j＝2；k＝-2；,