運籌學(xué)-第1章-3-單純形法

1、運籌學(xué),——計算機與通信工程學(xué)院,2,授課主要內(nèi)容,目錄：第一章線性規(guī)劃第二章運輸問題第三章動態(tài)規(guī)劃第四章 圖與網(wǎng)絡(luò)分析,3,1.3 單純形法,單純形法的基本思想：從可行域的一個基可行解（頂點）出發(fā)，判斷是否為最優(yōu)解，如果不是最優(yōu)解就轉(zhuǎn)移到另一個較好的基可行解（相鄰），如果目標函數(shù)達到最優(yōu)，則已經(jīng)得到最優(yōu)解，否則繼續(xù)轉(zhuǎn)移到其他較好的基可行解（頂點）。由于基可行解的數(shù)目有限，所以在有限次迭代內(nèi)，可以找到最優(yōu)解。,4,

2、單純形法迭代原理,迭代基礎(chǔ)：如果LP存在最優(yōu)解，則一定有一個基可行最優(yōu)解，且對應(yīng)LP可行域的頂點。（可行，基解，最優(yōu)）,1.確定初始基可行解,基解，可行解,（1）直接觀察法,5,max z = x1 + 3x2 + 2x3 + x4 s.t. x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 ≥ 0,選 XB =

3、(x1 x4)T 令x2 = x3 = 0 則 初始基可行解：X = (3 0 0 4)T,（2）人工變量法（大M法）,6,若給定問題標準化后，系數(shù)矩陣中不存在m個線性無關(guān)的單位列向量，則在某些約束的左端加一個非負變量xn+i（人工變量），使得變化后的系數(shù)矩陣中恰有m個線性無關(guān)的單位列向量，并且在目標函數(shù)中減去這些人工變量與一個足夠大的正數(shù)M的乘積，對于變化后的問題，取m個單位列向量構(gòu)成的單位子矩陣為初始基，

4、則該基對應(yīng)的可行解一定是基可行解。,（2）人工變量法（大M法）,7,原問題的任意基可行解都是變化后問題的基可行解若變化后的問題最優(yōu)解中不含有非零的人工變量，則該解就是原問題的最優(yōu)解若變化后的問題中含有非零的人工變量則元問題無可行解,例：max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 s.t. 2x1 + x2 + x3 = 4 x1,x2,

5、x3 ≥ 0,,8,2.最優(yōu)性檢驗和解的判別,非基變量檢驗數(shù),9,由檢驗數(shù)可以判斷解的最優(yōu)性情況（1）因為所有Xj≥0，當(dāng)所有σj0,且所有aik≤0(Pj≤0), i=1,2,…,m，則該問題無界（無界解）；（4）因為所有Xj≥0，當(dāng)存在σj>0時，則該基可行解不是最優(yōu)解，需要尋找另一個基可行解；,10,3.基變換,變換目的：使目標函數(shù)Z值得到改善，接近最優(yōu)解，一次基變換，是從該頂點到相鄰頂點，即一次基變換僅變換一個基變量。

6、,換入變量的確定（入基變量）σk>0,aik 至少一個大于0，若σk=Max{σj| σj>0},則xk為換入變量。換出變量的確定（出基變量）,則xl為換出變量。系數(shù)變換（初等行變換）,11,以alk為主元進行初等行變換,,,,,12,1.4 單純形法計算步驟,求初始基可行解最優(yōu)性檢驗基變換,13,單純形法原理—單純形法總結(jié),STEP 0 找到一個初始的基礎(chǔ)可行解，確定基變量和非基變量。轉(zhuǎn)STEP 1。S

7、TEP 1 將目標函數(shù)和基變量分別用非基變量表示。轉(zhuǎn)STEP 2。STEP 2 如果目標函數(shù)中所有非基變量的檢驗數(shù)全部為非正數(shù)，則已經(jīng)獲得最優(yōu)解，如果全為負數(shù)，則為唯一最優(yōu)解，運算終止。 ；如果有為0的非基變量檢驗數(shù)，則有無窮多最優(yōu)解。運算終止。如果有某非基變量檢驗數(shù)為正，且工藝系數(shù)全非正，則無界，運算終止。 否則，選取檢驗數(shù)為正數(shù)最大的非基變量進基。轉(zhuǎn)STEP 3。STEP 3

8、 選擇最小比值對應(yīng)的基變量離基，進行系數(shù)初等行變換，得新的基可行解，轉(zhuǎn)STEP 1。,14,一.求初始基可行解,1.當(dāng)約束條件為“≤”時，直接在約束不等式左邊加上非負的松弛變量，使約束方程的系數(shù)矩陣很容易找到一個單位矩陣，求出一個初始基可行解。2.當(dāng)約束條件為“≥時，直接在約束不等式左邊減去非負的剩余變量，此情況下很難找到一個單位矩陣，為求出初始基可行解，為此需要引入人工變量，以方便構(gòu)成初始基可行解的一個基。 為了不改變問題

