1-4線性規(guī)劃-單純形進(jìn)一步討論〔2〕三、無初始可行基求最優(yōu)解人工變量法大M法兩階段法大M法大M法是一種懲罰方法，它是處理人工變量的一種簡便方法。在通過人工變量構(gòu)造初始根本變量以后，假定人工變量在目標(biāo)函數(shù)中的系數(shù)為M〔M為任意大的正數(shù)〕作為對基變量中存在人工變量的懲罰，迫使人工變量成為非基變量，即取值為零。原問題才能到達(dá)最優(yōu)。例1-16用大M法求以下問題minz=-3x1+x2+x3s.t.X1-2x2+x311-4x1+x2+2x33-2x1+x3=1

x1,x2,x30解：將問題化成標(biāo)準(zhǔn)形式maxS=3x1-x2-x3-Mx6-Mx7s.t.X1-2x2+x3+x4=11-4x1+x2+2x3–x5+x6=3-2x1+x3+x7=1

x1,x2,

x3,

x4,

x5,x6,

x70M是任意大的正數(shù)初始根本可行解：X〔0〕=〔0，0，0，11，0，3，1〕tC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-21100011-MX6-4120-1103-MX7-20100011

-4MB1=〔P4，P6，P7〕=IC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-21100011-MX6-4120-1103-MX7-20100011

-4M檢驗數(shù)3=3M-1>0,X3為進(jìn)基變量C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-21100011-MX6-4120-1103-MX7-201000113-6MM-13M-10-M00-4M計算最小比值：X7為出基變量，主元為〔1〕C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-2110001111-MX6-4120-11033/2-MX7-20(1)0001113-6MM-13M-10-M00-4M第一行加上第三行的〔-1〕倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110

-MX6-4120-1103

-1X3-20(1)00011

第二行加上第三行的〔-2〕倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110

-MX60100-11-21

-1X3-20(1)00011

得到新的根本可行解：X〔1〕=〔0，0，1，10，0，1，0〕tC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110

-MX60100-11-21

-1X3-20(1)00011

-M-1計算檢驗數(shù)C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110--MX60(1)00-11-211

-1X3-20(1)00011-1M-100-M01-3M-M-1第一行加第二行2倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43001-22-512

-1X20100-11-21

-1X3-20100011

得到新的根本可行解：X〔2〕=〔0，1，1，12，0，0，0〕tC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43001-22-512

-1X20100-11-21

-1X3-20100011

1000-11-M-M-1-2C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X4(3)001-22-5124

-1X20100-11-21-

-1X3-20100011-1000-11-M-M-1-2C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X1(3)001-22-512

-1X20100-11-21

-1X3-20100011

1000-11-M-M-1-2第一行乘1/3C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X1(1)001/3-2/32/3-5/34

-1X20100-11-21

-1X3-20100011

1000-11-M-M-1-2第一行乘1/3C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X1(1)001/3-2/32/3-5/34

-1X20100-11-21

-1X30012/3-4/34/3-7/39

第三行加第一行2倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X11001/3-2/32/3-5/34

-1X20100-11-21

-1X30012/3-4/34/3-7/39

000-1/3-1/31/3-M2/3-M2得到新的根本可行解：X〔3〕=〔4，1，9，0，0，0，0〕t最優(yōu)值S=2Z=-2例1-17用大M法求以下問題maxS=6x1+4x2s.t.2x1+3x21004x1+2x2120x1=14x222x1,x20解：將問題化成標(biāo)準(zhǔn)形式maxS=6x1+

4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1=14x2-x5=22x1,x2,

x3,x4，x50解：引入人工變量,x60，x70maxS=6x1+4x2-Mx6-Mx7s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1+x6=14x2-x5+x7=22x1,x2,x3,x4,x5,x6,x70B1=〔P3，P4，P6，P7〕=I初始根本可行解：X〔0〕=〔0，0，100，120，0，14，22〕tC64000-M-MCBXBX1X2X3X4X5X6X7b0X323100001000X44201000120-MX6100001014-MX70100-10122

-36MB1=〔P3，P4，P6，P7〕=IC64000-M-MCBXBX1X2X3X4X5X6X7b0X32310000100

0X44201000120

-MX6100001014

-MX70100-10122

檢驗數(shù)1=6+M>0,X1為進(jìn)基變量C64000-M-MCBXBX1X2X3X4X5X6X7b0X32310000100

0X44201000120

-MX6(1)00001014

-MX70100-10122

6+M4+M00-M00-36M計算最小比值：X6為出基變量，主元為〔1〕C64000-M-MCBXBX1X2X3X4X5X6X7b0X32310000100500X4420100012030-MX6(1)0000101414-MX70100-10122-6+M4+M00-M00-36M第一行加上第三行的〔-2〕倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072

