《工程优化设计-线性及二次规划》由会员分享，可在线阅读，更多相关《工程优化设计-线性及二次规划（90页珍藏版）》请在金锄头文库上搜索。
1、工程优化设计,黄正东二0一二年九月,内容提要,工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统,线性规划与二次规划,线性规划问题是一类优化问题,其约束函数和目标函数均为线性.,一般形式: min f(x)=cTx=c1x1+c2x2+cnxn s.t. h(x)=Hx= h1x1+h2x2+hnxn=0 g(x)=Gx =g1x1+g2x2+gnxn 0 xRn, hi Rp, gi Rq,线性规划,线性规划-举例,线性规划-举例,Ti 张力,l 可删去,线性规划-举例
2、,Wi, wi 是已知量。,线性规划与二次规划,线性规划问题是一类优化问题,其约束函数和目标函数均为线性.,(1)基本理论,1.线性规划的标准形式,一般形式: min f(x)=cTx=c1x1+c2x2+cnxn s.t. h(x)=Hx= h1x1+h2x2+hnxn=0 g(x)=Gx =g1x1+g2x2+gnxn 0 xRn, hi Rp, gi Rq,一.线性规划,线性规划与二次规划,2.基本可行解,标准形式: min f(x)=cTx=c1x1+c2x2+cnxn s.t. Ax= a1x1+a2x2+anxn=b x0, xRn, ARmn,Ax=0, A=B N= , BRm
3、m,B,N,方阵,|B|0,N不一定是方阵,Ax=BxB+NxN=b, xB=B-1(b- NxN)=B-1b- B-1NxNxT=xB xN=B-1b- B-1NxN, xN=- B-1N I xN+ B-1b 0,线性规划与二次规划,xT=xB xN=- B-1N I xN+ B-1b 0因此, xN自由变化, x=f(xN) 为所有可行解的显式表达.,2.1 基本解 令 xN=0, xT= B-1b 0 为基本解.2.2 基本可行解 xT= B-1b 00 为基本可行解.2.3 基本解个数 随着B的构成列不同, 可得不同的基本解, 从n列中 选取m列的选择方案有Cnm=n!/m!(n-m
4、)!个. 除去|B|=0的情况, 基本解个数最多是Cnm.,线性规划与二次规划,3. 解的几何意义,min 3x1-2x2s.t. -x1+x23 -2x1+x2 2 4x1+x2 16x10, x20,min 3x1-2x2s.t. -x1+x2 +x3 =3 -2x1+x2+x4=2 4x1+x2 +x5 =16xi0, i=1,2,5,(x1=0, x2=0),(x1=0, x2=16),基本解,但非可行,线性规划与二次规划,3. 解的几何意义,3.1 可行域是超多面体.3.2 等高线是超平面.3.3 最优解在顶点处.3.4 顶点个数有限.3.5 顶点是基本可行解.,f=6,f=0,f=
5、-5,线性规划与二次规划,4. 单纯形法,(1)算法基本思想,因为最优解在顶点上,基本可行解为顶点,所以,优化搜索可以沿着可行域的边界,从一个顶点到另一个顶点的方式进行,每一步使目标函数值减小.由于顶点个数有限,在有限步内可达到最优解.,1.1 最优性检查,xT=xB xN=B-1b- B-1NxN, xN,f(x) =cTx=cBTxB+cNTxN= cBTB-1b-B-1NxN+cNTxN =cBTB-1b+(cNT-B-1N)xN,线性规划与二次规划,1.1 最优性检查,f(x) =cBTB-1b+(cNT-cBTB-1N)xN,这样, 如果cNT-cBTB-1N0, 因为xN0使f(x
6、)增加, 于是, 当前x是最优解.,设 f(x) =cBTB-1b+(cNT-cBTB-1N)xN=c0 +c xN,1.2 基本可行解更新,f(x) = c0+cTxN, c=c1,c2,cp,cNT取cp0, jB; 最先到零：xj=bjp-xpajp=0 写成一维搜索格式是: Xk+1=Xk+xpdk, dk=(-a, 0,0,1,0,0)T.,ajp=0 约束.,1.2 基本可行解更新,Xk=* * * *, 0 0 0 0,dk,xp,Xk+1= * * 0 *, 0 * 0 0 ,Xk+1=Xk+xpdk,随xp增加, x3k+1 最先变为零,xk+1= * * 0 *, 0 *
7、0 0 ,出基本变量,入基本变量,(2)算法流程,1.给定一个初始基本可行解x(1)=B1-1b, 0,记k=1.2.计算cNk=cNk-NkTBk-1cBk.3.最优性检验:计算cpk=mincjk | jNk, 如果cpk0, 则x(k)为最优 解,停止.否则,选xkp为入基变量.4.确定出基本变量:dk=Bk-1Nkep= x(k)=Bk-1b= , 若对所有jBk,dkj0, 则问题有 无界最优解; 否则,出基变量是满足下式的q: -xkq/dkq= min-xkj/dkj, dkj min=2/1 - 即选出分量 q=4. 注意:d=-B-1Nep,所以 dj=-ajp,p,q,x1
8、不变，x2变化引起x4变化,(3)单纯形法的表计算形式举例,线性规划与二次规划,相减,相减,2进,4出,将 cB=(c3, c2, c5)=(0, -3, 0)移至表前.,用消元法将x2变为基变量,(3)单纯形法的表计算形式举例,线性规划与二次规划,更新f系数: c新=c旧-cBTAi, Ai为列向量,第一轮完,(3)单纯形法的表计算形式举例,线性规划与二次规划,更新f系数: c新=c旧-cBTAi, Ai为列向量,第二轮完,(3)单纯形法的表计算形式举例,线性规划与二次规划,(3)单纯形法的表计算形式举例,线性规划与二次规划,更新f系数: c新=c旧-cBTAi, Ai为列向量,第三轮完,因为c=(0 0 2 0 1)0, 所以,结束, -f=22, f=-22.x*=(13/5, 28/5, 0, 8/5,0),线性规划与二次规划,min -2x1-3x2s.t. -x1+x2 +x3 =3 -2x1+x2+x4=2 4x1+x2 +x5 =16xi0, i=1,2,5,
