第3章-数学规划基础

1、第3章数学规划根底所谓数学规划，是指系统在一定约束条件下使某一评价目标到达最优极值的一种决策方法。数学规划的关键是从系统思想出发，在定性分析的根底上建立其数学模型。数学规划模型的一般形式为：系统在满足条件G"j) b1Dj Xj Dj的情况下，使评价目标到达最优最大或最小值，即maXmin)Z f (X j) 2其中，式1是系统必须满足的限制条件的数学描述，通常由等式或不等式组成，称为约 束条件，简记为s.t.subject to,意为“受的限制；式2是系统评价目标的数学描述， 称为目标函数。一、线性规划所谓线性规划，是指约束条件和目标函数均为线性的数学规划方法。根据系统评价目标是单

2、个还是多个，可将线性规划分为单目标线性规划和多目标线性规划。一单目标线性规划1. 问题的提出例1生产管理问题某工厂方案期内要安排生产i、n两种产品，生产单位产品所需的设备台时及 A、B两种原材料的消耗， 如表所示。该工厂每生产一件产品I可获利 2元，每生产一件产品n可获利3元，问如何安排生产方案才能使工厂获利最多？产品I产品n限制设备台时/件128台时原材料A kg /件4016kg原材料B kg /件0412kg利润元/件23解 上述所谓的“安排生产方案问题，其实质就是要寻求一个满足设备和原材料资 源约束的可行的生产方案，以确保工厂能获得最大的利润值。假设产品I、n的产量分别为X1、X2,那

3、么该工厂的获利值f = 2 X1 + 3 X2。由于可行的生产方案需要考虑不能超出设备的有效台时数限制，即X1+2 X2W 8;同时,还要考虑满足A、B原材料资源的约束条件，即 4X1W 16, 4X2< 12。因此，工厂的目标是在 满足设备和原材料资源限制的条件下， 如何确定两种产品的产量 Xj、X2,使工厂的获利最大。综上所述，上述安排生产方案问题的数学模型为目标 max f2x1 3x2满足约束条件s.t.X12x2 8设备约束4x116原材料A约束4x212原材料B约束X1 ,x20由此可见，将这类实际问题转换为数学模型的根本步骤可归纳如下：1确定决策变量；2确定所要追求的目标目

4、的；3确定约束条件；例2环保问题靠近某河流有两个化工厂，流经工厂1的河水流量是5 X 106m3/天，在两个工厂之间有一条流量为2X 106m3/天的支流，如下列图。工厂 1每天排放工业污水 2 X104m3x 104m3。从工厂1排出的污水流到工厂 2之前，有20%可自然净化。根据环保要求， 河流中工业污水的含量不应超过0.2%。假设这两个工厂都各自处理一局部污水，工厂1处理污水的本钱是1000元/104m3,工厂2处理污水的本钱是 800元/104m3,试问在满足环保要 求的条件下，各工厂应分别处理多少污水，才能使两个工厂处理污水的总费用最小？C解假设工厂1和工厂2每天处理污水量分别为X1

5、104m3、X2104m3,那么两个工厂处理污水的总费用f = 1000x1 + 800 X2。根据环保要求，从工厂1到工厂2之间的河流中污水含量不超过0.2%，那么可得2 X10.2500100x11由于从工厂1排出的污水流到工厂 2之前有20%会自然净化，且流经工厂 2后河流中污水含量仍要不超过0.2%，故有(1 0.2)(2 X1)(1.4 X2)0.20.8x1X21.6500 200100此外，各工厂每天的污水处理量不应超过其污水排放量，那么有X1< 2, X2< 1.4。因此，问题的目标是要求两个工厂处理污水的总费用最小。综上所述，上述环保问题的数学模型为目标min f

6、 1000 x1800x2满足约束条件s.t.x110.8为 x21.6x12x21.4x1, x202. 数学模型的建立应用单目标线性规划来解决实际的最优化问题时，必须符合以下特征参见P34:(1) 所求问题都有一个目标要求，且相应的目标函数可以用最大或最小值的形式来表达；(2) 要到达最优目标，必须有多种方案可供选择；注意：每一组决策变量X1, X2,Xn的取值就是一个具体方案。(3) 所寻求的目标必然有条件约束；(4) 目标函数和约束条件都是线性方程式，且决策变量具有非负性。因此，单目标线性规划问题的数学模型可归纳如下：n目标函数 max(min) fcjxjj i满足约束条件s.t.n

