运筹学-第1章线性规划与对偶问题

* 1运筹学OPERATIONS RESEARCH单而芳 (上海大学 管理学院 )公共邮箱 cst_ 201211* 2一、课程基本情况n 课程名称：运筹学 q Operations Research n 参考书：q 管理运筹学，于丽英（主编），同济大学出版社 ,2012q 运筹学教程（第三版），胡运权（主编），清华大学出版社,2007q 运筹学（第三版），运筹学教材编写组，清华大学出版社 ,2005* 3二、课程主要内容n 绪论n 线性规划n 运输问题n 整数规划n 网络优化（网络规划，网络计划技术）n 动态规划n 决策分析* 4三、课程考核方法n 平时成绩占 30%，包括：q 课堂考勤q 平时作业q 课堂讨论，练习q 课堂提问n 期末闭卷考试占 70%。* 5绪 论n 运筹学的含义及其发展n 运筹学的模型化方法论* 6n 运筹学的产生与发展q 三个来源军事、管理、经济q 运筹学的发展历程n 运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题 . 大规模轰炸的效果 搜索和攻击敌军潜水艇的策略 兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为 “作战研究 ”，英文是 Operational Research，在美国称为 Operations Research。0.1 运筹学的含义及其发展* 7第二次世界大战期间， “OR”成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为 “OR”后来的发展铺平了道路。n 战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样， Operations Research就转义成为 “作业研究 ”。n 世界上不少国家已成立了致力于该领域及相关活动的专门学会，美国于 1952年成立了运筹学会，并出版期刊 运筹学 ，世界其它国家也先后创办了运筹学会与期刊， 1957年成立了国际运筹学协会。q 运筹学在中国的发展n 1957年，我国科学家从 史记 中的古语 “夫运筹帷幄之中、决胜千里之外 ”摘取 “运筹 ”二字，把 Operations Research译成 “运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义n 我国运筹学的主要奠基人 :钱学森、华罗庚、许国志等。* 8n 运筹学的含义及其与其他学科的关系q 运筹学 Operations Research ,简称 ORn 研究如何以合理的方式，组织具有明确目标的活动的学科。n 研究在某一系统中，如何 统筹安排 ，合理利用，以使该系统在某些方面的 总效益达到最优 的一门学科。n 是由各领域的专家学者协力完成并从各领域角度出发而得出的 定量解决问题的方法 。* 9q 运筹学与决策科学的关系n 决策科学是 研究决策过程规律 , 提供决策方法的科学。决策过程可用决策问题表达如下 :OPTz(x)x S()其中 x为决策方案；S()为环境条件 下所有决策方案 x的集合；z(x)为关于决策方案 x的目标 (评价 )指标体系；OPT为关于 z(x)的 “最优 ”选择。对于环境 下的所有可行方案 x S(),依据决策准则 OPT， 依据指标 z(x)选择 “最优 ”者。* 10q 运筹学与管理科学的关系n 从管理的角度看，可以说运筹学是用 定量方法 为管理决策提供依据的一门学科。以便 实现 有效管理 、正确决策 和 现代化管理 可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案 ”。n 现在普遍认为，运筹学是近代 应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。n 运筹学已成为管理科学中最重要的组成部分之一。 * 110.2 运筹学的模型化方法论运筹学解决问题的关键 建立模型 确定现实问题模型模型解实施方案建摸分析求解解释* 12n 按照模型特征的分类：q 线性规划q 整数规划q 网络规划q 动态规划q 非线性规划q 多目标规划q 存贮论q 决策论q 排队论q 博弈论q 搜索论， 等等* 13n 运筹学模型求解的软件介绍 q EXCELq MATLAB q WINQSB q LINDO q LINGO q 等等* 14运筹学在管理中的应用n 生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等n 库存管理：多种物资库存量的管理，库存方式、库存量等n 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等n 人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等n 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等n 财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等n 设备维修、更新，项目选择、评价，工程优化设计与管理等n 城市交通* 15第一章 线性规划(Linear Programming, LP)n 线性规划模型n 图解法及单纯形算法几何意义n 单纯形算法及扩展n 对偶线性规划n 灵敏度分析n 线性规划应用举例n 软件应用* 161.1 线性规划模型n 生产计划模型n 运输模型n 投资模型n 人员安排模型n 等等* 17甲 乙 生产能力A生产线 1 0 12B生产线 0 1 8检测车间 1 2 20利润 100 250例 1 生产计划问题如何安排每天的如何安排每天的生产，使利润最生产，使利润最大大 ？产品甲产品乙* 18x1 12 x2 8x1 + 2x2 20x1， x2 0max Z= 100x1 +250x2s.t.解 : 设产品甲 , 乙产量分别为变量 x1 ， x2注意模型特点这是约束条件（资源量的限制和产品数量非负的限制）这是目标函数* 19例 2 运输问题单位运费 甲 乙 丙 供应量A 7 9 3 18B 1 5 4 12C 2 4 2 12需求量 6 16 8如何安排运输，可使总运费最小？销售点工厂* 20设 xij为 i 厂运到 j销售点的运输量 (i 1,2,3， j 1,2,3)minZ= 7x11 + 9x12+3x13+x21 +5x22 +4x23 +2x31 +4x32 +2x33s.t. x11 +x12+x13 18x21+x22+x23 12x31+x32+x33 12x11 +x21+x31 = 6x12 +x22+x32 = 16x13 +x23+x33 = 8xij 0注意模型特点* 21例 3 投资计划问题。某公司现有资金 10万元，欲制定其后三年对四个项目的投资计划，四个项目投资要求和收益如下：q 项目 1， 第一年至第三年每年年初投资，每年末回收本年本利 111%(即投资额的 111%，以下同 );q 项目 2， 第二年年初投资，第三年末回收本利 125%，但规定投资不超过 3万元 ;q 项目 3， 第三年初投资，年末收本利 120%， 但规定投资额不超过 4万元 ;q 项目 4， 第一年，第二年每年初投资，次年末收本利115%。公司应怎样对各年各项目投资，才能使第三年末拥有的资金量 (本利和 )最大 ? * 22n 分析1 2 31 x11 x21 x31 1.112 x22 1.25 33 x33 1.2 4 4 x14 x24 1.15maxXik( i =1,2,3; k =1,2,3,4)第 i年初投 k项目的资金数* 23n xik( i =1,2,3; k =1,2,3,4)第 i年初投 k项目的资金数n MaxZ= 1.11x31 +1.25 x22+1.2x33+1.15x24s.t.x11+x14=10x21+x22+x24= 1.11 x11x22 3x31 +x33 =1.11 x21+ 1.15x14x33 4xik 0 ( i =1,2,3; k =1,2,3,4)* 24例 4 租借计划某公司拟在下一年度的 1-4月的 4个月内需租用仓库堆放物资。已知各月所需仓库面积如表。仓库租借费用随合同期而定，期限越长，折扣越大，具体如表。该公司可根据需要在任何一个月初办理租借合同，每次办理时可签订各类合同。试建立总租借费用最小的租借计划。 月 1 2 3 4面积（ 100m2） 12 20 15 10租借期限 1个月 2个月 3个月 4个月合同期内租费（元/100m2）2000 3200 4200 4800* 25n 分析1 2 3 41 x11 x21 x31 x41 20002 x12 x22 x32 3200 3 x13 x23 42004 x14 480012 20 15 10xij( i =1,2,3,4; j =1,2,3,4)第 i月月初签订租借期为 j个月的合同租借面积租借期* 26xij( i =1,2,3,4; j =1,2,3,4)第 i月月初签订租借期为 j个月的合同租借面积资金数minZ= 2000（ x11 + x21+x31+x41 ） +3200（ x12 +x22 + x32 ） + 4200（ x13 +x23 ） 4800 x14 s.t.x11 +x12+x13 +x14 =12x21+x22+x23 + x12 +x23+x14=20x31+x22+x32 +x13 +x23+x14 =15x41 +x32+x23 +x14 = 10xij 0 ( i =1,2,3,4; j =1,2,3,4)* 27例 5 人员安排计划某昼夜服务的公交线路每天各时间区段所需司机和乘务人员数如表1-6所示。设司机和乘务人员分别在各时间区段一开始时上班，并连续工作 8h，问该公交线路 至少 需配备多少名司机和乘务人员。 班次 工作时间 所需司机人数（人） 所需乘务人员人数（人） 1 6:00-10:00 20 102 10:00-14:00 12 63 14:00-18:00 20 104 18:00-22:00 16 85 22:00-2:00 10 56 2:00-6:00 8 4* 28设 xi ， yi (i 1， 2， ， 6)分别表示第 i班次开始上班的司机和乘务员人数 ， * 29线性规划模型特点n 决策变量 ：向