第一章 线性规划

1、线线 性性 规规 划划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划的单纯形法线性规划的单纯形法线性规划的图解法线性规划的图解法单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论线性规划模型的应用线性规划模型的应用一、线性规划问题及其数学模型一、线性规划问题及其数学模型 例例1 1 某厂生产两种产品，下某厂生产两种产品，下表给出了单位产品所需资源及表给出了单位产品所需资源及单位产品利润单位产品利润 问：应如何安排生产计划，才问：应如何安排生产计划，才能使总利润最大？能使总利润最大？ （一）问题的提出（一）问题的提出解：解：

2、1.1.决策变量：设产品决策变量：设产品I I、IIII的的 产量分别为产量分别为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为z z，则，则 max z = 2 x1 + x23.3.约束条件：约束条件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20s.t. 设设 备备产产 品品 A B C D利润利润（元）（元） 2 1 4 0 2 2 2 0 4 3有有 效效 台台 时时 12 8 16 12 例例2 已知资料已知资料如右表所示，问如右表所示，问如何安排生产才如何安排生产才能使利润最大？能使利润最大？或如何考虑利润或如何考虑利润大，产品好销。大，产

3、品好销。解解max Z Z = 2x1 + 3x2 s.t. x1 , x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 121.1.决策变量：设产品决策变量：设产品I I、IIII的产量分别为的产量分别为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为Z Z，则：则：3.3.约束条件：约束条件： 例例3 3 某厂生产三种药物，这些某厂生产三种药物，这些药物可以从四种不同的原料中药物可以从四种不同的原料中提取。下表给出了单位原料可提取。下表给出了单位原料可提取的药物量提取的药物量 要求：生产要求：生产A A种药物至少种药物至少160160单单位，位，B

4、 B种药物恰好种药物恰好200200单位，单位，C C种药物不超过种药物不超过180180单位，且使单位，且使原料总成本最小。原料总成本最小。解：解：1.1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为：x1、x2 、x3 、x42.2.目标函数：设总成本为目标函数：设总成本为z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.3.约束条件：约束条件： 药物药物原料原料A AB BC C单位成本单位成本（元吨）（元吨）甲甲1 12 23 35 5乙乙2 20 01 16 6丙丙1 14 41 17 7丁丁1 12 22 28 8 x1 + 2x

5、2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 + x3 +2 x4 180 x1、x2 、x3 、x4 0s.t.1 1 问题中总有未知的变量，需要我们去解决。问题中总有未知的变量，需要我们去解决。 要求：有目标函数及约束条件，一般有非负条件要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。存在，由此组成规划数学模型。 如果在规划问题的数学模型中，变量是连续的如果在规划问题的数学模型中，变量是连续的（数值取实数）其（数值取实数）其目标函数是目标函数是有关变量的有关变量的线性函数线性函数（一次方），（一次方），约束条件是约束条件是有关变

6、量的有关变量的线性等式或不等线性等式或不等式式，这样，规划问题的数学模型是，这样，规划问题的数学模型是线性线性的。反之，就的。反之，就是非线性的规划问题（其中一个条件符合即可）。是非线性的规划问题（其中一个条件符合即可）。（二）数学模型（二）数学模型 （二）数学模型（二）数学模型 例例4 4 某工厂生产某工厂生产A A、B B两种产品，两种产品，有关资料如下表所示：有关资料如下表所示：设：总成本为设：总成本为Z，A、B产品产品销量为销量为x1、x2，产品，产品C C的销售的销售量为量为x3，报废量为，报废量为x4，则：，则： max z = 4 x1 + 10 x2 + 3 x3 2 x4 2

7、x1 + 3x2 12 3x1 + 4x2 24 - 4x2 +x3 + x4 = 0 x3 5 x1、x2 、x3 、x40s.t.解：解：（二）数学模型（二）数学模型 船只种类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量12002400航线号航线号船队船队类型类型编队形式编队形式货运成本货运成本（千元队）（千元队）货运量货运量（千吨）（千吨）拖轮拖轮A型型驳船驳船B型型驳船驳船1112362521436202322472404142720问：应如何编队，才能既完成合同任务，又使总货运成本问：应如何编队，才能既完成合同任务，又使总货运