7、ajXj( , )bii 1,2, ,mj iXj 0j 1, 2,n其中，aij, bi, cj为常数。3. 数学模型的标准化将单目标线性规划的数学模型规定为以下标准形式：(1) 目标函数是求最大值当目标函数是求最小值时，即nmin fCjXjj 1由于nmin fmax( f)cjxjj 1令f'=f,可得nmax fmin fcjxjj 1(2) 约束条件均用线性等式方程来表示，且右边常数项均为非负值当表达式中含“w时，可在约束条件左边加上一个非负的变量一一松弛变量，使原 来的“w变为“=；当表达式中含时，可在约束条件左边减去一个非负的变量一 剩余变量，使原来的变为“ =。另外，

8、在标准型中要求约束条件右边的常数项bi > 0,假设存在bi<0的情形，那么可在方程式两边各乘以 1,使所有bi > 0得到满足。(3) 所有变量要求非负当Xi w 0时，那么可令Xi' = Xi且Xi'?0；当Xi为无约束的自由变量时，那么可令 Xi' Xi" = Xi 且 xi'、xi" > 0。综上所述，可得 单目标线性规划模型的标准形式：目标函数 max fc jx jj1满足约束条件 s.t.naij Xj bij1i 1, 2,mXj 0j 1, 2,n例 3 将例 1 生产管理问题的数学模型化为标准形式。

9、 max f 2x1 3x2x1 2x2 84x1 16s.t. 14x2 12x1 ，x2 0解 例1的目标函数是求最大值，各不等式均为“W形式的不等式，故需要在各不等式的左边加上非负的松弛变量 X3, X4, X5,使不等式化为等式。由于所加变量X3, X4, X5表示未被利用的资源，那么也就没有被转化为价值，所以在目标函数中X3, X4, X5的系数应为零。因此，其标准形式为maX f 2X13X2 0X30X40X5X12X2 X384X1X416s.t.4X2X5 12X1，X2，X3，X4，X50例 4思考题 将例 2环保问题的数学模型化为标准形式。例5将以下数学模型化为标准型。m

10、in fX1X24X33X24X39X1X26s.t.5X22X316X10，X20，x3为自由变量解令 Xi = xi'且 xi'?0X3 = X3'X3"且 X3'、X3" > 0将第一个约束条件两端乘以1 并参加松弛变量X4,第二个约束条件减去剩余变量X5,第三个约束条件加上松弛变量X6，同时将目标函数变为求最大值，整理可得maX fmin fX1 X24X34X33X24X34X3X49X1 X2X56s.t.5X22X32X3X6 16X1 ，X2，X3，X3，X4，X5，X604. 图解法对于一般单目标线性规划问题满足 式的

11、点称为该问题的解；而同时又满足(3)式的点那么称为 可行解。所有可行解组成的集合称为可行域或可行解集。可行域上满足(1) 式的点称为最优解，最优解对应的目标函数nmax(min) fcjxjj 1(1)naijxj(,)bis.t.j 1i 1,2,m(2)xj 0j 1,2,n(3)值称为最优值。当单目标线性规划问题中只有两个决策变量.即二维线性规划.时，可纠囲图解法来求 解，以便直观地理解该问题解的几何意义。例6用图解法求例1生产管理问题的解。max f 2x1 3x2X12x284x116s.t.4X212X1 ,X20解 1由约束条件画出可行域因为x1, X2 > 0,可行域在第

12、一象限。 第一个约束条件 Xl+2X2< 8表示以直线Xl+2X2= 8为 边界的右下方平面；第二个约束条件4冷 16表示以X1= 4为边界的左半平面；第三个约束条件4X2W 12表示以X2= 3为边界的下半平面，因此， OABCD所围成的凸多边形即为可行f/打2考虑目标函数的等值线和梯度方向对目标函数f= 2x1 +3x2,令c为参数，那么2xi +3x2 = c表示目标函数的取值为 c的一簇平 行线，如图中的虚线所示，且位于同一直线上的点具有相同的目标函数值，故称其为“等值线。当c值由小变大时，直线 2xi +3x2 = c沿着其梯度方向，向右上方平行移动。3求问题的最优解当目标函数

