第一章 运筹学―线性规划1001上传

运筹学OperationalResearch天津大学管理学院教师简介张小涛，博士，副教授研究方向：计算实验金融，中小企业融资Email：[e-mail]@gmail.com运筹学简介什么是运筹学?运筹学的简史运筹学的分支有哪些?运筹学研究的一般程序课程要求2020/2/17古籍中的运筹问题田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议……——《十万个为什么.数学分册》P.312最早记载的《对策论》范例。2020/2/17123456上上上中中下下中中下上下中上下下中下上上中齐王田忌古籍中的运筹问题祥符中,禁火。时丁晋公主营复宫室,患取土远,公乃令凿通衢取土,不日皆成巨堑。乃决汴水入堑中,引诸道竹木排筏及船运杂材,尽自堑中入至宫门。事毕,却以斥弃瓦砾灰壤实于堑中,复为街衢。一举而三役济,计省费以亿万计。——沈括《梦溪笔谈.补笔谈卷二.权智》2020/2/17“运筹”的出典据《史记》记载：汉高祖刘邦称赞张良：运筹策帷帐中，决胜千里外，子房功也。——司马迁《史记·留侯世家》“筹”是古代比算盘还早的计算工具之一。“运筹”是计划、安排、比较、决策优化的一个过程。英文名：OperationalResearch,港台地区译为：《作业研究》、《运作研究》。五十年代末华罗庚等人介绍国外这一门新兴学科时就建议定名为：运筹学。近几十年来随着计算机的普及它的应用越来越广泛。其作用越来越被人们所认识。大学里为什么要开设《运筹学》呢?请自己考虑。2020/2/17我国当代数学家在《运筹学》中的贡献1957年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。20世纪70年代华罗庚先生在中国大力创导推广“统筹学”当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。凡是讲图论的优化的教科书，多半有专门的一章名：ChinesePostmanProblems,其中无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题(CPP)。2020/2/17运筹学（OperationalResearch)运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。2020/2/17运筹学的应用经济、工商管理；计算机算法的设计；数学理论；军事；工业；农、林、牧、渔业;医学、生物、理化、遗传；工程计划、安排等“优化”;学习、日常生活、旅游等。2020/2/17运筹学的发展：三个来源军事管理经济军事：运筹学的主要发源地古代军事运筹学思想中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。运筹学的正式产生：第二次世界大战鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。Blackett备忘录1941年12月，Blackett应盟国政府的要求，写了五份题为“ScientistsattheOperationalLevel”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁英国战斗机中队援法的决策管理泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等爱尔朗（Erlong）的排队论公式1909－1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支－－排队论。经济（数理经济学）VonNeumann与对策论1932年，VonNeumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的《对策论与经济行为》开创了对策论分支。康托洛维奇与“生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作－－《生产组织与计划中的数学方法》，其思想和模型被归入线性规划范畴。运筹学的性质和特点应用科学－“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。运筹学的特点定量化分析多学科交叉，如综合利用了心理学、经济学、物理等方法最优决策管理运筹学的工作程序明确问题问题分类建立数学模型求解数学模型结果分析实施运筹学的分支规划论(分线性、非线性、整数、目标、动态及随机规划等)图论与网络优化；排队论、存储论、搜索论；对策论(博弈论)、；可靠性理论;全面质量管理(TQC);计划评审、维修更新理论等。课程教材：胡运权，运筹学教程，北京：清华大学出版社，2007；主要参考书：[1]丁以中主编，管理科学---运用Spreadsheet建模和求解，北京：清华大学出版社，2003；[2][美]弗雷德里克·S·希利尔（FrederickSHillier）,任建标译,数据、模型与决策（原书名IntroductiontoManagementScience），北京：中国财政经济出版社，2004；[3]谢金星，优化建模LINDO/LINGO软件，清华大学出版社[4]钱颂迪等，运筹学，北京：清华大学出版社，1990；[5]吴育华,杜纲.《管理科学基础》，天津大学出版社。主要授课内容：•线性规划:模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整数规划•图论与网络分析•网络计划•动态规划•风险型决策•排队论•随机模拟课程基本要求掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算具备计算机解题的基本能力认真听课，勤于思考，多看书每周一交作业，独立完成闭卷考试有问题请Email联系第一章线性规划（LinearProgramming，简称LP）§1线性规划的模型与图解法一、LP问题及其数学模型例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。127单价300103油20054电36049煤资源限制乙甲产品资源甲乙资源限制煤94360电45200油310300单价712产品资源线性规划模型三要素：（1）决策变量设甲产品生产x1，乙产品生产x2（2）目标函数MaxZ=7x1+12x2（3）约束条件9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.返回SubjectTo，意为“使其满足”Max（Min）Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤（=,≥）b1……am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0s.t.LP模型的一般形式矩阵表示MaxZ=CXAX≤bX≥0s.t.其中:X=(x1,x2,…,xn)T为决策变量C=(c1,c2,…,cn)称为价格系数A=(aij)m×n称为技术系数b=(b1,b2,…,bm)T称为资源系数线性规划问题隐含的假定：•比例性假定•可加性假定•连续性假定•确定性假定线性规划问题隐含的假定：•比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。•可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。•连续性假定：线性规划问题中的决策变量应取连续值。•确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。例2某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千块)150000(吨)20000(吨)110000(千元)资源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105砖混住宅人工(工日/m2)砖(块/m2)钢材(公斤/m2)造价(元/m2)资源住宅体系解:设今年计划修建砖混、壁板、大模住宅各为x1,x2,x3m2,z为总面积,则本问题的数学模型为:0,,40000035.0003.00045.0147000210.0150000180.0190.0110.020000025.0030.0012.0110000120.0135.0105.0.3213211321321321xxxxxxxxxxxxxxxxts321xxxMaxz前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料答案：设购买M饲料x1，N饲料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2思考题二、线性规划的图解法1.步骤（1）作约束的图形——可行域可行解的集合①先作非负约束②再作资源约束9x1+4x2=3604x1+5x2=2003x1+10x2=300公共部分，即为可行域例：煤电油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.x1x240206080100204060801000（2）作目标函数的等值线①给z不同的值，作相应直线，判断出z增大时，直线的移动方向②将直线向增大方向移动，直至可行域边界，交点X*即为最优解。7x1+12x2=847x1+12x2=168如：令7x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10x2=300x1x240206080100204060801000X*=（20，24），Z*=428最优解：x1=0，x2=1最优目标值z=3课堂练习图解法求解线性规划0,)3(22)2(22)1(432min2121212121xxxxxxxxstxxz012341234x1x2O-1-2(1)(2)(3)2.LP解的几种情况（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解补充知识：凸集凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的