8、成本为最小？为最小？例例5 5 某航运局现有船只种类、数量以及计划期内各条航线的某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：货运量、货运成本如下表所示：解：设解：设x xj j为第为第j j号类型船队的队数（号类型船队的队数（j = 1j = 1，2 2，3 3，4 4），）， z z 为总货运成本为总货运成本则则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1+20 x2 200 40 x3+20 x4400 xj 0 （

9、j = 1,2,3,4）s.t.船只种类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量1200240000 12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcZ)()(min)max目标函数：目标函数：约束条件：约束条件：2 2、线性规划数学模型的一般形式、线性规划数学模型的一般形式 模型特点模型特点1 1 都用一组决策变量都用一组决策变量X = (x1,x2,xn)T表示某一方案，表示某一方案，且决策变量取值非负；且决策变量取值非负；满足以上三个条件的满足以上三个条件的数学模型数学模型称

10、为称为线性规划线性规划2 2 都有一个要达到的目标，并且目标要求可以表示成都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；决策变量的线性函数；3 3 都有一组约束条件，这些约束条件可以用决策变量都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。的线性等式或线性不等式来表示。也可以记为如下形式也可以记为如下形式：)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 目标函数：目标函数：约束条件：约束条件：如将上例用表格表示如下：如将上例用表格表示如下：设变量设变量)21( njxj 产产 品品 j 设设 备备

11、i 有效台时有效台时 利润利润 mnmijnaaaaa 1111n 2 1m 2 1 mbbb 21nccc 21jcib向向 量量 形形 式：式： ) (21ncccC nxxX1 mjjjaap1 mbbb1 0).( (min) max1XbxpCXZnjjj矩阵和向量形式：矩阵和向量形式： mnmnaaaaA1111 0 )( (min) maxXbAXCXZ（三）线性规划模型的标准形式（三）线性规划模型的标准形式 )n 2 1(j 0 m) 2 1(i jijijjjxbxaxcZmax1 1、标准形式标准形式 将模型的一般形式变成标准形式，再根据标准型将模型的一般形式变成标准形式，

12、再根据标准型模型，从可行域中找一个基本可行解，并判断是否是模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。个基本可行解，当目标函数达到最大时，得到最优解。 目标函数为求极大值，也可以用求极小值；目标函数为求极大值，也可以用求极小值； 所有约束条件（非负条件除外）都是等式，所有约束条件（非负条件除外）都是等式，右端常数项为非负；右端常数项为非负； 变量为非负。变量为非负。3、转换方式：、转换方式： 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即

13、 ，则可将目标函，则可将目标函数乘以（数乘以（1 1），可化为求极大值问题。），可化为求极大值问题。 jjxcZmin也就是：令也就是：令 ，可得到下式，可得到下式ZZ 即即=jjxcZaxm2、特征：、特征：(3) (3) 约束方程的转换：由不等式转换为等式约束方程的转换：由不等式转换为等式 。 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量 (2)(2)常数项常数项b bi i0 0的转换：约束方程两边乘以（的转换：约束方程两边乘以（1 1）。）。(4) (4) 变量的变换变量的变换 若存在取值无约

14、束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx。显然，令00jjjjx，xxx若若 例1：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0 解：首先,将目标函数转换成极大化：令 z= -f = -3.6x1+5.2x2-1.8x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性

15、规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 0例例2 ：将下列线性规划问题化为标准形式：将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321xxxxxxxxxxxxxxxZ为无约束（无非负限制）为无约束（无非负限制） 解解: : 用用 替换替换 ，且，且 ， 54xx 3x0,54 xx76, xx引入变量引入变量将第将第3 3个约束方程两边乘以个

16、约束方程两边乘以（1 1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式线性规划问题的求解方法线性规划问题的求解方法 二、图二、图 解解 法法（一）解题步骤（一）解题步骤4 4

17、 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 1 在直角平面坐标系中画出所有的约束等式，并找出所在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称有约束条件的公共部分，称为可行域，可行域中的点称为可行解。为可行解。 2 2 标出目标函数值增加的方向。标出目标函数值增加的方向。3 3 若求最大（小）值，则令目标函数等值线沿（逆）目若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。点，该点就是最优解。例：例： 0,0

18、124 16 482122232max2121212121xxxxxxxxxxZ 01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 最最 优优 解：解：x1 = 4 x2 = 2有惟一最优解有惟一最优解x2 x1(4 2) 00124 16 4821222322121212121xxxxxxxxxxZ,max最最 优优 值值：Z = 14（二）线性规划问题解的情况（二）线性规划问题解的情况惟惟 一一 解解无无 穷穷 解解无无 界界 解解无可行解无可行解01 2 3 4 5 6 7 8 1 2 3 4 5 6 例：例：x2 x1 00124 16 48212222212121

19、2121x,xxxxxxxxxZmax无穷多最优解无穷多最优解 例：例：无穷多最优解无穷多最优解无界解无界解x1x1x2 x2 例：例： 012221212121x,xxxxxxxZmax 0,02 1223622max212212121xxxxxxxxxZ 0,6321 23min2121211xxxxxxxxZx1x2 无可行解无可行解例例（三）由图解法得到的启示（三）由图解法得到的启示(1)(1)线性规划问题解的情况：惟一最优解；无穷线性规划问题解的情况：惟一最优解；无穷多最优解；无界解；无可行解多最优解；无界解；无可行解 (3)(3)最优解一定是在凸集的某个顶点最优解一定是在凸集的某个

20、顶点(2)(2)线性规划问题的可行域是凸集（凸多边形）线性规划问题的可行域是凸集（凸多边形） (4) (4)解题思路解题思路是，先找出凸集的任一顶点，计算是，先找出凸集的任一顶点，计算 其目标函数值，再与周围顶点的目标函数值比其目标函数值，再与周围顶点的目标函数值比 较，如不是最大，继续比较，直到找出最大为较，如不是最大，继续比较，直到找出最大为 止。止。（一）线性规划问题解的概念（一）线性规划问题解的概念 可行解可行解：满足约束条件：满足约束条件、的解的解 X=(x1, x2 ， ，xn)T为可行解。其中使目标函数达为可行解。其中使目标函数达 到最大值的可行解称为最优解。所有解的集合到最大值

21、的可行解称为最优解。所有解的集合 为可行解的集或可行域。为可行解的集或可行域。三、线性规划的单纯形法三、线性规划的单纯形法11max(1),1,2,(2)0,1,2,(3)njjjnijjijjzc xa xb imxjn（一）线性规划问题解的概念（一）线性规划问题解的概念 (2) (2) 基基：B B是系数矩阵是系数矩阵A A（m mn n阶）中的一个阶）中的一个m mm m阶的满秩子矩阵阶的满秩子矩阵( ( B B 0)0)，称，称B B是一个基。是一个基。) (211111mmmmmpppaaaaB 则称则称 Pj ( j = 1 2 m) 为基向量为基向量。 Xj 为基变量，否则为非基

22、变量。为基变量，否则为非基变量。三、线性规划的单纯形法三、线性规划的单纯形法 基解基解：满足条件：满足条件，但不满足条件，但不满足条件的的 所有解，最多为所有解，最多为 个。个。Cmn 基可行解基可行解：满足非负约束条件的基解，：满足非负约束条件的基解， 简称基可行解。简称基可行解。 可行基可行基：对应于基可行解的基称为可行基。：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解 例3: 考虑线性规划模型 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 +

23、 x5 = 75 x1 , x2 , x3 , x4 , x5 0 注意，线性规划的基本解、基本可行 解（极点）和可行基只与线性规划问 题标准形式的约束条件有关。 3 2 1 0 0A = P1 ,P2 ,P3 ,P4 ,P5 = 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个33的子矩阵： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5 其中B B

24、4= 0，因而B B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。 对于基B B3=p1 ，p2 ，p5 ，令非基变量x3 3 = 0， x4 = 0，在等式约束中令x3 = 0，x4 = 0，解线性方程组： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的基本可行解： x=(x1 ，x2 ，x3 ，x4 ，x5)T=(15，10，0，0，45)T。于是对应的基B B3是一个可行基。 类似可得到 x(2) = (5,25,0,5,

25、0)T （对应B2） x(7) = (20,0,5,0,75)T （对应B5） x(8) = (0,25,15,15,0)T （对应B7） x(9) = (0,0,65,40,75)T （对应B10） 是基本可行解； 而x(3)= (0,32.5,0,7.5,-22.5)T（对应B9） x(4)= (65/3,0,0,-10/3,75)T （对应B6） x(5)= (7.5,25,-7.5,0,0)T （对应B1） x(6) = (0,40,-15,0,-45)T （对应B8） 是基本解。 因此，对应基本可行解（极点）的B2 B3 B5 B7 B10都是可行基。 这里指出了一种求解线性规划问题

26、的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。 （二）凸集及其顶点（二）凸集及其顶点 凸集凸集：设设K是是n n维欧氏空间的一点集，若任意两点维欧氏空间的一点集，若任意两点 X(1)K，X(2)K的的连线上的所有点连线上的所有点X(1)+(1- )X(2)K，(01)；则称则称K K为凸集。为凸集。 任何两个凸集的交集是凸集 顶点顶点：设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为X=X(1)+(1-)X(2)，(01) 则称X为K的一

27、个顶点(或极点)。 图中0，Q1,2,3,4都是顶点推论 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。 几个基本定理 定理1 若线性规划问题存在可行域，则其可行域是凸集 njjjjxbxPXD10,证：为了证明满足线性规划问题的约束条件njjjjnjxbxP1, 2 , 1, 0,的所有点(可行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点；X(1)X(2)。TnTnxxxXxxxX222212112111,则有 njjjjnjjjjnjxbxPnjxbxP122111, 2 , 1, 0, 2 , 1, 0, 令 X=(x1，x2，xn)T

28、为 x(1),x(2)连线上的任意一点，即 X=X(1)+(1-)X(2) (01) X 的每一个分量是 21)1 (jjjxxx，将它代入约束条件， 得到 bbbbxPxPxPxxPxPnjnjjjjjnjjjnjnjjjjjj11221111211又因 01 , 0, 0,21jjxx，所以 xj0，j=1,2,n。 由此可见 XD，D 是凸集。 证毕。 引理 1 线性规划问题的可行解 X= (x1, x2, ，xn)T 为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。 定理定理2 2 线性规划问题的基可行解X对应于可行 D的顶点。定理定理3 3 若可行域有界，线性规划问题

29、的目标函数一定若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。可以在其可行域的顶点上达到最优。证证 设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z*=max z)。因X(0)不是顶点，所以它可以用D的顶点线性表示为 kikiiiiiixX1101, 0,定理定理33 若线性规划问题有最优解，一定存在一个若线性规划问题有最优解，一定存在一个基可行解是最优解。基可行解是最优解。代入目标函数得 kikiiiiiCXXCCX110 在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i

30、)中最大者。并且将X(m)代替(*)式中的所有X(i)，这就得到（*） mkimikiiiCXCXCX11由此得到 CX(0)CX(m)根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。 有时目标函数可能在多个顶点处达到最大;这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优解。 假设 是目标函数达到最大值的顶点，若是这些顶点的凸组合，即 kikiiiiiXX111, 0,于是 kiiikiiiXCXCXC11 kimXCi, 2 , 1,设：于是：mmXCkii1综上所述综上所述, ,我们在理论上得到了线性规划问题的以我

