運(yùn)籌學(xué)第5章 線性規(guī)劃(max)單純形法

Chapter5線性規(guī)劃LinearProgramming5.1標(biāo)準(zhǔn)型

StandardformofLP5.2單純形法

SimplexMethod5.1線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP04二月20233

在用單純形法求解線性規(guī)劃問題時(shí)，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。5.1線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP線性規(guī)劃問題的標(biāo)準(zhǔn)型為:1．目標(biāo)函數(shù)求最大值;2．約束條件都為等式方程;3．變量xj非負(fù);4．常數(shù)bi非負(fù).04二月20234max

Z=c1x1+c2x2+…+cnxn5.1線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP線性規(guī)劃問題的標(biāo)準(zhǔn)型為:04二月2023504二月2023604二月20237注：化標(biāo)準(zhǔn)型的方法1、目標(biāo)極小化極大：min(f)=--max(-f)2、不等式化等式：（1）大于等于“≥”：在左邊減去乘余變量（）≥b

（）--s=b（2）小于等于“≤”：在左邊添加松馳變量（）≤b

（）+t=b04二月202383、常數(shù)項(xiàng)負(fù)化正：兩邊乘（－1）4、變量負(fù)化正：乘（－1）5、自由變量（無要求)04二月202396、對于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替換。04二月202310

當(dāng)某個(gè)約束是絕對值不等式時(shí)，將絕對值不等式化為兩個(gè)不等式，再化為等式，例如約束將其化為兩個(gè)不等式

再加入松馳變量化為等式。1.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1.2單純形法SimplexMethod04二月202312一、典范式線性規(guī)劃的單純形法1.形如：典范式線性規(guī)劃04二月202313典范式線性規(guī)劃04二月202314典范式線性規(guī)劃04二月202315典范式線性規(guī)劃04二月202316典范式線性規(guī)劃04二月202317典范式線性規(guī)劃04二月202318(1)系數(shù)矩陣2.基本概念04二月202319系數(shù)矩陣列向量04二月202320

單位陣.

單位向量.04二月202321其余列向量稱為非基向量

單位向量對應(yīng)的列向量稱為基向量(2)基向量與非基向量

基向量非基向量04二月202322基向量對應(yīng)的變量稱為基變量，非基向量對應(yīng)的變量稱為非基變量

基向量非基向量(2)基變量與非基變量

基變量04二月202323(4)基本解

(basissolution)令非基變量等于零，由方程組

AX=b解出基變量，則這組解稱為方程組的基本解。令則方程組為04二月202324則基本解為令則方程組為04二月202325(5)基本可行解(basis

feasiblesolution)

若基本解是可行解則稱為是基本可行解（也稱基可行解）可行點(diǎn)(解)：滿足所有約束條件的點(diǎn)04二月202326基本可行解04二月202327(6)檢驗(yàn)數(shù)的檢驗(yàn)數(shù):04二月20232804二月202329(7)單純形表211040130130340000340004二月2023303.單純形法計(jì)算步驟：(1).求初始基可行解:根據(jù)典范式列出初始單純形表。(2).最優(yōu)解判斷：（a）若檢驗(yàn)數(shù)λj≤０（j＝１，２，…，n）得到最優(yōu)解；（b）某個(gè)檢驗(yàn)數(shù)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃無最優(yōu)解(具有無界解)。（c）若對λk>0,都有aik(i=1,…,m)不全為負(fù)，則進(jìn)行換基；04二月202331第Ｌ個(gè)比值最小，選最小比值對應(yīng)行的基變量為出基變量，aLk為主元素；

