运筹学 第一二章引言+线性规划PPT课件

1、.,1,运筹学,任课教师： 邮 箱： 手 机：,.,2,1 引言,1.1“运筹”的含义 最早出自史记高祖本纪：“夫运筹帷幄之中，决胜千里之外，吾不如子房。” 现代含义：运筹是对资源进行统筹安排，决策者进行决策提供最优解决方案，以达到最有效的管理。 古代典故：齐王赛马，丁谓修皇宫，沈括运粮。,.,3,1 引言,1.2 运筹学的由来与发展 起源于20世纪30年代二战时期，当时由数学、军事领域技术人员组成的小组，有效的解决了雷达布局、反潜深水炸弹爆炸深度、大小船只逃避轰炸等军事问题。 20世纪40-50年代，战争期间研究数据逐渐公开。 1951年P.M. Morse和G. E. Kimball书写的

2、运筹学方法著作问世。,.,4,1 引言,1.2 运筹学的由来与发展 20世纪50年代开始，各国陆续成立运筹学会，英国1948、美国1952、法国1956、中国1980。 英国 Operational Research，美国Operations Research，简称OR，是当前管理科学领域的主要基础理论课程。,.,5,1 引言,1.2 运筹学的由来与发展 运筹学在中国的发展 1956年钱学森和许国志在中国科学院力学所成立第1个运筹学小组； 1959年大跃进时期在中国科学院数学所成立第2个运筹学研究部门； 1960年两个部门合并； 1963年在中国科学技术大学开设运筹学课程； 1965年开始，“

3、华罗庚小分队”走遍20多个省，使“优选法”“统筹法”广为流传 ；（打麦场选址、中国邮递员问题） 1980年成立运筹学学会（系统工程学会、管理科学学会）。,.,6,1 引言,1.3 运筹学的应用 目前运筹学以被广泛的应用到：生产计划、库存管理、运输问题、财政和会计、工程优化与设计等众多领域。 运筹学研究领域重要奖项： INFORMS Franz Edelman奖，1972年开始每年选择一个运筹学领域的杰出应用成果授奖。/Recognize-Excellence/Franz-Edelman-Award获奖华人：于刚2002年。 INFORMS John

4、von Neumann Theory Prize 自1975年每年1-2人 /Recognize-Excellence/INFORMS-Prizes-Awards/John-von-Neumann-Theory-Prize获奖华人：叶荫宇2009年,.,7,本章小结,运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。 运筹学其他定义：主要研究人类对各种资源的运用及筹划活动，以期通过了解和发展这种运用及筹划活动的基本规律，发挥有限资源的最大效益，达到总体最优的目标。 当前运筹学已成为管理类、工业工程类等专业的

5、重要基础课程。,.,8,2 线性规划和单纯性法,2.1 模型的构建 （1）生产计划问题 例题1：某工厂在计划期内要安排生产I，II两种产品，已知生产单位产品所需要的设备台时和A、B两种原材料的消耗，如表所示。 该工厂每生产一件产品I可获利2元， II可获利3元，问如何安排生产计划使该工厂获利最多？,.,9,2 线性规划和单纯性法,2.1 模型的构建 建模的思路：a 设立决策变量；b 构建目标函数；c构建约束条件。 本问题模型： 决策变量： 表示生产产品I的数量； 表示生产产品II的数量； 目标函数： 约束条件：,约束条件Part1：条件约束,约束条件Part2：非负约束,目标函数z的优化方向，

6、Max表示越大越好，反之Min，全称Maximize，Minimize。,.,10,2 线性规划和单纯性法,2.1 模型的构建 污水处理问题 例题2：已知工厂1和工厂2同属某企业集团，且工厂1和2日排污水量分别为2万立方米和1.4万立方米，环保要求污水含量不超过0.2%，工厂1的污水流至工厂2可以自然净化20%，工厂1和2处理污水成本分别为1000元/万立方米和800元/万立方米，请问工厂1和2应各处理多少污水，使总成本最低。,.,11,2 线性规划和单纯性法,2.1 模型的构建 决策变量： 表示工厂1处理污水量； 表示工厂2处理污水量； 目标函数： 约束条件： 条件1工厂1处理污水后水质达标

7、： 条件2工厂2处理污水后水质达标： 条件3决策变量 和 应该满足的条件？,.,12,2 线性规划和单纯性法,2.1 模型的构建 整理后模型：,.,13,2 线性规划和单纯性法,2.1 模型的构建 租车问题 例题3：山东科技大学(青岛)在2015年招生8000余人，根据预先反馈信息在2015年9月19日有4800人(包括家长和接站人员)会到达青岛火车站。学校为了做好迎新工作，打算租用某公司车辆为新生接站，已知租车公司有小客车70辆，大客车40辆可供学校租用；且小客车可载16人(不包含司机)，大客车可载32人；小客车每天往返5次，大客车每天往返3次；小客车每天租金1200元，大客车每天租金140

