4-2 线性规划简介.pptVIP

文 科 数 学 文 科 数 学 §2 线性规划简介 一、线性规划问题举例 二、图解法 三、线性规划的标准型 四、线性规划解的概念 五、单纯形法 六、线性规划的应用 文 科 数 学 线性规划是运筹学的一个重要分支。由前苏联经济学家康托洛维奇于1939年提出，而此人也因此获得1960年的诺贝尔经济学奖。 线性规划是一类特殊的最优化问题，它是针对一类有限资源如何合理利用这样的问题而提出的。 1947年，G. B. Dantzig 提出求线性规划的单纯形法（simple method），理论上趋向成熟，实际上的应用也越来越广泛。 文 科 数 学 例1. 生产计划问题 某企业要在计划期内安排生产甲、乙两种产品，该企业现有生产资料：设备18台时，原材料A 4吨，原材料 B 12吨；已知单位产品所需消耗的生产资料及利润如下表。 问应如何确定生产计划使企业获利最多？ 一、线性规划问题举例 产品 资源 甲 乙 资源量 设备/机时 3 2 18 原料A/吨 1 0 4 原料B/吨 0 2 12 单位赢利/万元 3 5 文 科 数 学 问题的分析 首先明确要决策什么—确定产品甲、乙的生产量 为了定量分析解决该问题，应先建立数学模型 设 x1 , x2 分别表示甲、乙两种产品的产量，称为决策变量 用一组决策变量 (x1, x2)T 表示一个方案，变量的不同取值表示不同的方案（目标：寻找最优方案） 其次分析 x1, x2 应满足什么条件，才能使生产正常进行 由于现有的生产资料总量是有限的，因此：正常生产过程中生产资料的消耗不能超过现有量 文 科 数 学 产品 资源 甲 乙 资源量 设备/机时 3 2 18 原料A/吨 1 0 4 原料B/吨 0 2 12 单位赢利/万元 3 5 x1, x2 应同时满足下列条件： 设备台时限制： 原材料A限制： 原材料B限制： 由于产品产量不能是负的，故有非负限制： 文 科 数 学 x1, x2 应同时满足下列条件： 设备台时限制： 原材料A限制： 原材料B限制： 由于产品产量不能是负的，故有非负限制： 该生产计划的总利润为： 现在的问题是：找出 x1, x2 ，在上述各种条件的限制下，使 z 达到最大值 文 科 数 学 该生产计划问题的数学模型 目标函数 约束条件 非负约束条件 文 科 数 学 一般的资源合理利用问题 设某企业利用 m 种资源来生产 n 种产品，已知该企业拥有的第 i 种资源的数量是 bi, 生产单位第 j 种产品所消耗的第 i 种资源的数量为 aij，第 j 种产品的单位利润为 cj。 现制定一个生产计划方案，使总利润最大。 注：常用术语 aij：技术系数，bi：资源系数，cj：价值系数 用 xj 表示第 j 种产品的生产量 文 科 数 学 一般的资源合理利用问题的数学模型 文 科 数 学 例2. 人员分配问题 设某单位现有 n 个人员A1, A2, …, An 来完成 n 项工作B1, B2, …, Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成；已知人员Ai 做工作Bj 的效率是 cij。 问应如何分配，才使总效率最好？ 问题的分析 令 xij 表示分配人员 Ai 完成工作 Bj 的决策变量， xij = 1 表示分配 Ai 干工作 Bj xij = 0 表示不分配 Ai 干工作 Bj 按问题要求：每人要做一项工作，每项工作需一人去做。 文 科 数 学 令 xij 表示分配人员 Ai 完成工作 Bj 的决策变量， xij = 1 表示分配 Ai 干工作 Bj xij = 0 表示不分配 Ai 干工作 Bj 按问题要求：每人要做一项工作，每项工作需一人去做。 对人员 Ai，要求承担一项工作： 对工作 Bj，要求一人去完成： 派工方案的总效益： 文 科 数 学 人员分配问题的数学模型 文 科 数 学 A B C 产量 甲 21 25 7 2000 乙 51 51 37 1000 销量 1700 1100 200 例3. 物资运输问题 某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是2000吨、1000吨；另有A、B、C三个销地，销量分别是1700吨、1100吨、200吨；已知