运筹学第一章线性规划与单纯形法

运筹学 陈克东 上海工程技术大学 管理学院 “ 一门科学只有成功的应用数学时，才算达到了完善的地步 ”- 马克思运筹学的发展：三个来源v 军 事v 管 理v 经 济运筹学思想方法的起源可追溯到古代u我国先秦时期诸子著作中就存在许多朴素的运筹思想 . u 孙子兵法 中有丰富的运筹思想 . 军事起源u在国外 , 运筹学思想也可追溯到很早以前 . 如阿基米德、达芬奇、伽利略等都研究过作战问题军事起源二战期间 u1939年 , 由英国曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获得诺贝尔奖的布莱凯特(P.M.S.Blackett)为首 , 组建了一个代号为 “Blackett马戏团 ”的研究小组 , 专门就改进防空系统进行研究u二战中 , 除英国外 , 美国、加拿大等国也相继成立了军事运筹研究小组 ,解决战争中提出的运筹学课题 . 其中最著名的工作之一是改进深水炸弹的起爆深度 .军事起源资料 当时德国的潜水艇严重威胁盟军的运输船 , 1942年 , 美国大西洋舰队主持反潜战的官员贝克 (W.D.Baker)请求成立反潜战运筹组 , 麻省理工学院的物理学家莫尔斯 (P. W.Morse)被请来担任计划与监督 .莫尔斯领导的小组经过多方实地调查 , 提出两条重要建议：1. 将反潜攻击由反潜舰艇投掷水雷改为由飞机投掷深水炸弹 ; 仅当潜艇浮出水面或刚下潜时 , 方投掷深水炸弹 ; 深水炸弹的定深 (指起爆深度 )由 100-200英尺 , 修正为 20-50英尺 .2. 改进运送物资的船队及护航舰艇编队的方式 , 由小规模多批次 , 改进为加大规模、减少批次 , 可使损失减少，军方采用了上述建议 , 重创德国潜艇舰队 , 最终成功地打破了德国的海上封锁 . 军事起源 战争结束时 , 英美及加拿大军队中工作的运筹学工作者已超过了 700人 . 正是由于战争需要的促进 , 以及大批著名科学家的参与 , 运筹学得到迅速发展. 之后 , 运筹学从单纯军事和战争中的应用研究 , 扩展到经济和管理领域 , 并形成了自己的理论与方法. 1948年 , 美国麻省理工学院（ MIT）率先开设了运筹学课程 , 许多大学群起效法 , 内容也日益丰富。军事起源 1951年 , 莫尔斯和金博尔出版了 (1946年内部出版, 1951年公开出版 )第一本运筹学专著 : 运筹学的方法 (The Methods of Operations Research). 书中总结了第二次世界大战中运筹学的军事应用 , 并给出了运筹学的一个著名定义 运筹学 是为执行部门对它们控制下的 “业务 ”活动采取决策提供定量依据的科学方法 .管理起源第一次世界大战前就已经发展成熟的古典管理学派 , 对运筹学的产生和发展影响很大。1911年 , 泰勒出版了著名的 科学管理原理 一书 . 书中, 泰勒的管理思想和理论 , 概括起来主要有以下三个观点： 科学管理的根本目的是谋求最高工作效率。 达到最高工作效率的重要手段是科学的管理方法。 实施科学管理要求精神上的彻底变革。 根据以上观点泰勒提出管理制度 : 最佳动作原理 ; 合理的日工作量或恰当的工作定额原理 ; 刺激性付酬制度等 .与泰勒同时代的 , 对管理改革作出贡献的还有一些学者亨利 甘特甘特的贡献主要有以下几点：p提出了一种 “工资任务加奖金 ”的工资制度p1903年 , 发明了 “甘特图 ”. 至今还在实践中使用 , 并发展为统筹方法p强调管理民主和重视人的领导方式管理起源管理起源弗兰克 杰尔布雷斯夫妇 .有影响的著作有 : 动作研究 (1911年 )、 科学管理入门 (1912年 )以及 疲劳研究 (1916年 )等 . 他们的研究比泰勒的研究更为细致和广泛 , 其重要贡献在以下几方面：p 提出动作研究和动作经济原理p 疲劳研究 . p 注意到了工作、工人和环境之间的相互影响 .爱尔朗（ Erlong）的排队论公式1909 1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是 1909年的论文 “概率与电话通话理论 ”，开创了运筹学的重要分支排队论。管理起源带有拥挤效应的服务行业如通讯业、交通运输业等都隐含排队论的问题。经济起源经济学理论对运筹学的影响是和数理经济学学派紧密联系的 数理经济学对运筹学 , 特别是对线性规划的影响可以从魁奈 (Qusnay)1758年发表的 经济表 算起 . 最著名的经济学家沃尔拉斯 (Walras)研究了经济平衡问题 , 后来的经济学家对其数学形式继续研究并得到深入发展 . 1928年 冯 .诺伊曼以研究二人零和对策的一系列论文为 “对策论 ”奠基 . 1932年 , 又提出了广义经济平衡模型 . 1939年 , 苏联的康托洛维奇发表 生产组织和计划中的数学方法 .这些工作都可以看作是运筹学的先驱工作发展二战结束后 , 运筹学很快深入到工业、商业、政府部门等 , 并得到了迅速发展；运筹学在中国研究及应用从 20世纪 50年代中期开始。1957年 , 我国在建筑业和纺织业中首先应用运筹学 . 1958年 , 开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用20世纪 60年代起 , 在钢铁和石油部门得到了比较全面、深入的应用1965年起统筹法在建筑业、大型设备维修计划等方面的应用取得可喜的进展 . 1970年在全国大部分省、市和部门推广优选法70年代中期 , 最优化方法在工程设计界受到了广泛的重视 , 并在许多方面取得成果 ; 排队论开始应用于矿山、港口、电信及计算机设计等方面 ; 图论用于线路布置、计算机设计、化学物品的存放等70年代后期 , 存储论在应用汽车工业等方面获得成功近年来 , 运筹学已趋向研究和解决规模更大、更复杂的问题 , 并与系统工程紧密结合 .来历及定义二战期间 , 英国为了研究 “如何最好地运用空军及新发明的雷达保护国家 ”, 成立了一个由各方面专家组成的交叉学科小组 .这就是最早的运筹学小组 , 它的任务是进行 “作战研究 ”(Operational Research). 后来 , 美国从事这方面研究的科学家又称之为 “ Operations Research”, 简称为 O.R. O.R.的中文译名 “运筹学 ”取自成语 “运筹帷幄之中，决胜千里之外 ”，具有运用筹划，出谋献策，以策略取胜等内涵。目前国外的 管理科学 （ Management Science）与 运筹学 的内容基本相同运筹学是一门应用科学 , 它广泛地应用现有 科学技术知识 和 数学方法 , 解决实际中提出的 专门问题 , 为决策者选择最优决策 提供定量的依据 .运筹学发展三阶段：创建时期（ 45年至 50年代初）1948年 英国成立 “运筹学 ”俱乐部1948年 麻省理工学院 介绍运筹学1950年 伯明翰大学开设运筹学课程1952年 卡斯大学 设立运筹学硕士和博士学位1947年 丹捷格 提出单纯形法50年代初 计算机求解线性规划获得成功成长时期（ 50年代初至 50年代末）多个国家成立运筹学会，多种运筹学刊物问世1957年 在牛津大学召开第一次国际运筹学会议1959年 成立国际运筹学联合会迅速发展时期（ 60年代以来）运筹学进一步分为各个分支，更多运筹学出版物运筹学课程纳入教学计划我国运筹学发展历程：1956年 运筹学小组1958年 运筹学研究室1960年 应用运筹学经验交流会议1962年 全国运筹学专业学术会议1978年 全国运筹学专业学术会议1980年 成立中国运筹学学会运筹学分支运筹学是一门以决策支持为目标的学科，运筹学的内容丰富，应用范围非常之广，从军事、政治到管理、经济及工程技术等许多领域都能应用到运筹学的思想和方法。经过半个世纪左右的发展，运筹学形成了下面主要几个分支在这过程中，科学家，学者和 工程师 都起了很大的作用，在其它很多领域也是这样的！运筹学的分支 : 线性规划（ linear programming） 整数规划（ integer programming ） 运输问题 （ transportation Problems ） 多目标规划（ multiobjective programming ） 图论与网络分析（ graph theory and network analysis） 非线性规划（ nonlinear programming） 动态规划（ dynamic programming） 对策论（ game theory） 决策论（ decision theory） 排队论（ queueing theory） 存贮论（ inventory theory）运筹学的作用 运营管理：生产计划，项目进度和物资供应计划 物流管理：仓贮控制，配送中心选址，配送运输调度 财务和投资管理：资金流分析，债务链清偿，证券组合选择，商品套利和套期，资产定价 人力资源管理：调薪方案，人力资源分配 质量管理：服务系统分析 市场分析：市场占有率转移分析和模拟 社会系统分析：交通管理，社会保障系统分析，人口发展分析 .随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 运筹学有广阔的应用领域，它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面。 运筹学是软科学中 “硬度 ”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。本课程的要求和说明目 的： 通过学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点 ,理解 线性规划、整数规划、运输问题 、目标规划，图与网络等分支的基本优化原理，掌握其中常用的模型和算法 ,具有一定的建模能力。先修课程 : 线性代数，高等数学 等 .要 求 ： 课前预习，课后要复习课堂认真听讲（不能旷课）认真完成作业成 绩： 平时成绩 30% （作业、出勤、课堂纪律、实验报告）+考试成绩 70%答疑时间： 每次课后时间，周二、周五下午（行政楼 619 ，电话或短信联系）参考书目： 运筹学教程（第二版 胡运权 清华大学出版社 运筹学 赵可培 ,上海财经大学出版社 管理运筹学 谢家平 , 中国人民大学出版社复习线性代数内容 :列向量 x=(x1， x2， ， xn） T为 n维列向量。 xRn行向量 x=(x1， x2， ， xn） 为 n维列向量。 xRn矩阵 (向量 )运算规则 加减乘、求逆运算 结合律 分配律交换律 乘法无交换律线性相关 一组向量 v1, ,vn,如果有一组不全为零的系数 1, , n,使得 : 1 v1+ + nvn=0 则称 v1, ,vn 是线性相关的 .线性无关 一组向量 v1, ,vn,如果对于任何数 1, , n,若要满足 : 1 v1+ + nvn=0 ,则必有系数 1= = n=0,(全为零 )则称 v1, ,vn线性无关 . 矩阵 A的秩 设 A为一个 mn 阶矩阵 (mn)若矩阵中最大线性无关列向量个数为 k,则称矩阵 A的秩为 k,记为 rank(A)=k.Chapter 1线性规划与单纯形法Linear programming and the simplex method上海工程技术大学 管理学院Chapter 1 线性规划与单纯形法 线性规划 是用线性数学模型表示不同的生产活动、营销活动、金融活动或其他活动的计划。 引言引言本章重点1、根据实际问题写出线性规划模型2、掌握线性规划化标准型的方法3、理解并掌握线性规划解的概念4、能够用图解法求解线性规划问题5、熟练掌握线性规划单纯形法的基本思想和 步骤难点难点线性规划 （ Linear Programming,缩写为 LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。Chapter 1 线性规划与单纯形法 1 线性规划数学模型1.1问题的提出 线性规划应用的问题种类繁多，形式各异，主要分为四类线性规划问题。前三类问题分别是资源分配问题，成本效益问题以及