数学建模培训多目标规划PPT课件

1、 例如例如, ,对企业产品的生产管理对企业产品的生产管理, ,既希望达到高利既希望达到高利润润, ,又希望优质和低消耗又希望优质和低消耗, ,还希望减少对环境的污染等。还希望减少对环境的污染等。这就是一个多目标决策的问题。又如选购一个好的计这就是一个多目标决策的问题。又如选购一个好的计算机系统算机系统, ,似乎只有一个目标似乎只有一个目标, ,但由于要从多方面去反但由于要从多方面去反映映, ,要用多个不同的准则来衡量要用多个不同的准则来衡量, ,比如比如, ,性能要好性能要好, ,维护维护要容易要容易, ,费用要省。这些准则自然构成了多个目标费用要省。这些准则自然构成了多个目标, ,故故也是一

2、个多目标决策问题。一般来说也是一个多目标决策问题。一般来说, ,多目标决策问多目标决策问题有两类。一类是多目标规划问题题有两类。一类是多目标规划问题, ,其对象是在管理其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方决策过程中求解使多个目标都达到满意结果的最优方案。另一类是多目标优选问题案。另一类是多目标优选问题, ,其对象是在管理决策其对象是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选过程中根据多个目标或多个准则衡量和得出各种备选方案的优先等级与排序。方案的优先等级与排序。第1页/共112页多目标决策由于考虑的目标多多目标决策由于考虑的目标多, ,有些目标之间又彼有些

3、目标之间又彼此有矛盾此有矛盾, ,这就使多目标问题成为一个复杂而困难这就使多目标问题成为一个复杂而困难的问题的问题. .但由于客观实际的需要但由于客观实际的需要, ,多目标决策问题多目标决策问题越来越受到重视越来越受到重视, ,因而出现了许多解决此决策问题因而出现了许多解决此决策问题的方法的方法. .一般来说一般来说, ,其基本途径是其基本途径是, ,把求解多目标问把求解多目标问题转化为求解单目标问题题转化为求解单目标问题. .其主要步骤是其主要步骤是, ,先转化先转化为单目标问题为单目标问题, ,然后利用单目标模型的方法然后利用单目标模型的方法, ,求出求出单目标模型的最优解单目标模型的最优

4、解, ,以此作为多目标问题的解以此作为多目标问题的解. . 化多目标问题为单目标问题的方法大致可分化多目标问题为单目标问题的方法大致可分为两类为两类, ,一类是转化为一个单目标问题一类是转化为一个单目标问题, ,另一类是另一类是转化为多个单目标问题转化为多个单目标问题, ,关键是如何转化关键是如何转化. . 以下以下, ,我们会介绍几种主要的转化方法我们会介绍几种主要的转化方法: :主要主要目标法、线性加权和法、字典序法、步骤法。目标法、线性加权和法、字典序法、步骤法。第2页/共112页一、多一、多 目标目标 规规 划划 及及 其其 解解 多目标规划包含有三大要素：目标、方案和决策者。多目标规

5、划包含有三大要素：目标、方案和决策者。 在多目标规划中，目标有多层次的含义。从最高层次来在多目标规划中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，成衡量总目标得以实现的各个准则

6、，如食品的味道要好，质量要好，花费要少。质量要好，花费要少。 多目标规划中的方案即为决策变量，也称为多目标问题多目标规划中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。方案有其特征或特性，称之为属性。第3页/共112页 （一）任何多目标规划问题，都由两个基本部分组成（一）任何多目标规划问题，都由两个基本部分组成: : （1 1）两个以上的目标函数；）两个以上的目标函数； （2 2