13、沿其梯度方向平移至B点时，切点B即为最优解。那么求出 B点的坐标4为 16Xf 2x28得最优解 xi = 4，X2 = 2 ；相应的最优值 fmax = 2xi +3x2 = 8+6 =14。讨论：。假设例1是求最小值，那么在 0点处到达最优解 xi*= X2*= 0，且相应的最优值 fmin = 0 ； 假设例1中的目标函数变为 f = 2xi +4x2，那么等值线2xi +4x2 = c与约束条件xi+2x2W 8的边界线相平行。当 c值由小变大并与线段 CB重合时，目标函数值到达最大，那么表示线段CB上的任意一点都是最优解，即该问题有无穷多个最优解； 假设在例1的数学模型中再加一个约束

14、条件2X1+X2 > 4,那么可行域是空集，此时无可行解，当然也就无最优解。通过上述的图解法可见，单目标线性规划问题中，所有可行解构成的可行域一般是凸多边形或是无界的，其最优解具有以下重要特点：假设问题存在最优解，那么一定在可行域的某个顶点上得到； 假设两个顶点上同时得到最优解，那么这两个顶点连线上的任何一点都是最优解； 假设可行解无界，那么可能发生无最优解的情况； 假设无可行域，那么问题既无可行解也无最优解。5. 单纯形法单纯形法是由美国数学家 G B. Dantzing于1947年首先提出的。它是借助于电脑，用于 求解多变量.多维.线性规划的有效方法。(1)根本概念及其相关定理对于线

15、性规划问题的标准型nmax f Cj Xjj inaijXj bii 1,2, , ms.t.j iXj 0j 1, 2,n用矩阵形式表示，那么可以写成max f CXAX bs.t.X 0式中cC1C2CnTXX1X2Xna11a12a1 nAa21a22a2nam1am2amnbthb2bm其中，C是由价值系数Cj构成的价值向量，X是由决策变量xj构成的决策向量，A是由技术 系数 如构成的mx n阶约束系数矩阵，b是由资源系数bi构成的资源向量。假设矩阵A的秩为m，B是A阵中mx m阶非奇异矩阵| B |工0，那么称B是线性规划问题的一个基。也就是说，矩阵B是由m个线性独立的列向量Pj组成

16、，即a11a12a1ma21a22a2mBR P2Pmam1am2amm那么称Pjj = 1,2,，m为基向量，与基向量Pj相对应的非零变量 xjj = 1,2,，m为基根底变量；其余的零变量 xjj = m+1, m+2,n为非基根底变量与基B对应的线性规划问题的解x-ix2XiX2xmxm 1Xm0TXnT0那么称为线性规划问题的 基解。由于满足非负约束条件 X>0的解为线性规划问题的可行解,那么满足非负条件的基解就称为基可行解，而对应于基可行解的基就称为可行基。定理1：线性规划的可行解 X = Xi x2XnT为基可行解的充要条件是 X的正分量所 对应的系数列向量是线性独立的。因此

17、，为了简单起见，通常在单纯形法中要求根底变量对应的矩阵为单位矩阵假设在线性规划问题的标准型中，与基 B对应的基变量Xb = X1X2XmT，非基变量 Xn = Xm+1 Xm+2 XnT，且相应的矩阵C = C B Cn，其中Cb = C1C2Cm, Cn = Cm+1Cm+2Cn，那么可以证明以下判别线性规划问题最优解的依据参见P40。定理2最优解判别定理：在标准形式的线性规划问题中，对于基 B,假设B 1b> 0, 且C CbB 1A W 0即检验系数矩阵c = C CbB 1A那么对应于基B的基解就是最优解， 基B 就是最优基。尤其是，当最优解判别定理中基矩阵B = Imx m阶单

18、位阵时，那么对应的基可行解为Xb = b且Xn = 0，其最优解的判别式变为C CbAW 0。不失一般性，设 Xb = X1 X2XmT , Cb = C1 C2Cm，系数矩阵A为100a1, m 1a1n01a2, m 2a2nA0001am, m 1amn对于基变量Xj j = 1,2,m来说，其检验系数b j为零；对于非基变量 Xj j = m+1, , nm来说，其检验系数j CjCiaj j = m+1,n当w 0时，那么目前的根本可行解i1为最优解。否那么，假设存在某个检验系数bj >0,那么目前的根本可行解不是最优解。特别要指出的是，假设存在某个b m+k = 0 ,而其它

