最优化方法-第五章多目标规划

第四章多目标规划

本书大部分章节讨论的基本上都是单目标优化问题，实际上，许多实际问题的优化牵涉的目标往往不止一个，如设计一个工厂的施工方案，就要考虑工期、成本、质量、污染等目标,再如找工作,购买家用电器,追求的目标往往都不止一个。由于这类问题需同时考虑多个目标，而有些目标之间又相互矛盾，从而使决策问题变得复杂,这类决策问题称为多目标决策问题。多目标决策方法是现代管理科学的重要内容，也是系统分析的基本工具。按照决策变量是连续的还是离散的，多目标决策可以分为多目标规划决策(MultipleObjectiveDecisionMaking)和多准则决策(MultipleAttributeDecisionMaking)两大类，前者是以数学规划的形式呈现的决策问题，后者则是已知各个方案及它产生的结局向量，由此选择最优方案的决策。

多目标决策主要指多目标最优化，即多目标规划。对于某些问题，可以先用多目标规划选出几个备选方案，然后再用多准则决策方法作进一步处理，因此，这两者既有区别又有联系。多目标最优化的思想萌芽于1776年经济学中的效用理论。1896年，法国经济学家V·Pareto首先在经济理论的研究中提出了多目标最优化问题。1951年，美国数理经济学家T·C·Koopans从生产和分配的活动分析中考虑了多目标决策问题，并首次提出了多目标最优化问题解的概念，将其命名为“Pareto解”(即有效解)。同年，H·W·Kuhn和A·W·Tucker从数学规划论角度首次提出向量极值问题及有关概念。进入20世纪70年代，随着第一次国际多目标决策研讨会的召开及这方面专著的问世，多目标决策问题的研究工作迅速、蓬勃地开展起来，到目前为止，已取得若干有价值的研究成果。第一节多目标规划模型

线性规划及非线性规划研究的都是在给定的约束集合

R={X|gi(X)≥0，i=1，2，……，m)}X∈En上，求单目标f(x)的最大或最小的问题，即方案的好坏是以一个目标去衡量。然而，在很多实际问题中，衡量一个方案的好坏往往难以用一个指标来判断。也就是说，需要用一个以上的目标去判断方案的好坏，而这些目标之间又往往不是那么协调，甚至是相互矛盾的。本章将以实例归结出几类常见的描述多目标最优化问题的数学模型。第四章多目标规划一.一般多目标规划模型例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最佳的采购方案。我们先确定此问题应满足的条件（即约束条件）。不难看出，当甲级糖数量为x1，乙级糖数量为x2时，有：

在研究以什么为“最佳”的衡量标准时，“筹备小组”的成员们意见可能会发生分歧，其原因是他们会提出各种各样的目标来。如果要求总花费最小，即要求：

f1(x1,x2)=4x1+2x2

→min

如果要求糖的总数量最大，即要求：如果要求甲级糖的数量最大，即要求：易见，这是具有3个目标的规划问题（由于约束及目标均为线性函数，故它为多目标线性规划问题）。例2：【投资决策问题】某投资开发公司拥有总资金A万元，今有n(≥2)个项目可供选择。设投资第i(i=1，2，……，n)个项目要用资金ai万元，预计可得到收益bi万元。问应如何使用总资金A万元，才能得到最佳的经济效益？xi=0或1

所谓“最佳的经济效益”，如果理解为“少花钱多办事”，则变为两个目标的问题，即投资最少，收益最大：这是具有两个目标的0－1规划问题。例3：【木梁设计问题】把横截面为圆形的树干加工成矩形横截面的木梁。为使木梁满足一定的规格和应力及强度条件，要求木梁的高度不超过H，横截面的惯性矩不少于给定值W，且横截面的高度要介于其宽度和4倍宽度之间。问应如何确定木梁尺寸，可使木梁的重量最轻，并且成本最低。设所设计的木梁横截面的高为x1

，宽为x2（图1）。为使具有一定长度的木梁重量最轻，应要求其横截面面积x1x2为最小，即要求x1x2→min

x1

x2图1r

由于矩形横截面的木梁是由横截面为圆形的树干加工而成的，故其成本与树干横截面面积的大小成正比。由此，为使木梁的成本最低还应要求尽可能的小，或即：根据问题的要求，应满足下述约束条件：这是具有两个目标的非线性规划问题。

由以上实例可见，多目标最优化模型与单目标最优化模型的区别主要是目标多于一个。在这些目标中，有的是追求极大化，有的是追求极小化，而极大化与极小化是可以相互转化的。因此，我们不难将多目标最优化模型统一成一般形式：决策变量：x1，……，xn

