多目标规划建模-数学建模

《多目标规划建模-数学建模》由会员分享，可在线阅读，更多相关《多目标规划建模-数学建模（50页珍藏版）》请在金锄头文库上搜索。

1、数学建模,主讲 薛长虹 E-mail 地址: QQ: 315165,数学建模竞赛专题讲座,多目标规划模型,基本内容： 1、多目标规划的基本概念 2、多目标规划的问题的特征 3、多目标规划的求解方法 4、目标规划模型 5、应用实例模型.,一、多目标的基本概念,多目标的问题:在现实生活中,决策的目标往往有多个,例如,对企业产品的生产管理,既希望达到高利润,又希望优质和低消耗,还希望减少对环境的污染等.这就是一个多目标决策的问题. 。 又如选购一个好的计算机系统,似乎只有一个目标,但由于要从多方面去反映,要用多个不同的准则来衡量,比如,性能要好,维护要容易,费用要省.这些准则自然构成了多个目标,故

2、也是一个多目标决策问题. 应用:研究多目标决策问题的前提，因此研究解决这类问题在实际中是很有意义的，特别是在政治、经济、社会及军事管理、工程技术及科学决策等领域都有重要的应用价值。,一般来说,多目标规划问题有两类.一类是多目标规划问题,其对象是在管理决策过程中求解使多个目标都达到满意结果的最优方案.另一类是多目标优选问题,其对象是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选方案的优先等级与排序.,二、多目标规划问题的分类,多目标决策由于考虑的目标多,有些目标之间又彼此有矛盾,这就使多目标问题成为一个复杂而困难的问题.但由于客观实际的需要,多目标决策问题越来越受到重视,因而出现了许多

3、解决此决策问题的方法.一般来说,其基本途径是,把求解多目标问题转化为求解单目标问题.其主要步骤是,先转化为单目标问题,然后利用单目标模型的方法,求出单目标模型的最优解,以此作为多目标问题的解.,三、多目标规划问题的求解,化多目标问题为单目标问题的方法大致可分为两类,一类是转化为一个单目标问题,另一类是转化为多个单目标问题,关键是如何转化. 下面,我们介绍几种主要的转化方法:主要目标法、线性加权和法、字典序法、步骤法。,多目标规划问题的求解,在解决单目标问题时，我们的任务是选择一个或一组变量X，使目标函数f(X)取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁

4、优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标f1(X)，f2(X),希望它们都越大越好。下图列出在这两个目标下共有8个解的方案。其中方案1，2，3，4称为劣解，因为它们在两个目标值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却更差。,一、解的特点,多目标规划问题的特征,二、模型结构 多目标决策问题包含有三大要素：目标、方案和决策者。 在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目

5、、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。 多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题 的方案是无限的。方案有其特征或特性，称之为属性。,1、多目标规划问题的模型结构,为决策变量,如对于求极大(max)型，其各种解定义如下： 绝对最优解：若对于任意的X，都有F（X*）F(X) 有效解：若不存在X，使得F（X*） F(X) 弱有效解：若不存在X

6、，使得F（X*)F(X),2、多目标优选问题的模型结构 可用效用函数来表示。设方案的效用是目标属性的函数：,并设,且各个方案的效用函数分别为,则多目标优选模型的结构可表示如下：,多目标规划问题的求解,多目标规划问题的求解,(2)理想点法:对每一个目标,给出一个目标理想值,则称,为多目标函数,值域中的一个理想点。 将多目标问题转化为目标函数,与,之间的最小“距离”的单目标问题：,(3)极大极小法：基本思想是在最不利的情况下求最有利的策略。即求多目标中最大目标函数值最小。于是可化为如下单目标问题：,也可以给每个,配上权系数,，即考虑：,多目标规划问题的求解,（4）主要目标法 在有些多目标决策问题中

7、，各种目标的重要性程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。,例如，在上述多目标问题中，假定f1(X)为主要目标，其余p-1个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即,多目标规划问题的求解,例题1 某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗A，B，C三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？,解：问题的多目标模型如下,对于上述模型的

