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

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

2、單純形法迭代原理,迭代基礎(chǔ)：如果LP存在最優(yōu)解，則一定有一個(gè)基可行最優(yōu)解，且對(duì)應(yīng)LP可行域的頂點(diǎn)。（可行，基解，最優(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,若給定問(wèn)題標(biāo)準(zhǔn)化后，系數(shù)矩陣中不存在m個(gè)線性無(wú)關(guān)的單位列向量，則在某些約束的左端加一個(gè)非負(fù)變量xn+i（人工變量），使得變化后的系數(shù)矩陣中恰有m個(gè)線性無(wú)關(guān)的單位列向量，并且在目標(biāo)函數(shù)中減去這些人工變量與一個(gè)足夠大的正數(shù)M的乘積，對(duì)于變化后的問(wèn)題，取m個(gè)單位列向量構(gòu)成的單位子矩陣為初始基，

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

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

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

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

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

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

10、變換,用單純形法按上述步驟求解時(shí)，可采用表格形式，這樣更直觀，易于避免錯(cuò)誤，該表格稱為單純形表。,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,[ ],對(duì)應(yīng)0,對(duì)應(yīng)A,對(duì)應(yīng)B,19,1.5 單純形法的進(jìn)一步討論,一、人工變量法（大M法）約束條件：“≥” →減一個(gè)剩余變量后，再加一個(gè)人工變量；“＝” →加一個(gè)人工變量；

12、目標(biāo)函數(shù)：人工變量的系數(shù)為“－M”，即罰因子；若線性規(guī)劃問(wèn)題有最優(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ī)劃問(wèn)題中就存在一個(gè)B為單位矩陣，后面可以根據(jù)我們前面所講的單純形法來(lái)進(jìn)

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,,標(biāo)準(zhǔn)化及變形,21,二、兩階段法第一階段求初始基

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

15、行進(jìn)一步的求解。,22,求解輔助問(wèn)題，得到輔助問(wèn)題的最優(yōu)解,引進(jìn)人工變量x6，x7，構(gòu)造輔助問(wèn)題，輔助問(wèn)題的目標(biāo)函數(shù)為所有人工變量之和的極小化,MaxW=0?,原問(wèn)題沒有可行解。,把輔助問(wèn)題的最優(yōu)解作為原問(wèn)題的初始基可行解,用單純形法求解原問(wèn)題，得到原問(wèn)題的最優(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,目標(biāo)函數(shù)極小化最優(yōu)性；退化解

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

18、,0,-5,因?yàn)棣襧全?0,且σ1=0,則有無(wú)窮多最優(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,因?yàn)棣?=2,且ai2全小于0所以：無(wú)界,例:,26,例:,,下表為一極大化問(wèn)題對(duì)應(yīng)的單純形表,討論在a1,a2,a3,a4,a5,a6取何值的情況下，該表中的解為：唯一最優(yōu)解；無(wú)窮多最優(yōu)解；