7、）若干个约束条件。）若干个约束条件。 （二）对于多目标规划问题，可以将（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：其数学模型一般地描写为如下形式： 第4页/共112页（2 2）)(max(min)(max(min)(max(min)(max(min)21XfXfXfXFZkmmgggGXXXX2121)()()()(（1 1）式中：式中： 为决策变量向量。为决策变量向量。 TnxxxX,21第5页/共112页第6页/共112页第7页/共112页 （三）多目标规划解的特点（三）多目标规划解的特点 对于上述多目标规划问题，求解就意味着需要对于上述多目标规划问题，求解就意味着需要

8、做出如下的复合选择：做出如下的复合选择： （1 1）每一个目标函数取什么值，原问题可以得）每一个目标函数取什么值，原问题可以得到最满意的解决？到最满意的解决？ （2 2）每一个决策变量取什么值，原问题可以得）每一个决策变量取什么值，原问题可以得到最满意的解决到最满意的解决 ？ 多目标规划问题的求解不能只追求一个目标的多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。最优化（最大或最小），而不顾其它目标。第8页/共112页第9页/共112页第10页/共112页第11页/共112页 当目标函数处于冲突状态时，就不会当目标函数处于冲突状态时，就不会存在使所有目标函数同时达

9、到最大或最小存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。（又称非支配解或帕累托解）。 第12页/共112页非劣解：可以用图非劣解：可以用图3 3说明。说明。图3 多目标规划的劣解与非劣解第13页/共112页第14页/共112页第15页/共112页二、多二、多 目目 标标 规规 划划 问问 题题 的的 建建 模模 方方 法法 为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化，有如下几种建模方法。单目标

10、规划问题去处理。实现这种转化，有如下几种建模方法。第16页/共112页第17页/共112页第18页/共112页第19页/共112页第20页/共112页（三）约束模型三）约束模型 理论依据理论依据 ：若规划问题的某一目标可以给：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约作为约束条件而被排除出目标组，进入约束条件组中。束条件组中。假如，除第一个目标外，其余目标都可以假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：划

11、问题就可以转化为单目标规划问题： 第21页/共112页第22页/共112页第23页/共112页第24页/共112页第25页/共112页第26页/共112页 用目标达到法求解多目标规划的计用目标达到法求解多目标规划的计算过程，可以通过调用算过程，可以通过调用MatlabMatlab软件系统软件系统优化工具箱中的优化工具箱中的fgoalattainfgoalattain函数实现。函数实现。第27页/共112页三、多目标规划问题的求解(化多为少的方法)1 1、主要目标法、主要目标法 在有些多目标决策问题中，各种目标的重在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最要性程

12、度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。余的目标则称为非主要目标。0)(0)(. .)(. .)(),.,(),()(21XhXgtsorGXtsXfXfXfXoptFjiTk第28页/共112页例如，在上述多目标问题中，假定例如，在上述多目标问题中，假定f1(X)为主要为主要目标，其余目标，其余p p-1-1个为非主要目标。这时，希望个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足主要目标达到极大值，并要求其余的目标满足一定的条件，即一定的条件，即1,.,2 , 1,)(,.

13、,2 , 1, 0)(,.,2 , 1, 0)(. .)(max1pkXfmjXhniXgtsXfkkji第29页/共112页例题例题 某工厂在一个计划期内生产甲、乙两种产品，某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗各产品都要消耗A A，B B，C C三种不同的资源。每件产品三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大

14、，且造成的污染最小？才能使利润和产值都最大，且造成的污染最小？甲甲乙乙资源限量资源限量资源资源A A单位消耗单位消耗资源资源B B单位消耗单位消耗资源资源C C单位消耗单位消耗9 94 43 34 45 51010240240200200300300单位产品的价格单位产品的价格400400600600单位产品的利润单位产品的利润7070120120单位产品的污染单位产品的污染3 32 2第30页/共112页解：问题的多目标模型如下解：问题的多目标模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxx

15、xxxXfxxXfxxXf对于此模型的三个目标，工对于此模型的三个目标，工厂确定利润最大为主要目标。厂确定利润最大为主要目标。另两个目标则通过预测预先另两个目标则通过预测预先给定的希望达到的目标值转给定的希望达到的目标值转化为约束条件。经研究，工化为约束条件。经研究，工厂认为总产值至少应达到厂认为总产值至少应达到2000020000个单位，而污染控制个单位，而污染控制在在9090个单位以下，即个单位以下，即9023)(20000600400)(213212xxXfxxXf第31页/共112页由主要目标法化为单目标问题由主要目标法化为单目标问题0,300103200542404990232000

16、060040012070)(max212121212121211xxxxxxxxxxxxxxXf用单纯形法求得其最优解为用单纯形法求得其最优解为90)(,20750)(,4025)(,25.26, 5 .1232121xfxfxfxx第32页/共112页2 2、线性加权和目标规划、线性加权和目标规划0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp在上述目标规划中，假定在上述目标规划中，假定f1 1(X),(X),f2 2(X),(X),fp p(X)(X)具有具有相同的量纲相同的量纲, ,按照一定的规则分别给按照一定的规则分别给f fi i赋予相同的权赋

17、予相同的权系数系数i，作线性加权和评价函数，作线性加权和评价函数piiiXfXU1)()(第33页/共112页0)(0)(. .)()(max1XhXgtsXfXUjipiii则多目标问题化为如下的单目标问题则多目标问题化为如下的单目标问题第34页/共112页例如，某公司计划购进一批新卡车，可供选择的卡车有例如，某公司计划购进一批新卡车，可供选择的卡车有如下如下4 4种类型：种类型：A1A1，A2A2，A3A3，A4A4。现考虑。现考虑6 6个方案属性：个方案属性：维修期限维修期限f1 1，每，每100100升汽油所跑的里数升汽油所跑的里数f2 2，最大载重吨数，最大载重吨数f3 3，价格（万

18、元），价格（万元）f4 4，可靠性，可靠性f5 5，灵敏性，灵敏性f6 6。这。这4 4种型号的种型号的卡车分别关于目标属性的指标值卡车分别关于目标属性的指标值fijij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先对不同度量单位和不同数量级的指标值进行标准首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：化处理。先将定性指标定量化：第35页/共112页第36页/共112页变换后的指标值矩阵为：变换后的指

19、标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001第37页/共112页设权系数向量为设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则则925.57)(max*27.40)(925.57)(6 .40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最优方案为选购故最优方案为选购A3A3型卡车型卡车第38页/共112页第39页/共112页第40页/共112页第41页/共112页第42页/共1

20、12页4 4、步骤法（、步骤法（STEMSTEM法）法） 这是一种交互方法，其求解过程通过分析者与决策这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。者之间的对话逐步进行，故称步骤法。 步骤法的基本思想是，首先需要求出原多目标问题步骤法的基本思想是，首先需要求出原多目标问题的一组理想解的一组理想解(f(f1 1* *,f,f2 2* *,f,fk k* *) )。实际上，这些解。实际上，这些解f fi i* *(i=1,2,k)(i=1,2,k)无法同时达到，但可以当作一组理想的无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后最

21、优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直到决策的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。者得到满意的解。第43页/共112页第44页/共112页把上述计算结果列入下表把上述计算结果列入下表*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX第45页/共112页第46页/共112页第47页/共112页例题：例题：某公司考虑生产两种光电太阳能电池：产品甲和某公司考虑生产两种

22、光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性污染。因产品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收射性污染。已知在一个生产周期内，每单位甲产品的收益是益是1 1元，每单位乙产品的收益是元，每单位乙产品的收益是3 3元。而放射性污染的元。而放射性污染的数量，每单位甲产品是数量，每单位甲产品是1.51.5个单位个单位, ,每单位乙产品是每单位乙产品是1 1个个单位单位. .由于机器能力由于机器能力( (小时小时) )、装配能力（人时）

23、和可用、装配能力（人时）和可用的原材料（单位）的限制，约束条件是的原材料（单位）的限制，约束条件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料装配能力机器能力xxxxxx第48页/共112页)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料装配能力机器能力xxxxxxxxXfxxXfXfXfXFT目标有两个目标有两个: :一是利润最大一是利润最大, ,二是污染最小二是污染最小. .该问题该问题的多目标规划模型如下的多目标规划模型如下: :第49页/共112页解解: :首先

24、首先, ,分别求解两个单目标问题的最优解分别求解两个单目标问题的最优解, ,由它们由它们得到的目标函数值组成理想解得到的目标函数值组成理想解. .)(725)(42 . 02 . 0)(825. 05 . 03)(max212121211原材料装配能力机器能力xxxxxxxxXf)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(max212121212原材料装配能力机器能力xxxxxxxxXf46*)13, 7(1*1fX0*)0 , 0(1*2fX第50页/共112页由此由此, ,构造支付表构造支付表Xf1*f2*(7,13)(0,0)460-23.50由此计算两个

25、目标与理由此计算两个目标与理想值偏离的权重：想值偏离的权重：637. 0,363. 0,555. 0,316. 02121解下列线性规划问题解下列线性规划问题: :0,7254)2 . 02 . 08)25. 05 . 0)230(637. 0)346(363. 0min212121212121xxxxxxxxxxxx第51页/共112页第52页/共112页0,7254)2 . 02 . 08)25. 05 . 0192.21310)5 . 1346min21212121212121xxxxxxxxxxxxxx进行下一轮迭代进行下一轮迭代. .首先设首先设2 2=0,=0,并计算得并计算得1

