運(yùn)籌學(xué)ppt課件Ch1線性規(guī)劃

運(yùn)籌學(xué)OperationsResearchChapter1線性規(guī)劃LinearProgramming1.1LP的數(shù)學(xué)模型MathematicalModelofLP1.2圖解法

GraphicalMethod1.3標(biāo)準(zhǔn)型

StandardformofLP1.4基本概念

BasicConcepts1.5單純形法

SimplexMethod1/18/20231.1數(shù)學(xué)模型

MathematicalModel1/18/20231.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP線性規(guī)劃（LinearProgramming,縮寫為L(zhǎng)P）通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大）。1/18/2023【例1-1】生產(chǎn)計(jì)劃問題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。按工藝資料規(guī)定，每件產(chǎn)品甲需要消耗材料A2公斤，消耗材料B1公斤，每件產(chǎn)品乙需要消耗材料A1公斤，消耗材料B1.5公斤。已知在計(jì)劃期內(nèi)可供材料分別為40、30公斤；每生產(chǎn)一件甲、乙兩產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為300、400元，如表1－1所示。假定市場(chǎng)需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1.1.1應(yīng)用模型舉例1/18/2023【解】設(shè)x1、x2分別為甲、乙產(chǎn)品的產(chǎn)量，數(shù)學(xué)模型為：1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP產(chǎn)品

資源

甲

乙現(xiàn)有資源材料A2140材料B11.530利潤(rùn)（元/件）300400表1-11/18/2023線性規(guī)劃的數(shù)學(xué)模型由決策變量

Decisionvariables

目標(biāo)函數(shù)Objectivefunction及約束條件Constraints構(gòu)成。稱為三個(gè)要素。其特征是：1．解決問題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問題的約束條件是一組多個(gè)決策變量的線性不等式或等式。怎樣辨別一個(gè)模型是線性規(guī)劃模型？1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1/18/2023【例1-2】某商場(chǎng)決定：營(yíng)業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計(jì)，商場(chǎng)每天需要的營(yíng)業(yè)員如表1-2所示。表1-2營(yíng)業(yè)員需要量統(tǒng)計(jì)表商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營(yíng)業(yè)員最少。星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1/18/2023【解】設(shè)xj(j=1，2，…，7)為休息2天后星期一到星期日開始上班的營(yíng)業(yè)員，則這個(gè)問題的線性規(guī)劃模型為1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001/18/2023【例1-3】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長(zhǎng)度為4m?，F(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？【解】這是一個(gè)條材下料問題，設(shè)切口寬度為零。設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有10組，也就是有10種下料方式，如表1-3所示。表1-3下料方案方案規(guī)格12345678910需求量y1(根)

22111000001000y210210432101000y3

01023012451000余料（m）00.30.50.1o.400.30.60.20.51.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1/18/2023設(shè)xj(j=1,2…,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型為:求下料方案時(shí)應(yīng)注意，余料不能超過最短毛坯的長(zhǎng)度；最好將毛坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能遺漏了方案。如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP方案規(guī)格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料（m）00.30.50.1o.400.30.60.20.51/18/20231.1.2線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個(gè)約束，有n個(gè)決策變量xj,j=1,2…,n，目標(biāo)函數(shù)的變量系數(shù)用cj表示,cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成為了書寫方便，上式也可寫成：1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1/18/2023在實(shí)際中一般xj≥0,但有時(shí)xj≤0或xj無符號(hào)限制。1.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP1/18/20231.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個(gè)應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征3.線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。作業(yè)：教材習(xí)題1.1~1.61.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP下一節(jié)：圖解法1/18/20231.2圖解法

GraphicalMethod1/18/2023x1x2O1020304010203040(300,400)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=8500例1-71.2圖解法TheGraphicalMethod1/18/2023246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2例1-8(1,2)1.2圖解法TheGraphicalMethod1/18/2023246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例1-9有無窮多個(gè)最優(yōu)解即具有多重解,通解為0≤α≤1

當(dāng)α=0.5時(shí)Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)1.2圖解法TheGraphicalMethod1/18/2023246x1x2246(1,2)無界解(無最優(yōu)解)max

Z=x1+2x2例1-101.2圖解法TheGraphicalMethod1/18/2023x1x2O10203040102030405050無可行解即無最優(yōu)解maxZ=10x1+4x2例1-111.2圖解法TheGraphicalMethod1/18/2023由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例1-7例1-8)2.有多重解(例1-9)3.有無界解(例1-10)4.無可行解(例1-11)1、2情形為有最優(yōu)解3、4情形為無最優(yōu)解1.2圖解法TheGraphicalMethod1/18/2023圖解法的步驟：1.求可行解集合。分別求出滿足每個(gè)約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標(biāo)函數(shù)圖形。先過原點(diǎn)作一條矢量指向點(diǎn)（c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。一般地，將目標(biāo)函數(shù)直線放在可行域中求最大值時(shí)直線沿著矢量方向移動(dòng)求最小值時(shí)沿著矢量的反方向移動(dòng)1.2圖解法TheGraphicalMethod1/18/20231.通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點(diǎn)(1)可行解區(qū)域要畫正確(2)目標(biāo)函數(shù)增加的方向不能畫錯(cuò)(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)作業(yè)：教材習(xí)題1.71.2圖解法TheGraphicalMethod下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型1/18/20231.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023在用單純法求解線性規(guī)劃問題時(shí)，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP線性規(guī)劃問題的標(biāo)準(zhǔn)型為:1．目標(biāo)函數(shù)求最大值（或求最小值）2．約束條件都為等式方程3．變量xj非負(fù)4．常數(shù)bi非負(fù)1/18/2023max(或min)Z=c1x1+c2x2+…+cnxn1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP注：本教材默認(rèn)目標(biāo)函數(shù)是max1/18/2023或?qū)懗上铝行问剑?/p>