0X44201000120

6X1(1)00001014

-MX70100-10122

-36M第二行加上第三行的〔-4〕倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072

0X402010-4064

6X1100001014

-MX70100-10122

得到新的根本可行解：X〔1〕=〔14，0，72，64，0，0，22〕tC64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072

0X402010-4064

6X1100001014

-MX70100-10122

X2的檢驗數(shù)大于零，X2進(jìn)基變量X7為最小比值，X7為出基變量，主元〔1〕C64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072240X402010-4064326X1100001014--MX70(1)00-1012222

0

4+M00-M-M-60第一行加上第四行的〔-3〕倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X300103-2-36

0X402010-4064

6X1100001014

4X20(1)00-10122

第二行加上第四行的〔-2〕倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X300103-2-36

0X400012-4-220

6X1100001014

4X20100-10122

172主元運算，得到新的根本可行解：X〔2〕=〔14，22，6，20，0，0，0〕tC64000-M-MCBXBX1X2X3X4X5X6X7b0X300103-2-36

0X400012-4-220

6X1100001014

4X20100-10122

172X5的檢驗數(shù)大于零，X5進(jìn)基變量X3為最小比值，X3為出基變量，主元〔3〕C64000-M-MCBXBX1X2X3X4X5X6X7b0X30010(3)-2-3620X400012-4-220106X1100001014-4X20100-10122-0

0004-M-6-M-4172第一行除以3C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12

0X400012-4-220

6X1100001014

4X20100-10122

第二行加上第一行的〔-2〕倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12

0X400-2/310-8/3016

6X1100001014

4X20100-10122

第四行加上第一行C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12

0X400-2/310-8/3016

6X1100001014

4X2011/300-2/3024

180

主元運算，得到新的根本可行解：X〔3〕=〔14，24，0，16，2，0，0〕t為最優(yōu)解，最優(yōu)值S=180C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12

0X400-2/310-8/3016

6X1100001014

4X2011/300-2/3024

0

0-4/300-10/3-M-M180例1-18用大M法求以下問題maxS=x1+x2s.t.x1-x203x1-x2-3x1,x20解：將問題化成標(biāo)準(zhǔn)形式maxS=x1+x2s.t.-x1+x2+x3=0-3x1-x2-x4=3x1,x2,

x3,

x4

0解：引入人工變量,x50maxS=x1+x2-Mx5s.t.-x1+x2+x3=0-3x1+x2-x4+x5=3x1,x2,x3,x4,x50B1=〔P3，P5〕=IB1=〔P3，P5〕=IX〔0〕=〔0，0，0，0，3〕t計算檢驗數(shù)：計算檢驗數(shù)：最大的為X2，進(jìn)基變量計算最小比值為X3，出基變量主元〔1〕第二行加上第一行的〔-1〕倍主元運算：得到根底可行解X〔1〕=〔0，0，0，0，3〕t計算檢驗數(shù)全小于零，但X〔1〕=〔0，0，0，0，3〕t人工變量不等于零，原問題無可行解。兩階段法第一階段：引進(jìn)人工變量，構(gòu)造輔助問題用單純形法求解，得到原問題的可行基。兩階段法第一階段：引進(jìn)人工變量，構(gòu)造輔助問題用單純形法求解，得到原問題的可行基。第二階段：在第一階段得到可行基對應(yīng)的單純形表上，去掉人工變量所在的行和列，再用單純形求解，得到原問題的最優(yōu)解，或無最優(yōu)解。例1-19用兩階段法求以下數(shù)學(xué)模型minz=-3x1+x2+x3s.t.x1-2x2+x311-4x1+x2+2x33-2x1+x3=1x1,x2,x30問題的數(shù)學(xué)模型標(biāo)準(zhǔn)型

maxz=3x1-x2-x3s.t.x1-2x2+x3+x4=11-4x1+x2+2x3–x5+x6=3-2x1+x3+x7=1xj

0第一階段：構(gòu)造輔助線性規(guī)劃問題

max=

-x6–x7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3–x5+x6=3-2x1+x3+x7=1xj

0x6,

x7是人工變量。最大檢驗數(shù)X3進(jìn)基變量

計算最小比值X7出基變量

主元為〔1〕C00000-1-1CBXBX1X2X3X4X5X6X7b0X41-2110001111

-1X6-4120-11033/2-1X7-20(1)000111

-6

130-100-4第一行加上第三行的〔-1〕倍C00000-1-1CBXBX1X2X3X4X5X6X7b0X43-20100-110

