[第二章运筹学线性规划.doc

第二章 线性规划 主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质 3、图解法 4、单纯形法 5、大M法和两阶段法 重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。 要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握其求解技巧；培养解决实际问题的能力。 §1 线性规划的数学模型及解的性质 一、数学模型（一般形式） 例1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？ 造价（元/m2） 钢材（kg/m2） 水源（kg/m2） 砖(块/m2) 人工（工日/m2） 砖混结构 大板结构 大模结构 资源限量 105 137 122 11000万元 12 30 25 2000万千克 110 190 180 15000万块 210 14700万块 4.5 3.0 3.5 400万工日 解：设三种体系的建筑面积依次为,,万平方米， 则目标函数为 约束条件为 例2 某工厂要安排生产甲、乙两种产品。已知： 煤耗（T/T） 电耗（kwh/T） 油耗（T/T） 单价（万元/T） 甲产品 乙产品 资源限量 9 4 360T 4 5 200kwh 3 10 300T 7 12 问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设分别为甲、乙两种产品的生产量： 则目标函数为 约束条件为 从以上两例可以看出，它们都属于一类优化问题。它们的共同特征： ①每一个问题都有一组决策变量（）表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量的取值是非负的。 ②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。 ③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为： 目标函数 约束条件 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。 二、标准型 （一）问题的标准形式： 其中 注意：任何一个一般型都可转化为一个标准型。 （二）标准型的表示方法： 1、和式形式： 2、矩阵形式： 其中 -------价格系数向量 -------资源向量（限定系数向量） -----------约束条件系数矩阵 --------决策变量 3、向量形式： 其中 为约束条件系数矩阵A的第j列。 （三）一般型化为标准型的方法 1、 引进新的目标函数, 则可化为 2、不等式约束 ① 引进新的非负决策变量, 使得 称为松弛变量，在目标函数中，其价格系数为0。 ② 引进新的非负决策变量,使得 称为剩余变量，在目标函数中，其价格系数为0。 3、若，即 可变为 4、若某个变量无非负限制，称为自由变量。 令 例3 将下列问题化为标准型 解：标准型为 例4 将下列问题化为标准型 解：令 ，标准型为： 令 则标准型为：  三、线性规划问题的解 标准型 记 秩: 1、基阵：若列向量是线性无关的，则称为LP问题的一个基阵。基矩阵中每个列向量称为基向量。 由非基向量组成的矩阵称为非基矩阵，记为 例如： 取 线性无关，则 线性无关，则 2、基变量：基矩阵中各列向量对应的变量称为基变量，记为。 如, 则基变量为。 对应于非基向量的变量称为非基变量，记为 3、基本解：设基矩阵为，则非基矩阵 那么，约束方程 即 --------有无穷解 令 则 那么，约束方程组的解 ，将其称为问题的基本解。 注意：基本解不一定是可行解，若,则称为问题的基本可行解，对应于基本可行解的基矩阵，称为可行基。 4、最优解：对应于某一可行基，使目标函数获得最优值的基本可行解，称为最优解。最优解所对应的基矩阵称为最优基。 举例说明： 约束矩阵 若取基矩阵 则非基矩阵 基变量,非基变量 ∴基本解为 是基本可行解 若取基矩阵 则 -----基本可行解 注意：基本可行解与可行域