清华大学研究生公共课讲义_最优化理论与算法(第2版).pdf.pdf

第 1 页学科简述最优化理论与算法是一个重要的数学分支,它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案这类问题普遍存在例如,工程设计中怎样选择设计参数,使得设计方案既满足设计要求又能降低成本;资源分配中,怎样分配有限资源,使得分配方案既能满足各方面的基本要求,又能获得好的经济效益;生产计划安排中, 选择怎样的计划方案才能提高产值和利润;原料配比问题中,怎样确定各种成分的比例, 才能提高质量,降低成本;城建规划中,怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局,才能方便群众,有利于城市各行各业的发展;农田规划中,怎样安排各种农作物的合理布局,才能保持高产稳产,发挥地区优势;军事指挥中,怎样确定最佳作战方案,才能有效地消灭敌人,保存自己,有利于战争的全局;在人类活动的各个领域中,诸如此类,不胜枚举最优化这一数学分支,正是为这些问题的解决,提供理论基础和求解方法,它是一门应用广泛、实用性强的学科最优化长期以来,人们对最优化问题进行着探讨和研究早在是个古老的课题世发明微积分的时代,就已提出极纪,英国科学家值问题,后来又出现乘年法国数学数法家研究了函数值沿什么方向下降最快的问题,提出最速下降法提出了解决下料问题和运输问题这两种线年前苏联数学家性规划问题的求解方法但人们关于最优化问题的研究工作,随着历史的发展不断深入是,任何科学的进步,都年代,最优化这个古老课题受到历史条件的限制,直至世纪并未形成独立的有系统的学科世纪年代以来,由于生产和科学研究突飞猛进地发展,特别是电子计算机日益广泛应用,使最优化问题的研究不仅因此成为一种迫切需要,而且有了求解的有力工具至今已出现线性规划、整数规划、最优化理论和算法迅速发展起来,形成一个新的学科非线性规划、几何规划、动态规划、随机规划、网络流等许多分支最优化理论和算法在实际应用中正在发挥越来越大的作用第章引言第 2 页下面先来研究几求解这类问题,本书重点介绍线性与非线性规划个例题例生产计划问题设某工厂用种资种产品需要第源生产种产品,每单位第可,第获利润为种资源总消耗量不能超过,由于市场限制,第过,试问如何安排生产才能使总利润最大? 解析下面分析怎样设建立数学模型种产品的产量分别为变量,目标函,约束条件有资源限制数是总利润,及产,市场销量限制, 量非负限制题概括为,在一组约束条件下,确定一个( 最优生产方案最大数学模型如下: 其中例食谱问题设市种不同的食品,第种食品单位售价为场上可买到种食品营养成分,第种营养成分为每一个单位含第分的需试确定在保证营养要求条件下的最经济食谱要量不少于解析建立食谱问设每人每天需要各种食品的数量分别为题的数学模型我们的目标是使伙食费用最少,即使用餐者对各种营养成分的基本需要,即满足数学模型是线性与非线性规划问题线性与非线性规划有着广泛的实际背景,许多实际问题抽象成数学模型后,可归结为种资源的数量为种产品的产量不超,这是决策问,使目标函数值表示, ,读作“约束条件是”读作“极大化”表示每种食品含有种基本又设每人每天对第种营养成最小条件是保证第 3 页其中表示例结构设计问题,高已知桁架的跨度度,钢管的负荷,材料比重厚度及容许应力架的高度,使桁架的重量最小解析桁架的重量它是平均直径和高度不是任意的,必须满足以下几个条件: )由于空间限制,要求限,即力为钢管的横截面面积由此可知,钢管上的压应力为,读作“极小化”以两个构件组成的对称桁架为例(参见图的上限,承受,纵向弹性模量试确定钢管的平均直径及桁) 和的函数的选择图不能超过高度上钢管上的压应力不能超过材料的容许应在负荷力作用下,钢管承受的压因此要求参数的选择还必的作用下钢管不发生弯曲,这就要求压应力不须保证在负荷临界应超过临界应力力可由公式算出: 其中是已知的弹性模量按此要求应有根据以上分析,桁架的最优设计问题,就是求重量函数在上述个约束条件下的极小第 4 页点问题它的数学模型是例选址问题个市场,第设有个市场的位置为,对某种货物的需要量为现计划建立个货个货栈的容量为栈,第到各市场的运输量与路程乘积之和最小解析现在来建立数学设第个货栈的位置为( 模型栈供给第个市第场的货物量为距离,一般定义为为或我们的目标是使运输量与路程乘积之和最小,如果距离按( 最小约束条件是: 每个货栈向各市场提供的货物量之和不能超过它的容量每个市场从各货栈得到的货物量之和应等于它的需要量运输量不能为负数因此,问题的数学模型如下: 试确定货栈的位置,使各货栈个货第个市场的个货栈到第式定义,就是使第 5 页在和例上述例的数学模型中,目标函数和约束函数都是线性的,称之为线性规划问题;而例和例的数学模型中含有非线性函数,因此称为非线性规划问题在线性规划与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合如果一称为可行集或可