《运筹学-第一二章--引言+线性规划PPT课件》由会员分享，可在线阅读，更多相关《运筹学-第一二章--引言+线性规划PPT课件（74页珍藏版）》请在金锄头文库上搜索。
1、运筹学,任课教师： 邮 箱： 手 机：,1,1 引言,1.1“运筹”的含义 最早出自史记高祖本纪：“夫运筹帷幄之中，决胜千里之外，吾不如子房。” 现代含义：运筹是对资源进行统筹安排，决策者进行决策提供最优解决方案，以达到最有效的管理。 古代典故：齐王赛马，丁谓修皇宫，沈括运粮。,2,1 引言,1.2 运筹学的由来与发展 起源于20世纪30年代二战时期，当时由数学、军事领域技术人员组成的小组，有效的解决了雷达布局、反潜深水炸弹爆炸深度、大小船只逃避轰炸等军事问题。 20世纪40-50年代，战争期间研究数据逐渐公开。 1951年P.M. Morse和G. E. Kimball书写的运筹学方法著作问
2、世。,3,1 引言,1.2 运筹学的由来与发展 20世纪50年代开始，各国陆续成立运筹学会，英国1948、美国1952、法国1956、中国1980。 英国 Operational Research，美国Operations Research，简称OR，是当前管理科学领域的主要基础理论课程。,4,1 引言,1.2 运筹学的由来与发展 运筹学在中国的发展 1956年钱学森和许国志在中国科学院力学所成立第1个运筹学小组； 1959年大跃进时期在中国科学院数学所成立第2个运筹学研究部门； 1960年两个部门合并； 1963年在中国科学技术大学开设运筹学课程； 1965年开始，“华罗庚小分队”走遍20多
3、个省，使“优选法”“统筹法”广为流传 ；（打麦场选址、中国邮递员问题） 1980年成立运筹学学会（系统工程学会、管理科学学会）。,5,1 引言,1.3 运筹学的应用 目前运筹学以被广泛的应用到：生产计划、库存管理、运输问题、财政和会计、工程优化与设计等众多领域。 运筹学研究领域重要奖项： INFORMS Franz Edelman奖，1972年开始每年选择一个运筹学领域的杰出应用成果授奖。https:/www.informs.org/Recognize-Excellence/Franz-Edelman-Award获奖华人：于刚2002年。 INFORMS John von Neumann Th
4、eory Prize 自1975年每年1-2人 https:/www.informs.org/Recognize-Excellence/INFORMS-Prizes-Awards/John-von-Neumann-Theory-Prize获奖华人：叶荫宇2009年,6,本章小结,运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。 运筹学其他定义：主要研究人类对各种资源的运用及筹划活动，以期通过了解和发展这种运用及筹划活动的基本规律，发挥有限资源的最大效益，达到总体最优的目标。 当前运筹学已成为管理类、工业工程类等专业的重要基础课程。,7,2 线性规划
5、和单纯性法,2.1 模型的构建 （1）生产计划问题 例题1：某工厂在计划期内要安排生产I，II两种产品，已知生产单位产品所需要的设备台时和A、B两种原材料的消耗，如表所示。 该工厂每生产一件产品I可获利2元， II可获利3元，问如何安排生产计划使该工厂获利最多？,8,2 线性规划和单纯性法,2.1 模型的构建 建模的思路：a 设立决策变量；b 构建目标函数；c构建约束条件。 本问题模型： 决策变量： 表示生产产品I的数量； 表示生产产品II的数量； 目标函数： 约束条件：,约束条件Part1：条件约束,约束条件Part2：非负约束,目标函数z的优化方向，Max表示越大越好，反之Min，全称Ma
6、ximize，Minimize。,9,2 线性规划和单纯性法,2.1 模型的构建 污水处理问题 例题2：已知工厂1和工厂2同属某企业集团，且工厂1和2日排污水量分别为2万立方米和1.4万立方米，环保要求污水含量不超过0.2%，工厂1的污水流至工厂2可以自然净化20%，工厂1和2处理污水成本分别为1000元/万立方米和800元/万立方米，请问工厂1和2应各处理多少污水，使总成本最低。,10,2 线性规划和单纯性法,2.1 模型的构建 决策变量： 表示工厂1处理污水量； 表示工厂2处理污水量； 目标函数： 约束条件： 条件1工厂1处理污水后水质达标： 条件2工厂2处理污水后水质达标： 条件3决策变
7、量 和 应该满足的条件？,11,2 线性规划和单纯性法,2.1 模型的构建 整理后模型：,12,2 线性规划和单纯性法,2.1 模型的构建 租车问题 例题3：山东科技大学(青岛)在2015年招生8000余人，根据预先反馈信息在2015年9月19日有4800人(包括家长和接站人员)会到达青岛火车站。学校为了做好迎新工作，打算租用某公司车辆为新生接站，已知租车公司有小客车70辆，大客车40辆可供学校租用；且小客车可载16人(不包含司机)，大客车可载32人；小客车每天往返5次，大客车每天往返3次；小客车每天租金1200元，大客车每天租金1400元；请问山东科技大学应该租用大小客车各多少辆？,13,2
8、 线性规划和单纯性法,2.1 模型的构建 租车问题模型：,14,2 线性规划和单纯性法,2.1 模型的构建 下料问题 例题4：设原材料7.4m长1根，现需要1.5m、2.1m、2.9m各100根，求需要的原材料根数。,15,2 线性规划和单纯性法,2.1 模型的构建 下料问题模型： 最优方案：z=90根。其中，x2=50，x4=10，x7=30，其他决策变量均为0。,16,2 线性规划和单纯性法,2.1 模型的构建 项目连续投资问题 例题5：某部门在今后五年内考虑给下列项目投资，已知： 设当前有资金10万，请问如何投资这些项目，使到第5年年末拥有的资金最大？,17,2 线性规划和单纯性法,2.
9、1 模型的构建 设决策变量。,投资表,收益表,18,2 线性规划和单纯性法,2.1 模型的构建 连续投资问题模型：,19,2 线性规划和单纯性法,2.2 图解法 （1）适用条件：模型中仅有2个决策变量的简单模型 如例题1：模型,20,2 线性规划和单纯性法,2.2 图解法 （2）图解法步骤 第一步：建立以x1为横坐标轴的直角坐标系，x2为纵坐标轴； 第二步：根据约束条件，在坐标系中确定可行解的集合，即可行域； 第三步：根据目标函数，在可行域中找到最优解。 概念：解（方案）可分为 （1）可行解（可行方案）；（2）不可行解（不可行方案）。 满足所有约束条件的解为可行解，否则为不可行解。 最优解：可
10、行解中能够使目标函数取得最大（或最小）值的解。,21,2 线性规划和单纯性法,2.2 图解法 （2）图解法基础知识 直线方程，y=kx+b，其中k为斜率，b为截距； 线性不等式在直角坐标系中代表的几何含义，如y-x+1代表什么几何含义？,x,y,1,1,先画出边界直线y=-x+1,再根据特殊点（不在边界直线上）法，确定线性不等式代表的半个平面,22,2 线性规划和单纯性法,2.2 图解法 （3）例题1实例求解 步骤一：建立直角坐标系； 步骤二：确定可行域； 步骤三：根据目标函数确定最优解。,x1+2x2=8,4x2=12,4x1=16,23,2 线性规划和单纯性法,2.2 图解法 （4）图解法
11、注意问题 横坐标轴为x1，纵坐标轴x2； 准确判断不等式约束条件代表的半平面区域，确定可行域； 区分目标函数直线束与约束条件边界直线的陡峭程度。 如：斜率为1和2的直线，后者更陡峭；那么斜率为-1和-2的呢？ 注：斜率为同符号的，绝对值越大越陡峭。,24,2 线性规划和单纯性法,2.2 图解法 （5）图解法的其他3种情况 情况1：将例题1的模型修改如下： 这种情况属于无穷多最优解,线段上所有的点均为最优解。,25,2 线性规划和单纯性法,2.2 图解法 （5）图解法的其他3种情况 情况2：图解法求如下模型： 这种情况属于无界解,继续移动，目标函数可以无限制增大。,26,2 线性规划和单纯性法,
12、2.2 图解法 （5）图解法的其他3种情况 情况3：图解法求如下模型： 这种情况属于无可行解,没有可行域。,27,2 线性规划和单纯性法,2.2 图解法 （6）练习题 污水处理问题模型； P55页，2.1题（1）-（4）,28,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （1）标准模型,特点1：目标函数最大化,特点2：约束条件均为等式,特点3：等式右边常数均0,特点4：所有决策变量均0,29,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （2）标准模型的矩阵形式,价值向量,决策变量向量,资源向量,系数矩阵 mn,30,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （2
13、）标准模型的矩阵形式,31,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （3）非标准型模型的标准化 练习P55-2.2（1）,32,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 可行解满足所有约束条件(包括非负约束)的解 基是标准模型系数矩阵A中，选择m列构成的m阶非奇异方阵，用B表示。 如模型：,33,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 由于B是非奇异矩阵，所以是一个基。,34,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 基变量、非基变量 基中系数列向量，对
14、应的变量为基变量，其他的为非基变量。 因此，一个基对应一种基变量和非基变量的划分方式，以上基显然，x3、x4、x5为基变量，x1，x2为非基变量。,35,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 基解、基可行解、基不可行解、可行基 一个基会唯一对应一个基解； 求本基对应的基解方式，在标准模型等式约束中，令非基变量x1，x2为0，解方程组求出所有的基变量x3、x4、x5。,36,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 令非基变量x1，x2为0，解方程组求出所有的基变量x3、x4、x5。 得到B对应的一个基解 由
15、于X中所有的变量值，也满足模型中的非负约束，因此为基可行解（此时可知B为可行基），否则为基不可行解。,37,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 一个mn的系数矩阵A，至多有多少个基？ 可行解、非可行解，基可行解，基不可行解的关系。 练习题P55-2.3（1）（2）,基可行解,基不可行解,可行解,不可行解,38,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 凸集 凸集的定义：如果在一个区域中（n维）的任意两个不同点之间的连线也同属于该区域，那么该集合为凸集。 证明一个区域是凸集的方法，任取两个不同点，证明连线上
16、的点均属于该区域。,39,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 线性规划模型的可行域为凸集； 凸集的“角”：一个点如果找不到两个不同的点，连一条线，使该点在连线上（不含连线端点），那么该点为角。 基可行解与可行域凸集的角一一对应。 如果一个线性规划问题有最优解，那么一定可以在基可行解中找到最优解。,40,2 线性规划和单纯性法,2.4 单纯形法 （1）单纯形方法 由于线性规划问题的最优解一定可以在基可行解中找到，那么穷举所有的基可行解一定可以找到最优解。 但是遗憾的是当n和m足够大时 会非常大。,41,2 线性规划和单纯性法,2.4 单纯形法 （2）单纯形方法本质 由美国著名运筹学家George Bernard Dantzig在1947年提出。 单纯形方法本质：由任何一个基可行解开始，根据单纯形法规则可以找到下一个更优的基可行解，再不断重复单纯形法规则，直到找到最优的基可行解，即问题的最优解。 单纯形法在线性规
