數(shù)學(xué)建?；A(chǔ)知識 線性規(guī)劃單純形方法

MaxS=CXs.t.AX=bX0基，基解，基可行解，可行基。⊙線性規(guī)劃問題的可行域D是凸集。⊙頂點與基可行解相對應(yīng)⊙線性規(guī)劃問題的最優(yōu)解，必定在D的頂點上達到。⊙目標函數(shù)在多個頂點上達到最優(yōu)值。這些頂點的凸組合也是最優(yōu)值。（有無窮多最優(yōu)解）。第三節(jié)線性規(guī)劃-單純形方法單純形方法基本思路：從可行域中某個基礎(chǔ)可行解（一個頂點）開始（稱為初始基礎(chǔ)可行解）。線性規(guī)劃（2）-單純形方法單純形方法基本思路：從可行域中某個基礎(chǔ)可行解（一個頂點）開始（稱為初始基礎(chǔ)可行解）。如可能，從可行域中求出具有更優(yōu)目標函數(shù)值的另一個基礎(chǔ)可行解（另一個頂點），以改進初始解。線性規(guī)劃（2）-單純形方法單純形方法基本思路：從可行域中某個基礎(chǔ)可行解（一個頂點）開始（稱為初始基礎(chǔ)可行解）。如可能，從可行域中求出具有更優(yōu)目標函數(shù)值的另一個基礎(chǔ)可行解（另一個頂點），以改進初始解。繼續(xù)尋找更優(yōu)的基礎(chǔ)可行解，進一步改進目標函數(shù)值。當某一個基礎(chǔ)可行解不能再改善時，該解就是最優(yōu)解。第三節(jié)線性規(guī)劃-單純形方法單純形方法基本思路：1.從可行域中某個基礎(chǔ)可行解（一個頂點）開始（稱為初始基礎(chǔ)可行解）。2.如可能，從可行域中求出具有更優(yōu)目標函數(shù)值的另一個基礎(chǔ)可行解（另一個頂點），以改進3.繼續(xù)尋找更優(yōu)的基礎(chǔ)可行解，進一步改進目標函數(shù)值。當某一個基礎(chǔ)可行解不能再改善時，該解就是最優(yōu)解。初始解。一、消去法例1-18：一個企業(yè)需要同一兩種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達到最大？解：數(shù)學(xué)模型maxS=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0解：引進松弛變量x3,x4,x5>=0數(shù)學(xué)模型標準形式：maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,

x3,x4,x5≥0約束條件的增廣矩陣為：121008（Ab)=40010160400112顯然r(A)=r(Ab)=3<5,該問題有無窮多組解。令A(yù)=（P1，P2，P3，P4，P5）=121004001004001X=（x1,x2,x3,x4,x5)

A=（P1，P2，P3，P4，P5）

=12

100

40

010

04

001

X=（x1,x2,

x3,x4,x5)T

B=(P3，P4，P5）=100010001x3,x4,x5是基變量，x1,x2,是非基變量。

用非基變量表示的方程：x3=8-x1-2x2x4=16-4x1(I)x5=12-4x2S=0+2x1+3x2

令非基變量（x1,

x2）T=（0，0）T

得基礎(chǔ)可行解：x(1)=(0,0,8,16,12)TS1=0經(jīng)濟含義：不生產(chǎn)產(chǎn)品甲乙，利潤為零。二、已知初始可行基求最優(yōu)解線性規(guī)劃標準型的矩陣形式(3)：MAX

S=CX(1-17)

s.t.

AX=b(1-18)X>=0(1-19)

a11a12….a1nb1A=a21a22….a2nb

=

b2…………am1am2….amnbnc1x10c2x20Ct=X=0=……………..cnxn0并且r(A)=m<n.1.最優(yōu)解判別定理：不妨假設(shè)A=（B,N）（B為一個基）相應(yīng)地有XT=(XB,XN)

C=(CB,CN)由（1-17）（1-18）Z=

(CB,CN)(XB,XN)T=CBXB+CNXNAX=（B,N）(XB,XN)T=B

XB+N

XN=b因為B為一個基,|B|≠0有XB=B-1b-B-1NXNZ=CBXB+CNXN=

CBB-1b+(CN-

CBB-1N)XN令非基變量XN=0則X

=(XB,XN)T=（B-1b,0）T為基礎(chǔ)解，其目標函數(shù)值為S=

CBB-1b只要XB=B-1b>=0,X=（B-1b,0)T>=0X為基礎(chǔ)可行解,B就是可行基。另外，若滿足CN-

CBB-1N≤0或CBB-1N-CN

≥0則對任意的x>=0有S=CX≤CBB-1b即對應(yīng)可行基B的可行解x為最優(yōu)解。定理（最優(yōu)解判別準則）對于可行基B,若C-CBB-1A≤0則對應(yīng)于基B的基礎(chǔ)可行解x就是基礎(chǔ)最優(yōu)解，此時的可行基就是最優(yōu)基。σ=C-CBB-1A為檢驗數(shù)?；兞康臋z驗數(shù)：CB-CBB-1B

