1、設(shè)線性規(guī)劃的標(biāo)準(zhǔn)形式： max z=cjxj (1) s.t.aijxj=bi i=1,2,m (2) xj0 j=1,2,n (3) 可行域：由約束條件(2)、(3)所圍成的區(qū)域； 可行解：滿足(2)、(3)條件的解X=(x1，x2，xn)T為可行解； 基：設(shè)A是約束條件方程組的mn維系數(shù)矩陣,其秩為m，B是A中mm階非奇異子矩陣，則稱B為線性規(guī)劃問(wèn)題的一個(gè)基。 設(shè),復(fù)習(xí): 線性規(guī)劃問(wèn)題解的概念,基向量、非基向量、基變量、非基變量： 稱pj(j=1,2,m）為基向量，其余稱為非基向量； 與基向量pj(j=1,2,m）對(duì)應(yīng)的xj稱為基變量，其全體寫成XB=（x1，x2，xm）T；否則稱為非基變

2、量，其全體經(jīng)常寫成XN。 基解：對(duì)給定基B,設(shè)XB是對(duì)應(yīng)于這個(gè)基的基變量 XB=(x1，x2，xm)T； 令非基變量xm+1=xm+2=xn=0， 由（2）式得出的解X=（x1，x2，xm，0，0）T 稱為基解。 基可行解：所有決策變量滿足非負(fù)條件(xj 0)的基解, 稱作基可行解。 可行基：基可行解所對(duì)應(yīng)的基底稱為可行基。,寫出下述線性規(guī)劃問(wèn)題對(duì)應(yīng)的基、基變量、基解、基可行解和可行基。,定理2：X是線性規(guī)劃問(wèn)題的基可行解的充要條件是它對(duì)應(yīng)于可行域D的頂點(diǎn)。（線性規(guī)劃問(wèn)題的基可行解X 對(duì)應(yīng)于可行域D的頂點(diǎn)。） 定理3：若可行域有界,線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu).,3

3、 單純形法（Simplex Method）,例子：求解線性規(guī)劃問(wèn)題,線性規(guī)劃問(wèn)題的最優(yōu)解，可以從基可行解中找到 圖解法有局限性； 枚舉法計(jì)算量大；,3.1 單純形法的引入,解: 首先:將該問(wèn)題化成標(biāo)準(zhǔn)形,第二: 找初始可行解(即一個(gè)頂點(diǎn))。 系數(shù)矩陣 A=(p1 p2 p3 p4 p5),矩陣形式,因?yàn)閜3 ，p4， p5 線性獨(dú)立，故B=( p3 , p4, p5)構(gòu)成一個(gè)基底，對(duì)應(yīng)的基變量x3，x4， x5解出來(lái)為（用非基變量表示基變量） x3 =8- x1-2x2 x4 =16-4x1 (a) x5 =12- 4x2 將(a)代入目標(biāo)函數(shù)中得 z=0+2x1+3x2 令非基底變量 x1=

4、x2=0，則有z=0。這時(shí)得到一個(gè)基可行解 X(0) =(0,0,8,16,12) T -原點(diǎn),第三:判別 從目標(biāo)函數(shù)中得知，非基底變量的系數(shù)為正，因此，將非基變量換入基底后可使目標(biāo)函數(shù)增大，轉(zhuǎn)入第四步,第四:換基底(旋轉(zhuǎn)迭代) 確定換入變量：由于z=0+2x1+3x2 中非基底變量x2系數(shù)貢獻(xiàn)最大3，故換入基底為x2。 換入變量已定，必須從x3，x4，x5換出一個(gè)，并且要保證其余均是非負(fù)的，即x3，x4， x50。 x3 =8- 2x2 0 x4 =16 0 x5 =12- 4 x2 0 由此，只要選擇 x2 =min (8/2，-，12/4)=3，對(duì)應(yīng)基底變量x5 =0，從而確定用x2和x

5、5對(duì)調(diào)，即將x5 換出。有 x3 =2- x1+1/2x5 x4 =16-4x1 (b) x2 =3- 1/4 x5,將(b)代入目標(biāo)函數(shù)中得 z=9+2x1-3/4x5 令非基變量為零，又得到另一個(gè)基可行解 X(1) =(0,3,2,16,0) T 頂點(diǎn)Q4,返回 第三步：非基變量x1的系數(shù)是正的，還可增大， X (1) 不是最優(yōu)解。重復(fù)上述步驟。由于x1的系數(shù)是正的，從而x1為轉(zhuǎn)入變量，再由 x3 =2- x1 0 x4 =16- 4 x1 0 x2 =3 0,只要選 x1=min2，16/4，-=2 上式就成立，因?yàn)閤1= 2時(shí)，基變量x3=0，從而由x1換出x3，得 x1 =2- x3

