運籌學05-單純形法.ppt

1、第五章 單純形法,5.1 線性規(guī)劃問題的基本解 5.2 單純形法 5.3 求初始基的人工變量法,5.1 線性規(guī)劃問題的基本解,(1) 解的基本概念,定義 在線性規(guī)劃問題中，約束方程組(2)的系數(shù)矩陣A(假定 )的任意一個 階的非奇異(可逆)的子方陣B(即 )，稱為線性規(guī)劃問題的一個基陣或基。,基陣,非基陣,基 向 量,非 基 向 量,基變量,非基變量,令,則,定義 在約束方程組(2) 中，對于一個選定的基B，令所有的非基變量為零得到的解，稱為相應于基B的基本解。,定義 在基本解中，若該基本解滿足非負約束，即 ，則稱此基本解為基本可行解，簡稱基可行解；對應的基B稱為可行基。,定義 在線性規(guī)劃問題

2、的一個基本可行解中，如果所有的基變量都取正值，則稱它為非退化解，如果所有的基本可行解都是非退化解。稱該問題為非退化的線性規(guī)劃問題；若基本可行解中，有基變量為零，則稱為退化解，該問題稱為退化的線性規(guī)劃問題。,基本解中最多有m個非零分量。,基本解的數(shù)目不超過 個。,例 現(xiàn)有線性規(guī)劃問題,試求其基本解、基本可行解并判斷是否為退化解。,解: (1)首先將原問題轉(zhuǎn)化為標準型 引入松弛變量x3和x4,(2) 求基本解 由上式得,可能的基陣,由于所有|B| 0，所以有6個基陣和6個基本解。,對于基陣,令,則,對于基陣,令,則,為基本可行解，B13為可行基,為基本可行解，B12為可行基,對于基陣,令,則,對于

3、基陣,令,則,對于基陣,令,則,對于基陣,令,則,為基本可行解，B24為可行基,為基本可行解，B34為可行基,0,A,B,C,D,E,所以，本問題存在6個基本解，其中4個為基可行解,無退化解.,例2 現(xiàn)有線性規(guī)劃問題,試求其基本解、基本可行解并判斷是否為退化解。,解: (1)首先將原問題轉(zhuǎn)化為標準型 引入松弛變量x3和x4,(2) 求基本解 由上式得,可能的基陣,由于所有|B| 0，所以有6個基陣和6個基本解。,對于基陣,令,則,對于基陣,令,則,為基本可行解，B12為可行基,為基本可行解，B13為可行基,為退化解,對于基陣,令,則,對于基陣,令,則,為基本可行解，B23為可行基,為退化解,對

4、于基陣,令,則,對于基陣,令,則,為基本可行解，B24為可行基,為基本可行解，B34為可行基,為退化解,0,A,B,C,(2) 解的基本性質(zhì),判別可行解為基可行解的準則,定理1 線性規(guī)劃問題的可行解是基可行解的充要條件是它的非零向量所對應的列向量線性無關(guān).,線性規(guī)劃問題的基本定理:定理2和定理3,定理2 線性規(guī)劃問題有可行解,則它必有基可行解.,定理3 若線性規(guī)劃問題有最優(yōu)解,則一定存在一個基可行解是它的最優(yōu)解.,定理2 線性規(guī)劃問題有可行解,則它必有基可行解.,證:設 為線性規(guī)劃問題的一個可行解. 若 ,則它是一個基可行解,定理成立; 若 ,則令 的前k個分量為非零分量：,若上述分量所對應的

