單純行法-截止至理論部分

1、單 純 行 法線性規(guī)劃問題的解求解方法一 般 有兩種方法圖 解 法單純形法兩個(gè)變量、直角坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式提綱基本概念單純行法表格單純行法人工變量問題提綱基本概念單純行法表格單純行法人工變量問題例1（仍然使用圖解法的例題）首先檢驗(yàn)是否為標(biāo)準(zhǔn)形式！ max Z= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 x1x2x3x4x5單位矩陣max Z= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x

2、2 0基本概念 A是約束方程組的mn維系數(shù)矩陣，mn，其rank(A) = m；B是矩陣A中m階非奇異子矩陣，則稱B是線性規(guī)劃問題的一個(gè)基。B=(P1, P2, Pm)，其列向量Pj稱為基B的基向量。與基向量Pj相對(duì)應(yīng)的變量xj就成為基變量，其余的就成為非基變量。約束條件數(shù)遠(yuǎn)少于決策變量數(shù)！例1（仍然使用圖解法的例題）首先檢驗(yàn)是否為標(biāo)準(zhǔn)形式！ max Z= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 x1x2x3x4x5單位矩陣基變量x3，x4， x5，非

3、基變量是x1，x2的基最多有Cnm=C53=10 x3x4x5x1x4x5x2x4x5x3x1x5x3x2x5x3x4x1x3x4x2x1x2x5x1x2x4x1x2x5問題：是否所有33的子矩陣都是基？例題的演示基 可 行 解 定 義x3x4x5基變量x3，x4， x5，非基變量是x1，x2令非基變量x1=x2=0，得到一個(gè)基解 x3=8，x4=12， x5=36。此時(shí)得到一個(gè)基可行解，B為可行基。基 可 行 解 定 義可行解基解基可行解提綱基本概念單純行法表格單純行法人工變量問題基本定理定理1. 若可行域有界，線性規(guī)劃的最優(yōu)解一定可以在可行域的頂點(diǎn)上達(dá)到。 定理2. 線性規(guī)劃問題的基可行解

4、對(duì)應(yīng)可行域的頂點(diǎn)。線性規(guī)劃的基本定理 從可行域的某個(gè)頂點(diǎn)出發(fā)，即找到一個(gè)基可行解，拿目標(biāo)函數(shù)做尺度衡量一下看是否最優(yōu)。如若不是，則向鄰近的頂點(diǎn)轉(zhuǎn)移，即換一個(gè)基求解、檢驗(yàn)，如此迭代，目標(biāo)值逐步改善，直至求得最優(yōu)解。 線性規(guī)劃的解題思路 用單純行法求解最優(yōu)解的步驟Step1：確定基變量，非基變量；Step2：用非基變量表示基變量和目標(biāo)函數(shù)；Step3：求得基可行解，判斷是否為最優(yōu)解，是則停止，不是則轉(zhuǎn)Step1。 max Z=3x1 +5 x2 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 x1, x2 , x3 , x4 , x5 0 x1x2x3x4x5x

5、3x4x5非奇異子陣，做為一個(gè)基基變量：x3, x4, x5非基變量：x1, x2單純形法原理用非基變量線性表示基變量，即x3= 8 - x1 x4 =12 - 2x2 x5=36 -3x1-4 x2 用非基變量線性表示目標(biāo)函數(shù)：Z=3x1 +5x2 令非基變量x1=0，x2=0，找到一個(gè)初始基可行解： x1=0， x2 =0，x3 =8，x4 =12，x5 =36即X0=(0,0,8,12,36) T，Z=3x1 +5x2=0。從目標(biāo)函數(shù)Z=3x1 +5x2可知：非基變量x1和x2的系數(shù)(檢驗(yàn)數(shù))均為正數(shù)，增大x1，x2或都會(huì)增大目標(biāo)函數(shù)。1. 求初始基可行解 單純形法原理確定進(jìn)基變量因?yàn)閤

