数学建模培训多目标规划.ppt

《数学建模培训多目标规划.ppt》由会员分享，可在线阅读，更多相关《数学建模培训多目标规划.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多多 目目 标标 规规 划划数学建模培训数学建模培训2012.07多多 目目 标标 规规 化化 模模 型型n多目标规划是数学规划的一个分支。研究多多目标规划是数学规划的一个分支。研究多于一个的目标函数在给定区域上的最优化。于一个的目标函数在给定区域上的最优化。又称多目标最优化。通常记为又称多目标最优化。通常记为MOP(multi-MOP(multi-objective programming)objective programming)。n在很多实际问题中，例如经济、管理、军事、在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好科学和工程设计等领域，衡量一个方案的好

2、坏往往难以用一个指标来判断，而需要用多坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方甚至是矛盾的。因此有许多学者致力于这方面的研究。面的研究。例如例如,对企业产品的生产管理对企业产品的生产管理,既希望达到高利润既希望达到高利润,又又希望优质和低消耗希望优质和低消耗,还希望减少对环境的污染等。这就还希望减少对环境的污染等。这就是一个多目标决策的问题。又如选购一个好的计算机系是一个多目标决策的问题。又如选购一个好的计算机系统统,似乎只有一个目标似乎只有一个目标,但由于要从多方面去反映但由于要从

3、多方面去反映,要用要用多个不同的准则来衡量多个不同的准则来衡量,比如比如,性能要好性能要好,维护要容易维护要容易,费费用要省。这些准则自然构成了多个目标用要省。这些准则自然构成了多个目标,故也是一个多故也是一个多目标决策问题。一般来说目标决策问题。一般来说,多目标决策问题有两类。一多目标决策问题有两类。一类是多目标规划问题类是多目标规划问题,其对象是在管理决策过程中求解其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方案。另一类是多目使多个目标都达到满意结果的最优方案。另一类是多目标优选问题标优选问题,其对象是在管理决策过程中根据多个目标其对象是在管理决策过程中根据多个目标或多个准则

4、衡量和得出各种备选方案的优先等级与排序。或多个准则衡量和得出各种备选方案的优先等级与排序。多目标决策由于考虑的目标多多目标决策由于考虑的目标多,有些目标之间又彼有些目标之间又彼此有矛盾此有矛盾,这就使多目标问题成为一个复杂而困难这就使多目标问题成为一个复杂而困难的问题的问题.但由于客观实际的需要但由于客观实际的需要,多目标决策问题多目标决策问题越来越受到重视越来越受到重视,因而出现了许多解决此决策问题因而出现了许多解决此决策问题的方法的方法.一般来说一般来说,其基本途径是其基本途径是,把求解多目标问把求解多目标问题转化为求解单目标问题题转化为求解单目标问题.其主要步骤是其主要步骤是,先转化先转

5、化为单目标问题为单目标问题,然后利用单目标模型的方法然后利用单目标模型的方法,求出求出单目标模型的最优解单目标模型的最优解,以此作为多目标问题的解以此作为多目标问题的解.化多目标问题为单目标问题的方法大致可分化多目标问题为单目标问题的方法大致可分为两类为两类,一类是转化为一个单目标问题一类是转化为一个单目标问题,另一类是另一类是转化为多个单目标问题转化为多个单目标问题,关键是如何转化关键是如何转化.以下以下,我们会介绍几种主要的转化方法我们会介绍几种主要的转化方法:主要主要目标法、线性加权和法、字典序法、步骤法。目标法、线性加权和法、字典序法、步骤法。一、多一、多 目标目标 规规 划划 及及

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

7、衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花得以实现的各个准则，如食品的味道要好，质量要好，花费要少。费要少。n多目标规划中的方案即为决策变量，也称为多目标问题的多目标规划中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。有其特征或特性，称之为属性。（一）任何多目标规划问题，都由两个（一）任何多目标规划问题，都由两个基本部分组成基本部分组成:（1 1）两个以上的目

