运筹学电子教案（1）

1非常荣幸第二次来到仪征化纤股份公司上课谨祝同志们：身体健康万事如意2欢迎同学们进入运筹学课程的学习！教学相长合作愉快3情况介绍•本课程设置的有关问题•教学要求4第一讲绪论•本讲的主要内容：•一、运筹学的发展与展望•二、运筹学的学科体系•三、运筹学的定义与研究特点•四、运筹学在管理科学中的地位•五、运筹学在经济管理中应用的主要课题5一、运筹学的发展及展望•1、运筹学的产生与发展•科学意义上的运筹学公认为产生于第二次世界大战期间。以英国为代表的科学家做了奠基性的工作。•四十年代之后，运筹学取得全面的发展。表现在：1）数学理论得到加强，2）分支学科大量涌现，3）应用领域不断拓宽等。6一、运筹学的发展与展望•2、运筹学的展望•1）运筹学发展过程中面临的一些问题：抽象化风气日盛、大范围问题、高维问题、体系厐杂等。•2）运筹学发展展望•运筹学应该在三个方面都应有所发展：运筹学的学科体系、运筹学的应用及运筹学的数学理论。7二、运筹学的学科体系•运筹学发展到今天已经形成了一个庞大的学科体系：•1、Mathematicalprogramming:Linearprogramming,Nonlinearprogramming,Integerprogramming,Objectiveprogramming,Dynamicprogramming,Stochasticprogramming,Geometricprogramming等。8二、运筹学的学科体系•2、Graphtheory•3、Networkanalysis•4、Queueingtheory•5、Gametheory•6、Decisiontheory•7、Qualitycontrol•8、Reliabilitytheory9二、运筹学的学科体系•9、Storagetheory•10、Searchtheory•11、Maintenancetheory•12、Computersimulation•13、Schedulingmethod•14、Valuetheory•15、Renewaltheory•16、Controltheory•17、Militaryoperationsresearch等。10三、运筹学的定义与研究特点•1、运筹学认识上的一些分歧•1）学科的归属问题：数学学科、边缘学科、管理科学。•2）方法特征：优化技术、决策方法、一般的数量分析方法。•3）与相关学科的关系：控制论、系统论、技术经济方法、管理科学等。•4）研究的侧重点方面：理论方法、侧重于应用等。11三、运筹学的定义与研究特点•2、运筹学的定义•美国人的定义：运筹学是研究用科学的方法来解决在资源不充分的情况下如何最好地设计人-机系统，并使之最好地运行的一门学科。•英国人的定义：运筹学是运用科学方法（特别是数学方法）来解决那些在工业、商业等大型系统的指挥和管理方面出现的问题，目的是帮助管理者科学地决定其策略和行动。12三、运筹学的定义与研究特点•3、运筹学研究问题的特征：•1）科学性•2）实践性•3）系统性•4）综合性13四、运筹学在管理科学中的地位•管理科学的学科构架•1、基础理论部分•1）管理理论：企业理论、决策理论、运筹学、组织理论、行为理论、企业经营学、生产管理与运作理论、人-机工程等。•2）管理发展史：管理思想史、管理方法史、管理科学发展史、比较管理学等。•3）交叉知识：数学、系统论、哲学、经济学、人类学、心理学、社会学、计算机科学、思维科学等。14四、运筹学在管理科学中的地位•管理科学的学科构架•1、基础理论部分•4）管理学派：经营学派、决策学派、“管理科学”学派、经验学派、经理角色学派、群体行为学派、合作社会系统学派、权变学派等。15四、运筹学在管理科学中的地位•管理科学的学科构架•2、技术方法部分：决策方法、决策支持系统、计划与规划技术、库存控制、技术经济、预测技术、管理信息系统、管理系统工程、目标管理、质量管理与保证、管理数学方法、项目评估和可行性研究、价值工程、预算与成本控制、时间-动作研究等。16四、运筹学在管理科学中的地位•3、应用研究部分•1）宏观管理领域：国民经济管理、社会发展管理、管理体制研究等。•2）部门管理领域：行政管理、人事管理、工业管理、农业管理、财政管理等。•3）企业管理领域：设备管理、物资管理、质量管理、财务管理、人力资源管理、生产管理、计划管理、市场营销管理、技术开发管理等。•4）专项管理活动：环境管理、能源利用与开发等。17五、运筹学在经济管理中应用的主要课题•1、市场营销：广告预算、竞争性定价、新产品开发、销售方案等。•2、生产计划：生产作业计划、配料、物料管理等。•3、库存管理：合适的库存水平、进货方案等。•4、运输管理：运输方式的组合、运输计划等。18五、运筹学在经济管理中运用的主要课题•5、财务管理：预算、筹资、成本分析等。•6、人事管理：人员需求、人力资源开发、人员的合理利用、人才评价、工资标准等。•7、设备维修与更新8、可靠性分析•9、质量控制10、项目评估•11、城市公用事业和服务19参考书目1、管理科学(ManagementScience)（当代最有代表性的杂志之一）2、管理科学基础（美国希利尔等人编写的，中国财政经济出版社）3、管理科学事务教程（加拿大敖特斯编写的，华夏出版社）20第二讲线性规划与单纯形方法本讲的主要内容：一、线性规划模型及标准化二、二维线性规划的图解法三、线性规划的基本理论四、单纯形方法五、DSS、LINDO软件介绍21第一节情况介绍•一、线性规划的地位与研究进程•作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。•线性规划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。22二、线性规划研究的内容•1、在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求极大化问题）。•2、在给定目标下，如何以最少的资源消耗，实现这个目标（求极小化问题）。23第二节线性规划模型•一、线性规划模型的一般形式•根据实际问题的要求，可建立线性规划问题数学模型。线性规划问题的数学模型，由目标函数和约束条件两部分组成。下面我们举例说明线性规划问题的数学模型。•例一：生产计划问题•某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：•24例一、生产计划问题试用线性规划方法制订使利润最大的生产计划。产品甲产品乙产品丁产品丙设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.1825例一的数学模型解：设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：Maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.0x1+3.0x2+3.5x3+1.0x4≤5000x1，x2，x3，x4≥026例二：配料问题•某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：27例二：配料问题T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.3011597827628例二：配料问题•假设熔炼时重量没有损耗，要熔炼成100千克不锈钢G，应选用各种原料各多少才能使成本达到最小。•解：设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4千克，根据条件，可建立相应的线性规划模型如下：29例二的数学模型MinZ=115x1+97x2+82x3+76x4s.t.0.0321x1+0.0453x2+0.0219x3+0.0176x4≥3.200.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.100.0204x1+0.0112x2+0.0357x3+0.0433x4≥4.30x1+x2+x3+x4=100x1,x2,x3,x4≥030线性规划模型的一般形式：•通过上面的例子，可以写出线性规划模型的一般形式：Max(Min)z=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≥(=、≤)b1a21x1+a22x2+……+a2nxn≥(=、≤)b2……am1x1+am2x2+……+amnxn≥(=、≤)bmx1,x2,……,xn≥(≤)0，或者没有限制31二、线性规划的标准化方法•1、标准化形式Maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn=b1a21x1+a22x2+……+a2nxn=b2……am1x1+am2x2+……+amnxn=bmx1,x2,……,xn≥0322、线性规划的标准化方法•2、标准化方法（1）把最小化目标函数转化为求最大化问题。（2）把约束方程中的不等式转化为等式。具体做法是：对于不大于情况的，引进松弛变量，对于不小于情况的，引进剩余变量。（3）将变量中的非正限制或无限制转化为非负限制。其中，对于无限制变量的处理：一是同时引进两个非负变量，然后用它们的差代替无限制变量，二是从约束方程中任取一个包含无限制变量的等式约束，解出该变量，并把它代如目标函数和其他约束方程中去，以消除该无限制变量。33三、定理•定理：线性规划模型的一般形式与它的标准形是等价的。根据这一定理，由标准形求出的最优解，也一定是原问题的最优解。34四、线性规划的向量和矩阵表示•1、用“∑”表示•2、用向量表示•3、用向量和矩阵表示35第二节二维线性规划的图解法•一、图解法的含义在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。•二、图解法举例教材第9页例1.136二、图解法举例•作图37三、几个概念•1、法向量正法向量和负法向量。由目标函数系数组成的与等值线垂直的向量，称为正法向量。正法向量的反号称为负法向量。•2、等值线使目标函数取相等值的所有点的集合，称为目标函数的等值线。38三、几个概念•3、可行解由约束条件和变量取值限制围成的公共区域中的每一个点都称为线性规划问题的可行解。•4、可行域所有可行解的集合，构成线性规划问题的可行域。39四、二维线性规划解的形式•1、唯一解•2、无穷多个最优解Min–x1-2x2s.t.-x1+x2≤2x1+2x2≤103x1+x2≤15x1,x2≥040四、二维线性规划解的形式•3、有可行解但无最优解Min–x1-2x2s.t.-x1+x2≤2-x1+2x2≤6x1,x2≥0•4、无可行解也即问题无解Minx1+2x2s.t.x1+x2≤12x1+x2≥4x1,x2≥041二维线性规划问题解的小节无可行解线性规划问题唯一最优解有可行解无穷最优解无最优解42第四节线性规划的基本理论•一、线性规划解的概念•1、解：满足线性规划主约束条件的点，称为线性规划问题的解。•2、可行解：满足线性规划所有约束条件的点，称为线性规划问题的可行解。•3、最优解：使目标函数得到极值的可行解，称为线性规划问题的最优解。最优解包括：唯一最优解和无穷最优解，有界最优