第一講線性規(guī)劃應(yīng)用舉例與單純形法

第一講線性規(guī)劃應(yīng)用舉例與單純形法第1頁，課件共68頁，創(chuàng)作于2023年2月一、線性規(guī)劃的數(shù)學(xué)模型與應(yīng)用舉例

【例1】最優(yōu)生產(chǎn)計劃問題。某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要在設(shè)備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表1所示。已知在計劃期內(nèi)設(shè)備的加工能力各為200臺時，可供材料分別為360、300公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定市場需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的利潤收入最大？第2頁，課件共68頁，創(chuàng)作于2023年2月

產(chǎn)品資源

甲

乙丙現(xiàn)有資源設(shè)備A312200設(shè)備B224200材料C451360材料D235300利潤(元/件)

403050表1產(chǎn)品資源消耗線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第3頁，課件共68頁，創(chuàng)作于2023年2月【解】設(shè)x1、x2、x3

分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量,則數(shù)學(xué)模型為：

產(chǎn)品

資源甲

乙丙現(xiàn)有資源設(shè)備A312200設(shè)備B224200材料C451360材料D235300利潤(元/件)403050線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第4頁，課件共68頁，創(chuàng)作于2023年2月【例2】某飼料公司用甲、乙兩種原料配制飼料，甲乙兩種原料的營養(yǎng)成份及配合飼料中所含各營養(yǎng)成份最低量由表2給出。已知單位甲、乙原料的價格分別為10元和20元，求滿足營養(yǎng)需要的飼料最小成本配方。

線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第5頁，課件共68頁，創(chuàng)作于2023年2月【解】設(shè)x1、x2分別為甲、乙兩種原料的用料數(shù)量,則數(shù)學(xué)模型為：線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第6頁，課件共68頁，創(chuàng)作于2023年2月1．解決問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問題的約束條件是一組多個決策變量的線性不等式或等式。線性規(guī)劃數(shù)學(xué)模型的特征：線性規(guī)劃數(shù)學(xué)模型的三要素：決策變量(Decisionvariables);

目標(biāo)函數(shù)(Objectivefunction);約束條件(Constraints);建立一個問題的線性規(guī)劃模型的一般步驟：確定決策變量；(2)確定目標(biāo)函數(shù)；(3)確定約束條件；(4)確定變量是否有非負(fù)約束。線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第7頁，課件共68頁，創(chuàng)作于2023年2月線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中,有m個約束,有n個決策變量xj(j=1,2,…,n)，目標(biāo)函數(shù)的變量系數(shù)用cj表示,

cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第8頁，課件共68頁，創(chuàng)作于2023年2月在實際中一般xj≥0,但有時xj≤0或xj無符號限制。為了書寫方便，上式也可寫成：

線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第9頁，課件共68頁，創(chuàng)作于2023年2月

【例3】某農(nóng)戶計劃用12公頃耕地生產(chǎn)玉米，大豆和地瓜，可投入48個勞動日，資金360元。生產(chǎn)玉米1公頃，需6個勞動日，資金36元，可獲凈收入200元；生產(chǎn)1公頃大豆，需6個勞動日，資金24元，可獲凈收入150元；生產(chǎn)1公頃地瓜需2個勞動日，資金18元，可獲凈收入120元，問怎樣安排才能使總的凈收入最高。

【解】設(shè)農(nóng)戶種玉米、大豆及地瓜的數(shù)量分別為x1、x2、x3

公頃，則數(shù)學(xué)模型為：線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第10頁，課件共68頁，創(chuàng)作于2023年2月線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第11頁，課件共68頁，創(chuàng)作于2023年2月【例4】某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如表3所示。表3營業(yè)員需要量統(tǒng)計表問：商場人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場總的營業(yè)員最少？星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四400線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第12頁，課件共68頁，創(chuàng)作于2023年2月線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP【解】設(shè)

(j=1,2,…,7)為休息2天后星期一到星期日開始上班的營業(yè)員，則這個問題的線性規(guī)劃模型為第13頁，課件共68頁，創(chuàng)作于2023年2月【例5】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。

【解】設(shè)

x1：第一年的投資；

