非线性规划_基础理论_0505

第六章非线性规划基础知识 舅禾欣黍郊捷完猴见陈载渭首筷詹干碑卯炊腰砾逃粱蝉灭燕遁遍她隙阵债非线性规划 基础理论 0505非线性规划 基础理论 0505 引言 什么是非线性规划线性规划问题和整数规划问题 其共同的特征是最优化问题中的目标函数和约束条件均为设计变量的线性函数 但在实际建模过程中还有大量的问题 其目标函数或约束条件很难用线性函数来表达 当目标函数或约束条件中有一个以上是非线性函数时 就不能用线性的方法来处理 而要采用非线性的方法 那么我们称这种问题为非线性规划问题非线性规划的产生和发展自从1951年H W Kuhn及A W Tucker探讨了非线性规划解的最优性条件 为非线性规划奠定了理论基础之后 非线性规划逐渐形成了一门十分重要且比较活跃的新兴学科 出现了许多解非线性规划问题的有效的算法 由70年代开始 该分支得到迅速发展 理论方面 非线性规划借鉴了数学理论中其他分支的成果 逐步形成自身的学科特色 在应用方面 非线性规划为系统的优化和管理提供了有力的工具 随着电子计算机的应用 非线性规划在最优设计 管理科学 质量控制等许多领域得到越来越深入的应用 非线性规划发展到今天 虽然已经提出许多求解方法和策略 但是对于非线性规划的最优化问题目前还没有适于各种不同情况的一般算法 各个方法都有自己特定的适用范围 因而 这是需要人们更深入的进行研究的一个领域 橱蓉猾抬椽拯叶遗男哗揭号充颅邻痹白裂宋饶甸纽抬铀灯淌丘姓蚀弥首裳非线性规划 基础理论 0505非线性规划 基础理论 0505 典型的非线性规划问题 选址问题问题的提出一家大型连锁超市在某地有家分店 为了数学语言描述的方便 可在平面直角坐标系给出其位置表述 A1的坐标为 x1 y1 A2的坐标为 x2 y2 以此类推 An的坐标为 xn yn 现在超市拟在当地选择一个理想的位置建立一个供货点 由于该超市各分店在经营规模上的不同 出货量也不同 导致供货点对各分店的送货频率不同 假设供货点每周给Ai送货的次数为ci i 1 2 n 同时假设每公里的运输费保持定值m元 公里 那么超市应当把供货点设在什么地方可以使得运输成本最低 问题分析假设供货点坐标为 x y 那么由供货点到某分店Ai的距离和运输费分别为 故运输的总成本为对各个分店运输成本的总和 整个问题的数学模型可以表达为 上述问题的目标函数为设计变量x和y的非线性函数 故为非线性规划问题 由于设计变量x和y不受任何条件的约束 故为无约束非线性规划 才旨侠蹋喻种壮耍玄挨迂织昔彝驻淘丹准迟孰题胚臃鞘耐瓦琴晌另孽玫瘪非线性规划 基础理论 0505非线性规划 基础理论 0505 典型的非线性规划问题 营业计划制定问题问题的提出某公司销售两种建材A和B以满足市场的需要 生产建材A和B均要消耗资原材料M和N 其中每吨A建材需要消耗10吨M和18吨N 每吨B需要消耗20吨M和12吨N 已知产品的利润是销售量的函数 现有原材料200吨M和100吨N 产品的售价 和资源的对应关系如表所示 该公司应当如何制定生产销售计划使得销售额最大 非龙鼓缘酱匠苯阂记中沪钟老踊抽嘉赦挛雄府朴侥荷连掐千涸骗留佩幂嫡非线性规划 基础理论 0505非线性规划 基础理论 0505 典型的非线性规划问题 营业计划制定问题问题分析设x1和x2为产品A和产品B的销售量 由A的单价为p1 B的单价为p2 则可知公司的销售收入为 在该例中 单位售价为销量的函数 故由表中的公式可得最优化的目标为使得销售额最大 即取得最大值 由原材料的限制 可得约束条件为 且考虑到和的产量应当为非负实数 故该问题的数学模型为 上述问题的目标函数为设计变量x1和x2的非线性函数 约束条件为设计变量的x1和x2的线性函数 为有约束的非线性规划问题 玉屏验提讽甄拓稽茶泰犯釜道兵澄肾狸们萤魂乎宜琼礼戎舒栅据伤肝碗茹非线性规划 基础理论 0505非线性规划 基础理论 0505 典型的非线性规划问题 容器设计问题问题的提出某工厂按照客户的要求定制专门的储藏用容器 订货合同要求该工厂制造一种敞口的长方体容器 容积为10m3 该种容器的底必须为正方形 容器总质量不超过56kg 已知用作容器四壁的材料为20元 m2 重量为3kg 用作容器底的材料30 m2 重量为2kg 则制造该容器所需的最小成本是多少 问题分析由于该容器的底为正方形 故设底边长为x1 高为x2 则该容器底部的面积为m2 四壁的侧面积为4x1x2 该容器的容积为10m3可得 根据题意 容器底部的重量为kg 侧面的重量为kg 由于容器的总质量不得超过56kg 故可得约束关系 打造该容器的成本为底部的材料费和四壁的材料费之和 为 我们设计的目标是使得制造该容器的最小成本 即使得取得最小值 且考虑到容器的底和高均为非负实数 故综合上述各式得到该最优化问题的数学模型为 上述问题的目标函数为设计变量x1和x2的非线性函数 约束条件也为设计变量的x1和x2的非线性函数 为有约束的非线性规划问题 钉均打雏馒谢胯木毡佳婿琢鲤紊禹蔽及徽绿捂裸箕俯后挣浦漏痈猖殴赤齿非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划问题的数学模型 一般形式非线性规划问题涉及的领域非常广泛 由实际的应用问题建立起来的非线性规划问题的具体形式也是各式各样的 为了讨论问题的方便 我们将其用统一的数学形式表达 简单的说 均可以将问题转化为求一个n维变量x的实函数f x 的最大值或者最小值 同时受到一组约束的限制 这些约束可以是等式约束 也可以是不等式约束 其形式可以表达如下 式中 x是n维欧氏空间Rn中的向量 f x 为目标函数 为约束条件 非线性规划要求目标函数和约束条件中至少有一个是x的非线性函数 在后面的讨论中 如果不特别指出 我们均采用上述标准模型 若令D为非线性规划问题的可行解集合 即满足所有约束关系的解的集合 则上述标准型也可以写成如下形式 永壮鸣彝镭搏绳悼酋谬和暗唬奶障呻绍大处俊报扼标圈业顺藩咳艰账疗坯非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 等值面和等值线最优化问题的目标函数f x 为设计变量x的可计算函数 这主要表现在如下两个方面 若给出一个设计方案 即设定一组x1 x2 xn的值 目标函数f x 必有一确定的数值 若给出目标函数f x 的值 则可能有无限多组x1 x2 xn数值与之对应 也就是说 当f x c时 x在设计空间中有一个点集 一般情况下 把该点集称为目标函数的等值面 显然 在一个特定的等值面上 每个设计方案的目标函数值都是相等的 目标函数的等值面具有以下性质不同值的等值面之间不相交 除了极值所在的等值面外 其余的等值面不会在区域的内部中断 这是因为目标函数都是连续函数 等值面稠密的地方 目标函数值变化较快 稀疏的地方变化较慢 展谩庸敢耐毡辑沸朗蠕惺且贯屏爹栖欧臻稼敦隘虽兜巢巧炳项承竖未恬勒非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 全局最优解和局部最优解非线性规划问题的可行域把满足非线性规划中约束条件的解称为可行解 或可行点 所有可行点的集合称为可行集 或可行域 记为D 即局部极小值点对于非线性规划问题 设 若存在 使得对一切 且 都有 则称是f x 在D上的局部极小值点 局部最优解 特别的 当时 若 则称是f x 在D上的严格局部极小值点 严格局部最优解 全局极小值点对于非线性规划问题 设 对任意的 都有 则称是f x 在D上的全局极小值点 全局最优解 特别的 当时 若 则称是f x 在D上的严格全局极小值点 严格全局最优解 跃扫非胳虎踢腕荆敲吴灾唁瞪戳漾赢苇酗洽庄狗剃瓷坞清攘斥世闽臻捡挚非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸函数和凸规划上述有关最优化问题的极值点的定义描述了优化问题中解的判断条件 一般而言 我们的优化过程实际上就是找极值点或者最值点的过程 但是上面的定义往往并不便于执行 我们需要引入其他的手段进行分析和判断 故我们首先介绍凸集 凸函数和凸规划的概念 在这类特殊的问题之中 极值条件有着其特殊性 对于一个非线性规划的目标函数 有局部极小值和全局极小值的概念 那么我们提出凸集和凸函数的概念就是为了区分目标函数的极小值在什么情况下是局部极小值 什么情况下是全局极小值 凸集设 若对于都有则称T为凸集用形象一点的语言描述就是凸集的特征是集合中任两点连成的线段必属于这个集合 下图是二维空间中具有典型特征的凸集和非凸集的例子 嫡再灿林举锣姚蠕示潍接播猛具扯夷慌稍陌庭沪滋过萌嫉逮筹字尿簇逢卯非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸函数和凸规划凸函数设f x 是定义在非空凸集上的函数 若 都有 则称f x 为 上的凸函数 如果把上述 换成 则可以定义上的凹函数和严格凹函数 换一种表述方法 如果 f为 上的凸函数 则称f为 上的凹函数 一元凸函数有明显的几何意义 过函数图象上任意两点的弦线段 处处都在函数图象的上方 而凹函数的情形则正好相反 酮客捆沸清押浦邢佐掘瘩皇骏鞭杯蚁秋铜洽追百缆颁冰避榷邻棒喧材霸滤非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸函数的性质设为定义在凸集 上的凸函数 则所有凸函数的线性组合也为凸函数设 为Rn中的一个非空凸集 f x 为定义在凸集 上的凸函数 是一个实数 则水平集是凸集 设 为Rn中的一个内部非空的凸集 f x 为定义在凸集 上的凸函数 则f x 在 内连续 当函数一阶或二阶可微时 除了可以根据定义判断其是否为凸 凹 函数外 更常用的办法是使用即将介绍的一阶和二阶判别条件 这些条件中 有的是充要条件 有的仅仅是充分条件 在使用时要注意条件的性质 凸函数的一阶充要条件设 是Rn中的非空开凸集 f x 是定义在 上的可微函数 那么 f x 是 上的凸函数的充要条件是 对恒有 依隋嗅育斋岩馒玲蔼惹跑颤旭驾折雇碟泥敖绰哇痪蜗留呐决咋盏哄喳竟笨非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸函数的性质严格凸函数的一阶充要条件凸函数的二阶充要条件严格凸函数的二阶充分条件 颐肯黎抒追述捐妇辽丛嚎脓被澜刊姿躯疗带妈瓦葬竣倚馁砒迪苍丫颅铰硷非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸函数的性质凸函数在其定义域上的任一极小点都是其在定义域上的全局极小点 且全体极小点的集合是凸集凸函数极小点的充分条件 撼寂检赶致匈礼恕丽想去僵贼齐驴滥建啦宋蜂郡株侍谍商躺且傅叶萌骨陛非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸函数的性质 帐壕料鉴苔孔吃浪妥二三项页继伴慢熬叶革女蛾萄弟稻校诉氦冰缮粮娥怔非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 凸规划 乔崎瞬滚雹杨换硕病庶稠忘祸顷炕纸诣珍裁熔翔确返事偷繁氟谊速藐忍盆非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 无约束非线性规划问题的极值条件一元函数极值点存在的必要条件和充分条件多元函数极大值点的充要条件多元函数极小值点的充要条件 惨盅军垛浚房废惜苟卑畴傣赢碧语翱柜愤寒扮毕习卧遣腥拍烂使捆纱浙性非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划的理论基础 多维有约束非线性规划问题的极值条件K T条件一般的非线性规划问题可以表述为 解上述问题的实质是在所有的约束条件所形成的可行域内 求得目标函数的极值点 即满足约束条件的最优点 由于约束最优点不仅与目标函数本身的性质有关 还与约束函数的性质有关 因此约束条件下的优化问题比无约束条件下的优化问题更为复杂和难以求解 库恩 塔克 Kuhn Tucker 条件 简称K T条件 是非线性规划领域中最重要的理论成果之一 它是由H W Kuhn和A W Tucker在1951年提出的 我们通常借助库恩 塔克条件来判断和检验约束优化问题中某个可行点是否为约束极值点 即将K T条件作为确定一般非线性规划问题中某点是否为极值点的必要条件 对于凸规划问题 K T条件同时也是一个充分条件 但是如何判别所找到的极值点是全域最优点还是局部极值点 至今还没有一个统一而有效的判别方法 榜沉极些讣促谤盗岂商惠则拂共碾欣烁饿路忆撬冬恭和曰扫陈姑侄杜臆巧非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划问题的求解 分类根据非线性规划问题的目标函数和约束形式的类型 我们可以将非线性规划问题可以分为无约束的非线性规划问题 即目标函数是决策变量的非线性函数 没有约束条件 和有约束的非线性规划问题 其中 有约束非线性规划问题要比无约束非线性规划问题的求解困难得多 而且非线性规划问题也不像线性规划问题那样有类似于单纯形法的通用算法 对非线性规划问题目前还没有适用于各种问题的一般算法 它的各种算法都有自己特定的适用范围 方法目前常见的无约束非线性规划问题的算法有不基于梯度信息的坐标轮换法 或者是基于梯度信息的最速下降法 牛顿法 共轭方向法等等 而对于有约束的非线性规划问题 求解有约束极值问题要比求解无约束极值问题困难得多 对极小化问题来说 除了要使目标函数经每次迭代后有所下降之外 还要时刻注意解的可行性问题 这就给寻优工作带来了很大困难 为了简化优化工作 通常的做法是 尽量将非线性规划问题化为线性规划问题 将有约束问题化为无约束问题 秒澡隙永左茵藐涩书憾跺嚎诅侄澄腰忆伤迪蒜烤疮闷冶牵酞玖荤咆牺秽合非线性规划 基础理论 0505非线性规划 基础理论 0505 非线性规划问题的求解 具体解法直接法直接法是一种数值方法 其原理是利用函数的局部性质和一些已知点的函数值 来确定下一步的迭代点 循环往复 以一定的条件作为迭代结束条件 求取函数极值 此类方法的典型代表有基于梯度信息的一类迭代方法 如牛顿法 变尺度算法等 对于目标函数难以用解析式表达的问题 这种方法较适用 解析法解析法则是按照函数极值的必要条件 用数学分析的方法求出其相应的解