第5讲目标规划

1 1 目标规划的模型及求解 1学时 线性规划及目标规划软件求解 1学时 重点 目标规划模型 图解法 难点 目标规划模型建立 目标规划的软件求解 基本要求 掌握目标规划概念及模型建立 掌握目标规划的图解法 了解目标规划的单纯形法 掌握线性规划和目标规划的软件求解 第5讲目标规划 第2章 某厂计划在下一个生产周期内生产甲 乙两种产品 已知资料如表所示 试制定生产计划 使获得的利润最大 同时 根据市场预测 甲的销路不是太好 应尽可能少生产 乙的销路较好 可以扩大生产 试建立此问题的数学模型 引例 目标规划的模型及求解 2 1目标规划概述 设 甲产品x1 乙产品x2 一般有 maxZ 70 x1 120 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 同时 maxZ1 70 x1 120 x2minZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 显然 这是一个多目标规划问题 用线性规划方法很难找到最优解 目标值和偏差变量目标约束和绝对约束达成函数 即目标规划中的目标函数 优先因子 优先等级 与优先权系数满意解 具有层次意义的解 一 目标规划的基本概念 目标规划通过引入目标值和偏差变量 可以将目标函数转化为目标约束 目标值 是指预先给定的某个目标的一个期望值 实现值或决策值 是指当决策变量xj选定以后 目标函数的对应值 偏差变量 事先无法确定的未知数 是指实现值和目标值之间的差异 记为d 正偏差变量 表示实现值超过目标值的部分 记为d 负偏差变量 表示实现值未达到目标值的部分 记为d 1 目标值和偏差变量 当完成或超额完成规定的指标则表示 d 0 d 0当未完成规定的指标则表示 d 0 d 0当恰好完成指标时则表示 d 0 d 0 d d 0成立 引入了目标值和正 负偏差变量后 就对某一问题有了新的限制 既目标约束 目标约束即可对原目标函数起作用 也可对原约束起作用 目标约束是目标规划中特有的 是软约束 在一次决策中 实现值不可能既超过目标值又未达到目标值 故有d d 0 并规定d 0 d 0 2 目标约束和绝对约束 绝对约束 系统约束 是指必须严格满足的等式或不等式约束 如线性规划中的所有约束条件都是绝对约束 否则无可行解 所以 绝对约束是硬约束 例如 在引例中 规定Z1的目标值为50000 正 负偏差为d d 则目标函数可以转换为目标约束 既70 x1 120 x2 50000 同样 若规定Z2 200 Z3 250则有 若规定3600的钢材必须用完 原式9x1 4x2 3600则变为 maxZ1 70 x1 120 x2minZ2 x1maxZ3 x29x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 目标函数是一个使总偏差量为最小的目标函数 记为minZ f d d 一般说来 有以下三种情况 但只能出现其中之一 要求恰好达到规定的目标值 即正 负偏差变量要尽可能小 则minZ f d d 要求不超过目标值 即允许达不到目标值 也就是正偏差变量尽可能小 则minZ f d 要求超过目标值 即超过量不限 但不低于目标值 也就是负偏差变量尽可能小 则minZ f d 3 目标函数 优先因子Pk是将决策目标按其重要程度排序并表示出来 P1 P2 Pk Pk 1 PK k 1 2 K 权系数 k区别具有相同优先因子的两个目标的差别 决策者可视具体情况而定 对于这种解来说 前面的目标可以保证实现或部分实现 而后面的目标就不一定能保证实现或部分实现 有些可能就不能实现 4 优先因子 优先等级 与优先权系数 5 满意解 具有层次意义的解 某厂生产 两种产品 有关数据如表所示 经研究提出下列要求 1 产品 的产量不低于产品 的产量 2 充分利用设备有效台时 不加班 3 利润不小于56元 例1 二 目标规划的数学模型 解 设x1 x2分别表示产品 和产品 的产量 di di 分别为第i个目标的负 正偏差变量 建立目标约束 产品 的产量不低于产品 的产量 充分利用设备有效台时 不加班 利润不小于56元 原材料约束 优先等级 第一目标 即产品 的产量不大于 的产量 第二目标 即充分利用设备有效台时 不加班 第三目标 即利润不小于56元 达成函数 目标规划模型 若在引例中提出下列要求 1 完成或超额完成利润指标50000元 2 产品甲不超过200件 产品乙不低于250件 3 现有钢材3600吨必须用完 试建立目标规划模型 分析 目标约束与系统约束 例2 P170 x1 120 x2 50000P2x1 200P3x2 2509x1 4x2 36004x1 5x2 20003x1 10 x2 3000 x1 x2 0 解 设x1 x2分别表示产品甲和产品乙的产量 di di 分别为第i个目标的负 正偏差变量 优先等级 题目有三个目标层次 包含四个目标值 第一目标 第二目标 有两个要求即甲 乙 但两个具有相同的优先因子 因此需要确定权系数 本题可用单件利润比作为权系数即70 120 化简为7 12 第三目标 达成函数 目标规划模型为 目标规划模型一般形式 建模的步骤 1 根据要研究的问题所提出的各目标与条件 确定目标值 列出目标约束与绝对约束 4 对同一优先等级中的各偏差变量 若需要可按其重要程度的不同 赋予相应的权系数 3 给各目标赋予相应的优先因子Pk k 1 2 K 2 可根据决策者的需要 将某些或全部绝对约束转化为目标约束 这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可 5 根据决策者的要求 按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的 要求实现极小化的目标函数 即达成函数 恰好达到目标值 取 允许超过目标值 取 不允许超过目标值 取 1 19 目标规划是在线性规划的基础上 为适应经济管理中多目标决策的需要而逐步发展起来的一个分支 2 线性规划求最优解 目标规划是找到一个满意解 1 线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题 而目标规划是多个目标决策 可求得更切合实际的解 三 目标规划与线性规划的比较 1 20 4 线性规划的最优解是绝对意义下的最优 但需花去大量的人力 物力 财力才能得到 实际过程中 只要求得满意解 就能满足需要 或更能满足需要 3 线性规划中的约束条件是同等重要的 是硬约束 而目标规划中有轻重缓急和主次之分 即有优先权 目前 已经在经济计划 生产管理 经营管理 市场分析 财务管理等方面得到了广泛的应用 小结 适用范围 两个变量的目标规划问题 优点 操作简单有助于理解目标规划的求解原理和过程 2 2 1目标规划的图解法 2 2目标规划的求解方法 3对下一个优先级Pi求出解的区域 满足4重复3 直到所有优先等级的目标都已审查完毕为止 确定目标规划的满意解 图解法解题步骤如下 1画出约束条件的直线图形 包括绝对约束 对于目标约束暂不考虑正负偏差变量 确定绝对约束的围城的可行域 偏差变量以直线移动的方向加以考虑 即在目标约束所代表的直线上 用箭头标出正 负偏差变量值增大的方向 2对P1级目标 确定解的区域满足 例3 顾客访问策略 目标 访问时间最好不超过680小时 访问时间最好不少于600小时 销售利润尽量不少于70 000 访问老顾客数最好不少于200个 访问新顾客数最好不少于120个 模型 顾客访问策略 目标规划的图求解 序贯算法 第一级目标 第二级目标 第三级目标 第四级目标 第五级目标 1 32 某电视机厂装配黑白和彩色电视机 每装配一台电视机需占用装配线1小时 装配线每周计划开动40小时 预计市场每周彩色电视机的销量是24台 每台可获利80元 黑白电视机的销量是30台 每台可获利40元 该企业决策者确定的目标为 第一优先级 充分利用装配线每周计划开动40小时 第二优先级 允许装配线加班 但加班时间每周尽量不超过10小时 第三优先级 装配电视机的数量尽量满足市场需要 因彩色电视机的利润高 取其权数为2 试建立该问题的目标规划模型 并求解黑白和彩色电视机的产量 例4 书例2 5 1 33 A B C D E F H G E 24 26 为所求的满意解 解 设x1 x2分别表示彩色和黑白电视机的产量 1 34 0 12345678 123456 A x2 x1 B C B 0 6250 4 6875 C 0 5 2083 B C线段上的所有点均是该问题的解 无穷多最优解 例5 用图解法求解目标规划问题 例6 已知一个生产计划的线性规划模型为 其中目标函数为总利润 x1 x2为产品A B产量 现有下列目标 1 要求总利润必须超过2500元 2 考虑产品受市场影响 为避免积压 A B的生产量不超过60件和100件 3 由于甲资源供应比较紧张 不要超过现有量140 试建立目标规划模型 并用图解法求解 解 以产品A B的单件利润比2 5 1为权系数 模型如下 0 x2 0 x1 14012010080604020 20406080100 A B C D 结论 C 60 58 3 为所求的满意解 作图 检验 将上述结果带入模型 因 0 0 0 存在 0 存在 所以 有下式 minZ P3 将x1 60 x2 58 3带入约束条件 得 30 60 12 58 3 2499 6 2500 2 60 58 3 178 3 140 1 60 601 58 3 58 3 100 由上可知 若A B的计划产量为60件和58 3件时 所需甲资源数量将超过现有库存 在现有条件下 此解为非可行解 为此 企业必须采取措施降低A B产品对甲资源的消耗量 由原来的100 降至78 5 140 178 3 0 785 才能使生产方案 60 58 3 成为可行方案 应用举例 例7 人事问题 某单位领导在考虑本单位职工的升级调资方案时 依次遵守以下规定 1 不超过年工资总额60000元 2 每级的人数不超过定编规定的人数 3 II III级的升级面尽可能达到现有人数的20 且无越级提升 4 III级不足编制的人数可录用新职工 又I级职工中有10 要退休 有关资料汇总于下表 问该领导应如何拟订一个满意的方案 解 设x1 x2 x3分别表示提升I II级和录用到III级的新职工人数 di di 分别为第i个目标的负 正偏差变量 第一优先级P1 不超过年工资总额60000元 第二优先级P2 每级的人数不超过定编规定的人数 第三优先级P3 II III级的升级面尽可能达到现有人数的20 确定优先因子 建立目标约束 年工资总额不超过60000元 每级的人数不超过定编规定的人数 对I级有 对II级有 对III级有 II III级的升级面尽可能达到现有人数的20 达成函数 对II级有 对III级有 目标规划模型 用单纯形法求解得多重解 如下表 已知有三个产地给四个销地供应某种产品 产销地之间的供需量和单位运价见下表 有关部门在研究调运方案时依次考虑以下七项目标 并规定其相应的优先等级 P1 B4是重点保证单位 必须全部满足其需求 P2 A3向B1提供的产量不小于100 P3 每个销地的供应量不小于其需求量的80 P4 所定调运方案的总运费不超过最小运费调运方案的10 P5 因路段的问题 尽量避免安排将A2的产品运往B4 P6 给B1和B3的供应率要相同 P7 力求总运费最省 试求满意的调运方案 例8 运输问题 解 在不考虑优先等级的情况下 用表上作业法可求得最小运费的调运方案 再根据提出的目标要求建立目标规划模型 最小运费的调运方案 最小运费 2950元 供应约束 建立目标模型 需求约束 A3向B1提供的产量不小于100 每个销地的供应量不小于其需求量的80 调运方案的总运费不超过最小运费调运方案的10 因路段的问题 尽量避免安排将A2的产品运往B4 B1和B3的供应率要相同 力求总运费最省 达成函数为 某电子公司生产录音机和收音机两种产品 它们均需经过两个工厂加工 每一台录音机在第一个工厂加工2小时 然后送到第二个工厂装配试验2 5小时才变为成品 每一台收音机需在第一个工厂加工4小时 在第二个工厂装配试验1 5小时才变为成品 录音机与收音机每台厂内的每月储存成本分别为8元和15元 第一个工厂有12部制造机器 每部每天工作8小时 每月正常工作天数为25天 第二个工厂有7部装配试验设备 每部每天工作16小时 每月正常工作天数仍为25天 每台机器每小时的运转成本是 第一个工厂为18元 第二个工厂为15元 每台录音机的销售利润为20元 收音机为23元 依市场预测 下月录音机与收音机的销售量估计分别为1500台和1000台 例9 生产问题 该公司确定下列次序为目标优先次序 P1 厂内的储存成本不超过23000元 P2 录音机销售量必须完成1500台 P3 第一 二工厂的生产设备应全力运转 避免有空闲时间 两厂运转成本当作它们间的权系数 P4 第一个工厂的超时作业时间全月份不宜超过30小时 P5 收音机销售量必须完成1000台 P6 两个工厂的超时工作时间总应予限制 其限制的比率依各厂每小时运转成本为准 试建立这个问题的目标规划模型 解设x1 x2分别表示次月份录音机与收音机的产量 di di 分别为第i个目标的负 正偏差变量 1 第一 二工厂设备运转时间约束 第一个工厂设备总能力 8 12 25 2400小时第二个工厂设备总能力 16 7 25 2800小时于是 2 厂内储存成本约束 3 销售目标约束 4 第一个工厂超时作业之约束 注意 这里对偏差变量引进它的偏差变量 且用 5 达成函数为 分别表示它的负 正偏差变量 达成函数中级目标的权系数是取第一 第二两工厂每小时运转成本比率18 15 6 5 综合上述分析 即得这个问题的目标规划模型如下 约束条件 目标约束中偏差变量的选择 目前的有关目标规划的文献往往给人们这样一种印象 似乎模型中目标约束中的正负偏差变量要成对出现 而实际上决策者在解决实际多目标决策问题时 模型中目标约束中的正负偏差变量可能只出现一个 正偏变量或负偏差变量 或成对出现 目标约束中偏差变量的正确选择对于多目标决策问题的求解结果有很大的影响 决策者应该根据实际决策情况选择目标约束中的偏差变量 例10某企业在计划期内生产两种产品 每生产一件产品1可以获利12元 每生产一件产品2可以获利14元 生产一件产品1所需设备A和设备B的台时分别为8台时和10台时 生产一件产品2所需设备A和设备B的台时分别为10台时和6台时 设备A和设备B的有效台时分别为1500台时和1000台时 该企业决策者确定的目标优先级为 第一优先级 实现利润不低于5000元 第二优先级 充分利用设备A和设备B的有效台时问 如何安排产品1和产品2的生产 建立目标规划模型时 企业决策者需要从两个方面进行考虑 首先要考虑现有的设备资源在短期内能否满足所提出的目标 短期内设备的生产能力难以改变 所以这属于短期规划决策问题 其次是如果现有设备的生产能力不能满足既定的目标 那么要实现上述目标 在长期内又应该如何决策 因为设备的生产能力在长期可以改变 所以这属于长期规划决策问题 设产品1的产量为x1 产品2的产量为x2 短期规划决策目标规划模型为 利用解目标规划的单纯形法 模型的满意解为 其余变量为零 即产品1的产量为19 23单位 产品2的产量为134 62单位 可以验证 实际利润为2115 38元 第一优先级的目标没有完成 设备A和设备B的有效台时得到充分的利用 第二优先级的目标完成 这说明了在短期内 即使现有设备的生产能力得到充分的利用 仍然不能实现决策者所提出的利润目标 与短期规划决策目标模型不同 因为设备的生产能力在长期可以改变 长期规划决策目标规划模型在设备生产能力目标约束中同时考虑了正负偏差变量 其模型为 可以求出模型的满意解为 其余变量为零 即产品1的产量为416 67单位 不生产产品2 两个优先级的目标都得到完成 由两个正偏差变量的值可以看出 从长期来看 要实现决策者既定的利润目标 现有设备A的生产能力应该由1500台时增加到3333 33台时 设备B的生产能力应该由1000台时增加到4166 67台时 比较两模型可以看出 目标约束中偏差变量是单个出现还是成对出现 对于模型的求解结果和求解结果的分析有很大的影响 如果目标函数中的某优先等级出现负 或正 偏差变量 那么在相应的目标约束中一定包含这个负 或正 偏差变量 正 或负 偏差变量是否包含在该目标约束中应该视情况而定 目标约束中正负偏差变量不一定要同时成对出现 1 60 线性规划 目标规划的软件求解 1线性规划的计算机求解简介 1 8 2目标规划的计算机求解简介 2 3 常用的两种方法权系数法 或效用系数法 这类方法是力