或用矩陣形式1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023通常X記為：

稱Ａ為約束方程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，一般情況m≤n，且r(Ａ)＝m。其中:1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023【例1-12】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型【解】（１）因?yàn)閤3無符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023(3)第二個(gè)約束條件是≥號(hào)，在≥號(hào)左端減去剩余變量(Surplusvariable)x5，x5≥0。也稱松馳變量1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP(2)第一個(gè)約束條件是≤號(hào)，在≤左端加入松馳變量(slackvariable)x4，x4≥0,化為等式；(4)第三個(gè)約束條件是≤號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在≤左邊加入松馳變量x6，x6≥0，同時(shí)兩邊乘以－1。（5）目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時(shí)Z′達(dá)到最大值，反之亦然。1/18/2023綜合起來得到下列標(biāo)準(zhǔn)型1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023當(dāng)某個(gè)變量xj≤0時(shí),令x/j=－xj

。當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束將其化為兩個(gè)不等式再加入松馳變量化為等式。1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023【例1-13】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型【解】此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。令則有1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1/18/2023得到線性規(guī)劃的標(biāo)準(zhǔn)形式

1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP對(duì)于a≤x≤b(a、b均大于零)的有界變量化為標(biāo)準(zhǔn)形式有兩種方法。一種方法是增加兩個(gè)約束x≥a及x≤b另一種方法是令x'=x－a，則a≤x≤b等價(jià)于0≤x'≤b－a，增加一個(gè)約束x'≤b－a并且將原問題所有x用x=x'+a替換。1/18/20231.如何化標(biāo)準(zhǔn)形式？可以對(duì)照四條標(biāo)準(zhǔn)逐一判斷！標(biāo)準(zhǔn)形式是人為定義的，目標(biāo)函數(shù)可以是求最小值。2.用WinQSB軟件求解時(shí)，不必化成標(biāo)準(zhǔn)型。圖解法時(shí)不必化為標(biāo)準(zhǔn)型。3.單純形法求解時(shí)一定要化為標(biāo)準(zhǔn)型。作業(yè)：教材習(xí)題1.81.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP下一節(jié)：基本概念1/18/20231.4線性規(guī)劃的有關(guān)概念BasicConceptsofLP1/18/2023

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型maxZ=CX（1.1）AX=b（1.2）X≥0（1.3）式中A是m×n矩陣，m≤n并且r（A）=m，顯然A中至少有一個(gè)m×m子矩陣B，使得r（B）=m。1.4基本概念BasicConcepts

基(basis)A中m×m子矩陣B并且有r（B）=m，則稱B是線性規(guī)劃的一個(gè)基（或基矩陣basismatrix）。當(dāng)m=n時(shí)，基矩陣唯一，當(dāng)m<n時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過1/18/2023【例1-14】線性規(guī)劃求所有基矩陣。【解】約束方程的系數(shù)矩陣為2×5矩陣容易看出r(A)=2，2階子矩陣有C52=10個(gè)，其中第1列與第3列構(gòu)成的2階矩陣不是一個(gè)基，基矩陣只有9個(gè)，即1.4基本概念BasicConcepts

