数学建模培训多目标规划

多目标规划数学建模培训2019.07多目标规化模型多目标规划是数学规划的一个分支。研究多于一个的目标函数在给定区域上的最优化。又称多目标最优化。通常记为MOP(multi-objectiveprogramming)。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。例如,对企业产品的生产管理,既希望达到高利润,又希望优质和低消耗,还希望减少对环境的污染等。这就是一个多目标决策的问题。又如选购一个好的计算机系统,似乎只有一个目标,但由于要从多方面去反映,要用多个不同的准则来衡量,比如,性能要好,维护要容易,费用要省。这些准则自然构成了多个目标,故也是一个多目标决策问题。一般来说,多目标决策问题有两类。一类是多目标规划问题,其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方案。另一类是多目标优选问题,其对象是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选方案的优先等级与排序。多目标决策由于考虑的目标多,有些目标之间又彼此有矛盾,这就使多目标问题成为一个复杂而困难的问题.但由于客观实际的需要,多目标决策问题越来越受到重视,因而出现了许多解决此决策问题的方法.一般来说,其基本途径是,把求解多目标问题转化为求解单目标问题.其主要步骤是,先转化为单目标问题,然后利用单目标模型的方法,求出单目标模型的最优解,以此作为多目标问题的解.化多目标问题为单目标问题的方法大致可分为两类,一类是转化为一个单目标问题,另一类是转化为多个单目标问题,关键是如何转化.以下,我们会介绍几种主要的转化方法:主要目标法、线性加权和法、字典序法、步骤法。一、多目标规划及其解多目标规划包含有三大要素：目标、方案和决策者。在多目标规划中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。多目标规划中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。（一）任何多目标规划问题，都由两个基本部分组成:（1）两个以上的目标函数；（2）若干个约束条件。（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：（2）)(max(min))(max(min))(max(min))(max(min)21XfXfXfXFZkmmgggGXXXX2121)()()()(（1）式中：为决策变量向量。TnxxxX],,,[21（三）多目标规划解的特点对于上述多目标规划问题，求解就意味着需要做出如下的复合选择：（1）每一个目标函数取什么值，原问题可以得到最满意的解决？（2）每一个决策变量取什么值，原问题可以得到最满意的解决？多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。非劣解：可以用图3说明。图3多目标规划的劣解与非劣解二、多目标规划问题的建模方法为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化，有如下几种建模方法。（三）约束模型理论依据：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中。假如，除第一个目标外，其余目标都可以提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：用目标达到法求解多目标规划的计算过程，可以通过调用Matlab软件系统优化工具箱中的fgoalattain函数实现。三、多目标规划问题的求解(化多为少的方法)1、主要目标法在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。0)(0)(..)(..))(),....,(),(()(21XhXgtsorGXtsXfXfXfXoptFjiTk例如，在上述多目标问题中，假定f1(X)为主要目标，其余p-1个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即1,...,2,1,)(,...,2,1,0)(,...,2,1,0)(..)(max1pkXfmjXhniXgtsXfkkji例题某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗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xfxfxfxx2、线性加权和目标规划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很高一般首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：变换后的指标值矩阵为：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型卡车4、步骤法（STEM法）这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。步骤法的基本思想是，首先需要求出原多目标问题的一组理想解(f1*,f2*,…,fk*)。实际上，这些解fi*(i=1,2,…,k)无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。把上述计算结果列入下表***21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX例题：某公司考虑生产两种光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收益是1元，每单位乙产品的收益是3元。而放射性污染的数量，每单位甲产品是1.5个单位,每单位乙产品是1个单位.由于机器能力(小时)、装配能力（人时）和可用的原材料（单位）的限制，约束条件是)(725)(42.02.0)(825.05.0212121原材料装配能力机器能力xxxxxx)(725)(42.02.0)(825.05.05.1)(,3)())(),(()(max21212121221121原材料装配能力机器能力xxxxxxxxXfxxXfXfXfXFT目标有两个:一是利润最大,二是污染最小.该问题的多目标规划模型如下:解:首先,分别求解两个单目标问题的最优解,由它们得到的目标函数值组成理想解.)(725)(42.02.0)(825.05.03)(max212121211原材料装配能力机器能力xxxxxxxxXf)(725)(42.02.0)(825.05.05.1)(max212121212原材料装配能力机器能力xxxxxxxxXf46*)13,7(1*1fX0*)0,0(1*2fX由此,构造支付表Xf1*f2*(7,13)(0,0)460-23.50由此计算两个目标与理想值偏离的权重：637.0,363.0,555.0,316.02121解下列线性规划问题:0,,7254)2.02.08)25.05.0)230(637.0)346(363.0min212121212121xxxxxxxxxxxx0,,7254)2.02.08)25.05.0192.21310)5.1346min21212121212121xxxxxxxxxxxxxx进行下一轮迭代.首先设π2=0,并计算得π1=1.将模型修改为由此求得:10,3010,02121ffxx决策者把这一结果与前一轮的解及理想值作比较,认为两个目标值都比较满意,则迭代结束.线性目标规划模型线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。一、线性目标规划模型的建立例1：某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为8元和10元；生产单位甲、乙两种产品需要消耗的原