8、标函数；）两个以上的目标函数；（2 2）若干个约束条件。）若干个约束条件。（二）对于多目标规划问题，可以将（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：其数学模型一般地描写为如下形式：（2 2）（1 1）式中：式中：为决策变量向量。为决策变量向量。（三）多目标规划解的特点（三）多目标规划解的特点 对对于于上上述述多多目目标标规规划划问问题题，求求解解就就意意味味着着需需要要做出如下的复合选择：做出如下的复合选择：（1 1）每一个目标函数取什么值，原问题可以得）每一个目标函数取什么值，原问题可以得到最满意的解决？到最满意的解决？（2 2）每一个决策变量取什么值，原问题可以得）每

9、一个决策变量取什么值，原问题可以得到最满意的解决到最满意的解决？多目标规划问题的求解不能只追求一个目标的多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。最优化（最大或最小），而不顾其它目标。当目标函数处于冲突状态时，就不会当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。（又称非支配解或帕累托解）。非劣解：可以用图非劣解：可以用图3 3说明。说明。图图3 多目标规划的劣解与非劣解多目标规划的劣解与非劣解二、多二、多

10、目目 标标 规规 划划 问问 题题 的的 建建 模模 方方 法法 为为了了求求得得多多目目标标规规划划问问题题的的非非劣劣解解，常常常常需需要要将将多多目目标标规规划划问问题题转转化化为为单单目目标标规规划划问问题题去去处处理理。实实现现这这种种转转化化，有有如如下下几种建模方法。几种建模方法。（三）约束模型三）约束模型 理论依据理论依据 ：若规划问题的某一目标可以给：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约作为约束条件而被排除出目标组，进入约束条件组中。束条件组中。假如，除第一个目标外，其余目标都可

11、以假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：划问题就可以转化为单目标规划问题：用目标达到法求解多目标规划的计用目标达到法求解多目标规划的计算过程，可以通过调用算过程，可以通过调用MatlabMatlab软件系统软件系统优化工具箱中的优化工具箱中的fgoalattainfgoalattain函数实现。函数实现。三、多目标规划问题的求解(化多为少的方法)1 1、主要目标法、主要目标法 在有些多目标决策问题中，各种目标的重在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最要性

12、程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。余的目标则称为非主要目标。例如，在上述多目标问题中，假定例如，在上述多目标问题中，假定f1(X)为主要为主要目标，其余目标，其余p p-1-1个为非主要目标。这时，希望个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足主要目标达到极大值，并要求其余的目标满足一定的条件，即一定的条件，即例题例题 某工厂在一个计划期内生产甲、乙两种产品，某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗各产品都要消耗A A，B B，C C三种不同的资源。

13、每件产品三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？才能使利润和产值都最大，且造成的污染最小？甲甲乙乙资源限量资源限量资源资源A A单位消耗单位消耗资源资源B B单位消耗单位消耗资源资源C C单位消耗单位消耗9 94 43 34 45 51010240240200200300300单位产品的价格单位产品的价格40

14、0400600600单位产品的利润单位产品的利润7070120120单位产品的污染单位产品的污染3 32 2解：问题的多目标模型如下解：问题的多目标模型如下对于此模型的三个目标，工对于此模型的三个目标，工厂确定利润最大为主要目标。厂确定利润最大为主要目标。另两个目标则通过预测预先另两个目标则通过预测预先给定的希望达到的目标值转给定的希望达到的目标值转化为约束条件。经研究，工化为约束条件。经研究，工厂认为总产值至少应达到厂认为总产值至少应达到2000020000个单位，而污染控制个单位，而污染控制在在9090个单位以下，即个单位以下，即由主要目标法化为单目标问题由主要目标法化为单目标问题用单纯形

15、法求得其最优解为用单纯形法求得其最优解为2 2、线性加权和目标规划、线性加权和目标规划在上述目标规划中，假定在上述目标规划中，假定f1 1(X),(X),f2 2(X),(X),fp p(X)(X)具有具有相同的量纲相同的量纲,按照一定的规则分别给按照一定的规则分别给f fi i赋予相同的权赋予相同的权系数系数i，作线性加权和评价函数，作线性加权和评价函数则多目标问题化为如下的单目标问题则多目标问题化为如下的单目标问题例如，某公司计划购进一批新卡车，可供选择的卡车有例如，某公司计划购进一批新卡车，可供选择的卡车有如下如下4 4种类型：种类型：A1A1，A2A2，A3A3，A4A4。现考虑。现考

