多目标规划模型

在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.在数学建模竞赛中，这类题目更为常见.一般的多目标规划问题都可写成如下的形式：

R={x|g_i（x）≤0，i=1，2，…，m}称为多目标规划问题的可行集或容许集，x∈R称为可行解或容许解.多目标规划问题与前面讲的规划问题的主要区别在于：目标函数不止一个，而是p个（p≥2）.

多目标规划问题的解法大致可分为两类：直接解法和间接解法.到目前为止，常用的多为间接解法，即根据问题的实际背景和特征，设法将多目标优化问题转化为单目标优化问题，从而得到满意解的方法.但是在转化为单目标问题时，需要注意不同目标的量纲和数量级的不同，需要进行处理.

主要目标法：在多目标优化问题中，若能从p个目标中，确定一个目标为主要目标，例如f₁（x），而把其余目标作为次要目标，并根据实际情况，确定适当的界限值，这样就可以把次要目标作为约束来处理，而将多目标优化问题转化为求解如下的线性或非线性规划问题：

令R={x|g_i（x）≤0，i=1，2，…，m；f_j（x）≤a_j，j=2，3，…，p}，其中界限值取为min x∈Rf_j（x）≤a_j，j=2，3，…，p，则此非线性规划问题的最优解必为原问题的弱有效解.因此，用主要目标法求得的解必是多目标优化问题的弱有效解或有效解.

分层序列法：把多目标规划问题中的p个目标按其重要程度排一个次序，假设f₁（x）最重要，f₂（x）次之，f₃（x）再次之，最后一个目标为f_p（x）.先求出以第一个目标f₁（x）为目标函数，而原问题中的约束条件不变的问题P₁：

上述模型的最优解x^（1）及最优值f^*₁，再求问题P₂：

上述模型的最优解x^（2）及最优值f^*₂，即，其中：R={x|g_i（x）≤0，i=1，2，…，m}，R₁为问题P₂的可行域.

再求解问题P₃：

上述模型得最优解x^（3）及最优值f^*₃，如此继续下去，直到求出第p个问题P_p：

得最优解x^（p）及最优值f^*_p，则x^*=x^（p）就是原多目标规划问题在分层序列意义下得最优解，F^*=（f₁（x^*），f₂（x^*），…，f_p（x^*））^T为其最优值.

容易看出，在使用分层序列法时，若对某个问题P_i，其最优解是唯一的，则问题P_i+1，…，P_p的最优解也是唯一的，且x^（i+1）=…=x^（p）=x^（i）.因此常将分层序列法修改如下：选取一组适当的小正数ε₁，…，ε_p，成为宽容值，把上述的问题P_i修改如下：

再按上述方法依次求解各问题 P₂，…，P_p.

线性加权求和法：对多目标规划问题中的p个目标按其重要程度给以适当的权系数w_i≥0，i=1，2，…，p，且，然后用作为新的目标函数，成为评价函数：

得最优解x^（0），取x^*=x^（0）作为多目标规划问题的解．

在一定条件下，用线性加权求和法求得的最优解必是原多目标规划问题的有效解或弱有效解.

例5-12　生产计划问题

某厂生产三种布料A₁，A₂，A₃，该厂两班生产，每周生产时间为80 h，能耗不得超过160t标准煤，其他数据如表5-15所示.问每周应生产三种布料各多少才能使该厂的利润最高，而能源消耗最少？

表5-15　某厂生产数据表

【解题思路】

设该厂每周生产布料A₁，A₂，A₃的小时数为x₁，x₂，x₃，总利润为y₁=-f₁（x），总能耗为y₂=f₂（x），其中x=（x₁，x₂，x₃）^T，则上述问题的数学模型可表达如下：

采用线性加权法可以将多目标问题转化为单目标问题，其中线性加权系数可以由决策者决定，转化为如下模型：

采用Lingo软件可以求得以上模型的答案，亦可以采用Lingo进行系数的敏感度分析，讨论不同系数对于答案带来的影响.

例5-13　飞机精确定位问题

飞机在飞行过程中，能够收到地面上各个监控台发来的关于飞机当前位置的信息，根据这些信息可以比较精确地确定飞机的位置.如图5-8所示，VOR是高频多向导航设备的英文缩写，它能够得到飞机与该设备连线的角度信息；DME是距离测量装置的英文缩写，它能够得到飞机与该设备的距离信息.表5-16中飞机接收到来自3个VOR给出的角度和1个DME给出的距离（括号内是测量误差限），并已知这4种设备的x，y 坐标（假设飞机和这些设备在同一平面上）.如何根据这些信息精确地确定当前飞机的位置？

图5-8　飞机定位示意图

表5-16　飞机定位记录数据表

【解题思路】

记4种设备VOR1、VOR2、VOR3、DME的坐标为（x_i，y_i）（以km为单位），i=1，2，3，4；VOR1、VOR2、VOR3测量得到的角度为θ_i（按照航空飞行管理的惯例，该角度是从北开始，沿顺时针方向的角度，取值在0°～360°之间），角度的误差限为σ_i，i=1，2，3；DME测量得到的距离为d₄（km），距离的误差限为σ₄.设飞机当前位置的坐标为（x，y），则问题就是在已知数据下计算（x，y）.注意到θ_i除了与点（x-x_i，y-y_i）的横纵坐标的比值有关外，还与这个点在4个象限中的哪个象限有关.

如果不考虑误差影响，问题可以建立以下数学模型：

这是一个超定方程的最小二乘拟合问题.

其中四象限反正切函数a tan2（b，a）是Matlab中的数学函数，可以根据点（a，b）在4个象限的位置，计算原点与点（a，b）的连线和x轴正向的夹角（逆时针方向夹角为正），正好相当于原点与点（b，a）的连线和y轴正向的夹角（顺时针方向夹角为正）.需要注意的是问题中角度和距离的量纲和数量级是不一致的，为了能够使用线性加权的方法，因此需要将绝对误差转化为相对误差.并且4种设备测量的精度（误差限）不同，因此这4个误差平方和不应该同等对待，而用各自的误差限σ_i对它们进行无量纲化地加权处理是合理的，即求解如下的无约束优化问题：

其中a和b 是线性加权权重，采用Lingo软件可以求得以上模型的答案，亦可以采用Lingo进行系数的敏感度分析，讨论不同系数对于答案带来的影响.

规划（优化）类数学模型在全国大学生数学建模竞赛得到广泛的应用，基本上每年都会涉及数学规划（优化）问题，因此学好本章的内容是非常重要的.在本章中，呈现了线性规划、非线性规划、整数规划、目标规划和动态规划这样几类规划模型.但是大家还需注意以下几点：规划的种类不止以上几类，优化类数学模型还有许多形式，涉及的数学方法也有许多，例如变分法等，优化类数学模型的难度往往在算法上，因此大家还是需要不断地学习；在竞赛中出现的问题一般要比上面提到的题目更难一些，虽然是相同的方法，但是涉及的运算量就大多了，求解优化问题也是一个难题.学好本章的内容可以给同学们打好基础，大家还需要不断学习.相信大家只要努力，都可以学好本章的内容，掌握解决优化问题的一些基本方法.