线性规划与目标规划

1、5.1规划论基础规划论是运筹学中应用最为广泛的一个分支，本小节重点介绍在军事通信网分析和规 划中常用的两类模型一一线性规划和目标规划。5.1.1线性规划问题和模型线性规划问题主要有以下2种：一是如何有效利用现有的人力、物力完成更多的任务; 二是在预定的任务目标下，如何耗用最少的人力、物力去实现目标。这些规划问题的数学模 型都是由3个要素组成：一是变量，或称决策变量，是需要确定的未知量，用来表明规划 中的用数量表示的方案；二是目标函数，它是决策变量的线性函数，按优化目标在该函数前 加上max或min；三是约束条件，它是含决策变量的线性等式或不等式。下面，以一个具 体的例子来说明问题。例5.1某通

2、信连计划用两种通信设备A和B进行通信联络，建网方式有甲、乙两种， 有关数据见表5.1。问：两种方式的组网数各为多少时，能在规定的条件下，使得提供的话 路总数z达到最大？表5.1有关数据表单网所需 组网方式 设备数方式 设备甲乙设备数量A3124B2220单网能提供的话路数1815解：设x1，x2分别为甲、乙两种方式的组网数，则由已知条件，容易得到该问题的线 性规划模型为：目标函数：max z = 18x +15x123气 + x2 J 24约束条件： 012一般地，规定线性规划问题的标准形式如下：max z =乙 c xj=1 a x - b(i = 1,2, , m)s.t i j ij=1

3、a.x. = b , j =1 j jxj 0 (j = 1,2,., n)其中(Xj(j = 1,2,n)是决策变量,max z =c x为目标函数，j jj=1i = 1,2, ,m，x 0 (j = 1,2,n)为约束条件，s.t (subject to 的缩写)为约束于。.j.约束条件右端的常数项b全为非负。对于非标准形式的线性规划问题可以通过引入松弛 i变量等转化为标准形式。所谓松弛变量，是指在化为标准形式时，使约束不等式变为等式时 所加入的变量。对不符合标准形式(或称非标准形式)的线性规划问题，可分别通过下列方 法化为标准形式。目标函数为求极小值，即为：m i n =乙 c xj=

4、1因为求min z等价于求max(-z)，令z = -z，即化为max z = -8 c xjj j=1约束条件的右端项b 0时，只需将等式或不等式两端同乘一1,则等式右端项必 大于零。约束条件为不等式。当约束条件为“ ”时，如5气+ x2 0 ；当约束条件为“ ”时，如31212334x + 3x 25，可令 x = 4x + 3x - 25，得 4x + 3x -x = 25 ，显然 x 0 ；式中的变量x3, x4 0，即为引入的松弛变量，引进模型后它们在目标函数中的系数均为零。取值无约束的变量。如果变量x代表某产品当年计划数之差，显然x的取值可能是正也可能是负，这时可令x = x-x，

5、其中x 0, x 0，将其代入线性规划模型即可。对x 0。满足约束条件的解X = (x ,x , ,x )称为问题的可行解，可行解的全体称为可行域；12 . . . n使目标函数达到最大值的可行解称为最优解。可行域是一个凸多边形，最优解若存在一定在其某个顶点上取得。所谓凸集C，是指对任何X1，X渣C，有a% + (l-a)X2M (。a 1)。顶点 X 仁 C):不存在 , X? M ,使得X =a % + （1-。） X 2 e C （0 a 1）。所谓凸多边形，就是把一个多边形任意一边向两方无限延长成为一条直线，如果多边形 的其它各边均在此直线的同旁，那么这个多边形就叫做凸多边形。如图5.

6、1,多边形ABCDEF，把线段AF向两方无限延长，此多边形的其它各边AB、BC、CD、DE、EF均 在此直线的同旁，所以多边形ABCDEF是凸多边形。图5.1凸多边形值得注意的是，在凸多边形的定义中，延长的这一边是凸多边形的任意一边。图5.2中 的多边形ABCDEF，若分别把AB、BC、CD、DE各边延长为直线，这时均满足凸多边形 的定义，但这时并不能说多边形是凸多边形。因为，延长线段AF为直线后，多边形其它各 边并不在此直线的同旁。同样，把线段FE延长为直线后，又有类似的情况出现。B DC图5.2凹多边形在二维情况下可用图解法或计算顶点的枚举法求解，但在决策变量较多时，图解法失 效，枚举法计

