目标规划和线性规划

目标规划是为了解决多个目标问题而产生的一种数学规划方法，是由线性规划发展演变而来。目标规划和线性规划主要有以下区别：
线性规划是在一组线性约束条件下，寻求某一单一目标的最优值，只有一个目标函数，但在实际问题中往往要考虑多个目标。
目标规划模型中的目标函数可以有多个目标可以设置，多个目标之间可能是互相矛盾、相互排斥的，每个目标分别带有不同的优先级和权系数；
线性规划立足于满足所有约束条件的可行解，而目标规划是在条件下找到满意解,并不一定要满足所有约束，更能运用于实际生活中。

目标规划

目标规划包括线性目标规划，非线性目标规划，整数线性目标规划，整数非线性目标规划等，这里主要介绍线性目标规划，并将其简称为目标规划。

1 线性规划问题的建模及其局限性

线性规划的目标函数是单目标，但企业实际的经营管理中，需要完成多项指标，如企业计划中就包括产量、质量、利润、交货期等多项指标组成一个指标体系，均要全面完成，但是，这些指标的度量单位不同，各个指标的重要程度也不同，线性规划难以给出实际的答案，但是，在一定的约束条件下，多目标要求往往相互矛盾，造成无可行解域，提不出供决策参考的答案，从而失去实际决策价值。这些问题需用目标规划来加以解决。

例：某个工厂生产甲乙产品，单位生产所需材料、占用设备时间；现原材料拥有量、利润等信息如表1所示，问：该企业应如何去安排生产，才能使得利润最大？

解：设x1，x2分别为生产甲乙两种产品的数量，建立线性规划模型：

用Excel求解，见图1。得到最优解x1=4，x2=3，z*=6200

从线性规划的角度来看，该问题已有最优解，但是，这是理想化的模型，在实际生产过程中，企业往往会有更加复杂的问题，例如，现在，由于经营管理需要，又提出了四项要求：
（1）根据市场信息，产品A的销量有下降趋势，故A产品的产量不大于B产品。
（2）超过计划供应的原材料时，需用高价采购，故希望尽量不超过原材料的供应量。
（3）应尽可能充分利用设备，但不希望加班。
（4）应可能达到并超过计划利润指标。
现在企业该如何决策？线性规划的目标函数是单目标，所以这些问题我们通过线性规划无法解决，所以这时候我们就要运用目标规划模型进行该问题的求解。
上述问题是一个多目标问题，决策者的考虑用数学公式表示为：

x1-x2<=0 （1）
2x1+x2<=11 （2）
x1+2x2<=10 （3）
8x1+10x2<=56 （4）

现在我们就已经引入了目标规划模型。下面需要介绍与建立目标规划数学模型所相关的一些概念。
　
2 目标规划的基本概念

2.1 设置理想值
目标规划是用来解决多目标规划问题的，并且决策者事先对每个不同的目标都存在着一个期望值即理想值。

2.2 设置正，负偏差变量
偏差变量di：表示实际值与目标值之间的差距。
di+ 正偏差，表示超过目标值的偏差绝对值。di－负偏差，表示未达目标值的偏差绝对值。
（1）偏差变量之间的性质：
①当实际值确定只会大于目标值时，有：di+＞0，而di－＝0。
②当实际值确定只会小于目标值时，有：di－＞0，而di+＝0。
③实际值等于目标值时，有di+＝di－＝0
④任何一种情况下有：di+* di－=0
（2）硬约束与软约束
①硬约束：指必须严格满足的等式约束和不等式约束。这些约束是由客观条件限定的，一定要满足的，管理者无法控制，故不应考虑其偏差变量。
②软约束：实现起来可以有偏差（di）的管理目标约束。
例如：对于原目标函数，现在提出利润管理目标值56元，实现结果可能有正偏差di+，也可能有负偏差di－，于是构成软约束方程。
超利润目标时，超额利润为di+，达不到利润目标时，欠额利润为di－，恰好达到目标时，，di+＝di－＝0

2.2.3 统一处理目标与约束条件
目标规划追求的是管理目标优化，即要求目标量满足目标优化的需要，所以目标规划的目标函数应表示为所有目标约束方程中偏差量的函数，这是目标规划与单目标规划的最明显标志。

对于例中的第一个目标，x1≤x2目标约束一般写成：x1-x2+d1-d1+=0,因为实际的产量x1可能大于x2，也可能小于x2，所以d1－，d1+出现一个，但管理目标要求因不能满足x1≤x2，而出现的正偏差d1+越小越好（尽可能缩小偏差目标值），所以目标函数写为：min z1=P1d1+
第二个目标：尽可能充分利用设备，但又不希望加班，目标约束写成：x1+2x2+d2-d2+=10，这时的管理目标是都尽可能小，所以目标函数写为：min z2=P2（d2-+d2+）
对于第三个利润目标：8x1+10x2+d3-d3+=56，即允许超过目标，如果达不到目标值，希望负偏差越小越好，即：min z3=P3d3-

2.4 目标的优先级与权系数

在目标规划中，当需要实现多个目标时，根据各个目标之间也有主次、轻重、缓急等区别．决策者需要以第一位要求达到的目标，我们赋予它的优先因子为P1，只有在它实现的前提下才再去解决其他次要目标．之后依次把第二位达到的目标去赋予优先因子P2 ……，并做出如下规定Pk »Pk+1，即不管Pk+1乘以一个多大的正数M，总使Pk>MPk+1成立，这表示Pk比Pk+1具有绝对的优先权．这表明，不同的优先因子他们分别代表着各不相同的优先等级，且存在先后之分。

