最优化理论应用随机过程课件第3章单纯形法

PAGEPAGE1第三章单纯形§1单纯形法考虑具有标准形式的线性规划问题(LP)，

minzcTs.t.Axx

xB cB

其中r(A)m。设(LP)的约束集非空，B是(LP)的基。不妨设A=(BN)，x ，cc由第二章N N因此(LP)的目标函

xBB1NxN zcTxcTxcT(B1bB1Nx)cTxcTB1b(cTB1NcT) B N N 于是，由(1.1.1)和(1.1.2)，(LP)可等价地转化 minzcTB1b(cTB1N xB1Nx xB

xNii个单位向量ei记b0b0b0b0TB1ba0a0a0a0)TB1a(jI)zcTB1bcTb0 1 2 rT(rTrT)cTB1A

rT0T，rTcTB1NcTrrcTB1accTa0cxr0 B minzz0rjx x a0xb0,i1,,B Bi

ij i1,,

xj0,j注1.1.1(LP)与(1.1.3)和(1.1.5)单纯形典式(1.1.5)1.2.1（其中cB列和cT行不需要时可不写……r…i……c………i……x…1rim1rim001110r01i00m00z1ri第m行第m+1表 (LP)的单纯形表BNxxIb0rTcTB1N zcT 表 (LP)的矩阵形式单纯形iix0x0x0x0Tx0B1bx00 x0b0,i1,, x0 j 它的目标函数值为cTx0z0例 minzx1s.t.x1x2 -x1 x4x1,x2,x3,x4PAGEPAGE4111062018130001.2.11.2.1Ba3a4的单纯形表Bx(0)(0,0,6,8)T，相应目标函数值为cTx0=0 B12/ 1/3，B1N2/

1/3，bBb4/3 1/ 1/3 1/ zcTB1b(1,3)4/346/ 14/