=0C-CBB-1A=（0，CN-CBB-1N）換入基變量中，得到基可行解定理：若檢驗數(shù)全小于等于零，且某一個非基變量的檢驗數(shù)為0，則線性規(guī)劃問題有無窮多最優(yōu)解。（無窮多最優(yōu)解情況）證明：某個非基變量為最優(yōu)解。故線性規(guī)劃問題有無窮多最優(yōu)解。為一基可行解，有一個變量Xm+k對應(yīng)因為可行解。定理：若存在檢驗數(shù)大于零，但所對應(yīng)的換入變量Xm+k的系數(shù)向量Pm+k≤0,則原問題無最優(yōu)解。（無界解的情況）證明：構(gòu)造一個新的解，分量為定理：若非基變量檢驗數(shù)嚴格小于零，則線性規(guī)劃問題有唯一最優(yōu)解。定理：若檢驗數(shù)全小于等于零，且某一個非基變量的檢驗數(shù)為0，則線性規(guī)劃問題有無窮多最優(yōu)解。定理：若某一個非基變量的檢驗數(shù)大于0，其系數(shù)列向量Pm+k≤0,則原問題無最優(yōu)解。（無界解的情況）線性規(guī)劃為求最大化的標準型：線性規(guī)劃為求最小化的標準型時，相應(yīng)的結(jié)果？單純形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N注意：A=（B，N）檢驗數(shù)σ=C-CBB-1A=（0，CN-CBB-1N）非基變量檢驗數(shù)σ=CN-CBB-1N時,達到最優(yōu)。單純形表格：

單純形解題步驟：（已知初始可行基）求最大化時一、作對應(yīng)B的單純形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N單純形解題步驟：二、判別若檢驗數(shù)全小于等于零，則基B所對應(yīng)的基礎(chǔ)可行解X就是最優(yōu)解，終止。若存在檢驗數(shù)大于零，但所對應(yīng)的換入變量Xk的系數(shù)向量Pk≤0,則原問題無最優(yōu)解，終止。若存在檢驗數(shù)大于零，且對應(yīng)的系數(shù)列有大于零的分量，則需要換基迭代。三、換基迭代確定換入變量Xk，其中max(σj>0)=σk,xk為換入變量j=1,2,…,m確定換出基變量Xr,根據(jù)最小比值原則min(bi/aik,aik

>0,1≤i≤m)=bl/blkalk為主元素,Xl為換出基變量。對單純形表T（B）進行初等行變換（主元運算）得到新的單純形表。經(jīng)過上述有限次的換基迭代，就可得到原問題的最優(yōu)解，或判定無最優(yōu)解。例1-19求線性規(guī)劃問題：

maxS=2x1+3x2s.t.x1+2x2<=84x1<=164x2<=12x1,x2>=0解：對目標函數(shù)標準化maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,

x3,x4,x5>=0

12100A=4001004001（x1x2x3x4x5）=（NB）解：

100B=010=Ib=(8,16,12)T001x3

x4,x5為基變量，CB=（0，0,0）x1,x2為非基變量。有B-1=I,B-1b=b,B-1A=A,單純性表如下：初始單純性表TAB(1)為：x2換入,x5換出；得TAB(2)為：x1換入,x3換出；得TAB(3)為：x5換入,x4換出；得TAB(4)為：此時所有的檢驗數(shù)小于等于零，此時的基礎(chǔ)可行解X=（4，2，0，0,4）T就是最優(yōu)解，對應(yīng)的目標函數(shù)值：S=14就是最優(yōu)值，對應(yīng)的B4就是最優(yōu)基。

求最大化LP問題單純形表解題步驟：一.LP問題化成標準型,列初始單純形表二.判別1.若檢驗數(shù)全小于等于零，則基B所對應(yīng)的基礎(chǔ)可行解X就是最優(yōu)解，終止。2.若存在檢驗數(shù)大于零，但所對應(yīng)的換入變量Xk的系數(shù)向量Pk≤0,則原問題無最優(yōu)解，終止。3.若存在檢驗數(shù)大于零，且對應(yīng)的系數(shù)列有大于零的分量，則需要換基迭代。三.換基迭代1.確定換入變量Xk，其中max(σj>0)=σk,xk為換入變量j=1,2,…,m2.確定換出基變量Xr,根據(jù)最小比值原則min(bi/aik,aik>0,1≤i≤m)=bl/blkalk為主元素,Xl為換出基變量。對單純形表T（B）進行初等行變換（主元運算）得到新的單純形表。經(jīng)過上述有限次的換基迭代，就可得到原問題的最優(yōu)解，或判定無最優(yōu)解。定理（求最小化的最優(yōu)解判別準則）（1）若σ=C-CBB-1A≥0，則對應(yīng)于基B的基礎(chǔ)可行解x就是基礎(chǔ)最優(yōu)解，此時的可行基就是最優(yōu)基。（2）若檢驗數(shù)全大于等于零，且某一個非基變量的檢驗數(shù)為0，則線性規(guī)劃問題有無窮多最優(yōu)解。（無窮多最優(yōu)解情況）（3）若存在檢驗數(shù)小于零，但所對應(yīng)的換入變量Xm+k的系數(shù)向量Pm+k≤0,則原問題無最優(yōu)解。（無界解的情況）確定換入變量時，找小于0中的最小者。M法