-1X6-4120-1103

0X3-20(1)00011

第二行加上第三行的〔-2〕倍C00000-1-1CBXBX1X2X3X4X5X6X7b0X43-20100-110

-1X60100-11-21

0X3-20(1)00011

C00000-1-1CBXBX1X2X3X4X5X6X7b0X43-20100-110--1X60(1)00-11-211

0X3-20100011-

0

100-10-3-1計算檢驗數(shù)，確定進(jìn)基變量X2，出基變量X6，主元〔1〕C00000-1-1CBXBX1X2X3X4X5X6X7b0X43-20100-110--1X60(1)00-11-211

0X3-20100011-

0

100-10-3-1第一行加上第二行的2倍C00000-1-1CBXBX1X2X3X4X5X6X7b0X43001-22-512

0X20100-11-21

0X3-20100011

0第一階段求得最優(yōu)解=0X*=〔0，1，1，12，0，0，0〕是原問題的根底可行解。C00000-1-1bCBXBX1X2X3X4X5X6X70X43001-22-512

0X20100-11-21

0X3-20100011

0

0000-1-10第二階段：第一階段最優(yōu)表中去掉人工變量所在的行和列，目標(biāo)函數(shù)的系數(shù)填入原問題的系數(shù)，繼續(xù)求解。C3-1-100

bCBXBX1X2X3X4X5X6X70X43001-2

12

-1X20100-1

1

-1X3-20100

1

X1為進(jìn)基變量，X4出基變量，主元〔3〕C3-1-100

bCBXBX1X2X3X4X5X6X70X4(3)001-2

124

-1X20100-1

1-

-1X3-20100

1-1000-1

-2第一行乘以〔1/3〕C3-1-100

bCBXBX1X2X3X4X5X6X73X1(1)001/3-2/3

4

-1X20100-1

1

-1X3-20100

1

-2第三行加上第一行的〔2〕倍C3-1-100

bCBXBX1X2X3X4X5X6X73X11001/3-2/3

4

-1X20100-1

1

-1X30012/3-4/3

9

2計算檢驗數(shù)全部小于零，最優(yōu)解X*=〔4，1，9，0，0，0，0〕C3-1-100

bCBXBX1X2X3X4X5X6X73X11001/3-2/3

4

-1X20100-1

1

-1X30012/3-4/3

9

000-1/3-1/3

2檢驗數(shù)全為非正，得到原問題最優(yōu)解：X*=〔4，1，9，0，0〕t最優(yōu)值minz=-2例1-20用兩階段法求以下數(shù)學(xué)模型的解minS=2x1+8x2s.t.5x1+10x2=150x120x214x1,x20問題的數(shù)學(xué)模型標(biāo)準(zhǔn)型

maxS’=-2x1-8x2s.t.5x1+10x2=150x1+x3=20x2-x4=14x1,x2,

x3,x40第一階段：構(gòu)造輔助線性規(guī)劃問題

max=

-x5–x6s.t.5x1+10x2+

x5=150x1+x3=20x2-x4+

x6=14x1,

x2,

x3,

x4,

x5,

x60x5,

x6是人工變量。C0000-1-1bCBXBX1X2X3X4X5X6-1X55100010150

0X310100020

-1X6010-10114

最大檢驗數(shù)X2，進(jìn)基變量

計算最小比值X6出基變量

主元為〔1〕

C0000-1-1bCBXBX1X2X3X4X5X6-1X5510001015015

0X310100020-

-1X6010-10114145110-100-164第一行減去第三行的10倍C0000-1-1bCBXBX1X2X3X4X5X6-1X5500101-10100X3101000200X2010-10114-10計算檢驗數(shù)C0000-1-1bCBXBX1X2X3X4X5X6-1X5500101-10100X3101000200X2010-10114500100-11-10C0000-1-1bCBXBX1X2X3X4X5X6-1X5500101-101010X310100020-0X2010-10114-500100-11-10C0000-1-1bCBXBX1X2X3X4X5X6-1X51/20011/10-110X3101000200X2010-10114第一行除以10C0000-1-1bCBXBX1X2X3X4X5X60X41/20011/10-110X3101000200X21/21001/100150第三行加第一行此時Z=0〔0，15，20，1，0，0〕是原問題的可行解。C0000-1-1bCBXBX1X2X3X4X5X60X41/20011/10-110X3101000200X21/21001/100150第二階段：去掉人工變量所在的行和列，繼續(xù)求解。C-2-800bCBXBX1X2X3X4X5X60X4

1/2

001120X310102020-8X21/210015302000-120第一行乘2