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

《数学建模培训多目标规划.pptx》由会员分享，可在线阅读，更多相关《数学建模培训多目标规划.pptx（112页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

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

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

5、了问题要达到的总目标。如确定最满意的看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。质量要好，花费要少。多目标规划中的方案即为决策变量，也称为多目标问题多目标规划中的方案即为决策变量，也称为多

6、目标问题的解。备选方案即决策问题的可行解。在多目标决策中，的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。方案有其特征或特性，称之为属性。第3页/共112页 （一）任何多目标规划问题，都由两个基本部分组成（一）任何多目标规划问题，都由两个基本部分组成:（1 1）两个以上的目标函数；）两个以上的目标函数；（2 2）若干个约束条件。）若干个约束条件。（二）对于多目标规划问题，可以将（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：其数学模型一般地描写为如下

7、形式：第4页/共112页（2 2）（1 1）式中：式中：为决策变量向量。为决策变量向量。第5页/共112页第6页/共112页第7页/共112页 （三）多目标规划解的特点（三）多目标规划解的特点 对对于于上上述述多多目目标标规规划划问问题题，求求解解就就意意味味着着需需要要做出如下的复合选择：做出如下的复合选择：（1 1）每一个目标函数取什么值，原问题可以得）每一个目标函数取什么值，原问题可以得到最满意的解决？到最满意的解决？（2 2）每一个决策变量取什么值，原问题可以得）每一个决策变量取什么值，原问题可以得到最满意的解决到最满意的解决？多目标规划问题的求解不能只追求一个目标的多目标规划问题的求

8、解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。最优化（最大或最小），而不顾其它目标。第8页/共112页第9页/共112页第10页/共112页第11页/共112页 当目标函数处于冲突状态时，就不会当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。（又称非支配解或帕累托解）。第12页/共112页非劣解：可以用图非劣解：可以用图3 3说明。说明。图3 多目标规划的劣解与非劣解第13页/共112页第14页/共112页第15页/共112页二、

9、多二、多 目目 标标 规规 划划 问问 题题 的的 建建 模模 方方 法法 为为了了求求得得多多目目标标规规划划问问题题的的非非劣劣解解，常常常常需需要要将将多多目目标标规规划划问问题题转转化化为为单目标规划问题去处理。实现这种转化，有如下几种建模方法。单目标规划问题去处理。实现这种转化，有如下几种建模方法。第16页/共112页第17页/共112页第18页/共112页第19页/共112页第20页/共112页（三）约束模型三）约束模型 理论依据理论依据 ：若规划问题的某一目标可以给：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以出一个可供选择的范围，则该目标就可以作为约束条件而被

10、排除出目标组，进入约作为约束条件而被排除出目标组，进入约束条件组中。束条件组中。假如，除第一个目标外，其余目标都可以假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：划问题就可以转化为单目标规划问题：第21页/共112页第22页/共112页第23页/共112页第24页/共112页第25页/共112页第26页/共112页 用目标达到法求解多目标规划的计用目标达到法求解多目标规划的计算过程，可以通过调用算过程，可以通过调用MatlabMatlab软件系统软件系统优化工具箱中的优化工具箱中的fgoalatta

11、infgoalattain函数实现。函数实现。第27页/共112页三、多目标规划问题的求解(化多为少的方法)1 1、主要目标法、主要目标法 在有些多目标决策问题中，各种目标的重在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最要性程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。余的目标则称为非主要目标。第28页/共112页例如，在上述多目标问题中，假定例如，在上述多目标问题中，假定f1(X)为主要为主要目标，其余目标，其余p p-1-1个为非主要目标。这时，希望个为非主要目标

12、。这时，希望主要目标达到极大值，并要求其余的目标满足主要目标达到极大值，并要求其余的目标满足一定的条件，即一定的条件，即第29页/共112页例题例题 某工厂在一个计划期内生产甲、乙两种产品，某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗各产品都要消耗A A，B B，C C三种不同的资源。每件产品三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，假定产品能全部销售出去，问每期怎样安排生产，才能使利

13、润和产值都最大，且造成的污染最小？才能使利润和产值都最大，且造成的污染最小？甲甲乙乙资源限量资源限量资源资源A A单位消耗单位消耗资源资源B B单位消耗单位消耗资源资源C C单位消耗单位消耗9 94 43 34 45 51010240240200200300300单位产品的价格单位产品的价格400400600600单位产品的利润单位产品的利润7070120120单位产品的污染单位产品的污染3 32 2第30页/共112页解：问题的多目标模型如下解：问题的多目标模型如下对于此模型的三个目标，工对于此模型的三个目标，工厂确定利润最大为主要目标。厂确定利润最大为主要目标。另两个目标则通过预测预先另两