x2：第一年的預(yù)留資金；

x3：第二年新的投資；x4：第二年的預(yù)留資金；

x5：第三年新的投資；x6：第三年的預(yù)留資金；

x7：第四年新的投資；

x8：第四年的預(yù)留資金；

x9：第五年的預(yù)留資金；

線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第14頁，課件共68頁，創(chuàng)作于2023年2月

第五年：(x7/2+x9)=x8+2x5

第三年：(x3/2+x5)+x6=x4+2x1

第四年：(x5/2+x7)+x8=x6+2x3

到第六年實有資金總額為x9+2x7，整理后得到下列線性規(guī)劃模型

第一年：x1+x2=200(萬元)第二年：(x1/2+x3)+x4=x2線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第15頁，課件共68頁，創(chuàng)作于2023年2月【例6】均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲零件和3件乙零件組裝而成。兩種零件必須經(jīng)過設(shè)備A、B上加工，每件甲零件在A、B上的加工時間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時間分別為4分鐘和10分鐘。現(xiàn)有2臺設(shè)備A和3臺設(shè)備B，每天可供加工時間為8小時。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時間不超過另一種設(shè)備總時間1小時。怎樣安排設(shè)備的加工時間使每天產(chǎn)品的產(chǎn)量最大。線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第16頁，課件共68頁，創(chuàng)作于2023年2月【解】設(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是設(shè)備A、B每天加工工時的約束為要求一種設(shè)備每臺每天的加工時間不超過另一種設(shè)備1小時的約束為線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第17頁，課件共68頁，創(chuàng)作于2023年2月目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價于約束線性化。將絕對值約束寫成兩個不等式線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第18頁，課件共68頁，創(chuàng)作于2023年2月線性規(guī)劃模型為線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP第19頁，課件共68頁，創(chuàng)作于2023年2月線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP線性規(guī)劃問題的標(biāo)準(zhǔn)型為:1．目標(biāo)函數(shù)求最大值2．約束條件都為等式方程3．變量xj非負(fù)4．常數(shù)bi非負(fù)

在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。第20頁，課件共68頁，創(chuàng)作于2023年2月線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第21頁，課件共68頁，創(chuàng)作于2023年2月或?qū)懗上铝行问剑?/p>

或用矩陣形式線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第22頁，課件共68頁，創(chuàng)作于2023年2月稱Ａ為約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，n是決策變量的個數(shù)，一般情況m≤n，且r(Ａ)＝m。其中:線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第23頁，課件共68頁，創(chuàng)作于2023年2月一般形式線性規(guī)劃模型的標(biāo)準(zhǔn)化準(zhǔn)則:（前提bi

≥0

）5.xj≤0令xj

=－x'j,x'j≥0

線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第24頁，課件共68頁，創(chuàng)作于2023年2月【例7】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型

【分析】(１)因為x3無符號要求，即x3可取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第25頁，課件共68頁，創(chuàng)作于2023年2月

(3)第二個約束條件是“≥”號，在“≥”號左端減去剩余變量(surplusvariable)x5，x5≥0，也稱松馳變量；(2)第一個約束條件是“≤”號，在“≤”號左端加入松馳變量

(slackvariable)x4，x4≥0,化為等式；(4)第三個約束條件是“≤”號且常數(shù)項為負(fù)數(shù)，因此在“≤”左邊加入松馳變量x6，x6≥0，同時兩邊乘以－1。