26、1=1.=1.将将模型修改为模型修改为第53页/共112页由此求得由此求得: :10,3010, 02121ffxx决策者把这一结果与前一轮的解及理想值作比较决策者把这一结果与前一轮的解及理想值作比较, ,认为两个目标值都比较满意认为两个目标值都比较满意, ,则迭代结束则迭代结束. .第54页/共112页线线 性性 目目 标标 规规 划划 模模 型型 线性规划问题都是处理单个目标的情况，但是在现实世线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目标相互依赖，例如决相同，

27、往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。标规划问题。在这里我们主要讨论

28、线性目标规划问题。第55页/共112页一、线性目标规划模型的建立一、线性目标规划模型的建立 例例1 1：某一个企业利用某种原材料和现有设备可生某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价产甲、乙两种产品，其中，甲、乙两种产品的单价分别为分别为8 8元和元和1010元；生产单位甲、乙两种产品需要元；生产单位甲、乙两种产品需要消耗的原材料分别为消耗的原材料分别为2 2个单位和个单位和1 1个单位，需要占用个单位，需要占用的设备分别为的设备分别为1 1台时和台时和2 2台时；原材料拥有量为台时；原材料拥有量为1111个个单位；可利用的设备总台时为单位；可利用的设

29、备总台时为1010台时。试问：如何台时。试问：如何确定其生产方案？确定其生产方案？第56页/共112页第57页/共112页 但是，在实际决策时，企业领导者必须考虑市场但是，在实际决策时，企业领导者必须考虑市场等一系列其它条件，如：等一系列其它条件，如：根据市场信息，甲种产品的需求量有下降的趋势，根据市场信息，甲种产品的需求量有下降的趋势，因此甲种产品的产量不应大于乙种产品的产量。因此甲种产品的产量不应大于乙种产品的产量。超过计划供应的原材料，需用高价采购，这就会使超过计划供应的原材料，需用高价采购，这就会使生产成本增加。生产成本增加。应尽可能地充分利用设备的有效台时，但不希望加应尽可能地充分利

