2022年最优化方法教案 .pdf

《2022年最优化方法教案 .pdf》由会员分享，可在线阅读，更多相关《2022年最优化方法教案 .pdf（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备欢迎下载第一章最优化问题与数学预备知识最优化分支： 线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。应用最优化方法解决问题时一般有以下几个特点：1. 实用性强2. 采用定量分析的科学手段3. 计算量大，必须借助于计算机4. 理论涉及面广应用领域： 工业，农业，交通运输，能源开发，经济计划，企业管理，军事作战。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 34 页学习必备欢迎下载1.1 最优化问题实例最优化问题：追求最优目标的数学问题。经典最优化理论：（1）无约束极值问题：),(opt 21nxxxf（),(mi

2、n 21nxxxf或),(max21nxxxf）其中，),(21nxxxf是定义在 n 维空间上的可微函数。解法（求极值点）：求驻点，即满足0),(0),(0),(11121nxnxnxxxfxxfxxfn并验证这些驻点是否极值点。（2）约束极值问题：),(opt 21nxxxfs.t. )(,2, 1,0),(21nlljxxxhnj解法：采用 Lagrange乘子法，即将问题转化为求Lagrange函数),(),(),;,(1121121njjljnlnxxhxxxfxxxL的无约束极值问题。近代最优化理论的实例：例 1 (生产计划问题 ) 设某工厂有 3 种资源 B1，B2，B3，数量各

3、为 b1，b2，b3，要生产 10 种产品 A1，A10 。每生产一个单位的Aj需要消耗 Bi的量为 aij，根据合同规定，产品Aj的量不少于 dj，再设 Aj的单价为 cj 。问如何安排生产计划，才能既完成合同，又使总精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 34 页学习必备欢迎下载收入最多？（线性规划问题）数学模型：设 Aj的计划产量为jx，z 为总产值。目标函数：max101jjjxcz约束条件：10,2, 1,3 ,2, 1,101jdxibxajjjijij线性规划问题通常采用单纯形法来求解。例 2 (工厂设址问题 )

4、要在 m 个不同地点计划修建m 个规模不完全相同的工厂，他们的生产能力分别是maaa,21（为简便起见，假设生产同一种产品），第 i 个工厂的建设费用mifi, 2, 1,。又有 n 个零 售商店销售这 种产 品，对 这种 产品 的需求 量分 别为nbbb,21，从第 i 个工厂运送一个单位产品到第j 个零售商店的运费为 cij。试决定应修建哪个工厂， 使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。 （混合整数规划问题）数学模型：设第 i 个工厂运往第j 个零售商店的产品数量为xij（i=1，m；j=1， n） ，且miiyi, 1, 0, 1否则个工厂如果修建第目标函数：min1

5、1minjijijiixcyfz精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 34 页学习必备欢迎下载约束条件：njmixmiynjbxmiyaxijimijijnjiiij, 1;, 1,0, 1, 10, 1, 1,11或整数规划问题通常可用分枝定界法或割平面法来求解。例 3 (投资计划问题 ) 假设某一个生产部门在一段时间内可用于投资的总金额为a亿元，可供选择的项目总共有n 个，分别记为 1，2，n。并且已知对第 j 个项目的投资总数为ja亿元，而收益额总数为jc亿元。 问如何使用资金a亿元， 才能使单位投资获得的收益最大。（非

6、线性规划问题）数学模型：设njjxj, 1, 0, 1否则个项目投资对第目标函数：max11njjjnjjjxaxcz约束条件：njxaxajnjjj, 1, 101或非线性规划问题的求解方法很多，是本课的重点。动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman 最优性原理”，例如：资源分配问题， 生产与存储问题。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 34 页学习必备欢迎下载例 4 (多参数曲线拟合问题)已知热敏电阻R依赖于温度T的函数关系为321xTxexR（*）其中，321,xxx是待定的参数，通

7、过实验测得T和R的 15 组数据列表如下，如何确定参数321,xxx？i 1 2 3 4 5 6 7 8 /iT50 55 60 65 70 75 80 85 kRi/34.78 28.61 23.65 19.63 16.37 13.72 11.54 9.744 i 9 10 11 12 13 14 15 /iT90 95 100 105 110 115 120 kRi/8.261 7.03 6.005 5.147 4.427 3.82 3.307 建立数学模型：测量点),(iiRT与曲线)(TR对应的点产生“偏差” ，即2151132ixTxiiexRS得如下无约束最优化问题：21511)(

8、min32ixTxiiexRxf通常采用最小二乘法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 34 页学习必备欢迎下载1.2 最优化问题的数学模型一、 最优化问题的数学模型1. 定义 1：设向量T21T21,mmbbbaaa. 若), 2, 1(mibaii，则记或；若),2, 1(mibaii，则记或。2 一般模型：max)min( )(opt 或或xf，nxR（1）s.t. )3(, 1,0)()2(, 1,0)(ljxhmixSji其 中 ，T21,nxxxx；)(xf，)(xSi，)(xhj是 关 于 变 量nxxx,21

9、的实值连续函数， 一般可假定它们具有二阶连续偏导数。3 向量模型：max)min( )(opt 或或xf，nxR（1）s.t. )3(, 1,0)()2(, 1,0)(ljxhmixS其中，)(xf称为目标函数；)(xSi，)(xhj称为约束函数；满足约束条件（ 2） ， （3）的点称为容许解或容许点（或可行解） ；可行解的全体称为容许域（或可行域） ，记为 R；满足（1）的容许点称为最优点或最优解（或极小（大）点 ） ，记为*x；)(xf称为最优值；不带约束的问题称为无约束问题，带约束的问题称为约束问题；若目标函数)(xf，约束函数)(xSi，)(xhj都是线性函数，则称为线性规划；若其中存

10、在非线性函数，则称为非线性规划；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 34 页学习必备欢迎下载若变量只取整数，称为整数规划；若变量只取 0，1，称为 01 规划。注：因0)(xh0)(xh，0)(-xh，则最优化问题一般可写成0)(.)(opt xStsxf二、 最优化问题的分类动态规划非线性规划线性规划约束问题维问题一维问题无约束问题静态规划最优化问题n1.3 二维问题的图解法例 1. 32max21xxz0,16482. .21121xxxxxts解：1. 由全部约束条件作图，求出可行域R：凸多边形 OABC 2. 作出一

11、条目标函数的等值线：设63221xx，作该直线即为一条目标函数的等值线， 并确定在可行域内， 这条等值线向哪个方向平移可使z值增大。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 34 页学习必备欢迎下载3. 平移目标函数等值线，做图求解最优点，再算出最优值。顶点)2,4(B是最优点，即最优解Tx24，最优值14z。分析：线性规划问题解的几种情况（1）有唯一最优解（上例）；（2）有无穷多组最优解：目标函数改为42max21xxz（3）无可行解：增加约束52x，则R。（4）无有限最优解（无界解）：例max21xxz0,2-42.21212

12、1xxxxxxts结论： （1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。 （2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。例 2. 1)-()2min(2221xx0,0505. .21212221xxxxxxxts解：目标函数等值线：11)-()2(2221xxC 为最优点0505212221xxxxx，得Tx 14定义 2：在三维及三维以上的空间中，使目标函数取同一常数的点集是常数rrxfx,)(称为等值面。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 34 页学习必备欢迎下载1.4 预备知识（一）线性代

13、数一、 n维向量空间nR1. 向量的内积： 设T21T21,nnyyyyxxxx，则内积为niiinnTyxyxyxyxyx122112. 向量的范数（或长度或模） ：设nxR，若实数x具有以下性质： （1）,0 x当且仅当0 x时0 x；（2）R,xx；（3）nyxyxyxR,. 则称x为nR上的向量的范数，简记为。规定了向量范数的线性空间nR称为线性赋范空间 ,记为,Rn. 3. 常见的向量范数向量的pL范数：pnipipxx11，p1三个重要的向量范数：1x，2x，x注：若无特殊说明，本书中的指的是2x。4.yx,间的距离：yx5.x与y正交：0yxT若非零向量组)1(x，)(kx的向量

14、两两正交，称它们是正交向量组。6. 标准正交基：)1(e，)( ne是 n 个正交的单位向量，即精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 34 页学习必备欢迎下载jijieejiT, 0, 1)()(二、 特征值和特征向量定义： 设A为 n 阶方阵，存在数和非零向量x，使xAx，则称为矩阵A的特征值，非零向量x为矩阵A属于特征值的特征向量。三、 正定矩阵定义： 设A为 n 阶实对称方阵，若对任意非零向量x，均有0AxxT，则称AxxT为正定二次型，A为正定矩阵，记A0。 ；若0AxxT，半正定二次型，A为半正定矩阵。类似有负定（半

15、负定）二次型，负定（半负定）矩阵的概念。性质：实对称方阵A为正定矩阵（负）A的特征值均为正（负）A的各阶顺序主子式均为正（奇数阶为负，偶数阶为正）实对称方阵A为半正定矩阵A的特征值均非负A的各阶顺序主子式均为非负精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 34 页学习必备欢迎下载（二）数学分析一、 梯度和海色（ Hesse ）矩阵1. 多元函数的可微性可微定义：设1RR:nDf，Dx0，若存在n维向量l，对npR0，总有0)()(limT000pplxfpxfp（1）则称函数)(xf在点0 x处可微。式（1）等价于pplxfpxf

16、0)()(T00（2）其中，p0是p的高阶无穷小。定理 1： （可微的必要条件） 若函数)(xf在点0 x处可微，则)(xf在该点关于各个变量的偏导数存在，且T02010)(,)(,)(nxxfxxfxxfl2. 梯度（1）概念梯度：令T21)(,)(,)()(nxxfxxfxxfxf则称)(xf为 n 元函数)(xf在x处的梯度（或记为)(gradxf） 。又称为)(xf关于x的一阶导数。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 34 页学习必备欢迎下载注： 式（2）等价于ppxfxfpxf0)()()(T000（3）等值面：

17、在三维和三维以上的空间中，使目标函数取同一数值的点集,)(Rrrxfx称为等值面（曲面）。方向导数： 设1RR:nf在点0 x处可微，向量npR0，e是p方向上的单位向量，则极限txftexft)()(lim000称为函数)(xf在点0 x处沿p方向的方向导数，记作pxf)(0。方向导数的几何解释： 方向导数pxf)(0表示函数)(xf在点0 x处沿方向的p的变化率。函数的下降（上升）方向：设1RR:nf是连续函数，点nxR0，npR0为一方向，若存在0，对于),0(t，都有)()(00 xftpxf（)()(00 xftpxf）则称p方向是函数)(xf在点0 x处的下降（上升）方向；结论 1

18、：若方向导数0)(0pxf，则方向p是)(xf在点0 x处的下降方向；若方向导数0)(0pxf，则方向p是)(xf在点0 x处的上升方向；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 34 页学习必备欢迎下载（2）性质【性质 1】 ：梯度)(0 xf为等值面)()(0 xfxf在点0 x处的切平面的法矢（向）量。【性质 2】 ：梯度方向是函数具有最大变化率的方向。定理 2：设1RR:nf在点0 x处可微，则方向导数cos)()()(0T00 xfexfpxf其中，e是p方向上的单位向量，为梯度与p的夹角。结论 2：1）与梯度)(0

19、xf方向成锐角的方向是上升方向；与梯度)(0 xf方向成钝角的方向是下降方向；2）梯度方向是函数值上升最快的方向，称为最速上升方向；负梯度方向是函数值下降最快的方向，称为最速下降方向。（3）几种特殊函数的梯度公式（1）0C，C为常数；（2）bxb)(T，其中T21,nbbbb；（3）xxx2)(T；（4）若Q是对称方阵，则QxQxx2)(T. 例3. 泰勒（ Taylor）公式与 Hesse矩阵性质 1：设RR:)(nxf具有一阶连续偏导数，则pfxfpxfT)()()(（*）其中，) 10(px，即介于x与px之间。精选学习资料 - - - - - - - - - 名师归纳总结 - - -

20、- - - -第 13 页，共 34 页学习必备欢迎下载性质 2：设RR:)(nxf具有二阶连续偏导数，则pfppxfxfpxf)(21)()()(2TT（*）其中22221222222122122122122)()()()()()()()()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf为函数)(xf关于x的二阶导数，称为)(xf的海色（ Hesse ）矩阵。结论 1：当2)(Cxf时，njixxxfxxxfijji, 1,)()(22（即海色矩阵对称）。注 1：1) 设向量函数T21)(,),(),()(xgxgxgxgm时，nmnnmmxxgxxg

21、xxgxxgxxgxxgxxgxxgxxgxg)()()()()()()()()()(212222111211称为向量函数)(xg在点x处的导数（梯度）。2) 向量函数T21)(,),(),()(xgxgxgxgm在点0 x处可微是指所有分量都在点0 x处可微。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 34 页学习必备欢迎下载关于向量函数常见的梯度：（1）nC0，nCR；（2）nIx)(，nxR；（3）,)(TAAxnmAR（4）设)()(0tpxft，其中1RR:nf，11RR:，则ptpxftT0)()(，ptpxfpt)(

22、)(02T例：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 34 页学习必备欢迎下载（三）极小点的判定条件（求)(min xf）一、 基本概念1. 点0 x的邻域：0,),(00 xxxxN2. 局部极小点：设1RR:nDf. 若存在点Dx*和数0，对DxNx),(*都有)()(*xfxf，则称*x为)(xf在D上的（非严格）局部极小点；若)()(*xfxf（*xx） ，则称*x为)(xf在D上的严格局部极小点。3. 全局极小点：设1RR:nDf. 若存在点Dx*，对于Dx都有)()(*xfxf，则称*x为)(xf在D上的（非严格）

23、全局极小点；若)()(*xfxf（*xx） ，则称*x为)(xf在D上的严格全局极小点。性质：全局极小点必是局部极小点； 但局部极小点不一定是全局极小点。类似有极大点的概念。因)(min)(maxxfxf，本书主要给出极小问题。4. 驻点：设1RR:nDf可微，Dx*，若0)(*xf，则称点*x为)(xf的驻点或临界点。二、 极值的条件定理 1（一阶必要条件）设1RR:nDf具有一阶连续偏导数，*x是D的内点，若*x是)(xf的局部极小点，则0)(*xf定理 2（二阶必要条件）设1RR:nDf具有二阶连续偏导精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

24、 -第 16 页，共 34 页学习必备欢迎下载数，若*x是D的内点且为)(xf的局部极小点， 则)(*2xf是半正定的，即对npR恒有02Tpxfp)(*例定理 3 （二阶充分条件）设1RR:nDf具有二阶连续偏导数，*x为D的内点，且0)(*xf，若)(*2xf正定，则*x为)(xf的严格局部极小点。（四）凸函数与凸规划一、凸集1. 凸集的定义：一个n 维向量空间的点集D中任意两点的连线仍属于这个集合，即对Dxx21,，有)10()1(21Dxx则称该点集D为凸集。2. 凸集的性质：（1）凸集的交集仍是凸集)(21DD；（2）数乘凸集仍是凸集,DxxyyD；（3） 凸集的和集仍是凸集,212

25、1DzDxzxyyDD特别规定，空集是凸集。3. 超平面：设nR且R, 0 b，则集合R,TnxbxxH称为nR中的超平面，称为该超平面的法向量，即bxaxaxaHnn2211:； （是凸集）半空间：集合R,Tnxbxx称为nR中的一个半空间。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 34 页学习必备欢迎下载超球：rx。4. 凸组合：设lxxx,21为nR中的l个点，若存在laaa,21且1, 101liiiaa，使得llxaxaxax2211则称x为lxxx,21的凸组合。若laaa,21均为正，则称为严格凸组合。5. 顶点（

26、或极点）：设D是凸集，Dx，若x不能用D内不同两点1x和2x的凸组合表示，即) 10()1(21xxx，则称x为D的顶点。二、凸函数1. 凸函数 ：设1RR:nDf，D是凸集，若对Dxx21,及 1, 0，都有)()(1)()1 (2121xfxfxxf则称)(xf为凸集D上的凸函数；若) 10()()(1)()1(2121xfxfxxf则称)(xf为凸集D上的严格凸函数。类似有凹函数的定义。2.几何意义 ：函数图形上连接任意两点的线段处处都在函数图形的上方。3. 性质性质 1：)(xf为凸集D上的凸函数，0k，则)(xkf也为D上精选学习资料 - - - - - - - - - 名师归纳总结

27、 - - - - - - -第 18 页，共 34 页学习必备欢迎下载的凸函数。性质 2：两个凸函数的和仍是凸函数。)()(21xfxf推论 1：凸集D上有限个凸函数)(xfi的非负线性组合0),()(11immkxfkxfk仍为D上的凸函数。性质 3：若)(xf为凸集D上的凸函数，则对R，)(xf的水平集,)(DxxfxD是凸集。性质 4：)(xf为凸集D上的凹函数)(xf为凸集D上的凸函数。4. 凸函数的充分必要条件定理 1（一阶条件）设1RR:nDf可微，D是凸集，则（1）)(xf为凸函数对Dxx21,，恒有)-()()()(12T112xxxfxfxf（2）)(xf为严格凸函数对Dxx

28、21,，21xx恒有)-()()()(12T112xxxfxfxf定理 2（二阶条件）设1RR:nDf具有二阶连续偏导数，D为开凸集，则（1）)(xf在D内为凸函数对Dx，)(2xf是半正定的；（2）若)(2xf正定，则)(xf在D内为严格凸函数。特殊地，n元二次函数为CxbQxxxfTT21)(（Q为对称矩阵） ；若Q正定，则)(xf称为正定二次函数。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 34 页学习必备欢迎下载性质： 正定二次函数是严格凸函数。 （因为Qxf)(2）5. 凸函数的极值定理 3 设1RR:nDf为凸集D上的

29、凸函数，则（1）)(xf的任一局部极小点*x为全局极小点；（ 2） 若)(xf具 有 二 阶 连 续偏 导 数 ， 且存 在Dx*， 使0)(*xf，则*x为)(xf在D上的全局极小点；（3）若)(xf为严格凸函数，且全局极小点存在，则必唯一。特殊：对于正定二次函数CxbQxxxfTT21)(，有bQxxf)(，得唯一驻点bQx1*为唯一的全局极小点。6. 凸规划问题： 非空凸集D上的凸函数的极小化问题。考虑凸规划问题：)(minxf，nxR(1) s.t. )3(, 1, 0)()2(, 1, 0)(ljxhmixSji其中，)(xSi为nR上的凹函数，)(xhj为nR上的线性函数，, 1;

30、, 1, 0)(, 0)(ljmixhxSxDji为凸集，1RR:nDf为D上的凸函数。注：线性函数既可视为凸函数，又可视为凹函数。二次规划：CxbQxxxfTT21)(mins.t. dCxpAx其中，nxR，nmA，nlC，Q半正定或正定。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 34 页学习必备欢迎下载（五）下降迭代算法1. 下降迭代算法的步骤（1）选择一个初始点0 x，令 k：=0 （2）检验kx是否最优？若是，则停止迭代；若不是，则（3）确定一个下降方向kp：存在0，对),0t，使得kkkxftpxf（4）从点kx出发

