運(yùn)籌學(xué)05-單純形法.ppt

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

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

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

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

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

6、規(guī)劃問(wèn)題的基可行解(極點(diǎn))的個(gè)數(shù)是有限的,不會(huì)超過(guò) 個(gè).,上述結(jié)論說(shuō)明: 線性規(guī)劃的最優(yōu)解可通過(guò)有限次運(yùn)算在基可行解中獲得.,5.2 單純形法,基本思路和原理： 從可行域的某個(gè)頂點(diǎn)出發(fā)，判斷是否最優(yōu)。如不是，再找另一個(gè)使得目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)（迭代）。再判斷是否最優(yōu)，直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，或判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。 單純型法解題步驟： 1、找出一個(gè)初始基本可行解 2、最優(yōu)性檢驗(yàn) 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 當(dāng) X1 從 0 或 X2 從 0 Z 從 0, X(1) 不是最優(yōu)解,(3)、由一個(gè)基可行解另一個(gè)基可行解。, 50 40 選 X2 從 0，X1 =0,X2 = min ( 30/2 , 60/2 , 24/2 ) =12 X2 ：進(jìn)基變量， 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進(jìn)基， 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進(jìn)基， 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ī)劃的典則形式,標(biāo)準(zhǔn)型,上式稱為線性規(guī)劃問(wèn)題對(duì)應(yīng)于基B的典則形式，簡(jiǎn)稱典式。 約束方程組的系數(shù)矩陣中含有一個(gè)單位矩陣，并以其為基； 目標(biāo)函數(shù)中不含基變量，只有非基變量。,檢 驗(yàn) 數(shù),(3) 最優(yōu)性判別定理,在線性規(guī)劃問(wèn)題的典式中，設(shè) X(0)=(x1,x2,xm,0,0) 為對(duì)應(yīng)于基B 的一個(gè)基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 則X(0)是線性規(guī)劃問(wèn)題的最優(yōu)解，基B為最優(yōu)基。,證：設(shè)X為線性規(guī)劃問(wèn)題的一個(gè)可行解，必有 X 0 ，當(dāng) j 0， 則 X 0 Z*=CX(0) = Z(0) Z(0) + X =CX 故X(0)為線性規(guī)劃問(wèn)題的最優(yōu)解。,在線性規(guī)劃

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

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

12、，轉(zhuǎn)(3)。,(6) 單純形單純形法的迭代步驟,定Xr為出基變量，arm+k為主元。,由最小比值法求：,Max j = m+kXm+k 進(jìn)基變量,j 0,(4)、,轉(zhuǎn)(2),(5)、以arm+k為中心，換基迭代,從步驟(2)-(5)的每一個(gè)循環(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ī)劃問(wèn)題的單純形法第一步就是要找到一個(gè)初始可行基并求出初始基可行解，以它作為迭代的起點(diǎn)。 獲得初始可行基及初始基可行解的途徑主要有： (1) 試算法； (2) 人工變量法。 在約束方程組中的每一個(gè)沒(méi)有單位向量的約束方程中人為加入一個(gè)變量，使系數(shù)矩陣中湊成一個(gè)單位方陣，以形成一個(gè)初始可行基陣。,約束條件： 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,人工變量,人工基,等價(jià)否？,大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