多目标规划建模-17

数学建模主讲薛长虹E-mail地址:[e-mail]:315165网站：chxue.cuit.edu.cn多目标规划模型基本内容：1、多目标规划的基本概念2、多目标规划的问题的特征3、多目标规划的求解方法4、目标规划模型5、应用实例模型.一、多目标的基本概念多目标的问题:在现实生活中,决策的目标往往有多个,例如,对企业产品的生产管理,既希望达到高利润,又希望优质和低消耗,还希望减少对环境的污染等.这就是一个多目标决策的问题.。又如选购一个好的计算机系统,似乎只有一个目标,但由于要从多方面去反映,要用多个不同的准则来衡量,比如,性能要好,维护要容易,费用要省.这些准则自然构成了多个目标,故也是一个多目标决策问题.应用:研究解决这类问题在实际中是很有意义的，特别是在政治、经济、社会及军事管理、工程技术及科学决策等领域都有重要的应用价值。一般来说,多目标规划问题有两类.一类是多目标规划问题,其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方案.另一类是多目标优选问题,其对象是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选方案的优先等级与排序.二、多目标规划问题的分类多目标决策由于考虑的目标多,有些目标之间又彼此有矛盾,这就使多目标问题成为一个复杂而困难的问题.但由于客观实际的需要,多目标决策问题越来越受到重视,因而出现了许多解决此决策问题的方法.一般来说,其基本途径是,把求解多目标问题转化为求解单目标问题.然后利用单目标模型的方法,求出单目标模型的最优解,以此作为多目标问题的解.三、多目标规划问题的求解化多目标问题为单目标问题的方法大致可分为两类,一类是转化为一个单目标问题,另一类是转化为多个单目标问题,关键是如何转化.下面,我们介绍几种主要的转化方法:•主要目标法•线性加权和法•字典序法•步骤法多目标规划问题的求解f1f212345678在解决单目标问题时，我们的任务是选择一个或一组变量X，使目标函数f(X)取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标f1(X)，f2(X),希望它们都越大越好。下图列出在这两个目标下共有8个解的方案。其中方案1，2，3，4称为劣解，因为它们在两个目标值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却较差。一、解的特点多目标规划问题的特征二、模型结构多目标决策问题包含有三大要素：目标、方案和决策者。在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。1、多目标规划问题的模型结构0)(0)(..))(),....,(),(()(21XhXgtsXfXfXfXoptFjiTp),....,,(21nxxxX为决策变量如对于求极大(max)型，其各种解定义如下：绝对最优解：若对于任意的X，都有F（X*）≥F(X)有效解：若不存在X，使得F（X*）≤F(X)弱有效解：若不存在X，使得F（X*)F(X)2、多目标优选问题的模型结构可用效用函数来表示。设方案的效用是目标属性的函数：),...,,()(21pfffUxU并设)(jiijxfa且各个方案的效用函数分别为),...,,()(21pjjjjaaaUxU则多目标优选模型的结构可表示如下：0)(0)(..))(),....,(),(()(21XhXgtsXUXUXUXordUjiTp1),,1(1021piaaapia)()()()(min2211xfaxfaxfaxFpp(1)线性加权法:取对p个目标函数作线性加权化为单目标问题多目标规划问题的求解多目标规划问题的求解)(xfj,jfpjxffjjj,,2,1),(min即Tpffff,,,21Tpxfxfxfxf)(,),(),()(21)(xfffxfxU)()(min(2)理想点法:对每一个目标给出一个目标理想值则称为多目标函数值域中的一个理想点。将多目标问题转化为目标函数与之间的最小“距离”的单目标问题：))((max)(min1xfxUjpj)(xfjja))((max)(min1xfaxUjjpj(3)极大极小法：基本思想是在最不利的情况下求最有利的策略。即求多目标中最大目标函数值最小。于是可化为如下单目标问题：也可以给每个配上权系数，即考虑：多目标规划问题的求解（4）主要目标法在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。0)(0)(..))(),....,(),(()(21XhXgtsXfXfXfXoptFjiTp例如，在上述多目标问题中，假定f1(X)为主要目标，其余p-1个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即1,...,2,1,)(,...,2,1,0)(,...,2,1,0)(..)(max1pkXfmjXhniXgtsXfkkji多目标规划问题的求解例题1某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗A，B，C三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？甲乙资源限量资源A单位消耗资源B单位消耗资源C单位消耗9434510240200300单位产品的价格400600单位产品的利润70120单位产品的污染32解：问题的多目标模型如下0,300103200542404923))(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf对于上述模型的三个目标，工厂确定利润最大为主要目标。另两个目标则通过预测预先给定的希望达到的目标值转化为约束条件。经研究，工厂认为总产值至少应达到20000个单位，而污染控制在90个单位以下，即9023)(20000600400)(213212xxXfxxXf由主要目标法化为单目标问题0,300103200542404990232000060040012070)(max212121212121211xxxxxxxxxxxxxxXf用单纯形法求得其最优解为90)(,20750)(,4025)(,25.26,5.1232121xfxfxfxx（5）线性加权和目标规划0)(0)(..))(),....,(),(()(21XhXgtsXfXfXfXoptFjiTp在上述目标规划中，假定f1(X),f2(X),…,fp(X)具有相同的量纲,按照一定的规则分别给fi赋予不同的权系数ωi，作线性加权和评价函数piiiXfXU1)()(则多目标问题化为如下的单目标问题0)(0)(..)()(max1XhXgtsXfXUjipiii例如，某公司计划购进一批新卡车，可供选择的卡车有如下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按以下公式作无量纲的标准化处理1****)*(99jjjijijffffa其中：ijijijijffffminmax***变换后的指标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则925.57)(max*27.40)(925.57)(6.40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最优方案为选购A3型卡车（6）分层序列法：1.基本步骤：把(VP)中的p个目标按其重要程度排序。依次求单目标规划的最优解。2.过程：无妨设其次序为先求解得最优值，记再解得最优值，依次进行，直到得最优值则是在分层序列意义下的最优解集合。)(,),(1xfxfppfff,,,21SxtsxfP..)(min)(11*1fSfxfxS*111)(122..)(min)(SxtsxfP*2f1*222)(SfxfxS1..)(min)(pppSxtsxfP*pf1*)(ppppSfxfxS3.性质：，即在分层序列意义下的最优解是有效解。证明：反证。设，但，则必存在使即至少有一个j0，使,由于，即，矛盾。得证。4.进一步讨论：上述方法过程中，当某个问题(Pj)的解唯一时，则问题的求解无意义，因为解都是唯一的。实际求解时，有较宽容意义下的分层序列法：取为预先给定的宽容值，整个解法同原方法类似，只是取各约束集合时，分别取为：pjPP,,10,,011ppjSfxfxSjjjj,,3,2,)(1^*^)(min)(0000*~xffxfjSxjjj0~jSx)()(~~00xfyfjj1,,1),()(0~~jjxfyfjj)()(~~xFyFSy~*~paSxpSx~*papSS（7）步骤法（STEM法）这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。步骤法的基本思想是，首先需要求出原多目标问题的一组理想解(f1*,f2*,…,fp*)。实际上，这些解fi*(i=1,2,…,p)无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。步骤法算法如下：第一步：分别求解以下p个单目标问题的最优解0)(0)(..)(max1XhXgtsxcXfjinjjiji得到最优解，其相应的目标值即为理想值，此最优解处别的目标所取的值用表示，即，把上述计算结果列入下表)...,2,1(*piXi)...,2,1(*pifikizpkikXfzikki,...,2,1,),(****21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX