教案_目标规划_上课.ppt

运筹学 讲课教师 汤建影 南京航空航天大学经济与管理学院 第二章目标规划 2 1目标规划的数学模型目标规划的基本概念目标规划的数学模型目标的优先级问题2 2目标规划的单纯形法目标规划单纯形法的特点目标规划的单纯形法目标规划单纯形法的要点 目标规划的基本概念目标规划的分类目标规划的数学模型举例目标规划问题的图解法 2 1目标规划的数学模型 目标规划的基本概念 在管理实践中 常常遇到 不可能都实现的目标线性规划所讨论的问题只涉及一个目标而目标规划中 预期实现的目标不止一个这些目标可能都实现 也可能只实现部分相互矛盾的约束条件可行域为空集目标规划 是在给定的资源条件下 按所规定的若干目标值及实现这些目标的先后顺序 求总的偏差为最小的方案 即尽可能地接近预期目标 例如 约束条件矛盾 可行域为空 的情况 处理的办法 将一些约束条件 例如后两个 看成是管理目标 使其尽可能达到为目标函数确定一个目标值A 力求使目标函数值不小于A定义目标偏差变量目标函数改为 目标规划的分类 I 单目标规划只有一个预期达到的目标与线性规划模型相似 都是单一目标 不同之处在于 线性规划是在满足约束条件的前提下 使一个目标函数达到极大 小 值 而目标规划是找一个尽可能接近预期目标的解 例 最优生产计划 某工厂生产A B两种产品 有关数据如下 求最优生产方案 建模 最优解x1 12 x2 6 目标函数值Z 132 换一个思路 如果计划部门要求实现目标利润为140万元目标函数变成了约束条件预期目标带有一定的主观性 因此最终实现的目标与此之间会有一定的偏差 超出的偏差用 不足用表示 分别称为正偏差变量和负偏差变量 正负偏差变量至少有一个为零 从决策者的角度看 他希望超过利润目标值 若达不到 也希望尽可能接近 即负偏差最小 建模 X1 12 x2 6 d 8 即可获利润比预定的目标少8元 目标约束 绝对约束 目标规划的分类 II 级别相等的多目标规划上例 假设决策者根据市场预测 产品A的销售量有下降的趋势 故考虑实现下列两个目标 1 实现利润目标122万元 2 产品A的产量不多于10 分析 两个目标级别相等 即两个目标的重要程度一样 不存在谁优先的问题设分别为超过目标值的部分 以及未完成目标值的部分 于是两个目标可以等价地表示为 建模 X1 10 x2 7 d 1 0 d 2 0 利润为122 两个目标均已经实现 目标规划的分类 III 具有优先级别的多目标规划对于多个目标 如果有一定的优先顺序 即第一位重要的目标 其优先因子为P1 第二位重要的目标 其优先因子为P2 并规定P1 P2优先保证P1级目标的实现 此时不考虑次级目标 次级目标 P2 在实现了P1级目标的基础上再予以考虑 如果无法实现P1目标 则不考虑P2目标能否取得最优若有k个不同优先顺序的目标 则有P1 P2 Pk 将权重与偏差相乘构成目标函数 这样 权重越大 越先迫使相应的偏差等于零 这样可保证优先级高的目标首先实现 例 上例中 决策者拟订下列经营目标 并确定了目标之间的优先顺序P1级目标 充分利用设备有效台时 不加班 P2级目标 产品B的产量不多于4 P3级目标 实现利润值130万元 分析与建模 设分别为超过目标值的部分 以及未完成目标值的部分 根据决策者的要求 建立数学模型 目标规划的数学模型 某线性规划有m个目标函数令其偏差变量 可正可负 正 负偏差 可令这表明正 负偏差都是非负的变量 并且它们不能同时不为零 即至少有一个等于零 其它情况的处理 若给定目标不是等于 而是大于等于或小于等于 则偏差分别只取负偏差或正偏差 例如若则约束条件而目标函数则为 关于偏差的讨论 技巧 要求恰好实现规定的第i个目标 这时构造的目标是要求超额完成规定第i个目标 超过多少可以不计较 可以构造的目标是要求不得超过规定的第i个目标 这时构造的目标是 目标规划模型 不考虑优先级与绝对约束 一般目标规划模型 考虑优先级与绝对约束 教材例1 1的目标规划 对于例1 1 若汽车生产厂要求利润达到2600千元 则对应的目标规划为 s t 例1 1要求尽可能保证有效工时2500小时 s t 例1 1的目标优先级安排 目标如下 优先级顺次降低 总利润为2600千元大轿车的产量不超过300辆保证有效工时2500小时充分利用 避免开工不足钢材的消耗量不要超过库存量 相应的数学模型 s t 目标规划的图解法 习题 P 263 习题3 4 不求解 第二节目标规划的单纯形法 目标规划单纯形法的特点目标规划的单纯形法目标规划单纯形法的要点 一 目标规划单纯形法的特点 目标函数中只有偏差变量 且求它们的和最小目标函数中 价值系数 一般为优先级的权重 因此检验数不是一行 而是m行 m个目标约束 在m行检验数中 从上到下 按优先级从高到低的顺序排列 求解时 首先满足优先级高的变量 二 目标规划的单纯形法 例1 求解以下目标规划问题 板书 复习 最优性判定规则 目标函数极性最优性判断规则入基变量选择标准 x1 x2 l1 l2 O C B A l3 D l4 1 l1与l2形成的可行域OABC 2 先满足P1 OD线段 E 3 再满足P2 ED线段 满意解 E 500 11 500 11 D 360 7 360 7 150 50 100 50 100 150 例3 求解以下目标规划 x1 x2 O 2 4 6 8 10 2 4 6 8 10 l1 l2 l3 A B 1 绝对约束 ABO C D 2 P1 线段CD E 3 P2 线段CE 满意解 CE线段C 0 5 2 E 0 6 4 7 三 目标规划单纯形法的要点 约束方程中的负偏差为初始基变量 检验数在单纯形表中以矩阵形式表达 占有m行 且按优先级顺序排列 选择换入变量时