ch4 目标规划.ppt

第4章目标规划 书上引例 某工厂生产A B两种产品 有关数据如下 用线性规划求解 第四章 目标规划及其图解法 1 求利润最大的决策是产品A生产4产品B生产3利用线性规划求出 总利润为62万元这时原材料用完 设备剩余2小时实际中 决策时不只考虑利润最大 还要考虑市场等一系列条件 例如 1 根据市场信息 产品A的需求有下降的趋势 因此考虑产品A的产量不大于产品B的产量 2 超过计划供应的原材料时 需要用高价采购 使成本增加 3 尽可能利用设备 但不希望加班 4 尽可能达到并且超过利润指标56万元求 决策方案 第四章 目标规划及其图解法 1 例1 线性规划模型相关目标规划模型利润最大MaxZ 8x1 10 x2 原材料约束2x1 x2 0 难点1 建立模型中 目标函数偏差是正或者负 第四章 目标规划及其图解法 1 在此基础上考虑 1 产品 的产量不低于产品 的产量 2 充分利用设备有效台时 不加班 3 利润不小于56元 目标规划的基本概念 1 目标值和偏差变量目标值 决策者对每一个目标都有一个期望值 或称为理想值 正偏差变量 表示决策值 实现值 超过目标值的数量 记为di 如计划利润56元 实际值为60元 di 60 56 4 0此时超额完成指标di 0负偏差变量 表示决策值 实现值 未达到目标值的数量 记为di 如计划利润56元 实际值为50元 di 56 50 5 0di 0显然 di di 0 di di 0 2 目标约束和绝对约束绝对约束是指必须严格满足的等式约束和不等式约束 如线性规划问题的所有约束条件 不能满足这些约束条件的解称为非可行解 所以它们是硬约束 目标约束是目标规划特有的 可把约束右端看作要追求的目标值 在达到此目标值时允许发生正或负偏差 如何写目标约束 对每个原始目标表达式 或是等式 不等式 其右端为理想值 的左端都加上负偏差变量 减去正偏差变量后 变换为等式 即目标约束 3 优先因子 优先等级 与权系数一个多目标决策问题中 常有多个目标 这些目标是有主次或轻重缓急的不同 根据重要程度赋予优先因子 表示比有更大的优先权 通常 k值越小 代表的优先程度越高 对相同优先因子的两个目标 赋予它们不同的权系数优先因子和全系数一般根据题目要求而定 5 目标规划问题的解 满意解目标规划问题的求解是分级进行的 首先求满足级目标的解 然后在保证级目标不被破坏的前提下再求满足级目标的解 以此类推 因此 这样最后求出的解就不是通常意义下的最优解 称之为满意解 因为对于这种解来说 前面的目标是可以保证实现或部分实现的 后面的目标就不一定能保证实现或部分实现 有些可能就不能实现 满意解这一概念的提出是对最优化概念的一个突破 显然它更切合实际 更便于运用 4 目标规划的目标函数目标规划的目标函数 是由各目标约束的偏差变量及相应的优先因子和权系数构成 当一个目标规划确定后决策者的要求是尽可能接近各既定目标值 也就是偏差变量尽可能小 目标函数一定是极小化的 三种基本表达式 1 要求恰好达到目标值 这时决策值超过或低于目标值都是不希望的 因此有 2 要求不超过目标值 即允许达不到目标值 就是正偏差变量要尽可能地小 因此有 3 要求不低于目标值 即允许超过目标值 就是负偏差变量要尽可能地小 因此有 目标规划的数学模型一般形式 LP与GP的比较 d1 d1 X1 X2 1 0 X1 X2 d1 1 X1 X2 0 难点2 图解方法中 方向偏差是正或者负X1 X2 0X1 X2 1 0判断d1 方向判断d1 方向 第四章 目标规划及其图解法 1 如何表示x1 x2 d1 d1 0 d2 1 X1 2X2 1 0 X1 X2 5 10 X1 2X2 1 1 0 d2 d2 第四章 目标规划及其图解法 1 如何表示x1 2x2 1 d2 d2 0 P104例3 某电视机厂装配黑白和彩色两种电视机 每装配一台电视机需要占用装配线一小时 装配线每周计划开动40小时 预测每周黑白和彩色电视机的销售量各是30台和24台 黑白和彩色电视机每台利润40元和80元 该厂确定的目标 第1优先级 充分利用装配线 每周计划开动40小时第2优先级 允许装配线加班 加班时间每周尽量不超过10小时第3优先级 装配电视机尽量满足市场需要 因为彩色电视机利润更高 权系数为2 第四章 目标规划及其图解法 1 x1 x2 d1 d1 40 x1 x2 d2 d2 50 x1 d3 d3 24x2 d4 d4 30 xi 0 di d I 0 第四章 目标规划及其图解法 1 分析约束条件某电视机厂装配黑白和彩色两种电视机 每装配一台电视机需要占用装配线一小时 装配线每周计划开动40小时 预测每周黑白和彩色电视机的销售量各是30台和24台 黑白和彩色电视机每台利润40元和80元 该厂确定的目标 第1优先级 充分利用装配线 每周计划开动40小时第2优先级 允许装配线加班 加班时间每周尽量不超过10小时第3优先级 装配电视机尽量满足市场需要 因为彩色电视机利润更高 权系数为2 Minz Min P1d1 P2d2 P3 2d3 d4 x1 x2 d1 d1 40 x1 x2 d2 d2 50 x1 d3 d3 24x2 d4 d4 30 xi 0 di d i 0 第四章 目标规划及其图解法 1 分析目标函数第1优先级 充分利用装配线 每周计划开动40小时第2优先级 允许装配线加班 加班时间每周尽量不超过10小时第3优先级 装配电视机尽量满足市场需要 因为彩色电视机利润更高 权系数为2 d3 0 30 24 d4 d4 P104例3电视生产 d3 d2 0 d1 0 彩电X1 X2黑白 50 0 40 40 难点3 图解方法中 判断解 Min P1d1 P2d2 P3 2d3 d4 第四章 目标规划及其图解法 1 A B C D E F G H d1 解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别 所以可用单纯形法求解 但由于目标规划数学模型的一些特点 故要注意以下两点 1 因目标规划问题的目标函数都是求最小化 所以其最优准则为检验数 0j 1 2 n 2 因非基变量的检验数是各优先因子的线性组合 即j 1 2 n k 1 2 K所以在判别各检验数的正负及大小时 必须注意 设即的正负由的正负所决定 解目标规划问题的单纯形法的计算步骤 1 建立目标规划模型的初始单纯形表 在表中将检验数行按优先因子个数分别列成K行 设k 1 2 检验第k行检验数中是否存在负数 若有负数 且有些负数对应的前k 1行的检验数为零 则取这些负数中的最小者对应的变量为换入基变量转3 否则 即所有这些负数对应的前k 1行的检验数中都有大于零的数 此时 说明这些负数对应的检验数已为正数 转5 若无负数 说明在前k级中非零检验数对应的变量不需要换入基变量了 转5 3 按最小比值规划确定换出基变量 当存在两个和两个以上相同的最小比值时 选取具有较高优先级别的变量为换出变量 4 按单纯形法进行基变换运算 建立新的单纯形表 转2 5 当k K时 计算结束 表中的解即为满意解 否则设k k 1 转2 上例 某工厂生产A B两种产品 有关数据如下 用线性规划求解 第四章 目标规划单纯形法 P103例2目标规划单纯形法 实际中 决策时考虑利润市场等一系列条件 1 根据市场信息 产品A的需求有下降的趋势 因此考虑产品A的产量不大于产品B的产量 2 尽可能利用设备 但不希望加班 3 尽可能达到并且超过利润指标56万元求 决策方案 第四章 目标规划单纯形法 P103例2目标规划单纯形法 Minz p1d1 p2 d2 d2 p3d3 2x1 x2 Xs 11x1 x2 d1 d1 0 x1 2x2 d2 d2 108x1 10 x2 d3 d3 56xi 0 di d I 0 P106例目标规划单纯形法 第四章 目标规划单纯形法 如何得目标规划的第1张单纯形表 检验数 C2 CBB 1P2B 1 I C2 CBB 1P2 0 00P2P3 1 1210 T 2P2 10P3 B 1 I 直接找到单位矩阵 Minz p1d1 p2 d2 d2 p3d3 第四章 目标规划单纯形法 单纯形法 先定列 降成本 负中取小 再定行 相除后正中取小 转元所在列化为单位向量 对第1张单纯形表 如何寻找第一个转元 解目标规划的单纯形法 P105 C7 CBB 1P7 P2 000P3 1 2 1 2 1 25 T P2 5P3 单纯形法 降成本 负中取小 注 d2 的检验数为正 相除后正中取小 CB 转元所在列化为单位向量 第四章 目标规划单纯形法 解目标规划的单纯形法 P107 非基变量检验数为零对应无数最优解 单纯形法 最优解 X1 2 X2 4 Xs 3 d1 2 第四章 目标规划单纯形法 解目标规划的单纯形法 P107 单纯形法 最优解X1 10 3 X2 10 3 Xs 1 d3 4 非基变量检验数为零对应无数最优解 d1 d3 对换 第四章 目标规划单纯形法 灵敏度分析 优先级改变 107 优先彩电优先黑白 优先级改变目标函数改变 C改变CB改变 单纯形表中检验数CN CBB 1N改变 优先级改变单纯形表中检验数改变 第四章 目标规划单纯形法 灵敏度分析 优先级改变 107 Minz p1 2d1 3d1 p2d3 p3d4 优先级改变为Minz p1d3 p2 2d1 3d2 p3d4 x1 x2 d1 d1 10 x1 d2 d2 45x1 3x2 d3 d3 56x1 x2 d4 d4 12xi 0 di d I 0系数矩阵中有一个矩阵单位 优先级改变目标函数改变C改变CB改变 单纯形表中检验数CN CBB 1N改变 第四章 目标规划单纯形法 第四章 目标规划单纯形法 C4 CBB 1P4 2P2 00P10 1031 T 3P1 2P2 单纯形法 降成本 负中取小 注 d1 的检验数负 相除后正中取小 转元所在列化为单位向量 单纯形法 最优解 X1 4 X2 12 转元所在列化为单位向量 第四章 目标规划单纯形法 第四章 目标规划应用 目标规划应用举例 P109 例6 调工资方案目标1不超过年工资总额60000元2每级人数不超过定编人数二三级升级面尽可能达到现有人数的20 4三级不足人数可以录取新工人 一级有10 要退休 解 设X1 X2 X3表示提升到一二级和录取到三级的新工人人数 第1目标 不超过年工资总额60000元 MinP1d1 2000 10 10 0 1 X1 1500 12 X1 X2 1000 15 X2 X3 d1 d1 60000d1 不足工资总额的数量d1 超过工资总额的数量 第四章 目标规划应用 3 第2目标 每级人数不超过定编人数 MinP2 d2 d3 d4 10 1 0 1 X1 d2 d2 1212 X1 X2 d3 d3 15 X2 X3 d4 d4 15d2 一级超过定编人数的数量d2 一级不足定编人数的数量 第四章 目标规划应用 3 第3目标 二三级升级面尽可能达到现有人数的20 提问题 MinP3 d5 d6 X1 d5 d5 12 0 2X2 d6 d6 15 0 2d5 二级升级面不足规定的数量d5 二级升级面超过规定的数量 答案P110注意偏差变量的经济含意 第四章 目标规划应用 3 升级面不超过20 升级面不超过20 尽可能多提 升级面尽可能正好20 第四章 目标规划应用 3 1 B4是重点保证单位 必须满足全部需求2 A3向B1提供产量不少于1003 每个销地的供应量不少于需求的80 4 总运费不超过最小运费的110 5 因为路问题 A2尽量不运到B46 B1 B3的供应率要相同7 总运输费用尽量少 p110例7 目标规划应用案例运输问题一个物流企业的老板正在考虑如下问题 有三个产地A1 A2 A3给四个销地B1 B2 B3 B4供应某种产品 已经知道需求量和运输价格 要考虑以下7个目标 第四章 目标规划应用 3 第四章 目标规划应用 3 已知 第四章 目标规划应用 3 首先把产销不平衡化为产销平衡 求解如下 250 150100 目标规划应用运输问题 P110例7 本例中供 需供 虚产地 需七个要求目标规划表达如下 第1目标 B4是重点单位 必须满足 第2目标 A3向B1提供产量不少于100 MinP2d5 X31 d51 d51 100 MinP1d4 X14 X24 X34 d4 d4 250 第四章 目标规划应用 3 第3目标 每个销地供应不少于需求的80 MinP3 d6 d7 d8 d9 X11 X21 X31 d6 d6 200 0 8X12 X22 X32 d7 d7 100 0 8X13 X23 X33 d8 d8 450 0 8X14 X24 X34 d9 d9 250 0 8 第四章 目标规划应用 3 第4目标 调运方案总费用不超过最小费用的10 第5目标 因为路问题 A2尽量不运到B4 MinP4 d10 MinP5 d11 第四章 目标规划应用 3 第6目标 B1B3的供应