14、个目标则通过预测预先给定的希望达到的目标值转给定的希望达到的目标值转化为约束条件。经研究，工化为约束条件。经研究，工厂认为总产值至少应达到厂认为总产值至少应达到2000020000个单位，而污染控制个单位，而污染控制在在9090个单位以下，即个单位以下，即第31页/共112页由主要目标法化为单目标问题由主要目标法化为单目标问题用单纯形法求得其最优解为用单纯形法求得其最优解为第32页/共112页2 2、线性加权和目标规划、线性加权和目标规划在上述目标规划中，假定在上述目标规划中，假定f1 1(X),(X),f2 2(X),(X),fp p(X)(X)具有具有相同的量纲相同的量纲,按照一定的规则分

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

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

17、A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001第37页/共112页设权系数向量为设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则则故最优方案为选购故最优方案为选购A3A3型卡车型卡车第38页/共112页第39页/共112页第40页/共112页第41页/共112页第42页/共112页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、条件中去重新计算，直到决策者得到满意的解。者得到满意的解。第43页/共112页第44页/共112页把上述计算结果列入下表把上述计算结果列入下表第45页/共112页第46页/共112页第47页/共112页例题：例题：某公司考虑生产两种光电太阳能电池：产品甲和某公司考虑生产两种光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性污染。因产品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收射性污染。已知在一个生产周期内，每单位甲产品的收益是益是1 1

20、元，每单位乙产品的收益是元，每单位乙产品的收益是3 3元。而放射性污染的元。而放射性污染的数量，每单位甲产品是数量，每单位甲产品是1.51.5个单位个单位,每单位乙产品是每单位乙产品是1 1个单个单位位.由于机器能力由于机器能力(小时小时)、装配能力（人时）和可用的原、装配能力（人时）和可用的原材料（单位）的限制，约束条件是材料（单位）的限制，约束条件是第48页/共112页目标有两个目标有两个:一是利润最大一是利润最大,二是污染最小二是污染最小.该问题该问题的多目标规划模型如下的多目标规划模型如下:第49页/共112页解解:首先首先,分别求解两个单目标问题的最优解分别求解两个单目标问题的最优解

21、,由它们由它们得到的目标函数值组成理想解得到的目标函数值组成理想解.第50页/共112页由此由此,构造支付表构造支付表Xf1*f2*(7,13)(0,0)460-23.50由此计算两个目标与理由此计算两个目标与理想值偏离的权重：想值偏离的权重：解下列线性规划问题解下列线性规划问题:第51页/共112页第52页/共112页进行下一轮迭代进行下一轮迭代.首先设首先设2 2=0,=0,并计算得并计算得1 1=1.=1.将将模型修改为模型修改为第53页/共112页由此求得由此求得:决策者把这一结果与前一轮的解及理想值作比较决策者把这一结果与前一轮的解及理想值作比较,认为两个目标值都比较满意认为两个目标

22、值都比较满意,则迭代结束则迭代结束.第54页/共112页线线 性性 目目 标标 规规 划划 模模 型型 线线性性规规划划问问题题都都是是处处理理单单个个目目标标的的情情况况，但但是是在在现现实实世世界界中中有有许许多多问问题题具具有有多多个个目目标标，这这些些目目标标的的重重要要性性各各不不相相同同，往往往往有有不不同同的的量量纲纲，有有的的目目标标相相互互依依赖赖，例例如如决决策策者者既既希希望望实实现现利利润润最最大大，又又希希望望实实现现产产值值最最大大；有有的的相相互互抵抵触触，如如决决策策者者既既希希望望充充分分利利用用资资源源，又又不不希希望望超超越越资资源源限限量量。而而决决策策

23、者者希希望望在在某某些些限限制制条条件件下下，依依次次实实现现这这些些目目标标。这这就就是是目目标标规规划划所所要要解解决决的的问问题题。当当所所有有的的目目标标函函数数和和约约束束条条件件都都是是线线性性时时，我我们们称称其其为为线线性性目目标标规规划划问问题题。在在这这里我们主要讨论线性目标规划问题。里我们主要讨论线性目标规划问题。第55页/共112页一、线性目标规划模型的建立一、线性目标规划模型的建立 例例1 1：某某一一个个企企业业利利用用某某种种原原材材料料和和现现有有设设备备可可生生产产甲甲、乙乙两两种种产产品品，其其中中，甲甲、乙乙两两种种产产品品的的单单价价分分别别为为8 8元

