[数学]4 线性规划ppt课件

1、第四章第四章 线性规划线性规划线性规划模型的建立线性规划模型的建立线性规划模型的规范形线性规划模型的规范形 线性规划模型的图解法线性规划模型的图解法线性规划模型的单纯形法线性规划模型的单纯形法建立线性规划模型有三个根本步骤：第一步，找出问题中的一切相关的未知变量决策变量，并用代数符号表示它们，根据变量的物理性质研讨变量能否有非负性；第二步，找出问题中的目的，写成变量的线性函数，作为线性规划模型的目的函数；第三步，找出问题中一切的限制或约束，写成变量的线性方程或线性不等式，作为线性规划模型的约束条件。第一节第一节 线性规划模型的建立线性规划模型的建立例题例题5.1 (消费方案问题消费方案问题)

2、某厂方案内将安排消费某厂方案内将安排消费I,II两种产品，两种产品，知消费单位分量的产品所需的设备为知消费单位分量的产品所需的设备为A及及B、C两种原料的耗两种原料的耗费如表费如表1所示：所示：消费单位分量的产品消费单位分量的产品I可获利可获利2万，消费单位分量的产品万，消费单位分量的产品II可可获利获利5万。万。问：如何安排消费可使工厂获得的利润最多？问：如何安排消费可使工厂获得的利润最多？ 例题例题5.2合理下料问题某厂消费合理下料问题某厂消费过程中需求用长度分别为过程中需求用长度分别为31米、米、25米和米和17米的同种棒料毛坯分米的同种棒料毛坯分别为别为200、100和和300根，而如

3、今只需根，而如今只需一种长度为一种长度为9米的原料，问应如何下米的原料，问应如何下料才干使废料最少料才干使废料最少? 解 处理下料问题的关键在于找出一切能够的下料方法(假设不能穷尽一切的方法，也应尽量多搜集各种能够的下料方法)，然后对这些方案进展最正确结合。 对给定的9米长的棒料进展分割，可以有9种切割方法，见表5.2所示。表5.2 毛坯切割方案表例题例题5.3合理配料问题根据对合理配料问题根据对77种食物所含的九种营养物：种食物所含的九种营养物：热量热量(糖与脂肪糖与脂肪)、蛋白质、钙、铁、维生素、蛋白质、钙、铁、维生素A、维生素、维生素BI、维生、维生素素B2、草酸与维生素、草酸与维生素C

4、的成份及食物的市场价风格查，按照医生的成份及食物的市场价风格查，按照医生所提出的对每个人每天所需的营养要求，可得表所提出的对每个人每天所需的营养要求，可得表5.3问怎样采购食物才干在保证营养要求的前提下破费最省？这就是问怎样采购食物才干在保证营养要求的前提下破费最省？这就是营养问题或饮食问题，配料问题就是由此而推行来的。营养问题或饮食问题，配料问题就是由此而推行来的。n第二节第二节 线性规划模型的规范形线性规划模型的规范形一线性规划模型的可行解和最优解一线性规划模型的可行解和最优解 满足目的函数，即使得目的函数到达最大值或最小值的可行解，称为该线性规划模型的最优解。把最优解代入目的函数所得到的

5、目的函数的最大值或最小值称为最优值。 定义5.2 某个线性规划模型的全体可行解组成的集合，称为该线性规划模型的可行解域。二线性规划模型的规范型二线性规划模型的规范型 线性规划模型的规范型为：线性规划模型的规范型为：线性规划模型的规范型还可以记为：规范型具有以下特点： 目的函数是求最大值； 约束条件为线性方程组； 未知变量都有非负限制。线性规划模型的非规范型，在以下三种情况下可化为规范型：目的函数是求最小值约束条件为不等式模型中的某些变量没有非负限制第三节第三节 线性规划模型的图解法线性规划模型的图解法 例题例题5.4 求以下线性规划问题的最优解：求以下线性规划问题的最优解： 1第一步，求可行解

6、域： 可行解域是一切满足约束条件的数组，四个不等式是四个半平面，而可行解域就是这四个半平面的公共部分。其外形为一个凸多边形区域，可行解是凸多边形内的一个点，如图5.1。05051015OCAB可 行 解 域x2x1图5.1 例题5.41的可行解域第二步，求最优解：050510154x1+3x2=74x1+3x2=54x1+3x2=34x1+3x2=1可 行 解 域x2X1图5.2 例题5.41的最优解2线性规划的可行解域普通为凸多边形，而有时那么是无界的凸多边形，如此题图5.3所示。-505101520253001020ABCD4x1+3x2=1x1+x2=12x1+3x2=18可 行 解 域

7、Y X 图5.3 例题5.42的可行解域注：假设线性规划存在独一最优解，那么一定是可行解域的某个顶点。假设两个顶点都是最优解，那么这两个顶点连线上的任一点都是最优解，假设可行解区域无界，那么能够不存在最优解。第四节第四节 线性规划模型的单纯形法线性规划模型的单纯形法 一用换元迭代法解线性规划问题一用换元迭代法解线性规划问题 这种方法的过程的几何意义为：从凸多边形或多面体线性规划问题解的一个顶点可行基经换基迭代转变到另一顶点可行基，最终到达最优顶点，这就是线性规划问题解的换元迭代法，它奠定了矩阵方式的单纯形方法的根底。二二 单纯形方法的实际根底单纯形方法的实际根底三三. 换基迭代求最优解的过程换

8、基迭代求最优解的过程求解-单纯形法 将所给问题化为规范形 找出一个初始可行基,建立初始单纯形表 检查一切检验数(假设全为非负,那么已得到最优解,计算停顿.否那么继续下一步) 调查能否无解(假设是,计算停顿,否那么继续下一步) 确定入基变量,出基变量 对初始单纯形表进展单纯形变换四四. 用单纯形法解线性规划问题用单纯形法解线性规划问题作业作业某厂消费某厂消费A、B两种产品，每消费一件两种产品，每消费一件A产品需原资料产品需原资料90Kg，电量，电量400度度,工时工时30个，个，获利获利7000元；每消费一件元；每消费一件B产品需原资料产品需原资料40Kg，电量，电量500度度,工时工时100个，获利个，获利12000元，该厂每月方案可用原资料为元，该厂每月方案可用原资料为36000Kg，电量，电量20000度，工时度，工时3000个，问个，问每月消费每月消费A、B产品个多少件利润最大？建立其优化设计数学模型，并用几何图解产品个多少件利润最大？建立其优化设计数学模型，并用几何图解法求其最优解。法求其最优解。利用表利用表2-1所描画的