運籌學(xué)基礎(chǔ)線性規(guī)劃

運籌學(xué)基礎(chǔ)線性規(guī)劃第1頁，共39頁，2023年，2月20日，星期日另例：000-3-412-1023160-142x1

x2

x3x4

b問題：無標(biāo)準(zhǔn)的初始可行基，如何利用單純形法求解化為標(biāo)準(zhǔn)形不是標(biāo)準(zhǔn)的初始可行基第2頁，共39頁，2023年，2月20日，星期日

三、人工變量問題用單純形法解題時，需要有一個單位矩陣作為初始基。當(dāng)約束條件都是“≤”時，加入松弛變量就形成了初始基。但如果存在“≥”或“＝”型的約束，就沒有現(xiàn)成的單位矩陣。采用人造基的辦法：人為構(gòu)造單位矩陣處理方法有兩種：大M法兩階段法第3頁，共39頁，2023年，2月20日，星期日（一）大M法maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量。

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4

=6x1-2x2+x3+

x5=4x1,x2,x3,x4,x5≥0人工變量最終必須等于0才能保持原問題性質(zhì)不變。為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為-M。M為無限大的正數(shù)，這是一個懲罰項，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當(dāng)然亦無最優(yōu)解。第4頁，共39頁，2023年，2月20日，星期日大M法求解按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問題如下：

例如

maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.

maxZ=

3x1-x2-2x3-M

x4-M

x53x1+2x2-3x3+

x4

=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0第5頁，共39頁，2023年，2月20日，星期日

初始單純形表為：0-M-2-13411-2160-323-M01～10M0-2-2M-13+4M4

11-216

0-3230

0

1

3+3M-1+2M-2-3M0-M6M所以，此時求解不是最優(yōu)解，需要換基。x1

x2

x3x4x5b10M0-2-2M-13+4M411-2160-323001

3+4M-1-2-2M0

010M～第6頁，共39頁，2023年，2月20日，星期日

10M0-2-2M-13+4M411-2160-323001～-6+2M0

1+2M-3-8M/30212-8/3020-12/31-1-4M/3-1/31/3-7-M-1/20-5/3011/21-4/3031/20-2/31-M-5/6-1/61/6～x2=0,x4=0,x5=0,x1=3,x3=1,σj<0，此時求解最優(yōu)即X0=(3,0,1,0,0)T時，-Z=-7，最優(yōu)解maxZ=7第7頁，共39頁，2023年，2月20日，星期日試用大M法求解如下線性規(guī)劃問題的最優(yōu)解。劃為標(biāo)準(zhǔn)型，并按大M法引入人工變量x4,x5的輔助問題如下：松馳變量剩余變量人工變量懲罰項第8頁，共39頁，2023年，2月20日，星期日解：0-M0-1-1311010-230021-411011-2100-10-M010～4M00

-1+3M-1+M3-6M11010-230021-411011-21-M0-10

0010x1

x2

x3

x4

x5

x6x7bx1

x2

x3

x4

x5

x6x7b第9頁，共39頁，2023年，2月20日，星期日M+1-3M+10

0-1+M111010-21-2001010-110-23-M0-1000102-M-10

00111010-21-2001012-51003-10-1-21-M012-2-M+23-1/3

0009-7/32/31001-200104-5/31/3001-1/3-4/3-1-2/31/3-M4/312/3～～令x4=0,x5,=0,x6=0,x7,=0,得x1=4,x2=1,x3=9即X0=(4,1,9,0,0,0,0)T此時-Z’=-2為最大,則最優(yōu)解minZ=-2～第10頁，共39頁，2023年，2月20日，星期日（二）兩階段法這種方法是在約束條件中加入人工變量，將線性規(guī)劃問題分為兩階段進(jìn)行求解。第一階段是先求以人工變量等于0為目標(biāo)的線性規(guī)劃問題第二階段利用已求出的初始基可行解來求原問題最優(yōu)解。第11頁，共39頁，2023年，2月20日，星期日試用兩階段法求解如下線性規(guī)劃問題解：先劃約束條件為標(biāo)準(zhǔn)型第12頁，共39頁，2023年，2月20日，星期日初等變換0-10000-W11010-2030021-4011011-21000-10-1010～40031-6-W11010-2030021-4011011-210-10-100010-Z’

x1

x2

x3

x4

x5

x6x7b第13頁，共39頁，2023年，2月20日，星期日

～～0-10000-W

11010-20

1-200100

12-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010進(jìn)行第二階段的計算將第一階段的人工變量列取消,并將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù),重新計算檢驗數(shù)行,可得如下第二階段的初始單純形表；應(yīng)用單純形算法求解得最終表。3-1-100

30-10-11

