[数学]4 线性规划.pptVIP

第四章 线性规划 线性规划模型的建立 线性规划模型的标准形 线性规划模型的图解法 线性规划模型的单纯形法 第一节 线性规划模型的建立 建立线性规划模型有三个基本步骤： 第一步，找出问题中的所有相关的未知变量（决策变量），并用代数符号表示它们，根据变量的物理性质研究变量是否有非负性； 第二步，找出问题中的目标，写成变量的线性函数，作为线性规划模型的目标函数； 第三步，找出问题中所有的限制或约束，写成变量的线性方程或线性不等式，作为线性规划模型的约束条件。 例题5.1 (生产计划问题) 某厂计划内将安排生产I,II两种产品，已知生产单位重量的产品所需的设备为A及B、C两种原料的消耗如表1所示： 生产单位重量的产品I可获利2万，生产单位重量的产品II可获利5万。 问：如何安排生产可使工厂获得的利润最多？ [例题5.3]（合理配料问题）根据对77种食物所含的九种营养物：热量(糖与脂肪)、蛋白质、钙、铁、维生素A、维生素BI、维生素B2、草酸与维生素C的成份及食物的市场价格调查，按照医生所提出的对每个人每天所需的营养要求，可得表5.3 问怎样采购食物才能在保证营养要求的前提下花费最省？这就是营养问题或饮食问题，配料问题就是由此而推广来的。 满足目标函数，即使得目标函数达到最大值或最小值的可行解，称为该线性规划模型的最优解。把最优解代入目标函数所得到的目标函数的最大值或最小值称为最优值。 定义5.2 某个线性规划模型的全体可行解组成的集合，称为该线性规划模型的可行解域。 二．线性规划模型的标准型 线性规划模型的标准型为： 标准型具有以下特点： 目标函数是求最大值； 约束条件为线性方程组；  未知变量都有非负限制。 线性规划模型的非标准型，在以下三种情况下可化为标准型： 目标函数是求最小值 约束条件为不等式 模型中的某些变量没有非负限制 第三节 线性规划模型的图解法 [例题5.4] 求以下线性规划问题的最优解： （1）第一步，求可行解域： 可行解域是所有满足约束条件的数组，四个不等式是四个半平面，而可行解域就是这四个半平面的公共部分。其形状为一个凸多边形区域，可行解是凸多边形内的一个点，如图5.1。 第二步，求最优解： （2）线性规划的可行解域一般为凸多边形，而有时则是无界的凸多边形，如本题图5.3所示。 第四节 线性规划模型的单纯形法 一．用换元迭代法解线性规划问题 这种方法的过程的几何意义为：从凸多边形（或多面体）线性规划问题解的一个顶点（可行基）经换基迭代转变到另一顶点（可行基），最终达到最优顶点，这就是线性规划问题解的换元迭代法，它奠定了矩阵形式的单纯形方法的基础。 二． 单纯形方法的理论基础 三. 换基迭代求最优解的过程 求解--单纯形法 将所给问题化为标准形 找出一个初始可行基,建立初始单纯形表 检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步) 考察是否无解(若是,计算停止,否则继续下一步) 确定入基变量,出基变量 对初始单纯形表进行单纯形变换 四. 用单纯形法解线性规划问题 例题5.2（合理下料问题）某厂生产过程中需要用长度分别为3．1米、2．5米和1．7米的同种棒料毛坯分别为200、100和300根，而现在只有一种长度为9米的原料，问应如何下料才能使废料最少? 解 解决下料问题的关键在于找出所有可能的下料方法(如果不能穷尽所有的方法，也应尽量多收集各种可能的下料方法)，然后对这些方案进行最佳结合。 对给定的9米长的棒料进行分割，可以有9种切割方法，见表5.2所示。 表5.2 毛坯切割方案表 第二节 线性规划模型的标准形 一．线性规划模型的可行解和最优解 线性规划模型的标准型还可以记为： 图5.1 例题5.4（1）的可行解域 图5.2 例题5.4（1）的最优解 图5.3 例题5.4（2）的可行解域 注：若线性规划存在唯一最优解，则一定是可行解域的某个顶点。若两个顶点都 是最优解，则这两个顶点连线上的任一点都是最优解，若可行解区域无界， 则可能不存在最优解。