多目标规划建模

数学建模主讲薛长虹E-mail地址:

xuechanghongQQ:315165数学建模竞赛专题讲座

多目标规划模型

基本内容：1、多目标规划的基本概念2、多目标规划的问题的特征3、多目标规划的求解方法4、目标规划模型5、应用实例模型.一、多目标的基本概念

多目标的问题:在现实生活中,决策的目标往往有多个,例如,对企业产品的生产管理,既希望达到高利润,又希望优质和低消耗,还希望减少对环境的污染等.这就是一个多目标决策的问题.。

又如选购一个好的计算机系统,似乎只有一个目标,但由于要从多方面去反映,要用多个不同的准则来衡量,比如,性能要好,维护要容易,费用要省.这些准则自然构成了多个目标,故也是一个多目标决策问题.应用:研究解决这类问题在实际中是很有意义的，特别是在政治、经济、社会及军事管理、工程技术及科学决策等领域都有重要的应用价值。

一般来说,多目标规划问题有两类.一类是多目标规划问题,其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方案.另一类是多目标优选问题,其对象是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选方案的优先等级与排序.二、多目标规划问题的分类

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

化多目标问题为单目标问题的方法大致可分为两类,一类是转化为一个单目标问题,另一类是转化为多个单目标问题,关键是如何转化.下面,我们介绍几种主要的转化方法:主要目标法线性加权和法字典序法步骤法多目标规划问题的求解

f1f212345678在解决单目标问题时，我们的任务是选择一个或一组变量X，使目标函数f(X)取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标f1(X)，f2(X),希望它们都越大越好。下图列出在这两个目标下共有8个解的方案。其中方案1，2，3，4称为劣解，因为它们在两个目标值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却较差。一、解的特点多目标规划问题的特征