1000-12此時求解不是最優(yōu)，繼續(xù)迭代令x5=x6=x7=0，得最優(yōu)解X=(0,1,1,12,0)T，minW=0。因人工變量x6=x7=0,所以是原問題的基可行解。于是可以開始第二階段的計算。-Z’第14頁，共39頁，2023年，2月20日，星期日

～2-30001-Z’11010-201-20010012-110030-10-1-20010接上表-2-3-1/3000-Z’912/310001-2001004-11/30010-1/3-4/3-1-2/30010～σj<0，

x4=0,x5=0,x1=4,x2=1,x3=9,即X0=(4,1,9,0,0)T，此時最優(yōu)解–Z’=-2而maxZ’=2則minZ=-2第15頁，共39頁，2023年，2月20日，星期日（二）試用兩階段法求解MinZ=10x1+8x2+

7x32x1+x2≥6x1+x2+x3≥4x1,x2,x3≥0S.t.maxZ=－10x1

－

8x2－

7x3－M

x5

－M

x7

2x1+x2

－

x4+

x5

=6x1+x2+x3

－

x6+

x7=4x1,x2,x3,

x4,x5,x6,

x7≥

0第16頁，共39頁，2023年，2月20日，星期日（二）試用兩階段法求解～～00000-Z’4011106-10120

-1010-10-1

1

010-1

1

2

3-Z’4011106-10120001-1-100

1

01/2

1

1/2

0-Z’11/211/2003-1/201/210-3/2-1/21/2-1-100

1

01第一階段規(guī)劃求解第17頁，共39頁，2023年，2月20日，星期日

～0

00

0-Z11/211/2003-1/201/210-1-1/21/20-10-1

1

00～令x3=x4=x6=0得x1=2,x2=2,此解最優(yōu)

max-Z’=36σj<0-Z’-10-8-70-3/2

0

1/2

0

-Z’11/211/2003-1/201/2101/2-1/21/2-7-10-1

1

037～-2-1

0

0

-Z’2121002-11-10101/2-1/21/2-6-21-1

1

036從而得minZ=36σj<0第二階段規(guī)劃求解第一階段規(guī)劃最優(yōu)第18頁，共39頁，2023年，2月20日，星期日四、單純形法補遺進(jìn)基變量相持：單純形法運算過程中，同時出現(xiàn)多個相同的j最大。在符合要求的j(目標(biāo)為max：j＞0，min：j＜0)中，選取下標(biāo)最小的非基變量為換入變量；離基變量相持：單純形法運算過程中，同時出現(xiàn)多個相同的最小θ值。繼續(xù)迭代，便有基變量為0，稱這種情況為退化解。選取其中下標(biāo)最大的基變量做為換出變量。多重最優(yōu)解：最優(yōu)單純形表中，存在非基變量的檢驗數(shù)j=0。讓這個非基變量進(jìn)基，繼續(xù)迭代，得另一個最優(yōu)解。無界解：在大于0的檢驗數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk′≤0，則此問題是無界解。無可行解：最終表中存在人工變量是基變量。第19頁，共39頁，2023年，2月20日，星期日解的判別：情況1—無窮最優(yōu)解Cj比值CBXBb檢驗數(shù)j0x1x2x3x4x5x6240000221000120100X3X4X5X6000040001064-3Maxz=2x1+4x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1,x2,x3≥0標(biāo)準(zhǔn)化

Maxz=2x1+4x2+0x3+0x4+0x5+0x62x1+2x2+x3=12x1+2x2+x4=84x1+x5=164x2+x6=12x1,…,x6≥00400012400001281612第20頁，共39頁，2023年，2月20日，星期日迭代結(jié)果Cj比值CBXBb檢驗數(shù)j-36x1x2x3x4x5x6240000001-200.5

1

0

0

1

0-0.5X3X1X5X20204000-4124-432010000.25000-2002288j<0令x4=0，x6=0，得x1=2，x2=8，x3=2，x5=8即X0=(2,8,2,0,8,0)T此時Z＝2×2+4×8=36是最優(yōu)解第21頁，共39頁，2023年，2月20日，星期日再次迭代結(jié)果Cj比值CBXBb檢驗數(shù)j-36x1x2x3x4x5x6240000001-1-0.25

0

1

0000.25

0X3X1X6X20204000-20.5

1

0

100.5-0.125

0000-1.50

00447j<0令x4=0，x5=0，得x1=4，x2=7，x3=0，x6=4即X0=(4,7,0,0,0,4)T此時Z＝2×4+4×7=36也是最優(yōu)解結(jié)論：非基變量檢驗數(shù)有為0的，此線性規(guī)劃有無窮多個解兩最優(yōu)解對應(yīng)可行域兩頂點，兩點間連線上的點都是最優(yōu)解第22頁，共39頁，2023年，2月20日，星期日解的判別：情況2—解無界maxZ=