30、用设备的有效台时，但不希望加班。班。应尽可能达到并超过计划产值指标应尽可能达到并超过计划产值指标5656元。元。 这样，该企业生产方案的确定，便成为一个多这样，该企业生产方案的确定，便成为一个多目标决策问题，这一问题可以运用目标规划方法进目标决策问题，这一问题可以运用目标规划方法进行求解。行求解。第58页/共112页目标规划模型的有关概念第59页/共112页2 2、绝对约束和目标约束、绝对约束和目标约束 绝对约束：绝对约束：必须严格满足的等式约束和不必须严格满足的等式约束和不等式约束，譬如，线性规划问题的所有约束条等式约束，譬如，线性规划问题的所有约束条件都是绝对约束，不能满足这些约束条件的解

31、件都是绝对约束，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。称为非可行解，所以它们是硬约束。 目标约束：目标约束：目标规划所特有的，可以将目标规划所特有的，可以将约束方程右端项看作是追求的目标值，在达到约束方程右端项看作是追求的目标值，在达到此目标值时允许发生正的或负的偏差此目标值时允许发生正的或负的偏差 ，可加，可加入正负偏差变量，是软约束。入正负偏差变量，是软约束。 线性规划问题的目标函数，在给定目标线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可以转化为目标约值和加入正、负偏差变量后可以转化为目标约束，也可以根据问题的需要将绝对约束转化为束，也可以根据问题的需要将

