第八章地理系统的线性规划

1、第八章 地理系统的线性规划 (Liner Programming，LP) 线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它在实际应用中日益广泛与深入,已经被广泛地应用到工业、农业、商业与交通运输规划，工程技术的优化设计，以及企业管理等各个领域。 在地理学领域，线性规划，作为传统的计量地理学方法之一，是解决有关规划、决策和系统优化问题的重要手段。线性规划的数学模型线性规划的标准形式及方法线性规划的解及其性质线性规划问题的求解方法图解法线性规划问题的求解方法单纯形法应用实例: 农场种植计划模型 （一）线性规划模型之实例（一）线性规划模型之实例 线性规划研究的两类问题： 某项任务确定后，

2、如何统筹安排，以最少的人力、物力和财力去完成该项任务； 面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。 以下为一些实例。一、线性规划的数学模型一、线性规划的数学模型 合理运输问题合理运输问题设有两个煤矿A1，A2，其最少产煤量分别为23万吨和27万吨，他们的产煤量应充分供保证应B1,B2,B3三个城市的需求，这三个城市的需煤量最少分别为17万吨、18万吨和15万吨，而从两个煤矿到各个城市的运费见运费表。问应如何合理调运才能使总运费最省？ 城市煤矿B1B2B3发量A1X11X12X1323A2X21X22X2327收量17181550 城市煤矿B

3、1B2B3A1506070A260110160运煤量表 运费表n1. 运输问题运输问题 假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，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, 1(),2, 1(11njmixmiaxnjbx

4、ijnjiijmijijminjijijxcz11min资源合理利用问题某工厂以铜、电力和劳动日为主要原料生产A、B，现有资源数、生产每单位产品所需要原料数以及每单位产品可得利润数如下表所示。单位产品所需原单位产品所需原料料A(A(公斤公斤) )B B （公斤）（公斤）现有现有资资源源铜（吨）铜（吨）9 94 4360360电力（千瓦）电力（千瓦）4 45 5200200劳动日（个）劳动日（个）3 31010300300单位利润（千瓦）单位利润（千瓦） 7 71212n2. 2. 资源利用问题资源利用问题 假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，m)。这m种

5、资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，m；j=1,2, ,n)，第j种产品的单价为cj(j=1，2， ，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大? 设第j种产品的生产数量为xj(j=1，2，n)，则上述资源问题就是： 求一组实数变量xj(j=1，2，n)，使其满足), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjjxcZ1max问题问题1. 如何下料最节省如何下料最节省 ? 钢管下料钢管下料 原料钢管原料钢管: :每根每根19米米 4米米50根根 6米米20根根 8米

6、米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合

7、理切割模式合理切割模式2. 所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数 6米钢管根数米钢管根数 8米钢管根数米钢管根数 余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1. 原料钢管剩余总余量最小原料钢管剩余总余量最小xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 约束约束满足需求满足需求 决策变量决策变量 目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx203265

8、42xxxx152753xxx模式模式4米根数米根数6米根数米根数8米根数米根数余料余料14003231013201341203511116030170023需求需求502015整数约束：整数约束： xi 为整数为整数目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 最优解：最优解：x2=12, x5=15, 其余为其余为0；最优值：最优值：27xi 为整数为整数钢管下料钢管下料( (问题问题1) 1) 以上两

9、个模型均是一般以上两个模型均是一般整数线性规划整数线性规划 76543212xxxxxxxZMin目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条件不变约束条件不变 5023454321xxxxx20326542xxxx152753xxxxi 为整数当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 n合理下料问题合理下料问题 用某种原材料切割零件A1，A2, ,Am的毛坯，现已设计出在一块原材料上有B1，B2，Bn种不同的下料方式，如用Bj下料方式可得Ai种零件aij个，设Ai种零件的需要量为bi个。试问应该怎样组织下料活动，才能使得既满足需

10、要，又节约原材料？ 设采用Bj方式下料的原材料数为xj，则上述问题可表示为： 求一组整数变量xj(j=1，2，n)，使得), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjxZ1min （二）线性规划的数学模型（二）线性规划的数学模型 以上例子表明，线性规划问题具有以下特征： 每一个问题都用一组未知变量（x1，x2，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。 每一个问题的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。 每一个

