第五章线性规划方法

1、线性规划及其单纯形求解方法线性规划及其单纯形求解方法 运输问题的求解方法运输问题的求解方法表上作业法表上作业法v线性规划是运筹学中发展较快、应用较广和线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它在实际应用中日益比较成熟的一个分支。它在实际应用中日益广泛与深入广泛与深入,已经被广泛地应用到工业、农业、已经被广泛地应用到工业、农业、商业与交通运输规划，工程技术的优化设计，商业与交通运输规划，工程技术的优化设计，以及企业管理等各个领域。以及企业管理等各个领域。 v 在地理学领域，线性规划，作为传统的计在地理学领域，线性规划，作为传统的计量地理学方法之一，是解决有关规划、决策量地理学方

2、法之一，是解决有关规划、决策和系统优化问题的重要手段。和系统优化问题的重要手段。第一节第一节 线性规划及其单纯形求解方法线性规划及其单纯形求解方法v线性规划的数学模型线性规划的数学模型v线性规划的标准形式线性规划的标准形式v线性规划的解及其性质线性规划的解及其性质v线性规划问题的求解方法线性规划问题的求解方法单纯形法单纯形法v应用实例应用实例: 农场种植计划模型农场种植计划模型线性规划及其单纯形求解方法线性规划及其单纯形求解方法v一、线性规划的数学模型一、线性规划的数学模型（一）线性规划模型之实例（一）线性规划模型之实例线性规划研究的两类问题：线性规划研究的两类问题：某项任务确定后，如何统筹安

3、排，以最少的某项任务确定后，如何统筹安排，以最少的人力、物力和财力去完成该项任务；人力、物力和财力去完成该项任务；面对一定数量的人力、物力和财力资源，如面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。何安排使用，使得完成的任务最多。合理下料问题合理下料问题资源利用问题资源利用问题线性规划及其单纯形求解方法线性规划及其单纯形求解方法v已知：已知：某地区拥有某地区拥有m种资源。其中，第种资源。其中，第i种资源在规划期内的种资源在规划期内的限额为限额为bi(i=1，2，m);这这m种资源可用来生产种资源可用来生产n种产品，其中，生产单位数量种产品，其中，生产单位数量的第的第j种

4、产品需要消耗的第种产品需要消耗的第i种资源的数量为种资源的数量为aij(i=1，2，m；j=1,2, ,n);第第j种产品的单价为种产品的单价为cj(j=1，2， ，n)。v求：求：试问如何安排这几种产品的生产计划，才能使规划期试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大内资源利用的总产值达到最大?资源利用问题资源利用问题 资源利用问题资源利用问题returnv设第设第j种产品的生产数量为种产品的生产数量为xj(j=1，2，n)njjjxcZ1max消耗资源数量消耗资源数量第一种资源第一种资源第二种资源第二种资源第三种资源第三种资源第第m种资源种资源资源利用问题资源

5、利用问题.x1x1x1.x1x2x2x2.x2x3x3x3.x3xnxnxn.xn.return第一种产品第一种产品a11a21a31am1第二种产品第二种产品a12a22a32am2第三种产品第三种产品a13a23a33am3第第n种产品种产品a1na2na3namn消耗资源数量消耗资源数量第一种资源第一种资源第二种资源第二种资源第三种资源第三种资源第第m种资源种资源资源利用问题资源利用问题jnjjxa11jnjjxa12jnjjxa13jnjmjxa1 b1 b2 b3 bmnjijijmibxa1), 2 , 1(), 2 , 1(0njxj资源利用问题资源利用问题v设第设第j种产品的生

6、产数量为种产品的生产数量为xj(j=1，2，n)，则上，则上述资源问题就是：述资源问题就是： 求一组实数变量求一组实数变量xj (j=1，2，n)，使其满足，使其满足), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjjxcZ1maxreturn约束条件约束条件目标函数目标函数合理下料问题合理下料问题v设采用设采用Bj方式下料的原材料数为方式下料的原材料数为xj ，则上述问题可，则上述问题可表示为：表示为： 求一组整数变量求一组整数变量xj(j=1，2，n)，使得，使得), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjxZ1min约束条件约束条