19、任何b j<0j = m+1,n且j工m+k, 那么线性规划问题有无穷多个最优解； 假设存在某个b m+k >0，且A的列向量Pm+k中的所有元 素均不大于 0,那么线性规划问题无最优解。2根本思路单纯形法的基本思路是 ：根据线性规划问题的标准型,从可行域中的一个顶点基可 行解开始,转换到另一个顶点基可行解 ,并且使目标函数的值逐步增大。当目标函数 到达最大值时,就得到了问题的最优解。以例 1 的生产管理问题为例,说明单纯形法逐步迭代寻优的原理和思路。该问题的数学标准型为maX f2X13X20X30X40X5X12X2X384X1X416s.t.4X2X512X1 ,X2,X3,

20、X4,X501第一轮：约束方程系数矩阵12100A40010P1 P2P3P4P504001显然100P30P41P50001是线性独立的,这些列向量构成一个初始可行基 B100 B P3 P4 P50 1 0001X1和X2为非基变量。对应于初始可行基 B , X3、X4和X5为初始基变量,由方程组 1 可得x3 8 x1 2x2 x4 16 4x1 x5 12 4x22令非基变量 x1、x2 为零，得到初始的基可行解为X (0) x1 x2 x3 x4 x5 T 0 0 8 16 12 T将方程组 2代入目标函数，得f 2x1 3x23 将初始的根本可行解代入式 3，得 f (0) =0。

21、这个根本可行解表示：工厂没有安排生产产品i、n；设备的有效台时和原材料a、B没有被利用，所以工厂的利润指标 f (0) =0。从式3目标函数可以看到，Xi、X2即没有安排生产的产品i,n的系数都是正 数，显然将非基变量换成基变量，目标函数的值就可能增大。 从经济意义上讲，安排生产产 品I或n就可以使工厂的利润指标增加，所以只要式3目标函数中还存在有正系数的非基变量，那么目标函数值利润还有增加的可能，就需要将非基变量与基变量进行对换。一般选择正系数最大的那个非基变量X2为换入变量即引入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量。 可按以下方法来确定 换出变量即退

22、出变量。现在分析方程组2，当将X2定为换入变量后，必须要从X3、X4和X5中换出一个，并要保证其余的都是非负，即X3, X4, X5> 0。当 X1=0 时，由方程组 2可得X3 8 2X20X4 16 0X5 12 4X2 0 4 从方程组 4可见，只有选择 X2 = min8/2 ， - ， 12/4=3 时，才能使式 4成立。当 X2=3 时，X5=0，这就决定了 X5为换出变量，用X2去替换X5。以上数学描述说明：每生产一件产品n,需要用掉设备台时及原材料为2, 0, 4。这些资源能力中的薄弱环节就确定了产品n的产量，也就是由原料B的生产能力，确定了产品n的产量 X2=12/4=

23、3件。第二轮：X2与X5互换，即X2为基变量，X5为非基变量。那么互换后，X3、X4和X2为基变量，X1和X5为非基变量。为了求得新的基可行解，并将目标函数f用非基变量XI、X5表示，以判别所求的基可行解是否为最优解，那么需要用高斯消元法，将方程组2中第一个方程的X2消去，将第三个方程的X2移至左边，并将系数化为1,于是有X3X416X21X1X524x11X545令非基变量XI、X5为零，得基可行解为XiX2X3X4TX50 3 2 16 0T将方程组5代入目标函数中，得2X1 3x514 59。6 将X1=0，X5=0代入方程组6，可得目前基可行解的目标值为由式6可知，非基变量 X1的系数

24、大于0，那么目前的基可行解不是最优解， X1应为换 入变量。在方程组5中，用各方程负的 Xi的系数如果xi在方程的左边，那么用正的 xi 系数去除对应的常数项，选最小者，即X1 = min 2/1，16/4，=2于是，方程组5中的第一个方程对应的原基变量X3为换出变量。第三轮：X1与X3互换，那么互换后，X1、X4和X2为基变量，X3和X5为非基变量。将方程组5进 行初等变换，使得由基变量X1、X4和X2所构成的基为单位矩阵，即X12X32X5X484X32x5X231 X547令非基变量X3、X5为零，得基可行解X(2)x1X2X3X4TX52 3 0 8 0T将方程组7代入目标函数中,13