二、模型结构多目标决策问题包含有三大要素：目标、方案和决策者。在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。1、多目标规划问题的模型结构为决策变量如对于求极大(max)型，其各种解定义如下：绝对最优解：若对于任意的X，都有F（X*）≥F(X)有效解：若不存在X，使得F（X*）≤F(X)弱有效解：若不存在X，使得F（X*)<F(X)2、多目标标优选问题题的模型结结构可用效用函函数来表示示。设方案案的效用是是目标属性性的函数：：并设且各个方案案的效用函函数分别为为则多目标优优选模型的的结构可表表示如下：：(1)线性加权法:取对p个目标函数作线性加权化为单目标问题多目标规划划问题的求求解多目标规划划问题的求求解(2)理想想点法:对每一个目目标给出一个目目标理想值值则称为多目标函函数值域中的一一个理想点点。将多目标问问题转化为为目标函数数与之间的最小小“距离””的单目标标问题：(3)极大大极小法：：基本思想是是在最不利利的情况下下求最有利利的策略。。即求多目目标中最大大目标函数数值最小。。于是可化化为如下单单目标问题题：也可以给每每个配上权系数数，即考虑：：多目标规划划问题的求求解（4）主要要目标法在有些多目目标决策问问题中，各各种目标的的重要性程程度往往不不一样。其其中一个重重要性程度度最高和最最为关键的的目标，称称之为主要要目标法。。其余的目目标则称为为非主要目目标。例如，在在上述多多目标问问题中，，假定f1(X)为为主要目目标，其其余p-1个为为非主要要目标。。这时，，希望主主要目标标达到极极大值，，并要求求其余的的目标满满足一定定的条件件，即多目标规规划问题题的求解解例题1某工厂在在一个计计划期内内生产甲甲、乙两两种产品品，各产产品都要要消耗A，B，，C三种种不同的的资源。。每件产产品对资资源的单单位消耗耗、各种种资源的的限量以以及各产产品的单单位价格格、单位位利润和和所造成成的单位位污染如如下表。。假定产产品能全全部销售售出去，，问每期期怎样安安排生产产，才能能使利润润和产值值都最大大，且造造成的污污染最小小？甲乙资源限量资源A单位消耗资源B单位消耗资源C单位消耗9434510240200300单位产品的价格400600单位产品的利润70120单位产品的污染32解：问题题的多目目标模型型如下对于上述述模型的的三个目目标，工工厂确定定利润最最大为主主要目标标。另两两个目标标则通过过预测预预先给定定的希望望达到的的目标值值转化为为约束条条件。经经研究，，工厂认认为总产产值至少少应达到到20000个个单位，，而污染染控制在在90个个单位以以下，即即由主要目目标法化化为单目目标问题题用单纯形形法求得得其最优优解为（5）线线性加权权和目标标规划在上述目目标规划划中，假假定f1(X),f2(X),…,fp(X)具具有相同同的量纲纲,按照照一定的的规则分分别给fi赋予不同同的权系系数ωi，作线性性加权和和评价函函数则多目标标问题化化为如下下的单目目标问题题例如，某某公司计计划购进进一批新新卡车，，可供选选择的卡卡车有如如下4种种类型：：A1，，A2，，A3，，A4。。现考虑虑6个方方案属性性：维修修期限f1，每100升汽汽油所跑跑的里数数f2，最大载载重吨数数f3，价格（（万元））f4，可靠性性f5，灵敏性性f6。这4种种型号的的卡车分分别关于于目标属属性的指指标值fij如下表所所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般首先对不不同度量量单位和和不同数数量级的的指标值值进行标标准化处处理。先先将定性性指标定定量化：：效益型指标很低低一般高很高13579很高高一般低很低成本型指标可靠性和和灵敏性性都属于于效益型型指标，，其打分分如下可靠性一般低高很高5379灵敏性高一般很高一般7595按以下公公式作无无量纲的的标准化化处理其中：变换后的的指标值值矩阵为为：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.过过程：无妨设其其次序为为先求解得最优值值，，记记再解得最优值值，，依次进行行，直到到得最优值值则是是在在分层序序列意义义下的最最优解集集合。3.性性质：，即在分分层序列列意义下下的最优优解是有有效解。。证明：反反证。设设，，但，，则则必存在在使即至少有有一个j0，使,由于，，即，矛盾盾。得证证。4.进进一步讨讨论：上述方法法过程中中，当某某个问题题(Pj)的解唯唯一时，，则问题的的求求解无意意义，因因为解都都是唯一一的。实际求解解时，有有较宽容容意义下下的分层层序列法法：取为为预先给给定的宽宽容值，，整个解解法同原原方法类似似，只是是取各约约束集合合时，分分别取为为：（7）步步骤法（（STEM法））这是一种种交互方方法，其其求解过过程通过过分析者者与决策策者之间间的对话话逐步进进行，故故称步骤骤法。步骤法的的基本思思想是，，首先需需要求出出原多目目标问题题的一组组理想解解(f1*,f2*,…,fp*)。实实际上，，这些解解fi*(i=1,2,…,p)无无法同时时达到，，但可以以当作一一组理想想的最优优值。以以理想解解作为一一个标准准，可以以估计有有效解，，然后通通过对话话，不断断修改目目标值，，并把降降低要求求的目标标作为新新的约束束条件加加入原来来的约束束条件中中去重新新计算，，直到决决策者得得到满意意的解。。步骤法算算法如下下：第一步：：分别求求解以下下p个单单目标问问题的最最优解得到最优优解，，其其相应的的目标值值即即为为理想值，，此最优优解处别别的目标标所取的的值用表表示，即即，把上述述计算结结果列入入下表在表中，，确定每每一列的的最小值值并记第第i列的的最小值值为fip(i=1,2,…,p)第二步：：求解其中：这里（1）第三步：：将上述述模型（（1）的的解X0与相应的的目标值值f1(X0),f2(X0),……,fp(X0)交给给决策者者去判断断。决策策者把这这些目标标值与理理想值进进行比较较后，如如果认为为其中某某些目标标值太坏坏，另一一些目标标值可以以不要那那么太好好，可以以把比较较好的目目标值中中的某一一个修改改得差一一些，以以使水平平太坏的的目标得得到改善善。当决策者者减少了了第j个个目标的的值之之后后，约束束条件S应该改改为S*在进行下下一次迭迭代时，，对应于于降低了了要求的的那些目目标fj(j=1,2,…,k)的的权系数数πi应该设为为0。这这种迭代代继续下下去，直直到决策策者满意意为止。。例题：某公司考考虑生产产两种光光电太阳阳能电池池：产品品甲和产产品乙。。这种生生产过程程会在空空气中引引起放射射性污染染。因此此，公司司经理有有两个目目标：极极大化利利润与极极小化总总的放射射性污染染。已知知在一个个生产周周期内，，每单位位甲产品品的收益益是1元元，每单单位乙产产品的收收益是3元。而而放射性性污染的的数量，，每单位位甲产品品是1.5个单单位,每每单位乙乙产品是是1个单单位.由由于机器器能力(小时)、装配配能力（（人时））和可用用的原材材料（单单位）的的限制，，约束条条件是目标有两两个:一一是利润润最大,二是污污染最小小.该问问题的多多目标规规划模型型如下:解:首先先,分别别求解两两个单目目标问题题的最优优解,由由它们得得到的目目标函数数值组成成理想解解.由此,构构造支付付表Xf1*f2*(7,13)(0,0)460-23.50由此计算算两个目目标与理理想值偏偏离的权权重解下列线线性规划划问题:由此求得得,分析者把把计算结结果交给给决策者者,决策策者将目目标值(21.192,-7.064)与与理想值值(46,0)比较,如果认认为f2是满意的的,但利利润太低低,并认认为污染染可接受受到10个单位位.于是是,约束束集修改改成进行下一一轮迭代代.首先先设π2=0,并并计算得得π1=1.将将模型修修改为由此求得得:决策者把把这一结结果与前前一轮的的解及理理想值作作比较,认为两两个目标标值都比比较满意意,则迭迭代结束束.线性规划划问题都都是处理理单个目目标的情情况，但但是在现现实世界界中有许许多问题题具有多多个目标标，这些些目标的的重要性性各不相相同，往往往有不不同的量量纲，有有的目标标相互依依赖，例例如决策策者既希希望实现现利润最最大，又又希望实实现产值值最大；；有的相相互抵触触，如决决策者既既希望充充分利用用资源，，又不希希望超越越资源限限量。而而决策者者希望在在某些限限制条件件下，依依次实现现这些目目标。这这就是目目标规划划所要解解决的问问题。当当所有的的目标函函数和约约束条件件都是线线性时，，我们称称其为线线性目标标规划问问题。在在这里我我们主要要讨论线线性目标标规划问问题。一、、目目标标规规划划模模型型的的建建立立目标标规规划划模模型型引例1：对于生产计划问题：