1/18/2023由線性代數(shù)知，基矩陣B必為非奇異矩陣并且|B|≠0。當(dāng)矩陣B的行列式等式零即|B|=0時(shí)就不是基當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為基向量(basisvector)，其余列向量稱為非基向量

基向量對(duì)應(yīng)的變量稱為基變量(basisvariable)，非基向量對(duì)應(yīng)的變量稱為非基變量

在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量。基變量、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。1.4基本概念BasicConcepts

1/18/2023可行解(feasiblesolution)滿足式（1.2）及（1.3）的解X=（x1,x2…，xn)T稱為可行解?；究尚薪?basis

feasiblesolution)

若基本解是可行解則稱為是基本可行解（也稱基可行解）。例如，與X=（0，0，0，3，2，）都是例1的可行解?；窘?basissolution)對(duì)某一確定的基B，令非基變量等于零，利用式（1.２）解出基變量，則這組解稱為基Ｂ的基本解。最優(yōu)解(optimalsolution)滿足式（1.1）的可行解稱為最優(yōu)解，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例如可行解是例2的最優(yōu)解。非可行解(Infeasiblesolution)

無界解

(unboundsolution)1.4基本概念BasicConcepts

1/18/2023顯然，只要基本解中的基變量的解滿足式（1.３）的非負(fù)要求，那么這個(gè)基本解就是基本可行解。在例1-13中，對(duì)Ｂ１來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.２）為對(duì)B2來說，x1,x4,為基變量，令非基變量x2,x3,x5為零，由式（1.2）得到

，x4=4，因|B1|≠０，由克萊姆法則知，x1、x2有唯一解x1＝2/5,x2=1則基本解為1.4基本概念BasicConcepts

1/18/2023由于是基本解，從而它是基本可行解，在中x1<0,因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如滿足式（1.2）～（1.3），但不是任何基矩陣的基本解?；窘鉃?.4基本概念BasicConcepts

1/18/2023可行基基可行解對(duì)應(yīng)的基稱為可行基；最優(yōu)基基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基；如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當(dāng)最優(yōu)解唯一時(shí)，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不唯一時(shí)，則最優(yōu)解不一定是基本最優(yōu)解。例如右圖中線段的點(diǎn)為最優(yōu)解時(shí)，Q1點(diǎn)及Q2點(diǎn)是基本最優(yōu)解,線段的內(nèi)點(diǎn)是最優(yōu)解而不是基本最優(yōu)解。基本最優(yōu)解