目标函数：minf1(x1，……，xn)………………minfp(x1，……，xn)

若记X=(x1，……，xn)，V-min表示对向量F(X)=[f1(X)，

……，fp(X)]T中的各目标函数f1(X)，……，fp(X)同等的进行极小化。R={X|gi(X)≥0，i=1，……，m}表示约束集。则模型一般式也可简记为这里(VMP)为向量数学规划(VectorMathematicalProgramming)的简写。二.分层多目标规划模型

本节介绍一类不同于(VMP)形式的多目标最优化模型。这类模型的特点是：在约束条件下，各个目标函数不是同等的被优化，而是按不同的优先层次先后的进行优化。例如，在例1中，若筹备小组希望把所考虑的三个目标按重要性分成以下两个优先层。第1优先层——总的花费最小。第2优先层——糖的总数量最大。甲级糖数量最大。

那么这种先在第1优先层次极小化总花费，然后在此基础上再在第2优先层次同等的极大化糖的总数量和甲级糖的问题，就是所谓分层多目标最优化问题。可将其目标函数表示为：

L-min{P1[f1(X)]，P2[f2(X)，f3(X)]}

其中P1，P2是优先层次的记号，L-min表示按优先层次序进行极小化。下面，我们来看一个建立分层多目标最优化模型的例子例4：某水稻区一农民承包10亩农田从事农业种植。已知有三类复种方式可供选择，其相应的经济效益如表

方案复种方式粮食产量(公斤/亩)油料产量(公斤/亩)利润(元/亩)投入氮素(公斤/亩)用工量(小时/亩)1大麦－早稻－晚梗1056——120.27503202大麦－早稻－玉米1008——111.46483503油菜－玉米－蔬菜336130208.2740390

设该农户全年至多可以出工3410小时，至少需要油料156公斤。今该农户希望优先考虑总利润最大和粮食总产量最高，然后考虑使投入氮素最少。问如何确定种植方案。首先设立决策变量如下方案1的种植亩数：x1，方案2的种植亩数：x2，方案3的种植亩数：x3，根据农户的要求确定问题的三个目标函数为：

年总利润：

f1(x1，x2，x3)=120.27x1+111.46x2+208.27x3

粮食总产量：

f2(x1，x2，x3)=1056x1+1008x2+336x3

投入氮素量：

f3(x1，x2，x3)=50x1+48x2+40x3

根据农户的全年出工能力，对油料需求量，所承包农田数以及种植亩数应为非负等限制，应有约束条件：

总用工量：320x1+350x2+390x3≤3410

油料需求：130x3≥156

农田数：x1+x2+x3＝10

种植亩数非负：x1≥0，x2≥0，x3≥0。

根据农户对目标重要性的排序，将前两个目标作为第一优先层，将第三个目标作为第二优先层，再把其中的求最大化转化为求其负数的最小，便得到下列具有两个优先层次的分层多目标极小化模型：对它进行求解便可得到农户满意的种植方案。三.目标规划模型

本节介绍一类在实际中有着广泛应用的特殊多目标最优化模型。这类模型并不是去考虑对各个目标进行极小化或极大化，而是希望在约束条件的限制下，每一目标都尽可能的接近于事先给定的各目标值。设p个目标函数的给定目标值分别为：例5：某机器制造厂生产两种型号的机器，同时也进行机器的零部件和工业性作业生产。已知有关数据如下表，并且该工厂全年能承担生产的总工时为58万小时。生产项目单位产值利润工时需要量1号机套5万元/套1万元/套1000小时/套160套(指令性计划)2号机台1.6万元/套0.2万元/台400小时/台320～500台(市场预测)零部件和工业性作业万小时50元/小时8.1元/小时26万小时(市场预测)

今决策者希望在完成上级下达的指令性计划的前提下，全年总产值达到2750万元左右，总利润不低于440万元，并且要避免开工不足。然后，还希望工人的加班时间不超过总工时的4％，以及依据市场预测的信息进行生产。试问应如何安排工厂的年生产计划。首先，设立决策变量为

x1：生产1号机套数

x2：生产2号机台数

x3：生产零部件和工业性作业的工时数(万小时)第二节多目标规划问题的解

