经济数学方法与模型教学PPT课件-第三章 线性规划.pptVIP

第三章 线性规划 本章主要内容 LP问题的提出及其数学模型 LP问题的解及其性质 单纯形法 大M法与两阶段法 第一节 问题的提出及数学模型 线性规划问题的提出 线性规划问题的数学模型 线性规划模型的标准化 一、线性规划问题的提出 现实生活中，我们经常面临这种情况，有许多活动 要完成，同时存在为完成这些活动可供选择的多种方法。 但是，由于有时某些资源有限，这就有一个稀少资源的 最优分配问题．线性规划就是研究这样一类问题的理论 和方法．可以归纳成两种类型的问题：一类是给定了一 定数量的人力、物力、财力资源，研究如何运用这些资 源使完成的任务最多；另一类是给定了一项任务，研究 如何统筹安排，才能以最少的人力、物力、财力等资源 来完成该项任务． 例1 生产计划问题 某工厂生产甲、乙两种产品，这两种产品都需要在A、B、C三 种不同设备上加工．每吨甲、乙产品在不同的设备上加工所需的台 时数，它们销售后所能获得的利润值以及这三种加工设备在计划期 内能提供的有限台时数列于表3-1．试问：如何安排生产计划，即 甲、乙两种产品各生产多少吨，方可使该厂所得利润最大？ 表 3-1 解：设在计划期内甲、乙两种产品的产量分别为 、 吨 目标函数 约束条件 例2、营养配餐问题 有A、B两种食品，含有每天必须的营养成分C和D， 每天至少需要营养分成C和D分别为2和3个单位．食品A 和B的成分和单价如表3-2所示．试问如何定制食谱才能 使费用最省？ 表 3-2 解：设每天购买食品A、B分别为 ， 个单位 目标函数 约束条件 例3、合理下料问题 有一批某种型号的圆钢长8m，需要截取长2.5m的毛 坯100根，长1.3m的毛坯200根，问怎样选择下料方式，才 能既满足需要，又使总的用料最少？（各种可能的搭配 方案如表3-3所示）． 表 3-3 解：设第 种方式所用的原材料根数为 目标函数 约束条件 以上例子，尽管其实际问题的背景不同，但讨论的都是资源的最优分配问题．它具有如下一些共同特点： 目标明确：决策者有着明确的目标，即寻求某个整 体目标最优，如最大收益，最小费用等． 多种方案：决策者可以从多种可供选择的方案中选 取最佳方案，如不同的生产方案和不同的物资调运方案 以及不同的下料方案等． 资源有限：决策者的行为必须受到限制，如产品的 产量受到设备有限台时的限制，所用原料要受到产量的 限制，项目投资又要受到种种原因的限制． 线性关系：约束条件及目标函数均保持线性关系． 具有以上特点的决策问题，被称之为线性规划问题。 二、线性规划问题的数学模型 一般形式 标准形式 缩写形式 1、LP问题的一般形式 2、LP问题的标准形式 线性规划问题的标准形式要求所有约束必须为等式约束，所有变量为非负变量，并且本教材规定为目标函数极大化． 3、LP问题的缩写形式 （1）线性规划模型的一般缩写 （2）向量表示的缩写 其中 （3）矩阵表示的缩写 其中 ，其它同前．我们称 为约束 方程组的系数矩阵，一般 ， 与 均为正整数． 三、线性规划模型的标准化 1、将极小化目标函数转化为极大化目标函数． 求一个函数的极小值等价于求该函数相反值的极大 值，若求： 则可先将目标函数乘以（-1）化为 求极大值问题，即求： 。因此只需要改 变目标函数的符号就可以完成极大与极小之间的转换． 2、把不等式约束转化为等式约束． 可以在约束条件中添置变量：当约束为“≤”时， 在等式左端加上一个非