最優(yōu)解是基本解稱為基本最優(yōu)解。例如，滿足式（1.1）~(1.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解。1.4基本概念BasicConcepts

1/18/2023基本最優(yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關(guān)系如下所示：基本最優(yōu)解基本可行解可行解最優(yōu)解基本解例如,B點(diǎn)和D點(diǎn)是可行解,不是基本解;C點(diǎn)是基本可行解;A點(diǎn)是基本最優(yōu)解,同時(shí)也是最優(yōu)解、基本可行解、基本解和可行解。1.4基本概念BasicConcepts

1/18/2023凸集(Convexset)設(shè)K是n維空間的一個(gè)點(diǎn)集，對(duì)任意兩點(diǎn)

時(shí)，則稱K為凸集。就是以X（1）、X（2）為端點(diǎn)的線段方程，點(diǎn)X的位置由α的值確定，當(dāng)α=0時(shí)，X=X（2），當(dāng)α=1時(shí)X=X（1）凸組合(Convexcombination)

設(shè)是Rn中的點(diǎn)若存在

使得成立，則稱X為的凸組合。1.4基本概念BasicConcepts

1/18/2023極點(diǎn)(Extremepoint)

設(shè)K是凸集，，若X不能用K中兩個(gè)不同的點(diǎn)的凸組合表示為<)10()1()2()1(<-+=aaaXXX則稱X是K的一個(gè)極點(diǎn)或頂點(diǎn)。X是凸集K的極點(diǎn)即X不可能是K中某一線段的內(nèi)點(diǎn)，只能是K中某一線段的端點(diǎn)。O1.4基本概念BasicConcepts

1/18/2023【定理1.1】若線性規(guī)劃可行解K非空,則K是凸集?！径ɡ?.2】線性規(guī)劃的可行解集合K的點(diǎn)X是極點(diǎn)的充要條件為X是基本可行解?！径ɡ?.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個(gè)極點(diǎn)上到達(dá),最優(yōu)解就是極點(diǎn)的坐標(biāo)向量。定理1.2刻劃了可行解集的極點(diǎn)與基本可行解的對(duì)應(yīng)關(guān)系，極點(diǎn)是基本可行解，反之，基本可行解一定是極點(diǎn)，但它們并非一一對(duì)應(yīng)，有可能兩個(gè)或幾個(gè)基本可行解對(duì)應(yīng)于同一極點(diǎn)（退化基本可行解時(shí)）。線性規(guī)劃的基本定理1.4基本概念BasicConcepts

1/18/2023

定理1.3描述了最優(yōu)解在可行解集中的位置，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點(diǎn)上達(dá)到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點(diǎn)的凸組合，從而最優(yōu)解是可行解集的極點(diǎn)或界點(diǎn)，不可能是可行解集的內(nèi)點(diǎn)。若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解；若可行解集無界，則線性規(guī)劃可能有最優(yōu)解，也可能沒有最優(yōu)解。定理1.2及1.3還給了我們一個(gè)啟示，尋求最優(yōu)解不是在無限個(gè)可行解中去找，而是在有限個(gè)基本可行解中去尋求。下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法。1.4基本概念BasicConcepts

1/18/20231.線性規(guī)劃常用的概念：可行解、基本解、基本可行解、最優(yōu)解、基本最優(yōu)解、基、可行基、最優(yōu)基、凸集、極點(diǎn)（凸點(diǎn)）、凸組合2.線性規(guī)劃的三個(gè)基本定理。作業(yè)：教材習(xí)題1.91.4基本概念BasicConcepts

下一節(jié)：?jiǎn)渭冃畏?/18/20231.5單純形法SimplexMethod1/18/2023

單純形計(jì)算方法(SimplexMethod)是先求出一個(gè)初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個(gè)基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。

當(dāng)系數(shù)矩陣A中可以觀察得到一個(gè)可行基時(shí)（通常是一個(gè)單位矩陣或m個(gè)線性無關(guān)的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解?！纠?-15】用單純形法求例1－1線性規(guī)劃的最優(yōu)解1.5單純形法SimplexMethod1.5.1普通單純形法1/18/2023【解】化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為系數(shù)矩陣A及可行基B1r(B1)=2，B1是一個(gè)初始基,x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0由約束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

1.5單純形法

SimplexMethod1/18/2023以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù)Z=300x1+400x2中x1的系數(shù)大于零，如果x1為一正數(shù)，則Z的值就會(huì)增大，同樣若x2不為零為一正數(shù)，也能使Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作λj,j=1,2,…,n

本例中λ1=300,λ2=400,λ3=0,λ4=0。參看表1-6（a）

最優(yōu)解判斷標(biāo)準(zhǔn)

當(dāng)所有檢驗(yàn)數(shù)λj≤0（j=1，…，n）時(shí)，基本可行解為最優(yōu)解。

當(dāng)目標(biāo)函數(shù)中有基變量xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗(yàn)數(shù)。

1.5單純形法

SimplexMethod檢驗(yàn)數(shù)目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù)1/18/2023進(jìn)基列出基行bi/ai2，ai2>0θi表1-6(a)XBx1x2x3x4bx3211040x413/20130λj30040000

(b)x3x2λj

(c)x1

x210

λj

基變量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/211000-25-250將3/2化為11.5單純形法SimplexMethod20151/18/2023最優(yōu)解X=(15，10，0，0)T，最優(yōu)值Z=8500X(1)=(0,0)x11.5單純形法

SimplexMethodx1x2O1020304010203040X(2)=(0,20)X(3)=(15,10)1/18/2023單純形法全過程的計(jì)算，可以用列表的方法計(jì)算更為簡(jiǎn)潔，這種表格稱為單純形表（表1-6）。計(jì)算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零；2.判斷：（a）若λj≤０（j＝１，２，…，n）得到最優(yōu)解；（b）某個(gè)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解(見例1-18)。（c）若存在λk>0且aik(i=1,…,m)不全非正，則進(jìn)行換基；1.5單純形法

SimplexMethod1/18/2023第Ｌ個(gè)比值最小，選最小比值對(duì)應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個(gè)。aLk為主元素；

