线性规划最新课件

1、线性规划最新课件 线性规划研究的主要问题线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研究如 何充分合理地使用它们，才能使完成的任务量为最大。 实际上，上述两类问题是一个问题的两个不同的方面，都是求问 题的最优解（ max 或 min ）。 另一类是当一项任务确定以后，研究如何统筹安排，才能使完 成任务所耗费的资源量为最少。 第一部分第一部分 线性规划线性规划 （Linear Programming，简称，简称LP） 线性规划最新课件 第一章第一章 线性规划基础线性规划基础 例1.1 某厂生产两种产品，下表给 出了单位产品所需资源及单位产品 利润 问：应如何安排生产计

2、划，才能使 总利润最大？ 1.1 1.1 线性规划的基本概念线性规划的基本概念 一、问题的提出一、问题的提出 解：解： 1.决策变量：设产品I、II的产量分 别为 x1、x2 2.目标函数：设总利润为z，则有： max z = 2 x1 + 3 x2 3.约束条件： x1 + 2x2 8 4x1 16 4x2 12 x1， x20 线性规划最新课件 例1.2 某厂生产三种药物，这些药 物可以从四种不同的原料中提取。 下表给出了单位原料可提取的药物 量 要求：生产A种药物至少160单位； B种药物恰好200单位，C种药物不 超过180单位，且使原料总成本最 小。 解：解： 1.决策变量：设四种原

3、料的使用 量分别为： x1、x2 、x3 、x4 2.目标函数：设总成本为z，则有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x4 3.约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 药物 原料 ABC 单位成本 （元吨） 甲1235 乙2016 丙1417 丁1228 线性规划最新课件 二、数学模型二、数学模型 1.决策变量： X = (x1,x2,.,xn)T 2.目标函数：max(minz) = c1 x1 + c2 x2 + . + cnxn

4、3.约束条件： a11x1 + a12 x2 +.+ a1n xn (=) b1 a21x1 + a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0 线性规划最新课件 三、模型特点三、模型特点 1 都用一组决策变量X = (x1,x2,xn)T表示某一方案，且决策变量取值非负； 满足以上三个条件的数学模型称为线性规划满足以上三个条件的数学模型称为线性规划 2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数； 3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等 式来表示。 线性规划最新课件 ),2, 1(0 ),2, 1( M 1 1 njx mibxa xcaxz j n j ij n j jj j i 标准形式标准形式 线形规划的标准化线形规划的标准化 1如果求如果求min 2如果约束条件如果约束条件 3. 如果如果b0，则目标函数 不可能实现最优。 “惩罚” 人工变量！ 线性规划最新课件 线性规划最新课件 线性规划最新课件 m 1i jiij 0 i bPP)a(x bPX bxP i n 1i i 线性规划问题的一般形式线性规划问题的一般形式 m