北京交通大学经济管理学院Schoolof EconcnicsandMarenagomentBoijing Jinotong University第一章线性规划(1)(LinearProgrammingLP北京文通大学
第一章 线性规划(1) ( Linear Programming) LP
北京交通大学经济管理学院提纲rics andManagomentatresEtongonayIofEcono1.线性规划问题及其数学模型问题的提出图解法线性规划问题的标准形式线性规划问题解的概念线性规划问题的几何意义2. 基本概念几个定理北京文通大学
提 纲 1. 线性规划问题及其数学模型 • 问题的提出 • 图解法 • 线性规划问题的标准形式 • 线性规划问题解的概念 2. 线性规划问题的几何意义 • 基本概念 • 几个定理
北京交通大学经济管理学院1.线性规划SchoolticsandManagomenBouingotong University线性规划(Linear Programming,LP)是运筹学的重要分支线性规划线性+规划规划一确定决策变量(给出最优方案)线性--目标函数一线性函数约束条件一线性方程组或线性不等式组北京交通大学
1. 线性规划 线性规划(Linear Programming, LP)是运筹学的 重要分支. 线性规划=线性+规划 规划—确定决策变量 (给出最优方案). 线性- − − 目标函数 线性函数 约束条件 线性方程组或线性不等式组
北京交通大学经济管理学院SchoolotEBoingtonaUntBUR4.线性规划的发展1939年，前苏联数学家康托洛维奇用类似线性规划的模型研究提高组织和生产效率问题1947年,Dantzig提出线性规划及求解线性规划的单纯形法1960年，Dantzig和Wolfe研究成功分解算法,奠定了大规模线性规划问题理论和算法的基础1979年,苏联Khachivan提出第一个多项式时间的算法--椭球算法1984年，Karmarka研究成功线性规划的多项式算法--内点法北京交通大学
4. 线性规划的发展 – 1939年, 前苏联数学家康托洛维奇用类似线 性规划的模型研究提高组织和生产效率问题. – 1947年, Dantzig提出线性规划及求解线性规 划的单纯形法. – 1960年, Dantzig和Wolfe研究成功分解算法,奠 定了大规模线性规划问题理论和算法的基础. – 1979年,苏联Khachiyan提出第一个多项式时 间的算法-椭球算法. – 1984年, Karmarka研究成功线性规划的多项 式算法-内点法
北京交通大学经济管理学院1.线性规划Schooltofgcsand ManagomentBoijingJiaotongUniversity弄清问题的目标、约束、决策变量及提出和形成问题：其参数，收集有关资料等建立模型：将变量、参数、目标及约束关系用模型表示出来.求解：用各种手段对模型求解，解可以是最优解、次优解和满意解解的检验：求解步骤和程序有无错误、解是否能反映实际.解的控制：解的实施：北京交通大学
1. 线性规划 提出和形成问题：弄清问题的目标、约束、决策变量及 其参数, 收集有关资料等. 建立模型：将变量、参数、目标及约束关系用模型表示 出来. 求解：用各种手段对模型求解,解可以是最优解、次优解 和满意解. 解的检验：求解步骤和程序有无错误、解是否能反映实 际. 解的控制： 解的实施：
北京交通大学经济管理学院数学规划的三个要素Schoolof Econorics and ManagomentBoijing Jinotong University决策变量每组决策变量的值代表一个方案目标函数决策变量的函数约束条件决策变量的关系式1.决策变量是什么？2.要达到什么目标？3.受哪些约束约束？北京交通大学-
数学规划的三个要素 1.决策变量是什么？ 2.要达到什么目标？ 3.受哪些约束约束？ 决策变量 每组决策变量的值代表一个方案 目标函数 决策变量的函数 约束条件 决策变量的关系式
北京交通大学经济管理学院1.1 问题的提出Schoolat Economics andManagomentBoijing Jiaotong University例1.某工厂计划期内要安排生产I、（生产计划问题）II两种产品,已知生产单位产品所需的设备台时和A、B两种原材料的消耗，以及可获利润如表所示，问应如何安排计划使该工厂获利最多？【表格式条件】II x2I xi可利用资源设备28104原材料A160原材料B4122?元利润3
1.1 问题的提出 【生产计划问题】例1.某工厂计划期内要安排生产Ⅰ、 Ⅱ两种产品,已知生产单位产品所需的设备台时和 A、B 两种原材料的消耗, 以及可获利润如表所示, 问应如何 安排计划使该工厂获利最多？[表格式条件] x1 x Ⅰ Ⅱ 2 可利用资源 设备 原材料A 原材料B 1 4 0 2 0 4 8 16 12 利润 2 3 ？元
[决策变量]设x1、x.分别表示计划期内产品III的产量，建立数学模型：【目标函数】Z=2x +3x利润型目标maxXi +2x2 ≤84x ≤16资源约束【约束条件]S.t.4x, ≤12非负约束x ≥ 0,x ≥0实际含义，(s.t.=Subject to)隐形约束目标函数与约束条件都是线性的
[决策变量] 设 x1、x2 分别表示计划期内产品Ⅰ、 Ⅱ的产量，建立数学模型： [约束条件] （s.t.=Subject to） [目标函数] max Z x x = + 2 1 2 3 资源约束 利润型目标 1 2 1 2 1 2 2 8 4 16 . . 4 12 0, 0 x x x s t x x x + [约束条件] 1 2 1 2 1 2 2 8 4 16 . . 4 12 0, 0 x x x s t x x x + 非负约束 实际含义, 隐形约束 目标函数与约束条件都是线性的
【环保问题】例2.靠近某河流有两个化工厂（见图），流经第一化工厂的河流流量为每天500万m3.在两个工厂之间有一条流量为每天200万m3的支流.第一化工厂每天排放含有某种有害物质的工业污水2万m.第二化工厂每天排放这种工业污水1.4万m.从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化.根据环保要求，河流中工业污水的含量不应大于0.2%.这两个工厂都需各自处理一部分工业污水.第一化工厂处理工业污水的成本是1000元/万m.第二化工厂处理工业污水的成本是800元/万m3.现在要问在满足环保要求的条件下，每厂各应处理多少工业污水使这两个工厂总的处理工业污水费用最小
【环保问题】例 2.靠近某河流有两个化工厂(见图), 流 经第一化工厂的河流流量为每天 500 万m3 , 在两个工厂 之间有一条流量为每天 200 万m3 的支流. 第一化工厂 每天排放含有某种有害物质的工业污水 2 万m3 , 第二化 工厂每天排放这种工业污水 1.4 万m3 . 从第一化工厂排 出的工业污水流到第二化工厂以前, 有 20% 可以自然 净化. 根据环保要求, 河流中工业污水的含量不应大于 0.2%. 这两个工厂都需各自处理一部分工业污水. 第一 化工厂处理工业污水的成本是1000元/万m3 ,第二化工厂 处理工业污水的成本是 800 元/万m3 . 现在要问在满足 环保要求的条件下,每厂各应处理多少工业污水,使这两 个工厂总的处理工业污水费用最小
2万m3oI厂11.4万m3oI厂220%净化500万m3200万m2[决策变量]设 x}、x2 分别为第一、第二化工厂每天处理的工业污水量[约束1]第一化工厂到第二化工厂之间的污水含量要不大于0.2%(2-x)/500 ≤2/1000
[决策变量]设 x1、x2 分别为第一、第二化工 厂每天处理的工业污水量. [约束1] 第一化工厂到第二化工厂之间的污水含 量要不大于0.2% (2- x1 )/500 2/1000 2万m3 1.4万m3 20%净化