14/rTcTB1NcT(1,

2/

(0,0)(5/3,2/ 1/ 1/3 100100表 例1.2.1关于B(a1,a2)的单纯形由此知关于B的基本可行解x0(4/3,14/3,0,0)T，相应目标函数值为cTx0=-46/3。注1.2.1 其中b0

minzcTs.t.Axx

minzcTs.t.Axsx0,s

(LP1已经是关于B=I的典式，它的矩阵形式的单纯形表为表1.2.3 s b 0表 (LP1)的矩阵形式单纯形最优性条1.3.1BST(B)BrN0B的基本可行解x0即(1.2.1)是(LP)的最优解，z0是(LP)的最优值。

0。于是，根据典式(1.1.5)

00jjcTxzzr0jj

cTx0即(1.2.1)是(LP)z0cTx0z0是(LP)的最优值。证毕。1.3.11.2.1。jI我们构造(LP)xx1x2xn)TjIN

xjj

jINj

x

b0a0xb0a0x0，i1,, ijj ikkzz0

rjxjz0rkxk xi1,ma00定理 设B是S的可行基。若存在kI使r0，并且a0B1a0，则(LP)无下界 证明：根据条件a00i1,ma00。于是，由(1.4.2)和(1.4.3) dB1.4.1条件下，S存在极向d

dNd 0,jda00, 0,j

使cTdcTdcT cTa0cr0，根据第二章定理2.1.1知(LP)无下界B N B 我们再考虑存在i{1,,m}，使

现在我们先设(LP)是非的。这时，b0(b0,b0,,b0)TB1b0。为保证x的可行性，只要 b rminia00 1im

xj xb r

jIN

b0a0x rk rk bb0 r i1,,m,i

ika

zz0rkra0a0

{aB,,aB,ak,aB,,aB}线性无

det(B1(a,, ,a, ,, ))det(e,,e,B1a, ,,e)a0 r B(aB,,aB,ak,aB,,aB xjjIBIB\{Br{k}B的基变量，xj,jININ\{k{Br}rrbr brxka0

BrB

Nzz0jk

rjxjrk zrxrr rj 0j

j

jI j

a0 zrr rjrkrjxj

0 r

jI

a0

k z

rjx

rk

jzz0

rk b0ba0a

rk

a0rr a0

a a （j=Br时，r0，a1，故rr rj

1zxr,jI k k BT(B)1.2.1BT(B)。其实，关键是通过等价的行初等变换，将表1.2.1xk所对应的系数列向量变换为erxk的检验数变换为0。为此，对T(B)即表1.2.1作以下变换，我们称之为以(r,k)元素为主元的旋转变换。算法1.5.1：以(r,k)元素为主元的旋转r行。n+1a0a,j1,n和b rj,j1,nzr…r…i……x…1r…r…i……x…1im00a101100000r-表 (LP)的单纯形表T(B

01ri第m行第m+1例 取B=I时的单纯形表如表1.2.1，其中r2maxrj30，故取k=2。并且存在a0>0

i2minia00r=2，以(2,2)aa iaa i 01102400表 例1.5.1关于B(a3,a2)的单纯形Ba3a2x0,4,2,0)T，相应目标函数值为cTx12单纯形法算法1.6.1：已知初始可行基的单纯形法i(ix*b0,i1,,x*(x*,x*,,x*)T x*

j

kIrmax{r|jI}a00(i1,m，则停止，(LP)

r{1,m}，使rminia00 1im 修改单纯形表。以(r,k)为主元进行旋转变换，设所得单纯形表如表1.2.1。转2注1.6.1 根据注1.2.1，对于线性规划问题(LP1)，其中b0，很容易形成其标准形式(LP1)的初始单纯形表如表1.2.3。例1.6.11.2.1得单纯形表1.6.2(即表1.5.2)。再求得k=1，r=1，则以(1,1)为主元进行旋转，得单纯形表1.6.3(即表1.2.2)。1110620181300001210400表 例1.6.1第一张单纯形 表 例1.6.1第二张单纯形100100表 例1.6.1第三张单纯形

minzx12 s.t.x1x22x3x42x1x2 x12x24 xj0,j1,,minzx12 s.t.x1x22x3x4 2x1x2x3 x5 8x12x24xj0,j1,,

x610100111100021010802001403000

表 例1.6.2第一张单纯形0010-8015110011-0000010-0010-80201-1-0020400-4rj0x*(0,12,5,8)Tz*16 情前面的讨论是在非的情况下进行的。那么，如果(LP)是的又会发生什么情况呢循环现用单纯形法求解(LP)得单纯形表1.2.1，设所对应的可行基B 的，即b0B1b中存在量。(1.4.4)知，可能出 bbrmini 1im

a002.1.1考虑线性规划问题

min +1x4-8x5-4 +1x4-12x5-1x6+3x7 + xj0,j1009010300010010100060表 例2.1.1的第一张单纯形4001010040010010100000表 例2.1.1的第二张单纯形480108-0010001001010000表 例2.1.1的第三张单纯形10010010100120000表 例2.1.1的第四张单纯形2 0010610010000表 例2.1.1的第五张单纯形1000001001001010000表 例2.1.1的第六张单纯形10090010300010010100060表 例2.1.1的第七张单纯形2.1.72.1.1完全一样，因此再做下去将出现无限循法，它是R.G.Bland于1976年。Bland算法2.2.1：确定主元Blandkmin{j|rjr rR

ia0

rmin{i|iR}

1im

例 考虑例2.1.1，用Bland法则确定主元。前四张表同例2.1.1的前四张表，后三张如下001010030021106000030表 例2.2.1的第五张单纯形001001011010910103000206表 例2.2.1的第六张单纯形001001011-0-002110610002.2.32.2.1的第七张单纯形表x*(34,0,0,1,0,1,0)Tz*54。 M M对于线性规划问题

minzcTs.t.AxxminfcTxMeTs.t.Axyx0,yxy罚项，目的是使人工变量y变为0。我们简记(xy) y 显然，B=I可作为(LPM)的初始可行基，对应的基可行解为xy0b，并fcTxMeTycTxMeT(bAx)mbM c (aij m

j1mxjrjaijMcjj12n，基本可行解xy0b的目标值为biM因此(LPM)B=I的单纯形表如下表

cMMM…x………Ma1100M010M001mai1MmmainM000mbi表 (ALP)关于B=I的单纯形将表3.1.1作为初始单纯形表，用单纯形法求解(LPM)(人工变量出基后不再进基)，得到(LPM)x*y*或得知(LPM)无下定理 设x*y*是(LPM)的最优解。若y*0，则x*是(LP)的最优解，否则(LP)无可行解则存在(LP)x，使cTxcTx*x0是(LPM)的可行解，并且cTxMeT0cTxcT即(LPM)在x0处的目标值小于(LPM)的最优值 ，因此x*是(LP)的最优解y*0，则(LPM)的最优值等于cTx*MeTy*，其中eTy*0。假设(LP)存在可行解x，显然x是(LPM)的可行解，并且当M充分大时cTxMeT0cTxcTx*MeT即(LPM)在x0处的目标值小于(LPM)的最优值， 定理 设(LPM)无下界，并且对应的基可行解为xy。若y0，则(LP)无下界，否则(LP)无可*证明y0x是(LP)的可行解。假如(LP)有下界，则(LP)存在最优解，设为x*。显然，x*是(LPM)的可行解，并且x*0是(LPM)的最优解（否则存在(LPM)的可行解xycTxMeTycTx*MeT0cTM的任意大性知eTy0y0，因x是(LP)的可行解，并且由上式得cTxcTx*x*是的最优解。与(LPM)无下界。因此，(LP)无下界基变量cBxBx… ……001y0yi(i基变量cBxBx… ……001ccBxB001001rjrk00f0则eTy

mi

mimi

0

表 (LPM)无下界时的最终单纯形m i

a00,j ，其INxx中非基变量下标集jka00(i1,mpp

i

a00pr ca0

ma0crpca0

ma0c

ca0m知i

ja00

B i

B i

Bi 3.1.2m-p个方程相加

a0xy b0mm ijj i ip1jINx ip1mm

(i

0aa

iii

biibi假设(LP)存在可行解x，则x0是(LPM)的可行解，代入上式m0m

a0)x

b0。因此(LP)无可行解

jI

i

i3.1.1：当或pq时，MpMqpq时，MpMq。3.1.1求解线性规划问题M

minz=-x1-3x2- x1+x2+x3x1+x2+2x3-x1+2x2+xj0,minf=-x1-3x2-6x3+My1 x1+x2+x3+ x1+ + . -x1+2x2+ +.xj0,j=1,2,3,4,yi0,rcTB1accTac B 0MM01111008M112010M21001413M3M0003.1.23.1.13.1.33.1.3rcTB1accTa0c c0MMc0MM001061002M001-3/2M-00-3/2M-02M-表3.1.3 第二次变换得到单纯形表3.1.4。注意在表3.1.4中，rcTB1accTa0c B c0MM010011010100000-M-表3.2.4 因此，x*(0,4/3,4/3)T，z*z0=-12。例 M

min x1+x2+x3-2x1+x2- 3x2+x3+x4=9xj0,min +My1 x1+x2+x3