2x1+3x2+0x34x1+x3=16x1,x2,x3≥0Cj比值CBXBb檢驗數(shù)jx1x2x323016401230x30確定x2進(jìn)基，但x2所在列的系數(shù)為0，x2可以任意增大，解無界Maxz=2x1+3x2

4x1≤16x1,x2≥0說明此線性規(guī)劃解無界第23頁，共39頁，2023年，2月20日，星期日另例maxZ=

5x1+6x2+0x3–Mx4+0x52x1-x2-

x3+x4=2-2x1+3x2+x5=2x1,x2,x3,x4,x5≥0Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5560-M022-1-1102-23001X4X5-M0Maxz=5x1+6x2

2x1-x2≥2-2x1+3x2≤2x1,x2≥0560-M0檢驗數(shù)j5+2M6-M

-M0011-1/2-1/21/20402-11

1-5017/25/2-M+5/20第24頁，共39頁，2023年，2月20日，星期日另例Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5560-M0210-3/4

3/41/42

01-0.50.50.5X1X256560-M00

027/4-M+27/4-17/4確定x3進(jìn)基，但x3所在列的系數(shù)為負(fù)，此時解無界結(jié)論：入基變量系數(shù)均≤0的，該問題目標(biāo)函數(shù)無界第25頁，共39頁，2023年，2月20日，星期日解的判別：情況3—無解maxZ=

3x1+2x2-2x1+x2≥2x1-3x2≥3x1,x2≥0S.t.標(biāo)準(zhǔn)化

maxZ=

3x1+2x2-M

x5-M

x6-2x1+x2-x3+x5=2x1-3x2-x4+x6=3x1,x2,x3,x4≥0Cj比值CBXBb檢驗數(shù)j3200-M-Mx5x6-M-M此時檢驗數(shù)j<0，無進(jìn)基變量,但x5,x6還沒有替換出去。Z不能達(dá)到最優(yōu)說明此線性規(guī)劃無解x1x2x3x4x5x62-21-101

031-30-1013200-M-M檢驗數(shù)jx5x62-21-101031-30-1012M3-2M2+M-M00-M5M3-M2-2M-M-M0000結(jié)論：人工變量仍為基變量的，該問題無解第26頁，共39頁，2023年，2月20日，星期日圖示：無解maxZ=

3x1+2x2-2x1+x2≥

2

x1-3x2≥

3x1,x2≥0S.t.用圖示法x1x22462460說明此線性規(guī)劃無解第27頁，共39頁，2023年，2月20日，星期日五、單純形法的矩陣計算求解用矩陣描述的線性規(guī)劃的標(biāo)準(zhǔn)形式為：求解問題：B和B-1是什么？，待后討論第28頁，共39頁，2023年，2月20日，星期日單純形法小結(jié)1.根據(jù)實際問題給出數(shù)學(xué)模型，列出初始單純形表，進(jìn)行標(biāo)準(zhǔn)化第29頁，共39頁，2023年，2月20日，星期日

添加松馳變量、人工變量列出初始單純形表基變量中有非零的人工變量sk=max(sj)對所有aik>0計算qi=bi/aik令q=min(qi)所有sj≤0是否2.對目標(biāo)函數(shù)求max的線性規(guī)劃，用單純形法計算步驟如下計算非基變量各列的檢驗數(shù)sj否某非基變量檢驗數(shù)為零否唯一最優(yōu)解對任一sj≥0有Pj≤0是無界解無可行解是是無窮多最優(yōu)解是迭代運算第30頁，共39頁，2023年，2月20日，星期日六、用計算機(jī)軟件求解線性規(guī)劃問題關(guān)于線性規(guī)劃問題的求解，有許多好的專業(yè)軟件和商務(wù)軟件，通過計算機(jī)可十分方便地完成求解過程。其中簡便易行的求解軟件是Excel，下面介紹其使用方法。（1）建立Excsl工作表。用一組單元格表示變量，作為可變單元格（空）；用幾組單元格分別表示各約束條件和目標(biāo)函數(shù)的系數(shù)；用一些單元格輸入公式表示各組系數(shù)和變量的關(guān)系。（2）打開工具欄中的“規(guī)劃求解”對話框，指定存有目標(biāo)函數(shù)的單元格為目標(biāo)單元格，指定表示變量的單元格為可變單元格，建立約束條件。（3）在規(guī)劃求解對話框中按下“求解”按鈕，即可求出最優(yōu)解和最優(yōu)值。推出規(guī)劃求解對話框。第31頁，共39頁，2023年，2月20日，星期日利用EXCEL求線性規(guī)劃的步驟1、激活“工具欄”中的“規(guī)劃求解”第32頁，共39頁，2023年，2月20日，星期日利用EXCEL求線性規(guī)劃的步驟2、根據(jù)線性規(guī)劃模型建立計算模板

maxZ=3x1+5x2x1

≤8