25、2X31J5X5的系数大于0，那么目前的基可行解不是最优解，X5为换入8 由式8可知，非基变量变量，因为 min ，8/2，3/(1/4)=4，故取&为换出变量。 第四轮：X5与X4互换，那么互换后，X1、X5和X2为基变量，X3和X4为非基变量。用高斯消元法对 方程组7进行初等变换，使得每个约束方程中只含有一个基变量且基变量的系数为1，即XiX54x222x312X418X49令非基变量X3、X4为零，得基可行解为T 为 X2 X3 X4 X5将方程组9代入目标函数中，得18X410由式10可见，X3与X4的系数均为负数，说明假设想使用剩余的设备台时和原材料A，就必须支付附加费用。所

26、以当X3 = X4 =0时，即不再利用这些设备能力和原材料时，目标函数到达最大fmax=14，于是基可行解X(3)TX1X2X3X4X5为最优解。3单纯形表max f对于标准化的线性规划模型CnXnX1a1, m 1Xm 1X2a2, m 1Xm 1S.t.Xmam, m 1 Xm 1X1, X2 , Xn0a1 n Xnb1a2nXnb2ammXnbm式中，X1, X2,，Xm为基变量，且对应的基为 B = Imx m阶单位阵。所设计的初始单 纯形表如表1所示。表1初始单纯形表CC1CmCm+1Cn9 iCbXbbX1XmXm+1XnC1X1b110a1, m+1a1ne 1C2X2b200

