第01章 线性规划及单纯形法.ppt

电子商务基本知识 运 筹 学 贾江鸣 浙江理工大学工业工程系 手机 邮件：jarky@126.com 教材结构 第1章 线性规划与单纯形法 第2章 线性规划的对偶理论与灵敏度分析 第3章 运输问题 第4章 目标规划 第5章 整数规划 第6章 图与网络规划 第7章 动态规划 第9章 存贮论 考核方式 期末成绩70%+平时30% 必修课：期末闭卷考试 如何理解成绩的“三公”：公平、公正和公开 前言 运筹学（Operations Research）是用数学方法研究各种系统的最优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。 运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存储论，决策论和对策论等，其中数学规划又包括线性规划，整数规划，非线性规划，目标规划和动态规划等; 虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。 前言 概括：１，运筹学的研究对象是各种系统；２，运筹学的研究目的是实现系统的最优化，求得合理利用各种资源的最优方案；３，运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解；４，运筹学的研究动机是为决策者提供科学决策的依据。 运筹学在工业，农业，商业，物流，经济计划，人力资源，军事等行业都有着非常广泛的应用。有人曾对世界上500家著名的企业集团或跨国公司进行过调查，发现其中95%曾使用过线性规划，75%使用过运输模型，90%使用过网络计划技术，90%使用过存储模型，43%使用过动态规划。 可见运筹学一门应用性很强的学科。特别是随着计算机技术的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显示出其广泛的使用价值。 前言 运筹学这一名词最早出现于1938年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如１，防空雷达的布置问题：英美等国为了对付德国的空袭配备了先进的雷达作为防空系统的一部分，但是由于雷达系统的布置不甚合理，通过防空演习发现实际效果并不理想，２，护航舰队的编队问题：英美等国需要对本国的商船队配备护航舰队，以防止德国潜艇的攻击，这里有一个如何合理编队才能使商船队一旦遭受德国潜艇攻击时损失最少的问题。 为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为“Operational Research”，其他英语国家称为“Operations Research”，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。 前言 二次大战以后，在军事运筹小组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。1947年美国数学家G.B.Dantzig在研究美国空军资源配置时,提出了求解线性规划的有效方法—单纯形法。二十世纪五十年代初，应用计算机求解线性规划获得成功。 至五十年代末，一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事业。 同时很多国家成立了运筹学研究学会，一些大学的相关专业也陆续设置了运筹学的有关课程。专门发表运筹学研究论文的刊物开始出版，运筹学的理论研究日趋成熟，在实际应用上则日趋广泛。 前言 我国运筹学的研究始于五十年代中期，当时由钱学森教授将运筹学从西方国家引入我国，以华罗庚教授为首的一大批科学家在有关企事业单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我国年轻的数学家管梅谷于1962年首先提出的，在国际上统称为中国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。 如今对运筹学的研究大致在三个领域发展：运筹学应用，运筹科学和运筹数学。一般的共识是，运筹学的研究不能忘记其原有的应用性强的特色，必须强调多学科的交叉联系和解决实际问题的研究。我们面临的很多系统通常涉及到大量的经济，技术，社会，政治和心理等综合因素，这些综合因素受到人的影响和干预，存在非结构性的复杂问题，仅用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步，实践将对运筹学提出更新更多的研究课题，运筹学正处于不断发展，不断进步的时期。