32、绝对约束转化为目标约束。目标约束。 目标规划模型的有关概念第60页/共112页目标规划模型的有关概念第61页/共112页目标规划模型的有关概念第62页/共112页b) b) 要求不超过目标值，即允许达不到目标要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能小，即值，就是正偏差变量要尽可能小，即)(mindfZ（23） c) c) 要求超过目标值，也就是超过量不限，要求超过目标值，也就是超过量不限，但负偏差变量要尽可能小，即但负偏差变量要尽可能小，即 )(mindfZ（24） 在实际问题中，可以根据决策者的要求，在实际问题中，可以根据决策者的要求，引入正、负偏差变量和目标约束，并给不

33、同引入正、负偏差变量和目标约束，并给不同目标赋予相应的优先因子和权系数，构造目目标赋予相应的优先因子和权系数，构造目标函数，建立模型。标函数，建立模型。 第63页/共112页例例2 2：在例在例1 1中，如果决策者在原材料供中，如果决策者在原材料供应受严格控制的基础上考虑：首先是甲应受严格控制的基础上考虑：首先是甲种产品的产量不超过乙种产品的产量；种产品的产量不超过乙种产品的产量；其次是充分利用设备的有限台时，不加其次是充分利用设备的有限台时，不加班；再次是产值不小于班；再次是产值不小于5656元。并分别赋元。并分别赋予这三个目标优先因子予这三个目标优先因子 。试建立。试建立该问题的目标规划模

34、型。该问题的目标规划模型。321,PPP第64页/共112页第65页/共112页第66页/共112页在以上各式中，在以上各式中， 、 分别为赋予分别为赋予 优先因子的第优先因子的第 个目标的正、负个目标的正、负偏差变量的权系数，偏差变量的权系数， 为第为第 个目标的预期值，个目标的预期值， 为决策变量，为决策变量， 、 分别为第分别为第 个目标的正、负偏差变量，个目标的正、负偏差变量，（2525）式为目标函数，（）式为目标函数，（2626）式为目标约束，（）式为目标约束，（2727）式）式为绝对约束，（为绝对约束，（2828）式和（）式和（2929）式为非负约束，）式为非负约束， 、 、 分别

35、为目标约束和绝对约束中决策变量的系数及约束值。分别为目标约束和绝对约束中决策变量的系数及约束值。其中，其中， ； ； ； 。 lklklpkkgkjxkdkdk)(kjcijaibmi, 2 , 1nj, 2 , 1Ll, 2 , 1Kk, 2 , 1第67页/共112页图解法求解例图解法求解例2 2第68页/共112页首先考虑具有首先考虑具有 优先因子优先因子的目标的实现，在目标函的目标的实现，在目标函数中要求实现数中要求实现 ，图，图中可以满足中可以满足 . .这时这时 的取值只能在的取值只能在OBCOBC的边界和的边界和内部取得。内部取得。 1p1mind01d21,xx接着考虑接着考虑

36、 优先因子的优先因子的目标的实现，在目标函目标的实现，在目标函数中要求实现数中要求实现 ，当时当时 ，其值，其值 可在线段可在线段EDED上取得。上取得。 2p)min(22 dd022dd21,xx第69页/共112页最后考虑最后考虑 优先因子的目标优先因子的目标的实现，在目标函数中要求实的实现，在目标函数中要求实现现 ，当，当 时，其值时，其值 缩小到在线段缩小到在线段GDGD上取得上取得. .这就这就是该目标规划问题的解是该目标规划问题的解.G.G和和D D点凸组合都是此目标规划的解点凸组合都是此目标规划的解. .3p3mind03d21,xx注注：在目标规划问题求解时，把绝对约束作最高

37、优先级考虑。：在目标规划问题求解时，把绝对约束作最高优先级考虑。在此例中，能依先后次序都满足在此例中，能依先后次序都满足 因因而而 。但是大多数问题中并非如此，还可能出现非可行解，。但是大多数问题中并非如此，还可能出现非可行解，故将目标规划问题的最优解成为满意解。故将目标规划问题的最优解成为满意解。 0, 0, 03221dddd0*z第70页/共112页例如例如， 某电视机厂装配黑白和彩色两种电视机，每某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线装配一台电视机需占用装配线1 1小时，装配线每周计划小时，装配线每周计划开动开动4040小时。预计市场每周彩色电视机的销量是小时

38、。预计市场每周彩色电视机的销量是2424台，台，每台可获利每台可获利8080元；黑白电视的销量是元；黑白电视的销量是3030台，每台可获台，每台可获利利4040元。该厂确定的目标为：元。该厂确定的目标为：第一优先级：充分利用装配线每周计划开动第一优先级：充分利用装配线每周计划开动4040小时；小时；第二优先级：允许装配线加班，但加班时间每周尽量第二优先级：允许装配线加班，但加班时间每周尽量不超过不超过1010小时；小时；第三优先级：装配电视机的数量尽量满足市场需求。第三优先级：装配电视机的数量尽量满足市场需求。因彩色电视机的利润高，取其权系数为因彩色电视机的利润高，取其权系数为2.2.试建立此

39、问题的目标规划模型，并求解黑白和彩色电试建立此问题的目标规划模型，并求解黑白和彩色电视机的产量。视机的产量。第71页/共112页解：设解：设 分别为黑白分别为黑白和和彩色电视机的产量。彩色电视机的产量。 目标规划模型为目标规划模型为21,xx4,.,1, 0,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddpdpdpzii第72页/共112页从图中可以看到，再考虑具有从图中可以看到，再考虑具有 的目标实现的目标实现后，后， 的取值范围为的取值范围为ABCDABCD。考虑。考虑 的目标要求的目标要求时，因时，因 的权系数大于的权

40、系数大于 ，故先取，故先取 。这时。这时 的取值范围为的取值范围为ABEFABEF。在。在ABEFABEF中，只有中，只有E E点使得点使得 取值最小，故去取值最小，故去E E点为满意解。其坐标点为满意解。其坐标为为(24,26)(24,26)，即该厂每，即该厂每周应装配彩色电视机周应装配彩色电视机2424台，黑白电视机台，黑白电视机2626台。台。21, pp21,xx3p3d4d03d21, xx4d第73页/共112页第74页/共112页所以检验数的正、负首先决定于所以检验数的正、负首先决定于 的系数的系数 的的正、负，若正、负，若 ，则检验数的正、负就决定于，则检验数的正、负就决定于

41、的系数的系数 的正、负，下面可依此类推。的正、负，下面可依此类推。1pj101j2pj2 据此，我们可以总结出求解目标规划问题的单纯据此，我们可以总结出求解目标规划问题的单纯形方法的计算步骤如下：形方法的计算步骤如下：建立初始单纯形表，在表中将检验数行按优先因建立初始单纯形表，在表中将检验数行按优先因子个数分别排成子个数分别排成L L行，置行，置 。 1l第75页/共112页检查该行中是否存在负数，且对应的前检查该行中是否存在负数，且对应的前L-1L-1行行的系数是零。若有，取其中最小者对应的变量为的系数是零。若有，取其中最小者对应的变量为换入变量，转。若无负数，则转。换入变量，转。若无负数，

42、则转。按最小比值规则（按最小比值规则（ 规则）确定换出变量，当规则）确定换出变量，当存在两个和两个以上相同的最小比值时，选取具存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。有较高优先级别的变量为换出变量。按单纯形法进行基变换运算，建立新的计算表，按单纯形法进行基变换运算，建立新的计算表，返回。返回。当当l=Ll=L时，计算结束，表中的解即为满意解。时，计算结束，表中的解即为满意解。否则置否则置l=l+1l=l+1，返回，返回 。第76页/共112页例例3 3：试用单纯形法求解例试用单纯形法求解例2 2所描述的目标规划问题所描述的目标规划问题解：首先将这一问题化为如下

43、标准形式：解：首先将这一问题化为如下标准形式： 3322211)(mindpddpdpZ112. .321xxxts01121ddxx1022221ddxx561083321ddxx)3 , 2 , 1(0,iddxiii第77页/共112页取取 、 、 、 为初始基变量，列出初为初始基变量，列出初始单纯形表。始单纯形表。表13x1d2d3d第78页/共112页 取取 ，检查检验数的，检查检验数的 行，因该行无负检验行，因该行无负检验数，故转。数，故转。 因为因为 ，置，置 ，返回。，返回。 检查发现检验数检查发现检验数 行中有行中有 ， ，因为有，因为有 ，所以，所以 为换入变量，转入。为换

44、入变量，转入。 1l1p31Ll21ll2p1222, 1min2x 按按 规则计算：规则计算： ，所以，所以 为换为换出变量，转入。出变量，转入。 进行换基运算，得到表进行换基运算，得到表2 2。以此类推，直至得到。以此类推，直至得到最终单纯形表为止，如表最终单纯形表为止，如表3 3所示。所示。 2101056,210,111min2d第79页/共112页表2第80页/共112页表3由表由表3 3可知，可知， ， ，为满意解。检查，为满意解。检查检验数行，发现非基变量的检验数为检验数行，发现非基变量的检验数为0 0，这表，这表明该问题存在多重解。明该问题存在多重解。2*1x42x第81页/共

45、112页表表4 4在表在表3 3中，以非基变量中，以非基变量 为换入变量，为换入变量， 为换出变量，为换出变量，经迭代得到表经迭代得到表4 4。 3d1d 从表从表4 4可以看出，可以看出， ， 也是该也是该问题的满意解。问题的满意解。 3/101x3/102x第82页/共112页 案例（提级加新问题） 某公司的员工工资有四级，根据公司某公司的员工工资有四级，根据公司的业务发展情况，准备招收部分新员工，并将部分员工的工的业务发展情况，准备招收部分新员工，并将部分员工的工资提升一级。该公司的员工工资及提级前后的编制表如下，资提升一级。该公司的员工工资及提级前后的编制表如下，其中提级后编制是计划编

46、制，允许有变化，其中其中提级后编制是计划编制，允许有变化，其中1 1级员工中有级员工中有8%8%要退休。公司领导的目标如下：要退休。公司领导的目标如下：1 1）提级后在职员工的工资总额不超过）提级后在职员工的工资总额不超过550550千元；千元；2 2）各级员工不要超过定编人数；）各级员工不要超过定编人数；3)3)为调动积极性，各级员工的升级面不少于现有人数的为调动积极性，各级员工的升级面不少于现有人数的18%18%；4 4）总提级面不大于）总提级面不大于20%20%，但尽可能多提；，但尽可能多提；5 5）4 4级不足编制人数可录用新工人。级不足编制人数可录用新工人。 第83页/共112页问：