(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時Z′達(dá)到最大值。線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第26頁，課件共68頁，創(chuàng)作于2023年2月綜合起來得到下列標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第27頁，課件共68頁，創(chuàng)作于2023年2月當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束

將其化為兩個不等式

再加入松馳變量化為等式。

線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第28頁，課件共68頁，創(chuàng)作于2023年2月

設(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中至少有一個m×m子矩陣B，使得r(B)=m。線性規(guī)劃的有關(guān)概念

可行解(feasiblesolution):

滿足式(1.2)及(1.3)的解X=（x1,x2,…,xn)T稱為可行解；基

(basis)：A中m×m子矩陣B并且有r(B)=m，則稱B是線性規(guī)劃的一個基(或基矩陣basismatrix)。線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP第29頁，課件共68頁，創(chuàng)作于2023年2月當(dāng)確定某一矩陣為基矩陣時，則基矩陣對應(yīng)的列向量稱為基向量(basicvector)，其余列向量稱為非基向量;

基向量對應(yīng)的變量稱為基變量(basicvariable)，非基向量對應(yīng)的變量稱為非基變量；注：基變量、非基變量是針對某一確定基而言的，不同的基對應(yīng)的基變量和非基變量也不同。

基本概念BasicConcepts

基本可行解(basic

feasiblesolution):

若基本解是可行解則稱為是基本可行解（也稱基可行解）。

基本解(basicsolution):對某一確定的基B，令非基變量等于零，利用式(1.2)解出基變量，則這組解稱為基Ｂ的基本解。第30頁，課件共68頁，創(chuàng)作于2023年2月

最優(yōu)解(optimalsolution):滿足式(1.1)的可行解稱為最優(yōu)解，即使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解；非可行解(infeasiblesolution)

無界解

(unboundedsolution)注：（1）只要基本解中的基變量的解滿足式(1.3)的非負(fù)要求，那么這個基本解就是基本可行解。

（2）可行解不一定是基本可行解，同樣基本解也不一定是可行解?？尚谢?

基可行解對應(yīng)的基稱為可行基；最優(yōu)基:基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基；基本最優(yōu)解:

最優(yōu)解是基本解稱為基本最優(yōu)解。

基本概念BasicConcepts

第31頁，課件共68頁，創(chuàng)作于2023年2月凸集(Convexset):設(shè)K是n維空間Rn的一個點集，對任意兩點

時，則稱K為凸集。

就是以X(1)、X(2)為端點的線段方程,點X的位置由α的值確定,當(dāng)α=0時,X=X(2),當(dāng)α=1時X=X(1)。凸組合(Convexcombination)

:設(shè)是Rn中的點，若存在使得成立，稱X為的凸組合

基本概念BasicConcepts

第32頁，課件共68頁，創(chuàng)作于2023年2月極點(Extremepoint)::

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

基本概念BasicConcepts

第33頁，課件共68頁，創(chuàng)作于2023年2月【定理1.1】若線性規(guī)劃可行解集K非空,則K是凸集。

【定理1.2】線性規(guī)劃的可行解集合K的點X是極點的充要條件為X

是基本可行解?！径ɡ?.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個極點上達(dá)到,最優(yōu)解就是極點的坐標(biāo)向量。注：定理1.2刻劃了可行解集的極點與基本可行解的對應(yīng)關(guān)系，極點是基本可行解，反之，基本可行解一定是極點，但它們并非一一對應(yīng)，有可能兩個或幾個基本可行解對應(yīng)于同一極點(退化基本可行解時)。線性規(guī)劃的基本定理

基本概念BasicConcepts

第34頁，課件共68頁，創(chuàng)作于2023年2月

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

當(dāng)系數(shù)矩陣A中可以觀察得到一個可行基時(通常是一個單位矩陣或m個線性無關(guān)的單位向量組成的矩陣)，則可以通過解線性方程組求得基本可行解。單純形法

SimplexMethod單純形法第35頁，課件共68頁，創(chuàng)作于2023年2月【例8】用單純形法求下列線性規(guī)劃的最優(yōu)解

【解】化為標(biāo)準(zhǔn)型:單純形法

SimplexMethod第36頁，課件共68頁，創(chuàng)作于2023年2月系數(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ōu)解？單純形法

SimplexMethod第37頁，課件共68頁，創(chuàng)作于2023年2月我們可在目標(biāo)函數(shù)中把基變量用非基變量來表示，則可根據(jù)非基變量的系數(shù)來判斷目標(biāo)函數(shù)有沒有達(dá)到最優(yōu)值，把判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作λj(j=1,2,…,n)。

本例中λ1=3,λ2=4,λ3=0,λ4=0。

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

當(dāng)所有檢驗數(shù)λj≤0(j=1，…，n)時，基本可行解為最優(yōu)解。注：當(dāng)目標(biāo)函數(shù)中有基變量xi時，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗數(shù)。

檢驗數(shù):目標(biāo)函數(shù)用非基變量表達(dá)時的變量系數(shù)。單純形法

SimplexMethod第38頁，課件共68頁，創(chuàng)作于2023年2月典則形式(典式):(1)約束方程組中基變量的系數(shù)矩陣是的單位矩陣，移項后基變量可由非基變量表出；(2)目標(biāo)函數(shù)中不含有基變量，只含非基變量(因為基變量可由非基變量表出)。

通常我們把典式中的相關(guān)數(shù)據(jù)列在一張表上，顯得比較直觀、簡潔。若初始基可行解不是最優(yōu)解，我們也可直接在表上進(jìn)行作業(yè)，換到下一個基可行解，把這樣的表叫做單純形表。

如何通過觀察第一個基本可行解并能判斷是否為最優(yōu)解，關(guān)鍵看模型是不是典則形式（簡稱典式）：單純形法

SimplexMethod第39頁，課件共68頁，創(chuàng)作于2023年2月進(jìn)基列出基行bi/ai2，ai2>0θi表6(1)XBx1x2x3x4bx3211040x4130130λj3400

(2)x3x2λj

(3)x1

x2

λj

基變量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1將3化為1乘以1/3后得到3018單純形法

SimplexMethod第40頁，課件共68頁，創(chuàng)作于2023年2月注:

(1)

在選進(jìn)基變量時，一般選λk>0中較大者所對應(yīng)的變量進(jìn)基，也可任選一個λk>0所對應(yīng)的變量進(jìn)基，還可第一個λk>0所對應(yīng)的變量進(jìn)基。(2)選出基變量時，必須遵循最小比值原則(保證從一個可行基換到另一個可行基)，若有兩個或兩個以上相同最小的比值，則任選一個最小比值所對應(yīng)的基變量出基，這時下一個基可行解中存在為0的基變量，稱之為退化的基可行解。(3)表(1.5)中的每一張表對應(yīng)的模型都是典式，從一個可行基換到另一個可行基，接下來的任務(wù)就是從當(dāng)前典式換到另一個典式。(4)當(dāng)目標(biāo)函數(shù)是求最大值時,λj≤0(j=1，…，n)時達(dá)到最優(yōu)解；當(dāng)目標(biāo)函數(shù)是求最小值時,λj≥0(j=1，…，n)時達(dá)到最優(yōu)解。單純形法

SimplexMethod第41頁，課件共68頁，創(chuàng)作于2023年2月單純形法的計算步驟：1.找一個初始可行基，寫出對應(yīng)的典式，列出初始單純形表,其中基變量的檢驗數(shù)必為零；

2.判斷：(a)若λj≤０(j＝１，２，…，n)，則得到最優(yōu)解；(b)若存在某個λk>0且aik≤０(i=1，2,…,m)，則線性規(guī)劃具有無界解；(c)若存在λk>0且aik(i=1,…,m)不全非正，則進(jìn)行換基；3.換基：(a)選進(jìn)基變量：設(shè)λk=max｛λj|λj>0｝,選第k列所對應(yīng)的變量xk為進(jìn)基變量。單純形法

SimplexMethod第42頁，課件共68頁，創(chuàng)作于2023年2月第Ｌ個比值最小，選最小比值對應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個aLk為主元素。

(c)求新的基可行解：用初等行變換方法將aLk化為１,第k列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。(b)選出基變量：求最小比值單純形法

SimplexMethod第43頁，課件共68頁，創(chuàng)作于2023年2月【例9】用單純形法求解

【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：單純形法

SimplexMethod第44頁，課件共68頁，創(chuàng)作于2023年2月Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表71/3150120301713751/30－90－2—2025601017/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單純形法

SimplexMethod第45頁，課件共68頁，創(chuàng)作于2023年2月【例10】用單純形法求解

【解】

這是一個極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可直接求解,這時判斷標(biāo)準(zhǔn)是:

λj≥0(j=1,…,n)得到最優(yōu)解。容易觀察到系數(shù)矩陣中有一個3階單位矩陣,x3、x4、x5為基變量。單純形法

SimplexMethod第46頁，課件共68頁，創(chuàng)作于2023年2月XBx1x2x3x4x5bθ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)T,最優(yōu)值Z=2x1－2x2－x4=－2×5－1=－11。表8單純形法