甲乙资源限额材料2324工时3226单位利润43

现在在工工厂厂领领导导要要考考虑虑市市场场等等一一系系列列其其他他因因素素，，提提出出如如下下目目标标：：（1））根根据据市市场场信信息息，，甲甲产产品品的的销销量量有有下下降降的的趋趋势势，，而而乙乙产产品品的的销销量量有有上上升升的的趋趋势势，，故故考考虑虑乙乙产产品品的的产产量量应应大大于于甲甲产产品品的的产产量量。。（2））尽尽可可能能充充分分利利用用工工时时，，不不希希望望加加班班。。（3））应应尽尽可可能能达达到到并并超超过过计计划划利利润润30元元。。现在在的的问问题题是是：：在在原原材材料料不不能能超超计计划划使使用用的的前前提提下下，，如如何何安安排排生生产产才才能能使使上上述述目目标标依依次次实实现现？？解：：（（1））决决策策变变量量：：仍仍设设每每天天生生产产甲甲、、乙乙两两种种产产品品各各为为x1和x2偏差差变变量量：：对对于于每每一一目目标标，，我我们们引引进进正正、、负负偏偏差差变变量量。。如对对于于目目标标1，，设设d1-表示示乙乙产产品品的的产产量量低低于于甲甲产产品品产产量量的的数数，，d1+表示示乙乙产产品品的的产产量量高高于于甲甲产产品品产产量量的的数数。。称称它它们们分分别别为为产产量量比比较较的的负负偏偏差差变变量量和和正正偏偏差差变变量量。。则则对对于于目目标标1，，可可将将它它表表示示为为等等式式约约束束的的形形式式-x1+x2+d1--d1+=0(目标约束束)同样设d2-和d2+分别表示示安排生生产时，，低于可可利用工工时和高高于可利利用工时时，即加加班工时时的偏差差变量，，则对目目标2，，有3x1+2x2+d2--d2+=26对于目标标3，设设d3-和d3+分别表示示安排生生产时，，低于计计划利润润30元元和高于于计划利利润30元的偏偏差变量量，有：：4x1+3x2+d3--d3+=30（2）约约束条件件：有资资源约束束和目标标约束资源约束束：2x1+3x2≤24目标约束束：为上上述各目目标中得得出的约约束（3）目目标函数数：三个个目标依依次为：：minZ1=d1-，minZ2=d2++d2-，minZ3=d3-因而该问题的数学模型可表述如下：minZ1=d1-，minZ2=d2++d2-，minZ3=d3-2x1+3x2≤24s．t．-x1+x2+d1--d1+=03x1+2x2+d2--d2+=264x1+3x2+d3--d3+=30案例2（（提级加加新问题题）某公司的的员工工工资有四四级，根根据公司司的业务务发展情情况，准准备招收收部分新新员工，，并将部部分员工工的工资资提升一一级。该该公司的的员工工工资及提提级前后后的编制制表如下下，其中中提级后后编制是是计划编编制，允允许有变变化，其其中1级级员工中中有8%要退休休。公司司领导的的目标如如下：（1）提提级后在在职员工工的工资资总额不不超过550千千元；（2）各各级员工工不要超超过定编编人数；；（3）为为调动积积极性，，各级员员工的升升级面不不少于现现有人数数的18%；（4）总总提级面面不大于于20%，但尽尽可能多多提；（5）4级不足足编制人人数可录录用新工工人。问：应如如何拟定定一具满满意的方方案，才才能接近近上述目目标？级别1234工资（千元）8643现有员工数10204030编制员工数10225230解：（1）决策策变量：：设x1,x2,x3,x4分别表示示提升到到1，2，3级级和新录录用的员员工数。。偏差变量量：为各各目标的的正、负负偏差变变量。（2）约约束条件件：1）提级后在在职员工工的工资资总额不不超过550千千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1--d1+=5502）各级员工工不要超超过定编编人数1级有：：10-108%+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+=2218%对3级有有：x2+d7--d7+=4018%对4级有有：x3+d8--d8+=3018%4）总提级面面人数不不大于20%，，但尽可可能多提提x1+x2+x3+d9--d9+=10020%（3）目目标函数数：minZ1=d1+minZ2=d2++d3++d4++d5+minZ3=d6-+d7-+d8-minZ4=d9++d9-案例3有三个产产地向四四个销地地供应物物资。产产地Ai(i=1,2,3)的的供应量量ai、销地Bj(j=1,2,3,4)的需需要量bj、各产销销地之间间的单位位物资运运费Cij如表2所所示。表表中，ai和bj的单位为为吨，Cij的单位为为元/吨吨。编制制调运方方案时要要求按照照相应的的优先级级依次考考虑下列列七个目目标：P1：B4是重重点保证证单位，，其需要要量应尽尽可能全全部满足足；P2：A3向B1提供供的物资资不少于于100吨；P3：每每个销地地得到的的物资数数量不少少于其需需要量的的80%；P4：实实际的总总运费不不超过当当不考虑虑P1至至P6各各目标时时的最小小总运费费的110%，，这里的的最小总总费用利利用第三三大题中中第2小小题求出出的结果果；P5：因因路况原原因，尽尽量避免免安排A2的物物资运往往B4；；P6：对对B1和和B3的的供应率率要尽可可能相同同；P7：力力求使总总运费最最省。试建立该该问题的的运筹学学模型。。CijBjAiB1B2B3B4aiA15267300A23546200A34523400bj200100450250解：用表表上作业业法可求求得不考考虑P1至P6各目标标时的最最小运费费调运方方案，相相应的最最小运费费为2950元元（1）决决策变量量：设Ai运往往Bj的的物资为为xij吨（2）约约束条件件：产量约束束B4销量量要满足足销量80%的限限制供应率尽尽可能相相同二、目标标规划的的解法由于目标标规划有有多个目目标，各各个目标标又有相相对不同同的重要要性，求求解时是是首先满满足重要要性权数数大的目目标，再再满足重重要性权权数次大大的目标标，所以以并不能能保证所所有的目目标都能能达到，，所求的的解也不不一定是是最优解解，而只只能求出出满意解解。（3）目标标函数求解目标规规划的仍用用单纯形法法，但是与与线性规划划的单纯形形法不同的的是，此时时检验数行行不再是一一行，而是是变化为一一个检验数数矩阵。