7、算量较大，通常用基于线性方程组变换的单纯形法进行求解。图解法（又称几何法）图解法是对于只是两个决策变量的线性规划问题，在平面内建立直角坐标系，使每个 决策变量的取值在一个数轴上表示出来，可行解就成为平面上的点，可行域就是平面上的 一个共域，从而最优解必定是在这个平面区域内（包括边界上）的点。根据目标函数在这 个平面区域内的取值找出使目标函数取得最优值的点（即最优解）。图解法便于我们理解和了解线性规划问题的一些概念、理论及解的一些特性，也为我 们进一步学习单纯方法提供一个直观图形。1例5.2求解线性问题7 x +5x =106min S = 7 x + 5 x12+ 2 x2 = 287气 +

8、5x2 = 50 x + 2x 28S .t Mx + x 0虹12图5.3线性规划图解法解：第一步，在平面直角坐标系Oxix2上绘出约束条件图，如图5.3所示。画出这条直线气+ 2x2= 28，再定出气+ 2x2 28区域。把（0, 0 ）代入不等式得0 + 20 V28,所以，原点所在半平面及直线本身就是 气+ 2x2 28代表的区域。画出4气+ x2= 42这条直线，定出4气+ x2 42代表的区域，有（0，0）代入不等式得04+0V42所以，4气+ x2 0, x2 0的区域，它就是第一象限。从图5.3看出，满足全部约束条件的 点所构成的区域（即可行域），就是凸多边形OABC。第二步，

9、绘制目标函数图形。对于目标函数S = 7气+ 5x2将S看作参数，即得到一簇 平行直线（图5.3中虚线所示），直线上每一点的目标函数值为S。由图可见，直线离原点 越远，S值越大，我们寻找的是在可行域内使S值最大点。可见，B点即为可行域内使目 标函数最大的点，即为最优解。第三步，确定最优解。B点是直线气+2x2= 28与4x+x2=42交点，所以解方程组J x + 2 x = 284 x + x = 42得到x广8, x2 = 10这就是最优解。将其代入目标函数，得最优解maxS = 7x8 + 5 x 10=106例中有可行解且有唯一最优解将目标函数改为S =气+ 2x2或S = 4气+ x2

10、仍求其最大 值，则BC或AB上每一点的坐标均为最优解，最优解有无穷多个，而它们对应的目标函数 数值是28或42。单纯形法线性规划问题的标准形式用矩阵可表示为:max z = ctx（LP） 0, x e Rn其中，c为n维列向量，A为mxn矩阵，b为m维列向量。设m 01212单纯形表0 （原始表）X1X2y1y2z右端项3110024 ( y)12201020 ( y2)18)-150010 ( z)相关变量：3， y， z；独立变量：X X 0 ；顶点：（X ,X ）=（。,。）；目标函数121212值：z 0最优化检验进入变量是X （对应于最后一行的系数）1可行性检验用右端项除以X1所在

11、列的系数，计算相应的比值，并确定正的最小比值。X1X2y1y2z右端项比值31100248(=24/3)220102010(=20/2)-18-150010*退出变量正的最小比值为8,选择对应的变量y1为退出变量。旋转将退出变量所在的行（这里是第1彳亍）除以该行中进入变量的系数（这里是X1的系数）， 使得进入变量在本行中的系数变为1,用消元法消去其它行的进入变量X1，这些行中不含 有退出变量（对应的系数为0）。结果表示见单纯形表1。单纯形表1相关变量：x， y， z；独立变量：X = y = 0；顶点：（x ,X ） = （8，0）；目标函数122112xxJJz右端项121211/31/30

12、08 （=气）04/3-2/3104 (= y2)0601144(= z)值：z = 144最优化检验进入变量是x （对应于最后一行的系数-9）2最小正比值为3,可行性检验xxyiy2z右端项比值11/31/30082404/3-2/310430-96010*用右端项除以X2所在列的系数，计算相应的比值，并确定正的最小比值。进入变量选择对应的J为退出变量。退出变量旋转类似于前面，得到结果见下表:单纯形表2x1x2y12z右端项101/2-1/40701-1/23/403003/227/41171由单纯形法计算结果可以知道，甲、乙两种方式组网数分别为7和3时，能在规定的 条件下，使得提供的话路总

