運籌學單純形法

關于運籌學單純形法基向量、非基向量、基變量、非基變量：

稱pj(j=1,2,…,m）為基向量，其余稱為非基向量； 與基向量pj(j=1,2,…,m）對應的xj稱為基變量，其全體寫成XB=（x1，x2，…，xm）T；否則稱為非基變量，其全體經(jīng)常寫成XN?；猓簩o定基B,設XB是對應于這個基的基變量

XB=(x1，x2，…，xm)T；

令非基變量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T

稱為基解?；尚薪猓核袥Q策變量滿足非負條件(xj≥0)的基解,

稱作基可行解?？尚谢夯尚薪馑鶎幕追Q為可行基。第2頁,共48頁，星期六，2024年，5月寫出下述線性規(guī)劃問題對應的基、基變量、基解、基可行解和可行基。第3頁,共48頁，星期六，2024年，5月定理2：X是線性規(guī)劃問題的基可行解的充要條件是它對應于可行域D的頂點。（線性規(guī)劃問題的基可行解X對應于可行域D的頂點。）定理3：若可行域有界,線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu).第4頁,共48頁，星期六，2024年，5月§3單純形法（SimplexMethod）例子：求解線性規(guī)劃問題線性規(guī)劃問題的最優(yōu)解，可以從基可行解中找到

圖解法有局限性；

枚舉法計算量大；§3.1單純形法的引入0Q4Q31123234Q2Q1X1X2x1+2x2=84x1=164x2=12第5頁,共48頁，星期六，2024年，5月解:

首先:將該問題化成標準形第二:

找初始可行解(即一個頂點)。系數(shù)矩陣A=(p1p2p3p4p5)矩陣形式第6頁,共48頁，星期六，2024年，5月

因為p3，p4，

p5線性獨立，故B=(p3,p4,p5)構成一個基底，對應的基變量x3，x4，x5解出來為（用非基變量表示基變量）

x3=8-x1-2x2x4=16-4x1(a)x5=12-4x2

將(a)代入目標函數(shù)中得z=0+2x1+3x2令非基底變量x1=x2=0，則有z=0。這時得到一個基可行解X(0)=(0,0,8,16,12)T---原點第三:判別從目標函數(shù)中得知，非基底變量的系數(shù)為正，因此，將非基變量換入基底后可使目標函數(shù)增大，轉入第四步第7頁,共48頁，星期六，2024年，5月第四:換基底(旋轉迭代)

確定換入變量：由于z=0+2x1+3x2

中非基底變量x2系數(shù)貢獻最大3，故換入基底為x2。換入變量已定，必須從x3，x4，x5換出一個，并且要保證其余均是非負的，即x3，x4，x50。

x3=8-2x2

0

x4=160

x5=12-4x20

由此，只要選擇x2=min(8/2，-，12/4)=3，對應基底變量x5=0，從而確定用x2和x5對調(diào)，即將x5

換出。有

x3

=2-x1+1/2x5

x4=16-4x1(b)x2=3-1/4x5

第8頁,共48頁，星期六，2024年，5月

將(b)代入目標函數(shù)中得z=9+2x1-3/4x5

令非基變量為零，又得到另一個基可行解

X(1)=(0,3,2,16,0)T–頂點Q4

返回第三步：非基變量x1的系數(shù)是正的，還可增大，X(1)

不是最優(yōu)解。重復上述步驟。由于x1的系數(shù)是正的，從而x1為轉入變量，再由x3=2-x1

0

x4=16-4x1

0

x2=30

第9頁,共48頁，星期六，2024年，5月只要選

x1=min{2，16/4，-}=2上式就成立，因為x1=2時，基變量x3=0，從而由x1換出x3，得

x1=2-x3+1/2x5

4x1+x4=16

(c)x2=3-1/4x5高斯消去法（行變換）得

x1=2-x3+1/2x5

x4=8-2x5+4x3x2=3-1/4x5

第10頁,共48頁，星期六，2024年，5月代入目標函數(shù)中，得

z=13-2x3+1/4x5令非基變量x3=x5=0，又得到另一個基可行解X(2)X(2)=(2,3,0,8,0)T–新頂點Q3

同理，返回第三步，再迭代，x5作為轉入變量

x1=2+1/2x5

0

x4=8-2x50

x2=3-1/4x5

0

第11頁,共48頁，星期六，2024年，5月只要取x5=min{-，8/2，12}=4就有上式成立。x5=4時，x4=0，故決定用x5換x4x1=4-1/4x4

x5=4-1/2x4+2x3x2=2+1/8x4–1/2x3

代入得z=14-3/2x3–1/8x4

，令x3，x4=0得z=14。新基可行解為

X(3)=(4,2,0,0,4)T–為最優(yōu)解，新頂點Q2最優(yōu)目標值z=14。第12頁,共48頁，星期六，2024年，5月從實際例子中分析單純形法原理的基本框架為

第一步：將線性規(guī)劃模型變換成標準型，確定一個初始可行解（頂點）。

第二步：對初始基可行解最優(yōu)性判別，若最優(yōu)，停止；否則轉下一步。

第三步：從初始基可行解向相鄰的基可行解（頂點）轉換，且使目標值有所改善—目標函數(shù)值增加，重復第二和第三步直到找到最優(yōu)解。第13頁,共48頁，星期六，2024年，5月§3.2初始可行基的確定設線性規(guī)劃問題：第14頁,共48頁，星期六，2024年，5月

為了確定初始基可行解，首先要找出初始可行基，其方法如下：從Pj(j=1,2,…,n)中一般能直接觀察到存在一個初始可行基

確定初始可行基的幾種方法：

形式的不等式

形式的不等式=的情形觀察“小加大減+人造”第15頁,共48頁，星期六，2024年，5月

約束是≤形式的不等式，可以利用化標準型的方法，左端加一個松弛變量，經(jīng)過整理，重新對xj及aij（i=1,2,…,m；j=1，2，…，n）進行調(diào)整編號，則可得下列方程組“小加”第16頁,共48頁，星期六，2024年，5月x1+a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2

……

xm+am,m+1xm+1+…+amnxn=bmxj≥0，j=1,2,…,n顯然得到一個m×m單位矩陣注意：aij和bi已經(jīng)變化第17頁,共48頁，星期六，2024年，5月移項整理得

x1=b1-a1,m+1xm+1-…-a1nxn

x2=b2–a2,m+1xm+1-…-a2nxn

……

xm=bm–am,m+1xm+1-…-amnxn

令xm+1=xm+2=…=xn=0，可得

xi=bi

（i=1，2，…，m）

又因bi≥0，所以得到一個初始基可行解：

X（0）=（x1x2…

xm0…0)T