7、件目标函数目标函数用某种原材料切割零件用某种原材料切割零件A1，A2, ,Am的毛坯，现已设的毛坯，现已设计出在一块原材料上有计出在一块原材料上有B1，B2，Bn种不同的下料种不同的下料方式，如用方式，如用Bj下料方式可得下料方式可得Ai种零件种零件aij个，设个，设Ai种零种零件的需要量为件的需要量为bi个。试问应该怎样组织下料活动，才个。试问应该怎样组织下料活动，才能使得既满足需要，又节约原材料？能使得既满足需要，又节约原材料？ 假设某种物资（譬如煤炭、钢铁、石油等）有假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，个产地，n个销地。第个销地。第i产地的产量为产地的产量为ai（i=1，2

8、，m），第），第j 销地的需求量为销地的需求量为bj(j=1, 2，n)，它们满，它们满足产销平衡条件。足产销平衡条件。 如果产地如果产地i到销地到销地j的单位物资的运费为的单位物资的运费为Cij，要使，要使总运费达到最小，可这样安排物资的调运计划：总运费达到最小，可这样安排物资的调运计划：minjjiba11运输问题运输问题 设设xij表示由产地表示由产地i供给销地供给销地j 的物资数量，则的物资数量，则上述问题可以表述为：上述问题可以表述为： 求一组实值变量求一组实值变量xij(i=1，2，m；j=1，2，n)，使其满足，使其满足 而且使而且使 ), 2 , 1;, 2 , 1(0), 2

9、 , 1(), 2 , 1(11njmixmiaxnjbxijnjiijmijijminjijijxcz11min线性规划及其单纯形求解方法线性规划及其单纯形求解方法v（二）线性规划的数学模型（二）线性规划的数学模型 以上例子表明，线性规划问题具有以下特征：以上例子表明，线性规划问题具有以下特征： 每一个问题都用一组未知变量（每一个问题都用一组未知变量（x1，x2，xn）表示某一规划方案，其一组定值）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。变量的取值是非负的。 每一个问题的组成部分：一是目标函数，每一个问题

10、的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。解范围，使问题的解必须在这一范围之内。 每一个问题的目标函数和约束条件都是线每一个问题的目标函数和约束条件都是线性的。性的。线性规划及其单纯形求解方法线性规划及其单纯形求解方法v（二）线性规划的数学模型（二）线性规划的数学模型 由此可以抽象出线性规划问题的数学模型，一由此可以抽象出线性规划问题的数学模型，一般形式为：般形式为：在线性约束条件在线性约束条件以及非负约束条件以及

11、非负约束条件 xj0（j=1，2，n）下，求一组未知变量下，求一组未知变量xj (j=1，2， ，n)的值，使的值，使njijijmibxa1), 2 , 1(),(njjjxcZ1(min)max线性规划及其单纯形求解方法线性规划及其单纯形求解方法在约束条件在约束条件 AX(，)bX0下，求未知向量下，求未知向量 ，使得，使得Z=CXmax(min) TnxxxX,21,2121nTmcccCbbbbmnmmnnaaaaaaaaaA212222111211线性规划及其单纯形求解方法线性规划及其单纯形求解方法v二二 线性规划的标准形式线性规划的标准形式（一）（一）线性规划的标准形式线性规划的标

12、准形式 在讨论与计算时，需要将线性规划问题的数在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式学模型转化为标准形式（二）（二）化为标准形式的方法化为标准形式的方法 mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111xj0（j = 1，2，n） 下，求一组未知变量下，求一组未知变量xj （j = 1，2，n）的值，）的值，使使njjjxcZ1maxnjijijmibxa1), 2 , 1(在约束条件下在约束条件下线性规划及其单纯形求解方法线性规划及其单纯形求解方法记为如下更为紧凑的形式：记为如下更为紧凑的形式： ), 2 , 1(0)

