[管理学]运筹学课件.ppt

第一章 线性规划 (Linear Programming) 第一节 LP问题的数学模型 第二节 两个变量LP问题的图解法 第三节 数学模型的标准化 第四节 标准形式的解的概念 第五节 LP问题解的基本理论 第六节 单纯形法 第七节 改进单纯形法 第八节 运输问题的表上作业法 第一节 线性规划问题的数学模型 线性规划的数学模型由决策变量、目标函数、约束条件构成，称为三个要素。 其特征是： 1、目标函数是决策变量的线性函数，通常是求最大值或最小值； 2、约束条件是一组线性不等式或等式。 这样的模型称为线性规划模型, 相应的实际问题称为线性规划问题。 线性规划的数学模型的一般形式为： 线性规划是运筹学的一个重要分支，其应用范围极广，如：合理运用原材料问题、配料问题、投资问题、产品生产计划、劳动力安排、运输问题等都可以用线性规划模型来解决。 具体来说，线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原材料、人工、时间等）去完成确定的任务或目标． 例2 如图，靠近某河流有两个化工厂，流经甲厂的河水流量为每天500万m3 ， 在两个工厂之间有一条流量为每天200万m3 的支流．甲厂每天排放工业污水2万m3 ，乙厂每天排放工业污水1.4万m3 ．甲厂排出的污水流到乙厂之前有20%可以自然净化．应环保要求，河流中工业污水的含量应不大于0.2% ．两厂都需清理部分工业污水,甲厂清理工业污水的成本是1000元/万m3 ,乙厂清理污水的成本是800元/万m3 ． 问：在满足环保要求的条件下，每厂各应处理多少污水，使两个工厂总的处理费用最小？ 解 设甲厂每天处理工业污水 x1 万m3 ，乙厂每天处理工业污水 x2 万m3，则 解 设甲厂每天处理工业污水 x1 万m3 ，乙厂每天处理工业污水 x2 万m3，则 通过以上两例，我们基本上已经掌握了如何 建立线性规划模型。 需要注意的是，建立模型是运筹学的核心， 为了便于分析和研究问题，一般地，数学模型 应具有两个特点： 1、要尽可能简单； 2、要能完整地描述所研究的系统。 建立模型时首先要弄清问题所涉及的决策 变量以及它们的相互关系，从而建立目标函数 和约束方程。 建立模型是第一步。接下来应该对数 学模型进行求解。 下面给出线性规划问题的解的一些概念。 线性规划问题的解： 1 可行解：满足所有约束条件的解． 2 可行域：全部可行解组成的集合． 3 最优解：使得目标函数值取得最小值 或最大值的可行解． 4 最优值：最优解对应的目标函数值． 第二节 图解法 图解法是直接在平面直角坐标系中作图 解线性规划问题的一种方法。这种方法简单直 观，适合于求解两个变量的线性规划问题． 根据以上例题可知，LP问题的可行域及最优解有以下几种情况： 1、可行域为封闭的有界区域 a. 有唯一最优解 b.有无穷多个最优解 2、 可行域为非封闭的无界区域 a.有唯一最优解 b.有无穷多最优解 c.无最优解（无界解） 3、可行域为空集 无可行解，无最优解 线性规划的数学模型的一般形式为： 为了便于讨论和制定统一的算法，规定线性规划问题的标准形式为 标准形式的特点： （1）目标函数求最小值； （2）约束条件全为等式； （3）约束方程右端的常 数非负； （4）决策变量非负。 目标函数中的系数cj 称为目标函数的系数，也可按问题的经济意义称之为收益系数、利润系数、费用系数或价值系数等； 约束条件中的右端常数bi 称为需要系数或限定系数； aij 称为工艺系数或消耗系数。 标准形式可用向量表示 标准形式也可用矩阵表示 下面举例说明如何化一般形式为标准形式： 例1 把下面线性规划问题化为标准形式 解：目标函数化为最小： 对(1)式，将其变为 称为松弛变量； 对(2)式，两边同乘以-1，得 再将上式变为 称为剩余变量； 又x3无符号限制，令 1、若目标函数是求最大值，则将其化为求最小 值 ，令S’=-S 即可，求解 maxS minS’ 2、若 ，则两