例4

用单纯形法求解如下线性目标规划模型minZ1=d1-，minZ2=d2++d2-，minZ3=d3-2x1+3x2≤24加入松驰变量化为标准形

2x1+3x2+x3=24s．t．-x1+x2+d1--d1+=03x1+2x2+d2--d2+=264x1+3x2+d3--d3+=30解（1）取x3，d1-，d2-，d3-为基变量，，建立初始始单纯形表表-1-2-1123-13402630Z1Z2Z3000-100-100-10000010010010010003[1]232-1342402630x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步骤骤完全与线线性规划的的单纯形法法一样。（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其中第一、、三目标已已达到最优优，第二个个目标未达达最优。目标利润Z=4x1+3x2=168/5某化工厂拟拟生产两种种新产品A和B，其其生产设备备投资分别别为：A，，2万元／／吨；B，，5万元／／吨。这两两种产品均均会造成环环境污染，，设由公害害所造成的的损失可折折算为：A，4万元元／吨；B，1万元元／吨。由由于条件限限制，工厂厂生产产品品A和B的的最大生产产能力各为为每月5吨吨和6吨，，而市场需需要这两种种产品的总总量每月不不少于7吨吨。试问工工厂如何安安排生产计计划，在满满足市场需需要的前提提下，使设设备投资和和公害损失失均达最小小。

