最优化方法南京邮电大学理学院前言一、什么是最优化最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。二、包含的内容按照优化思想分为经典方法与现代方法。经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。我们学习的内容主要是经典的最优化方法。内容包括线性规划及其对偶规划，无约束最优化方法、约束最优化方法等主要内容。三、学习方法1、认真听讲，课后及时复习巩固，并主动完成课后习题。2、多看参考书，通过不同学者的讲述，全方位理解最优化方法的思想方法和应用，特别是计算方法。3、学以致用，通过最优化方法的学习，培养研究生数学建模的能力和解决实际问题的能力。大家可以尝试对于一些实际问题，先建立数学模型，转化为数学问题，通过一些算法解决。四、主要参考书教材：解可新、韩健、林友联：最优化方法（修订版），天津大学出版社，2004年8月。其它参考书：1.蒋金山，何春雄，潘少华：最优化计算方法，广州：华南理工大学出版社，2007年10月。2.谢政，李建平，汤泽滢：非线性最优化。长沙：国防科技大学出版社，2003年9月。3.李董辉等：数值最优化。北京：科学出版社，2005年。4.谢政，李建平，陈挚：非线性最优化理论与方法。北京：高等教育出版社，2010年1月。目录第一章最优化问题概述第二章线性规划第三章无约束最优化方法第四章约束最优化方法第一章最优化问题概述§1.1最优化问题的数学模型与基本概念例1.1.1运输问题设有m个水泥厂A1,A2,…,Am,年产量各为a1,a2,…,am吨.有k个城市B1,B2…,Bk用这些水泥厂生产的水泥,年需求量b1,b2,…,bk吨.再设由Ai到Bj每吨水泥的运价为cij元.假设产销是平衡的,即:试设计一个调运
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
,在满足需要的同时使总运费最省.A1由题意可画出如下的运输费用图:B2AmB1A2Bk产量需求量设Ai→Bj的水泥量为xij,已知Ai→Bj单价为cij,单位为元,则总运费为:数学模型:注:平衡条件作为已知条件并不出现在约束条件中.例1.1.2生产计划问题设某工厂有m种资源B1,B2,…,Bm,数量分别为:b1,b2,…,bm,用这些资源产n种产品A1,A2,…,An.每生产一个单位的Aj产品需要消耗资源Bi的量为aij,根据
合同
劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载
规定,产品Aj的量不少于dj.再设Aj的单价为cj.问如何安排生产计划,才能既完成合同,又使该厂总收入最多?假设产品Aj的计划产量为xj.由题意可画出如下的生产与消耗的关系图:B1B2BmAnA2A1消耗数学模型例1.1.3指派问题设有四项任务B1,B2,B3,B4派四个人A1,A2,A3,A4去完成.每个人都可以承担四项任务中的任何一项,但所消耗的资金不同.设Ai完成Bj所需资金为cij.如何分配任务,使总支出最少?设变量指派Ai完成bj不指派Ai完成bj则总支出可表示为:数学模型:例1.1.4数据拟合问题在实验数据处理或统计资料分析中常遇到如下问题.设两个变量x和y,已知存在函数关系,但其解析表达式或者是未知的或者虽然为已知的但过于复杂.设已取得一组数据:(xi,yi)i=1,2,…,m.根据这一组数据导出函数y=f(x)的一个简单而近似的解析表式.最小二乘法解这种问题常用的方法是最小二乘法,以一个简单的函数序列j1(x),j2(x),···,jn(x)为基本函数.一般选取1,x,x2,···,xn为基本函数,即以作为近似表达式.最小二乘法系数的选取要使得下面得平方和最小:因此,数据拟合问题得数学模型为其中xi,yi(i=1,2,…,m)及jj(x)(j=0,1,…,n)为已知.最优化问题最优化问题的一般形式为:(1.1)(目标函数)(1.3)(不等式约束)(1.2)(等式约束)其中x是n维向量.在实际应用中,可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式.我们总是讨论P:相关定义定义1.1.1(可行解)满足约束条件(1.2)和(1.3)的x称为可行解,也称为可行点或容许点.定义1.1.2(可行域)全体可行解构成的集合称为可行域,也称为容许集,记为D,即:D={x|hi(x)=0,i=1,···,m,gj(x)≥0,j=1,···,p,x∈Rn}.若hi(x),gj(x)为连续函数,则D为闭集.相关定义定义1.1.3(整体最优解)若x*∈D,对于一切x∈D恒有f(x*)≤f(x),则称x*为最优化问题(P)的整体最优解.若x*∈D,x≠x*,恒有f(x*)
0}.当x≠x*时,若上面的不等式为严格不等式则称x*为问题(P)的严格局部最优解.显然,整体最优解一定是局部最优解,而局部最优解不一定是整体最优解.x*对应的目标函数值f(x*)称为最优值，记为f*.相关定义求解最优化问题(P),就是求目标函数f(x)在约束条件(1.2),(1.3)下的极小点,实际上是求可行域D上的整体最优解.但是,在一般情况下,整体最优解是很难求出的,往往只能求出局部最优解.在求解时需要范数的概念，以下给出定义。向量范数定义1.1.5如果向量x∈Rn的某个实值函数||x||,满足条件(1)||x||≥0(||x||=0当且仅当x=0)(正定性);(2)||ax||=|a|·||x||(对于任意a∈R);(3)||x+y||≤||x||+||y||(三角不等式);则称||x||为Rn上的一个向量范数.常用的向量范数1-范数2-范数(欧氏范数)∞-范数p-范数∞-范数是p-范数的极限常用的向量范数对向量x=(1,-2,3)T,有||x||p是p的单调递减函数.最优化问题的分类根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题.根据目标函数和约束函数的函数类型分类:线性最优化问题,非线性最优化问题,二次规划,多目标规划,动态规划,整数规划,0-1规划.§1.2最优化问题的一般算法迭代算法迭代算法选取一个初始可行点x0∈D,由这个初始可行点出发,依次产生一个可行点列:x1,x2,···,xk,···,记为{xk},使得某个xk恰好是问题的一个最优解,或者该点列收敛到问题的一个最优解x*.下降算法在迭代算法中一般要求f(xk+1)≤f(xk).可行点列的产生在xk处求得一个方向pk(下降方向),在射线xk+apk(a>0)上求一点:xk+1=xk+akpk使得f(xk+1)≤f(xk).其中ak称为步长.定义1.2.1(下降方向)在点xk处,对于方向pk≠0,若存在实数b>0,使得任意的a∈(0,b),有:f(xk+apk)0,使得对任意的a∈(0,b),有:xk+apk∈D,则称pk为点xk处关于区域D的可行方向.对于D的内点(存在邻域包含于D),任意方向可行,对于边界点(任意邻域既有D的点也有不在D中的点),则有些方向可行,有些方向不可行.若下降方向关于域D可行,则称为可行下降方向.最优化问题的算法的一般迭代格式给定初始点x0,令k=0.(1)确定xk处的可行下降方向pk;(2)确定步长ak,使得f(xk+akpk)0是预先给定的.§1.3二维最优化问题的几何解释理论分析二维最优化问题的目标函数z=f(x1,x2)表示三维空间R3中的曲面.在空间直角坐标系O-x1x2z中,平面z=c与曲面z=f(x1,x2)的交线在0-x1x2平面上的投影曲线为:取不同的c值得到不同的投影曲线,每一条投影曲线对应一个c值,称投影曲线为目标函数的等值线或等高线.理论分析求目标函数z=f(x1,x2)在可行域D上的极小点,是在与可行域D有交集的等值线中找出具有最小值的等值线.也就是在可行域D上沿着f(x1,x2)的负梯度方向或某种下降方向上找取得最小值c的点.例1.3.1解首先画出可行域D,目标函数的等值线是以点(1,2)为圆心的一族圆.f(x1,x2)的梯度为例1.3.1负梯度方向（下降方向）指向等值线圆心,所以等值线与可行域D的边界相切的点x*=(1/2,3/2)T是此问题的最优解,目标函数的最优值为1/2.例1.3.2解首先画出可行域D的图形.D为凸多边形ODEFGO.再以c为参数画出目标函数的等值线2x1+3x2=c.例1.3.2目标函数c的值由小到大逐渐增加,等值线沿着目标函数的梯度方向平行移动.当移动到点E时,再移动就与可行域D不相交了,所以顶点E就是最优点,最优值为14.例1.3.3解如图所示,可行域只能是圆弧ABE,其中点A和点E是等值线–x1–x2+1=0和圆x12+x22-9=0的交点.注意到等值线是平行的抛物线,图中画出了几条目标函数的等值线.容易看出B点是最优点,所以最优解是(0,-3)T,最优值为-3.§1.4一维搜索问题描述已知xk,并且求出了xk处的可行下降方向pk,从xk出发,沿方向pk求目标函数的最优解,即求解问题:设其最优解为ak,于是得到一个新点xk+1=xk+akpk所以一维搜索是求解一元函数f(a)的最优化问题(也叫一维最优化问题).我们来求解令()=0,求出的值。在[a,b]内任取x10,step1令x2=a+0.618(b-a),f2=f(x2);step2令x1=a+0.382(b-a),f1=f(x1);step3若|b–a|f2,则a=x2,x1=x2,f1=f2,转step5;step5令x2=a+0.618(b–a)，f2=f(x2),转step3.例1.4.1用黄金分割法求函数f(x)=x2-x+2在区间[-1,3]上的极小值，要求区间长度不大于原始区间长的0.08。用0.618法求解例1.4.1的数据表迭代次数[a,b]x1x2f1f2|b-a|0,x1=x0+Dx.x0下面分两种情况讨论.(1)f(x1)≤f(x0)x1对应着图上用红线标出的一部分进退法(寻找下单峰区间)x0(1)f(x1)≤f(x0)此时x1取值小,我们加大步长向右搜索,取Dx=2Dx,x2=x1+Dx若f(x1)≤f(x2),则我们要找的区间即为[x0,x2]x1x2Dx2Dx进退法(寻找下单峰区间)x0(1)f(x1)≤f(x0)若f(x1)>f(x2),则我们所取的步长偏小.令x1=x2,Dx=2Dx,x2=x1+Dx继续往下判断,直到满足f(x1)≤f(x2).x1x2Dx2Dxx1x2进退法(寻找下单峰区间)x0(2)f(x1)>f(x0)此时x1取值大,我们缩小步长向x1左边搜索,取Dx=Dx/2,x2=x1,x1=x2-Dx若f(x1)≤f(x0),则我们要找的区间即为[x0,x2]否则继续缩小区间,直到满足f(x1)≤f(x0).x1x2x11.4.2二分法若f(x)的导数存在且容易计算,则线性搜索的速度可以得到提高,下面的二分法每次将区间缩小至原来的二分之一.设f(x)为下单峰函数,若f(x)在[a,b]具有连续的一阶导数,且f’(a)<0,f’(b)>0取c=(a+b)/2,若f’(c)=0,则c为极小点;若f’(c)>0,则以[a,c]代替[a,b]作为新区间;若f’(c)<0,则以[c,b]代替[a,b]作为新区间.1.4.3抛物线法在求一元函数的极小点问题上,我们可以利用若干点处的函数值来构造一个多项式,用这个多项式的极小点作为原来函数极小点的近似值.抛物线法就是一个用二次函数来逼近f(x)的方法,这也是我们常说的二次插值法.设在已知的三点x1f0,f00,使或用下面更强的条件代替(1.7)式:Wolfe原则关于满足Wolfe原则的步长ak的存在性:定理1.4.2设f(x)有下界且gkTpk<0.令m∈(0,1/2),s∈(m,1),则存在区间[c1,c2],使得任意的a∈[c1,c2]均满足式(1.6)和(1.7)(也满足(1.8)).不精确一维搜索Wolfe算法问题:设已知xk和下降方向pk,求问题的近似值ak,使ak满足(1.6)和(1.7).算法1.4.6不精确一维搜索Wolfe算法step1给定m∈(0,1),s∈(m,1),令a=0,b=∞,a=1,k=0;step2xk+1=xk+apk,计算fk+1,gk+1;若a满足(1.6)和(1.7)式,则令ak=a;若a不满足(1.6)式,则令k:=k+1,转step3;若a不满足(1.7)式,则令k:=k+1,转step4;step3令转step2step4令转step2.step1给定m=0.1,s=0.5,令a=0,b=∞,a=1,j=0;Wolfe准则(例1.4.2)用不精确一维搜索求Rosenbrock函数f(x)=100(x2-x12)2+(1-x1)2在点xk=(0,0)T处沿方向pk=(1,0)T的近似步长ak.解因为fk–fk+1=1–100=–99<–magkTpk=0.2所以(1.6)式成立。转step3step2xk+1=xk+apk=(1,0)T,fk+1=f(1,0)=100step3令b=1,a=(a+a)/2=(1+0)/2=0.5,转step2.重新计算xk+1.迭代四次得到满足Wolfe条件的步长ak=0.125xk+1=xk+akpk=(0.125,1)T.
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
一维搜索的方法利用导数的方法仅用函数值的方法二分法(算法1.4.4)精确方法不精确方法Fibonacci方法(算法1.4.1)黄金分割法(算法1.4.2)求初始区间的方法进退法(算法1.4.3)二次插值法(算法1.4.5)Wolfe算法(算法1.4.6)第二章线性规划§2.1凸集与凸函数凸集定义2.1.1设集合DRn,若对于任意点x,y∈D,及实数a,0≤a≤1,都有ax+(1-a)y∈D,则称集合D为凸集.常见的凸集:空集(补充定义),整个欧式空间Rn,超平面H={x∈Rn|a1x1+a2x2+…anxn=b}半空间H+={x∈Rn|a1x1+a2x2+…anxn≥b}凸集的例例2.1.2超球||x||≤r为凸集证明设x,y为超球中任意两点,0≤a≤1,则有||ax+(1-a)y||≤a||x||+(1-a)||y||≤ar+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.凸集的性质(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j∈J)是凸集,则它们的交集D={x|x∈Dj,j∈J}是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD={y|y=bx,x∈D}.凸集的性质(iii)设D1,D2是凸集,则D1与D2的和集D1+D2={y|y=x+z,x∈D1,z∈D2}是凸集.注:和集与并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T|x∈R}表示x轴上的点,D2={(0,y)T|y∈R},表示y轴上的点.则D1∪D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集推论凸集的线性组合是凸集.定义2.1.2设xi∈Rn,i=1,…,k,实数li≥0,则称为x1,x2,…,xk的凸组合.容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.两点的凸组合三点的凸组合多点的凸组合极点定义2.1.3设D为凸集,x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得x=ay+(1-a)z则称x为D的极点.凸集极点凸集极点极点例D={x∈Rn|||x||≤a}(a>0),则||x||=a上的点均为极点证明:设||x||=a,若存在y,z∈D及a∈(0,1),使得x=ay+(1-a)z.则a2=||x||2=（ay+(1-a)z,ay+(1-a)z）≤a2||y||2+(1-a)2||z||2+2a(1-a)||y||||z||≤a2不等式取等号,必须||y||=||z||=a,且（y,z）=||y||||z||,容易证明y=z=x,根据定义可知,x为极点.凸函数定义2.1.4设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,及任意的a∈[0,1]都有f(ax+(1-a)y)≤af(x)+(1-a)f(y)则称函数f(x)为凸集D上的凸函数.凸函数定义2.1.5设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,x≠y,及任意的a∈(0,1)都有f(ax+(1-a)y)f(x)+f(x)T(y-x)二阶条件设在开凸集DRn上f(x)可微,则(i)f(x)是D内的凸函数的充要条件为,在D内任一点x处,f(x)的Hesse矩阵G(x)半正定,其中(ii)若在D内G(x)正定,则f(x)在D内是严格凸函数.凸规划定义2.1.6设DRn为凸集,则f(x)为D上的凸函数,则称规划问题minf(x)s.t.x∈D为凸规划问题.定理2.1.5(i)凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.(ii)若f(x)是DRn上的严格凸函数,且凸规划问题minf(x)s.t.x∈D的整体极小点存在,则整体极小点唯一.定理2.1.5证明(思路)(i)x*为局部极小点,若存在x0使得f(x0)0.假设x不是基可行解,于是p1,p2,···,pk线性相关,即有一组不全为0的数a1,a2,···,ak,使得a1p1+a2p2+···+akpk=0(2.4)又x∈D,所以x1p1+x2p2+···+xkpk=b(2.5)用e>0乘(2.4)再与(2.5)相加减得(x1+ea1)p1+(x2+ea2)p2+···+(xk+eak)pk=b(x1–ea1)p1+(x2–ea2)p2+···+(xk–eak)pk=b令u=(x1+ea1,x2+ea2,···,xk+eak,0,···,0)Tv=(x1–ea1,x2–ea2,···,xk–eak,0,···,0)T则有Au=b,Av=b,当e充分小时,可使u≥0,v≥0.因此,当e充分小时,u,v都是(LP)的可行解,且u≠v,x=1/2u+1/2v,这与x是D的极点相矛盾.因此x是基可行解.推论:线性规划(LP)的可行域D={x|Ax=b,x≥0}最多具有有限个极点(p1,p3,p4),(11,0,-6,11,0)T不可行(p1,p3,p5),(0,0,5,0,22)T退化(p1,p4,p5),(5,0,0,5,12)T非退化(p2,p3,p4),(0,11,-6,11,0)T不可行(p2,p3,p5),(0,0,5,0,22)T退化(p2,p4,p5),(0,5,0,5,12)T非退化(p3,p4,p5),(0,0,5,0,22)T退化前例中三个退化的基可行解对应着同一个极点(基可行解与极点不是一一对应)有可行解有基可行解定理2.3.3若线性规划(LP)存在可行解,则它一定存在基可行解.证明设x=(x1,x2,···,xn)T是(LP)的可行解.不失一般性,设其前k个分量为正,其余分量为零.则有若p1,p2,···,pk线性无关,则x为基可行解;若p1,p2,···,pk线性相关,即有一组不全为0的数a1,a2,···,ak,使得a1p1+a2p2+···+akpk=0与定理2.3.2的证明类似,作x1=x+ea,x2=x-ea,其中a=(a1,···,ak,0,···,0)T当e充分小时,x1,x2是线性规划(LP)的可行解.选择适当的e,使得xj+eaj,xj-eaj(j=1,···,k)中至少有一个为零,而其余的值大于零.这样得到一个新的可行解,其中非零分量的个数比x至少减少一个.如果新的可行解正分量对应的列向量线性无关,则问题得证.否则重复上面的过程直到正分量对应的列向量线性无关为止.有最优解有最优的基可行解定理2.3.4若线性规划(LP)存在最优解,则必存在基可行解是最优解.证明:设x是最优解.若x不是基可行解,作出两个新的可行解:x+ea,x-ea,对应的目标函数值为cTx+ecTa与cTx-ecTa.由于x是最优解,cTx+ecTa≥cTx;cTx-ecTa≥cTx.因此cTa=0.于是,当e>0充分小时,x+ea,x-ea也是可行最优解.仿照定理2.3.3的证明,可以得到最优的基可行解.单纯形方法的思路找出一基可行解(极点)若其不是最优,找到一个相邻极点新的目标函数值不大于原目标函数值经过有限次迭代给出最优解或判断无最优解单纯形方法的思路(几何)线性规划min-72x1-64x2s.t.x1+x2+x3=5012x1+8x2+x4=4903x1+x5=100x1,x2,x3,x4,x5≥0的等价形式为min-72x1-64x2s.t.x1+x2≤5012x1+8x2≤4903x1≤100x1,x2≥0OABCD梯度方向x2=0x1=0x5=0x3=0x4=0等值线基可行解OOABCDx2=0x1=0x5=0x3=0x4=0基可行解AOABCDx2=0x1=0x5=0x3=0x4=0基可行解BOABCDx2=0x1=0x5=0x3=0x4=0基可行解C是最优解单纯形方法的思路(代数)例考察线性规划min-72x1-64x2s.t.x1+x2+x3=5012x1+8x2+x4=4903x1+x5=100x1,x2,x3,x4,x5≥0以x3,x4,x5为基变量,容易得到基可行解(0,0,50,490,100)T.由于x1的价格系数为负数,增加x1的取值可以使得目标函数值减少.类似的,我们也可以增加x2的取值,使得目标函数值减少.由于-72负得多一些,我们先增加x1.单纯形方法的思路(代数)min-72x1-64x2s.t.x1+x2+x3=5012x1+8x2+x4=4903x1+x5=100x1,x2,x3,x4,x5≥0x1可以增加多少?x1≤50x1≤490/12x1≤100/3因此x1的最大取值为min(50,490/12,100/3)=100/3此时x5的取值为0,x5“出基”.单纯形方法的思路(代数)根据3x1+x5=100,我们将原来的线性规划改写如下min-64x2+24x5-2400s.t.x2+x3-x5/3=50/38x2+x4-4x5=90x1+x5/3=100/3x1,x2,x3,x4,x5≥0此时,基变量为x1,x3,x4,基可行解为(100/3,0,50/3,90,0)T.若x2(其系数为负)的取值增加,可以使得目标函数值减少x2≤50/3x2≤90/8因此x2的最大取值为min(50/3,90/8)=90/8x4“出基”.单纯形方法的思路(代数)此时,x4,x5是非基变量,将原规划化为min8x4-8x5-3120s.t.x3-x4/8+x5/6=65/12x2+x4/8-x5/2=45/4x1+x5/3=100/3x1,x2,x3,x4,x5≥0解为(100/3,45/4,65/12,0,0)T.x5最大可以取为65/2.对应的,线性规划可以转化为下页的形式单纯形方法的思路(代数)min48x3+2x4-3380s.t.6x3-3x4/4+x5=65/2x2+3x3-x4/4=55/2x1-2x3+x4/4=45/2x1,x2,x3,x4,x5≥0对应的解为(45/2,55/2,0,0,65/2)T.此时,目标函数中非基变量的系数为正,因此目标函数的取值不能再减少.最优值为-3380.单纯形方法的思路(代数)单纯形方法求解线性规划,首先找出一个基可行解.将目标函数写成非基变量的线性组合(再加上一个常数)的形式.如果组合的系数全部非负,则已经找到最优解.如果组合的系数中有负数,从中选取一个变量(“进基”)来增加取值,可以使得函数值减少.根据约束条件,可以控制增加的范围.在进基变量取最大值时,有一个变量出基,从而得到另一个基可行解.重复上面的过程,可以求得最优解.§2.4单纯形方法设线性规划R(A)=m，x1,x2,…,xm是基变量，而xm+1,…,xn是非基变量，并记基矩阵B=(p1,p2,…,pm),N=(pm+1,…,pn),A=(B,N),则上述线性规划问题化为进一步可以将线性规划问题转化为以下形式
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
式线性规划与基变量x1,···,xm对应的规范式线性规划与基变量xj1,···,xjm对应的规范式S={j1,···,jm},T={1,2,···,n}\S2.4.1基可行解是最优解的判断准则在规范式中,令非基变量xj=0,j∈T,得到一个基解x0=(x1,···,xn)T,其中如果b’j≥0(j∈S),则x0是基可行解.判别数定义2.4.1令,则称为变量xj的判别数.写成向量形式为其中pj为A的列向量,pj’为B-1A的列向量最优性条件目标函数中各个变量的系数就是判别数.在规范式中,定理2.4.1设x0是线性规划(LP)对应于基B=(pj1,···,pjm)的基可行解.与基变量xj1,···,xjm对应的规范式中,若x0的全体判别数非负,则x0是(LP)的最优解.判断无最优解定理2.4.2设x0是线性规划(LP)对应于基B=(p1,···,pm)的基可行解.与基变量x1,···,xm对应的规范式中,若存在sk<0,且对所有的i=1,2,···,m有aik’≤0,则线性规划(LP)无最优解.判断无最优解证明:令d=(–a1k’,···,–amk’,0,···,0,1,0,···,0)T(第k个分量为1),y=x0+ld,则由于aik’≤0,bi’≥0,i=1,···,m,所以对任意l>0,y是可行解.y对应的目标函数值为f=f0+skl→–∞(l→+∞时).目标函数在可行域无解,(LP)无最优解.基可行解的转换从上面定理的证明中可以看出,如果某个判别数为负时,可以构造新的可行解,使得目标函数值减少.1.确定进基变量负的判别数对应的变量都可以作为进基变量.一般的,若sk=min{sj|sj<0}则以xk为进基变量.基可行解的转换2.确定离基变量设已确定xk为进基变量,根据以及xj=0,(j=m+1,···,n,j≠k),得到xi=b’i-a’ikxk,i=1,2,···,m我们选取xk=max{xk|xi=b’i-a’ikxk≥0,i=1,2,···,m}显然xk=min{qi=b’i/a’ik|a’ik>0}=b’l/a’lk=ql,此时,我们选择xl为离基变量.单纯形方法如果线性规划是非退化的,则按照上面的方法(进基,离基)迭代一次后,目标函数值有所下降.经过有限次迭代之后,一定可以得到一个基可行解,使得其所有判别数非负(得到最优解),或者其有一个判别数是负的,但对应列向量的所有分量非正(线性规划无最优解).这种求解线性规划的方法称为单纯形方法.显然，xj=bij=1,…,m;xi=0i=m+1,…,n是基本可行解对应的基是单位矩阵。以下是初始单纯形表：n其中：f=f0+∑cjxii=m+1mi=0i=1,…,mj=cj-∑ciaij为检验数i=1j=m+1,…,n建立实用单纯形表=单纯形法的迭代步骤单纯形法的迭代的主要工作是将原来的规范式写为新的规范式.进基变量离基变量主元=通过初等行变换将主元变为1通过初等行变换将主元所在列其它元素变为0得到新的规范式§2.5单纯形表例2.5.1用单纯形法解线性规划minf=–2x1–3x2s.t.x1+x2≤6x1+2x2≤8x1≤4x2≤3x1,x2≥0解引入松弛变量将原问题化为标准型minf=–2x1–3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x6≥0显然p3,p4,p5,p6是一组基,标准型线性规划中的系数以及这一组基可用表格的形式给出minf=-2x1-3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x6≥0目标函数中的系数基向量基变量的价格系数右端系数约束等式的系数cj-2-30000p1p2p3p4p5p6Bp3p4p5p6cB0000b6843111000120100100010010001第一步的判别数:由于在此例中基变量的价格系数均为0,所以判别数就是价格系数.cj-2-30000cBBbp1p2p3p4p5p60000p3p4p5p66843111000120100100010010001sj-2-30000进基变量:s2=-3=min{sj|sj<0},所以x2为进基变量离基变量的判别标准:qi=bi/ai2(ai2>0)qi64/3离基变量:q6=minqi,所以x6为离基变量()-33标出主元第二步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60000p3p4p5p668431110001201001000100(1)000164/3sj-2-30000p3p4p5p2写出基向量(p6换成p2)归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变)3010001写出价格系数000-3消去:用初等行变换将主元所在列其它元素消为0p5所在行不变4100010p2所在行乘以-1加到p3所在行310100-1p2所在行乘以-2加到p4所在行210010-2p2所在行乘以3加到判别数所在行sj-200003第二步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60000p3p4p5p668431110001201001000100(1)000164/3sj-2-30000p3p4p5p23010001000-34100010310100-1210010-2sj-200003cj-2-30000cBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-110010-2100010010001sj-200003进基变量:s1=-2=min{sj|sj<0},所以x1为进基变量离基变量的判别标准:qi=bi/ai1(ai1>0)qi324/离基变量:q4=2=minqi,x4为离基变量()-22标出主元第三步迭代过程cj-2-30000qicBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-1(1)0010-2100010010001324/sj-200003p3p1p5p2写出基向量(p4换成p1)归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变)3010001写出价格系数0-20-3消去:用初等行变换将主元所在列其它元素消为0p2所在行不变2000-112p1所在行乘以-1加到p3所在行1001-101p1所在行乘以-1加到p5所在行210010-2p1所在行乘以2加到判别数所在行sj00020-1第三步迭代过程cj-2-30000qicBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-1(1)0010-2100010010001324/sj-200003p3p1p5p230100010-20-32000-1121001-101210010-2sj00020-1cj-2-30000cBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-112010001sj00020-1进基变量:s6=–1=min{sj|sj<0},所以x6为进基变量离基变量的判别标准:qi=bi/ai6(ai6>0)qi1/13离基变量:q5=1=minqi,x5为离基变量(此处可选x3)()-11标出主元第四步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-11(2)0100011/13sj00020-1p3p1p6p2写出基向量(p5换成p6)归一化:若主元不等于1,则进行行变换,将主元变为1(此处除以2)2010½-½0写出价格系数0-20-3消去:用初等行变换将主元所在列其它元素消为01000-½½1p6所在行乘以-1加到p3所在行0001-½-½0p6所在行乘以2加到p1所在行4100010p6所在行乘以1加到判别数所在行sj0003/2½0p6所在行乘以-1加到p2所在行第四步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-11(2)0100011/13sj00020-1p3p1p6p22010½-½00-20-31000-½½10001-½-½04100010sj0003/2½0cj-2-30000cBBbp1p2p3p4p5p60-20-3p3p1p6p20412001-1/2-1/201000
浙公网安备 33021202002483