16、虑6 6个方案属性：个方案属性：维修期限维修期限f1 1，每，每100100升汽油所跑的里数升汽油所跑的里数f2 2，最大载重吨数，最大载重吨数f3 3，价格（万元），价格（万元）f4 4，可靠性，可靠性f5 5，灵敏性，灵敏性f6 6。这。这4 4种型号的卡种型号的卡车分别关于目标属性的指标值车分别关于目标属性的指标值fijij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先对不同度量单位和不同数量级的指标值进行标准首先对不同度

17、量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：化处理。先将定性指标定量化：变换后的指标值矩阵为：变换后的指标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001设权系数向量为设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则则故最优方案为选购故最优方案为选购A3A3型卡车型卡车4 4、步骤法（、步骤法（STEMSTEM法）法）这是一种交互方法，其求解过程通过分析者与决策这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行

18、，故称步骤法。者之间的对话逐步进行，故称步骤法。步骤法的基本思想是，首先需要求出原多目标问题步骤法的基本思想是，首先需要求出原多目标问题的一组理想解的一组理想解(f(f1 1*,f*,f2 2*,f*,fk k*)*)。实际上，这些解。实际上，这些解f fi i*(i=1,2,k)*(i=1,2,k)无法同时达到，但可以当作一组理想的无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中

19、去重新计算，直到决策的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。者得到满意的解。把上述计算结果列入下表把上述计算结果列入下表例题：例题：某公司考虑生产两种光电太阳能电池：产品甲和某公司考虑生产两种光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性污染。因产品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收射性污染。已知在一个生产周期内，每单位甲产品的收益是益是1 1元，每单位乙产品的收益是元，每单位乙产品的收益是3 3元

20、。而放射性污染的元。而放射性污染的数量，每单位甲产品是数量，每单位甲产品是1.51.5个单位个单位,每单位乙产品是每单位乙产品是1 1个单个单位位.由于机器能力由于机器能力(小时小时)、装配能力（人时）和可用的原、装配能力（人时）和可用的原材料（单位）的限制，约束条件是材料（单位）的限制，约束条件是目标有两个目标有两个:一是利润最大一是利润最大,二是污染最小二是污染最小.该问题该问题的多目标规划模型如下的多目标规划模型如下:解解:首先首先,分别求解两个单目标问题的最优解分别求解两个单目标问题的最优解,由它们由它们得到的目标函数值组成理想解得到的目标函数值组成理想解.由此由此,构造支付表构造支付

21、表Xf1*f2*(7,13)(0,0)460-23.50由此计算两个目标与理由此计算两个目标与理想值偏离的权重：想值偏离的权重：解下列线性规划问题解下列线性规划问题:进行下一轮迭代进行下一轮迭代.首先设首先设2 2=0,=0,并计算得并计算得1 1=1.=1.将将模型修改为模型修改为由此求得由此求得:决策者把这一结果与前一轮的解及理想值作比较决策者把这一结果与前一轮的解及理想值作比较,认为两个目标值都比较满意认为两个目标值都比较满意,则迭代结束则迭代结束.线线 性性 目目 标标 规规 划划 模模 型型 线线性性规规划划问问题题都都是是处处理理单单个个目目标标的的情情况况，但但是是在在现现实实世

22、世界界中中有有许许多多问问题题具具有有多多个个目目标标，这这些些目目标标的的重重要要性性各各不不相相同同，往往往往有有不不同同的的量量纲纲，有有的的目目标标相相互互依依赖赖，例例如如决决策策者者既既希希望望实实现现利利润润最最大大，又又希希望望实实现现产产值值最最大大；有有的的相相互互抵抵触触，如如决决策策者者既既希希望望充充分分利利用用资资源源，又又不不希希望望超超越越资资源源限限量量。而而决决策策者者希希望望在在某某些些限限制制条条件件下下，依依次次实实现现这这些些目目标标。这这就就是是目目标标规规划划所所要要解解决决的的问问题题。当当所所有有的的目目标标函函数数和和约约束束条条件件都都是

