运筹学目标规划ppt课件.ppt

Chapter4目标规划GoalProgramming 运筹学OperationsResearch 4 1目标规划数学模型MathematicalModelofGP4 2目标规划的图解法ThegraphicalmethodofGP4 3单纯形法SimplexMethod 4 1目标规划数学模型MathematicalModelofGP 线性规划模型的特征是在满足一组约束条件下 寻求一个目标的最优解 最大值或最小值 而在现实生活中最优只是相对的 或者说没有绝对意义下的最优 只有相对意义下的满意 1978年诺贝尔经济学奖获得者 西蒙 H A Simon 美国卡内基 梅隆大学 1916 教授提出 满意行为模型要比最大化行为模型丰富得多 否定了企业的决策者是 经济人 概念和 最大化 行为准则 提出了 管理人 的概念和 令人满意 的行为准则 对现代企业管理的决策科学进行了开创性的研究 4 1目标规划的数学模型MathematicalModelofGP 例4 考虑例1 1 资源消耗如表4 1所示 x1 x2 x3分别为甲 乙 丙的产量 使企业在计划期内总利润最大的线性规划模型为 表4 1 4 1 1引例 4 1目标规划的数学模型MathematicalModelofGP 最优解X 50 30 10 Z 3400 4 1目标规划的数学模型MathematicalModelofGP 现在决策者根据企业的实际情况和市场需求 需要重新制定经营目标 其目标的优先顺序是 1 利润不少于3200元 2 产品甲与产品乙的产量比例尽量不超过1 5 3 提高产品丙的产量使之达到30件 4 设备加工能力不足可以加班解决 能不加班最好不加班 5 受到资金的限制 只能使用现有材料不能再购进 解 设甲 乙 丙产品的产量分别为x1 x2 x3 如果按线性规划建模思路 最优解实质是求下列一组不等式的解 4 1目标规划的数学模型MathematicalModelofGP 通过计算不等式无解 即使设备加班10小时仍然无解 在实际生产过程中生产方案总是存在的 无解只能说明在现有资源条件下 不可能完全满足所有经营目标 这种情形是按事先制定的目标顺序逐项检查 尽可能使得结果达到预定目标 即使不能达到目标也使得离目标的差距最小 这就是目标规划的求解思路 对应的解称为满意解 下面建立例4 1的目标规划数学模型 4 1目标规划的数学模型MathematicalModelofGP 设d 为未达到目标值的差值 称为负偏差变量 negativedeviationvariable d 为超过目标值的差值 称为正偏差变量 positivedeviationvariable d 0 d 0 设d1 未达到利润目标的差值 d1 为超过目标的差值 当利润小于3200时 d1 且d1 0 有40 x1 30 x2 50 x3 d1 3200成立当利润大于3200时 d1 且d1 有40 x1 30 x2 50 x3 d1 3200成立当利润恰好等于3200时 d1 且d1 0 有40 x1 30 x2 50 x3 3200成立实际利润只有上述三种情形之一发生 因而可以将三个等式写成一个等式 40 x1 30 x2 50 x3 d1 d1 3200 4 1目标规划的数学模型MathematicalModelofGP 2 设分别为未达到和超过产品比例要求的偏差变量 则产量比例尽量不超过1 5的数学表达式为 3 设d3 d 分别为品丙的产量未达到和超过30件的偏差变量 则产量丙的产量尽可能达到30件的数学表达式为 利润不少于3200理解为达到或超过3200 即使不能达到也要尽可能接近3200 可以表达成目标函数 d1 取最小值 则有 4 1目标规划的数学模型MathematicalModelofGP 4 设d4 d4 为设备A的使用时间偏差变量 d5 d5 为设备B的使用时间偏差变量 最好不加班的含义是d4 和d5 同时取最小值 等价于d4 d5 取最小值 则设备的目标函数和约束为 5 材料不能购进表示不允许有正偏差 约束条件为小于等于约束 由于目标是有序的并且四个目标函数非负 因此目标函数可以表达成一个函数 4 1目标规划的数学模型MathematicalModelofGP 式中 Pj j 1 2 3 4 称为目标的优先因子 第一目标优于第二目标 第二目标优于第三目标等等 其含义是按P1 P2 的次序分别求后面函数的最小值 则问题的目标规划数学模型为 4 1目标规划的数学模型MathematicalModelofGP 满意解 约束分析 4 1目标规划的数学模型MathematicalModelofGP 1 目标规划数学模型的形式有 线性模型 非线性模型 整数模型 交互作用模型等 2 一个目标中的两个偏差变量di di 至少一个等于零 偏差变量向量的叉积等于零 d d 0 3 一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值 按多个目标的重要性 确定优先等级 顺序求最小值 4 按决策者的意愿 事先给定所要达到的目标值当期望结果不超过目标值时 目标函数求正偏差变量最小 当期望结果不低于目标值时 目标函数求负偏差变量最小 当期望结果恰好等于目标值时 目标函数求正负偏差变量之和最小 4 1 2数学模型 4 1目标规划的数学模型MathematicalModelofGP 5 由目标构成的约束称为目标约束 目标约束具有更大的弹性 允许结果与所制定的目标值存在正或负的偏差 如例4 1中的5个等式约束 如果决策者要求结果一定不能有正或负的偏差 这种约束称为系统约束 如例4 1的材料约束 6 目标的排序问题 多个目标之间有相互冲突时 决策者首先必须对目标排序 排序的方法有两两比较法 专家评分等方法 构造各目标的权系数 依据权系数的大小确定目标顺序 7 合理的确定目标数 目标规划的目标函数中包含了多个目标 决策者对于具有相同重要性的目标可以合并为一个目标 如果同一目标中还想分出先后次序 可以赋予不同的权系数 按系数大小再排序 例如 在例4 1中要求设备B的加班时间不超过设备A的时间 目标函数可以表达为 表示在中先求最小再求最小 4 1目标规划的数学模型MathematicalModelofGP 8 多目标决策问题 多目标决策研究的范围比较广泛 在决策中 可能同时要求多个目标达到最优 例如 企业在对多个项目投资时期望收益率尽可能最大 投资风险尽可能最小 属于多目标决策问题 本章的目标规划尽管包含有多个目标 但还是按单个目标求偏差变量的最小值 目标函数中不含有决策变量 目标规划只是多目标决策的一种特殊情形 本章不讨论多目标规划的求解方法 只给出WinQSB软件求解线性多目标规划的操作步骤 参看例4 3和4 9 4 1目标规划的数学模型MathematicalModelofGP 9 目标规划的一般模型 设xj j 1 2 n 为决策变量 4 1目标规划的数学模型MathematicalModelofGP 式中pk为第k级优先因子 k 1 2 K wkl wkl 为分别赋予第l个目标约束的正负偏差变量的权系数 gl为目标的预期目标值 l 1 L 4 1b 为系统约束 4 1c 为目标约束 例4 2 某企业集团计划用1000万元对下属5个企业进行技术改造 各企业单位的投资额已知 考虑2种市场需求变化 现有竞争对手 替代品的威胁等影响收益的4个因素 技术改造完成后预测单位投资收益率 单位投资获得利润 单位投资额 100 如表4 2所示 4 1目标规划的数学模型MathematicalModelofGP 集团制定的目标是 1 希望完成总投资额又不超过预算 2 总期望收益率达到总投资的30 3 投资风险尽可能最小 4 保证企业5的投资额占20 左右 集团应如何作出投资决策 表4 2 4 1目标规划的数学模型MathematicalModelofGP 解 设xj j 1 2 5 为集团对第j个企业投资的单位数 1 总投资约束 4 1目标规划的数学模型MathematicalModelofGP 2 期望利润率约束 整理得 4 1目标规划的数学模型MathematicalModelofGP 3 投资风险约束 投资风险值的大小一般用期望收益率的方差表示 但方差是x的非线性函数 这里用离差 rij E rj 近似表示风险值 例如 集团投资5个企业后对于市场需求变化第一情形的风险是 则4种因素风险最小的目标函数为 约束条件为 4 1目标规划的数学模型MathematicalModelofGP 根据目标重要性依次写出目标函数 整理后得到投资决策的目标规划数学模型 例4 3 车间计划生产I II两种产品 每种产品均需经过A B两道工序加工 工艺资料如表4 3所示 1 车间如何安排生产计划 使产值和利润都尽可能高 2 如果认为利润比产值重要 怎样决策 表4 3 4 1目标规划的数学模型MathematicalModelofGP 解 设x1 x2分别为产品甲和产品乙的日产量 得到线性多目标规划模型 4 1目标规划的数学模型MathematicalModelofGP 1 将模型化为目标规划问题 首先 通过分别求产值最大和利润最大的线性规划最优解 产值最大的最优解 X 1 20 40 Z1 3800利润最大的最优解 X 2 30 30 Z2 540目标确定为产值和利润尽可能达到3800和540 得到目标规划数学模型 4 1目标规划的数学模型MathematicalModelofGP 4 1目标规划的数学模型MathematicalModelofGP 等价于 2 给d2 赋予一个比d1 的系数大的权系数 如 约束条件不变 权系数的大小依据重要程度给定 或者根据同一优先级的偏差变量的关系给定 例如 当利润d2 减少一个单位时 产值d1 减少3个单位 则赋予d2 权系数3 则目标函数为 本节介绍了如何建立目标规划的数学模型及有关概念 1 目标规划由哪些要素构成 与线性规划有哪些不同之处2 偏差变量的含义及其作用3 目标函数的表达方法4 优先级别的含义 4 1目标规划的数学模型MathematicalModelofGP 作业 教材P901 2 4 下一节 目标规划的图解法 4 2目标规划的图解法ThegraphicalmethodofGP 4 2目标规划的图解法ThegraphicalmethodofGP 当目标规划模型中只含两个决策变量 不包含偏差变量 时 可以用图解法求出满意解 例4 4 企业计划生产I II两种产品 这些产品需要使用两种材料 要在两种不同设备上加工 工艺资料如表4 4所示 表4 4 解 设x1 x2分别为产品甲和产品乙的产量 目标规划数学模型为 企业怎样安排生产计划 尽可能满足下列目标 1 力求使利润指标不低于80元 2 考虑到市场需求 II两种产品的生产量需保持1 1的比例 3 设备A既要求充分利用 又尽可能不加班 4 设备B必要时可以加班 但加班时间尽可能少 5 材料不能超用 4 2目标规划的图解法ThegraphicalmethodofGP 2 1 3 4 x2 x1 6 5 o 4 6 4 6 2 2 图4 1 A B C 满意解C 3 3 满意解X 3 3 3 x1 x2 20 40 60 80 100 20 40 60 80 100 2 1 4 图5 3 B C 满意解是线段上任意点 端点的解是B 100 3 80 3 C 60 0 决策者根据实际情形进行二次选择 A 3 x1 x2 20 40 60 80 100 20 40 60 80 100 2 1 4 图5 3 B C 满意解是点B X 100 3 80 3 A 3 x1 x2 20 40 60 80 100 20 40 60 80 100 2 1 4 图5 3 满意解是点A X 20 40 A 本节介绍了目标规划的图解法 1 画出系统约束和目标约束直线2 标明偏差变量大于零的变量X的取值区域3 按优先次序分别求各目标的最小值 作业 教材P91T3 下一节 目标规划的单纯形法 4 2目标规划的图解法ThegraphicalmethodofGP 4 3单纯形法SimplexMethod 单纯形法求解目标规划可参照第一章的步骤 只是目标规划的检验要按优先级顺序逐级进行 不同的是 1 首先使得检验数中P1的系数非负 再使得P2的系数非负 依次进行 2 当P1 P2 Pk对应的系数全部非负时得到满意解 3 如果P1 Pi行系数非负 而Pi 1行存在负数 并且负数所在列上面P1 Pi行中存在正数时 得到满意解 计算结束 4 3单纯形法SimplexMethod 例4 6 用单纯形法求解下述目标规划问题 解 以d1 d2 d3 为基变量 求出检验数 将检验数中优先因子分离出来 每一优先级做一行 列出初始单纯形表4 5 4 3单纯形法SimplexMethod 表4 5 4 3单纯形法SimplexMethod 表4 5中 P1行中 2 最小 则x2进基 求最小比值易知d1 出基 将第二列主元素化为1 其余元素化为零 得到表4 6 表4 6 4 3单纯形法SimplexMethod 表4 6中P1行全部检验数非负 表明第一目标已经得到优化 P2行存在负数 x1的检验数为 P2 0 选x1进基 也可以选d1 进基 则d3 出基 迭代得到表4 7 4 3单纯形法SimplexMethod 表4 7 在表4 7中 P1行的系数全部非负 P2行存在负数 d1 的检验数 2 3P2 0 选d1 进基 则x1出基 迭代得到表4 8 应当注意 表4 7中不能选d2 进基 检验数P1 2 3P2应理解为 大于零 P1 P2是优先级别的比较 而不是 数 的比较 例如 P1 3P2 5P3理解为小于零 2P2 4P4理解为大于零等等 表4 8 4 3单纯形法SimplexMethod 表4 8中P2行的 2 小于零 但 2 列上面P1行存在正数1 检验数P1 2P2 0 所有检验数非负 得到满意解X 0 40 例4 7 1 用单纯形法求解例4 5 2 当目标函数变为 解 1 初始单纯形表见表4 9 最终单纯形表见表4 12 满意解X 100 3 80 3 T 对应于图4 6点B 不难看出有多重解 将d4 进基x2出基 得到另一满意解X 60 0 T 对应于图4 6点C 见表4 13 4 3单纯形法SimplexMethod 求满意解 表4 9 4 3单纯形法SimplexMethod 表4 10 4 3单纯形法SimplexMethod 表4 11 4 3单纯形法SimplexMethod 表4 12 4 3单纯形法SimplexMethod 表4 13 4 3单纯形法SimplexMethod 2 将目标函数改写成 以表4 12为基础 计算出检验数得到表4 14 表4 14 4 3单纯形法SimplexMethod 表4 15 4 3单纯形法SimplexMethod 表4 16 用单纯形法求解得到最终表4 16 满意解X 20 40 T 对应于图4 6中点A在 2 中如果按求解 单纯形法计算如表4 17所示 4 3单纯形法SimplexMethod 表4 17 转下表 4 3单纯形法SimplexMethod 最终表 4 3单纯形法SimplexMethod 满意解X 80 9 560 9 T d3 200 9而d2 0 与目标要求相悖 还可以从图4 6说明这个结果是错误的 例4 7 2 是在原问题中作了部分变动后再求解 等价于第二章的灵敏度分析 求解原理基本相同 TheEndofChapter4 4 2目标规划的图解法Thegraphicalmetho