运筹学——目标规划.ppt

OPERATIONSRESEARCH运筹学 徐玲 第五章目标规划 要求1 理解概念2 掌握建模3 掌握图解法和单纯形解法4 理解目标规划的灵敏度分析 5 1目标规划的概念及数学模型1 多目标问题多目标线性规划例1 求利润最大的生产方案 例2 例1的要求多元化 决策者在原材料供应受严格限制的基础上 1 首先是产品A的产量不大于产品B的产量 2 其次是充分利用设备的有效台时 不加班 3 再次是使利润额尽可能达到并超过计划利润指标56元 此问题即为多目标决策问题 目标规划就是解这类问题的方法 minZ P1d1 P2 d2 d2 P3d3 例2的解法 解 问题分析 找差别 定概念 与单目标规划相比 1 绝对约束 必须严格满足的等式约束和不等式约束 称之为绝对约束 2x1 1 5x2 50 1 x1 2x2 40 2 2 目标约束 那些不必严格满足的等式约束和不等式约束 称之为目标约束 软约束 目标约束是目标规划特有的 这些约束不一定要求严格完全满足 允许发生正或负偏差 因此在这些约束中可以加入正负偏差变量 3 偏差变量 目标约束不是刚性的 而是弹性的 允许在一定范围内有偏差 这更接近于实际 为表达这种灵活性 便引入了偏差变量的概念 偏差变量有正负之分 正偏差变量表示为 d d 表示超过目标值的部分 负偏差变量表示为 d d 表示不足目标值的部分 显然有d d 0 4 目标 期望 值 是指预先给定的某个目标的期望值 5 实际值 是指当决策变量选定以后 目标函数的对应值 显然 d 实际值 目标值 0d 目标值 实际值 0 尽可能达到并超过计划利润指标56元 此处的56元即为目标值 6 目标函数的优先级与权系数 目标的重要程度不同 因此目标的满足有先有后 即有优先级别 设最重要的为P1级 次之者为P2级 P看成实数 且有P1 P2注 目标的优先级是一个定性概念 不同的优先级之间无法用数量衡量 仅仅表示优化过程中的目标考虑的先后次序 对于同一优先级的不同目标 按其重要程度可分别赋予不同的权系数 权系数是一种可以用数量表示的指数 因此 对于一个具体的目标规划问题 它是一个数字 7 目标规划的目标函数 目标规划的目标函数是按各约束的正 负偏差变量和赋予相应的优先因子而构造的 目标函数的基本形式有三种 1 要求恰好达到目标值 即正负偏差变量都要尽可能地小 这时 minZ f d d 2 要求不超过目标值 即允许达不到目标值但正偏差变量要尽可能地小 这时 minZ f d 3 要求超过目标值 即超过量不限但负偏差变量要尽可能的小 这时 minZ f d 显然 本题目标函数表示为 minZ P1d1 P2 d2 d2 P3d3 综上所述 本题的数学模型为 minZ P1d1 P2 d2 d2 P3d3 2x1 x2 11x1 x2 d1 d1 0 x1 2x2 d2 d2 108x1 10 x2 d3 d3 56x1 x2 di di 0 i 1 2 3 几点说明 1 有时绝对约束转化为目标约束 则不再表示为绝对约束 2 有时同级别的目标中 其重要程度又有差别 则设置不同的权重 目标规划问题的特点 1 问题的目标函数是关于优先等级 权系数和偏差变量的极小化函数 2 约束条件由绝对约束或目标约束构成 3 所有决策变量和偏差变量都受到非负约束 例3 请建立以下问题的数学模型 某建筑施工单位计划生产A B两种预制构件 决策者首先考虑要充分利用供电部门分配的电量限额指标62 5kw 日 其次考虑完成与超额完成利润指标10百元 日 每日可供给予制水泥8吨 其它有关数据如下表 问应如何确定A B的产量 课堂练习 某工厂生产A B两种产品 已知有关数据如下 要求 首先 B产品不超过10单位 其次 利润不低于1600元 再次 充分利用2车间的生产能力 尽量不加班 请建立该问题的模型 图解法的基本步骤 1 先作硬约束与决策变量的非负约束 同一般线性规划作图法 2 作目标约束 此时 先让di di 0 然后标出di 及di 的增加方向 实际上是目标值减少与增加的方向 3 按优先级的次序 逐级让目标规划的目标函数中极小化偏差变量取0 从而逐步缩小可行域 最后找出问题的解 5 2目标规划的图解法 5 2目标规划的图解法 图解例2 minZ P1d1 P2 d2 d2 P3d3 2x1 x2 11x1 x2 d1 d1 0 x1 2x2 d2 d2 108x1 10 x2 d3 d3 56x1 x2 di di 0 i 1 2 3 例4 考虑目标规划数学模型的一些特点 作以下规定 1 因目标函数为求最小化 所以要求2 因非基变量检验数中含有不同等级的优先因子 即 因p1 p2 pk 从每个检验数的整体看 检验数的正 负首先决定于p1的系数a1j的正负 若a1j 0 则此检验数的正 负就决定于p2的系数a2j的正负 依次类推 5 3目标规划的单纯形解法 3 目标规划使用单纯形法求解 di di 视为普通变量 P1 P2 PL 求解目标规划单纯形法的步骤 P105 1 建立初始单纯形表 在表中将检验数行按优先因子个数分别列成K行 置k 1 2 检查该行中是否存在负数 且对应的前k 1行的系数是零 若有负数 取其中最小者对应的变量为换入变量 转 3 若无负数 则转 5 3 按最小比值规则确定换出变量 当存在两个和两个以上相同的最小比值时 选取具有较高优先级别的变量为换出变量 4 按单纯形法进行基变换运算 建立新的计算表 返回 2 5 当k K时 计算结束 表中的解即为满意解 否则置k k 1 返回到 2 例题5 用单纯形法求解下列目标规划问题 minZ P1d1 P2 d2 d2 P3d3 2x1 x2 11x1 x2 d1 d1 0 x1 2x2 d2 d2 108x1 10 x2 d3 d3 56x1 x2 di di 0 i 1 2 3 5 5目标规划的灵敏度分析 例5 已知目标规划问题 目标函数的等级变化为 试分析原解有什么变化 解 原问题的最优单纯形表为 问题1的变化情况为 p2 p3 000 此时 检验数大于等于零 可见 原解仍是满意解 p3 003 20 3 002 30 2 001 010 p1 2p2 3p2 p1 320 300 200 230 100 p1级的检验数不是大于等于零 则p1级目标未实现 继续迭代 过程见书第108页 某单位考虑职工的升级调资方案时 依次遵守得规定 1 不超过年工资总额60000元 2 每级的人数不超过定编规定的人数 3 二 三级的升级面尽可能达到现有人数的20 且无越级提升 4 三级不足编制的人数可录用新职工 又一级的职工中有10 要退休 有关资料如下 问应如何拟定一个满意的方案 已知有三个产地给四个销地供应某种产品 产销地之间地供需量和单位运费见下表 有关部门在研究调运方案时依次考虑以下七项目标 并规定其相应地优先等级 P1 B4是重点保证单位 必须全部满足其需要 P2 A3向B1提供地产量不少于100 P3 每个销地地供应量不小于其需求量地80 P4 所定调运方案的总运费不超过最小运费调运方案的10 P5 因路段的问题 尽量避免安排将A2的产品往B4 P6 给B1和B3的供应率要相同 P7 力求总运费最省 试求满意的调运方案 其它条件不考虑 用表上作业法得最小运费为2950 习题