24、元和和1010元元；生生产产单单位位甲甲、乙乙两两种种产产品品需需要要消消耗耗的的原原材材料料分分别别为为2 2个个单单位位和和1 1个个单单位位，需需要要占占用用的的设设备备分分别别为为1 1台台时时和和2 2台台时时；原原材材料料拥拥有有量量为为1111个个单单位位；可可利利用用的的设设备备总总台台时时为为1010台台时时。试试问问：如如何何确定其生产方案？确定其生产方案？第56页/共112页第57页/共112页 但但是是，在在实实际际决决策策时时，企企业业领领导导者者必必须须考考虑虑市市场场等一系列其它条件，如：等一系列其它条件，如：根根据据市市场场信信息息，甲甲种种产产品品的的需需求求

25、量量有有下下降降的的趋趋势势，因此甲种产品的产量不应大于乙种产品的产量。因此甲种产品的产量不应大于乙种产品的产量。超过计划供应的原材料，需用高价采购，这就会使超过计划供应的原材料，需用高价采购，这就会使生产成本增加。生产成本增加。应尽可能地充分利用设备的有效台时，但不希望加应尽可能地充分利用设备的有效台时，但不希望加班。班。应尽可能达到并超过计划产值指标应尽可能达到并超过计划产值指标5656元。元。这样，该企业生产方案的确定，便成为一个多这样，该企业生产方案的确定，便成为一个多目标决策问题，这一问题可以运用目标规划方法进目标决策问题，这一问题可以运用目标规划方法进行求解。行求解。第58页/共1

26、12页目标规划模型的有关概念第59页/共112页2 2、绝对约束和目标约束、绝对约束和目标约束 绝对约束：绝对约束：必须严格满足的等式约束和不必须严格满足的等式约束和不等式约束，譬如，线性规划问题的所有约束条等式约束，譬如，线性规划问题的所有约束条件都是绝对约束，不能满足这些约束条件的解件都是绝对约束，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。称为非可行解，所以它们是硬约束。目标约束：目标约束：目标规划所特有的，可以将约目标规划所特有的，可以将约束方程右端项看作是追求的目标值，在达到此束方程右端项看作是追求的目标值，在达到此目标值时允许发生正的或负的偏差目标值时允许发生正的或负的

27、偏差 ，可加入，可加入正负偏差变量，是软约束。正负偏差变量，是软约束。线性规划问题的目标函数，在给定目标值线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可以转化为目标约束，和加入正、负偏差变量后可以转化为目标约束，也可以根据问题的需要将绝对约束转化为目标也可以根据问题的需要将绝对约束转化为目标约束。约束。目标规划模型的有关概念第60页/共112页目标规划模型的有关概念第61页/共112页目标规划模型的有关概念第62页/共112页b)b)要要求求不不超超过过目目标标值值，即即允允许许达达不不到到目目标标值，就是正偏差变量要尽可能小，即值，就是正偏差变量要尽可能小，即（23）c)c)要

28、求超过目标值，也就是超过量不限，要求超过目标值，也就是超过量不限，但负偏差变量要尽可能小，即但负偏差变量要尽可能小，即 （24）在实际问题中，可以根据决策者的要求，在实际问题中，可以根据决策者的要求，引入正、负偏差变量和目标约束，并给不同引入正、负偏差变量和目标约束，并给不同目标赋予相应的优先因子和权系数，构造目目标赋予相应的优先因子和权系数，构造目标函数，建立模型。标函数，建立模型。第63页/共112页例例2 2：在在例例1 1中中，如如果果决决策策者者在在原原材材料料供供应应受受严严格格控控制制的的基基础础上上考考虑虑：首首先先是是甲甲种种产产品品的的产产量量不不超超过过乙乙种种产产品品的

29、的产产量量；其其次次是是充充分分利利用用设设备备的的有有限限台台时时，不不加加班班；再再次次是是产产值值不不小小于于5656元元。并并分分别别赋赋予予这这三三个个目目标标优优先先因因子子 。试试建建立立该问题的目标规划模型。该问题的目标规划模型。第64页/共112页第65页/共112页第66页/共112页在以上各式中，在以上各式中，、分别为赋予分别为赋予 优先因子的第优先因子的第 个目标的正、负偏个目标的正、负偏差变量的权系数，差变量的权系数，为第为第 个目标的预期值，个目标的预期值，为决策变量，为决策变量，、分别为第分别为第 个目标的正、负偏差变量，个目标的正、负偏差变量，（2525）式为目