27、a2, m+1a2n9 2CmXmbm01am, m+1amne mmGbi 100mCm 1Ciai, m 1i 1mCnCi ai ni 1(T j表中，Xb列中填入基变量，这里是 X1, X2,，Xm；Cb列中填入基变量的价值系数，这里是C1, C2,，Cm,它们随基变量改变而改变,并与基变量相对应；b列中填入约束方程组右端的常数；X行填入决策变量名；在X行上面的C行，相应填入各决策变量的价值系数；最后一行是检验数行，对应各非基变量Xj的检验数是mj CjCiaij (j m 1,n)i 1e i列的数字是在确定换入变量后，按e规那么计算后填入表中的。单纯形表要求初始可行基 B=I，这时

28、可以从表上直接得到基可行解，即XiX2XmXm 1TXnbib2bm 0m且该基可行解的目标值为cb。i 1单纯形法就是以上述形式的初始单纯形表为起点进行迭代，每迭代一次后，得到使新 的基B'=I的另一个单纯形表；从表上得到新的基可行解和目标值，并进行最优判别，直到 找到最优解为止。(4) 单纯形法小结下面将单纯形法的计算步骤归纳如下：第一步，建立线性规划的数学模型，并使其标准化。标准化的要求为： 。目标函数化成求最大值问题；囤 约束条件均表达为等式关系必要时引入松弛变量和剩余变量；模型存在一个初始可行基一一单位矩阵必要时引入人工变量。第二步，建立初始单纯形表，如表1所示。第三步，检验

29、各非基变量Xj的检验数mj CjCi ai ji 1假设所有b jW 0j = m+1，n，那么已得到最优解，可停止计算，否那么转入下一步。第四步，在b j >0, j = m+1，n中，假设有某个b k >0对应的Xk的系数列向量Pk W 0, 那么此问题无最优解，停止计算，否那么转入下一步。第五步，根据max b j >0= b k，在单纯形表中b k所在的列为主元列即关键列，主元列 所对应的变量Xk为换入变量入基变量。再根据e规那么计算，有e i = bi /aikaik >0, i =1 , 2,，m，e l = min( e i) = bi /aik,确定e

30、i所在的行为 主元行即关键行，主元行在单纯 形表中所对应的基变量 Xi为换出变量出基变量。主元行与主元列相交的元素 aik为主元素即关键元素，用方括号标明，转入下一步。aik第六步，以aik为主元素，用高斯消元法进行约束方程组的初等变换，将主元列中主元素P kalk a2kalkTa mk将Xb列中的XI转换为Xk, Cb列中的ci换成ck，得到新的单纯形表。重复第三步 第六步, 直到算法终止。例6用单纯形法计算例1生产管理问题的最优解。解 第一步，将模型标准化后，即为max f 2x13x2OX30x40X5X12X2X384x1X416s.t.4X2X512X1 ,X2,X3, X4,X5

31、0模型中已存在一个初始可行基，对应的基变量为X3、X4和X5,那么令非基变量X1、X2为零，可得初始基可行解为X(0)X1X2X3X4TX500 816 12T且相应的目标函数值 f°=0。第二步，将有关内容填入表中，得到如表2所示的初始单纯形表。表2初始单纯形表230009 iCbXbbX1X2X3X4X50X381210040X41640010一0X512040013b j23000第三步，计算各非基变量的检验数，bi =2，2 =3，故存在b j >0,目前的解不是最优解，转入下一步。第四步，Pi, P2均有正分量存在，转入下一步。第五步，经比拟 max b j >

32、0= b 2,确定X2为换入变量，X2所在列为主元列；计算 9 i =8/2=4 , 9 3=12/4=3，取最小值者为9 3,于是9 3所在的行为主元行，主元行所对应的基变 量X5为换出变量，主元行与主元列相交的元素4为主元素。第六步，以4为主元素，用高斯消元法进行初等行变换，使对应主元列的列向量P2变换为0 0 1T，在Xb列中将X5替换为X2，于是得到表3。表3 X5替换为X2后的单纯形表Ci230009 iCbXbbX1X2X3X4X50X3210101/220X4164001043X2301001/4一20003/4这样，得到新的根本可行解TXiX2X3X4X50 3 2 16且相应

33、的目标函数值 f (1) =9。第七步，重复第三步第六步的计算步骤，由于表 3中检验数b 1 =2>0，那么目前的解不 是最优解。同理可以确定 X1为换入变量，X3为换出变量，于是得到表4。X(2)TX1 X2X3X4X5表4 X3替换为X1后的单纯形表Cj23000e iCbXbbX1X2X3X4X52X1210101/2一0X480041243X2301001/412b j00-201/4那么其新的根本可行解且相应的目标函数值f=13。第八步，再次重复第三步第六步的计算步骤，由于表4中检验数b 5 =1/4>0 ,那么目前的 解还不是最优解。同理可以确定X5为换入变量，X4为换

34、出变量，于是得到表5。表5 X4替换为X5后的单纯形表最优单纯形表Cj23000e iCbXbbX1X2X3X4X52X141001/40一0X540021/21一3X22011/21/80一b j003/21/80第九步，表5最后一行的所有检验数b j都已为负或零，这表示目标函数值已不可能再增大，于是得到最优解X X(3)x1x2x3X4x4 2 0 0 4且相应的最优值即工厂的最大获利f*= f=14。6.对偶问题在线性规划问题中，任何一个求最大值的规划问题必有一个求最小值的规划问题与之 相对应，二者含有相同的数据，且它们的解也有密切联系，反之亦然。假设两个问题中，其 中一个称为原问题，那

35、么另一个就称为对偶问题。(1) 对偶问题的关系以下两个线性规划问题i、n是互为对偶的，其中max f 2x1 5x2 7x3问题1：2x1 3x2 3x312s.t. x1 2x2 x313X1,X2,X3min f 12y1 13y22y1 y2 2问题n：3y1 2y2 5 s.t.3y1 y2 7y1,y2 0不难发现， 互为对偶的两个问题之间具有以下关系 ：。一个问题目标函数的系数是另一个问题约束条件右端的常数；囤一个问题第i个约束条件的各系数是另一个问题第i个变量的约束条件系数；一个问题是求目标函数的最大值，其约束条件均为“w形式，而另一个问题那么是求目标函数的最小值，其约束条件均为

36、形式；® 两个问题的变量均是非负的。2对偶问题的转化一个线性规划问题，在实际应用中通常可以根据具体情况将原问题转化为对偶问题，其具体方法如下 ：如果目标函数是求最大值，首先应将约束条件全部转化为“w形式，即。原约束条件为形式时，那么可在该不等式两边同乘以1，使其变为“w形式； 原约束条件为等式时，那么可将该式再将形式转化为“w形式；原问题中有自由变量时，那么可用两个非负变量相减来代替， 如Xi为自由变量，令Xi = Xi' Xi"且 Xi'、Xi"> 0。然后，再根据对偶问题的关系进行转化。同理，如果目标函数是求最小值，那么应先将约束条件全部

37、转化为形式，然后再 转化为相应的对偶问题。例 7 试写出以下线性规划问题的对偶问题min f 5X1 8X2 20X3X1 6X2 12X3 1X1 7X2 9X3 2s.t.X1 3X2 9X333X1 5X2 9X3 4X!为自由变量，x2 , x30解 令X1 = X1' X1"且X1'、X1" > 0,并将第四个约束条件转化为两个不等式，那么原问题可改写为min f 5x1 5x1 8x2 20x3x1 x1 6x2 12x3 1x1 x1 7x2 9x3 2s.t.x1x13x29x333x13x15x29x343x13x15x29x34x1

38、,x1, x2, x303x13x15x2 9x3由原问题与对偶问题的关系可得，相应的对偶问题为max f y1 2y2 3y3 4y4 4y5y1 y2 y3 3y4 3y5 5y1 y2 y3 3y4 3y55s.t. 6y1 7y2 3y3 5y4 5y5 812y1 9y2 9y3 9y4 9y5 20y1，y2，y3， y4，y5 03) 对偶问题最优解的关系 互为对偶的两个问题最优解之间的关系为 ：3求最小问题的任意可行解对应的目标函数值都不小于求最大问题的最优目标函数值，而 求最大问题的任意可行解的目标函数值都不大于求最小问题的最优目标函数值；32 如果一个线性规划问题有最优解，

