1、线性规划与目标规划Date 1目 录1.线性规划与单纯形法2.对偶理论和灵敏度分析3.运输问题4.目标规划Date 2q线性规划 (Linear Programming)是运筹学的一个重要分支。q线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。它已是现代科学管理的重要手段之一。q线性规划最常用的求解方法 单纯形法 (Simplex Method) 由丹捷格 (G B Dantzig)提出 (1947年 )。线性规划问题及其数学模型Date 3线性规划问题及其数学模型1.1 问题的提出例 1 生产计划 某工厂在计划期内要安排生产 、 两种产品，已知生产单位产品所需的设备台时及 A、 B两
2、种原材料的消耗，如表所示。问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？如何用数学关系式描述这个问题？Date 4线性规划问题及其数学模型q设 x1 ， x2 分别表示计划生产 I， II产品的数量，称它们为决策变量 。q生产 x1 ， x2 的多少，受到资源拥有量的限制，即存在 约束条件 。 x1 +2x2 84 x1 164 x2 12q生产的产品不能是负值： x1 ， x2 0。q如何安排生产，使得利润最大，这是 目标函数 。max z = 2 x1 + 3 x2Date 5线性规划问题及其数学模型q因此该问题的数学模型为：( 设 生产甲产品 x1 个单位、生产乙产品 x2
3、个单位 )q目标函数 : max z = 2 x1 + 3 x2q约束条件 : x1 +2x2 84 x1 164 x2 12x1 ， x2 0q这种模型实际上是一种约束限制下的最优线性数学模型，称为线性规划。Date 6线性规划问题及其数学模型q例 2 简化的环境保护问题 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天 500万立方米，在两个工厂之间有一条流量为每天 200万立方米的支流。q 第一化工厂每天排放含有某种有害物质的工业污水 2万立方米，第二化工厂每天排放这种工业污水 1.4万立方米。q 从第一化工厂排出的工业污水流到第二化工厂以前，有 20%可自然净化。根据环保要求，河
4、流中工业污水的含量应不大于 0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是 1000元 /万立方米。第二化工厂处理工业污水的成本是 800元 /万立方米。q 现在问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。Date 7线性规划问题及其数学模型q 建模型之前的分析和计算q 设 ：第一化工厂每天处理工业污水量为 x1 万立方米，第二化工厂每天处理工业污水量为 x2 万立方米。此问题的线性规划模型 ：目标函数 ： max z = 1000 x1 + 800 x2 约束条件 ： s.t. x1 10.8x1 + x2 1.6
5、x1 2 x2 1.4x1 , x2 0Date 8线性规划问题及其数学模型q 从以上两例可以看出，其共同特征：(1) 每一个线性规划问题都用一组 决策变量 表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量取值是非负且连续的；(2) 存在有关的数据，同决策变量构成互不矛盾的 约束条件 ，这些约束条件可以用一组线性等式或线性不等式来表示； (3) 存在一个要求达到的目标，它可用决策变量及其有关的价值系数构成的的线性函数 (称为 目标函数 )来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为 线性规划 的数学模型。Date 9线性规划问题及其数学模型q 线性规划问题是 在一组线性等式或不等式的约束之下，求一个线性函数的最大值或最小值的问题。q 它由以下部分 组成：目标函数 max z 或 min f约束条件 s. t. (subject to) 满足于决策变量 用符号 xj 等来表示可控制的因素。Date 10