13、, 2 , 1(max11njxmibxaxcZjnjijijnjjj或0XbAXCXZmax线性规划及其单纯形求解方法线性规划及其单纯形求解方法returnv具体的线性规划问题，需要对目标函数或约束条件进行转换，化为标准形式。1.目标函数化为标准形式的方法目标函数化为标准形式的方法 v如果其线性规划问题的目标函数为：v min Z = CX v显然有： minZ = max(-Z)=max Z v则目标函数的标准形式为： max Z= -CX线性规划及其单纯形求解方法线性规划及其单纯形求解方法2.2.约束方程化为标准形式的方法约束方程化为标准形式的方法 若第k个约束方程为不等式，即 引入松弛

14、变量 , K个方程改写为：则目标函数标准形式为：knknkkbxaxaxa)(22110knxkknnknkkbxxaxaxa)(2211njnjknjjjjxoxcxcZ11线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划及其单纯形求解方法三、线性规划的解及其性质三、线性规划的解及其性质 v（一）线性规划的解（一）线性规划的解 可行解与最优解可行解与最优解满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。 基本解与基本可行解基本解与基本可行解 在线性规划问题中，将约束方程

15、组的mn阶矩阵A写成由n个列向量组成的分块矩阵,21npppA), 2 , 1(,21njaaaPTmjjjj线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划及其单纯形求解方法 如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设：则称 为基向量，与基向量相对应的向量 为基变量，而其余的变量 为非基变量。 ,21212222111211mmmmmmmPPPaaaaaaaaaB),2, 1(mjPj),2, 1(mjxj),2, 1(nmmjxi线性规划及其单纯形求解方法线性规划及其单纯形求解方法如果 是方程组 的解，则就是方

16、程组式 的一个解，它称之为对应于基B的基本解，简称基解。 满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。TmBxxxX,21bBXBTmxxxX0,0,0,21CXZmax线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划问题的以上几个解的关系，可用下图来描述：线性规划及其单纯形求解方法线性规划及其单纯形求解方法 (二二)线性规划解的性质线性规划解的性质 凸集和顶点凸集和顶点 凸集凸集：若连接n维点集S中的任意两点X(1)和X(2)之间的线段仍在S中，则S为凸集。 顶点顶点：若凸集S中的点X(0)不能成为S中任何线段的内点，则称X(0)为S的顶点或极点。

17、 线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划解的性质线性规划解的性质 线性规划问题的可行解集（可行域）为凸集。可行解集S中的点X是顶点的充要条件是基本可行解。若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。 因此线性规划的最优解只需从其可行解集的有限个顶点中去寻找。线性规划及其单纯形求解方法线性规划及其单纯形求解方法四、线性规划问题的求解方法四、线性规划问题的求解方法单纯形法单纯形法 （一）单纯形表（一）单纯形表 根据以上讨论，令 则基变量 ，非基变量 ，则有： 变形得：,21nmmpppN,NBA TmBxxxx,21TnmmNxxxx,21bNXBXNBNB

18、NXBbBX11线性规划及其单纯形求解方法线性规划及其单纯形求解方法v相应地，记：v目标函数记为：v则对应于基B的基本解为：,21mBcccC,21nmmNcccC,NBCCC NBNBXNBCCbBCZ)(11bBXB10NX线性规划及其单纯形求解方法线性规划及其单纯形求解方法最优解的判定：当 时， 则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。于 与 等价，故可得最优解的判定定理最优解的判定定理： 对于基B ，若 ，且 则对应于基B 的基本解为最优解， B为最优基。01NBCCBN01NBCCBN01ABCCB01bB01ABCCB线性规划及其单纯形求解方法线

19、性规划及其单纯形求解方法bBbBCXZABABCCBB111101在上式中，称系数矩阵 为对应于基B的单纯形表，记为T(B).ABbBABCCbBCBB111101ABbBABCCbBCBB1111或对目标函数与约束不等式运用矩阵变形得：线性规划及其单纯形求解方法线性规划及其单纯形求解方法001bbBCB,002011nBbbbABCCTmbbbbB,020101如果记：mnmmnnbbbbbbbbbAB2122221112111以及mnmmmnnnbbbbbbbbbbbbbbbbBT210222212011211100020100)(则线性规划及其单纯形求解方法线性规划及其单纯形求解方法(二

20、二) 单纯形法的计算步骤单纯形法的计算步骤 v第一步第一步，找出初始可行基，建立初始单纯形表。v第二步第二步，判别检验所有的检验系数 （1）如果所有的检验系数 ，则由最优性判定定理知，已获最优解，即此时的基本可行解就是最优解。 （2）若检验系数中，有些为正数，但其中某一正的检验系数所对应的列向量的各分量均非正，则线性规划问题无解。（3）若检验系数中，有些为正数，且它们所对应的列向量中有正的分量，则需要换基、进行迭代运算。), 2 , 1(0njbj), 2 , 1(00njbj线性规划及其单纯形求解方法线性规划及其单纯形求解方法第三步第三步，选主元。 在所有大于零的检验数中选取最大的一个b0s

21、，对应的非基变量为xs,对应的列向量为若则确定brs为主元项。 第四步第四步，在基B中调进Ps，换出Pjr，得到一个新的基第五步第五步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。第六步第六步，转入上述第二步。 Tmssssbbbp,21rsrisisibbbbb000min,1121mrrjjsjjjpPPPPPB线性规划及其单纯形求解方法线性规划及其单纯形求解方法例例1：用单纯形方法求解线性规划问题 2121212132max0, 092123xxZxxxxxx解解：首先引入松弛变量 ，把原问题化为标准形式： 43,xx21432142132132max0,

22、92123xxZxxxxxxxxxx线性规划及其单纯形求解方法线性规划及其单纯形求解方法第一步，确定初始单纯形表 如下：x1x2x3x4-z02300 x3121310 x492101第二步，判别。在初始单纯形表中b01=2, b02=3，所以B1不是最优基，进行换基迭代。第三步，选主元。 根据选主元法则，确定主元项 。第四步 ，换基，得一新基 。312b,422ppB 线性规划及其单纯形求解方法线性规划及其单纯形求解方法第五步，进行初等行变换， 得B2下的新单纯形表x1x2x3x4-z-1210-10 x241/311/30 x455/30-1/31第六步，因检验系数有正数b01=1，重复以

23、上步骤可得对应于 B3=p2,p3的单纯形表，检验各检验数可知得最优解X1=3,X2=3, X3=0, X4=0:目标函数最大值为 Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1 310-1/53/5线性规划及其单纯形求解方法线性规划及其单纯形求解方法产销平衡表与单位运价表产销平衡表与单位运价表 表上作业法表上作业法 产销不平衡的运输问题的求解方法产销不平衡的运输问题的求解方法线性规划及其单纯形求解方法线性规划及其单纯形求解方法一、产销平衡表与单位运价表一、产销平衡表与单位运价表 v运输问题还可用产销平衡表与单位运价表进行描述。v假设某种物资有m个生产地点

24、Ai（i=1，2，m），其产量（供应量）分别为ai（i=1，2，m），有n个销地Bj（j=1，2，n），其销量（需求量）分别为bj（j=1，2，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表4.3.1。线性规划及其单纯形求解方法线性规划及其单纯形求解方法销地产地产量销量n21表表4.3.1 产销平衡表与单位运价表产销平衡表与单位运价表mnmmnnccccccccc212222111211m21maaa21线性规划及其单纯形求解方法线性规划及其单纯形求解方法二、表上作业法二、表上作业法 v运输这一类特殊问题可用更加简便的求解方法表上作业法求解，

25、实质仍是单纯形法，步骤如下：v（一）（一）找出初始基可行解，即在产销平衡表上给出m+n-1个数字格。v1 确定初始可行基的方法确定初始可行基的方法：最小元素法最小元素法：从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。线性规划及其单纯形求解方法线性规划及其单纯形求解方法伏格尔法伏格尔法采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。（二）（二）求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。若已是最优解，则停止计算，否则转入下一步。线性规划及其单纯形求解方法线性规划及其单

26、纯形求解方法v计算非基变量（空格）的检验数 时为最优解。v求空格检验数的方法有：闭回路法：闭回路法：以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转900后，继续前进，直到回到起始空格为止。01ijBijPBCc线性规划及其单纯形求解方法线性规划及其单纯形求解方法闭回路如图（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为，m+n-1个数字格（基变量）对应的系数向量是一个基，任一空格（非基变量）对应的系数向量是这个基的线性组合。线性规划及其单纯形求解方法线性规划及其单纯形求解方法例1：假设某种物资共有三个产地，其日产量分别是：A1为7吨，

27、A2为4吨， A3为9吨；该种物质的四个销售地，其日销量分别： B1为3吨， B2为6吨， B3为5吨， B4为6吨；各产地到销售地的单位物资的运价如表4.3.2所示。在满足各销售点需要量的前提下，如何调运该种物资，才能使总运费达到最小？销地销地产地产地B1B2B3B4A1A2A3317119432101085线性规划及其单纯形求解方法线性规划及其单纯形求解方法解：首先列出这一问题的产销平衡表，见表4.3.5。 表表4.3.5 某物资运输的产销平衡表某物资运输的产销平衡表 销地销地产地产地B1B2B3B4产量产量A1A2A3749销量销量3656线性规划及其单纯形求解方法线性规划及其单纯形求解

28、方法用最小元素法求解用最小元素法求解第一步，从表4.3.4中找出最小运价为1，将A2 的产品供应 B1 。在表4.3.5中（ A2 B1 ）的交叉格处填上3，得表4.3.6。将表4.3.4中的B1 列运价划去，得表4.3.7。销地销地产地产地B1B2B3B4产量产量A1A2A33749销量销量3656表表4.3.6线性规划及其单纯形求解方法线性规划及其单纯形求解方法销地销地产地产地B1B2B3B4A1A2A3119432101085表表4.3.7第二步，在表4.3.7未划去的元素中再找出最小运价为2，确定A2多余的1吨物资供应B3 。得表4.3.8。将表4.3.7的行运价划去，得表4.3.9。

29、线性规划及其单纯形求解方法线性规划及其单纯形求解方法销地销地产地产地B1B2B3B4产量产量A1A2A331749销量销量3656表表4.3.8销地销地产地产地B1B2B3B4A1A2A3114310105表表4.3.9线性规划及其单纯形求解方法线性规划及其单纯形求解方法第三步 ，按照上述方法直到单位运价表上的所有元素被划去为止。最后在产销平衡表上得到一个调运方案，即初始基可行解，见表4.3.8。销地销地产地产地B1B2B3B4产量产量A1 A2A3341749销量销量3656表表4.3.10线性规划及其单纯形求解方法线性规划及其单纯形求解方法销地销地产地产地B1B2B3B4A1A2A3114

30、105销地销地产地产地B1B2B3B4产量产量A1 A2A33641749销量销量3656线性规划及其单纯形求解方法线性规划及其单纯形求解方法销地销地产地产地B1B2B3B4A1A2A3105销地销地产地产地B1B2B3B4产量产量A1 A2A336413749销量销量3656线性规划及其单纯形求解方法线性规划及其单纯形求解方法销地销地产地产地B1B2B3B4A1A2A310销地销地产地产地B1B2B3B4产量产量A1 A2A3364133749销量销量3656线性规划及其单纯形求解方法线性规划及其单纯形求解方法伏格尔法的步骤是：伏格尔法的步骤是：第一步：在表4.3.4中分别计算出各行、各列的

31、最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表4.3.11。销地销地产地产地B1B2B3B4行差额行差额 A1A2A3317119432101085011列差额列差额 2513表表4.3.11线性规划及其单纯形求解方法线性规划及其单纯形求解方法第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表4.3.11中，可确定A3的产品应首先供应B2，得表4.3.12。将单位运价表中的列的数字划去，得表4.3.13。线性规划及其单纯形求解方法线性规划及其单纯形求解方法表表4.3.12销地销地产地产地B1B2B3B4产量产量A1A2A36749销量销量3656销地产地B1B2B3B4A1A2A331732101085表表4.3.13