39、那么其对偶问题也一定有最优解，且两个问题的最优目 标函数值相等； 最大值问题的原变量 Xj的值等于最小值对偶问题的第 j个剩余变量的检验数。 二多目标线性规划这种通常，在实际情况下，希望得到的某个行动方案并不像前面介绍的单目标规划那样， 只是使一个目标函数到达最优值， 而是希望该方案尽可能同时接近几个预定的目标值， 数学方法就称为 多目标规划法 ，简称 目标规划 。目标规划是由 Charnes 和 Cooper 于 1961 年 首次提出的。这里，着重介绍线性目标规划的有关问题。1. 问题的提出 在实际问题中，常需要研究在某些限制条件下，同时考虑多个目标的最优化问题。例如，人们在购置一件衣服时

40、，往往需要考虑质量、颜色、式样、大小、价格这五个目标；又 如在选择一个新厂址时， 除了要考虑运费、造价、 燃料供应费等经济指标以外，还要考虑对 环境影响等社会因素； 再如在设计货船时， 通常要考虑选取使船舶的试航速率最大， 年货运 量最多和运输本钱最低等多个目标都尽可能好的方案。例8投资决策问题 某投资开发公司拥有总资金 A万元，今有n 5?2个投资项 目可供选择。设投资第i i = 1,2,n个工程需用资金 a万元，预计可获利 bi万元，试 问应如何决策投资方案？解 一个好的投资方案应该是投资少，收益大的方案。设投资决策变量xi1,决定投资第i个工程0,决定不投资第i个工程(i 1,2, ,

41、n)由题意可知，投资第i i = 1,2,n个工程需用资金aixi万元，那么为了使总投资金额 尽可能地少，即有nmin f1ai xii1同时，投资第ii = 1,2,n个工程预计可获利 biXi万元，那么为了使获得的收益最大，又 应要求nmax f 2bi xii1此外，由于该公司的总资金为 A 万元，故有限制条件nai xiAi1而投资决策变量 xi 只能取 1 或 0，即满足xi(1 xi) 0，i 1, 2, ,n综上所述，所考虑的投资决策问题可归纳为以下具有两个目标的最优化问题： nnmin f1aixi， max f2bixii1i1nai xi As.t. i 1 i ixi (

42、1 xi ) 0， i 1, 2, ,n2. 数学模型的建立建立目标规划模型的基本思路是 ：(1) 确定决策定量 为，选择约束条件和各个目标函数，构造出多目标的线性规划；(2) 根据决策者的意图， 对各个目标函数确定相应的目标值， 并在这些目标函数方程中加 入偏离系数di、di + ,组成一组新的约束条件；(3) 用这些偏离系数产生目标规划的目标函数F,再根据各目标的轻重缓急赋予不同优先 级别的权因子3 i，使目标规划的目标函数到达最小。目标规划数学模型的一般形式为 ： mmin F i (di di )i1naij xj didibij1s.t.di ? di0xj 0 bi，di ，di0

