[经管营销]第二章 线性规划与单纯形法.pptVIP

第二章 线性规划与单纯形法（Linear Programming，简称LP） §1 线性规化问题及其数学模型 §2 线性规化问题的几何意义 §3 单纯形法 §4 单纯形法的计算步骤 §5 单纯形法的进一步讨论 §6 应用案例 §1线性规化问题及其数学模型 1.1 问题的提出 例1：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表，该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划使该工厂获利最多？ 例2：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3,在两个化工之间有一条河流量为每天200万m3的支流,第一化工厂每天排放含某种有害物质的工业污水2万m3,第二化工厂排放这种工业污水1.4万m3,从第一化工厂排出的工业污水流到第二化工厂之前，有20%可以自然净化。根据环保要求河流中工业污水的含量应不大于0.2%。这两个化工厂都需处理一部分工业污水。第一化工厂处理工业污水的成本为1000元/万m3,第二化工厂处理工业污水的成本为800元/万m3。问在满足环保要求的条件下，每厂各应处理多少工业污水，使两个化工厂处理工业污水的总成本最小。 特征： 每一个问题都用一组决策变量（ x1， x2， …，xn ）表示某一个方案； 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示； 都有一个要求达到的目标，它可以用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化。 线性规划问题的数学模型的一般形式为： 1.2 图解法 1.3 线性规化问题的标准型式 如何化标准型 目标函数求最小minz = CX 。可化为： max (-z) = -CX。 约束条件为不等式。对于“≤”不等式，在不等式的左边加上非负松驰变量后变为等式；对于 “≥”不等式，在不等式的左边减去非负剩余变量后变为等式。 3. 变量 xk 无约束。可令 xk = xk’ -xk’’ 1.4 线性规化问题的基可行解 1.4 线性规化问题的基可行解 基：设A是约束方程组的m×n阶系数矩阵，其秩为m，B是矩阵A中m×m阶非奇异子矩阵（|B|≠0），则称B是线性规划问题的一个基。 基B的列Pj称为基向量，与基向量对应的变量xj称为基变量，否则称为非基变量。 基解：令非基变量为零，由约束方程AX=b求得的解称为基解。 基可行解：满足非负条件的基解称为基可行解。 可行基: 对应于基可行解的基称为可行基。 注：基解的个数最多是Cnm个，基可行解的个数一般要小于基解的个数。 §2 线性规化问题的几何意义 2.1 基本概念 2.2 基本定理 定理1：若线性规划问题存在可行域，则可行域一定是凸集。 引理1 线性规划问题的可行解X为基可行解的是充要条件是X的正分量所对应的系数列向量是线性独立的。 引理2 若K是有界凸集，则任何一点X ∈K可表示为 K的顶点的凸组合。 定理2 线性规化问题的基可行解对应于可行域的顶点。 　 定理３ 若可行域有界，线性规划的目标函数一定可以在其可行域的顶点上达到最优． 1.线性规划问题的所有可行解构成的集合可行域是凸集，也可能是无界域； 2.可行域有有限个顶点，线性规划问题的每个基可行解对应于可行域的一个顶点； 3.若线性规划问题有最优解，必在可行域的某顶点上达到。 §3 单纯形法 单纯形法的基本思路： 3.1 实例分析 例： 3.2 初始可行解的确定 1.观察法：通过观察确定初始可行解，例如下列线性规划问题： 3.3 最优性检验与解的判别 检验数：目标函数用非基变量表达后，非基变量的系数称为检验数。 1. 最优解的判别定理：若X(0)是线性规划问题的一个基可行解，如果对应的非基变量的检验数都小于等于零，则X(0)为最优解。 2. 无穷多最优解的判别定理：若X(0)是线性规划问题的一个基可行解，如果对应的非基变量的检验数都小于等于零，又存在某个非基变