13、数z达到最大，其值为171。5.1.2目标规划前面所述的线性规划问题在实际中有很多局限性，如：目标单一，局限于某个方案的 最优性；各约束条件必须相容；线性规划解的可行性和最优性是针对特定的数学模型的， 而这种数学模型只是对实际问题的某种近似，在设计和规划过程中，还需考虑新的情况。 由于目标规划能在一定程度上弥补线性规划的上述局限性，因而被认为是较为接近于实际 决策过程的决策工具。目标规划问题的建模目标规划解决的是多目标决策问题。这些目标很多时候是互不相容且有轻重缓急之分 的，如在军事通信网的组建中，通常要考虑这样一些决策目标：通信网的可靠性、抗毁性、 安全保密性、抗干扰性、机动性、组网投入少等

14、，这些决策目标有的冲突，有的相容，且 针对不同的作战方式，所要考虑的目标达成的优先顺序和侧重点是不同的。目标规划就是 在处理这类决策问题时，承认各项决策目标的合理性，而不强调其绝对意义的最优性，按 优先等级兼顾各个目标，尽量满足某些约束条件。下面以一个具体的目标规划问题为例来 说明目标规划问题的模型建立和求解。例5.4对例5.3的单目标规划问题，再提出以下目标要求：甲方式的组网数尽可能 不超过乙方式的组网数；设备B尽量用完；总话路数不低于156；设备A的总量绝 对不允许突破。问：如何确定甲、乙两种方式的组网数量，才能满足以上要求？要建立该目标规划问题的数学模型，还需要引入与建模有关的一些概念。

15、与线性规划 模型不同，目标规划模型的每个约束关系式对应一个决策目标，对每一个决策目标，引入正、负偏差变量d +和d-，分别表示决策值超过或不足目标值的部分。使约束条件严格满 足的约束称为硬约束，硬约束无偏差变量；使约束条件尽量满足的约束称为软约束，其决 策值和目标值之间的差异用偏差变量表示。不同目标的主次轻重的描述可以用优先因子和 权系数来表示。将软约束对应的目标分为若干优先等级，用优先因子马(/ =1,2, .，k)来表示。优先因子之间的关系为pP ，表示P对应的目标比P对应的目标有绝对的优先ll+1ll+1性，若不同的目标有相同的优先因子，则可以用权系数的不同来表示其重要程度的差异。 目标

16、规划的目标函数由各目标约束的偏差变量、相应的优先因子的权系数构成因目标函数 追求的是尽可能地接近目标值，故其目标函数是使得各约束关系式的偏差变量之和构成的 偏差变量和函数最小化。应用中，有3种基本形式。要求恰好达到目标值：minf(d + d-)；要求不超过目标值：minf(d+)；要求不低于目标值：minf(d-)。设P，P，P分别是的优先因子，d+，d-(i = 1,2,3)是相应的正、负偏差变量，z为123i i偏差总和，则例5.3的目标规划问题数学模型可建立为：min z = p d+，p (d - + d+)，p d -)1 12223 33 尤+ x 24 TOC o 1-5 h

17、z HYPERLINK l bookmark110 o Current Document x - x + d - - d + = 0 1211 0, d-, d + 0, i = 1,2,31211目标规划数学模型的一般形式为 HYPERLINK l bookmark122 o Current Document minp (f (W-d-+ W+d+),l = 1,2, ,L) lIk k Ik k k=1 HYPERLINK l bookmark125 o Current Document f c x + d- - d + = g k = 1,2, , K kj j k k kj=1st a

18、 x ) = b i = 1,2, , mij jij=1x. 0 j = 1,2,.,n HYPERLINK l bookmark134 o Current Document d-, d + 0 k = 1,2, , K k k.其中，g为第k个目标约束的预期目标值，W-和W +为p优先因子对应各目标的权 klk lk l系数。目标规划问题的求解目标规划的图解法对于只有两个决策变量的目标规划问题，可以用图解法来求解。例5.5用图解法解例5.4的目标规划模型。解：解题过程见图5.4。图5.4中，AOAB区域是硬约束的解空间，去掉偏差变量，画出所有软约束的边界直 线，然后标出偏差变量变化时直线的平移方向。按优先级高低，首先考虑P，得解