43、式中，3 i为决策者根据具体情况选定的各目标优先级的权因子；di、di+分别表示未到达目标或超过目标的偏离系数，且对于任何目标都只能取二者 之一，故有 di ?di+=0 条件成立。示，试求获利最大的生产方案。数据甲乙拥有量原材料kg/件2111 kg设备台时/件1210台时利润f元/件810解 这是个单目标线性规划问题，设甲、乙产品的产量分别为Xi、X2,那么其数学模型为max f 8x110x22x1 x211s.t.x1 2x2x1, x2010用单纯形法求得最优决策方案为：X1 =4， X2 = 3， f = 62元。但实际上工厂在作决策时，还要考虑市场等一系列其它条件，譬如 。严格限

44、制原材料供应； 产品乙的产量不低于产品甲的产量； 充分利用设备的有效台时，但不希望加班；利润额不小于56元。同时希望将O2作为第一优先目标，将O 3作为第二优先目标，将O 4作为第三优先目标。先对条件O ,可引入偏离系数变量 d1+、d1 ,建立目标约束X2 X1 d1+d1 =0,并使3 1d1 tmin ;再对条件O3，可引入偏离系数变量d2+、d2，建立目标约束 X1+2X2 d2+d2 =10,并使3 2d2+d2 t min ;最后对条件O 4，可引入偏离系数变量d3+、d3，建立目标约束8x1+10x2 d3+d3 =56，并使3 3d3 t min。因此，建立相应的目标规划数学模

45、型为X1,X2,di ,di其中，权因子 1(i 1,2,3)minF1d1 2 (d2 d2 )2x1x211X2X1d1d10s.t.X12x2 d2 d2108x110x2 d3 d3563d3由此可见，在建立目标规划数学模型时，需要确定目标值、优先次序以及相应的权系 数等，它们都具有一定的主观性和模糊性，可以通过组织专家进行评估给以量化。3. 图解法例10用图解法求解例9的生产管理问题。解1在平面直角坐标系中，做出约束条件所确定的区域，如下列图O先画出绝对约束条件 1画法同线性规划图解法，即三角形区域 OAB ;O再画出目标约束条件 24。先令di =di+ =0 ,做出相应直线；然后

46、在直线旁标上di、di+，说明目标约束可沿着 di、di+所示方向平移平移方向是使di+或 di增加的方向。2根据目标函数中的优先因子来分析求解 先考虑第一优先因子3 1,即要求实现 min di。由图可见，可以满足 di =0，这时， xi、X2的取值范围只能在三角形 OBC上； 再考虑第二优先因子3 2,即要求实现 min(d2+d2)。当d2+= d2 =0时，xi、X2可在线 段ED上取值； 最后考虑第三优先因子3 3,即要求实现 mind3。从图中可以看到，要使 d3 =0, xi、 X2只能在多边形BCJF取值；因此，线段GD上的点即为该目标规划的最优解有效解。4. 分层单纯形法目

47、标规划与线性规划的数学模型没有本质区别，因而也可以用单纯形法求解，但考虑 到目标规划的某些特点，做出以下规定：j > 0j =1,2,n为最1由于目标规划问题的目标函数均为求最小值，故以检验数b 优准那么;b n=C CbA，所以各检验数b j中含有1,2, ,n2由于目标规划的检验系数矩阵b = b 1 b 2 不同优先级的权因子3k，即mMj cjciai jk j ki 1k 1当权因子3 1> 3 2>3 M时，从各检验数的整体来看，各检验数的正负首先决定于31的系数B 1 j的正负；假设卩1 j =0，那么检验数的正负就取决于32的系数B 2 j的正负；以此类推。注意：在目标规划的分层单纯形法中，其基变量的检验数同样为零向量。求解目标规划问题的.分层.单纯形法计算步骤为：1建立初始单纯形表，在表中将检验数行按优先因子个数分别列成M行，令k=1 ；2检查该检验数行中是否存在负数，且对应的前k 1行的系数是零。假设有负数，那么取其中最小者对应的变量为换入变量，并转至3；假设无负数，那么转至