(c）求新的基可行解：用初等行變換方法將aLk化為１,k列其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。（b）選出基變量，求最小比值：1.5單純形法SimplexMethod3.換基：（a）選進(jìn)基變量設(shè)λk=max｛λj|λj>0｝,xk為進(jìn)基變量1/18/2023【例1-16】用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計(jì)算結(jié)果如表1-7所示。1.5單純形法

SimplexMethod1/18/2023Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表1－71/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/31.5單純形法

SimplexMethod1/18/2023【例1-17】用單純形法求解

【解】這是一個(gè)極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時(shí)判斷標(biāo)準(zhǔn)是：λj≥0(j=1，…，n)時(shí)得到最優(yōu)解。容易觀察到,系數(shù)矩陣中有一個(gè)3階單位矩陣,x3、x4、x5為基變量。目標(biāo)函數(shù)中含有基變量x4,由第二個(gè)約束得到x4=6+x1－x2，并代入目標(biāo)函數(shù)消去x4得1.5單純形法

SimplexMethod1/18/2023XBx1x2x3x4x5bθx3x4x51-16[1]121000100015→6215621/2λj1-1↑000

x2x4x51-241001-1-20100015111

λj20100

表中λj≥0,j=1,2,…,5所以最優(yōu)解為X=(0,5,0,1,11,)最優(yōu)值Z=2x1－2x2－x4=－2×5－1=－11極小值問題,注意判斷標(biāo)準(zhǔn),選進(jìn)基變量時(shí),應(yīng)選λj<0的變量xj進(jìn)基。1.5單純形法Simplex

Method表1-81/18/2023【例1-18】求解線性規(guī)劃【解】化為標(biāo)準(zhǔn)型1.5單純形法

SimplexMethod1/18/2023初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2進(jìn)基，而a12<0，a22<0，沒有比值，從而線性規(guī)劃的最優(yōu)解無界。由模型可以看出，當(dāng)固定x1使x2→+∞且滿足約束條件，還可以用圖解法看出具有無界解。1.5單純形法

SimplexMethod1/18/2023【例1-19】求解線性規(guī)劃【解】:化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如下表所示1.5單純形法

SimplexMethod1/18/2023XBx1x2x3x4x5bθ(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－201/18/2023表(3)中λj全部非正,則最優(yōu)解為:表(3)表明,非基變量x3的檢驗(yàn)數(shù)λ3=0,x3若增加,目標(biāo)函數(shù)值不變,即當(dāng)x3進(jìn)基時(shí)Z仍等于20。使x3進(jìn)基x5出基繼續(xù)迭代,得到表(4)的另一基本最優(yōu)解X(1),X(2)是線性規(guī)劃的兩個(gè)最優(yōu)解，它的凸組合仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。1.5單純形法

SimplexMethod1/18/2023唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解

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

某個(gè)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個(gè)基變量為零的基本可行解。1.5單純形法SimplexMethod1/18/2023在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法?！纠?-20】用大M法解下列線性規(guī)劃1.大M單純形法1.5.2大M和兩階段單純形法1.5單純形法

SimplexMethod1/18/2023【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式式中x4，x5為松弛變量，x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x7，目標(biāo)函數(shù)中加入―Mx6―Mx7一項(xiàng)，得到人工變量單純形法數(shù)學(xué)模型用前面介紹的單純形法求解，見下表。1.5單純形法

SimplexMethod1/18/2023Cj32－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/31/18/2023（2）初始表中的檢驗(yàn)數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達(dá)式代入目標(biāo)涵數(shù)消去x6和x7，得到用非基變量表達(dá)的目標(biāo)函數(shù)，其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公式計(jì)算，如最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3注意：1.5單純形法

SimplexMethod(1)M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值1/18/2023【例1-21】求解線性規(guī)劃【解】加入松馳變量x3、x4化為標(biāo)準(zhǔn)型在第二個(gè)方程中加入人工變量x5，目標(biāo)函數(shù)中加上Mx5一項(xiàng)，得到1.5單純形法

SimplexMethod1/18/2023用單純形法計(jì)算如下表所示。

Cj5－800MbCBXBx1x2x3x4x50Mx3x5[3]11－2100－1016→4λj5－M↑－8+2M0M0

5Mx1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0

1.5單純形法

SimplexMethod1/18/2023表中λj≥0，j=1，2，…，5，從而得到最優(yōu)解X=（2，0，0，0，2），Z=10+2M。但最優(yōu)解中含有人工變量x5≠0說明這個(gè)解是偽最優(yōu)解，是不可行的，因此原問題無可行解。

兩階段單純形法與大M單純形法的目的類似，將人工變量從基變量中換出，以求出原問題的初始基本可行解。將問題分成兩個(gè)階段求解，第一階段的目標(biāo)函數(shù)是約束條件是加入人工變量后的約束方程，當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時(shí)，得到原線性規(guī)劃的一個(gè)基本可行解，第二階段就以此為基礎(chǔ)對(duì)原目標(biāo)函數(shù)求最優(yōu)解。當(dāng)?shù)谝浑A段的最優(yōu)解w≠0時(shí)，說明還有不為零的人工變量是基變量，則原問題無可行解。1.5單純形法

SimplexMethod2.兩階段單純形法1/18/2023【例1-22】用兩階段單純形法求解例19的線性規(guī)劃。【解】標(biāo)準(zhǔn)型為在第一、三約束方程中加入人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計(jì)算表如下：1.5單純形法

SimplexMethod1/18/2023Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7－4123－1－212[1]－1000101000014101→λj2－1－2↑1000

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

3→81λj6－5↑0100

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

3/531/511/5λj00000

1.5單純形法

SimplexMethod1/18/2023最優(yōu)解為最優(yōu)值w=0。第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為1.5單純形法

SimplexMethod1/18/2023Cj32-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/31.5單純形法

SimplexMethod1/18/2023【例1-23】用兩階段法求解例1-21的線性規(guī)劃。【解】例1-21的第一階段問題為用單純形法計(jì)算如下表：1.5單純形法

SimplexMethod1/18/2023Cj00001bCBXBx1x2x3x4x501x3x5[3]11－2100－1016→4λj

－1↑2010

01x1x5101/3－7/31/3－1/30－10122λj

07/31/310

λj≥0,得到第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標(biāo)值w=2≠0,x5仍在基變量中,從而原問題無可行解。1.5單純形法

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

某個(gè)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個(gè)基變量為零的基本可行解。無可行解的判斷：(1)當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí)，則表明原線性規(guī)劃無可行解。(2)當(dāng)?shù)谝浑A段的最優(yōu)值w≠0時(shí)，則原問題無可行解。1.5單純形法

