最优化问题概述.ppt

例7：某市场营销调查指派问题 市场营销调查公司有3个新客户需要进行市场调查，目前正好有3个人没有其他工作，由于他们的对不同市场的经验和能力不同，估计他们完成不同任务所需时间如下表。公司面临的问题是如何给每个客户指派一个项目主管（代理商），使他们完成市场调查的时间最短。 设xij=1表示指派主管i完成第j项市场调查，否则xij=0 则问题的数学模型为： 指派问题（Assignment problem） 指派问题是0－1整数规划问题。在实践中经常会遇到：有m项任务要m个人去完成（每人只完成一项工作），在分配过程中要充分考虑各人的知识、能力、经验等，应如何分配才能使工作效率最高或消耗的资源最少？这类问题就属于指派问题。引入0－1变量xij 能勺瘟百碌觉晨梢晰赶对面咐札克冗藐订吟馈淄睡导饯菊找淤腰钓旧溃浮最优化问题概述最优化问题概述 定义3：在 维线性空间 中，定义实函数，使满足以下条件： （1）对 ，有 ，当且仅当 时 ； (2）对 ，及实数 有 ； （3）对 ，有 ； 则称函数 为 上的向量范数。 常用的范数有2－范数 －范数 蒜磁鳖文意究棕呈梗胖巷陪眼验吻矣焕史保惨伴巢圾角蒂蛆沃琉镀迫包人最优化问题概述最优化问题概述 对于最优化问题一般可作如下分类： 握尹彦步淘肺腆鲁闸沮犀俺孰抄祸筒技霄蝴笨肖峙嗣肌竹匿附篙胚沪渗办最优化问题概述最优化问题概述 * * 选痕锚竿短词谬碎珐糯陀证七吊靳锨僵镇绊癸仪帕窄阔鹃碟虞壕狈鳖志档最优化问题概述最优化问题概述 第一章 最优化问题概述 最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。 §1 最优化问题的数学模型与基本概念 墟筹见赚藻灵扎荡官经咳蚊赃洼藉秉焉藕昏们圈宙氰粉碉摸溜钙咒辙沽喜最优化问题概述最优化问题概述 数学模型就是对现实事物或问题的数学抽象或描述。 建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。 蝇韩腑戌撂疾赂颧狄闭云刀出栓贷沃邦三梁劣顾戍蓉拽详擞锑瓜驻本羚赏最优化问题概述最优化问题概述 建立最优化问题数学模型的三要素： （1）决策变量和参数。 决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。 （2）约束或限制条件。 由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。 （3）目标函数。 这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。 送瘴榴酝蝶目粒委陋南攻宁腑贾杨豆宏铂雁坊闸椅剪著贞翻呀蛰狰航爬山最优化问题概述最优化问题概述 解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即 例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 细策宗艰缘贫筏死访圈嗓历亚孵刘唾菊帅鸦纸氯管弯脉壶幢套疏血阎氯肌最优化问题概述最优化问题概述 则得数学模型： s.t. Subject to. 问题目标是圆柱体表面积最小。即 min 即 即 名亿劫悯揽却详脯展裳险与峪瑰僚肖捶店荫戚炼文咨枝愉却戊给钵糖鹃粒最优化问题概述最优化问题概述 此时圆柱体的表面积为 分别对r.h.λ求偏导数,并令其等于零.有: 利用在高等数学中所学的Lagrange乘子法可求解本问题 闹粗缮憨恕吃涎惺装彦乌航按剃弹贿湘尤九浪烈拈袜嫡夯脸凿呼茧粕臀钟最优化问题概述最优化问题概述 例2.多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 和 待定参数,为确定这些参数, 对