30、标函数，（）式为目标函数，（2626）式为目标约束，（）式为目标约束，（2727）式）式为绝对约束，（为绝对约束，（2828）式和（）式和（2929）式为非负约束，）式为非负约束，、分别为目标约束和绝对约束中决策变量的系数及约束值。分别为目标约束和绝对约束中决策变量的系数及约束值。其中，其中，；。第67页/共112页图解法求解例图解法求解例2 2第68页/共112页首先考虑具有首先考虑具有 优先因子优先因子的目标的实现，在目标函的目标的实现，在目标函数中要求实现数中要求实现 ，图，图中可以满足中可以满足 .这时这时 的取值只能在的取值只能在OBCOBC的边界和的边界和内部取得。内部取得。接着考

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

32、，能依先后次序都满足在此例中，能依先后次序都满足 因因而而 。但是大多数问题中并非如此，还可能出现非可行解，。但是大多数问题中并非如此，还可能出现非可行解，故将目标规划问题的最优解成为满意解。故将目标规划问题的最优解成为满意解。第70页/共112页例如例如，某电视机厂装配黑白和彩色两种电视机，每某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线装配一台电视机需占用装配线1 1小时，装配线每周计划小时，装配线每周计划开动开动4040小时。预计市场每周彩色电视机的销量是小时。预计市场每周彩色电视机的销量是2424台，台，每台可获利每台可获利8080元；黑白电视的销量是元；黑白电视的销

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

34、1页/共112页解：设解：设 分别为黑白分别为黑白和和彩色电视机的产量。彩色电视机的产量。目标规划模型为目标规划模型为第72页/共112页从图中可以看到，再考虑具有从图中可以看到，再考虑具有 的目标实现的目标实现后，后，的取值范围为的取值范围为ABCDABCD。考虑。考虑 的目标要求的目标要求时，因时，因 的权系数大于的权系数大于 ，故先取，故先取 。这时。这时 的取值范围为的取值范围为ABEFABEF。在。在ABEFABEF中，只有中，只有E E点使得点使得 取值最小，故去取值最小，故去E E点为满意解。其坐标点为满意解。其坐标为为(24,26)(24,26)，即该厂每，即该厂每周应装配彩色

35、电视机周应装配彩色电视机2424台，黑白电视机台，黑白电视机2626台。台。第73页/共112页第74页/共112页所以检验数的正、负首先决定于所以检验数的正、负首先决定于 的系数的系数 的正、的正、负，若负，若 ，则检验数的正、负就决定于，则检验数的正、负就决定于 的系数的系数 的正、负，下面可依此类推。的正、负，下面可依此类推。据据此此，我我们们可可以以总总结结出出求求解解目目标标规规划划问问题题的的单单纯纯形方法的计算步骤如下：形方法的计算步骤如下：建建立立初初始始单单纯纯形形表表，在在表表中中将将检检验验数数行行按按优优先先因因子个数分别排成子个数分别排成L L行，置行，置 。第75页

36、/共112页检检查查该该行行中中是是否否存存在在负负数数，且且对对应应的的前前L-1L-1行行的的系系数数是是零零。若若有有，取取其其中中最最小小者者对对应应的的变变量量为为换入变量，转换入变量，转。若无负数，则转。若无负数，则转。按按最最小小比比值值规规则则（规规则则）确确定定换换出出变变量量，当当存存在在两两个个和和两两个个以以上上相相同同的的最最小小比比值值时时，选选取取具具有较高优先级别的变量为换出变量。有较高优先级别的变量为换出变量。按按单单纯纯形形法法进进行行基基变变换换运运算算，建建立立新新的的计计算算表表，返回返回。当当l=Ll=L时时，计计算算结结束束，表表中中的的解解即即为

37、为满满意意解解。否则置否则置l=l+1l=l+1，返回，返回 。第76页/共112页例例3 3：试用单纯形法求解例试用单纯形法求解例2 2所描述的目标规划问题所描述的目标规划问题解：首先将这一问题化为如下标准形式：解：首先将这一问题化为如下标准形式：第77页/共112页取取 、为初始基变量，列出初为初始基变量，列出初始单纯形表。始单纯形表。表1第78页/共112页 取取 ，检检查查检检验验数数的的 行行，因因该该行行无无负负检检验验数，故转数，故转。因为因为 ，置，置 ，返回，返回。检查发现检验数检查发现检验数 行中有行中有 ，因为有，因为有 ，所以，所以 为换入变量，转入为换入变量，转入。按

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

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

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

