多目标规划2人文社科

1/1多目标规划2-人文社科

第五章多目标规划1.问题的提出与目标规划的数学模型2.目标规划的图解分析法

3.用单纯形法求解目标规划4.求解目标规划的层次算法

5.应用举例

1.问题的提出与目标规划的数学模型线性规划、整数规划和后面将要学习的动态规划都是解决单个目标函数在一组约束条件下的极值问题。但在许多实际问题中，在一组约束条件下，往往要求实现多个目标。例如，在企业支配生产问题中，既要利润高，又要消耗低，还要考虑市场需求，等等。这些目标的重要性各不相同，目标规划正是为了解决这类多目标规划问题而产生的，它能把决策者的意愿反映到数学模型中去。

线性规划问题的局限性：1.要求问题的解必需满意全部约束条件，但实际问题中并非全部约束都需严格满意；2.只能处理单目标的优化问题，因此线性规划模型认为地将一些次要目标转为约束。而实际问题中，目标和约束可以相互转化，处理时不肯定严格区分；3.线性规划中各个约束条件都处于同等重要的地位，但实际问题中，各目标的重要性是有差别的；4.线性规划寻求最优解，但许多实际问题中只需找出满足解就可以了。

一、问题的提出最佳生产方案问题某工厂方案生产甲、乙两种产品，这两种产品的有关数据如下表所示。

工厂在作决策时，要实现如下的目标：目标1:依据市场信息，产品甲的销售量有下降的趋势，故考虑产品甲的产量不大于产品乙；

目标2:超过方案供应的原料时，需要高价选购，使成本增加，因而只选购方案供应的原料；目标3:应尽可能利用现有设备，但不盼望加班；目标4:应尽可能达到并超过方案利润指标(56元)。这样，在考虑产品生产决策时，不再是单纯追求利润最大，而是同时要考虑多个目标，这样的问题一般的线性

规划方法已无法解决，需引入一种新的数学模型——目

标规划。

二、目标规划模型的建立1.偏差变量用来表示实际值与目标值之间的差异。

d+——超出目标的差值，称为正偏差变量。d-——未达到目标的差值，称为负偏差变量。因实际决策值不行能既超过目标值又低于目标值，故最终结果中恒有d+d-=0(即两者至少有一个为0)。目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量。

2.肯定约束和目标约束

肯定约束是指必需严格满意的等式约束或不等式约束；如线性规划问题的全部约束条件，不能满意这些条件的解称为非可行解，所以肯定约束是硬约束。

目标约束是目标规划所特有的一种约束，它把要追求的目标值作为右端常数项，在追求

此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的软约束。

目标约束不会不满意，但可能偏差过大。

假设问题中甲、乙两产品的产量分别为x1和x2。肯定约束：问题中的目标2,在原料供应受严格限制的基础上考虑，可写成肯定约束为

2x1x211目标约束：问题中的目标4可写成目标约束为

8x110x256dd

1

1

化为标准形式是：8x110x2d1d156线性目标约束的一般形式是：

fiXddbiiiTni1

其中：

Xx1,x2,,xn,fiXCijxj

3.优先因子和权系数目标规划中，当决策者要求实现多个目标时，这些目标之间是有主次区分的。凡要求第一位达到的目标，赋于优先因子p1,要求第二位达到的目标，赋于优先因子p2…并规定pk+1∝pk,表示pk比pk+1有肯定优先权。因此，不同的优先因子代表着不同的优先等级。在实现多个目标时，首先保证p1级目标的实现，这时可不考虑其它级目标，而p2级目标是在保证p1级目标值不变的前提下考虑的，以此类推。若要区分具有相同优先因子的多个目标，可分别给予它们不同的权系数k。越重要的目标，其权系数的值越大。

4.目标函数

目标规划的目标函数是由各目标约束的正、负偏差变量及相应的优先因子、权系数构成的，其中不含决策变量。由于决策者的愿望总是尽可能缩小偏差，实现目标。故总是将目标函数微小化，其基本形式有三种。对于第i个目标:

fiXddbiii

(1)若要求决策值超过目标值，则相应的负偏差变量要尽可能地小，而对正偏差变量不加限制，目标函数的形式为：