(c）求新的基可行解：用行變換方法將aLk

化為１,其所在列的其它元素化為零,得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。（b）選出基變量

:求最小比值(3).換基(換基可行解)：（a）選進(jìn)基變量設(shè)λk=max｛λj|λj>0｝,xk為進(jìn)基變量04二月202332【例1】用單純形法求下列線性規(guī)劃的最優(yōu)解04二月202333【解】化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為1.5單純形法

SimplexMethod04二月202334初始單純形表比值211040130130340000340004二月202335進(jìn)基列出基行bi/ai2，ai2>0θi表1-4(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后得到1.5單純形法

SimplexMethod30183

4

0

0

0

0

0

4

4

3

04二月202336最優(yōu)解X=(18，4，0，0)T，最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18,4)最優(yōu)值Z=70X(1)=(0,0)2010x2x1301.5單純形法

SimplexMethodX(2)=(0,10)04二月202337【例2】

用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計(jì)算結(jié)果如表1.５所示。1.5單純形法

SimplexMethod04二月202338Cj12

100bθCBXBx1x2x3x4x50x42－3210150x51/3-150120λj12100

0x4

2x2λj

1x1

2x2

λj

表1－51/3150120301713751/30-90-22025601017/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單純形法

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

SimplexMethod04二月202340比值3-21012-1014-110000-1100初始單純形表為04二月202341λ2=1>0,

而a12<0，a22<0，沒有比值，從而線性規(guī)劃的最優(yōu)解無界。比值3-21012-1014-110000-110004二月202342由模型可以看出，當(dāng)固定x1使x2→+∞且滿足約束條件，還可以用圖解法看出具有無界解。04二月202343【例4】求解線性規(guī)劃【解】:化為標(biāo)準(zhǔn)型1.5單純形法

SimplexMethod04二月202344用單純形法計(jì)算如下表所示04二月202345

C24000CBXBx1x2x3x4x5bθ000x3x4x5－111[2]2－11000100014→10225—λj24↑000400x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0-200420x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑-20420x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000-2004二月202346420x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑-20

表(3)中λj全部非負(fù),則最優(yōu)解為:420x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000-20得到表(4)的另一基本最優(yōu)解04二月202347X(1),X(2)是線性規(guī)劃的兩個(gè)最優(yōu)解，它的凸組合

仍是最優(yōu)解，從而原線性規(guī)劃有多重最優(yōu)解。04二月202348唯一最優(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單純形法

SimplexMethod04二月202349

通常線性規(guī)劃的標(biāo)準(zhǔn)型并非典范式,為了得到典范式，在約束條件的等式左端加一組虛擬變量，這種人為加的變量稱為人工變量。構(gòu)成典范式后再用單純形法求解，基于這種解法的有：大M法或兩階段法(人工變量法)。1.5.2大M法1.5單純形法

SimplexMethod04二月202350【例5】用大M法解下列線性規(guī)劃1.大M法04二月2023511.5單純形法

SimplexMethod【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式引進(jìn)x4，x5(松弛變量)，得到標(biāo)準(zhǔn)型(非典范式)第一、三約束中分別加入人工變量x6、x7，目標(biāo)函數(shù)中加入―Mx6―Mx7，得到典范式Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M

0-Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑-M000-M0-1x6x5x3－6－32[5]3－2001－100010100-1-213→81λj5-6M5M↑0-M00-2M+120-1x2x5x3－6/5[3/5]－2/5100001-1/53/5-2/50101/5-3/52/5-1/5-13/5-2/53/531/5→11/5λj5↑0000-M-M04二月202353Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M

0-Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑-M000-M0-1x6x5x3－6－32[5]3－2001－100010100-1-213→81λj5-6M5M↑0-M00-2M+120-1x2x5x3－6/5[3/5]－2/5100001-1/53/5-2/50101/5-3/52/5-1/5-13/5-2/53/531/5→11/5λj5↑0000-M-M23-1x2x1x301010000111025/32/3-1-10-27/5-13/3-32/51331/319/3λj000-5-25/3-M+2-M+22/504二月202354M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3注意：1.5單純形法

SimplexMethod04二月2023551.5單純形法

SimplexMethod【例6】求解線性規(guī)劃【解】加入松馳變量x3、x4化為標(biāo)準(zhǔn)型在第二個(gè)方程中加入人工變量x5，目標(biāo)函數(shù)中加上Mx5一項(xiàng)，得到04二月202356用單純形法計(jì)算如下表所示。

Cj-5800-MbCBXBx1x2x3x4x50-Mx3x5[3]11－