23、是线线性性时时，我我们们称称其其为为线线性性目目标标规规划划问问题题。在在这这里里我我们们主主要要讨讨论论线性目标规划问题。线性目标规划问题。一、线性目标规划模型的建立一、线性目标规划模型的建立 例例1 1：某某一一个个企企业业利利用用某某种种原原材材料料和和现现有有设设备备可可生生产产甲甲、乙乙两两种种产产品品，其其中中，甲甲、乙乙两两种种产产品品的的单单价价分分别别为为8 8元元和和1010元元；生生产产单单位位甲甲、乙乙两两种种产产品品需需要要消消耗耗的的原原材材料料分分别别为为2 2个个单单位位和和1 1个个单单位位，需需要要占占用用的的设设备备分分别别为为1 1台台时时和和2 2台台

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

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

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

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

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

29、为赋予 优先因子的第优先因子的第 个目标的正、负偏个目标的正、负偏差变量的权系数，差变量的权系数，为第为第 个目标的预期值，个目标的预期值，为决策变量，为决策变量，、分别为第分别为第 个目标的正、负偏差变量，个目标的正、负偏差变量，（2525）式为目标函数，（）式为目标函数，（2626）式为目标约束，（）式为目标约束，（2727）式）式为绝对约束，（为绝对约束，（2828）式和（）式和（2929）式为非负约束，）式为非负约束，、分别为目标约束和绝对约束中决策变量的系数及约束值。分别为目标约束和绝对约束中决策变量的系数及约束值。其中，其中，；。图解法求解例图解法求解例2 2首先考虑具有首先考虑具

30、有 优先因子优先因子的目标的实现，在目标函的目标的实现，在目标函数中要求实现数中要求实现 ，图，图中可以满足中可以满足 .这时这时 的取值只能在的取值只能在OBCOBC的边界和的边界和内部取得。内部取得。接着考虑接着考虑 优先因子的目优先因子的目标的实现，在目标函数中标的实现，在目标函数中要求实现要求实现 ，当，当时时 ，其值，其值 可可在线段在线段EDED上取得。上取得。最后考虑最后考虑 优先因子的目标优先因子的目标的实现，在目标函数中要求实的实现，在目标函数中要求实现现 ，当，当 时，其值时，其值 缩小到在线段缩小到在线段GDGD上取得上取得.这就这就是该目标规划问题的解是该目标规划问题的

31、解.G.G和和D D点凸组合都是此目标规划的解点凸组合都是此目标规划的解.注注：在目标规划问题求解时，把绝对约束作最高优先级考虑。：在目标规划问题求解时，把绝对约束作最高优先级考虑。在此例中，能依先后次序都满足在此例中，能依先后次序都满足 因因而而 。但是大多数问题中并非如此，还可能出现非可行解，。但是大多数问题中并非如此，还可能出现非可行解，故将目标规划问题的最优解成为满意解。故将目标规划问题的最优解成为满意解。例如例如，某电视机厂装配黑白和彩色两种电视机，每某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线装配一台电视机需占用装配线1 1小时，装配线每周计划小时，装配线每周计

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

33、权系数为因彩色电视机的利润高，取其权系数为2.2.试建立此问题的目标规划模型，并求解黑白和彩色电试建立此问题的目标规划模型，并求解黑白和彩色电视机的产量。视机的产量。解：设解：设 分别为黑白分别为黑白和和彩色电视机的产量。彩色电视机的产量。目标规划模型为目标规划模型为从图中可以看到，再考虑具有从图中可以看到，再考虑具有 的目标实现的目标实现后，后，的取值范围为的取值范围为ABCDABCD。考虑。考虑 的目标要求的目标要求时，因时，因 的权系数大于的权系数大于 ，故先取，故先取 。这时。这时 的取值范围为的取值范围为ABEFABEF。在。在ABEFABEF中，只有中，只有E E点使得点使得 取值

