运筹学第1章线性规划清华大学出版社资料.ppt

线性规划研究的主要问题： 在一定的人力、财力、资源条件下，如何合理安排使用，使效益最高? 某项任务确定后，如何安排人力、财力、物力，使之花费最省? 线性规划介绍 历史悠久，理论成熟，应用广泛 运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。 一、线性规划问题及其数学模型 1、问题的提出 建立该问题的数学模型 解(1)决策变量:设生产产品I x1个单位，产品II x2个单位； (2)目标：总利润最大，于是记成max z=2x1+3x2, z 称为目标函数； (3)限制条件 (约束条件) a:各种设备的数量有限，无论如何安排生产，x1,x2均应满足如下条件： 数学模型 线性规划数学模型中隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比； 可加性：每个决策变量对目标和约束的影响独立于其它变量； 连续性：每个决策变量取连续值； 确定性：线性规划中的参数aij , bi , ci为确定值。 线性规划数学模型 线性规划问题应用 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用) 2、线性规划数学模型的形式 二、线性规划问题的求解方法 (一)图 解 法 例5、 (三)线性规划问题的解 需待解决的理论问题 什么条件下LP的可行域非空？可行域D有何特性？ 可行域D是否有顶点？顶点有多少个？顶点的数学含义？ 是否一定能保证最优解在顶点（D内）上达到？ 顶点是什么概念？ 基本可行解是否存在？如何判断？ 基本可行解是否唯一对应D的一个顶点？ 如何求基本可行解？ （三）、单纯形表 练习 需要注意的几个问题 若存在两个以上相同的最小比值，就会出现退化解。理论上讲，退化解可能使计算出现循环，从而得不到最优解。然而，实际问题中很少出现这种情况。 当计算中出现最小比值相同的情况时，可按Bland规则 来计算。 Bland 规则： ①在σj0中，选下标小的非基变量入基； ②对相同的最小比值，选下标小的基变量出基。 （二）、线性规划小结 练习1 练习2 四、线性规划模型的应用 例1： 例2： 例3： （五）、作物布局问题 土地面积 播种面积 单 土 产 地 作物 (六）分派问题 设有n件工作 分派给n人 去做， 每人只做一件工作且每件工作只分 派一人去做。设Ai完成Bj的工时为 。 问：应如何分派才使完成全部工作的总工时最少。 解：设 为Bj分派给人Ai情况： Bj分派给Ai时， ； 不分派给Ai时， 。 那末这一问题的数学模型为： 求一组变量 的值， 使目标函数 的值最小。 (完成全部工作的总工时最少） (六）分派问题 约束条件 每件工作只分派一人去做 每人只做一件工作 每人对每件工作只有 做与不做两种情况 分派问题的模型 目标函数 (七）生产组织与计划问题 (Ⅰ) 生产的机器最多 (Ⅱ) 总的加工成本最低 （Ⅲ）生产存储问题 (七）生产组织与计划问题 设某车间用机床 生产由 这n个不同零件 构成的机器。如果每架机器需要各 种零件的数目成比例 ; 机床 生产零件 的效率(每日 生产零件数)为 。 (Ⅰ) 生产的机器最多 应如何分配机床负荷，才使生产的机器最多? 求一组变 的值, 解：设 为一天机床 生产零件 的时 间（单位：日） 这一问题的数学模型为： 生产的机器台数 (七）生产组织与计划问题 (Ⅰ) 生产的机器最多 约束条件 各机床一天生产 各种零件总数， 应成已定比例 生产零件时间不能为负数 (七）生产组织与计划问题 各机床生产各种零件 时间总和应等于1 特别地