《多目标规划建模ppt课件》由会员分享，可在线阅读，更多相关《多目标规划建模ppt课件（50页珍藏版）》请在金锄头文库上搜索。
1、数学建模数学建模主讲主讲薛长虹薛长虹E-mail地址地址:QQ:315165多目标规划模型多目标规划模型 基本内容基本内容：1、多目标规划的基本概念2、多目标规划的问题的特征 3、多目标规划的求解方法 4、目标规划模型5、应用实例模型.一、一、多目标的基本概念多目标的基本概念 多目标的问题多目标的问题: :在现实生活中在现实生活中, ,决策的目标往往决策的目标往往有多个有多个, ,例如例如, ,对企业产品的生产管理对企业产品的生产管理, ,既希望达到高既希望达到高利润利润, ,又希望优质和低消耗又希望优质和低消耗, ,还希望减少对环境的污还希望减少对环境的污染等染等. .这就是一个多目标决策的
2、问题这就是一个多目标决策的问题. . 。又如选购一个好的计算机系统又如选购一个好的计算机系统, ,似乎只有一个目似乎只有一个目标标, ,但由于要从多方面去反映但由于要从多方面去反映, ,要用多个不同的准则要用多个不同的准则来衡量来衡量, ,比如比如, ,性能要好性能要好, ,维护要容易维护要容易, ,费用要省费用要省. .这些这些准则自然构成了多个目标准则自然构成了多个目标, ,故也是一个多目标决策问故也是一个多目标决策问题题. .应用应用: :研究多目标决策问题的前提，因此研究解决这研究多目标决策问题的前提，因此研究解决这类问题在实际中是很有意义的，特别是在政治、经类问题在实际中是很有意义的
3、，特别是在政治、经济、社会及军事管理、工程技术及科学决策等领域济、社会及军事管理、工程技术及科学决策等领域都有重要的应用价值。都有重要的应用价值。 一般来说一般来说, ,多目标规划问题有两类多目标规划问题有两类. .一类是多目一类是多目标规划问题标规划问题, ,其对象是在管理决策过程中求解使多个其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方案目标都达到满意结果的最优方案. .另一类是多目标优另一类是多目标优选问题选问题, ,其对象是在管理决策过程中根据多个目标或其对象是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选方案的优先等级与排多个准则衡量和得出各种备选方案的优先等
4、级与排序序. .二、二、多目标规划问题的分类多目标规划问题的分类 w多目标决策由于考虑的目标多多目标决策由于考虑的目标多, ,有些目标之间又彼此有些目标之间又彼此有矛盾有矛盾, ,这就使多目标问题成为一个复杂而困难的问这就使多目标问题成为一个复杂而困难的问题题. .但由于客观实际的需要但由于客观实际的需要, ,多目标决策问题越来越多目标决策问题越来越受到重视受到重视, ,因而出现了许多解决此决策问题的方法因而出现了许多解决此决策问题的方法. .一般来说一般来说, ,其基本途径是其基本途径是, ,把求解多目标问题转化为把求解多目标问题转化为求解单目标问题求解单目标问题. .其主要步骤是其主要步骤
5、是, ,先转化为单目标问先转化为单目标问题题, ,然后利用单目标模型的方法然后利用单目标模型的方法, ,求出单目标模型的求出单目标模型的最优解最优解, ,以此作为多目标问题的解以此作为多目标问题的解. .三、三、多目标规划问题的求解多目标规划问题的求解 w化多目标问题为单目标问题的方法大致可分为两类化多目标问题为单目标问题的方法大致可分为两类, ,一类是转化为一个单目标问题一类是转化为一个单目标问题, ,另一类是转化为多个另一类是转化为多个单目标问题单目标问题, ,关键是如何转化关键是如何转化. .w 下面下面, ,我们介绍几种主要的转化方法我们介绍几种主要的转化方法: :主要目标主要目标法、
6、线性加权和法、字典序法、步骤法。法、线性加权和法、字典序法、步骤法。多目标规划问题的求解多目标规划问题的求解 f1f212345678在解决单目标问题时，我们的任务是选择一个或一组变在解决单目标问题时，我们的任务是选择一个或一组变量量X，使目标函数，使目标函数f(X)取得最大（或最小）。对于任意两方案取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标两个目标f1(X)，f2(X),希望它们都越大越
7、好。下图列出在这两希望它们都越大越好。下图列出在这两个目标下共有个目标下共有8个解的方案。其中方案个解的方案。其中方案1，2，3，4称为劣解，称为劣解，因为它们在两个目标值上都比方案因为它们在两个目标值上都比方案5差，是可以淘汰的解。而差，是可以淘汰的解。而方案方案5，6，7，8是非劣解（或称为有效解，满意解），因为是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却更差。个相比，总有一个指标更优越，而另一个指标却更差。一、解的特点一、解的特点多目标规划问题的特征
8、多目标规划问题的特征 二、模型结构二、模型结构多目标决策问题包含有三大要素：目标、方案和决策者。多目标决策问题包含有三大要素：目标、方案和决策者。在多目标决策问题中，目标有多层次的含义。从最高层次在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量目的
9、盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。好，花费要少。多目标决策问题中的方案即为决策变量，也称为多目多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题策中，有些问题的方案是有限的，有些问题的方案是无限的方案是无限的。方案有其特征或特性，称之为属性。的。方案有其特征或特性，称之为属性。1、多目标规划问题的模型结构、多目标规划问题的模型结构为决策变
10、量为决策变量如对于求极大如对于求极大(max)型，其各种解定义如下：型，其各种解定义如下：绝对最优解：若对于任意的绝对最优解：若对于任意的X，都有，都有F（X*）F(X)有效解：若不存在有效解：若不存在X，使得，使得F（X*）F(X)弱有效解：若不存在弱有效解：若不存在X，使得，使得F（X*)F(X)2、多目标优选问题的模型结构、多目标优选问题的模型结构可用效用函数来表示。设方案的效用是目标属性可用效用函数来表示。设方案的效用是目标属性的函数：的函数：并设并设且各个方案的效用函数分别为且各个方案的效用函数分别为则多目标优选模型的结构可表示如下：则多目标优选模型的结构可表示如下：(1)线性加权法
11、线性加权法:取取对对p个目标函数作线性加权化为单目标问题个目标函数作线性加权化为单目标问题多目标规划问题的求解多目标规划问题的求解多目标规划问题的求解多目标规划问题的求解(2)理想点法理想点法:对每一个目标对每一个目标给出一个目标理想值给出一个目标理想值则称则称为多目标函数为多目标函数值域中的一个理想点。值域中的一个理想点。将多目标问题转化为目标函数将多目标问题转化为目标函数与与之间的最小之间的最小“距离距离”的单目标问题：的单目标问题：(3)极大极小法：极大极小法：基本思想是在最不利的情况下求最有基本思想是在最不利的情况下求最有利的策略。即求多目标中最大目标函数值最小。于是利的策略。即求多目
12、标中最大目标函数值最小。于是可化为如下单目标问题：可化为如下单目标问题：也可以给每个也可以给每个配上权系数配上权系数，即考虑：，即考虑：多目标规划问题的求解多目标规划问题的求解（4）主要目标法）主要目标法在有些多目标决策问题中，各种目标的重要性程度在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最高和最为关键的往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标，称之为主要目标法。其余的目标则称为非主要目标。目标。例如，在上述多目标问题中，假定例如，在上述多目标问题中，假定f1(X)为主要目标，其余为主要目标，其余p-1个为
13、非主要目标。这时，希望主要目标达到极大值，并要求个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即其余的目标满足一定的条件，即多目标规划问题的求解多目标规划问题的求解例题例题1某工厂在一个计划期内生产甲、乙两种产品，各产品某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗都要消耗A，B，C三种不同的资源。每件产品对资源的单位三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每所造成的单位污染如下表。假定产品能全部销售出去，
14、问每期怎样安排生产，才能使利润和产值都最大，且造成的污染期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？最小？甲甲乙乙资源限量资源限量资源资源A单位消耗单位消耗资源资源B单位消耗单位消耗资源资源C单位消耗单位消耗9434510240200300单位产品的价格单位产品的价格400600单位产品的利润单位产品的利润70120单位产品的污染单位产品的污染32解：问题的多目标模型如下解：问题的多目标模型如下对于上述模型的三个目标，工厂对于上述模型的三个目标，工厂确定利润最大为主要目标。另两确定利润最大为主要目标。另两个目标则通过预测预先给定的希个目标则通过预测预先给定的希望达到的目标值转化为
15、约束条件。望达到的目标值转化为约束条件。经研究，工厂认为总产值至少应经研究，工厂认为总产值至少应达到达到20000个单位，而污染控制个单位，而污染控制在在90个单位以下，即个单位以下，即由主要目标法化为单目标问题由主要目标法化为单目标问题用单纯形法求得其最优解为用单纯形法求得其最优解为（5）线性加权和目标规划）线性加权和目标规划在上述目标规划中，假定在上述目标规划中，假定f1(X),f2(X),fp(X)具有相同的量纲具有相同的量纲,按照一定的规则分别给按照一定的规则分别给fi赋予相同的权系数赋予相同的权系数i，作线性加权和，作线性加权和评价函数评价函数则多目标问题化为如下的单目标问题则多目标
16、问题化为如下的单目标问题例如，某公司计划购进一批新卡车，可供选择的卡车有如例如，某公司计划购进一批新卡车，可供选择的卡车有如下下4种类型：种类型：A1，A2，A3，A4。现考虑。现考虑6个方案属性：维个方案属性：维修期限修期限f1，每，每100升汽油所跑的里数升汽油所跑的里数f2，最大载重吨数，最大载重吨数f3，价，价格（万元）格（万元）f4，可靠性，可靠性f5，灵敏性，灵敏性f6。这。这4种型号的卡车分别种型号的卡车分别关于目标属性的指标值关于目标属性的指标值fij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一
17、般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先对不同度量单位和不同数量级的指标值进行标准化处理。首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：先将定性指标定量化：效益型指标效益型指标很低很低低低一般一般高高 很高很高13579很高很高高高一般一般低低 很低很低成本型指标成本型指标可靠性和灵敏性都属于效益型指标，其打分如下可靠性和灵敏性都属于效益型指标，其打分如下可靠性可靠性一般一般低低高高很高很高5379灵敏性灵敏性高高一般一般很高很高一般一般7595按以下公式作无量纲的标准化处理按以下公式作无量纲的标准化处理其中：变换后的指
18、标值矩阵为：变换后的指标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则故最优方案为选购故最优方案为选购A3型卡车型卡车（6）分层序列法：）分层序列法：1.基本步骤：基本步骤：把把(VP)中的中的p个目标个目标按其重要程度排序。按其重要程度排序。依次求单目标规划的最优解。依次求单目标规划的最优解。2.过程：过程：无妨设其次序为无妨设其次序为先求解先求解得最优值得最优值，记，记再解再解得最优值得最
19、优值，依次进行，直到依次进行，直到得最优值得最优值则则是在分层序列意义下的最优解集合。是在分层序列意义下的最优解集合。3.性质：性质：，即在分层序列意义下的最优解是有，即在分层序列意义下的最优解是有效解。效解。证明：反证。设证明：反证。设，但，但，则必存在，则必存在使使即至少有一个即至少有一个j0，使，使,由于由于，即，即，矛盾。得证。矛盾。得证。4.进一步讨论：进一步讨论：上述方法过程中，当某个问题上述方法过程中，当某个问题(Pj)的解唯一时，则的解唯一时，则问题问题的求解无意义，因为解都是唯一的。的求解无意义，因为解都是唯一的。实际求解时，有较宽容意义下的分层序列法：实际求解时，有较宽容意
20、义下的分层序列法：取取为预先给定的宽容值，整个解法同原为预先给定的宽容值，整个解法同原方法类似，只是取各约束集合时，分别取为：方法类似，只是取各约束集合时，分别取为：（7）步骤法（）步骤法（STEM法）法）这是一种交互方法，其求解过程通过分析者与决策者这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。之间的对话逐步进行，故称步骤法。步骤法的基本思想是，首先需要求出原多目标问题的步骤法的基本思想是，首先需要求出原多目标问题的一组理想解一组理想解(f1*,f2*,fp*)。实际上，这些解。实际上，这些解fi*(i=1,2,p)无法同时达到，但可以当作一组理想的最优值。以
21、理想解无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。来的约束条件中去重新计算，直到决策者得到满意的解。步骤法算法如下：步骤法算法如下：第一步：分别求解以下第一步：分别求解以下p个单目标问题的最优解个单目标问题的最优解得到最优解得到最优解，其相应的目标值，其相应的目标值即为即为理想值，此最优解处别的目标所取的值用理想值，此最优解处别的目标所取的值
22、用表示，即表示，即，把上述计算结果列入下表，把上述计算结果列入下表在表中，确定每一列的最小值并记第在表中，确定每一列的最小值并记第i列的最小值为列的最小值为fip(i=1,2,p)第二步：求解第二步：求解其中：其中：这里这里（1）第三步：将上述模型（第三步：将上述模型（1）的解）的解X0与相应的目标值与相应的目标值f1(X0),f2(X0),fp(X0)交给决策者去判断。决策者把这些目标值与理想值进交给决策者去判断。决策者把这些目标值与理想值进行比较后，如果认为其中某些目标值太坏，另一些目标值可以行比较后，如果认为其中某些目标值太坏，另一些目标值可以不要那么太好，可以把比较好的目标值中的某一个
23、修改得差一不要那么太好，可以把比较好的目标值中的某一个修改得差一些，以使水平太坏的目标得到改善。些，以使水平太坏的目标得到改善。当决策者减少了第当决策者减少了第j个目标的值个目标的值之后，约束条件之后，约束条件S应该改应该改为为S*在进行下一次迭代时，对应于降低了要求的那些目标在进行下一次迭代时，对应于降低了要求的那些目标fj(j=1,2,k)的权系数的权系数i应该设为应该设为0。这种迭代继续下去，直到。这种迭代继续下去，直到决策者满意为止。决策者满意为止。例题：例题：某公司考虑生产两种光电太阳能电池：产品甲和产某公司考虑生产两种光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性
24、污染。因此，品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放射性污公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收益是染。已知在一个生产周期内，每单位甲产品的收益是1元，元，每单位乙产品的收益是每单位乙产品的收益是3元。而放射性污染的数量，每单元。而放射性污染的数量，每单位甲产品是位甲产品是1.5个单位个单位,每单位乙产品是每单位乙产品是1个单位个单位.由于机器由于机器能力能力(小时小时)、装配能力（人时）和可用的原材料（单位）、装配能力（人时）和可用的原材料（单位）的限制，约束条件是的限制，约束条件是目
25、标有两个目标有两个:一是利润最大一是利润最大,二是污染最小二是污染最小.该问题的多目标该问题的多目标规划模型如下规划模型如下:解解:首先首先,分别求解两个单目标问题的最优解分别求解两个单目标问题的最优解,由它们得由它们得到的目标函数值组成理想解到的目标函数值组成理想解.由此由此,构造支付表构造支付表Xf1*f2*(7,13)(0,0)460-23.50由此计算两个目标与理想值偏离的权重由此计算两个目标与理想值偏离的权重解下列线性规划问题解下列线性规划问题:由此求得由此求得,分析者把计算结果交给决策者分析者把计算结果交给决策者,决策者将目标值与理想值决策者将目标值与理想值(21.192,-7.0
26、64)与理想值与理想值(46,0)比较比较,如果认为如果认为f2是满意的是满意的,但利润太低但利润太低,并认为并认为污染可接受到污染可接受到10个单位个单位.于是于是,约束集修改成约束集修改成进行下一轮迭代进行下一轮迭代.首先设首先设2=0,并计算得并计算得1=1.将模型修改为将模型修改为由此求得由此求得:决策者把这一结果与前一轮的解及理想值作比较决策者把这一结果与前一轮的解及理想值作比较,认为两个目标值都认为两个目标值都比较满意比较满意,则迭代结束则迭代结束.线线性性规规划划问问题题都都是是处处理理单单个个目目标标的的情情况况，但但是是在在现现实实世世界界中中有有许许多多问问题题具具有有多多
27、个个目目标标，这这些些目目标标的的重重要要性性各各不不相相同同，往往往往有有不不同同的的量量纲纲，有有的的目目标标相相互互依依赖赖，例例如如决决策策者者既既希希望望实实现现利利润润最最大大，又又希希望望实实现现产产值值最最大大；有有的的相相互互抵抵触触，如如决决策策者者既既希希望望充充分分利利用用资资源源，又又不不希希望望超超越越资资源源限限量量。而而决决策策者者希希望望在在某某些些限限制制条条件件下下，依依次次实实现现这这些些目目标标。这这就就是是目目标标规规划划所所要要解解决决的的问问题题。当当所所有有的的目目标标函函数数和和约约束束条条件件都都是是线线性性时时，我我们们称称其其为为线线性
28、性目目标标规规划划问问题题。在在这这里我们主要讨论线性目标规划问题。里我们主要讨论线性目标规划问题。一、目标规划模型的建立一、目标规划模型的建立目标规划模型目标规划模型 引例引例1：对于生产计划问题：对于生产计划问题：甲甲乙乙资源限额资源限额材料材料2324工时工时3226单位利润单位利润43现现在在工工厂厂领领导导要要考考虑虑市市场场等等一一系系列列其其他他因因素素，提提出出如如下下目目标：标：（1）根根据据市市场场信信息息，甲甲产产品品的的销销量量有有下下降降的的趋趋势势，而而乙乙产产品品的的销销量量有有上上升升的的趋趋势势，故故考考虑虑乙乙产产品品的的产产量量应应大大于于甲甲产产品的产量
29、。品的产量。（2）尽可能充分利用工时，不希望加班。）尽可能充分利用工时，不希望加班。（3）应尽可能达到并超过计划利润）应尽可能达到并超过计划利润30元。元。现在的问题是：在原材料不能超计划使用的前提下，如何现在的问题是：在原材料不能超计划使用的前提下，如何安排生产才能使上述目标依次实现？安排生产才能使上述目标依次实现？解：（解：（1）决策变量：仍设每天生产甲、乙两种产品各为）决策变量：仍设每天生产甲、乙两种产品各为x1和和x2偏差变量：对于每一目标，我们引进正、负偏差变量。偏差变量：对于每一目标，我们引进正、负偏差变量。如如对对于于目目标标1，设设d1-表表示示乙乙产产品品的的产产量量低低于于
30、甲甲产产品品产产量量的的数数，d1+表表示示乙乙产产品品的的产产量量高高于于甲甲产产品品产产量量的的数数。称称它它们们分分别别为为产产量量比比较较的的负负偏偏差差变变量量和和正正偏偏差差变变量量。则则对对于于目目标标1，可可将将它它表表示示为等式约束的形式为等式约束的形式-x1+x2+d1-d1+=0(目标约束目标约束)同同样样设设d2-和和d2+分分别别表表示示安安排排生生产产时时，低低于于可可利利用用工工时时和和高高于于可利用工时，即加班工时的偏差变量，则对目标可利用工时，即加班工时的偏差变量，则对目标2，有，有3x1+2x2+d2-d2+=26对于目标对于目标3，设，设d3-和和d3+分
31、别表示安排生产时，低于计划利润分别表示安排生产时，低于计划利润30元和高于计划利润元和高于计划利润30元的偏差变量，有：元的偏差变量，有：4x1+3x2+d3-d3+=30（2）约束条件：有资源约束和目标约束）约束条件：有资源约束和目标约束资源约束：资源约束：2x1+3x224目标约束：为上述各目标中得出的约束目标约束：为上述各目标中得出的约束（3）目标函数：三个目标依次为：）目标函数：三个目标依次为：minZ1=d1-，minZ2=d2+d2-，minZ3=d3-因而该问题的数学模型可表述如下：因而该问题的数学模型可表述如下：minZ1=d1-，minZ2=d2+d2-，minZ3=d3-2
32、x1+3x224st-x1+x2+d1-d1+=03x1+2x2+d2-d2+=264x1+3x2+d3-d3+=30案例案例2（提级加新问题）（提级加新问题）某公司的员工工资有四级，根某公司的员工工资有四级，根据公司的业务发展情况，准备招收部分新员工，并将部分据公司的业务发展情况，准备招收部分新员工，并将部分员工的工资提升一级。该公司的员工工资及提级前后的编员工的工资提升一级。该公司的员工工资及提级前后的编制表如下，其中提级后编制是计划编制，允许有变化，其制表如下，其中提级后编制是计划编制，允许有变化，其中中1级员工中有级员工中有8%要退休。公司领导的目标如下：要退休。公司领导的目标如下：（
33、1）提级后在职员工的工资总额不超过）提级后在职员工的工资总额不超过550千元；千元；（2）各级员工不要超过定编人数；）各级员工不要超过定编人数；（3）为为调调动动积积极极性性，各各级级员员工工的的升升级级面面不不少少于于现现有有人人数数的的18%；（4）总提级面不大于）总提级面不大于20%，但尽可能多提；，但尽可能多提；（5）4级不足编制人数可录用新工人。级不足编制人数可录用新工人。问：应如何拟定一具满意的方案，才能接近上述目标？问：应如何拟定一具满意的方案，才能接近上述目标？级别级别1234工资（千元）工资（千元）8643现有员工数现有员工数10204030编制员工数编制员工数1022523
34、0解解：（1）决决策策变变量量：设设x1,x2,x3,x4分分别别表表示示提提升升到到1，2，3级和新录用的员工数。级和新录用的员工数。偏差变量：为各目标的正、负偏差变量。偏差变量：为各目标的正、负偏差变量。（2）约束条件：）约束条件：1）提级后在职员工的工资总额不超过提级后在职员工的工资总额不超过550千元；千元；8(10-10 8%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=5502）各级员工不要超过定编人数各级员工不要超过定编人数1级有：级有：10-10 8%+x1+d2-d2+=102级有：级有：20-x1+x2+d3-d3+=223
35、级有：级有：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）目标函数：）目标函数：minZ1=d1+minZ2=d2+d3+d4+d5+minZ3=d6-+d7-+d8-minZ4=d9+d9-案例案例3有三个产
36、地向四个销地供应物资。产地有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量的供应量ai、销地、销地Bj(j=1,2,3,4)的需要量的需要量bj、各产销地之间、各产销地之间的单位物资运费的单位物资运费Cij如表如表2所示。表中，所示。表中，ai和和bj的单位为吨，的单位为吨，Cij的单位为元的单位为元/吨。编制调运方案时要求按照相应的优先吨。编制调运方案时要求按照相应的优先级依次考虑下列七个目标：级依次考虑下列七个目标：P1：B4是重点保证单位，其需要量应尽可能全部满足；是重点保证单位，其需要量应尽可能全部满足；P2：A3向向B1提供的物资不少于提供的物资不少于100吨；吨；P
37、3：每个销地得到的物资数量不少于其需要量的：每个销地得到的物资数量不少于其需要量的80%；P4：实实际际的的总总运运费费不不超超过过当当不不考考虑虑P1至至P6各各目目标标时时的的最最小小总总运运费费的的110%，这这里里的的最最小小总总费费用用利利用用第第三三大大题题中中第第2小小题题求出的结果；求出的结果；P5：因路况原因，尽量避免安排：因路况原因，尽量避免安排A2的物资运往的物资运往B4；P6：对：对B1和和B3的供应率要尽可能相同；的供应率要尽可能相同；P7：力求使总运费最省。：力求使总运费最省。试建立该问题的运筹学模型。试建立该问题的运筹学模型。Cij BjAiB1B2B3B4aiA
38、15267300A23546200A34523400bj200100450250解：用表上作业法可求得不考虑解：用表上作业法可求得不考虑P1至至P6各目标时的最小运各目标时的最小运费调运方案，相应的最小运费为费调运方案，相应的最小运费为2950元元（1）决策变量：设）决策变量：设Ai运往运往Bj的物资为的物资为xij吨吨（2）约束条件：）约束条件：产量约束产量约束B4销量要满足销量要满足销量销量80%的限制的限制供应率尽可能相同供应率尽可能相同二、目标规划的解法二、目标规划的解法由于目标规划有多个目标，各个目标又有相对不同的由于目标规划有多个目标，各个目标又有相对不同的重要性，求解时是首先满足
39、重要性权数大的目标，再满足重要性，求解时是首先满足重要性权数大的目标，再满足重要性权数次大的目标，所以并不能保证所有的目标都能重要性权数次大的目标，所以并不能保证所有的目标都能达到，所求的解也不一定是最优解，而只能求出满意解。达到，所求的解也不一定是最优解，而只能求出满意解。（3）目标函数）目标函数 求求解解目目标标规规划划的的仍仍用用单单纯纯形形法法，但但是是与与线线性性规规划划的的单单纯纯形形法法不不同同的的是是，此此时时检检验验数数行行不不再再是是一一行行，而是变化为一个检验数矩阵。而是变化为一个检验数矩阵。 例例4用单纯形法求解如下线性目标规划模型用单纯形法求解如下线性目标规划模型mi
40、nZ1=d1-，minZ2=d2+d2-，minZ3=d3-2x1+3x224加入松驰变量化为标准形加入松驰变量化为标准形2x1+3x2+x3=24st-x1+x2+d1-d1+=03x1+2x2+d2-d2+=264x1+3x2+d3-d3+=30解解（1）取取x3，d1-，d2-，d3-为基变量，建立初始单纯形表为基变量，建立初始单纯形表-1-2-1123-13402630Z1Z2Z3000-100-100-100000100100100100031232-1342402630x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步骤完全与线性规划的单纯形法一样
41、。迭代的步骤完全与线性规划的单纯形法一样。（2）满意解的判定：检验数矩阵的每一列从上至下第一个）满意解的判定：检验数矩阵的每一列从上至下第一个非零元为负数，则解为满意解。迭代的最优表如下：非零元为负数，则解为满意解。迭代的最优表如下：-2-1-1-11-1020Z1Z2Z3100000-106/5-2/5-13/5-10000010-6/52/51-3/57/51/5-11/50100000118/524/5224/5d3+x2d2-x1d3+d2+d1+d3-d2-d1-x3x2x1bXB因而满意解为：因而满意解为：x1=24/5，x2=24/5，d2-=2，d3+=18/5其中第一、三目标
42、已达到最优，第二个目标未达最优。其中第一、三目标已达到最优，第二个目标未达最优。目标利润目标利润Z=4x1+3x2=168/5某化工厂拟生产两种新产品某化工厂拟生产两种新产品A和和B，其生产设备投，其生产设备投资分别为：资分别为：A，2万元吨；万元吨；B，5万元吨。这两种万元吨。这两种产品均会造成环境污染，设由公害所造成的损失可折产品均会造成环境污染，设由公害所造成的损失可折算为：算为：A，4万元吨；万元吨；B，1万元吨。由于条件限万元吨。由于条件限制，工厂生产产品制，工厂生产产品A和和B的最大生产能力各为每月的最大生产能力各为每月5吨吨和和6吨，而市场需要这两种产品的总量每月不少于吨，而市场需要这两种产品的总量每月不少于7吨。吨。试问工厂如何安排生产计划，在满足市场需要的前提试问工厂如何安排生产计划，在满足市场需要的前提下，使设备投资和公害损失均达最小。下，使设备投资和公害损失均达最小。工厂决策认为：这两个目标中环境污染应优先考虑，工厂决策认为：这两个目标中环境污染应优先考虑，设备投资的目标值为设备投资的目标值为20万元，公害损失的目标为万元，公害损失的目标为12万万元。元。多目标规划的建模作业多目标规划的建模作业 E-mail:主页：主页：http:/
