斯隆运筹学-最优化理论01

《斯隆运筹学-最优化理论01》由会员分享，可在线阅读，更多相关《斯隆运筹学-最优化理论01（8页珍藏版）》请在金锄头文库上搜索。

1、 15.053 2002 年年 2 月月 5 日日 ? 最优化导论 分发：讲稿 概述概述 教学大纲和常用信息 讲稿 作业 1 第第 3 页是麻省理工学院的特定信息页是麻省理工学院的特定信息 ? 其他资源： Winston 著 运筹学 Bertsimas 建立了 MIT 运筹学中心，协助建 立了 ORSA（美国运筹学学会） 。什么是管理科学（运筹学）？什么是管理科学（运筹学）？ ? 今天：运筹学与管理科学是指在现 有信息状态下，运用数学模型指导 管理者进行有效的决策，或者在现 有信息不足时，为决策者做出正确 的决策寻求更多信息。 ? 相关领域：决策科学，系统分析， 运筹学，系统动力学，运营分析，

2、 工程系统学，系统工程等等。 历史的名句历史的名句 ? 不浪费时间和资金，使二者利用率 最大。 Benjamin Franklin ? 显然，效率最高的类型在于最大化 利用现有物资。 Jawaharlal Nehru ? 很有可能，一个普通人在不损害自 身健康的情况下可以把效率提高 50%。 Walter Scott 运筹学发展历史运筹学发展历史 ? 1947 年 George Dantzig 等人的 Scoop 项目 （最适宜的科学计算程序） ，建立了 线性规划的单纯形法。 ? 1950-1959 排队论、数学规划等数学理论得 到发展，获得大量可喜的成果。 相关领域：1960 年代航空业 ?

3、 1960-1969 更多成就，更大的发展，重大的 规划 相关领域：1980 年代航空业 运筹学发展历史运筹学发展历史 ? 1970-1979 遭遇挫折，暂停发展。不完全 NP 问题。更多的实际要求。 ? 1980-1989 PC 广泛应用。 数据获取更加容易。 决策者普遍愿意使用模型。 ? 1990-1999 修正了运筹学的应用，运筹学技 术的大量涌现，比如最优化和电 子数据表格的加载仿真包，建模 语言，大规模优化。运筹学与航 空业更加密切地结合。 2000 年以后运筹学的新发展年以后运筹学的新发展 ? 运筹学应用作为独立领域 ? 数据，数据，还是数据 电子交易数据（点击量，采购， 其他交易

4、数据，电子邮件等） 人类基因组工程及其派生影响。 ? 需要更加自动化的决策 ? 日益增长的协调资源的有效利用问 题（供应链管理） 最 优 化 像 时 间 一 样永存。 自然科学中的最优化 亚历山大时期的 Heron(海伦) 公元 1 世纪 费马 1628-29 微积分微积分 入射角 入 射 角 1 反射角 入射角 折 射 角2 费马，牛顿，欧拉，拉格朗日，高斯等。课程的一些主旨课程的一些主旨 ? 最优化无处不在 ? 模型，模型，还是模型 ? 建模的目的是洞察，而不是数字 Richard Hamming 注解 极大值 ? 算法，算法，还是算法 极小值 最优化无处不在最优化无处不在 ? 对事物知道

5、的越多，越能知道最优 化的应用。 ? 一些个人决策的示例 确定最快回家（到校）路径； 课后作业时间优化分配； 预算最优化； 选择专业方向。 最优化无处不在最优化无处不在 ? MIT 的一些决策示例 确定考试次数使重复最小； 在既定约束下给课程分配教室 和时间； 确定停车费用价格和公共交通 补贴，以最大程度体现公平并提 供足够的通道； 最优化筹资。 最优化无处不在最优化无处不在 ? 练习：向你临近的同学自我介绍， 之后讲一两个你比较熟悉的主题 （暑期工作，专业，或者父母的职 业或者其他的什么） 。 ? 然后和你的同伴一起讨论产生最优 化的地方。 ? 之后，选择 2 或 3 个你所喜欢的应 用与大