31、们在理论上得到了线性规划问题的以下结论：下结论： 线性规划问题的可行域是一凸集（包括有界凸集和无界凸集）；线性规划问题的每个基本可行解对应着可行域的一个极点（顶点）；若线性规划问题有最优解,必在可行域的某一极点上得到。由此可见,我们只需在基本可行解中寻求最优解。如何有效地寻求最优解,这就是下节要介绍的单纯形法。 基本思路：基本思路：将模型的一般形式变成标准形式，再根将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基可行解，并判据标准型模型，从可行域中找一个基可行解，并判断是否是最优。如果是，获得最优解；如果不是，断是否是最优。如果是，获得最优解；如果不是，转换到另一个基可行解，

32、当目标函数达到最大时，转换到另一个基可行解，当目标函数达到最大时，得到最优解。得到最优解。（四）单纯形法迭代原理（四）单纯形法迭代原理例例: 0,124 16 482122232max2121212121xxxxxxxxxxZ变成标准型变成标准型 0 12 4 16 4 8 2 21 220000326543216251421321654321x,x,x,x,x,xxxxxxxxxxxxxxxxxZmax 约束方程约束方程的系数矩阵的系数矩阵 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21

33、xx ,为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立确定初始基确定初始基B B令：令：12x 16x 8x 12x 0654321 xx则：则： 基可行解为基可行解为（0 0 12 8 16 120 0 12 8 16 12）T T 此时，此时，Z = 0Z = 0 找另一个基可行解。找另一个基可行解。即将非基变量换入基变量即将非基变量换入基变量中，但保证其余的非负中，但保证其余的非负。如此循环下去，直到找如此循环下去，直到找到最优解为止。到最优解为止。 注意注意：为尽快找到最优解，在换入变量时有一定：为尽快找到最优解，在换入变量时有一定的要求。如将目标