47、应如何拟定一具满意的方案，才能接近上述目标？问：应如何拟定一具满意的方案，才能接近上述目标？ 级别级别1 12 23 34 4工资（千元）工资（千元）8 86 64 43 3现有员工数现有员工数1010202040403030编制员工数编制员工数1010222252523030解：（解：（1 1）决策变量：设）决策变量：设x x1 1, ,x x2 2, ,x x3 3, ,x x4 4分别表示提升到分别表示提升到1 1，2 2，3 3级和新录用的员工数。级和新录用的员工数。 偏差变量：偏差变量：d di i+, +, d di i- -为各目标的正、负偏差变量。为各目标的正、负偏差变量。 （

48、2 2）约束条件：）约束条件：1 1） 提级后在职员工的工资总额不超过提级后在职员工的工资总额不超过550550千元；千元；8(10-10 8%+x1)+6(20-x1+x2)+4(40-x2+x3)+ 3(30-x3+x4)+ d1-d1+=550 第84页/共112页 2）各级员工不要超过定编人数各级员工不要超过定编人数 1级有：级有： 10-10 8%+x1+d2-d2+=10 2级有：级有： 20-x1+ x2+d3-d3+=22 3级有：级有： 40-x2+ x3+d4-d4+=52 4级有：级有： 30-x3+ x4+d5-d5+=303）各级员工的升级面不少于现有人数的各级员工的