6、2的系數(shù)5（檢驗(yàn)數(shù)）大于x1的系數(shù)3（檢驗(yàn)數(shù)），即每增加一個(gè)單位x2，目標(biāo)函數(shù)增加得多，因此x2被選為進(jìn)基變量。2. 第一次迭代 單純形法原理確定離基變量x3 =8 x1 x4 =12- 2x2 x5=36 -3x1-4 x2保持原非基變量x1 =0 x2變成基變量時(shí)應(yīng)保證 x3 , x4, x5非負(fù)，即2. 第一次迭代（續(xù)） x3 =8 0 x4 =12- 2x2 0 x5=36 -4 x2 0 x2 12/2x2 36/4 單純形法原理2. 第一次迭代（續(xù)）用非基變量x1、 x4線性表示基變量x2、x3、x5用非基變量x1、 x4表示目標(biāo)函數(shù) max Z=3x1 +5 x2 x1 + x3

7、 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 x1, x2 , x3 , x4 , x5 0單純形法原理2. 第一次迭代（續(xù)）主行主列主元 x1 +0 x2 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 -Z+3x1 +5x2 +0 x3 +0 x4+0 x5 =0進(jìn)基變量所在列為主列，確定離基變量所在的行為主行單純形法原理進(jìn)行初等變換，變主元為1，主列為單位列向量。2. 第一次迭代（續(xù)） x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5

8、 =-30 x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +5 x2 +0 x3 +0 x4 +0 x5 =0 x1 +0 x2 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 x2 +1/2 x4 =6 3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4 +0 x5 =0單純形法原理2. 第一次迭代（續(xù)）用非基變量x1、 x4表示基變量x2、x3、x5，即x3=8 x1 x2=6- 1

9、/2x4 x5=12 -3x1+4 x4用非基變量x1、 x4表示目標(biāo)函數(shù)Z=3x15/2x4 +30令非基變量x1=0，x4=0，找到另一個(gè)基可行解 x1=0， x2 =6，x3 =8，x4 =0， x5 =12即X1=(0, 6, 8, 0, 12) T目標(biāo)函數(shù)Z=3x15/2x4 + 30=30單純形法原理確定進(jìn)基變量3. 第二次迭代 目標(biāo)函數(shù)Z=3x1 5/2x4 +30 =30，非基變量x1的檢驗(yàn)數(shù)為正數(shù)，確定x1為進(jìn)基變量。單純形法原理確定離基變量3. 第二次迭代 （續(xù)） x3 =8- x1 0 x2 =6 0 x5=12 -3x10 x1 8/1x1 12/3 上一次迭代后，基變

10、量x2、x3、x5用非基變量x1 、x4表示 x3=8 x1 x2=6- 1/2x4 x5=12 -3x1+4 x4保持原非基變量x4 =0，x1變成基變量時(shí)應(yīng)保證 x2 , x3, x5非負(fù)，即 單純形法原理用非基變量x4,x5線性表示基變量x1,x2,x3進(jìn)基變量所在列為主列，確定離基變量所在的行為主行變主元為1，主列為單位列向量3. 第二次迭代（續(xù)） x1 + x3 =8 x2 +1/2 x4 =6 x1 + -2/3 x4 + 1/3x5=4 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30 x3 +2/3 x4 -1/3x5 =4 x2 +1/2 x4 =6 x

11、1 + -2/3 x4 + 1/3x5=4 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30 x3 +2/3 x4 -1/3x5 =4 x2 +1/2 x4 =6 x1 + -2/3 x4 +1/3x5=4 -Z+0 x1 +0 x2 +0 x3 -1/2x4 - x5 =-42 1 x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30單純形法原理3. 第二次迭代（續(xù)）用非基變量x4,x5表示基變量x1,x2,x3，即x3 =4 2/3x4 +1/3x5x2=6- 1/4x4 x1=4 +2/3x4-1/3 x5 令非基變量x4=0，x5=0，又找到一個(gè)基可行解 目標(biāo)函數(shù)中非基變量檢驗(yàn)數(shù)均非正，得最優(yōu)解X*=(4,6,4,0,0)T，Z*=42 x1=4， x2 =6，x3 =4，x4 =0， x5 =0即 X2=(4,6,4,0,0)T Z=42 用非基變量x4,x5表示目標(biāo)函數(shù)Z= -1/2x4 -x5 +42單純形法的幾