mind

i

(2)允许达不到目标值，就是相应的正偏差变量要尽可能地小，目标函数的形式为：

mind

i

(3)恰好达到目标，则相应的正、负偏差变量都要尽可能地小，目标函数的形式为：

minddi

i

加入优先因子和权系数后，建立目标函数，其一般形式为：

minzpkddk1l1kllkl

K

L

l

前述问题的目标规划模型可以写为：

minzpdp2ddpd,2x1x211xxdd2110,1x12x2d2d210,8x110x2d3d356,x1,x2,di,di0,i1,2,3。

11

2

2

33

s.t.

目标规划的一般数学模型，见教材135~136页。

2.目标规划的图解分析法对于只有两个决策

变量的线性目标规划的数学模型，可以用图解法来分析求解。传统的线性规划一般只是寻求一个点，在这个点上得到单目标的最优值，目标规划一般是寻求一个区域，这个区域供应了相互冲突的目标集的折衷方案。

步骤1建立直角坐标系，令各偏差变量为0,作出全部的约束直线。满意全部肯定约束条件的区域，用阴影标出。

步骤2作图表示差变量增减对约束直线的影响

在全部目标约束直线旁标上d+,d-,如图所示。这表明目标约束直线可以沿d+,d-,所示的方向平移。

步骤3依据目标函数中的优先因子次序，逐步分析求解。依据目标函数中的优先因子次序，首先考虑具有优先因子p1的目标的实现。目标函数要求实现mind1+,从图中可见，可以满意d1+=0,这时，只能在三角形OBC的区域上取值；考察具有优先因子p2的目标，此时可在线段ED上取值；

考察优先因子p3的目标，这就使取值范围缩小到线段GD上，该线段上全部点的坐标，都是问题的解。

多目标规划问题的另一类表示方法买糖问题设商店有甲、乙、丙三种糖果，单价分别为4元/kg,2.80元/kg和2.40元/kg。今要筹办一次节日茶话会，要求用于买糖的钱数不超过20元，糖的总量不少于6kg,甲、乙两种糖的总和不少于3kg,问应如何确定最好的买糖方案。

解：设购买甲,乙,丙三种糖果的斤数分别为x1,x2,x3用于买糖所花的钱数为y1,所买糖的总斤数为y2。我们盼望y1取最小值，y2取最大值。

y14x12.8x22.4x3miny2x1x2x3max

约束条件可以写为：

4x12.8x22.4x320x1x2x36x1x23x1,x2,x30这是含有两个目标的线性规划问题，这里可以将求y2的最大值转化为求(-y2)的最小值，这时目标函数可以写为：

Vminf1x,f2x其中：

T

f1(x)y1,f2(x)y2,x(x1,x2,x3)T

3.用单纯形法求解目标规划因此利用单纯形法求解步骤也基本相同，但是需要尤其注

目标规划的数学模型与线性规划的数学模型基本相同，

意它们之间的区分。线性规划的单纯形法求解过程：1.建立初始单纯形表，计算出全部变量的检验数。2.在非基变量检验数中找到最大的正数σj,它所对应的变量xj作为换入基的变量。3.对于全部aij0计算bi/aij,其中最小的元素θ所对应的基变量xi作为换出基的变量。4.建立新单纯形表，重复上述步骤2、3,直到全部检验数都小于等于零。

由于目标规划的目标函数都是求微小化问题，而线性规划问题的标准型中目标函数都是求极大化问题，因此在用单纯形法

求解时要留意一些重要的的差别。用单纯形法求解下述目标规划问题：minzPddPd11223x1d1d1102xxdd1222403x2xdd1233100x,x,d,d0(i1,2,3)12ii

第一步：列出初始单纯形表，并计算检验数。

将表格中最终一行检验数按优先级改写为：(这是与线性规划单纯形法的第一个差别)

对两行检验数需分别进行处理。

其次步：确定换入基的变量。在负检验数中，选择最小的一个σj所对应的变量xj作为换入基的变量。在这个问题中第一优先级P1所的检验数中–1是最小的，因此x1为换入基的变量。这是与线性规