5、列向量 線性無關(guān),則它是一個基可行解,定理成立; 若 線性相關(guān)，從 出發(fā)， 必可找到線性規(guī)劃問題的一個基可行解。,由于 線性相關(guān)，則存在一組不全為零的數(shù) ， 使得,假定,令,若,令,(若,令,),(*),由(*)可知,即,與 相比， 的非零分量減少1個，若對應的k-1個列向量線性無關(guān)，則即為基可行解；否則繼續(xù)上述步驟，直至剩下的非零變量對應的列向量線性無關(guān)。,幾點結(jié)論,若線性規(guī)劃問題有可行解,則可行域是一個凸多邊形或凸多面體(凸集),且僅有有限個頂點(極點); 線性規(guī)劃問題的每一個基可行解都對應于可行域上的一個頂點(極點); 若線性規(guī)劃問題有最優(yōu)解,則最優(yōu)解必可在基可行解(極點)上達到; 線性

6、規(guī)劃問題的基可行解(極點)的個數(shù)是有限的,不會超過 個.,上述結(jié)論說明: 線性規(guī)劃的最優(yōu)解可通過有限次運算在基可行解中獲得.,5.2 單純形法,基本思路和原理： 從可行域的某個頂點出發(fā)，判斷是否最優(yōu)。如不是，再找另一個使得目標函數(shù)值更優(yōu)的頂點（迭代）。再判斷是否最優(yōu)，直到找到一個頂點為其最優(yōu)解，或判斷出線性規(guī)劃問題無最優(yōu)解為止。 單純型法解題步驟： 1、找出一個初始基本可行解 2、最優(yōu)性檢驗 3、基變換,(1)單純形法的引入,5.2 單純形法,例1,(1)單純形法的引入,解：(1)、確定初始可行解,B = ( P3 P4 P5 ) = I,令X1 = X2 =0,X(1) =(0, 0, 30

7、, 60, 24)T Z(1) =0,(2)、判定解是否最優(yōu),Z=0+40X1+50X2 當 X1 從 0 或 X2 從 0 Z 從 0, X(1) 不是最優(yōu)解,(3)、由一個基可行解另一個基可行解。, 50 40 選 X2 從 0，X1 =0,X2 = min ( 30/2 , 60/2 , 24/2 ) =12 X2 ：進基變量， X5 ：出基變量。,B2=( P3 P4 P2 ), 1/2 ， 代入 式， ，,令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )T Z(2) = 600,(2) 判斷, 400 X(2)不是最優(yōu)解。,(3) 選X1從0， X5

8、=0,X1=min( 6/1 , 36/3 , 12 /0) =6 X1進基， X3出基。,B3 =(P1 P4 P2 ),令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)T Z(3) =840,(2) 150 X(3)不是,(3) 選X5從0， X3 =0,X5=min( 18/2 , 12/1/2 ) =9 X5進基， X4出基。,B4=(P1 P5 P2 ),令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975,0,(0,0),X2,X1,X(3),X(4),X(1),X(2),X(3),Z=40X1+50X2,(2) 線

9、性規(guī)劃的典則形式,標準型,上式稱為線性規(guī)劃問題對應于基B的典則形式，簡稱典式。 約束方程組的系數(shù)矩陣中含有一個單位矩陣，并以其為基； 目標函數(shù)中不含基變量，只有非基變量。,檢 驗 數(shù),(3) 最優(yōu)性判別定理,在線性規(guī)劃問題的典式中，設 X(0)=(x1,x2,xm,0,0) 為對應于基B 的一個基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 則X(0)是線性規(guī)劃問題的最優(yōu)解，基B為最優(yōu)基。,證：設X為線性規(guī)劃問題的一個可行解，必有 X 0 ，當 j 0， 則 X 0 Z*=CX(0) = Z(0) Z(0) + X =CX 故X(0)為線性規(guī)劃問題的最優(yōu)解。,在線性規(guī)劃