8、0元；请问山东科技大学应该租用大小客车各多少辆？,.,14,2 线性规划和单纯性法,2.1 模型的构建 租车问题模型：,.,15,2 线性规划和单纯性法,2.1 模型的构建 下料问题 例题4：设原材料7.4m长1根，现需要1.5m、2.1m、2.9m各100根，求需要的原材料根数。,.,16,2 线性规划和单纯性法,2.1 模型的构建 下料问题模型： 最优方案：z=90根。其中，x2=50，x4=10，x7=30，其他决策变量均为0。,.,17,2 线性规划和单纯性法,2.1 模型的构建 项目连续投资问题 例题5：某部门在今后五年内考虑给下列项目投资，已知： 设当前有资金10万，请问如何投资这

9、些项目，使到第5年年末拥有的资金最大？,.,18,2 线性规划和单纯性法,2.1 模型的构建 设决策变量。,投资表,收益表,.,19,2 线性规划和单纯性法,2.1 模型的构建 连续投资问题模型：,.,20,2 线性规划和单纯性法,2.2 图解法 （1）适用条件：模型中仅有2个决策变量的简单模型 如例题1：模型,.,21,2 线性规划和单纯性法,2.2 图解法 （2）图解法步骤 第一步：建立以x1为横坐标轴的直角坐标系，x2为纵坐标轴； 第二步：根据约束条件，在坐标系中确定可行解的集合，即可行域； 第三步：根据目标函数，在可行域中找到最优解。 概念：解（方案）可分为 （1）可行解（可行方案）；

10、（2）不可行解（不可行方案）。 满足所有约束条件的解为可行解，否则为不可行解。 最优解：可行解中能够使目标函数取得最大（或最小）值的解。,.,22,2 线性规划和单纯性法,2.2 图解法 （2）图解法基础知识 直线方程，y=kx+b，其中k为斜率，b为截距； 线性不等式在直角坐标系中代表的几何含义，如y-x+1代表什么几何含义？,x,y,1,1,先画出边界直线y=-x+1,再根据特殊点（不在边界直线上）法，确定线性不等式代表的半个平面,.,23,2 线性规划和单纯性法,2.2 图解法 （3）例题1实例求解 步骤一：建立直角坐标系； 步骤二：确定可行域； 步骤三：根据目标函数确定最优解。,x1+

11、2x2=8,4x2=12,4x1=16,.,24,2 线性规划和单纯性法,2.2 图解法 （4）图解法注意问题 横坐标轴为x1，纵坐标轴x2； 准确判断不等式约束条件代表的半平面区域，确定可行域； 区分目标函数直线束与约束条件边界直线的陡峭程度。 如：斜率为1和2的直线，后者更陡峭；那么斜率为-1和-2的呢？ 注：斜率为同符号的，绝对值越大越陡峭。,.,25,2 线性规划和单纯性法,2.2 图解法 （5）图解法的其他3种情况 情况1：将例题1的模型修改如下： 这种情况属于无穷多最优解,线段上所有的点均为最优解。,.,26,2 线性规划和单纯性法,2.2 图解法 （5）图解法的其他3种情况 情况

12、2：图解法求如下模型： 这种情况属于无界解,继续移动，目标函数可以无限制增大。,.,27,2 线性规划和单纯性法,2.2 图解法 （5）图解法的其他3种情况 情况3：图解法求如下模型： 这种情况属于无可行解,没有可行域。,.,28,2 线性规划和单纯性法,2.2 图解法 （6）练习题 污水处理问题模型； P55页，2.1题（1）-（4）,.,29,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （1）标准模型,特点1：目标函数最大化,特点2：约束条件均为等式,特点3：等式右边常数均0,特点4：所有决策变量均0,.,30,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （2）标准模型

13、的矩阵形式,价值向量,决策变量向量,资源向量,系数矩阵 mn,.,31,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （2）标准模型的矩阵形式,.,32,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （3）非标准型模型的标准化 练习P55-2.2（1）,.,33,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 可行解满足所有约束条件(包括非负约束)的解 基是标准模型系数矩阵A中，选择m列构成的m阶非奇异方阵，用B表示。 如模型：,.,34,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 由于B是非奇异矩阵，

14、所以是一个基。,.,35,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 基变量、非基变量 基中系数列向量，对应的变量为基变量，其他的为非基变量。 因此，一个基对应一种基变量和非基变量的划分方式，以上基显然，x3、x4、x5为基变量，x1，x2为非基变量。,.,36,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 基解、基可行解、基不可行解、可行基 一个基会唯一对应一个基解； 求本基对应的基解方式，在标准模型等式约束中，令非基变量x1，x2为0，解方程组求出所有的基变量x3、x4、x5。,.,37,2 线性规划和单纯性法,

15、2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 令非基变量x1，x2为0，解方程组求出所有的基变量x3、x4、x5。 得到B对应的一个基解 由于X中所有的变量值，也满足模型中的非负约束，因此为基可行解（此时可知B为可行基），否则为基不可行解。,.,38,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 一个mn的系数矩阵A，至多有多少个基？ 可行解、非可行解，基可行解，基不可行解的关系。 练习题P55-2.3（1）（2）,基可行解,基不可行解,可行解,不可行解,.,39,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关

