最优化理论与方法第三章2015年9月9日

第三自动化学自动化学一.单纯形法的正正规式虑线性

a1nminf(X)CT

AX

A

2nX

mn设可行

p1 p pnBp1 p pm3则x1x

,,

x1 mxm1xm2,x

Xx XA

p N

XXB

NAXb NXBb NX X X N B1bB fX)f(X)CTXC

T

B

T CT N N CT(B1bB ) CTB1b(CTB1NCT) minf(X)CTB1b(CTB1NCT

B1bX CTB1b CTB1N

T

m m B1b

B1N

2,n

m,nn minf(X)n

0jxjjm1n n

i1~正规式s.t

jmxj j=1~x CX BCCCxxx1000100012,mm,m1000f与正规式对应的单纯检验数的

C

C m

例1：写出正规minf(x)2x3x x32x4x5x 3 2x x 34 0,j1~

pj

pjm正规式为：minfX)

0jx is.t

xj j=1~x若令所有非基变量xj都取零值正规式得到对应基B的基 j1nxX1nx

j

j B是可行基，

j j优解的判别准minf(X)CT(LP)s.tAXXj 则相应的基可行解是最优

x1,,xnT T

jSf(X) 0 j0

TXx1,xnT

f(X)f0jx xj0,j0,jf(X)f0X在其对应的正规式中，如果存在j0T,使检验数j00, 并且对所有的iS,i,

,0例2minfx)x12x23x32xx12x2 4x4xx

2x4x 0,j1~x minf(x)x13x12 2x x 0,j1~x 1）存在j0T,j02）存在i0S, , 3）对所有的iS,i目标函数值优于当前基可行解的目标函数下面的证明是构造性的,中心思想就是完成换三.换基运1.纯形例 minf(x)x1x2x3x4x 6x5x

2x2 x42x5

j1~第二

M自动化学 一.两阶段 初始可行基的常用求法：两阶段法M两阶段nminf(x)cin

aijxj

(A中不含有单位可行 0,j1第一阶段:引入人工变量xn1,xn2,,求解辅助

minZ xja11x1

x

21 xx m1

xnmBx0

PnmIT bmT

是初始基可行Tx*

nmx*出现以下两种情形1：若x

中人工变量全为非基变量，这基向量全在p1,p2,,pn 情形2：若x*中存在某些人工变量为基变量，x*x（如

),这时原规划无可行解,故没有最优1反证：假设原规划有可1

x0

x0

x0

x0

x n x n

应是辅助规划的可行 假设可知，最优解x*中 原规划无最例5两阶段法minf(x)4x1x2x2x1+x2+2x3=s.t3x13x2+x3x 0 j1~x 解：第一引入人工x4x5求解辅助规minf(x)x42x1+x2+2x3+x4s.t3x13x2+x x5x j1~ 用单纯形法可以求出辅助规划最优解xxxxxxxxxxx4212104x5331013543007x40-1-2x111010-0-2xx3101-10--000--011j

(j1~ x*

,

,0,0)T32为辅助线性规划问题32并且人工变量x4,x 都是非基变量，x40x50第二阶段：建立原规划的初始单纯xxxxxx30-1x11000x301x210-0014故原问题的最优 x* f(x*)11/M例6M法求解例minf(x)4x1x2x2x1+x2+2x3s.t3x13x2+x3x j1~ 解：引入人工

求解辅助规minf(x)4x1x2x3Mx4Mx2x1+x2+2x3+x4s.t3x13x2+x x5x j1~ xx xxxx xx xx42 4x53 35M-4M- 3M- x40- -2x11 10- 0-x0- -x1 - 0 -M- -14xxx - - - -M+2/5-1故原问题的最优解x* f(x*)11/在大M方法中，求出辅