當原問題求最大化時，假定人工變量在目標函數(shù)中的系數(shù)為（-M）（M為任意大正數(shù)），目標函數(shù)求最大化，必須把人工變量從基變量換出，否則，不可能實現(xiàn)最大化。

當原問題求最小化時，假定人工變量在目標函數(shù)中的系數(shù)為M（M為任意大正數(shù)），目標函數(shù)求最小化，必須把人工變量從基變量換出，否則，不可能實現(xiàn)最小化。例8線性規(guī)劃問題

-3 1 100MMcj→cj→-3 1 100MM

線性規(guī)劃問題達到最優(yōu),最優(yōu)解及最優(yōu)值為:

二.兩階段法

當用計算機求解含人工變量的線性規(guī)劃問題時，只能用很大的數(shù)代替M，否則，會造成計算機的錯誤。而兩階段法避免了這一錯誤。第一階段：不考慮原問題是否存在基可行解；給原線性規(guī)劃問題加入人工變量，構(gòu)造目標函數(shù)為人工變量的和，約束是原問題的約束。

用單純形法求解上述模型，若目標函數(shù)值為0，說明原問題有基可行解，進行第二階段計算，否則，原問題無可行解。第二階段：將第一階段計算得到的最終表，除去人工變量，將目標函數(shù)行的系數(shù)，換為原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表。例9線性規(guī)劃問題

解：加入人工變量，給出第一階段的線性規(guī)劃模型:人工變量已經(jīng)換出，則ω=0，得到基可行解，將第一階段的人工變量取消，填入原問題的目標函數(shù)的系數(shù)，進行第二階段運算。

cj→

0 0 00011人工變量已經(jīng)換出，則ω=0，得到基可行解，將第一階段的人工變量取消，即上表中劃去人工變量所在列，填入原問題的目標函數(shù)的系數(shù)，進行第二階段運算。

cj→ -3 1 100最優(yōu)解為：x1,=4,x2,=1,x3=9,最優(yōu)值z=-2.

應(yīng)用舉例例1配料問題某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價，每天能供應(yīng)的原材料數(shù)量及原材料單價見下表。該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？產(chǎn)品名稱規(guī)格要求單價（元/kg)A原材料C不少于50﹪，原材料P不超過25﹪50B原材料C不少于25﹪，原材料P不超過50﹪35D不限25原材料名稱每天最多供應(yīng)量（kg)單價（元/kg)CPH10010060652535解：設(shè)xij為產(chǎn)品A、B、D中含C、P、H的公斤數(shù)。列表如下：原材料

產(chǎn)品

CPHAx11x12x13Bx21x22x23Dx31x32x33解：數(shù)學(xué)模型為：產(chǎn)品名稱規(guī)格要求單價（元/kg)A原材料C不少于50﹪，原材料P不超過25﹪50B原材料C不少于25﹪，原材料P不超過50﹪35D不限25原材料產(chǎn)品CPHAx11x12x13Bx21x22x23Dx31x32x33例2連續(xù)投資問題某部門有100萬元，在今后五年內(nèi)考慮給下列項目進行投資項目A:從第一年到第四年每年年初需要投資，并于次年末回收本利104％；項目B:從第三年初投資，到第五年末回收本利105％；但規(guī)定最大投資額不超過40萬元；項目C:從第二年初投資，到第五年末回收本利108％；但規(guī)定最大投資額不超過30萬元；項目D:五年內(nèi)每年可購買國債，于當年末歸還，并加息3％；問該部門如何確定每年的投資計劃，使五年末擁有的本金最大？解：設(shè)xiA,xiB,xiC,xiD,分別表示第i年年初給項目A、B、C、D的投資額。列表如下：

年份項目

12345

ABCD

x1Ax2Ax3Ax4A

x3B

x2Cx1Dx2Dx3Dx4Dx5D數(shù)學(xué)模型為：人力資源分配的問題

解：設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標函數(shù)：MinZ=x1+x2+x3+x4+x5+x6

s.t.x1+x6

≥60

x1+x2

≥70

x2+x3

≥60

x3+x4

≥50

x4+x5

≥20

x5+x6

≥30

x1,x2,x3,x4,x5,x6

≥0

班次：1，2，3，4，5，6

x6+x1,x1+x2,x2+x3,x3+x4,x4+x5,x5+x6例求線性