工厂厂决策认为为：这两个个目标中环环境污染应应优先考虑虑，设备投投资的目标标值为20万元，公公害损失的的目标为12万元。。多目标规划划的建模作作业谢谢观看!9、静夜四四无邻，，荒居旧旧业贫。。。12月-2212月-22Friday,December23,202210、雨雨中中黄黄叶叶树树，，灯灯下下白白头头人人。。。。09:11:4009:11:4009:1112/23/20229:11:40AM11、以我独沈久久，愧君相见见频。。12月-2209:11:4009:11Dec-2223-Dec-2212、故人江海别别，几度隔山山川。。09:11:4009:11:4009:11Friday,December23,202213、乍见翻疑疑梦，相悲悲各问年。。。12月-2212月-2209:11:4009:11:40December23,202214、他乡生生白发，，旧国见见青山。。。23十十二月20229:11:40上午午09:11:4012月-2215、比不了了得就不不比，得得不到的的就不要要。。。十二二月月229:11上上午午12月月-2209:11December23,202216、行行动动出出成成果果，，工工作作出出财财富富。。。。2022/12/239:11:4009:11:4023December202217、做做前前，，能能够够环环视视四四周周；；做做时时，，你你只只能能或或者者最最好好沿沿着着以以脚脚为为起起点点的的射射线线向向前前。。。。9:11:40上上午午9:11上上午午09:11:4012月月-229、没有有失败败，只只有暂暂时停停止成成功！！。12月月-2212月月-22Friday,December23,202210、很多多事情情努力力了未未必有有结果果，但但是不不努力力却什什么改改变也也没有有。。。09:11:4009:11:4009:1112/23/20229:11:40AM11、成功功就是是日复复一日日那一一点点点小小小努力力的积积累。。。12月月-2209:11:4009:11Dec-2223-Dec-2212、世间间成事事，不不求其其绝对对圆满满，留留一份份不足足，可可得无无限完完美。。。09:11:4009:11:4009:11Friday,December23,202213、不不知知香香积积寺寺