31、，沿方向kp进行直线搜索（一维搜索） ，即求步长kt使kkkkktpxfptxfmin（5）计算kkkkptxx1，令 k：=k+1，转（2）2. 直线搜索及其性质（1）简记),(pxlsz：ptxztpxfptxf00min表示从点x出发，沿方向p进行直线搜索，得到极小点z。（ 2） 定 理 ：设 目 标 函 数)(xf具 有 一 阶连 续 偏 导 数 ， 若),(pxlsz，则0)(Tpzf证明： （反正法）设0)(Tpxf，则1）0)(Tpxf，此时p是点z的下降方向；2）0)(Tpxf，此时p是点z的下降方向；与),(pxlsz矛盾。精选学习资料 - - - - - - - - - 名

32、师归纳总结 - - - - - - -第 21 页，共 34 页学习必备欢迎下载3. 收敛速度定 义 1：设 序 列kx是 线 性赋 范 空 间,Rn中 的 点列 ，nxR*，若0lim*xxkk则称序列kx收敛于*x，记为*limxxkk。定 义2 ： 设 向 量 函 数T21)(,),(),()(xfxfxfxfm，nDxR，若当00 xx时，总有0)()(0 xfxf，则称)(xf在点0 x连续；若)(xf在D内每一点都连续， 则称)(xf在D内连续。特别地， m=1 时，)(xf为数量函数，则)()()()(00 xfxfxfxf定义 3：设序列kx收敛于*x，若存在与k无关的数) 1

33、(和)0(，使得当k从某个)0(0k开始，都有*1xxxxkk则称序列kx收敛的阶为，或kx为阶收敛。当1，且10时，称线性收敛或一阶收敛；当2时，称二阶收敛；当21时，称超线性收敛。4. 计算终止准则计算终止准则根据相继两次迭代的结果a. 根据相继两次迭代的绝对误差（不常用）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 34 页学习必备欢迎下载11kkxx，21)()(kkxfxfb. 根据相继两次迭代的相对误差311kkkxxx，411)()()(kkkxfxfxfc. 根据目标函数梯度的模足够小5)(kxf54321,为给定的

34、足够小的正数。以上准则统称为Himmelblau 计算终止准则，简称H 终止准则。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 34 页学习必备欢迎下载第二章线性规划2.1 数学模型一、线性规划的标准型1. 繁写形式：nnxcxcxcz2211min s.t. 0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa其中，mibi,2, 1,0（否则，等式两端同乘以“-1” ） 。2. 缩写形式：njjjxcz1min s.t. njxmibxajinjjij, 2, 1

35、,0,2, 1,13. 向量形式：XCzTmin s.t. 01Xbxpnjjj其中，T21,ncccC，T21,nxxxX，T21,mbbbb，T21,mjjjjaaap。4. 矩阵形式：XCzTmin精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 34 页学习必备欢迎下载s.t. 0XbAX其中，,21212222111211nmnmmnnpppaaaaaaaaaAA：约束条件的nm系数矩阵，0m，0n，一般地，nm；b：限定向量，一般地，mibi,2, 1,0；C：价值向量；X：决策向量，0X；通常A，b，C为已知，X未知。二、

36、任一模型化为标准型1. 极大化目标函数：XCzTmax 令zz，则问题转化为XCzTmin 2. 约束条件为不等式若约束为“”型，则“左端 +松弛变量 =右端” （松弛变量0）如：ininiibxaxaxa2211，引入松弛变量0inx，化为iinniniibxxaxaxa2211若约束为“”型，则“左端 -剩余变量 =右端” （剩余变量0）如：ininiibxaxaxa2211，引入剩余弛变量0inx，化为精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 34 页学习必备欢迎下载iinniniibxxaxaxa22113. 若存在无非

37、负要求的变量kx（称为自由变量）令kkkxxx，其中0kx，0kx，代入目标函数及约束条件即可。4. 某变量jx有上、下界若jjux， 即0jjux， 令jjjuxx， 有0jx。 用jjux代替jx即可。若jjtx，即0jjxt，令jjjxtx，有0jx。用jjxt代替jx即可。例：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 34 页学习必备欢迎下载2.2 线性规划解的性质一、基本概念标准型（ LP） ：)1 (minTXCzs.t. (3)0)2(XbAX可行解（容许解）：满足约束（ 2） 、 （3）的解。最优解：满足（ 1）

38、的容许解。基：设nmA的秩为m，若B是A中的mm阶可逆矩阵，称B是线性规划问题（ LP）的一个基。基向量：基B中的一列（ip）即为一个基向量。（共m个）非基向量： 基B之外的一列（jp）即为一个非基向量。（共mn个）基变量：与基向量ip相应的变量ix。 （共m个）非基变量：与非基向量jp相应的变量jx。 （共mn个）基本解：令所有非基变量为0，求出的满足约束（ 2）的解。基本容许解：满足约束（3）的基本解。最优基本容许解：满足约束（1）的基本容许解。退化的基本解：若基本解中有基变量为0 的基本解。退化的基本容许解：退化的最优基本容许解：精选学习资料 - - - - - - - - - 名师归纳

39、总结 - - - - - - -第 27 页，共 34 页学习必备欢迎下载二、线性规划问题的基本定理定理 1 若线性规划问题存在容许域，则其容许域是凸集。定理 2 线性规划问题的基本容许解对应于容许域的顶点。定理 3 若线性规划问题存在有限最优解，则其目标函数最优值一定可以在容许域的顶点达到。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 34 页学习必备欢迎下载2.3 单纯形法一、单纯形法原理单纯形法的基本思路： 根据问题的标准型， 从容许域的一个基本容许解（一个顶点）开始，转移到另一个基本容许解（顶点），并且使目标函数值逐步下降；

40、 当目标函数达到最小值时， 问题就得到了最优解。二、单纯形法的步骤（以“大M 法”为例）数学描述例（大 M 法） ：321834min xxxzs.t. 1,2,3)(j05223231jxxxxx1. 构造初始容许基初始容许基是一个mm单位矩阵，它相应的基本解是容许的。1o 引入附加变量，把数学模型化为标准型。2o 若约束条件中附加变量系数为“-1” ，或原约束即为等式，则一般须引入人工变量。3o 目标函数中，附加变量系数为0，而人工变量系数为M （很大的正数）。人工变量系数为大M ：只要人工变量 0，使前后约束条件不等价，但由于目标函数的修改， 同时也使所求的目标函数最小值是一个很大的数，

41、也是对“篡改”约束条件的一种惩罚，因此，M 叫做罚因子，大 M 法也叫做罚函数法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页，共 34 页学习必备欢迎下载若对极大化问题，目标函数中人工变量系数为（-M） 。得到如下标准型：njjjxcz1min s.t. ),2, 1(j011,2211,221111,11nxbxaxaxbxaxaxbxaxaxjmnmnmmmmnnmmnnmm其中，),2, 1(mixi表示基变量；), 1j(nmxj表示非基变量。2. 求出一个基本容许解1o 用非基变量表示基变量和目标函数。用非基变量表示基变量，

42、即有), 1(1mixabxnmjjijii用非基变量表示目标函数，即nmjjjnmjjjjnmjjmiijijimiinmjjjmiiinkkkxxzcxaccbcxcxcxcz1010111111z)(z)(其中，miiibc10z，而jjjzc称为非基变量jx的检验数。上式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 34 页学习必备欢迎下载中，规定各基变量的检验数为0。jBjBBjmmjjmmjmjjmiijijpCpccpccaaccacacacaczmT11122111,1若干次迭代其中，BC是基变量的价值系数，随基的改

43、变而改变。2o 求出一个基本容许解及相应的目标函数值。令非基变量 =0 即得初始基本容许解：), 1(mibxii，), 1j(0nmxj初始目标函数值：0zz3. 最优性检验1o 检验数j：目标函数式中，各非基变量的系数，即称为各非基变量的检验数。2o 最优解判别定理： 若在极小化问题中， 对于某个基本容许解，所有检验数0j，且人工变量为0，则该基本容许解是最优解。3o 无穷多最优解判别定理：若在极小化问题中，对于某个基本容许解，所有检验数0j，又存在某个非基变量的检验数为0，且人工变量为 0，则该线性规划问题有无穷多最优解。4o 无容许解判别定理：若在极小化问题中，对于某个基本容许解，所有

44、检验数0j，但人工变量不为0，则该线性规划问题无容许解。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 34 页学习必备欢迎下载4. 基变换1o 基本容许解的改进定理：已知一个非退化的基本容许解具有目标函数值0z，设某一个非基变量jx，其0j，则存在一个可行解具有目标函数值0zz；如果用jp代替原基中的某一列向量而产生一个新的基本容许解，则该新的解将有0zz。2o 换入变量的确定kx为换入变量，使0minjjk。3o 换出变量的确定最小非负比值规则rx为换出变量，使0minikikirkraabab4o 无有限最优解判别定理：若在极小

45、化问题中，对于某个基本容许解，有一个非基变量的检验数0k，但kp列中没有正元素，且人工变量为 0，则该线性规划问题无有限最优解。三、单纯形法的表格形式1构造初始可行基，并计算检验数j2从表中找出基本可行解和相应的目标函数值3最优性检验4基变换1o 换入变量的确定2o 换出变量的确定3o 主元素的确定精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 32 页，共 34 页学习必备欢迎下载单纯形表中，换入变量所在的列和换出变量所在的行交叉处的元素为主元素（即rka） ，标“ *”号。4o 取主变换（基变换）即单纯形法的一次迭代。在表中以rka主元素进行旋

46、转变换（高斯消去法），把kx所对应的列向量0101行初等变换mkrkkkaaap于是得到新一轮的单纯形表。四、单纯形法解极大化和极小化问题的区别原模型目标函数标准型最优性检验换入变量的确定njjjxcz1min 目标函数中人工变量系数为大 M 所有0j， 且人工变量为 00minjjknjjjxcz1max目标函数中人工变量系数为“-M ”所有0j， 且人工变量为 00maxjjk五、两阶段法1. 第一阶段：判断原线性规划问题是否有容许解。先求解以下线性规划mnnxxw1min （人工变量之和）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 33 页，共 34 页学习必备欢迎下载s.t. ,2, 1j0, 1,1mnxmibxxajiinnjjij用单纯形法对上述问题求解。若0w，则原问题有容许解；若0w，则原问题无容许解，停止计算。2. 第二阶段：求原线性规划问题的最优解。以第一阶段的最终单纯形表为基础，去掉其中的人工变量列， 把目标函数换成原问题的目标函数，于是得到第二阶段的初始单纯形表，继续迭代下去，得最优解。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 34 页，共 34 页