-线性规划.pptVIP

线 性 规 划 线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解 对偶理论 灵敏度分析 计算软件 案例分析 线 性 规 划 问 题 线性规划实例 生产计划问题 运输问题 线性规划模型 一般形式 规范形式 标准形式 形式转换 概念 某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划 问 题 分 析 模 型 计 算 结 果 运 输 问 题 问 题 分 析 模 型 一 般 形 式 注 释 规 范 形 式 标 准 形 式 概 念 模 型 转 换 约束转换 实例 约 束 转 换 不等式变等式 不等式变不等式 不 等 式 变 等 式 不等式变不等式 例2.1.3 把问题转化为标准形式 可行区域与基本可行解 ?图解法 ? 可行域的几何结构 ?基本可行解与基本定理 图 解 法 例2.2.1 解线性规划 例2.2.1 解线性规划 注 释 可能出现的情况： 可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是最优解 可行域的几何结构 基本假设 凸集 可行域的凸性 基 本 假 设 凸 集 问 题 基 本 可 行 解 与 基 本 定 理 定义 基本定理 问题 基 本 可 行 解 定 义 基 本 定 理 结　　　论 单 纯 形 算 法 理论方法 算法步骤 单纯形表 算例 算 法 步 骤 单 纯 形 表 算 例 初 始 单 纯 形 表 迭 代 1 迭 代 2 初 始 解 两阶段法 大M法 计 算 软 件 LinDo LinGo Matlab 人力资源分配问题 某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？ 模 型 假 设 每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时间； 每天安排的人员数不得低于需求量，但可以超过需求量 问 题 分 析 因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用； 方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。 变量：每天开始休息的人数 约束条件 ： 1.每人休息时间2天，自然满足。 2. 每天工作人数不低于需求量，第i天工作的人数就是除第i天和第i-1天休息的人外，其余5天休息的人数之和，如星期一工作的人应是星期二至六休息的人数之和，所以有约束： 目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于 模 型 注 解 该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。 配 料 问 题 某化工厂要用三种原料混合配置 三种不同规格的产品，各产品的规格 单价如表1， 问如何安排生产使得生产利润最大？ 配 料 问 题 案 例 问题 问题分析 模型 求解和结果分析（省略） 问 题 分 析 变量 约束条件 目标函数 变 量 生产计划就是要确定每天生产三种产品的数量以及三种产品中三种原料的数量。而由于每种产品的数量等于三种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料数，设用于生产第 i 种产品的第 j 种原料数为 约 束 条 件 规格约束 约 束 条 件 资源约束 目标函数 模 型 25 35 50 单价（元/公斤） 不限 原料Ⅰ不少于25% 原料Ⅱ不超过50% 原料Ⅰ不少于50% 原料Ⅱ不超过25% 规格 C B A 产品 35 25 65 单价(元/公斤) 60 100 100 日最大供应量 Ⅲ Ⅱ Ⅰ 原料 原料的单价与每天最大供应量如表2 19 七 18 六 16 五 14 四 12 三 15 二 12 一 人数 星期 3.变量非负约束： 第*页 第*页 刘建州，实用数学建模教程， 武汉理工大学出版社，武汉，2003年 胡运权