多目标规划（运筹学）

*1 主要内容 了解目标规划与线性规划的相同点与不同点 掌握建立目标规划模型的方法 可用图解法解决有两决策的目标规划 掌握用描述层次分析法解决的问题 熟悉用AHP计算每个方案的一致性比例、优 先级百分比和优先级分数方法 *2 目标规划的来源 保持稳定的利润 增加市场份额 多样化产品线 保持价格稳定 管理层的目标通常包括下面一些内容： 提高员工的士气 保持对业务的控制力 增加公司的声誉 第一节 目标规划 *3 线性规划与目标规划 n 线性规划只能处理单目标问题 n 通过目标规划可以同时实现多个目标，最基本的方 法是为每一个目标建立一个量化的标准，通过平衡各 标准目标的实现程度，求得最优解。 n 分配给各个目标的惩罚权重（penalty weights）表示 是偏离各目标的严重程度。根据各目标建立总目标函 数，该目标函数表示的目标是要使得每个目标函数的 偏差之和最小 。 第一节 目标规划 目标规划模型的约束和目标 目标规划模型里，目标被描述成了约束条件 约束分为软约束和硬约束 硬约束：必须得到满足的条件 软约束（目标约束）：描述模型目标的约束条件 硬约束必须得到满足 目标规划模型的目标是各个目标约束满足程 度的偏差量的加权和 *4 目标约束建模： 如一个管理者构建了一个劳动力工时的目标，则： 4x1+2x2+u1-v1=100 u1：未达到量，负偏差 v1：超量，正偏差 如果劳动力约束里不允许超量，那么约束等 式里面就不会有v1 *5 *6 举例： 某公司希望用新一代产品替换目前生产的三种产品，以使企 业获得更大盈利。由于资金有限，公司不得不在三种新产品 中间作出取舍选择，以期望达到下面的目标： 1.新产品产生的总利润不得少于1.25亿。 2.员工是公司的第一财产，要保持现有的4000人的员工水 平。 3.投资资金限制在550万元以内。 *7 惩罚权重和相关参数见下表： 问题的目标为： 惩罚权重 5 2(+) 4(-) 3 *8 1，加权目标规划模型 min z=5u1+2v2+4u2+3v3 s.t. 12x1+9x2+15x3+u1-v1=125 5x1+3x2+4x3+u2-v2=40 5x1+7x2+8x3+u3-v3=55 xi0, ui 0, vi0 *9 LINDO中数据输入为 求解为 Min 5u1+2v2+4u2+3v3 St 12x1+9x2+15x3+u1-v1=125 5x1+3x2+ 4x3+u2-v2=40 5x1+ 7x2+ 8x3 +u3-v3=55 end *10 2，优先目标规划模型 min z=P1(2v2+3v3)+P2(5u1+4u2) s.t. 12x1+9x2+15x3+u1-v1=125 5x1+3x2+4x3+u2-v2=40 5x1+7x2+8x3+u3-v3=55 xi0, ui 0, vi0 *11 Lindo中输入如下模型： Min obj1+obj2 St 12x1+9x2+15x3+u1-v1=125 5x1+3x2+4x3+u2-v2=40 5x1+7x2+8x3+u3-v3=55 obj1-2v2-3v3=0 obj2-5u1-4u2=0 end 输入完成后，用solve菜单的Preemptive Goal 命令执行 建立目标规划模型的步骤： 1. 明确决策变量。 2. 明确约束并确定哪些是目标约束。 3. 如果有非目标（硬性）约束的话先建立非目标（硬性） 约束。 4. 建立目标（软）约束。 5. 加入非负约束条件。 6. 根据问题写出由偏差变量表示的模型的目标函数 *12 阅读材料： 书P153，例7-1 书P160-161，7-3节 *13 14 第二节 层次分析法 多准则决策问题(multi-criterion decision making problems) 可分为: 多目标决策问题(multi-objective decision making problem)：决策变量是连续的，备选方案有无限多。如 目标规划可以解决此类问题。 多属性决策问题(multi-attribute decision making problem)，也称为多指标决策)：决策变量是离散的，备 选方案数量是有限个。如层次分析法可以解决此类问题 。 许多决策问题是属于多属性决策问题，比如买房子，需 要考虑地点、环境、价格、结构、面积等；选择供应商 ，需要考虑质量、价格、服务、交货期等 这类问题具有如下特点: (1)目标多于一个. (2)目标间不可公度(non-commensurable). (3)各目标间的矛盾性. 15 例：选择供应商 假设有四家供应商可以选择，从质量、价格、服务 、交货期等四个方面(准则)考察： 目标类 准则类 措施类 16 层次分析法是定性与定量相结合，解决多目标决策问题的 一种方法 主要思想就是将多个准则归结为一个。具体说就是，通过 两两比较，确定每个准则的权重，然后将每个方案在每个 准则下的得分综合起来，就得到每个方案的总得分，得分 高的为最优。 为什么采用两两比较确定权重？ 因为直接给每个打分太困难。 对前面的例子，我们要先确定选择最佳供应商时，质量、 价格、服务和交货期四类标准准则在评价供应商时的权重 ；然后要确定每个供应商在这四类标准中的得分。 层次分析法 17 两两比较 假设四个供应商在质量方面分别得分（w1, w2, w3, w4 ），那么两两互相比较，相对重要性为 反过来，如果知道两两比较矩阵，那么得分向量如何求？ w1 w2 w3 w4 w1 w2 w3 w4 18 两两比较的原则 采用TL Saaty提出的做法，用数字19及其倒数作为标度 。来自于下述根据： （1）在估计事务的区别时，人们常用五种判断表示，即相 等、较强、强、很强、绝对强。需要更高精度时，还可以 在相邻判断之间做出比较，共九个等级。 （2）心理学家认为，人们在同时比较若干个对象时，能够 区别差异的心理学极限为72个对象。Saaty将19标度法 与一种26标度法进行比较，表明19标度法可行且可以较 好地将思维进行量化。 两两比较的结果用1, 2, 3, , 9表示： 1表示强弱或重要性相同 3表示略微重要 5表示比较重要 7表示非常重要 9表示绝对重要 2, 4, 6, 8分别介于它们之间 19 质量方面两两比较 质量S1S2S3S4 S11561/3 S2121/6 S311/8 S41 20 由两两比较求权重 和积法 设判断矩阵为 按列将判断矩阵A规范化， 其中分母为矩阵的列和，得到矩阵B。 计算矩阵B的行和， 权重 21 质量方面两两比较 得分 22 价格方面两两比较 23 服务方面两两比较 24 交货期 25 质量/价格/服务/交货期 比较 26 四个供应商的总排序 S1S4S2S3 27 一致性检验问题 AHP的关键是成对比较，因此需要格外注意进 行成对比较时的一致性。例如若质量与服务相 当，为1，而服务与价格相比为1/2，这质量与 价格相比应为11/2=1/2。如果不是该值，那 在成对比较中就存在不一致性。 成对比较的数量较多，很难做到完全一致性。 AHP提供了一种方法来测量决策者进行成对比 较的一致性。若达不到一致性要求，则需要重 新审核成对比较并进行修改。 28 一致性检验 1.A*w 2.A*w各分量分别除以w对应分量 3.计算第2步结果的平均值 4.计算一致性指标 维数n123456789 RI000.58 0.96 1.12 1.24 1.32 1.41 1.45 5. 计算一致性比率 CR=CI/RI 0.1，则一致 性检查通过。 29 问题: 一致性 设左边对应的矩阵为A 权重向量 w=(0.303，0.573，0.078，0.046)为矩阵A 的特征向量 30 1.A*w 2.A*w各分量分别除以w对应分量 3.计算第2步结果的平均值 4.计算一致性指标 维数n123456789 RI000.58 0.96 1.12 1.24 1.32 1.41 1.45 5. 计算一致性比率 CR=CI/RI 0.1，则一致性通过 31 层次分析法的基本步骤 第1步，明确问题，提出总目标 第2步，建立层次结构，分解问题为若干层次. 第3步，从高层到低层求同一层次上的权系数. 第4步，求同一层次上的组合权系数. 第5步，一致性检验. 阅读材料： 书P162-167，7-4节 *32 *33 本讲小结 小结 目标规划能够使多个目标同时最大限度实现，为各个目标分 配数量化的标准，通过平衡各目标的实现程度来求得最优解 目标规划有加权目标规划和优先目标规划两种模型。加权目 标规划为各个目标建立量化目标，而后通过平衡各目标的实 现程度来求得最优解；优先目标规划则将各个目标按照其重 要性进行排序，之后按照排序每次都只集中到一个目标上。 两者都可以建立线性规划模型，使得求解比较容易。