线 性 规 划幻灯片.ppt_第1页
线 性 规 划幻灯片.ppt_第2页
线 性 规 划幻灯片.ppt_第3页
线 性 规 划幻灯片.ppt_第4页
线 性 规 划幻灯片.ppt_第5页
已阅读5页,还剩141页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

LinearProgramming 运筹学课件 线性规划 线性规划问题可行区域与基本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析 线性规划问题 线性规划实例生产计划问题运输问题线性规划模型一般形式规范形式标准形式形式转换概念 某工厂用三种原料生产三种产品 已知的条件如表2 1 1所示 试制订总利润最大的生产计划 生产计划问题 问题分析 模型 计算结果 运输问题 问题分析 模型 一般形式 目标函数 约束条件 注释 规范形式 标准形式 概念 模型转换 约束转换实例 目标转换 变量转换 约束转换 不等式变等式不等式变不等式 等式变不等式 不等式变等式 松弛变量 剩余变量 不等式变不等式 例2 1 3把问题转化为标准形式 可行区域与基本可行解 图解法可行域的几何结构基本可行解与基本定理 图解法 例2 2 1解线性规划 注释 可能出现的情况 可行域是空集可行域无界无最优解最优解存在且唯一 则一定在顶点上达到最优解存在且不唯一 一定存在顶点是最优解 可行域的几何结构 基本假设凸集可行域的凸性 基本假设 凸集 可行域的凸性 问题 基本可行解与基本定理 定义基本定理问题 基本可行解定义 基本定理 问题 单纯形算法 理论方法算法步骤单纯形表算例 理论方法 定理2 3 1 定理2 3 2 定理2 3 3 算法步骤 单纯形表 算例 初始单纯形表 迭代1 迭代2 初始解 两阶段法大M法说明 两阶段法 基本思想第一阶段 通过求解辅助问题的最优基可行解得到原问题的初始基可行解 第二阶段 求原问题的最优解算例 辅助问题 原辅助题问与题的关系 求辅助问题的三种情况 算例 第1阶段 第1阶段 第1阶段 第1阶段 第1阶段 第2阶段 大M法 说明 对偶理论 对偶规划对偶理论对偶单纯形算法 对偶规划 标准形式线性规划的对偶规划规范形式线性规划的对偶规划一般形式线性规划的对偶规划实例 标准形式的对偶规划 规范形式的对偶规划 一般形式的对偶规划 实例 对偶理论 定理2 5 1 定理2 5 2 定理2 5 5 对偶单纯形算法 基本思想算法过程算例 基本思想 单纯形算法 对偶单纯形 正则解 正则解 对偶可行解 正则解的单纯性表 规划无可行解 保持正则性 入基变量 否 算法过程 初始正则解 是则停止 得最优解 选出基变量 检查是否无可行解 是则停止 否 无最优解 选入基变量 计算典式检验数 算例 迭代 迭代 迭代 灵敏度分析 概况改变价值向量改变右端向量 概况 信息的不确定性信息的变化 价值向量 市场变化右端向量 资源变化系数矩阵 技术进步认知的误差分析方法静态分析 比较静态分析 动态分析 改变价值向量 一般改变情况改变非基变量的价值向量改变基变量的价值向量算例 一般改变 非基变量 基变量 算例 改变右端向量 基本思想算例 基本思想 算例 计算软件 LinDoLinGoMatlab LinDo 输入模型求解点击求解按钮即可结果 输入模型 注释内容 可用中文 目标函数 最大 max 最小 min 大小写不分max3x1 5x2 4x3 约束 以subjectto开始subjectto2x1 3x2 15002x2 4x3 8003x1 2x2 5x3 2000end 注意事项 变量以字母开头 下标写在后面 系数与边量之间加空格不等号为 与 等同变量非负约束可省略结束时以end标示 结果 LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1 2675 000VARIABLEVALUEREDUCEDCOSTX1375 0000000 000000X2250 0000000 000000X375 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000001 0500003 0 0000000 6250004 0 0000000 300000 LinGo 输入模型LinDo模式LinGo模式求解点击求解按钮即可结果 LinDo输入模式 model MAX 3 x1 5 x2 4 x3 2 x1 3 x2 1500 2 x2 4 x3 800 3 x1 2 x2 5 x3 2000 end 注意与LinDo的区别 目标函数中加等号变量与系数之间用 Model end可省略 LinGo模式 集合部分 model 开始sets 定义集合ve 1 3 c x co 1 3 b ma co ve a endsets 注 集表达式 名称 成员 属性名称 初始集 属性 定义数据 data 定义数据c 354 ba 230024325 Enddata 注 数据的大小与集合定义中一致 分量中间用空格或逗号分开 数据结束后用分号 调用函数 max sum ve j c j x j for co i sum ve j a i j x j b i 主要函数 for set set index list condition expression sum set set index list condition expression min max set set index list condition expression 结果 Globaloptimalsolutionfoundatiteration 3Objectivevalue 2675 000VariableValueReducedCostC 1 3 0000000 000000C 2 5 0000000 000000C 3 4 0000000 000000X 1 375 00000 000000X 2 250 00000 000000X 3 75 000000 000000 B 1 1500 0000 000000B 2 800 00000 000000B 3 2000 0000 000000A 1 1 2 0000000 000000A 1 2 3 0000000 000000A 1 3 0 0000000 000000A 2 1 0 0000000 000000A 2 2 2 0000000 000000A 2 3 4 0000000 000000A 3 1 3 0000000 000000A 3 2 2 0000000 000000A 3 3 5 0000000 000000 RowSlackorSurplusDualPrice12675 0001 00000020 0000001 05000030 0000000 625000040 0000000 3000000 Scilab函数 命令1 x lagr f linpro p C b x0 命令2 x lagr f linpro p C b ci cs x0 命令3 x lagr f linpro p C b ci cs me x0 命令4 x lagr f linpro p C b ci cs me x0 imp 命令5 x1 crit karmarkar a b c x0 注意事项 命令1 问题形式minp xs t C x b x lagr f linpro p C b x0 命令2 命令3 命令4 x lagr f linpro p C b ci cs me x0 imp 问题形式minp xs t C j x b j j 1 meC j x b j j me 1 me mdci x cs指定初始可行解x0 命令5 x1 crit karmarkar a b c x0 问题形式minc xs t a x bx 0 注意事项 命令2和3中x0可省略 但命令4和5中不可省略向量都是列向量 参数的顺序不可换命令3中等式约束必须在前面 人力资源分配问题 某个中型百货商场对售货人员 周工资200元 的需求经统计如下表为了保证销售人员充分休息 销售人员每周工作5天 休息2天 问应如何安排销售人员的工作时间 使得所配售货人员的总费用最小 模型假设 每天工作8小时 不考虑夜班的情况 每个人的休息时间为连续的两天时间 每天安排的人员数不得低于需求量 但可以超过需求量 问题分析 因素 不可变因素 需求量 休息时间 单位费用 可变因素 安排的人数 每人工作的时间 总费用 方案 确定每天工作的人数 由于连续休息2天 当确定每个人开始休息的时间就等于知道工作的时间 因而确定每天开始休息的人数就知道每天开始工作的人数 从而求出每天工作的人数 变量 每天开始休息的人数约束条件 1 每人休息时间2天 自然满足 2 每天工作人数不低于需求量 第i天工作的人数就是从第i 2天往前数5天内开始工作的人数 所以有约束 3 变量非负约束 目标函数 总费用最小 总费用与使用的总人数成正比 由于每个人必然在且仅在某一天开始休息 所以总人数等于 模型 计算 注解 该问题本质上是个整数规划问题 放松的线性规划的最优解是个整数解 所以两规划等价 定义整数变量用函数 gin x1 gin x7 0 1整数变量为 bin x1 配料问题 某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表1 问如何安排生产使得生产利润最大 原料的单价与每天最大供应量如表2 配料问题案例 问题问题分析

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论