对于例子中的三个目标，如优先考虑x1≤x2，则对其目标函数赋予优先因子P1，在满足第一级目标的前提下，才考虑第二级目标：充分利用设备，最后才是利润目标。
对于几个具有相同优先等级的目标，也可赋予不同的权系数，表示其重要程度的不同。

2.5 目标规划中的目标函数——准则函数

通过引入偏差变量，我们使原规划问题中的目标函数变成了现在的目标约束，而目标规划的目标函数就可以由偏差变量所构成．它具有以下三种基本表现形式：
① 要求恰好达到目标值的，不多也不少，即正、负偏差变量都要尽可能小．构造目标函数为：min z= di++ di- ．
② 要求不能超过目标值的，即允许达不到目标值，但即使超过，一定要越小越好．构造目标函数为：min z= di+ ．
③ 要求超过目标值的，即允许超过目标值，但即使不足，一定要使缺少量越少越好．构造目标函数为：min z= di-
．
这样根据各个目标的不同要求，确定出总的目标函数

3 目标规划的一般模型

3.1 建模步骤

<1>列出全部的约束条件。
<2>将要达到指标的约束不等式进行修改，加上正，负偏差变量，将其化为目标约束等式。
<3>对目标赋予相应的优先因子。
<4>对同一级优先因子中存在的各偏差变量，根据题意，若重要程度等方面存在不同时，可赋予各偏差变量不同的加权系数。
<5>构造一个目标函数，按优先因子及加权系数和对应的目标偏差量所要实现最小化的原则

3.2 模型

对于上述的例子，其目标规划的数学模型如下：

上述第一个约束是硬约束，可以引入一个松驰变量 x3 , 从而将它们可化为标准型为：2x1+x2+x3=11
对于一般的的规划来说，设其有n个决策变量，有m个目标约束，有k个资源约束，和L个优先级的目标规划，其一般的目标规划模型为：

2.4 求解目标规划模型的方法

线性目标规划的解决可采用图解法、单纯形算法和序贯式算法等，本论文采用序贯式算法，并借用Excel软件求解。

4.1 图解法

图解法计算步骤：
第1步：根据决策变量（当然不能多于2个）绘画所有（软、硬）约束条件的直线图形，偏差变量以移动（平移）直线的方法加以考虑．
第2步：对P1级的各目标，确定解区域R1．
第3步：对下一个优先级别Pi 级各目标，确定它的最优解空间Ri ，但必须是Ri  Ri-1 ( i=2,3,…)．
第4步：在这个过程中，如果某解区域Ri 减小到一点，则可结束这个过程，因为此时没有进一步改进的可能．
第5步：重复第3、4步过程，直到解区域Ri 减少到一点或满 足了所有k个级别的目标为止，此时，Rk 即为这个目标规划的最优解区域，其中的任何一点均为目标规划的满意解．[6]
根据上面例子用图解法可以做出如下的图2
硬约束 ： 2x1+x2=11 （1）
目标约束：
x1-x2=0 （2）
x1+2x2=10 （3）
8x1+10x2=56 （4）

按优先级的次序，逐级让目标规划的目标函数中极小化偏差变量取0，这样可行域逐步缩小，最后发现例子的解为线段GD上所以的点（无穷多个解）。G点的坐标（2，4），D点的坐标（10/3，10/3）。

4.2 单纯形法

解目标规划问题单纯形法的计算步骤：
（1）建立初始单纯形表，在表中将检验数行按优先因子个数分别列成 K 行，置 k =1。
（2）检验该行中是否存在负数，且对应的前k 1行的系数是零。若有负数，取其 中最小者对应的变量为换入变量，转（3）；若无负数，则转（5）。
（3）按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时， 选取具有较高优先级别的变量为换出变量。
（4）按单纯形法进行基变换运算，建立新的计算表，返回（2）。
（5）当k =K 时，计算结束，表中的解即为满意解，否则置k = k +1，返回到（2）。
对于上述例子，用单纯形法进行计算，可以引入一个松驰变量 x3 , 从而将它们可化为标准型.

由上表我们知，x1*=2，x2*=4为原问题的满意解。
但是非基变量d3+的检验数为0，这说明原问题存在多重解。
将d3+为换入变量，以d1-为换出变量再迭代一步

所以，得x1*=10/3，x2*=10/3也为原问题的满意解。
综上所述，（2,4）和（10/3,10/3)这两点之间的线段上的所有点均为原问题的满意解。

3.3 序贯式算法

序贯式算法核心原理是根据优先级的先后次序，从而将原目标问题分解，使其成为一系列的、传统的单目标线性规划问题，最后再依次求解。决策者通常是需要根据自己对目标的重要程度去赋予每个目标一定的优先级，从而对所有目标进行排序（ P1 >> P2 >>>Pk ），序贯式算法就是按照目标的优先级逐个求解。
上述例子有三个目标优先级（ P1，P2，P3),所以要分三步完成： 第一步：首先保证 P1级目标的实现，这时不考虑其他级目标，

第二步：在保证 P1级目标的基础上考虑 P2级目标，并将第一级偏差设为0

第三步：在保证P1，P2级目标实现的基础上，再去考虑 P3级目标，并将第二季偏差设为0

所以，得x1*=10/3，x2*=10/3，d1-=2，计算方法与单纯性法求解结果相同。
本论文就运用了这种序贯式算法思想，在Excel软件中求得目标规划模型的满意解