49、升级面不少于现有人数的18% 对对2级有：级有： x1+d6-d6+=22 18% 对对3级有：级有： x2+d7-d7+=40 18% 对对4级有：级有： x3+d8-d8+=30 18% 4）总提级面人数不大于总提级面人数不大于20%，但尽可能多提，但尽可能多提 x1+ x2+ x3+d9-d9+=100 20% 第85页/共112页)()()(min99487635432211ddpdddpddddpdpZ99487635432211minminminminddZdddZddddZdZ（3 3）目标函数：）目标函数：或者：或者：第86页/共112页五、五、层层 次次 分分 析析 法法（一

50、）层次分析法的基本原理（一）层次分析法的基本原理 层次分析法，又称层次分析法，又称AHP(Analytic AHP(Analytic Hirrarchy Process)Hirrarchy Process)方法，是美国运筹学家萨蒂方法，是美国运筹学家萨蒂(T.Saaty)(T.Saaty)提出的一种多目标、多准则的决策分提出的一种多目标、多准则的决策分析方法。该方法被广泛应用于工程、经济、军事析方法。该方法被广泛应用于工程、经济、军事、政治、外交等领域，解决了诸如系统评价、资、政治、外交等领域，解决了诸如系统评价、资源分配、价格预测、项目选择等许多重要问题，源分配、价格预测、项目选择等许多重要

51、问题，是一种定量分析与定性分析相结合的有效方法。是一种定量分析与定性分析相结合的有效方法。第87页/共112页用层次分析法作决策分析，首先要把问题层用层次分析法作决策分析，首先要把问题层次化。根据问题的性质和要达到的总目标，次化。根据问题的性质和要达到的总目标，将问题分解为不同的组成因素，并按照因素将问题分解为不同的组成因素，并按照因素间的相互影响以及隶属关系按不同层次聚集间的相互影响以及隶属关系按不同层次聚集组合，形成一个多层次的分析结构模型。最组合，形成一个多层次的分析结构模型。最终把系统分析归结为最低层（如决策方案）终把系统分析归结为最低层（如决策方案）相对于最高层（总目标）的相对重要性

52、权值相对于最高层（总目标）的相对重要性权值的确定或相对优劣次序的排序问题，从而为的确定或相对优劣次序的排序问题，从而为决策方案的选择提供依据。决策方案的选择提供依据。第88页/共112页 （二（二) )层次分析法大体分为六个步骤层次分析法大体分为六个步骤1 1）明确问题：为了运用）明确问题：为了运用AHPAHP进行系统分析，首先要对问题进行系统分析，首先要对问题有明确的认识，弄清问题范围、所包含的因素及其相互关有明确的认识，弄清问题范围、所包含的因素及其相互关系、解决问题的目的、是否具有系、解决问题的目的、是否具有AHPAHP所描述的特征。所描述的特征。2 2）建立层次结构模型：将问题中所包含

53、的因素划分为不）建立层次结构模型：将问题中所包含的因素划分为不同层次。例如，对于决策问题，通常可以划分为下面几个同层次。例如，对于决策问题，通常可以划分为下面几个层次：层次：最高层：表示解决问题的目的，称为目标层。最高层：表示解决问题的目的，称为目标层。中间层：表示采取某种措施或政策实现预定目标的涉及的中间层：表示采取某种措施或政策实现预定目标的涉及的中间环节，一般又分为策略层、准则层等。中间环节，一般又分为策略层、准则层等。最低层：表示解决问题的措施或方案，称为措施层或方案最低层：表示解决问题的措施或方案，称为措施层或方案层。如下图所示。层。如下图所示。第89页/共112页决策目标准则1准则

54、1准则m子准则1子准则2子准则k方案1方案2方案n目标层准则层子准则层方案层第90页/共112页3 3）构造判断矩阵）构造判断矩阵针对上一层某元素，对每一层次各个元素的相对重要性进针对上一层某元素，对每一层次各个元素的相对重要性进行两两比较，并给出判断。这些判断用数值表示出来，写行两两比较，并给出判断。这些判断用数值表示出来，写成矩阵形式，即所谓的判断矩阵。成矩阵形式，即所谓的判断矩阵。nnnnnnnnkbbbBbbbBbbbBBBA2122221211211121B其中其中b bijij表示对于表示对于A Ak k而言，而言，B Bi i对对B Bj j的相对重要性，通常的相对重要性，通常b