34、最小，故去取值最小，故去E E点为满意解。其坐标点为满意解。其坐标为为(24,26)(24,26)，即该厂每，即该厂每周应装配彩色电视机周应装配彩色电视机2424台，黑白电视机台，黑白电视机2626台。台。所以检验数的正、负首先决定于所以检验数的正、负首先决定于 的系数的系数 的正、的正、负，若负，若 ，则检验数的正、负就决定于，则检验数的正、负就决定于 的系数的系数 的正、负，下面可依此类推。的正、负，下面可依此类推。据据此此，我我们们可可以以总总结结出出求求解解目目标标规规划划问问题题的的单单纯纯形方法的计算步骤如下：形方法的计算步骤如下：建建立立初初始始单单纯纯形形表表，在在表表中中将将

35、检检验验数数行行按按优优先先因因子个数分别排成子个数分别排成L L行，置行，置 。检检查查该该行行中中是是否否存存在在负负数数，且且对对应应的的前前L-1L-1行行的的系系数数是是零零。若若有有，取取其其中中最最小小者者对对应应的的变变量量为为换入变量，转换入变量，转。若无负数，则转。若无负数，则转。按按最最小小比比值值规规则则（规规则则）确确定定换换出出变变量量，当当存存在在两两个个和和两两个个以以上上相相同同的的最最小小比比值值时时，选选取取具具有较高优先级别的变量为换出变量。有较高优先级别的变量为换出变量。按按单单纯纯形形法法进进行行基基变变换换运运算算，建建立立新新的的计计算算表表，返

36、回返回。当当l=Ll=L时时，计计算算结结束束，表表中中的的解解即即为为满满意意解解。否则置否则置l=l+1l=l+1，返回，返回 。例例3 3：试用单纯形法求解例试用单纯形法求解例2 2所描述的目标规划问题所描述的目标规划问题解：首先将这一问题化为如下标准形式：解：首先将这一问题化为如下标准形式：取取 、为初始基变量，列出初为初始基变量，列出初始单纯形表。始单纯形表。表表1 取取 ，检检查查检检验验数数的的 行行，因因该该行行无无负负检检验验数，故转数，故转。因为因为 ，置，置 ，返回，返回。检查发现检验数检查发现检验数 行中有行中有 ，因为有，因为有 ，所以，所以 为换入变量，转入为换入变

37、量，转入。按按 规规则则计计算算：，所所以以 为为换换出变量，转入出变量，转入。进行换基运算，得到表进行换基运算，得到表2 2。以此类推，直至得到最。以此类推，直至得到最终单纯形表为止，如表终单纯形表为止，如表3 3所示。所示。表表2表表3由由表表3 3可可知知，为为满满意意解解。检检查查检检验验数数行行，发发现现非非基基变变量量的的检检验验数数为为0 0，这这表表明该问题存在多重解。明该问题存在多重解。表表4 4在表在表3 3中，以非基变量中，以非基变量 为换入变量，为换入变量，为换出变量，为换出变量，经迭代得到表经迭代得到表4 4。从表从表4 4可以看出，可以看出，也是该问也是该问题的满意

38、解。题的满意解。案例（提级加新问题）案例（提级加新问题）某公司的员工工资有四级，根据公司某公司的员工工资有四级，根据公司的业务发展情况，准备招收部分新员工，并将部分员工的工的业务发展情况，准备招收部分新员工，并将部分员工的工资提升一级。该公司的员工工资及提级前后的编制表如下，资提升一级。该公司的员工工资及提级前后的编制表如下，其中提级后编制是计划编制，允许有变化，其中其中提级后编制是计划编制，允许有变化，其中1 1级员工中有级员工中有8%8%要退休。公司领导的目标如下：要退休。公司领导的目标如下：1 1）提级后在职员工的工资总额不超过）提级后在职员工的工资总额不超过550550千元；千元；2

39、2）各级员工不要超过定编人数；）各级员工不要超过定编人数；3)3)为调动积极性，各级员工的升级面不少于现有人数的为调动积极性，各级员工的升级面不少于现有人数的18%18%；4 4）总提级面不大于）总提级面不大于20%20%，但尽可能多提；，但尽可能多提；5 5）4 4级不足编制人数可录用新工人。级不足编制人数可录用新工人。问：应如何拟定一具满意的方案，才能接近上述目标？问：应如何拟定一具满意的方案，才能接近上述目标？级别级别1 12 23 34 4工资（千元）工资（千元）8 86 64 43 3现有员工数现有员工数1010202040403030编制员工数编制员工数10102222525230