34、系数大的先换入等。的要求。如将目标系数大的先换入等。确定新的基（换基）确定新的基（换基）找出一个初始可行解找出一个初始可行解 是否最优是否最优转移到另一个目标函数转移到另一个目标函数（找更大的基可行（找更大的基可行 解）解）最优最优 解解是是否否循循环环直到找出为止，直到找出为止，核心核心是：是：变量迭代变量迭代结结 束束其步骤总结如下：其步骤总结如下：当当 时，时， 为换入变量为换入变量 01x2x0 4120 160 2 802122652423 xxxxxxx确定换出变量确定换出变量3)412 28 212min( 2x6x为换出变量为换出变量接下来有下式：接下来有下式： 4 124 3

35、 416 2 82 1 212 2 6215124123xxxxxxxxxx 用高斯法，将用高斯法，将 的系数列向量换为单位列向量，的系数列向量换为单位列向量，其步骤是：其步骤是：2x(3)(3,)(42-2)()(2,)(42-(1)(1 ,4)4()4( 结果是：结果是：621561461341 3 416 21 2 2126 xxxxxxxxxx 1 2 3 4 4 12 4 3 416 2 8 2 1 212 2 6215124123xxxxxxxxxx 代入目标函数：代入目标函数：616143294392xxxxZ 有正系数表明：还有潜力可挖，没有达到最大值；有正系数表明：还有潜力可

36、挖，没有达到最大值；此时：令此时：令 得到另一个基可行解得到另一个基可行解 （0，3，6，2，16，0）T1x 有负系数表明：若要剩余资源发挥作用，就必须有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当支付附加费用。当 时，即不再利用这些资源。时，即不再利用这些资源。6x06 x9 , 061 Zxx如此循环进行，直到找到最优为止。如此循环进行，直到找到最优为止。本例最优解为：本例最优解为：（4，2，0，0，0，4）T14maxZ 81231454 xxz一般线性规划问题的求解 初始基可行解的确定为了确定初始基可行解，要首先找出初始可行基，其方法如下。 (1)直接观察 (2)加松弛变

37、量 (3)加非负的人工变量(1)直接观察njxbxPxczjnjjjnijjj, 2 , 10211201max1若线性规划问题 从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基111,21mPPPB(2)加松弛变量 对所有约束条件是“”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。 经过整理，重新对xj及aij (i=1, 2,m; j=1,2,n)进行编号，则可得下列方程组其中x1,x2,xm 为松弛变量njxbxaxaxbxaxaxbxaxaxjmnmmmmmnnmmnnmm, 2 , 1, 022111,2211, 221111, 11于是含

38、有mm单位矩阵，以B作为可行基。 111,21mPPPB将(1-22)式每个等式移项得令xm+1=xm+2=xn=0，由(1-23)式可得 xi=bi (i=1,2,m)nmmmmmmnnmmnnmmxaxabxxaxabxxaxabx11,211, 222111, 111231得到一个初始基可行解 又因bi0(在1-3节中已做过规定)，所以得到一个初始基可行解 X=(x1,x2,xm,0，0)T n-m个 =(b1,b2,bm,0，0)T n-m个(3)加非负的人工变量 对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。 即对不等式约束减去一个非负的剩余变

39、量后，再加上一个非负的人工变量； 对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。关于这个方法将在本章第5节中进一步讨论。3.33.3最优性检验与解的判别最优性检验与解的判别 对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况， 为此需要建立对解的判别准则。一般情况下，经过迭代后(1-23)式变成 1,1,2,1 24niiijjj mxba xim 将 代入目标函数(1-20)式，整理后得251)(11111111111111111 minmjjmiijijiinmjjjnmjjijmiimiiinmjjjnmjjijmiimiiinmjjjmin

40、mjjijiiminmjjjiinjjjxaccbcxcxacbcxcxacbcxcxabcxcxcxcznmjmijxijaibix1), 2 , 1,(令mimiijijiinmjaczbcz110, 1,nmjjjjxzczz10)261 (于是nmjzcjjj, 1设27110nmjjjxzz1最优解的判别定理 若 为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。 TmbbbX0,0,210当所有非基变量的j0时，由（1-27）式可知已不存在任一可换入的非基变量，使目标函数继续增大。所以以j0，为最优解的判别准则。27110nmjjjxz

41、z2.无穷多最优解判别定理 若 为一个基可行解，对于一切j=m+1，,n，有j0，又存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。证: 只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因m+k=0，由(1-27)知z=z0，故X(1)也是最优解。由凸组合的性质可知X(0)，X(1)连线上所有点都是最优解。 Tm,b ,b ,bX002103无界解判别定理若 为一基可行解，有一个m+k0，并且对i=1,2,，m，有存在。 那么该线性规划问题具有无界解(或称无最优解)。 TmbbbX0,0,210,0i mka证: 构造一个新的解 X(1)，它的分量为 kmjn

42、mjxxabxjkmkmiii并且, 1; 0011,1因 ，所以对任意的0都是可行解，把x(1)代入目标函数内得z=z0+m+k因m+k0，故当+，则z+，故该问题目标函数无界。0,kmia 以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述，将其化为标准型。 如果不化为标准型，只需在上述1，2点中把j0改为j0，第3点中将m+k0改写为m+k0即可。 二、单纯形法的矩阵描述二、单纯形法的矩阵描述 在线性规划问题的标准型：在线性规划问题的标准型： Max TzC X0. .XbAXts中，不妨设中，不妨设 是一个可行基，则系数是一个可行基，则系数矩阵可

43、分块为（，）。对应于的基变量为矩阵可分块为（，）。对应于的基变量为 非基变量为非基变量为令，其中为基变量令，其中为基变量 的系数列向的系数列向量。量。N=于是原问题可化为于是原问题可化为NBTNTBTXXCCXCZMax),(),(21mpppBTmBxxxX),(21TnmmNxxxX),(21),(21nmmppp),(TNTBTCCCTBCBX0,),(. .NBNBXXbXXNBts 即 对约束方程两边同左乘以 ， 得 = ， 并代入目标函数，得NTNBTBTXCXCXCZMax0,. .NBNBXXbNXBXts1BNNXBbB11BXNTBTNTBXNBCCbBCZ)(11 令非基

44、变量 =0得 = , 从而相应的基本可行解为 目标函数取值为 又由于 ,故有 NXBXbB101bBXXXNBbBCZTB101BBCCTBTBNTBTNBTBTBTBXNBCCXBBCCbBCZ)()(111XABCCbBCTBTB)(11将 及Z的表达式又可写成令 则又有 + = +BX1111()BNTTTNBNBXB NXB bZCC B N XC B bNBCCTBTNN1ABCCTB1bBCZTB1NNXbBCTB1XAjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc lkl

45、k ik iiabaab=)0min(=四、单纯形法计算步骤四、单纯形法计算步骤单纯形表单纯形表1-1根据max(j0)=kjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0lklk ik iiabaab=)0min(=四、单纯形法计算步骤四、单纯形法计算步骤单纯形表单纯形表1-11,11mmii micc a1mniinicc a根据max(j0)=k单纯形表的说明 XB列中填入基变量，这里是x1，x2,，xm； CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的； b列中填入约

46、束方程组右端的常数； cj行中填入基变量的价值系数c1,c2,cn； i列的数字是在确定换入变量后，按规则计算后填入； 最后一行称为检验数行，对应各非基变量xj的检验数是1,1,2,mjjiijicc ajn4.2 4.2 计算步骤计算步骤 表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。 计算步骤： (1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。 (2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。 miijijjacc1,njj, 2 , 1, 0 (3) 在j0,j=m+1,n中，若有某个k对应xk的系数

47、列向量Pk0，则此问题是无界，停止计算。 否则，转入下一步。 (4) 根据max(j0)=k，确定xk为换入变量，按规则计算lklikikiabaab0min (5) 以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量 将XB列中的xl换为xk，得到新的单纯形表。重复(2)-(5)，直到终止。行第变换laaaaPmklkkkk010021 0 12 4 16 4 8 2 21 220000326543216251421321654321x,x,x,x,x,xxxxxxxxxxxxxxxxxZmax例例 题：题：判定标准：判定标准： zc zcacz zcjjjjij

48、ijjjj)0:(min0:max= cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z i2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x6000 x3x4x5 Z i3x23010001/42620100-1/210010 0-1/216 40 0 0 1 020000-3/4 cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60003x3

49、x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4Z i2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412Z 0 0 0 -2 0 1/4icj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -

50、1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0 Z 0 0 -1/2 -1 0 0i 0 0 0 -2 0 1/4Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cjicj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8

51、 0Z 0 0 0 -3/2 -1/8 0i 0 0 0 -2 0 1/4Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cji最优解最优解： X=（4，2，0，0，0，4）T 最优值最优值： Z=14（一）模型情况（一）模型情况 变变 量：量：xj0 xj0 xj无约束无约束 结结1、组成、组成 约束条件：约束条件： = b 目标函数：目标函数： max min 果果2 、变量、变量 xj0 令令 xj= -xj

52、， xj0 xj0 不处理不处理 xj 无约束无约束 令令xj = xj xj, xj0 , xj0 惟一最优解惟一最优解无穷最优解无穷最优解无界解无界解无可行解无可行解 五、单纯形法的进一步讨论五、单纯形法的进一步讨论3 3、约束、约束 条件：条件：bxpbxpbxpjjjjjj 加入松弛变量加入松弛变量加入人工变量加入人工变量先减去先减去 再加上再加上axaxsxsx例：例： x,x,xx xxxxxx x xxxZmax0123241123321313213213214 4、目标函数：、目标函数：max (min) 设规划模型约束条件为设规划模型约束条件为 ，需加入人工变，需加入人工变量

53、量 ，而得到一个，而得到一个mm的单位矩阵，即基变量组合。的单位矩阵，即基变量组合。因人工变量为因人工变量为虚拟变量虚拟变量，且存在于初始基可行解中，需要，且存在于初始基可行解中，需要将它们从基变量中替换出来。若基变量中将它们从基变量中替换出来。若基变量中不含有非零的人不含有非零的人工变量工变量，表示原问题有解。若当，表示原问题有解。若当 ，还有人工变，还有人工变量（非零）时，则表示原问题无可行解。量（非零）时，则表示原问题无可行解。axbxpJJ 0 jjzc123123 123131257467max3 2 11 42 3 2 1 ,0 Zxxxxxxxxxxxxxxxxxx， ， 加入人

54、工变量后，目的是找到一个单位向量，叫人加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：取值。一般可采用两种方法处理：大大M法法和和两阶段法两阶段法。 即假定人工变量在目标函数中的系数为即假定人工变量在目标函数中的系数为M（任意大正数），（任意大正数），如果是求极大值，需加如果是求极大值，需加- -M；如果；如果是求极小值，需加是求极小值，需加M。如基变量中还存在。如基变量中还存在M，就不能，就不能实现极值。实现极值。 003 003 如上例：76543217654321Mx

55、MxxxxxxZminMxMxxxxxxZmax 或或：大大M法法：来判断计算过程如下：用 zcjj0cj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z3-6M-1+M-1+3M0-M00cBxBbx1x2x3x4x5x6x70 x4103-20100-1-Mx610100-11-21-1x31-2010001Z1-1+M00-M0-3M+1iimiijijjacc1,cj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-1

56、1-2-1x31-2010001Z1000-1-M+1-M-1cBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z000-1/3-1/3-M+1/3-M+2/3ii最优解为最优解为（4 1 9 0 0 0 0）T，Z = 2 用计算机处理数据时，只能用很大的用计算机处理数据时，只能用很大的 数代替数代替M, ,可能造成计算机上的错误，故多采用两可能造成计算机上的错误，故多采用两 阶段法。阶段法。 第一阶段第一阶段(先求解一个只包含人工变量的先求解一个只包含人工变量的LP) 在原线性规划问题中加

57、入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型： 0 0011111111111mnmmnnmnmnnnnmnnxxbxxaxabxxaxaxxxxmin（2）两阶段法：两阶段法： 对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若=0,=0,说明问说明问题存在基可行解，可以进行第二个阶段；否则，原问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。题无可行解，停止运算。 第二阶段：第二阶段：在第一阶段的最终表中，去掉人工变在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，量，将目标函数的系数换成原问题的目标函数系

58、数，作为第二阶段计算的初始表（用单纯形法计算）。作为第二阶段计算的初始表（用单纯形法计算）。32143217624112xxxxxxxxxminl 第一阶段目的是为原问题求初始基可行解；或明确第一阶段目的是为原问题求初始基可行解；或明确 原问题无解。原问题无解。l第二阶段再在此基可行解的基础上对原目标函数进第二阶段再在此基可行解的基础上对原目标函数进 行优化，或者明确有无界解。行优化，或者明确有无界解。1231234 123513127max3 2 11 42 3 2 1 ,0 Zxxxxxxxxxxxxxxxx， 上例：上例： x,x,xx xxxxxx x xxxZmax012324112

59、3321313213213216 x7 x x,x,x x x x xx xxx xxx x xxmin 01232411272173165321432176，第一阶段第一阶段的线性规划问题可写为：的线性规划问题可写为：第一阶段单纯形法迭代的过程见下表第一阶段单纯形法迭代的过程见下表（注意：化为标准形式，即极大化问题）（注意：化为标准形式，即极大化问题）cj00000-1-1cBxBbx1x2x3x4x5x6x70 x4111-21100011-1x63-4120-1103/2-1x71-20100011-6130-1000 x4103-20100-1-1x610100-11-210 x31-

60、20100010100-10-3i0 x4123001-22-50 x210100-11-20 x31-201000000000-1-1cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z1000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z000-1/3-1/3i第二阶段第二阶段： 最优解为（最优解为（4 1 9 0 04 1 9 0 0）T T，目标函数，目标函数 Z = 2Z = 254321003xxxxxZmax3231 323x , 3 :052122 xxxbbii，变变换