16、概念 凸集 凸集的定义：如果在一个区域中（n维）的任意两个不同点之间的连线也同属于该区域，那么该集合为凸集。 证明一个区域是凸集的方法，任取两个不同点，证明连线上的点均属于该区域。,.,40,2 线性规划和单纯性法,2.3 线性规划问题的标准型 （4）相性规划问题的相关概念 线性规划模型的可行域为凸集； 凸集的“角”：一个点如果找不到两个不同的点，连一条线，使该点在连线上（不含连线端点），那么该点为角。 基可行解与可行域凸集的角一一对应。 如果一个线性规划问题有最优解，那么一定可以在基可行解中找到最优解。,.,41,2 线性规划和单纯性法,2.4 单纯形法 （1）单纯形方法 由于线性规划问题的

17、最优解一定可以在基可行解中找到，那么穷举所有的基可行解一定可以找到最优解。 但是遗憾的是当n和m足够大时 会非常大。,.,42,2 线性规划和单纯性法,2.4 单纯形法 （2）单纯形方法本质 由美国著名运筹学家George Bernard Dantzig在1947年提出。 单纯形方法本质：由任何一个基可行解开始，根据单纯形法规则可以找到下一个更优的基可行解，再不断重复单纯形法规则，直到找到最优的基可行解，即问题的最优解。 单纯形法在线性规划领域的出现，就好比帮助一群迷路的登山者，找到了一条通往山顶的阶梯（可以保证每一步后都更接近目标）。,.,43,2 线性规划和单纯性法,2.4 单纯形法 （3

18、）单纯形方法 适用于求解任何线性规划问题标准模型。,.,44,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤一：找到标准模型中的初始基可行解。 如果标准模型系数矩阵中包括1个m阶单位矩阵，那么可以找到一个显见的基可行解。 因此显见的基可行解为,.,45,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 本步骤的内容是对等式约束条件和目标函数变形，即用非基变量和常数表示基变量和目标z。本例变形：,选择系数为正数，且最大的非基变量。,.,46,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：

19、基于当前的基可行解 ，找到下一个更优的基可行解 。 重新用当前非基变量和常数表示基变量和目标z。,.,47,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 重新用当前非基变量和常数表示基变量和目标z。,.,48,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 重新用当前非基变量和常数表示基变量和目标z。,找不到系数大于0的非基变量，说明？,.,49,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤三：如果所有非基变量在目标函数中的系数小

20、于等于0，说明找到最优解。,.,50,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 将上述标准模型，修改。,.,51,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤一：找到标准模型中的初始基可行解。 如果标准模型系数矩阵中包括1个m阶单位矩阵，那么可以找到一个显见的基可行解。 因此显见的基可行解为,.,52,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 本步骤的内容是对等式约束条件和目标函数变形，即用非基变量和常数表示基变量和目标z。本例变形：,选择系数为正数，且最大的非基变量。,.,53

21、,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 重新用当前非基变量和常数表示基变量和目标z。,.,54,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 重新用当前非基变量和常数表示基变量和目标z。,.,55,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤二：基于当前的基可行解 ，找到下一个更优的基可行解 。 重新用当前非基变量和常数表示基变量和目标z。,.,56,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 步骤三：如

22、果所有非基变量在目标函数中的系数小于等于0，说明找到最优解，如果还存在非基变量检验数等于0，说明有无穷个解。 为什么求得两个不同基可行解，就可以确定得到无穷个最优解？ 证明： 引理：如果可行域中线段端点使目标函数值相等，那么线段上的点目标函数值与端点相同。,.,57,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 用单纯形法求解以下模型。,.,58,2 线性规划和单纯性法,2.4 单纯形法 （3）单纯形方法 此模型为无界解。,说明x1可以无限制增加，x3和x4也不会取负数。,.,59,2 线性规划和单纯性法,2.4 单纯形法 （4）单纯形表形式-唯一解 单纯形表格式,.,60,2

23、线性规划和单纯性法,2.4 单纯形法 （4）单纯形表形式-唯一解 单纯形表格式,目标Max：非基变量检验数，均小于0。,.,61,2 线性规划和单纯性法,2.4 单纯形法,.,62,2 线性规划和单纯性法,2.4 单纯形法 （5）单纯形表-无穷多最优解,目标Max：非基变量检验数，均小于等于0，且至少有一个非基变量的检验数等于0。,.,63,2 线性规划和单纯性法,2.4 单纯形法,.,64,2 线性规划和单纯性法,2.4 单纯形法,.,65,2 线性规划和单纯性法,2.4 单纯形法 （5）无穷最优解判断,.,66,2 线性规划和单纯性法,2.4 单纯形法 （5）无穷最优解判断,x1,x2,3,2,1,1,2,3,4,4,(2,3),射线上的点均为最优解,.,67,2 线性规划和单纯性法,2.4 单纯形法 （6）单纯形表-无界解,目标Max：存在某非基变量检验数大于