40、30解解：（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-为各目标的正、负偏差变量。为各目标的正、负偏差变量。（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 2）各级员工不要超过定编人数各级员工不要超过定编人数1级有：

41、级有：10-10 8%+x1+d2-d2+=102级有：级有：20-x1+x2+d3-d3+=223级有：级有：40-x2+x3+d4-d4+=524级有：级有：30-x3+x4+d5-d5+=303）各级员工的升级面不少于现有人数的各级员工的升级面不少于现有人数的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%（3 3）目标函数：）目标函数：或者：或者：五、五、层层次

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

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

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

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

46、n目标层目标层准则层准则层子准则层子准则层方案层方案层3 3）构造判断矩阵）构造判断矩阵针对上一层某元素，对每一层次各个元素的相对重要性进针对上一层某元素，对每一层次各个元素的相对重要性进行两两比较，并给出判断。这些判断用数值表示出来，写行两两比较，并给出判断。这些判断用数值表示出来，写成矩阵形式，即所谓的判断矩阵。成矩阵形式，即所谓的判断矩阵。其中其中b bijij表示对于表示对于A Ak k而言，而言，B Bi i对对B Bj j的相对重要性，通常的相对重要性，通常b bijij取取1,2,91,2,9及它们的倒数，其含义为：及它们的倒数，其含义为：1 1表示表示B Bi i与与B Bj

47、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及各数的倒数有相应的类似意义。及各数的倒数有相应的类似意义。显然，对判断矩阵有显然，对判断矩阵有因此，对于因此，对于n n阶判断矩阵，我们仅需对阶判断矩阵，我们仅需对n(n-1)/2n(n-1)/2个元素给个元素给出数值。出数值。4 4）层次单排序及其一致性检验）层次单排序及其一致性

48、检验 所谓层次单排序，即把同一层次相应元素对于上一所谓层次单排序，即把同一层次相应元素对于上一层次某元素相对重要性的排序权值求出来。其方法是计算层次某元素相对重要性的排序权值求出来。其方法是计算判断矩阵判断矩阵A A的满足等式的满足等式 的最大特征值的最大特征值 和对应的特征向量和对应的特征向量W W，这个特征向量就是单排序权值。，这个特征向量就是单排序权值。可以证明，对于可以证明，对于n n阶判断矩阵，其最大特征根阶判断矩阵，其最大特征根 为单根，且为单根，且 ，所对应的特征向量均由正数所对应的特征向量均由正数组成。特别，当判断矩阵具有完全一致性时组成。特别，当判断矩阵具有完全一致性时,有有

49、 这里，所谓完全一致性是指对于判断矩阵来说，存在这里，所谓完全一致性是指对于判断矩阵来说，存在1.451.451.411.411.321.321.241.241.121.120.900.900.850.850.000.000.000.00RIRI9 98 87 76 65 54 43 32 21 1阶数阶数为检验判断矩阵的一致性，需要计算一致性指标为检验判断矩阵的一致性，需要计算一致性指标此外，还需要判断矩阵的平均随机一致性指标此外，还需要判断矩阵的平均随机一致性指标RIRI。对于。对于1 1至至9 9阶矩阵，阶矩阵，RIRI的值如下表。的值如下表。在这里，对于在这里，对于1,21,2阶判断矩

50、阵，阶判断矩阵，RIRI只是形式上的，只是形式上的，因为因为1 1，2 2阶判断矩阵总具有完全一致性，当阶数大于阶判断矩阵总具有完全一致性，当阶数大于2 2时，时，判断矩阵的一致性指标判断矩阵的一致性指标CICI与同阶平均随机一致性指标与同阶平均随机一致性指标RIRI之之比称谓随机一致性比率，记为比称谓随机一致性比率，记为CRCR，CR=CI/RI0.10CR=CI/RI0.10时，即时，即认为判断矩阵具有满意的一致性，否则就需要调整判断矩认为判断矩阵具有满意的一致性，否则就需要调整判断矩阵，使其具有满意的一致性。阵，使其具有满意的一致性。5 5）层次总排序）层次总排序 计算同一层次所有元素对