6、 +1/2x5 4x1 +x4 =16 (c) x2 =3- 1/4 x5 高斯消去法（行變換）得,x1 =2- x3 +1/2x5 x4 =8-2 x5 +4 x3 x2 =3- 1/4 x5,代入目標(biāo)函數(shù)中，得 z=13-2 x3 +1/4x5 令非基變量x3= x5=0，又得到另一個(gè)基可行解X(2) X(2) =(2,3,0,8,0) T 新頂點(diǎn)Q3 同理，返回第三步，再迭代，x5作為轉(zhuǎn)入變量 x1 =2+1/2x5 0 x4 =8-2 x5 0 x2 =3- 1/4 x5 0,只要取 x5=min-，8/2，12=4 就有上式成立。 x5=4時(shí)， x4=0，故決定用x5換x4 x1 =

7、4- 1/4 x4 x5 =4-1/2 x4 +2 x3 x2 =2+1/8 x41/2 x3 代入得 z=14-3/2 x3 1/8 x4 ，令x3 ，x4=0得z=14。新基可行解為 X(3) =(4,2,0,0,4) T 為最優(yōu)解，新頂點(diǎn)Q2 最優(yōu)目標(biāo)值z(mì)=14 。,從實(shí)際例子中分析單純形法原理的基本框架為 第一步：將線性規(guī)劃模型變換成標(biāo)準(zhǔn)型，確定一個(gè)初始可行解（頂點(diǎn)）。 第二步：對(duì)初始基可行解最優(yōu)性判別，若最優(yōu)，停止；否則轉(zhuǎn)下一步。 第三步：從初始基可行解向相鄰的基可行解（頂點(diǎn)）轉(zhuǎn) 換，且使目標(biāo)值有所改善目標(biāo)函數(shù)值增加，重復(fù)第二和第三步直到找到最優(yōu)解。,3.2 初始可行基的確定,設(shè)線性

8、規(guī)劃問(wèn)題：, 為了確定初始基可行解，首先要找出初始可行基，其方法如下：從Pj(j=1,2,n)中一般能直接觀察到存在一個(gè)初始可行基,確定初始可行基的幾種方法：, 形式的不等式 形式的不等式 =的情形 觀察,“小加大減+人造”, 約束是形式的不等式，可以利用化標(biāo)準(zhǔn)型的方法，左端加一個(gè)松弛變量，經(jīng)過(guò)整理，重新對(duì)xj及aij（i=1,2,m；j=1， 2，n）進(jìn)行調(diào)整編號(hào)，則可得下列方程組,“小加”,x1 +a1,m+1xm+1+a1nxn=b1 x2 +a2,m+1xm+1+a2nxn=b2 xm +am,m+1xm+1+amnxn=bm xj0，j=1,2,n,顯然得到一個(gè)mm單位矩陣,注意：a

9、ij和bi 已經(jīng)變化,移項(xiàng)整理得 x1 = b1-a1,m+1xm+1-a1nxn x2 = b2a2,m+1xm+1-a2nxn xm = bmam,m+1xm+1-amnxn 令xm+1=xm+2=xn=0，可得 x i=bi （i=1，2，m） 又因bi0，所以得到一個(gè)初始基可行解： X（0）=（x1 x2 xm 0 0)T = (b1 b2 bm 0 0)T,非基向量可以用基向量的線性組合表示 將(3)式乘以一個(gè)正的數(shù)0,得到,記初始基可行解為X(0),有 該解滿足約束方程, 即,3.3 從初始基可行解轉(zhuǎn)換為另一基可行解,(4)式和(1)式相加,整理后得到 由(5)式可以找到滿足約束方

10、程的另一個(gè)點(diǎn)X(1),其中是點(diǎn)X(1)的第j個(gè)坐標(biāo)值,要使X(1)是一個(gè)基本可行解,則要求 并且這m個(gè)等式中至少要有一個(gè)等號(hào)成立 當(dāng) 時(shí),(6)式必然成立 當(dāng) 時(shí),令 因此有 所以X(1)中的正分量最多有m個(gè),可證明m個(gè)向量P1, , Ps-1, Ps+1, ,Pm, Pj 線性無(wú)關(guān),按照式(7)確定值, X(1)就是一個(gè)新的基可行解.,何時(shí)達(dá)最優(yōu)解, 何種最優(yōu)解？,3.4 最優(yōu)性檢驗(yàn)和判別定理,將基本可行解X(0)和X(1)分別代入目標(biāo)函數(shù)得 由此 j稱做檢驗(yàn)數(shù),是對(duì)線性規(guī)劃問(wèn)題的解進(jìn)行最優(yōu)性檢驗(yàn)的標(biāo)志.,最優(yōu)解的判別定理：,且對(duì)一切的 j=m+1,.,n有,則X(0) 為最優(yōu)解。,若 是一

