《运筹学OperationsResearchppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学OperationsResearchppt课件.ppt（17页珍藏版）》请在三一文库上搜索。
1、,运筹学 Operations Research,Chapter 1 线性规划 Linear Programming,1.LP的数学模型 Mathematical Model of LP 2.图解法 Graphical Method 3.标准型 Normalized Form of LP 4.基本概念 Basic Concepts 5.单纯形法 Simplex Method 6.人工变量法 Artificial Variable Method 7.计算公式 Calculate Formula 8.附录：软件求解操作及LP常用词汇,2019年5月11日星期六,2019年5月11日星期六,线性规划
2、（Linear Programming缩写为LP）是运筹学的重要分支之一。 自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理
3、科学的重要基础和手段之一。,2019年5月11日星期六,线性规划主要解决两个方面的问题： （1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？ （2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？,2019年5月11日星期六,【例1.1】某企业计划生产甲、乙、丙三种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如表1-1所示 ，已知各设备在计划期内的能力分别为20、15、16、12小时；每生产一件甲、乙、丙三种产品，企业可获得利润分别为4、3、5元。企业决策者应如何安排生产计划，使企业在计划期内总的
4、利润收入最大？,2019年5月11日星期六,【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型为：,2019年5月11日星期六,线性规划的数学模型由,决策变量 Decision variables 目标函数Objective function 及约束条件Constraints 构成。称为三个要素。,其特征是： 1解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或 最小值； 2解决问题的约束条件是一组多个决策变量 的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,2019年5月11日星期六,200万m3,500万m3,工厂2：,【例1.2】 河流1：每天流量500
5、万m3 ；河流2：每天流量200万m3 ,水质要求：污水含量0.2%,2万m3,1.4万m3,污水从工厂1流向工厂2有20%可以净化 处理污水成本：工厂1 1000元/万m3； 工厂2 800元/万m3 问两个工厂每天各处理多少污水总成本最少？,工厂1：,【解】设x1 、x2分别为工厂1、2每天处理的污水量（万m3），则,2019年5月11日星期六,数学模型为：,2019年5月11日星期六,【例1.3】下料问题，某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9，2.1,1.5（m），这些轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少圆钢来生
6、产这些轴？,【解】第一步：设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如y1=2,y2=0则y3只能为1，余料为0.1。象这样的非负整数解共有8组，也就是有8种下料方式，如表1-2所示。,第二步：建立线性规划数学模型。设xj(j=1,2,8)为第j种下料方案所用圆钢的根数。则数学模型为,2019年5月11日星期六,2.9y1+2.1y2+1.5y37.4 表12,2019年5月11日星期六,最优下料方案为：第一种方案用料10根，第二种方案50根，第四种方案30根，
7、总余料为 16m。,用1.5的单纯形法求得最优解为x1=10,x2=50,x4=30，其余x为零，即第一种方案用料10根，第二种方案用50根，第四种方案用30根，共计用料90根。,如果要求余料最少，则目标函数及约束条件为：,2019年5月11日星期六,注意： 1 .余料不能超过最短毛坯的长度； 2.最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的；不能遗漏了方案。 3.在实际中，如果毛坯规格较多，毛坯的长度又很短的方案可能很多，甚至有几千个方案，这时用人工计算几乎是不可能的，使用计算机来确定下料方式。,2019年5月11日星期六,一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2,n，目标函数的变量系数用cj表示, cj称为价值系数。 约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示, bi称为资源限量。,2019年5月11日星期六,则线性规划数学模型的一般表达式可写成：,2019年5月11日星期六,在实际中一般xj0,但有时xj0或xj无符号限制。,为了书写方便，上式也可写成,2019年5月11日星期六,1.什么是线性规划，掌握线性规划在管理中的几个应用例子 2.线性规划数学模型的组成及其特征 3.线性规划数学模型的一般表达式。,图解法,Exit,返回首页,