55、 bijij取取1,2,91,2,9及它们的倒数，其含义为：及它们的倒数，其含义为：第91页/共112页1 1表示表示B Bi i与与B Bj j相比，两者重要性相同相比，两者重要性相同3 3表示表示B Bi i比比B Bj j稍重要稍重要5 5表示表示B Bi i比比B Bj j重要重要7 7表示表示B Bi i比比B Bj j强烈重要强烈重要9 9表示表示B Bi i比比B Bj j极端重要极端重要它们之间的数它们之间的数2 2，4 4，6 6，8 8及各数的倒数有相应的类似意义及各数的倒数有相应的类似意义。显然，对判断矩阵有。显然，对判断矩阵有).,2 , 1,( , 1,1njibbb

56、iijiij因此，对于因此，对于n n阶判断矩阵，我们仅需对阶判断矩阵，我们仅需对n(n-1)/2n(n-1)/2个元素给个元素给出数值。出数值。第92页/共112页4 4）层次单排序及其一致性检验）层次单排序及其一致性检验 所谓层次单排序，即把同一层次相应元素对于上一所谓层次单排序，即把同一层次相应元素对于上一层次某元素相对重要性的排序权值求出来。其方法是计算层次某元素相对重要性的排序权值求出来。其方法是计算判断矩阵判断矩阵A A的满足等式的满足等式 的最大特征值的最大特征值 和对应的特征向量和对应的特征向量W W，这个特征向量就是单排序权值。，这个特征向量就是单排序权值。WAWmaxmax

57、 可以证明，对于可以证明，对于n n阶判断矩阵，其最大特征根阶判断矩阵，其最大特征根 为单根，且为单根，且 ， 所对应的特征向量均由正数所对应的特征向量均由正数组成。特别，当判断矩阵具有完全一致性时组成。特别，当判断矩阵具有完全一致性时, ,有有 这里，所谓完全一致性是指对于判断矩阵来说，存在这里，所谓完全一致性是指对于判断矩阵来说，存在maxnmaxmaxnmax),.,2 , 1,(nkjibbbjkikij第93页/共112页1.451.451.411.411.321.321.241.241.121.120.900.900.850.850.000.000.000.00RIRI9 98 8

58、7 76 65 54 43 32 21 1阶数阶数为检验判断矩阵的一致性，需要计算一致性指标为检验判断矩阵的一致性，需要计算一致性指标1maxnnCI此外，还需要判断矩阵的平均随机一致性指标此外，还需要判断矩阵的平均随机一致性指标RIRI。对于。对于1 1至至9 9阶矩阵，阶矩阵，RIRI的值如下表。的值如下表。 在这里，对于在这里，对于1,21,2阶判断矩阵，阶判断矩阵，RIRI只是形式上的，只是形式上的，因为因为1 1，2 2阶判断矩阵总具有完全一致性，当阶数大于阶判断矩阵总具有完全一致性，当阶数大于2 2时时，判断矩阵的一致性指标，判断矩阵的一致性指标CICI与同阶平均随机一致性指标与同

59、阶平均随机一致性指标RIRI之比称谓随机一致性比率，记为之比称谓随机一致性比率，记为CRCR，CR=CI/RI0.10CR=CI/RI0.10时，时，即认为判断矩阵具有满意的一致性，否则就需要调整判断即认为判断矩阵具有满意的一致性，否则就需要调整判断矩阵，使其具有满意的一致性。矩阵，使其具有满意的一致性。第94页/共112页5 5）层次总排序）层次总排序 计算同一层次所有元素对于最高层相对重计算同一层次所有元素对于最高层相对重要性的排序权值，称为层次总排序。这一过程是要性的排序权值，称为层次总排序。这一过程是最高层次到最低层次逐层进行的。若上一层次最高层次到最低层次逐层进行的。若上一层次A A

60、包包含含m m个元素个元素A A1 1,A,A2 2,A,Am m，其层次总排序权值分别为，其层次总排序权值分别为a a1 1,a,a2 2,a,am m，下一层次，下一层次B B包含包含n n个元素个元素B B1 1,B,B2 2,B,Bn n，它们对于元素它们对于元素A Aj j的层次单排序权值分别为的层次单排序权值分别为b b1j1j,b,b2j2j,b,bnjnj（当（当B Bk k与与A Aj j无关系时无关系时,b,bkjkj=0=0），此时），此时，层次总排序权值为，层次总排序权值为第95页/共112页B B层次总排序权重层次总排序权重层次层次mAAA21maaa21nBBB21