最优化方法绪论

最优化方法

（学时：40）

杨丰梅北京化工大学理学院Email：yangfm@什么是最优化(Optimization)最优化就是在复杂环境中遇到的许多决策问题时，从所有可能的方案中选择最合理的一种方案，以达到最佳目标的一门科学。什么是最优化方法最优化方法就是寻找最优决策的方法。最优化模型线性规划、整数规划、非线性规划、目标规划、动态规划(五规划)对策论、存储论、排队论、决策论、图论(五论)运筹学运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法.

最优化方法被分成两个方面：一是由实际生产或科技问题形成最优化的数学模型，？二是对所形成的数学问题进行数学加工和求解。√最优化的发展历程费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)

f(x)=0欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m一般最优化问题可写成如下形式:1930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；

KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划

6-70年代：Cook等复杂性理论，组合优化迅速发展

电子计算机发展———最优化方法最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，adhoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）1.

食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。1.

食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解2

运输问题设某种物资有m个产地A1,A2,…Am,各产地的产量是a1,a2,…,am;有n个销地B1,B2,…,Bn.各销地的销量是b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2

运输问题（续）以价格qi

购买了si份股票i,i=1,2,…,n股票i的现价是pi你预期一年后股票的价格为ri

在出售股票时需要支付的税金=资本收益×30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50×1000-0.3(50-30)1000-0.1×50×1000=390003

税下投资问题我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3

税下投资问题（续）4

选址问题实例:一组潜在位置（地址）,一组顾客集合及相应的利润和费用数据；解:

设施开放(使用)的数目，他们的位置，以及顾客被哪个设施服务的具体安排方案；目标：总的利润最大化。数据与约束J={1,2,…,n}:放置设施的可能的潜在位置集合I={1,2,…,m}:顾客集合,其要求的服务需要某设施所提供.4

选址问题（续1）5选址问题（续2）6负载平衡(续1)实例:网络G(V,E)

及一组m

个数的集合{s,d>0}，表示

连接源点

s与汇点d

之间的流量解:{s,d>0}的一组路由,即G(V,E)

中m

条s

与

d间的路,

表示连接s与d

的负载流量的路径。目标:极小化网络负载6

负载平衡(续2)7.结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈吸强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。

受力分析图圆杆截面图桁杆示意图

受力分析图圆杆截面图桁杆示意图7.结构设计问题7.结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：

圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为

由此得稳定约束：7.结构设计问题

另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：7.结构设计问题重量应力要求稳定要求1.

线性规划

对偶定理2.

非线性规划

K-K-T定理3.最优化算法

算法设计技巧使用教材：最优化方法何坚勇参考书：最优化理论与算法陈宝林清华大学出版社其他参考书目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性CombinatorialOptimization

蔡茂诚、刘振宏

AlgorithmsandComplexity清华大学出版社，1988

Printice-HallInc.,1982/1998

其他参考书目《最优化技术方法及MATLAB的实现》，曹卫华，郭正，化学工业出版社，2005其他计算方面参考书目：《最优化方法及其MATLAB程序设计》