线 性 规 划幻灯片.ppt

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 配料问题案例 问题问题分析