11、個(gè)基可行解，,無(wú)窮多最優(yōu)解判別定理：,若 是一個(gè)基可行解，,且對(duì)一切的 j=m+1,.,n 有,又存在某個(gè)非基變量的檢驗(yàn)數(shù) 則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。,無(wú)界解的判別定理：,3.5 基變換 換入變量的確定: max(j0)= k, j=m+1,n; xk是換入變量(也可任選). 換出變量的確定: 確定換出變量的原則是保持解的可行性,就是說(shuō)要使原基可行解的某一正分量xs變成零,同時(shí)保持其它的分量均非負(fù)(換基原則) min(xi/aij|aij0)= xs/asj=, s1,2,m (最小比值準(zhǔn)則,或準(zhǔn)則),3.6 旋轉(zhuǎn)運(yùn)算 在確定換入變量xk和換出變量xs以后，要把xk所對(duì)應(yīng)的系數(shù)列向量pk變

12、成單位向量，為此,只要對(duì)系數(shù)矩陣的增廣陣進(jìn)行“行”的初等變換即可。行變換的定義：,(第s行)*1/ask得: 當(dāng)is時(shí),(第i行)-(第s行)*aik,經(jīng)過(guò)初等變換后,新的增廣矩陣是,4 單純形法的計(jì)算步驟和單純形表 約束方程組和目標(biāo)函數(shù)組成 n+1個(gè)變量,m+1個(gè)方程的方程組,該方程組對(duì)應(yīng)的增廣矩陣是,確定初始單純形表后可以得到初始基可行解x0, 若有某個(gè)非基底變量xk對(duì)應(yīng)的檢驗(yàn)數(shù)k=(ck-zk)0,則當(dāng)前解不是最優(yōu)解，取使目標(biāo)增長(zhǎng)最大的非基底變量進(jìn)入基底。 根據(jù) 確定xk為換入變量 根據(jù) 確定xs為換出變量 將xk對(duì)應(yīng)的列向量Pk=(a1k,ask,ank)T變換為 aik=0，i s

13、aik=1，i=s 重復(fù)上述步驟直到所有的檢驗(yàn)數(shù)滿足最優(yōu)條件，得最優(yōu)解。,5 單純形法的進(jìn)一步討論,人工變量法（確定初始可行基）：,原約束方程：AX=b,加入人工變量：xn+1，xn+m,人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過(guò)基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原問(wèn)題無(wú)可行解。,1、大M法 方法：在約束條件中，加入人工變量后，要求目標(biāo)函數(shù)不受影響？目標(biāo)函數(shù)中人工變量的系數(shù)取（-M）。,理由：目標(biāo)函數(shù)實(shí)現(xiàn)最大化，就必須將人工變量從基變量中換出，否則目標(biāo)函數(shù)就不可能取得最大化。,例1：用大M法求解如

14、下線性規(guī)劃問(wèn)題,cj,最優(yōu)解是,目標(biāo)函數(shù)為-2。,2、兩階段法 第一階段： 建立一個(gè)輔助線性規(guī)劃并求解，以此判斷原線性規(guī)劃是否存在可行解。 輔助線性規(guī)劃問(wèn)題：目標(biāo)函數(shù)取成所有的人工變量之和，并對(duì)目標(biāo)函數(shù)取極小化，約束條件依然為原問(wèn)題的以單位矩陣作為可行基的標(biāo)準(zhǔn)型的約束條件。 所有人工變量都變成非基變量，目標(biāo)函數(shù)值為0，原問(wèn)題存在基可行解。轉(zhuǎn)到第二階段。 若目標(biāo)函數(shù)值不為0，至少有一個(gè)人工變量不能從基變量中轉(zhuǎn)出，原問(wèn)題沒(méi)有可行解。停止。 第二階段： 從第一階段最優(yōu)表格中去掉人工變量，將目標(biāo)函數(shù)系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，用單純形法計(jì)算，直到得到最優(yōu)解為止。,第一階段：求解輔助規(guī)劃問(wèn)題,cj,x6，x7是人工變量，第一階段求解的最優(yōu)結(jié)果是=0，因此得最優(yōu)解為：,第二階段：取消人工變量，添入原問(wèn)題目標(biāo)函數(shù)的系數(shù)，求解相應(yīng)的線性規(guī)劃。,最優(yōu)解為：,最優(yōu)值為： z= -2,兩階段法：輔助規(guī)劃； 去掉人工變量，單純形法。,對(duì)目標(biāo)函數(shù)求max的線性規(guī)劃問(wèn)題,用單純形法計(jì)算