[工学]01-1线性规划建模-1h.ppt

运筹学Operational Research 运筹帷幄，决胜千里 ?史记《张良传》 第一章 线性规划建模及单纯形法 linear Programming Simplex Method 知识点要求 理解线性规划的含义，能根据实际问题列出线性规划的数学模型； 理解线性规划的一般形式与标准形式，能将一般形式化为标准形式； 掌握线性规划图解法及其几何意义； 理解可行解、最优解及标准形式下的基、基解、基可行解等概念； 掌握单纯性法基本原理，了解并掌握运用单纯性表计算线性规划的步骤及解法。 引言（1） 线性规划—— 运筹学中应用最广泛的方法之一； 运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础； 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。 引言（2） 从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作， 其中比较著名的还有西蒙Simon，萨缪尔逊Samullson，列昂惕夫Leontief，阿罗Arrow等。 引言（3） 线性规划的研究对象： 在一定的人力、财力、资源条件下，如何合理安排使用，效益最高； 某项任务确定后，如何安排人、财、物，使费用最省。 主要内容 1.1 线性规划问题及其一般数学模型 LP Problem LP Mathematical Model 1.2 线性规划图解法 Graphic Solution of LP 1.3 单纯形法 Simplex Method 1.4 应用举例 Application Cases 1.1 问题的提出 线性规划问题引例（1）——下料问题 如图所示，用一块边长为a的正方形铁皮做一个容器，应如何裁剪，使做成的容器的容积为最大。 解题-1 容积为： 要使容积最大，就是要确定x的值，使V达到最大。 线性规划问题引例（2）——生产计划问题 问：该企业应安排生产两种产品各多少件，使总的利润收入为最大？ 解题2（1） 假定要x1和x2分别表示Ⅰ、Ⅱ两种产品在计划期内的产量。因设备A在计划期内的可用时间为12h，不允许超过，于是有 2x1+2x2≤12。 对设备B、C、D也可列出类似的不等式： x1+2x2 ≤8； 4x1 ≤16； 4x2 ≤12。 企业的目标：是在各种设备能力允许的条件下，使总的利润收入为最大。 解题2（2） 线性规划问题引例（3）——配料问题 解例3 设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量 比较 上述三个例子，从数学角度讲，都是求极值问题，但例1中除变量取值要求非负外无其它更多限制，这类问题可以用微积分中已学过的求极值的古典方法可以解决； 而例2、例3中变量的取值要受一系列条件的限制，求解这类带附加限制条件的极值问题是运筹学中规划论部分研究的内容。 1.2 线性规划问题的数学模型 原型prototype：通常称现实世界中人们关心、研究的实际对象为原型。 模型model：是指将某一部分信息简缩、提练而构造的原型替代物。 数学模型mathematical model：是对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设，并运用适当数学工具得到的一个数学结构。 规划问题的数学模型包含的三个组成要素/特点 决策变量decision variable：指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量； 目标函数objective function：指问题要达到的目的要求，表示为决策变量的函数； 约束条件constraint condition：指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。 线性规划问题的数学模型 在规划问题的数学模型中， 决策变量为可控的连续变量， 目标函数和约束条件都是线性 的模型。 一般线性规划问题的数学模型表现形式 线性规划数学模型的一般表示方式 1、和式 2、向量式 3、矩阵式 1.3 线性规划问题的标准形式 目标函数为求极大值(或求极小值)； 约束条件全为等式； 约束条件右端常数项bi全为非负值； 变量xj的取值为非负； 线性规划数学模型的标准化（1） 1．目标函数为求极小值 令： 标准化为： 线性规划数学模型的标准化（2） 2. 约束条件为不等式 当约束条件为“≤”时，增加松弛变量， 如2x1+2x2≤12，可令2x1+2x2+x3=12(x3≥0) 当约束条件为“≥”时，减去剩余变量， 如3x1+7x2≥18，可令3x1+7x2-x4=18，(x4≥0) 线性规划数学模型的标准化（3） 3