8、三个目标，工厂确定利润最大为主要目标。另两个目标则通过预测预先给定的希望达到的目标值转化为约束条件。经研究，工厂认为总产值至少应达到20000个单位，而污染控制在90个单位以下，即,由主要目标法化为单目标问题,用单纯形法求得其最优解为,（5）线性加权和目标规划,在上述目标规划中，假定f1(X),f2(X),fp(X)具有相同的量纲,按照一定的规则分别给fi赋予相同的权系数i，作线性加权和评价函数,则多目标问题化为如下的单目标问题,例如，某公司计划购进一批新卡车，可供选择的卡车有如下4种类型：A1，A2，A3，A4。现考虑6个方案属性：维修期限f1，每100升汽油所跑的里数f2，最大载重吨数f3

9、，价格（万元）f4，可靠性f5，灵敏性f6。这4种型号的卡车分别关于目标属性的指标值fij如下表所示。,首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：,可靠性和灵敏性都属于效益型指标，其打分如下,按以下公式作无量纲的标准化处理,其中：,变换后的指标值矩阵为：,设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3), 则,故最优方案为选购A3型卡车,（6）分层序列法： 1.基本步骤：把(VP)中的p个目标 按其重要程度排序。依次求单目标规划的最优解。 2. 过程：无妨设其次序为 先求解 得最优值 ，记 再解 得最优值 ， 依次进行，直到 得最优值 则 是

10、在分层序列意义下的最优解集合。,3. 性质： ，即在分层序列意义下的最优解是有效解。 证明：反证。设 ，但 ，则必存在 使 即至少有一个j0 ，使 , 由于 ，即 ， 矛盾。得证。 4. 进一步讨论： 上述方法过程中，当某个问题(Pj)的解唯一时，则 问题 的求解无意义，因为解都是唯一的。 实际求解时，有较宽容意义下的分层序列法： 取 为预先给定的宽容值，整个解法同原 方法类似，只是取各约束集合时，分别取为：,（7）步骤法（STEM法） 这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。 步骤法的基本思想是，首先需要求出原多目标问题的一组理想解(f1*,f2*,fp

11、*)。实际上，这些解fi*(i=1,2,p)无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。 步骤法算法如下： 第一步：分别求解以下p个单目标问题的最优解,得到最优解 ，其相应的目标值 即为 理想值，此最优解处别的目标所取的值用 表示，即 ，把上述计算结果列入下表,在表中，确定每一列的最小值并记第i列的最小值为fip(i=1,2,p),第二步：求解,其中：,这里,（1）,第三步：将上述模型（1）的解X0与相应的目标值f1(X0), f2(X0)

12、, ,fp(X0) 交给决策者去判断。决策者把这些目标值与理想值进行比较后，如果认为其中某些目标值太坏，另一些目标值可以不要那么太好，可以把比较好的目标值中的某一个修改得差一些，以使水平太坏的目标得到改善。 当决策者减少了第j个目标的值 之后，约束条件S应该改为S*,在进行下一次迭代时，对应于降低了要求的那些目标fj(j=1,2,k)的权系数i应该设为0。这种迭代继续下去，直到决策者满意为止。,例题：某公司考虑生产两种光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收益是1元，

13、每单位乙产品的收益是3元。而放射性污染的数量，每单位甲产品是1.5个单位,每单位乙产品是1个单位.由于机器能力(小时)、装配能力（人时）和可用的原材料（单位）的限制，约束条件是,目标有两个:一是利润最大,二是污染最小.该问题的多目标规划模型如下:,解:首先,分别求解两个单目标问题的最优解,由它们得到的目标函数值组成理想解.,由此,构造支付表,由此计算两个目标与理想值偏离的权重,解下列线性规划问题:,由此求得,分析者把计算结果交给决策者,决策者将目标值与理想值(21.192,-7.064)与理想值(46,0)比较,如果认为f2是满意的,但利润太低,并认为污染可接受到10个单位.于是,约束集修改成

14、,进行下一轮迭代.首先设2=0,并计算得1=1.将模型修改为,由此求得:,决策者把这一结果与前一轮的解及理想值作比较,认为两个目标值都比较满意,则迭代结束.,线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。 一、目标

15、规划模型的建立,目标规划模型,现在工厂领导要考虑市场等一系列其他因素，提出如下目标： （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+3x224 目标约束：为上述各目标中得出的约束 （3）目标函数：三个目标依次为：