SimplexMethod1/18/2023設(shè)有線性規(guī)劃其中Am×n且r(A)=m,X≥0應(yīng)理解為X大于等于零向量，即xj≥0,j=1,2…,n。1.5.3計(jì)算公式1.5單純形法

SimplexMethod1/18/2023不妨假設(shè)A＝（P1，P2，…，Pn）中前m個(gè)列向量構(gòu)成一個(gè)可行基，記為B=(P1，P2，…，Pm)。矩陣A中后n－m列構(gòu)成的矩陣記為N＝（Pm+1,…Pn）,則A可以寫成分塊矩陣A=（B，N）。對(duì)于基B，基變量為XB=（x1,x2，…，xm

）T,非基變量為XN=(xm+1,xm+2,…xn)T。則X可表示成同理將C寫成分塊矩陣C=（CB，CN），CB=(C1,C2,…,Cm),

CN=(Cm+1Cm+2，…，cn)則AX=b可寫成1.5單純形法

SimplexMethod1/18/2023因?yàn)閞（B）=m（或|B|≠0）所以B—1存在，因此可有令非基變量XN=0，XB=B—1b，由B是可行基的假設(shè)，則得到基本可行解X=(B－1b，0)T將目標(biāo)函數(shù)寫成1.5單純形法

SimplexMethod1/18/2023得到下列五個(gè)計(jì)算公式：(令XN=0)

1.5單純形法

SimplexMethod1/18/2023上述公式可用下面較簡(jiǎn)單的矩陣表格運(yùn)算得到，設(shè)初始矩陣單純形表1-16

將B化為I（I為m階單位矩陣）,CB化為零,即求基本可行解和檢驗(yàn)數(shù)。用B－1左乘表中第二行,得到表1-17XBXNbXBIB-1NB-1bCj-ZjCBCN0XBXNbXBBNbCj-ZjCBCN0表1－16表1－171.5單純形法

SimplexMethod1/18/2023再將第二行左乘－CB后加到第三行,得到λΝXB－Z0XBXNbXBIB-1NB-1bλ＝Cj-Zj0CN-CBB－1N－CBB－1b表1－181.5單純形法

SimplexMethod1/18/2023五個(gè)公式的應(yīng)用【例1-24