=(b1b2…

bm0…0)T第18頁,共48頁，星期六，2024年，5月非基向量可以用基向量的線性組合表示將(3)式乘以一個正的數(shù)

>0,得到記初始基可行解為X(0),有該解滿足約束方程,即§3.3從初始基可行解轉換為另一基可行解第19頁,共48頁，星期六，2024年，5月(4)式和(1)式相加,整理后得到由(5)式可以找到滿足約束方程的另一個點X(1),其中是點X(1)的第j個坐標值第20頁,共48頁，星期六，2024年，5月要使X(1)是一個基本可行解,則要求并且這m個等式中至少要有一個等號成立當時,(6)式必然成立當時,令因此有所以X(1)中的正分量最多有m個,可證明m個向量P1,…,Ps-1,Ps+1,…,Pm,Pj線性無關,按照式(7)確定

值,X(1)就是一個新的基可行解.第21頁,共48頁，星期六，2024年，5月線性規(guī)劃解的四種可能：1、有唯一解；2、無窮多最優(yōu)解；3、無界解；4、無可行解。何時達最優(yōu)解,何種最優(yōu)解？§3.4

最優(yōu)性檢驗和判別定理第22頁,共48頁，星期六，2024年，5月將基本可行解X(0)和X(1)分別代入目標函數(shù)得由此

j稱做檢驗數(shù),是對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標志.第23頁,共48頁，星期六，2024年，5月最優(yōu)解的判別定理：且對一切的j=m+1,...,n有則X(0)

為最優(yōu)解。若是一個基可行解，第24頁,共48頁，星期六，2024年，5月無窮多最優(yōu)解判別定理：若是一個基可行解，且對一切的j=m+1,...,n有又存在某個非基變量的檢驗數(shù)則線性規(guī)劃問題有無窮多最優(yōu)解。第25頁,共48頁，星期六，2024年，5月無界解的判別定理：第26頁,共48頁，星期六，2024年，5月§3.5基變換換入變量的確定:max(

j>0)=k,j=m+1,…,n;xk是換入變量(也可任選).換出變量的確定:

確定換出變量的原則是保持解的可行性,就是說要使原基可行解的某一正分量xs變成零,同時保持其它的分量均非負(換基原則)min(xi/aij|aij>0)=xs/asj=,s{1,2,…,m}(最小比值準則,或

準則)§3.6旋轉運算在確定換入變量xk和換出變量xs以后，要把xk所對應的系數(shù)列向量pk變成單位向量，為此,只要對系數(shù)矩陣的增廣陣進行“行”的初等變換即可。行變換的定義：第27頁,共48頁，星期六，2024年，5月(第s行)*1/ask得:當is時,(第i行)-(第s行)*aik第28頁,共48頁，星期六，2024年，5月經(jīng)過初等變換后,新的增廣矩陣是第29頁,共48頁，星期六，2024年，5月§4單純形法的計算步驟和單純形表約束方程組和目標函數(shù)組成n+1個變量,m+1個方程的方程組該方程組對應的增廣矩陣是第30頁,共48頁，星期六，2024年，5月第31頁,共48頁，星期六，2024年，5月第32頁,共48頁，星期六，2024年，5月確定初始單純形表后可以得到初始基可行解x0,

若有某個非基底變量xk對應的檢驗數(shù)

k=(ck-zk)>0,則當前解不是最優(yōu)解，取使目標增長最大的非基底變量進入基底。根據(jù)確定xk為換入變量根據(jù)確定xs為換出變量將xk對應的列向量Pk=(a1k,,…,ask,…,ank)T變換為aik=0，is

aik=1，i=s重復上述步驟直到所有的檢驗數(shù)滿足最優(yōu)條件，得最優(yōu)解。第33頁,共48頁，星期六，2024年，5月§5單純形法的進一步討論

人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，，xn+m

人工變量是虛擬變量，加入原方程中是作為臨時基變量，經(jīng)過基的旋轉變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗數(shù)小于零，而且基變量中還有某個非零的人工變量，原問題無可行解。第34頁,共48頁，星期六，2024年，5月1、大M法方法：在約束條件中，加入人工變量后，要求目標函數(shù)不受影響？目標函數(shù)中人工變量的系數(shù)取（-M）。理由：目標函數(shù)實現(xiàn)最大化，就必須將人工變量從基變量中換出，否則目標函數(shù)就不可能取得最大化。例1：用大M法求解如下線性規(guī)劃問題第35頁,共48頁，星期六，2024年，5月111-211000113-4120-1103/21-20[1]000110M16xx4

x3103-20100-110[1]00-11-211-2010001-3x11x21x341001/3-2/32/3-5/310100-11-2900102/3–4/3-7/3

-31100

MM

-10001M-1M+1zj-cj

0001/31/3M-1/3M-2/3zj-cj0x41x21x312[3]001-22-5410100-11-21-2010001cj0MMX4X6X7

b

CBXBX1X2X3X4X5X6X7

i-3+6M1-M1-3M0M00cj-zj

-11-M00M03M-1cj-zj第36頁,共48頁，星期六，2024年，5月最優(yōu)解是目標函數(shù)為-2。

第37頁,共48頁，星期六，2024年，5月2、兩階段法第一階段：建立一個輔助線性規(guī)劃并求解，以此判斷原線性規(guī)劃是否存在可行解。輔助線性規(guī)劃問題：目標函數(shù)取成所有的人工變量之和，并對目標函數(shù)取極小化，約束條件依然為原問題的以單位矩陣作為可行基的標準型的約束條件。所有人工變量都變成非基變量，目標函數(shù)值為0，原問題存在基可行解。轉到第二階段。若目標函數(shù)值不為0，至少有一個人工變量不能從基變量中轉出，原問題沒有可行解。停止。第二階段：從第一階段最優(yōu)表格中去掉人工變量，將目標函數(shù)系數(shù)換成原問題的目標函數(shù)系數(shù)，用單純形法計算，直到得到最優(yōu)解為止。第38頁,共48頁，星期六，2024年，5月第一階段：求解輔助規(guī)劃問題第39頁,共48頁，星期六，2024年，5月

111-211000113-4120-1103/21-20[1]000110106xx4

x3103-20100-110[1]00-11-211-2010001

00000

11

0000011zj-cj0x40x20x312[3]001-22-5410100-11-21-2010000cj011X4X6X7

b

CBXBX1X2X3X4X5X6X7

i6-1-30100cj-zj

0-100103cj-zj第40頁,共48頁，星期六，2024年，5月12[311-20100-3112xx1

x341001/3-2/310100-190012/3-4/3

-31100cj011X4X2X3

b

CBXBX1X2X3X4X5

i-10001cj-zj

0001/31/3cj-zjx6，x7是人工變量，第一階段求解的最優(yōu)結果是

=0，因此得最優(yōu)解為：

第二階段：取消人工