《运筹学课件02线性规划》课件.pptVIP

命 令 5 [x1,crit]=karmarkar(a,b,c,x0) 问题形式 min c*x s.t. a*x = b x=0 注 意 事 项 命令2和3中x0可省略，但命令4和5中不可省略 向量都是列向量，参数的顺序不可换 命令3中等式约束必须在前面 人力资源分配问题 某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？ 星期 一 二 三 四 五 六 七 人数 12 15 12 14 16 18 19 模 型 假 设 每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时间； 每天安排的人员数不得低于需求量，但可以超过需求量 问 题 分 析 因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用； 方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。 变量：每天开始休息的人数 约束条件 ： 1.每人休息时间2天，自然满足。 2. 每天工作人数不低于需求量，第i天工作的人数就是从第i-2天往前数5天内开始工作的人数，所以有约束： 3.变量非负约束： 目标函数：总费用最小，总费用与使 用的总人数成正比。由于每个人必然在 且仅在某一天开始休息，所以总人数等 于 模 型 计 算 注 解 该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。 定义整数变量用函数@gin(x1)…… @gin(x7); 0-1整数变量为@bin(x1) 配 料 问 题 某化工厂要用三中原料混合配置 三种不同规格的产品各产品的规格 单价如表1， 产品 规格 单价（元/公斤） A 原料Ⅰ不少于50% 原料Ⅱ不超过25% 50 B 原料Ⅰ不少于25% 原料Ⅱ不超过50% 35 C 不限 25 问如何安排生产使得生产利润最大？ 原料 日最大供应量 单价(元/公斤) Ⅰ 100 65 Ⅱ 100 25 Ⅲ 60 35 原料的单价与每天最大供应量如表2 配 料 问 题 案 例 问题 问题分析 模型 求解 结果分析 问 题 分 析 变量 约束条件 目标函数 变 量 生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量。而由于每种产品的数量等于三种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料数，设用于生产第 i 种产品的第 j 种原料数为 约 束 条 件 规格约束 资源约束 约 束 条 件 目标函数 总产值 总成本 总利润=总产值-总成本 模 型 求 解 谢谢！ 概 况 信息的不确定性 信息的变化： 价值向量—市场变化 右端向量—资源变化 系数矩阵—技术进步 认知的误差 分析方法 静态分析- 比较静态分析-动态分析 改变价值向量 一般改变情况 改变非基变量的价值向量 改变基变量的价值向量 算例 一 般 改 变 非 基 变 量 基 变 量 算 例 改变右端向量 基本思想 算例 基 本 思 想 算 例 计 算 软 件 LinDo LinGo Matlab LinDo 输入模型 求解 点击求解按钮 即可 结果 输 入 模 型 !注释内容，可用中文 !目标函数：最大-max,最小-min,大小写不分 max 3 x1+5 x2+4 x3 !约束，以subject to开始 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2 +5 x3=2000 end 注 意 事 项 变量以字母开头，下标写在后面，系数与边量之间加空格 不等号为:= ( ),=( ) , =, =与 等同 变量非负约束可省略 结束时以end标示 结 果 LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1)