1、單純形法求解2022/9/5第1頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二LP的基本定理定義 凸集（convex set），頂點(diǎn)（極點(diǎn)corner point ）定理1：線性規(guī)劃問題的可行域是凸集定理2：線性規(guī)劃問題的最優(yōu)解在極點(diǎn)上定理3：若LP問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。凸集凸集不是凸集極點(diǎn)第2頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二單純形表 基變量 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 a1nC

2、2 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 amn第3頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0（2）列（初始）單純形表引例用單純形法求解生產(chǎn)計(jì)劃問題。解： （1）化標(biāo)準(zhǔn)型第4頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0

3、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 24第5頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X

4、3 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 24第6頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30

5、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 24第7頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1

6、 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 24第8頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0

7、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 24第9頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二 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

8、1/2 1 50 X2 15/2 0 1 3/4 -1/4 0(3)本問題的最優(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.圖解分析見下。第10頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二0(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)從一個(gè)基可行解到另一個(gè)基可行解第11頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二單純形法基本步驟(1)、定初始基，初始基本可行解(3)、若有 k 0，Pk全 0，停， 沒有有限

9、最優(yōu)解； 否則轉(zhuǎn)(4)(2)、對應(yīng)于非基變量檢驗(yàn)數(shù) j全 0。 若是，停，得到最優(yōu)解； 若否，轉(zhuǎn)(3)。第12頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二= min aim+k 0 =biaim+kbrarm+k定Xr為換出變量，arm+k為主元。由最小比值法求：maxj = m+kXm+k 換入變量 j0(4)、第13頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二轉(zhuǎn)(2) m+k 0 a1m+k 0arm+k 1amm+k 0初等行變換Pm+k =(5)、以arm+k為中心，換基迭代第14頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二單純形法的進(jìn)一步討論（簡介

10、）(一)、大M法 the Big M Method 初始基本可行解的求法 - 加入人工變量 大M使人工變量 - 0第15頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二例：用大 M 法求解下列問題。maxZ= 6X1 +4X2 2X1 +3X2 1004X1 +2X2 120 X1 =14 X2 22X1 X2 0第16頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二解： （1）化標(biāo)準(zhǔn)型maxZ=6X1+4X22X1 +3X2 +X3 =1004X1 +2X2 +X4 =120 X1 =14 X2 - X5 = 22X1 X5 0第17頁，共28頁，2022年，5月20日，3點(diǎn)

11、18分，星期二（2）加人工變量X6，X7，問題化為maxZ=6X1+4X2-MX6 -MX72X1 +3X2 +X3 =1004X1 +2X2 +X4 =120 X1 +X6 =14 X2 - X5 +X7 = 22X1 X7 0（3）單純形求解判定無解條件：當(dāng)進(jìn)行到最優(yōu)表時(shí)，仍有人工變量在基中，且0，則說明原問題無可行解。第18頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二原問題 maxZ= Cj xj j=1nxj 0j=1naij xj =bi ( i=1,2, ,m)(二)、兩階段法 The Two-phase Method第19頁，共28頁，2022年，5月20日，3點(diǎn)18

12、分，星期二作輔助問題minW= yi i=1mXj ， yi 0j=1naij xj + yi =bi ( i=1,2, ,m)解題過程：第1階段：解輔助問題當(dāng)進(jìn)行到最優(yōu)表時(shí)，、若W=0, 則得到原問題的一個(gè)基本可行解，轉(zhuǎn)入第2階段。 、若W0, 則判定原問題無可行解。第20頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二第1階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個(gè)沒有人工變量的基礎(chǔ)可行解第2階段：以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解第21頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二兩階段法原理：(1)、輔助問題的基本可行解X(0) 為最優(yōu)解，對應(yīng)

13、最小值=0 則X(0) 的前n個(gè)分量是原問題的基本可行解。第22頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二小結(jié)與應(yīng)用舉例 小結(jié)應(yīng)用舉例第23頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二(1)、LP數(shù)學(xué)模型及標(biāo)準(zhǔn)型maxZ=CXAX=b (b0)X0(2)、LP問題解的性質(zhì)：圖解法分析小結(jié)第24頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二(3)、單純形法：1)、標(biāo)準(zhǔn)型中有單位基。2)、標(biāo)準(zhǔn)型中沒有單位基，用大M法加人工變量，使之構(gòu)成單位基。 求maxZ時(shí)，目標(biāo)中MXj 求minZ時(shí)，目標(biāo)中MXj3)、判定最優(yōu)解定理：maxZ問題，檢驗(yàn)數(shù) j 0minZ問題，檢驗(yàn)數(shù) j 0第25頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二4)、解的幾種情況：唯一解無窮多解 （多重解 ）無有限最優(yōu)解 （無界解）無可行解第26頁，共28頁，2022年，5月20日，3點(diǎn)18分，星期二多重解多個(gè)解都是最優(yōu)解，這些解在同一