運籌學ppt課件Ch1線性規(guī)劃

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

GraphicalMethod1.3標準型

StandardformofLP1.4基本概念

BasicConcepts1.5單純形法

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

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

資源

甲

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

Decisionvariables

目標函數(shù)Objectivefunction及約束條件Constraints構成。稱為三個要素。其特征是：1．解決問題的目標函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問題的約束條件是一組多個決策變量的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？1.1線性規(guī)劃的數(shù)學模型MathematicalModelofLP1/18/2023【例1-2】某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如表1-2所示。表1-2營業(yè)員需要量統(tǒng)計表商場人力資源部應如何安排每天的上班人數(shù)，使商場總的營業(yè)員最少。星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1線性規(guī)劃的數(shù)學模型MathematicalModelofLP1/18/2023【解】設xj(j=1，2，…，7)為休息2天后星期一到星期日開始上班的營業(yè)員，則這個問題的線性規(guī)劃模型為1.1線性規(guī)劃的數(shù)學模型MathematicalModelofLP星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001/18/2023【例1-3】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長度為4m?，F(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產這些軸？【解】這是一個條材下料問題，設切口寬度為零。設一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求這個不等式關于y1，y2，y3的非負整數(shù)解。象這樣的非負整數(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ù)學模型MathematicalModelofLP1/18/2023設xj(j=1,2…,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學模型為:求下料方案時應注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案。如果方案較多，用計算機編程排方案，去掉余料較長的方案，進行初選。1.1線性規(guī)劃的數(shù)學模型MathematicalModelofLP方案規(guī)格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料（m）00.30.50.1o.400.30.60.20.51/18/20231.1.2線性規(guī)劃的一般模型一般地，假設線性規(guī)劃數(shù)學模型中，有m個約束，有n個決策變量xj,j=1,2…,n，目標函數(shù)的變量系數(shù)用cj表示,cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學模型的一般表達式可寫成為了書寫方便，上式也可寫成：1.1線性規(guī)劃的數(shù)學模型MathematicalModelofLP1/18/2023在實際中一般xj≥0,但有時xj≤0或xj無符號限制。1.1線性規(guī)劃的數(shù)學模型MathematicalModelofLP1/18/20231.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個應用例子2.線性規(guī)劃數(shù)學模型的組成及其特征3.線性規(guī)劃數(shù)學模型的一般表達式。作業(yè)：教材習題1.1~1.61.1線性規(guī)劃的數(shù)學模型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有無窮多個最優(yōu)解即具有多重解,通解為0≤α≤1

當α=0.5時Ｘ=(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.求可行解集合。分別求出滿足每個約束包括變量非負要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標函數(shù)圖形。先過原點作一條矢量指向點（c1,c2)，矢量的方向就是目標函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應的坐標就是最優(yōu)解。一般地，將目標函數(shù)直線放在可行域中求最大值時直線沿著矢量方向移動求最小值時沿著矢量的反方向移動1.2圖解法TheGraphicalMethod1/18/20231.通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關鍵有三點(1)可行解區(qū)域要畫正確(2)目標函數(shù)增加的方向不能畫錯(3)目標函數(shù)的直線怎樣平行移動作業(yè)：教材習題1.71.2圖解法TheGraphicalMethod下一節(jié)：線性規(guī)劃的標準型1/18/20231.3線性規(guī)劃的標準型StandardformofLP1/18/2023在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。1.3線性規(guī)劃的標準型StandardformofLP線性規(guī)劃問題的標準型為:1．目標函數(shù)求最大值（或求最小值）2．約束條件都為等式方程3．變量xj非負4．常數(shù)bi非負1/18/2023max(或min)Z=c1x1+c2x2+…+cnxn1.3線性規(guī)劃的標準型StandardformofLP注：本教材默認目標函數(shù)是max1/18/2023或寫成下列形式：

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

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

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

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

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

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

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

基向量對應的變量稱為基變量(basisvariable)，非基向量對應的變量稱為非基變量

在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞俊⒎腔兞渴轻槍δ骋淮_定基而言的，不同的基對應的基變量和非基變量也不同。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)對某一確定的基B，令非基變量等于零，利用式（1.２）解出基變量，則這組解稱為基Ｂ的基本解。最優(yōu)解(optimalsolution)滿足式（1.1）的可行解稱為最優(yōu)解，即是使得目標函數(shù)達到最大值的可行解就是最優(yōu)解，例如可行解是例2的最優(yōu)解。非可行解(Infeasiblesolution)

無界解

(unboundsolution)1.4基本概念BasicConcepts

1/18/2023顯然，只要基本解中的基變量的解滿足式（1.３）的非負要求，那么這個基本解就是基本可行解。在例1-13中，對Ｂ１來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.２）為對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可行基基可行解對應的基稱為可行基；最優(yōu)基基本最優(yōu)解對應的基稱為最優(yōu)基；如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解，當最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。例如右圖中線段的點為最優(yōu)解時，Q1點及Q2點是基本最優(yōu)解,線段的內點是最優(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)解、基本可行解、基本解、可行解的關系如下所示：基本最優(yōu)解基本可行解可行解最優(yōu)解基本解例如,B點和D點是可行解,不是基本解;C點是基本可行解;A點是基本最優(yōu)解,同時也是最優(yōu)解、基本可行解、基本解和可行解。1.4基本概念BasicConcepts

1/18/2023凸集(Convexset)設K是n維空間的一個點集，對任意兩點

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

設是Rn中的點若存在

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

1/18/2023極點(Extremepoint)

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

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

1/18/2023

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

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

下一節(jié)：單純形法1/18/20231.5單純形法SimplexMethod1/18/2023

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

當系數(shù)矩陣A中可以觀察得到一個可行基時（通常是一個單位矩陣或m個線性無關的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解?！纠?-15】用單純形法求例1－1線性規(guī)劃的最優(yōu)解1.5單純形法SimplexMethod1.5.1普通單純形法1/18/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

1.5單純形法

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

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

最優(yōu)解判斷標準

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

當目標函數(shù)中有基變量xi時，利用約束條件將目標函數(shù)中的xi消去即可求出檢驗數(shù)。

1.5單純形法

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

SimplexMethod1/18/2023第Ｌ個比值最小，選最小比值對應行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素；

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

【解】這是一個極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時判斷標準是：λj≥0(j=1，…，n)時得到最優(yōu)解。容易觀察到,系數(shù)矩陣中有一個3階單位矩陣,x3、x4、x5為基變量。目標函數(shù)中含有基變量x4,由第二個約束得到x4=6+x1－x2，并代入目標函數(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極小值問題,注意判斷標準,選進基變量時,應選λj<0的變量xj進基。1.5單純形法Simplex

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

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

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

SimplexMethod1/18/2023【例1-19】求解線性規(guī)劃【解】:化為標準型后用單純形法計算如下表所示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的檢驗數(shù)λ3=0,x3若增加,目標函數(shù)值不變,即當x3進基時Z仍等于20。使x3進基x5出基繼續(xù)迭代,得到表(4)的另一基本最優(yōu)解X(1),X(2)是線性規(guī)劃的兩個最優(yōu)解，它的凸組合仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。1.5單純形法

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

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

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

SimplexMethod1/18/2023【解】首先將數(shù)學模型化為標準形式式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量x6、x7，目標函數(shù)中加入―Mx6―Mx7一項，得到人工變量單純形法數(shù)學模型用前面介紹的單純形法求解，見下表。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）初始表中的檢驗數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達式代入目標涵數(shù)消去x6和x7，得到用非基變量表達的目標函數(shù)，其系數(shù)就是檢驗數(shù)；第二種算法是利用公式計算，如最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3注意：1.5單純形法

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

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

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說明這個解是偽最優(yōu)解，是不可行的，因此原問題無可行解。

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

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

用單純形法計算得到下表最優(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ī)劃?！窘狻坷?-21的第一階段問題為用單純形法計算如下表：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)目標值w=2≠0,x5仍在基變量中,從而原問題無可行解。1.5單純形法

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

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

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

SimplexMethod1/18/2023不妨假設A＝（P1，P2，…，Pn）中前m個列向量構成一個可行基，記為B=(P1，P2，…，Pm)。矩陣A中后n－m列構成的矩陣記為N＝（Pm+1,…Pn）,則A可以寫成分塊矩陣A=（B，N）。對于基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因為r（B）=m（或|B|≠0）所以B—1存在，因此可有令非基變量XN=0，XB=B—1b，由B是可行基的假設，則得到基本可行解X=(B－1b，0)T將目標函數(shù)寫成1.5單純形法

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

1.5單純形法

SimplexMethod1/18/2023上述公式可用下面較簡單的矩陣表格運算得到，設初始矩陣單純形表1-16

將B化為I（I為m階單位矩陣）,CB化為零,即求基本可行解和檢驗數(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五個公式的應用【例1-24