第一章线性规划

第一章线性规划 LP Linearprogramming 线性规划 是运筹学中研究较早 发展较快 应用广泛 方法较成熟的一个重要分支 它是辅助人们进行科学管理的一种数学方法 在经济管理 交通运输 工农业生产等经济活动中 提高经济效果是人们不可缺少的要求 而提高经济效果一般通过两种途径 一是技术方面的改进 例如改善生产工艺 使用新设备和新型原材料 二是生产组织与计划的改进 即合理安排人力物力资源 线性规划所研究的是 在一定条件下 合理安排人力物力等资源 使经济效果达到最好 例1 1原料分配问题 某工厂生产A B两种产品 已知生产A每吨要用煤9吨 电4度 劳动力3个工作日 生产B每吨要用煤5吨 电5度 劳动力10个工作日 又知每吨A B的利润分别为7000元和1 2万元 现在该工厂只有煤360吨 电200度 劳动力300个工作日 问在这种情况下 各生产A B多少吨 才能获最大利润 请建立模型 例1 1原料分配问题 例1 1原料分配问题 设生产A B分别x1吨和x2吨 获取利润为Z元 则 目标是获取利润最大 maxZ 7000 x1 12000 x2约束条件 9x1 5x2 360 煤的限制 4x1 5x2 200 电力限制 3x1 10 x2 300 工作日限制 x1 0 x2 0 数据最小值限制 例1 2环保问题 靠近某河流有两个化工厂 流经工厂1的河流流量为每天500万m3 两工厂之间有一条流量为每天200万m3的支流 见图 例1 2环保问题 工厂1每天排放污水2万m3 工厂2每天排放污水1 4万m3 污水从工厂1流到工厂2前会有20 自然净化 根据环保要求 河水中污水的含量应不大于0 2 而工厂1和工厂2处理污水的成本分别为1000元 万m3和800元 万m3 问两工厂各应处理多少污水才能使处理污水的总费用最低 例1 2环保问题 设工厂1和工厂2每天分别处理污水x1和x2万m3 两个工厂总的污水处理费用为Z 则有 目标 MinZ 1000 x1 800 x2 2 x1 500 0 002 0 8 2 x1 1 4 x2 700 0 002 x1 2 x2 1 4 x1 x2 0 约束 建立线性规划问题模型的步骤 确定决策变量确定目标函数确定约束条件 线性规划数学模型的形式 目标函数 Max Min z c1x1 c2x2 cnxn约束条件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 例1 3运输问题 要从甲乙两个仓库向A B C三个纺织厂运送原棉 三个纺织厂对原棉的需求量 甲乙仓库的库存量 以及从各仓库运送单位原棉到纺织厂所需的费用如图所示 问 如何调运 才能使总的运费最低 例1 3运输问题 例1 3运输问题 设仓库甲运往A B C三个纺织厂的原棉数量分别为x1 x2 x3 设仓库乙运往A B C三个纺织厂的原棉数量分别为x4 x5 x6 发生的总费为Z 则有 目标 MaxZ 2x1 x2 3x3 x4 2x5 4x6 xi 0 i 1 6 约束 x1 x2 x3 50 x2 x5 15 x1 x4 40 x4 x5 x6 30 x3 x6 25 重点内容 线形规划模型的组成部分线形规划模型的建立 问题 建立线性规划问题包括哪几步 确定决策变量 确定目标函数 确定约束条件求解线性规划问题的目的是什么 得到最优方案线性规划的目标函数是求其什么值 最大值或最小值 上机求解线性规划问题 安装软件 安装office2000以上版本 重点 应用其中excel部分 下载地址 ftp 例题建模 某企业可以生产A B两种产品 生产单位产品A和B所需要的机器 人工 原材料的数量 每天可用资源的总量和各种资源的价格 都在表中给出 已知产品A的售价600元 B的售价400元 市场需求旺盛 问 如何安排生产能使企业的利润最大 表企业产品生产与资源使用情况 分析 假设 X1为产品A每天的产量X2为产品B每天的产量C1为每天使用机器的数量C2为每天使用人工的数量C3为每天使用原材料的数量 分析与建模 Max600X1 400X2 5C1 20C2 1C3ST 6X1 8X2 C110X1 5X2 C211X1 8X2 C3C1 1200C2 1000C3 1300X1 0 X2 0 例题的上机求解 标示题设条件1确定决策变量的单元格2确定约束条件的单元格3确定售价 成本等的单元格4确定目标函数单元格 确定各单元格的数学表达式 规划求解 单击 规划求解 确定 目标单元格可变单元格约束条件 规划求解选项采用线性模型假定非负 最重要的 单击 确定 Anyquestion 27 例1 某工厂在计划