第四章-目标规划

第四章目标规划 一 目标规划问题及其数学模型二 目标规划的图解法三 解目标规划的单纯形法 一 目标规划问题的提出 例1 某工厂生产两种产品 受到原材料供应和设备工时的限制 在单件利润等有关数据已知的条件下 要求制定获利最大的生产计划 解得 最优生产计划为 x1 8件 x2 2件 maxz 64元 一 目标规划问题的提出 1 单目标最优化 不能满足多方面的要求 2 线性规划有最优解的必要条件是其可行解集非空 即各约束条件必须彼此相容 但现实中各约束条件有可能产生冲突 3 线性规划模型是对现实问题的一种近似 它提供严格的数字 无法为决策者提供进一步的参考 线性规划中的问题 例2 建议 假设在例1的基础上 计划人员还被要求考虑如下的意见 1 由于产品II销售疲软 希望产品II的产量不超过产品I的一半 2 原材料严重短缺 生产中应避免过量消耗 3 最好能节约4小时设备工时 4 计划利润不少于48元 目标规划是一种在考虑多方面目标和决策要求 约束条件 冲突的基础上 根据目标优先级确定其满足的先后顺序 并求出满意区域为决策者提供多种计划方案的规划问题 目标规划的定义 1 偏差变量对每一个决策目标 引入正 负偏差变量d 和d d 决策值超过目标值的部分 d 决策值未达到目标值的部分 d 0和d 0d d 0 目标规划中涉及的概念 D d Z D d Z 2 绝对约束和目标约束绝对约束 必须严格满足的等式或不等式约束 目标约束 目标规划所特有的约束 约束右端项看作要追求的目标值 在达到目标值时 允许发生正或负的偏差 绝对约束是硬约束 目标约束是一种软约束 目标约束中决策值和目标值之间的差异用偏差变量表示 必为等式 目标规划中涉及的概念 3 优先因子和权系数不同目标的主次轻重有两种差别 一种差别是绝对的 可用优先因子Pt来表示 优先因子间的关系为Pt Pt 1 即Pt对应的目标比Pt 1对应的目标有绝对的优先性 另一种差别是相对的 这些目标具有相同的优先因子 它们的重要程度可用权系数Wi的不同来表示 目标规划中涉及的概念 4 目标规划的目标函数目标规划的目标函数 又称为准则函数或达成函数 由各目标约束的偏差变量及相应的优先因子和权系数构成 其目标函数只能是极小化 目标规划中涉及的概念 4 目标规划的目标函数有三种基本表达式 1 要求恰好达到目标值 min f d d 2 要求不超过目标值 但允许不足目标值 min f d 3 要求不低于目标值 但允许超过目标值 min f d 其他 min f d d min f d d 目标规划中涉及的概念 目标规划的数学模型 小结 1 约束条件 硬约束 绝对约束 软约束 目标约束 引入d d 2 目标优先级 P1 P2 PL同一级中可以有若干个目标 P21 P22 P23 其重要程度用权重系数W21 W22 W23 表示 3 目标函数 1 恰好达到目标 minZ f d d 2 超过目标 minZ f d 3 不超过目标 minZ f d 一般模型 4 目标规划 求一组决策变量的满意值 使决策结果与给定目标总偏差最小 Z 0 各级目标均已达到Z 0 部分目标未达到 目标函数中只有偏差变量 目标函数总是求偏差变量最小 建模步骤 1 设定约束条件 目标约束 绝对约束 2 规定目标约束优先级 3 建立模型 目标规划的数学模型 例2 目标规划的数学模型 最优生产计划为 x1 8件 x2 2件 maxz 64元 假设在例1的基础上 计划人员还被要求考虑如下的意见 1 由于产品II销售疲软 希望产品II的产量不超过产品I的一半 2 原材料严重短缺 生产中应避免过量消耗 3 最好能节约4小时设备工时 4 计划利润不少于48元 最后达成了一致意见 目标 1 首先原材料使用限额不得突破 2 其次要求考虑产品II产量问题 3 再次考虑设备工时问题 节约4个 4 最后考虑计划利润的要求 目标规划的数学模型 目标规划的数学模型 绝对约束 目标约束 目标约束 目标约束 1 原材料严重短缺 生产中应避免过量消耗 2 由于产品II销售疲软 希望产品II的产量不超过产品I的一半 3 最好能节约4小时设备工时 4 计划利润不少于48元 1 原材料严重短缺 生产中应避免过量消耗 2 由于产品II销售疲软 希望产品II的产量不超过产品I的一半 3 最好能节约4小时设备工时 4 计划利润不少于48元 目标规划模型的约束条件 x1 x2 di di 0di di 0i 1 2 3 目标规划的数学模型 min P1d1 P2d2 P3d3 目标规划模型目标函数 目标规划的数学模型 目标规划模型 例1 某企业生产甲 乙两种产品 受到金工 装配工时的限制 在单件收益已知的条件下 制订获利最大的生产计划 x 50 100 Z 13000 dP 去年总收益9000 今年要求增长11 1 即 今年希望总收益不低于10000 分析 只有一个目标约束 引入d 决策超过目标值部分 正偏差变量 d 决策不足目标值部分 负偏差变量 目标函数 minZ d 例2 1 原材料价格上涨 超计划要高价购买 所以要严格控制 2 市场情况 产品 销售量下降 产品 的产量不大于产品 的产量 3 充分利用设备 不希望加班 4 尽可能达到并超过利润计划指标56千元 绝对约束 目标约束 目标约束 目标约束 2x1 x2 11 x1 x2 x1 x2 d1 d1 0 x1 2x2 d2 d2 10 8x1 10 x2 d3 d3 56 x1 2x2 10 8x1 10 x2 56 minZ1 d1 minZ2 d2 d2 minZ3 d3 d1 x1产量不足x2部分d1 x1产量超过x2部分d2 设备使用不足10部分d2 设备使用超过10部分d3 利润不足56部分d3 利润超过56部分 设x1 x2为产品 产品 产量 目标函数minZ1 d1 minZ2 d2 d2 minZ3 d3 或minZ P1d1 P2 d2 d2 P3 d3 min P1d1 P2 d2 d2 P3 d3 电视机厂装配25和21寸两种彩电 每台电视机需装备时间1小时 每周装配线计划开动40小时 预计每周25寸彩电销售24台 每台可获利80元 每周21寸彩电销售30台 每台可获利40元 练习 该厂目标 1 充分利用装配线 避免开工不足 2 允许装配线加班 但尽量不超过10小时 3 尽量满足市场需求 设x1 x2分别表示25寸 21寸彩电产量 minZ P1d1 P2d2 P3 d3 d4 x1 x2 d1 d1 40 x1 x2 d2 d2 50 x1 d3 d3 24x2 d4 d4 30 x1 x2 di di 0 i 1 2 3 4 解 例1 二 目标规划的图解法 B C E minZ d 绝对约束可行域 目标约束满意域 1 绝对约束可行域OBEC 2 目标约束满意域CBE 3 多个可行满意解 B 100 0 10000 C 0 125 10000 E 50 100 13000 4 Zmin 0解为 1 100 0 2 0 125 3 50 1000 1 2 3 1 例2 用图解法求解 4 3 问题的解为 线段DE 例3 minZ P1d1 P2 d2 d2 P3 d3 d2 d1 d3 练习 作业 minZ P1d1 P2d2 P3 2d3 d4 x1 x2 d1 d1 40 x1 x2 d2 d2 50 x1 d3 d3 24 x2 d4 d4 30 二 目标规划的单纯形法 1 目标规划属于线性规划 2 目标规划的数学模型求目标函数最小化 3 检验数是各优先因子的线性组合 4 在判断检验数的正负和大小时 优先因子P1 P2 P3 解的情况 1 按最小负值规则确定换入变量 当存在两个及两个以上相同的最小负值时 选取具有较低级别的变量为换入变量 2 按最小比值规则确定换出变量 当存在两个及两个以上相同的最小比值时 选取具有较高级别的变量为换出变量 3 当出现非基变量检验数为零时 出现多重满意解 目标函数的解就是多重满意解所组成的凸组合 4 目标规划的最终单纯形表中 允许较低级别变量的优先因子系数为负值 这说明该规划问题的目标并未完全实现 例1 min P1d1 P2d2 P3d3 解 min P1d1 P2d2 P3d3 化标准形 列初始单纯形表 0 0 0 0 8 6 0 2 1 满意解x1 24 5 x2 12 5 满意解x1 8 x2 0 满意解x1 6 x2 3 满意解x1 9 x2 0 所以 满意解为四点所组成的凸组合 1 24 5 12 5 2 8 0 3 6 3 4 9 0 1 2 3 4 1 例2 解 列初始单纯形表 计算检验数值 检验P1行是否存在负数 检验P2行是否存在负数 检验P3行是否存在负数 所以 原问题的解为 x1 24 x2 26 d4 4 P3行中负数对应的前2行系数是否为0 minZ P1d1 P2d2 P3 2d3 d4 所以市场需求没有满足 X2 d4 d4 30 每周14寸彩电只生产26台 作业 1 红星制药厂生产A B两种药品 有关数据如