运输问题
• 根据目标的类型，问题分为：线性问题或非线性问题； 单目标或多目标问题。 • 根据约束的类型，问题可分为：二维或三维问题；平 衡问题或非平衡问题。 • 基本的运输问题是线性单目标二维平衡问题。 • 线性运输问题：从不同的供给起点和来源向不同的终 点运送同一种物品，每个端点需要特定数量的物品。 问题是如何分配在每个起点的供给，以便在满足每个 终点需求的条件下，优化某个目标。 • 常用的目标函数是最小全部运输费用、最小全部加权 距离和最大全部利润等。
作业车间调度问题描述
• 例如：单机排序问题——4个工作，P1=8， P2=18，P3=5，P4=15，求总流水时间最小 的顺序。 • 原则：最短时间优先。 • F=4•5+3•8+2•15+18=92=F*
机器调度问题
• • • • 应用领域：机械制造、逻辑、计算机结构等 主要方面：机械配置、工件特征、目标函数 单机和多机调度问题 工件特征包括：工件之间的先后关系、工件下 达时间、工件交货期和工件的优先权等。 • 目标函数包括单目标问题和多目标问题。目标 函数还进一步分为规则度量和非规则度量。例 如非规则性能度量可以随着工件完成时间的减 少而增加。
• • • • 优化理论与方法 优化控制 基础——介绍 提高——讨论
背包问题
• 从多种物品（一般称为项目）中选择几 件物品，装满背包。 • 不同的项目有不同的重量和价值，背包 有最大承重量。 • 背包问题就是要在不超过背包承重量的 前提下，使装入背包的价值最大。 • 阿里巴巴的故事
பைடு நூலகம்
旅行商问题
• 一个商人要找一条通过n个城市的最短巡 回。 • 邮递员的路线
可靠性优化问题
• 可靠性是系统性能的度量。 • 随着系统复杂程度的增加，系统的非可靠性以 费用、费力程度和寿命等方面的问题来表示。 • 系统的可靠性可以定义为：系统在给定的时间 区段和状态下正常工作的概率。 • 研究的领域：可靠性分析、失效建模、可靠性 优化、可靠性增长与建模、可靠性测试、可靠 性数据分析、加速测试及生命周期费用等。 • 优化主要集中于冗余元件的最优分配和比较设 计的最优选择以满足系统的需求。
最优化与最优控制
安徽工业大学电气信息学院 张捍东 2009年2月
主要内容
• • • • • • 工程优化问题 不同优化方法 决策方法与过程 对于问题的求解 进一步的思考 课程内容安排
工程优化问题
• • • • • • • 公开、公平、公正 满意——办人民满意的大学 和谐——和谐社会 榜样——英雄人物、劳动模范 示范——示范工程、示范中心 基地——实验基地 没有最好，只有更好；不怕不识货，就怕货比 货；货比三家不吃亏；便宜没好货，好货不便 宜
作业车间调度问题
• 机器调度问题来源于不同的领域：柔性 制造系统、生产计划、计算机设计、后 勤及通信等。 • 这些问题的共同特性是：没有一个有效 的算法能在多项式时间内求出其最优解。 • 古典的作业车间调度问题是最著名的机 器调度问题之一。
作业车间调度问题描述
• 给定一个工件的集合和一个机器的集合， 每个工件包括多道工序，每道工序需要 在一台给定的机器上非间断地加工某一 段时间；每台机器最多只能加工一道工 序；调度就是把工序分配给机器上的某 个时间段。 • 问题的目标是找到最小时间长度。
工程优化问题
• 选择投资方法（股票、基金、储蓄）、资金额、 组合方式（不要把鸡蛋放在同一个栏子里）等 • 企业转型：关、停、并、转； • 合作方式：独资、合资、承包、租赁 • 新产品的投入计划与策略，产品的生命周期 • 技术改造：引进、吸收、消化、集成、创新
工程优化问题
• 公用事业合作实例：中北巴士、港华燃气、首 创水务 • 马钢一钢厂改造：平改电→平改转 • 马钢的内部结构调整：一钢轧、… • 马钢新区建设 • 马鞍山的东向发展 • 宝钢对于梅山钢铁公司的合并
工程优化问题
• • • • • 研究生招生：综合优化 选拔领导，招收公务员，人才市场 超市的布点、流通的方式、货物摆放 房地产开发 优先发展公共交通事业
若干问题举例
• 组合优化问题：具有有限个可行解的优化问题。 例如如何有效地利用不充足的资源以提高生产 效率。包括车辆路径问题、作业车间调度问题、 网络设计、设备分配与布置等 • 背包问题 • 二次指派问题 • 旅行商问题 • 影片递送问题 • 应用：基本问题求解，复杂问题推广。算法检 验效果。
工程优化问题
• • • • • 问题——发现问题 理解——理解含义 解决——求解方法 解释——合理解释 发现问题、解决问题的能力
工程优化问题
• • • • • • 对于问题的描述（刻画） 目标函数 约束条件 可选方案 系统状态 存在优化的状态、寻找状态、恰当判断、 合理决策
工程优化问题
• • • • • • • • • 选择方案 选择人员 选择技术 选择场地 选择设备 选择时间 选择顺序 协议、契约、合同、承诺、诚信 考虑性能价格比
当前值得关心的问题
• • • • • • • • 金融危机 次贷危机 房地产 市场与政府的作用 救市救什么 医疗改革 优化资源配置——激励、风险、联盟 节能降耗
当前值得关心的问题
• • • • • 公平与效率 就业与升学 继承与创新 学生适应社会 教育改革——结构、规模、质量、效益
课程内容安排
设备布局设计问题
• 在制造等环境中，布局设计是指在确定 的区域内最适宜地安排物理设备，如车 间或者机器。 • 通常设计准则是最小化储运费用等。
优化与控制问题
• • • • • • • • • 优化的方法——经典、现代、智能 检测、通讯与控制的手段、工具、方法 控制理论 控制方法 控制器 执行机构 控制对象 测量的变化：例如传感器的不同 通讯的变化：例如网络连接方式