9、的性質(zhì)，對引入人工變量Xi”的線性規(guī)劃問題，需要在目標函數(shù)中減去MXi”,M為足夠大的正數(shù)，稱罰因子，促使Xi”最終必為0。3.當(dāng)約束條件為”=“時，同樣需要引入人工變量，以方便構(gòu)成初始基可行解的一個基。目標函數(shù)需要減去罰因子。,15,二.最優(yōu)性檢驗,（1）若所有σj0,且所有aik≤0(Pj≤0), i=1,2,…,m，則該問題無界，計算終止。（4）當(dāng)存在σj>0時，且有aik>0,繼續(xù)第三步（基變換）；,16,三.基

10、變換,用單純形法按上述步驟求解時，可采用表格形式，這樣更直觀，易于避免錯誤，該表格稱為單純形表。,17,例,σj,2,1,0,0,0,[ ],-,4,5,[ ],x1入，x4出,σj,0,1/3,0,-1/3,0,[ ],x2入，x5出,3,12,3/2,[ ],σj,0,0,0,-1/4,-1/2,所以：X*=(x1,x2,x3)T=(7/2,3/2,15/2)T Z*=17/2,18,例:1.4(1),σj

11、,10,5,0,0,[ ],3,8/5,[ ],x1入,x4出,σj,0,1,0,-2,[ ],x2入,x3出,3/2,4,σj,0,0,-5/14,-25/14,所以：X*=(x1,x2)T=(1,3/2)T Z*=35/2,[ ],對應(yīng)0,對應(yīng)A,對應(yīng)B,19,1.5 單純形法的進一步討論,一、人工變量法（大M法）約束條件：“≥” →減一個剩余變量后，再加一個人工變量；“＝” →加一個人工變量；

12、目標函數(shù)：人工變量的系數(shù)為“－M”，即罰因子；若線性規(guī)劃問題有最優(yōu)解則人工變量必為0。,20,MaxZ=-3x1+x3 x1+ x2+ x3≤4 -2x1+ x2- x3≥1 3x2+x3=9 xi ≥0,j=1,2,3,,,,增加人工變量后，線性規(guī)劃問題中就存在一個B為單位矩陣，后面可以根據(jù)我們前面所講的單純形法來進

13、行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7,,標準化及變形,21,二、兩階段法第一階段求初始基

14、可行解。給原問題加入人工變量，并構(gòu)建一個僅含人工變量的目標函數(shù)（對人工變量和的相反數(shù)求最大），約束條件和原問題的一樣。當(dāng)?shù)谝浑A段中目標函數(shù)的最優(yōu)值＝0，既人工變量＝0，則轉(zhuǎn)入第二階段；若第一階段中目標函數(shù)的最優(yōu)值不等于0，既人工變量不等于0，則判斷原問題為無解。第二階段求原問題最優(yōu)解。將第一階段計算所得的單純形表劃去人工變量所在的列，并將目標函數(shù)換為原問題的目標函數(shù)，作為第二階段的初始單純形表，以第一階段的最優(yōu)解作為初始基可行解，進

15、行進一步的求解。,22,求解輔助問題，得到輔助問題的最優(yōu)解,引進人工變量x6，x7，構(gòu)造輔助問題，輔助問題的目標函數(shù)為所有人工變量之和的極小化,MaxW=0?,原問題沒有可行解。,把輔助問題的最優(yōu)解作為原問題的初始基可行解,用單純形法求解原問題，得到原問題的最優(yōu)解,,,,,,否,是,兩階段法的算法流程圖,MaxZ=-3x1+x3 x1+ x2+ x3≤4 -2x1+ x2- x3≥1

16、 3x2+x3=9 xi ≥0,j=1,2,3,MaxW=-x6-x7 x1+ x2+ x3+x4 =4-2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7,23,目標函數(shù)極小化最優(yōu)性；退化解

17、的判別；無可行解的判別；無界的判別；無窮多最優(yōu)解的判別；唯一最優(yōu)解的判別.,三、單純形法計算中的幾個問題,當(dāng)所有非基變量的σj≥0時為最優(yōu)解；,最優(yōu)解中基變量有取值為0的值時；,最優(yōu)解中人工變量為非0的基變量時；,存在某個σk>0，且所有的aik≤0時；,得最優(yōu)解時，有檢驗數(shù)為0的非基變量；,得最優(yōu)解時，所有非基變量檢驗數(shù)為負；,24,σj,40,45,0,25,100/3,40,[ 3 ],x2入，x3出,σj,0,0

18、,0,-5,因為σj全?0,且σ1=0,則有無窮多最優(yōu)解。 所以：X*=(0,80/3,20,0,0),Z*=1700,例:,0,-10,……,25,σj,1,1,0,0,-,50,[ ],x1入，x4出,σj,0,2,0,-1,因為σ2=2,且ai2全小于0所以：無界,例:,26,例:,,下表為一極大化問題對應(yīng)的單純形表,討論在a1,a2,a3,a4,a5,a6取何值的情況下，該表中的解為：唯一最優(yōu)解；無窮多最優(yōu)解；