SimplexMethod第47頁，課件共68頁，創(chuàng)作于2023年2月

【例11】求解線性規(guī)劃【解】化為標(biāo)準(zhǔn)型單純形法

SimplexMethod第48頁，課件共68頁，創(chuàng)作于2023年2月初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2進(jìn)基，而a12<0，a22<0，沒有比值，故該線性規(guī)劃問題具有無界解。另外由模型可以看出，當(dāng)固定x1，而使x2→+∞且滿足約束條件，從而原問題具有無界解。單純形法

SimplexMethod第49頁，課件共68頁，創(chuàng)作于2023年2月【例12】求解線性規(guī)劃用單純形法計算如下表所示：【解】化為標(biāo)準(zhǔn)型為：單純形法

SimplexMethod第50頁，課件共68頁，創(chuàng)作于2023年2月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/23/41/41/2－1/40017/235/2→λj000－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－201/4－1/2[3/4]0↑14—10/3單純形法

SimplexMethod第51頁，課件共68頁，創(chuàng)作于2023年2月

表(3)中λj全部非正,此時已找到最優(yōu)解，且最優(yōu)解為:另外表(3)中非基變量x3的檢驗數(shù)λ3=0,x3若增加,目標(biāo)函數(shù)值不變,即當(dāng)x3進(jìn)基時Z仍等于20?，F(xiàn)使x3進(jìn)基,x5出基繼續(xù)迭代,得到表(4)的另一基本最優(yōu)解X(1),X(2)是線性規(guī)劃的兩個最優(yōu)解，它的凸組合

仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。單純形法

SimplexMethod第52頁，課件共68頁，創(chuàng)作于2023年2月唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解

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

某個λk>0且aik≤０(i=1,2,…,m)，則線性規(guī)劃具有無界解。退化基本可行解的判斷:存在某個基變量為零的基本可行解。單純形法

SimplexMethod第53頁，課件共68頁，創(chuàng)作于2023年2月設(shè)有線性規(guī)劃其中矩陣Am×n且r(A)=m,X≥0理解為X大于等于零的向量，即xj≥0(j=1,2,…,n)。計算公式單純形法

SimplexMethod第54頁，課件共68頁，創(chuàng)作于2023年2月不妨假設(shè)A＝(P1,P2,…,Pn)中前m個列向量構(gòu)成一個可行基，記為B=(P1,P2,…,Pm)。矩陣A中后n－m列構(gòu)成的矩陣記為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+1,Cm+2,…,cn),

則AX=b可寫成單純形法

SimplexMethod第55頁，課件共68頁，創(chuàng)作于2023年2月因為r(B)=m(或|B|≠0)所以B-1存在，因此可有令非基變量XN=0，XB=B—1b，由B是可行基的假設(shè)，則得到基本可行解X=(B－1b，0)T消去目標(biāo)函數(shù)中的基變量，于是目標(biāo)函數(shù)可寫成單純形法

SimplexMethod第56頁，課件共68頁，創(chuàng)作于2023年2月得到下列五個計算公式：(令XN=0)

單純形法

SimplexMethod第57頁，課件共68頁，創(chuàng)作于2023年2月上述公式可用下面較簡單的矩陣表格運算得到，將目標(biāo)函數(shù)寫成CBXB+CNXN

－Z=0,約束為BXB+NXN=b將B化為E(E為m階單位矩陣),即求基本可行解。用B－1左乘表中第二行,得到表10XBXNbXBEB-1NB-1bCBCN0XBXNbXBBNbCBCN0表10單純形法

SimplexMethod第58頁，課件共68頁，創(chuàng)作于2023年2月將第二行左乘－CB后加到第三行,得到λΝXB－Z0XBXNbXBEB-1NB-1bλ＝Cj－Zj0CN-CBB－1N－CBB－1b表11將CB化為零,即求檢驗數(shù):單純形法