在单目标规划问题中，任意两个可行方案都可通过比较其目标函数值来确定其优劣。在所有可行方案中，使目标达最优的就是最优解。而在多目标规划问题中，约束集R中的两个方案x1，x2其优劣往往不能进行比较。这是因为它们的目标值F(X1)与F(X2)是向量，而向量是无法直接比较大小的。所以，在R中也往往不存在一个方案对每个目标都是最优的。这种多目标规划问题区别于单目标规划问题的本质表明，仅仅将单目标问题最优解的概念平移到多目标问题中是不行的。本章将介绍多目标规划问题各种解的概念及其相互关系。一.各种解的概念图2给出了两个目标，一维变量时绝对最优解的例子图3给出了两个目标，一维变量时有效解集合的例子二.各种解之间的关系多目标决策与单目标决策区别点评价与向量评价 单目标：方案dj←评价值f(dj)

多目标：方案dj←评价向量(f1(dj)，f2(dj)…，fp(dj))全序与半序:方案di与dj之间 单目标问题:di<dj;di=dj;di>dj

多目标问题：除了这三种情况之外,还有一种情况 是不可比较大小决策者偏好：多目标决策过程中，反映决策者对 目标的偏好。解概念区别解的概念单目标决策的解只有一种（绝对）最优解多目标决策的解有下面四种情况：绝对最优解劣解有效解(pereto解)弱有效解d1807588有效解d2758185有效解d3767889有效解劣解d5797486d4858292绝对最优解数学外语专业解的类型多目标决策解的例子第三节多目标最优化问题的解法

求解多目标最优化模型，就是要根据问题的特点和决策者的意图，选择适当解法，求得模型的有效解或弱有效解。本章将介绍一些常用的多目标最优化问题解法。一.评价函数法λkp……λk2λk1k…………………………λ2p……λ22λ212λ1p……λ12λ111……fp(X)……f2(X)f1(X)

目标权系数老手二.分层求解法

本节将针对第一节中介绍的分层多目标最优化模型，介绍一般的分层评价法和适用于线性分层模型的分层单纯形法。

1、分层评价法设将目标分为L个优先层，则可首先在约束集R上对第一优先层进行多目标极小化，然后在第一层优化所得的（弱）有效解集上对第二层进行优化，然后在第二层优化所得的（弱）有效解集上对第三层进行优化……

可以证明，按分层评价法进行求解时，只要每一层选用的评价函数都是严格增的，则最后所得的解必为相应的不分层多目标最小化模型的有效解。

上述结果表明：若该农户认为利润和粮食目标在问题中的重要程度分别为0.6和0.4的话，则他应该选择如下的种植方案：方案1种植7亩，方案2不种植，方案3种植3亩。这时，还可算出年总利润＝1466.66元粮食总产量＝8400公斤氮素投入量＝470公斤油料产量＝390公斤总用工量＝3410小时

2、分层单纯形法将普通单纯形法加以适当推广，便可用来求解分层多目标线性规划模型。其一般步骤如下：

(1)将每一优先层中各目标函数通过评价函数法（如线性加权和）转化为单目标；

(2)用单纯形法求解各层目标相应的线性规划问题。设共有L个优先层，则在每张单纯形表上的检验数位置有L行检验数(Cj-CBB-1pj)，将P1层对应的检验数写在最下行，PL层对应的检验数写在最上行。

(3)检验调整时由下往上，先调P1行（迭代方法同单纯形法），直至P1行检验数满足最优性要求（检验数≥0），再开始调P2行。若某行负检验数相应下行中有正检验数，则根据“高级优先”的原则，放弃调整该列。这样进行直至无法再调时（全部检验数为非负或虽有某为负，但其下方有正的）为止。0000000001-2020-31-1-1P3P2P10010101000011[1]-110-1x45x52x64x6x5x4x3x2x1XBB-1b0000030001-200001-1-1P3P2P1001-111100001010[1]0-1x43x22x66x6x5x4x3x2x1XBB-1b0001-12-1111-20000000P3P2P1001-11010100[1]010100x13x22x69x6x5x4x3x2x1XBB-1bXBB-1bx1x2x3x4x5x6x13x22x39100010001101-110001P3P2P1000000000-231-1-12-120三.目标规划法

第一节提出的目标规划模型(3)已经化为单目标问题。特别，当目标函数fi(X)(i=1，……，p)和约束R均为线性时，它就是一个线性规划，其解法不必赘述。本节主要举例说明在实际中常用的分层加权线性目标规划的解法。例12有一纺织厂生产尼龙和棉布，平均生产能力都是1千米/小时，工厂生产能力为每周80小时。根据市场预测，下周最大销量为：尼龙布70千米，棉布45千米，尼龙布利润为2.5元/米，棉布利润为1.5元