41、040403030编制员工数编制员工数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-为各目标的正、负偏差变量。为各目标的正、负偏差变量。（2 2）约束条件：）约束条件：1 1）提级后在职员工的工资总额不超过提级后在职员工的工资总额不超过550550千元；千元；8(10-10 8%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=5

42、50第84页/共112页 2）各级员工不要超过定编人数各级员工不要超过定编人数1级有：级有：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+

43、d9-d9+=100 20%第85页/共112页（3 3）目标函数：）目标函数：或者：或者：第86页/共112页五、五、层层次次分分析析法法（一）层次分析法的基本原理（一）层次分析法的基本原理 层次分析法，又称层次分析法，又称AHP(Analytic AHP(Analytic Hirrarchy Process)Hirrarchy Process)方法，是美国运筹学家萨蒂方法，是美国运筹学家萨蒂(T.Saaty)(T.Saaty)提出的一种多目标、多准则的决策分提出的一种多目标、多准则的决策分析方法。该方法被广泛应用于工程、经济、军事、析方法。该方法被广泛应用于工程、经济、军事、政治、外交等领

44、域，解决了诸如系统评价、资源政治、外交等领域，解决了诸如系统评价、资源分配、价格预测、项目选择等许多重要问题，是分配、价格预测、项目选择等许多重要问题，是一种定量分析与定性分析相结合的有效方法。一种定量分析与定性分析相结合的有效方法。第87页/共112页用层次分析法作决策分析，首先要把问题层用层次分析法作决策分析，首先要把问题层次化。根据问题的性质和要达到的总目标，次化。根据问题的性质和要达到的总目标，将问题分解为不同的组成因素，并按照因素将问题分解为不同的组成因素，并按照因素间的相互影响以及隶属关系按不同层次聚集间的相互影响以及隶属关系按不同层次聚集组合，形成一个多层次的分析结构模型。最组合

45、，形成一个多层次的分析结构模型。最终把系统分析归结为最低层（如决策方案）终把系统分析归结为最低层（如决策方案）相对于最高层（总目标）的相对重要性权值相对于最高层（总目标）的相对重要性权值的确定或相对优劣次序的排序问题，从而为的确定或相对优劣次序的排序问题，从而为决策方案的选择提供依据。决策方案的选择提供依据。第88页/共112页 （二（二)层次分析法大体分为六个步骤层次分析法大体分为六个步骤1 1）明确问题：为了运用）明确问题：为了运用AHPAHP进行系统分析，首先要对问题进行系统分析，首先要对问题有明确的认识，弄清问题范围、所包含的因素及其相互关有明确的认识，弄清问题范围、所包含的因素及其相

46、互关系、解决问题的目的、是否具有系、解决问题的目的、是否具有AHPAHP所描述的特征。所描述的特征。2 2）建立层次结构模型：将问题中所包含的因素划分为不）建立层次结构模型：将问题中所包含的因素划分为不同层次。例如，对于决策问题，通常可以划分为下面几个同层次。例如，对于决策问题，通常可以划分为下面几个层次：层次：最高层：表示解决问题的目的，称为目标层。最高层：表示解决问题的目的，称为目标层。中间层：表示采取某种措施或政策实现预定目标的涉及的中间层：表示采取某种措施或政策实现预定目标的涉及的中间环节，一般又分为策略层、准则层等。中间环节，一般又分为策略层、准则层等。最低层：表示解决问题的措施或方

47、案，称为措施层或方案最低层：表示解决问题的措施或方案，称为措施层或方案层。如下图所示。层。如下图所示。第89页/共112页决策目标准则1准则1准则m子准则1子准则2子准则k方案1方案2方案n目标层准则层子准则层方案层第90页/共112页3 3）构造判断矩阵）构造判断矩阵针对上一层某元素，对每一层次各个元素的相对重要性进针对上一层某元素，对每一层次各个元素的相对重要性进行两两比较，并给出判断。这些判断用数值表示出来，写行两两比较，并给出判断。这些判断用数值表示出来，写成矩阵形式，即所谓的判断矩阵。成矩阵形式，即所谓的判断矩阵。其中其中b bijij表示对于表示对于A Ak k而言，而言，B Bi

48、 i对对B Bj j的相对重要性，通常的相对重要性，通常b 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及各数的倒数有相应的类似意义。及各数的倒数有相应的类似意义。显然，对判断矩阵有显然

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

50、以证明，对于n n阶判断矩阵，其最大特征根阶判断矩阵，其最大特征根 为单根，且为单根，且 ，所对应的特征向量均由正数所对应的特征向量均由正数组成。特别，当判断矩阵具有完全一致性时组成。特别，当判断矩阵具有完全一致性时,有有 这里，所谓完全一致性是指对于判断矩阵来说，存在这里，所谓完全一致性是指对于判断矩阵来说，存在第93页/共112页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阶数阶数为检验判断矩阵的一致性，需要计算一致性指标为检验判