單純形法求解

1、線性規(guī)劃的基本概念可行解 feasible solution 最優(yōu)解 optimal solution 基 basic matrix (the basis)基解 basic solution 基可行解 basic feasible (BF) solution可行基 feasible basic matrix可行域 feasible region2022/9/51LP的基本定理定義 凸集（convex set），頂點(diǎn)（極點(diǎn)corner point ）定理1：線性規(guī)劃問(wèn)題的可行域是凸集定理2：線性規(guī)劃問(wèn)題的最優(yōu)解在極點(diǎn)上定理3：若LP問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。凸集凸集不是凸集極點(diǎn)

2、2022/9/52單純形表 基變量 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+k XnCB XB -Z0 0 0 0 m+1 m+k nC1 X1 b1 1 0 0 a1m+1 a1m+k a1nC2 X2 b2 0 1 0 a2m+1 a2m+k a2nCr Xr br 0 0 0 arm+1 arm+k arnCm Xm bm 0 0 1 amm+1 amm+k amn2022/9/53maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0（2）列（初始）單純形表引例用單純

3、形法求解生產(chǎn)計(jì)劃問(wèn)題。解： （1）化標(biāo)準(zhǔn)型2022/9/54 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0 0 150 X4 60 3 2 0 1 0 300 X5 24 0 2 0 0 1 12 XB 600 40 0 0 0 -250 X3 6 1 0 1 0 -1 60 X4 36 3 0 0 1 -1 1250 X2 12 0 1 0 0 1/2 840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 2 950 X2 12 0 1 0 0 1/2 242022/

4、9/55 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0 0 150 X4 60 3 2 0 1 0 300 X5 24 0 2 0 0 1 12 XB 600 40 0 0 0 -250 X3 6 1 0 1 0 -1 60 X4 36 3 0 0 1 -1 1250 X2 12 0 1 0 0 1/2 840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 2 950 X2 12 0 1 0 0 1/2 242022/9/56 40 50 0 0 0 X1 X2 X3

5、X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0 0 150 X4 60 3 2 0 1 0 300 X5 24 0 2 0 0 1 12 XB 600 40 0 0 0 -250 X3 6 1 0 1 0 -1 60 X4 36 3 0 0 1 -1 1250 X2 12 0 1 0 0 1/2 840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 2 950 X2 12 0 1 0 0 1/2 242022/9/57 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0

6、 X3 30 1 2 1 0 0 150 X4 60 3 2 0 1 0 300 X5 24 0 2 0 0 1 12 XB -600 40 0 0 0 -250 X3 6 1 0 1 0 -1 60 X4 36 3 0 0 1 -1 1250 X2 12 0 1 0 0 1/2 -840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 2 950 X2 12 0 1 0 0 1/2 242022/9/58 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0 0 150 X4

7、60 3 2 0 1 0 300 X5 24 0 2 0 0 1 12 XB -600 40 0 0 0 -250 X3 6 1 0 1 0 -1 60 X4 36 3 0 0 1 -1 1250 X2 12 0 1 0 0 1/2 -840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 2 950 X2 12 0 1 0 0 1/2 242022/9/59 XB -975 0 0 -35/2 -15/2 040 X1 15 1 0 -1/2 1/2 0 0 X5 9 0 0 -3/2 1/2 1 50 X2 15/2 0 1 3/4 -1/4

8、0(3)本問(wèn)題的最優(yōu)解 X =(X1, X2, X3, X4, X5)T = (15, 15/2, 0, 0, 9)T且Z=975. X3 , X4 =0表示資源1 ，2用完, X5 =9表示資源3剩余9.圖解分析見(jiàn)下。2022/9/5100(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)從一個(gè)基可行解到另一個(gè)基可行解2022/9/511單純形法基本步驟(1)、定初始基，初始基本可行解(3)、若有 k 0，Pk全 0，停， 沒(méi)有有限最優(yōu)解； 否則轉(zhuǎn)(4)(2)、對(duì)應(yīng)于非基變量檢驗(yàn)數(shù) j全 0。 若是，停，得到最優(yōu)解； 若否，轉(zhuǎn)(3)。2022/9/512= min aim+

9、k 0 =biaim+kbrarm+k定Xr為換出變量，arm+k為主元。由最小比值法求：maxj = m+kXm+k 換入變量 j0(4)、2022/9/513轉(zhuǎn)(2) m+k 0 a1m+k 0arm+k 1amm+k 0初等行變換Pm+k =(5)、以arm+k為中心，換基迭代2022/9/514單純形法的進(jìn)一步討論（簡(jiǎn)介）(一)、大M法 the Big M Method 初始基本可行解的求法 - 加入人工變量 大M使人工變量 - 02022/9/515例：用大 M 法求解下列問(wèn)題。maxZ= 6X1 +4X2 2X1 +3X2 1004X1 +2X2 120 X1 =14 X2 22X

10、1 X2 02022/9/516解： （1）化標(biāo)準(zhǔn)型maxZ=6X1+4X22X1 +3X2 +X3 =1004X1 +2X2 +X4 =120 X1 =14 X2 - X5 = 22X1 X5 02022/9/517（2）加人工變量X6，X7，問(wèn)題化為maxZ=6X1+4X2-MX6 -MX72X1 +3X2 +X3 =1004X1 +2X2 +X4 =120 X1 +X6 =14 X2 - X5 +X7 = 22X1 X7 0（3）單純形求解判定無(wú)解條件：當(dāng)進(jìn)行到最優(yōu)表時(shí)，仍有人工變量在基中，且0，則說(shuō)明原問(wèn)題無(wú)可行解。2022/9/518原問(wèn)題 maxZ= Cj xj j=1nxj 0j

11、=1naij xj =bi ( i=1,2, ,m)(二)、兩階段法 The Two-phase Method2022/9/519作輔助問(wèn)題minW= yi i=1mXj ， yi 0j=1naij xj + yi =bi ( i=1,2, ,m)解題過(guò)程：第1階段：解輔助問(wèn)題當(dāng)進(jìn)行到最優(yōu)表時(shí)，、若W=0, 則得到原問(wèn)題的一個(gè)基本可行解，轉(zhuǎn)入第2階段。 、若W0, 則判定原問(wèn)題無(wú)可行解。2022/9/520第1階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個(gè)沒(méi)有人工變量的基礎(chǔ)可行解第2階段：以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解2022/9/521兩階段法原理：(1)、輔助問(wèn)題

12、的基本可行解X(0) 為最優(yōu)解，對(duì)應(yīng)最小值=0 則X(0) 的前n個(gè)分量是原問(wèn)題的基本可行解。2022/9/522小結(jié)與應(yīng)用舉例 小結(jié)應(yīng)用舉例2022/9/523(1)、LP數(shù)學(xué)模型及標(biāo)準(zhǔn)型maxZ=CXAX=b (b0)X0(2)、LP問(wèn)題解的性質(zhì)：圖解法分析小結(jié)2022/9/524(3)、單純形法：1)、標(biāo)準(zhǔn)型中有單位基。2)、標(biāo)準(zhǔn)型中沒(méi)有單位基，用大M法加人工變量，使之構(gòu)成單位基。 求maxZ時(shí)，目標(biāo)中MXj 求minZ時(shí)，目標(biāo)中MXj3)、判定最優(yōu)解定理：maxZ問(wèn)題，檢驗(yàn)數(shù) j 0minZ問(wèn)題，檢驗(yàn)數(shù) j 02022/9/5254)、解的幾種情況：唯一解無(wú)窮多解 （多重解 ）無(wú)有限最優(yōu)解 （無(wú)界解）無(wú)可行解2022/9/