6、家分享。 本课程与最优化工具本课程与最优化工具 ? 最优化问题无处不在，但是最优化 工具并没有得到广泛应用。 ? 本课程目标：介绍一些最优化工具， 以及在生产、理财、电子交易、市 场营销等领域的应用。 ? 当你在工作中发现最优化问题（一 定会发现） ，就知道有一些工具可以 帮助你解决。 确定管理问题：管理科学框架确定管理问题：管理科学框架 1. 明确明确要解决的问题； 2. 观察系统并收集数据； 3. 建立解决该问题的数学模型以及其 他重要子问题的数学模型； 4. 验证模型， 并应用模型进行预测和分 析； 5. 选择一个合适的解决方案； 6. 提交解决方案； 7. 执行和评估。 线性规划（第一

7、个工具，也许是最重要 的）线性规划（第一个工具，也许是最重要 的） ? 最大化或者最小化线性目标； ? 线性等式或不等式约束； Max 3x+4y S.t 5x+8y24 x, y0 这是可行解集这是可行解集 术语术语 ? 决策变量：如 x 和 y 一般是指那些可以控制的，用来 改善目标函数、完整描述决策方案 集合的变量。 ? 约束：如x+8y24, x00, y0 决策变量取值的限制条件。 ? 目标函数：如 3x+4y 衡量解优劣次序数量描述； 寻求目标的最大或者最小； 最优解 如净现值最大，成本最小。 与同伴一起建立数学模型与同伴一起建立数学模型 ? 需要做哪些决定？这是决策变量。 ? 目

8、标是什么？用决策变量来表示目 标。 ? 约束是什么？用决策变量表示约 束。 ? 如果有时间，尝试寻找最优解。 雕琢工具公司（雕琢工具公司（GTC） ? 私营企业 ? 建筑工具的使用者和工业市场行情 ? 总部设于西雅图 ? 在美国、加拿大及墨西哥设有工厂； ? 为便于说明，做如下简化假设： 温尼伯湖生产厂，加拿大 有扳钳和老虎钳 用钢铁制造 注模成型设备 组装设备 GTC 问题数据问题数据 扳钳 老虎钳 拥有量 钢铁 1.51 15000 吨 成型设备 11 12000 小时装配设备 0.40.5 5000 小时 需求限制 800010000 盈利 （美元/ 每单位） 0.40.3 我们需要确定

9、在既定原材料，机器工时 和需求限制下扳钳和老虎钳的生产量。 MSR 营销公司（摘自营销公司（摘自 Frontline System）? 需要选择广告以达到 150 万人 ? 成本最低 ? 每种类型的广告数量上限 电视电台 邮件报纸受众规模 5000025000 20000 15000成本 500 200 250 125 最大广告量 20 45 10 15 与你的伙伴一起做与你的伙伴一起做 ? 与你的伙伴一起根据 GTC 问题建立 一个线性规划模型。先不要看讲稿。 ? 设 p 是生产老虎钳的数量； ? w 是生产扳钳的数量。 建立建立 GTC 问题的模型问题的模型 第一步：设定决策变量 p 是生

10、产老虎钳的数量(千)； w 是生产扳钳的数量(千)。 第二步：写出目标函数 Max Profit=0.3p+0.4w 继续建立模型继续建立模型 第三步：确定约束条件 钢材： p+1.5w15000 成型： p+w12000 装配： 0.5p+0.4w5000 钳子需求 p10000 扳钳需求 w8000 我们将在下一讲介绍如何解该问题。 模型的代数表达式模型的代数表达式 ? J 代表产品的集合 如 S=钳子，扳钳； pj代表每单位产品 j 的赢利； dj代表产品 j 的需求量； xj代表产品 j 的生产量。 ? M 代表生产环节的集合 如 M=成型，装配； bi代表生产环节 i 的资源量； a