10、問題的典式中，設 X(0)=(x1,x2,xm,0,0) 為對應于基B 的一個基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 且 j+k = 0 則線性規(guī)劃問題有無窮多個最優(yōu)解。,無窮多最優(yōu)解判別定理,在線性規(guī)劃問題的典式中，設X(0) 為對應于基B 的一個基可行解，若某一非基變量xj+k的檢驗數(shù) j+k 0 且對應的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k) 0 則線性規(guī)劃問題具有無界解。,無界解判別定理,(4) 基可行解改進定理,在線性規(guī)劃問題的典式中，設 X(0)=(x1,x2,xm,0,0) 為對應于基B 的一個基可行解，若滿足以下條件： 某

11、個非基變量的檢驗數(shù) k 0 ( m+1 k n ); aik ( i = 1,2,m )不全小于或等于零，即至少有一個 aik 0 ( 1 k m ); bi 0( I = 1 , 2,m ),即X(0)為非退化的基可行解。 則從X(0)出發(fā)，一定能找到一個新的基可行解X(1)，使得 CX(1) CX(0) 。,(5) 單純形表,將線性規(guī)劃問題典式中的數(shù)據(jù)按一定規(guī)則列入表中，該表即為單純形表。,(1)、確定初始基域初始基本可行解,列出初始單純形表,(3)、若有j 0，Pj 全 0，停止， 沒有有限最優(yōu)解； 否則轉(zhuǎn) (4),(2)、對應于非基變量檢驗數(shù)j全小于零。 若是，停止，得到最優(yōu)解； 若否

12、，轉(zhuǎn)(3)。,(6) 單純形單純形法的迭代步驟,定Xr為出基變量，arm+k為主元。,由最小比值法求：,Max j = m+kXm+k 進基變量,j 0,(4)、,轉(zhuǎn)(2),(5)、以arm+k為中心，換基迭代,從步驟(2)-(5)的每一個循環(huán)，稱為一次單純形迭代。,例1、Max Z=40X1+ 50X2,X1+2X2 30 3X1+2X2 60 2X2 24 X1 , X2 0,s.t,X1+2X2 +X3 = 30 3X1+2X2 +X4 =60 2X2 +X5 = 24 X1 X5 0,s.t,例1、Max Z=40X1+ 80X2,X1+2X2 30 3X1+2X2 60 2X2 24

13、 X1 , X2 0,s.t,X1+2X2 +X3 = 30 3X1+2X2 +X4 =60 2X2 +X5 = 24 X1 X5 0,s.t,5.3 求初始基的人工變量法,求解線性規(guī)劃問題的單純形法第一步就是要找到一個初始可行基并求出初始基可行解，以它作為迭代的起點。 獲得初始可行基及初始基可行解的途徑主要有： (1) 試算法； (2) 人工變量法。 在約束方程組中的每一個沒有單位向量的約束方程中人為加入一個變量，使系數(shù)矩陣中湊成一個單位方陣，以形成一個初始可行基陣。,約束條件： a11x1 + a12x2 + + a1nxn +xn+1= b1 a21x1 + a22x2 + + a2nx

14、n +xn+2 = b2 . . . am1x1 + am2x2 + + amnxn +xn+m = bm x1 ，x2 ， ，xn , xn+1 , , xn+m 0,s.t,人工變量,人工基,等價否？,大M法,兩階段法,(1) 大M法,例3、 Max Z=2X1+ 4X2,2X1+X2 8 -2X1+X2 2 X1 , X2 0,s.t,2X1+X2-X3 =8 -2X1+X2 +X4= 2 X1 X4 0,s.t,Max Z=2X1+ 4X2 MX5,2X1+X2-X3 +X5 =8 -2X1+X2 +X4= 2 X1 X5 0,s.t,例4、 Max Z=3X1+2X2,-X1 -X2 1 X1 , X2 0,s.t,-X1 -X2 X3 =1 X1 , X2 0,s.t,Max Z=3X1+2X2 MX4,-X1 -X2 X3 +X4 =1 X1 X4 0,s.t,(2) 兩階段法,例3、 Max Z=2X1+ 4X2,2X1+X2 8 -2X1+X2 2 X1 , X2 0,s.t