11、问题的目标函数和约束条件都是线性的。 由此可以抽象出线性规划问题的数学模型，一般形式为： 在线性约束条件njijijmibxa1), 2 , 1(),( 以及非负约束条件 xj0（j=1，2，n）下，求一组未知变量xj (j=1，2， ，n)的值，使njjjxcZ1(min)max 采用矩阵形式可描述为： 在约束条件 AX(，)b X0 下，求未知向量 ，使得Z=CXmax(min) 其中,2121nTmcccCbbbbmnmmnnaaaaaaaaaA212222111211TnxxxX,21 二、线性规划的标准形式及方法二、线性规划的标准形式及方法 (一）线性规划的标准形式一）线性规划的标准

12、形式 在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式，即在约束条件mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111xj0（j = 1，2，n） 下，求一组未知变量xj（j = 1，2，n）的值，使njjjxcZ1max其缩写形式为：在约束条件 njijijmibxa1), 2 , 1( x0（j = 1，2，n） 下，求一组未知变量（j = 1，2，n）的值，使得 常记为如下更为紧凑的形式 njjjxcZ1max), 2 , 1(0), 2 , 1(max11njxmibxaxcZjnjijijnjjj或0XbAXCXZmax（

13、二）化为标准形式的方法（二）化为标准形式的方法 具体的线性规划问题，需要对目标函数或约束条件进行转换，化为标准形式。目标函数化为标准形式的方法目标函数化为标准形式的方法 如果其线性规划问题的目标函数为 min Z = CX 显然有 minZ = max(-Z)=max Z 则目标函数的标准形式为 max Z= -CXknknkkbxaxaxa)(2211kknnknkkbxxaxaxa)(2211n约束方程化为标准形式的方法约束方程化为标准形式的方法 若第k个约束方程为不等式，即 引入松弛变量 , K个方程改写为 则目标函数标准形式为0knxnjnjknjjjjxoxcxcZ11三、线性规划的

14、解及其性质三、线性规划的解及其性质 (一一)线性规划的解线性规划的解 可行解与最优解可行解与最优解 满足约束条件（即满足线性约束和非负约束）的一组变量为可行解可行解。所有可行解组成的集合称为可行域。 使目标函数最大或最小化的可行解称为最优使目标函数最大或最小化的可行解称为最优解解。 基本解与基本可行解基本解与基本可行解 在线性规划问题中，将约束方程组的mn阶矩阵A写成由n个列向量组成的分块矩阵,21npppA), 2 , 1(,21njaaaPTmjjjj 如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称 为基向量基向量，与基向量相对应的向量 为基变量基

15、变量，而其余的变量 为非基变量非基变量。 ,21212222111211mmmmmmmPPPaaaaaaaaaB), 2 , 1(mjPj), 2 , 1(mjxj), 2, 1(nmmjxi 如果 是方程组 的解, 则 就是方程组 的一个解，它称之为对应于基B的基本解基本解，简称基解。 满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。TmBxxxX,21bBXBTmxxxX0 , 0 , 0 ,21CXZ max 线性规划问题的以上几个解的关系，可用下图来描述： (二二)线性规划解的性质线性规划解的性质 凸集和顶点凸集和顶点 凸集凸集：若连接n维点集S中的任意两点

16、X(1)和X(2)之间的线段仍在S中，则S为凸集。 顶点顶点：若凸集S中的点X(0)不能成为S中任何线段的内点，则称X(0)为S的顶点或极点。 n线性规划解的性质线性规划解的性质 线性规划问题的可行解集（可行域）为凸集。 可行解集S中的点X是顶点的充要条件是基本可行解。 若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到顶点上达到。 因此线性规划的最优解只需从其可行解集的有限个顶点中去寻找。四、线性规划问题的求解方法四、线性规划问题的求解方法图解法图解法 线性规划的图解法(解的几何表示)：对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解

17、。一般的一般的 2 2 维线性规划问题维线性规划问题Max ( Min ) z = c1x1 + c2x2 s.t. a11x1+a12x2 ( =, )b1 a21x1+a22x2 ( =, )b2 . . . am1x1+am2x2 ( =, )bm x1 ，x2 0 图解法求解线性规划问题的步骤如下： (1)建立直角坐标系： 分别取决策变量x1 ,x2 为坐标向量。 图解法求解图解法求解2 维维线性规划线性规划（2）绘制可行域： 对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行

18、集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。图解法求解图解法求解2 维维线性规划线性规划 （3）绘制目标函数等值线，并移动求解： 目标函数随着取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）； 然后，确定该直线平移使函数值增加的方向(直线的法方向)； 最后，依照目标的要求平移此直线。图解法求解图解法求解2 维维线性规划线性规划(4) 结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，

19、此时称无有限最优解。图解法求解图解法求解2 维维线性规划线性规划 例:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500 问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。 解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据前面分析，可以建立如下的线性规划模型： Max z = 1500 x1 + 2500 x2 s.t

20、. 3x1+ 2x2 65 (A) 2x1+ x2 40 (B) 3x2 75 (C) x1 , x2 0 (D, E)按照图解法的步骤： （1）以决策变量x1 ，x2 为坐标向量作平面直角坐标系；（2 2）对每个约束（包括非负约）对每个约束（包括非负约束）条件作出直线（束）条件作出直线（A A、B B、C C、D D、E E），并通过判断确定不等），并通过判断确定不等式所决定的半平面。式所决定的半平面。 各约束半平面交出来的区各约束半平面交出来的区域即可行集或可行域如下图阴域即可行集或可行域如下图阴影所示。影所示。第2步图示(1) 分别作出各约束半平面2x1+ x2 40 3x2 75x1

21、0X2 03x1+ 2x2 65 第2步图示(2) 各约束半平面的交可行域（3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再 增 加 的 位 置 ， 得 到 交 点 (5,25)T ，即最优解。此目标函数的值为70000。w第3步图示 作出目标函数等值线函数值增大第3步图示(2) 求出最优解根据上面的过程根据上面的过程 我们得到这个线性规划的 最优解 x1=5、x2=25， 最优值 z = 70000即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为

22、70000元。线性规划的解有如下几种情况： 1、存在有限最优解： 唯一最优解；无穷多个最优解 2、无有限最优解（无界解） 3、无可行解（可行域空） 例：在线性规划模型中，如果目标函数变为： Max z = 1500 x1 + 1000 x2 那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点 (5,25)T到点 (15,10)T 线段上的所有点，最优值为32500。如下图所示： 无穷多解的情况(15, 10)T 例：在线性规划模型中,如果约束条件（A）、（C）变为： 3 x1 + 2 x2 65 (A） 3 x2 75 (C）并且去掉（D、E）的非负限制。那么，可

23、行域成为一个上无界的区域。这时，没有有限最优解，如下图所示： 无有限解的情况 例：在线性规划模型中，如果增加约束条件（F）为： x1 + x2 40 （F） 那么，可行域成为空的区域。这时， 没有可行解，显然线性规划问题无 解。如下图所示： 无可行解的情况 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为封闭的无界区域 (c)有唯一的最优解； (d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。 3.

24、可行域为空集 (f)没有可行解，原问题无最优解 五、线性规划问题的求解方法五、线性规划问题的求解方法单纯形法单纯形法 （一）单纯形表（一）单纯形表 根据以上讨论，令 则 基变量 ，非基变量 ，则有 变形得,21nmmpppN,NBA TmBxxxx,21TnmmNxxxx,21bNXBXNBNBNXBbBX11相应地，记目标函数记为则对应于基B的基本解为,21mBcccC,21nmmNcccC,NBCCC NBNBXNBCCbBCZ)(11bBXB10NXn最优解的判定最优解的判定 当 时， 则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。 由于 与 等价，故可得。

25、n最优解的判定定理最优解的判定定理 对于基B ，若 ，且 , 则对应于基B 的基本解为最优解， B为最优基。01NBCCBN01NBCCBN01ABCCB01bB01ABCCBbBbBCXZABABCCBB111101在上式中，称系数矩阵 为对应于基B的单纯形表，记为T(B) 。ABbBABCCbBCBB111101ABbBABCCbBCBB1111或对目标函数与约束不等式运用矩阵变形得001bbBCB,002011nBbbbABCCTmbbbbB,020101如果记mnmmnnbbbbbbbbbAB2122221112111以及mnmmmnnnbbbbbbbbbbbbbbbbBT210222

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

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

28、单纯形表。x1x2x3x4-z02300 x3121310 x492101 第2步，判别。在初始单纯形表中b01=2, b02=3，所以B1不是最优基，进行换基迭代。 第3步，选主元。 根据选主元法则，确定主元项 。 第4步 ，换基，得一新基 。312b,422ppB 第5步，进行初等行变换， 得B2下的新单纯形表x1x2x3x4-z-1210-10 x241/311/30 x455/30-1/31 第6步，因检验系数有正数b01=1，重复以上步骤可得对应于 B3=p2,p3的单纯形表，检验各检验数可知得最优解X1=3,X2=3, X3=0, X4=0:目标函数最大值为 Z=15。x1x2x3

29、x4-z-1500-4/5-3/5x23012/5-1/5x1 310-1/53/5 六、应用实例六、应用实例: 农场种植计划模农场种植计划模型型 某农场I、II、III等耕地的面积分别为100 hm2、300 hm2和200 hm2，计划种植水稻、大豆和玉米，要求3种作物的最低收获量分别为190 000 kg、130 000 kg和350 000 kg。I、II、III等耕地种植3种作物的单产如表5.1.4所示。若3种作物的售价分别为水稻1.20元/kg，大豆1.50元/ kg，玉米0.80元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（2）如何制订种植计划，才能使总产值最大？表 不同等级耕地种植不同作物的单产(单位:kg / hm2) I等耕地II等耕地III等耕地水稻11 0009 5009 000大豆8 0006 8006 000玉米14 00012 00010 000表5.1.4 对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。 根据题意，决策变量设置如表所示, 表中Xij表示在第j等级的耕地上种植第i种作物的面积。 3种作物的产量可以用表表示。 作物种类总产量水稻大豆玉米表 作物计划种植面积（单位:hm2) 表 3种作物的总产量（单位:kg