?100??1??1???1???1?
E0?1p2??010????????001????1????1??(4) 确定出基变量
?bi??150,i?1,2,3??min?根据θ规则，求出?r?min??1?ai2?为出基变量。于是得到新的基矩阵E1??p3
(5) 计算新的基矩阵的逆阵
270180?80|r?3,，x5被确定??1?1p4p2?，相应的cE1??0090?。
?101??10?1????01?3? ?1E1?1?(E0E1)?1??013???????001???001???x3??10?1??150??70???E?1x??01?3??270???30?
xE1??x41E0???????????x2???001????80????80???10?1????0090? T?1cE090??01?31E1??0????001??用E1代替E0，重复步骤(2)~(5)。 (6) 计算各非基本变量的判别数
?1?1?1?10?1??2???1??25 T?1?1?c1?cE090??01?30E1p1?25??0??????001????0???10?1??0??01?1??0???90 T?1???5?c5?cEEp?0?0090115??????001????1??(7) 再确定进基变量
?1?25,?5??90???1，对应非基本变量x1，确定x1为进基变量。同时计算 根据max??10?1??2??2???1???1?
E1?1p1??01?3????????001????0????0??(8) 再确定出基变量
根据θ规则，求出?r?min??bi??70,i?1,2,3??min??2?ai1?30180?30|r?2，x4被确定为??0?1出基变量。于是得到新的基矩阵E2??p3
(9) 计算新的基矩阵的逆阵
p1T2590?。 p2?，相应的cE2??0?121??1?25????01?3? ?1E2??013??????1??001???00?xE2?x1??1?25??150??10???E?1x??01?3??270???30? ??x2E0?2?????????1??x3???00???80????80???1?1?25????02515? T?1cE2590??01?32E2??0???1??00??1?25??0??01?3??1???25 T?1???3?c4?cEEp?0?02590224?????1??00???0???1?25??0???0???15 T?1?5?c5?cE2590??01?32E2p5?0??0?????1??00???1??因判别数ζj均小于0，迭代结束。最优解为x??30801000?,fmax?7950。
T3.5 优化工具箱
用MATLAB优化工具箱求线性规划的函数linprog（）来求解此问题。
线性规划问题数学模型 min CTX s.t. AX≤B AeqX=Beq Lb≤X≤Ub
其中：C，X，B，Beq，Lb，Ub为向量；A，Aeq为矩阵 函数输入变量
X= linprog（C,A,B）[]
X= linprog（C,A,B,Aeq,Beq） [] X= linprog（C,A,B, Aeq,Beq,Lb,Ub） X= linprog（C,A,B ,Aeq,Beq,Lb,Ub,x0）
X= linprog（C,A,B, ,Aeq,Beq,Lb,Ub,x0,options）
函数左端输出变量 [x]=linprog()
[x,fval]= linprog()
[x,fval,exitflag]= linprog()
[x,fval,exitflag,output]= linprog()
[x,fval,exitflag,output,lambda]= linprog()
X返回目标函数最优解,fval返回目标函数最优值,exitflag终止迭代的标志（整数值）,output输出迭代次数,lambda解x的拉格朗日乘子 exitflag=1 exitflag=0 exitflag=-2 exitflag=-3
output, algorithm output, funcCount output,iterations output,message
第4章 一维搜索方法
是指求解一维目标函数f(x)的极小点和极小值的数值迭代方法，可归纳为单变量函数的极小化问题。虽然优化设计中大部分问题是多维问题，一维问题的情况较少，但是一维优化方法是优化方法中最基本的方法，在数值迭代过程中都要进行一维搜索。另外，很多多维优化问题最终归结为一维优化问题来处理。
如果确定了迭代点x(k)及其搜索方向d(k)，那么迭代所得的新点x(k+1)将取决于步长a(k)，即
x(k+1)= x(k)+ a(k) d(k)，k=0，1，2，… (4.1)
由式4.1可知，不同的步长a(k)会得到不同的迭代点和不同的目标函数值f(x(k+1))。一维优化问题的目的是在既定的迭代点x(k)和搜索方向d(k)下寻求最优步长a(k)，使迭代产生的新点x(k+1)的函数值最小，即
min f[x(k)+ a(k) d(k)]
在初始迭代点x(k)和搜索方向d(k)确定后，就把求解多维优化问题的极小值变成求解一个自变量即最优步长a的最优值的一维问题了。即求一元函数 f(x(k+1))=f(x(k)+ a d(k))=φ( a) (4.2) 的极值问题。
一维搜索的优化方法很多，常用进退法、黄金分割法和二次插值法。 一维搜索方法的步骤：
(1) 确定初始搜索区间[a,b]，即最优步长a所在的区间[a,b]。搜索区间应为单峰区间，并且在区间内目标函数应只有一个极小值。
(2) 在搜索区间[a,b]内寻找最优步长a，使目标函数式4.2达到极小值。
4.1 确定初始单峰区间的方法—进退法
原理
进退法也称为外推法，是一种通过比较函数值大小来确定单峰区间的方法。由单峰函数的性质可知，在极小点左边函数值应严格下降，而在极小点右边函数值应严格上升。因此，从某一种给定的初始点x0出发，以初始步长a沿着目标函数值的下降方向，逐步前进（或后退），直至找到相继的3个计算点的函数值出现“大-小-大”的趋势为止。 利用进退法确定搜索区间[a,b]的步骤如下： (1) 任取x0，步长a>0，取x1=x0+a。 (2) 后退运算。φ(x1)>φ(x0)，则令a=2a（步长加倍），x2=x0-a。分以下两种情况：若φ(x2)<φ(x0)，则令x1=x0，x0=x2。重复(2)；若φ(x2)>φ(x0)，则停止a=x2，b=x1。 (3) 前进运算，若φ(x1)<φ(x0)，则令a=2a（步长加倍），x2=x1+a。若φ(x2)<φ(x1)，则令x0=x1，x1=x2，重复(3)；若φ(x2)>φ(x1)，则停止，a=x0，b=x2。 程序框图
4.2 黄金分割法
1 基本原理
又称为0.618法，它通过不断缩短搜索区间的长度来寻求一维函数f(x)的极小点。对于单峰函数f(x)，在其极值存在的某个区间[a,b]内取若干点，计算这些点的函数值并进行比较，总可以找到极值存在的更小区间。在这更小区间内增加计算点，又可以讲区间进一步缩小。当
区间足够小，即满足精度要求时，就可以用该区间内任意一点的函数值来近似表达函数的极值。
设单变量函数f(x)在区间[a,b]上有定义，若存在一点x*(a b)，使得f(x)在区间[a,x*]上严格单调减，f(x)在区间[x*,b]上严格单调增，则称f(x)是区间[a,b]上的（下）单峰函数。显然x*是f(x)在区间[a,b]上的唯一的极小值点。
根据（下）单峰函数所具有的性质，对在某区间[a,b]上的（下）单峰函数f(x)可采用黄金分割法搜索其在区间[a,b]内得极小值点。 2 计算方法
设区间[a,b]的长度为L，在区间内取点λ1，将区间分割为两部分，线段aλ1的长度记作λ，并满足
?L?L????q2且2??L??
?1?5，取正根2由上式有??L??L?0，两边同除L2，得q2+q-1=0，则有q?q?5?1?0.6180339887。q称为区间收缩率，它表示每次缩小所得的新区间长度与缩2小前区间长度之比。
在一维搜索时，在区间内取两对称点λ1和λ2，并满足
q??2L??1L??2??0.618 ?2?2显然，经一次分割后，所保留的极值存在的区间要么是[a, λ2]，要么是[λ1，b]。而经k次分割后，所保留的区间的长度为??qL?(0.618)L。
由于区间收缩率q是一个近似值，每次分割必定带来一定的舍入误差，因此，分割次数太多
时计算会失真。经验表明，黄金分割的次数k应限制在11以内。
kkk4.3 拉格朗日插值多项式
是一种显式公式,它将pn(x)表示为一组插值基函数的线性组合。 1 线性插值
设函数y=f(x)在给定的互异节点x0，x1上的函数值分别为y0=f(x0)，y1=f(x1)，若能构造一个函数
p1(x)=a+bx (4.3)
使它满足p1(x0)=y0，p1(x1)=y1，则式4.3所示的插值问题称为线性插值。
线性插值的几何意义是过曲线y=f(x)上的两点(x0,y0)和(x1,y1)作一直线，用p1(x)近似值代f(x)。
对于给定的两点(x0,y0)和(x1,y1)，某一点x(x0 p1(x)?y0?记 y1?y0x?x1x?x0(x?x0)?y0?y1 x1?x0x0?x1x1?x0