11、ij代表生产单位产品j消耗的生产 环节 i 的资源量。 模型的代数表达式模型的代数表达式 ? Max Jjjxp j? S.t. , iJjjijbxaMiJjdxjj, Jjxj , 0 即使即使|J|=10000,|M|=100,上述模型依然可 用。上述模型依然可 用。 模型的另一种代数表示形式模型的另一种代数表示形式 ? Max , j=1,n 0jx, j=1,n jjdx , i=1,m jjxps.t. iJjjijbxa线性规划线性规划 ? 线性函数有如下形式： =+=niiinnn xcxcxcxcxxxf.1221121.).,(例如，例如，3x1+4x2-3x4 ? 如果一

12、个数学规划的目标函数是线 性函数，而且约束是线性等式或不 等式，则称之为线性规划。 如约束 3x1+4x2-3x47 x1-2x5=7 ? 一般，线性规划问题有非负约束。 非线性规划允许有一个非线性目标函数 和约束非线性规划允许有一个非线性目标函数 和约束。如 ? Max f(x,y)=xy ? S.t x-y2/210 3x-4y2 x0, y0 整数规划是含有约束全部或者部分决策 变量是整数的线性规划。整数规划是含有约束全部或者部分决策 变量是整数的线性规划。 ? Max 3x2+4x2-3x3 3x1+2x2-x317 3x2-x3=14 x1,x2,x30 并且为整数。 等式约束的线性

13、规划的代数形式等式约束的线性规划的代数形式 ? Max 或者 Min jjxc =nj 1? S.t. mibxainjjij.1,1= =njxj.1, 0= 线性规划假设前提线性规划假设前提： Max 4w+3p 1.5w+p15 . 比例性假定比例性假定： w 对于目标函数的贡献与 w 成比例； 可加性假定可加性假定： p 对于目标函数的贡献与 w 独立； 可分割假定可分割假定：每个决策变量都可是分数； 确定性假定确定性假定：目标函数和约束条件中的 系数是已知的（不存在随机变量） 。 一些成功的事例一些成功的事例 ? 最优化人员安排使美国航空公司每 年节约最优化人员安排使美国航空公司每

14、年节约 2000 万美元；万美元； ? 优化货运路线让优化货运路线让 Yellow Freight 每 年的节约超过每 年的节约超过 1730 万美元；万美元； ? Reynolds Metal 公司通过改进卡车 调度，提高了即时交付率，每年节 约货运成本公司通过改进卡车 调度，提高了即时交付率，每年节 约货运成本 700 万美元；万美元； ? GTE 本地能力扩张每年节约本地能力扩张每年节约 3000 万美元。万美元。 小结小结： ? 回答了什么是运筹学和管理科学， 描述了一些相关的历史背景。 ? 介绍了线性规划中的术语。 ? 两个例子： 1. MSR 营销公司 2. Gemstone To

15、ol 公司 小型（2 维）线性规划，没有明显 的最优解。 ? 下一讲我们将详细讨论这个问题。 一些成功的事例（续）一些成功的事例（续） ? Digital Equipment 通过优化全球供 应链节约了 3 亿美元； ? Proctor & Gamble(保洁公司)通过北 美运营重构，削减了 20%的厂房， 每年节约 2 亿美元； ? 在日本大阪的 Hanshin Expressway， 优化交通控制每年节省 1700 万司机 小时； 一些成功的事例（续）一些成功的事例（续） ? Sadia(巴西)的优化生产计划使连续 三年节约 5000 万美元； ? Harris 公司的生产优化将按时交货 率从 75%提高到 90%； ? Tala 钢铁公司 （印度） 优化了对电力 短缺的反应， 获得 7300 万美元效益； ? 巡逻警队的优化安排每年会节约 1100 万美元； ? Texaco 的配油每年节约 3000 万美 元。 ? 优化水热生成器安排让南部公司每 年节约 1.4 亿美元；