线性规划及其单纯形求解方法课件.ppt

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

2、的两类问题：某项任务确定后，如何统筹安排，以最少的人力、物力和财力去完成该项任务；面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。以下为一些实例。一、线性规划的数学模型一、线性规划的数学模型 n运输问题运输问题 假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，m），第j 销地的需求量为bj(j=1,2，n)，它们满足产销平衡条件 。如果产地i到销地j的单位物资的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：minjjiba11 设xij表示由产地i供给销地j 的物资数量，则上述问题可以表

3、述为：求一组实值变量xij(i=1，2，m；j=1，2，n)，使其满足 而且使),2,1;,2,1(0),2,1(),2,1(11njmixmiaxnjbxijnjiijmijijminjijijxcz11minn资源利用问题资源利用问题 假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，m)。这m种资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，m；j=1,2,n)，第j种产品的单价为cj(j=1，2，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大?设第j种产品的生产数量为xj(j

4、=1，2，n)，则上述资源问题就是：求一组实数变量xj(j=1，2，n)，使其满足),2,1(0),2,1(1njxmibxajnjijijnjjjxcZ1maxn合理下料问题合理下料问题 用某种原材料切割零件A1，A2,Am的毛坯，现已设计出在一块原材料上有B1，B2，Bn种不同的下料方式，如用Bj下料方式可得Ai种零件aij个，设Ai种零件的需要量为bi个。试问应该怎样组织下料活动，才能使得既满足需要，又节约原材料？设采用Bj方式下料的原材料数为xj，则上述问题可表示为：求一组整数变量xj(j=1，2，n)，使得),2,1(0),2,1(1njxmibxajnjijijnjjxZ1min

5、（二）线性规划的数学模型（二）线性规划的数学模型 以上例子表明，线性规划问题具有以下特征：每一个问题都用一组未知变量（x1，x2，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。每一个问题的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。每一个问题的目标函数和约束条件都是线性的。由此可以抽象出线性规划问题的数学模型，一般形式为：在线性约束条件njijijmibxa1),2,1(),(以及非负约束条件 xj0（j=1，2，n）下，求一组未知变量xj(j=1，

6、2，n)的值，使njjjxcZ1(min)max 采用矩阵形式可描述为：在约束条件 AX(，)b X0 下，求未知向量 ，使得Z=CXmax(min)其中,2121nTmcccCbbbbmnmmnnaaaaaaaaaA212222111211TnxxxX,21 二、线性规划的标准形式及方法二、线性规划的标准形式及方法 (一）线性规划的标准形式一）线性规划的标准形式 在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式，即在约束条件mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111xj0（j=1，2，n）下，求一组未知变量xj（j=1，2

7、，n）的值，使njjjxcZ1max其缩写形式为：在约束条件 njijijmibxa1),2,1(x0（j=1，2，n）下，求一组未知变量（j=1，2，n）的值，使得 常记为如下更为紧凑的形式 njjjxcZ1max),2,1(0),2,1(max11njxmibxaxcZjnjijijnjjj或0XbAXCXZmax（二）化为标准形式的方法（二）化为标准形式的方法 具体的线性规划问题，需要对目标函数或约束条件进行转换，化为标准形式。n目标函数化为标准形式的方法目标函数化为标准形式的方法 如果其线性规划问题的目标函数为 min Z=CX 显然有 minZ=max(-Z)=max Z 则目标函数

8、的标准形式为 max Z=-CXknknkkbxaxaxa)(2211kknnknkkbxxaxaxa)(2211n约束方程化为标准形式的方法约束方程化为标准形式的方法 若第k个约束方程为不等式，即 引入松弛变量 ,K个方程改写为 则目标函数标准形式为0knxnjnjknjjjjxoxcxcZ11三、线性规划的解及其性质三、线性规划的解及其性质 (一一)线性规划的解线性规划的解 n可行解与最优解可行解与最优解 满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。n基本解与基本可行解基本解与基本可行解 在线性规划问

9、题中，将约束方程组的mn阶矩阵A写成由n个列向量组成的分块矩阵,21npppA),2,1(,21njaaaPTmjjjj 如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称 为基向量，与基向量相对应的向量 为基变量，而其余的变量 为非基变量。,21212222111211mmmmmmmPPPaaaaaaaaaB),2,1(mjPj),2,1(mjxj),2,1(nmmjxi 如果 是方程组 的解,则 就是方程组 的一个解，它称之为对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。TmBxxxX,21b

10、BXBTmxxxX0,0,0,21CXZ max 线性规划问题的以上几个解的关系，可用下图来描述：(二二)线性规划解的性质线性规划解的性质 n凸集和顶点凸集和顶点 凸集凸集：若连接n维点集S中的任意两点X(1)和X(2)之间的线段仍在S中，则S为凸集。顶点顶点：若凸集S中的点X(0)不能成为S中任何线段的内点，则称X(0)为S的顶点或极点。n线性规划解的性质线性规划解的性质 线性规划问题的可行解集（可行域）为凸集。可行解集S中的点X是顶点的充要条件是基本可行解。若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。因此线性规划的最优解只需从其可行解集的有限个顶点中去寻找。四、线性规划问

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

12、基B 的基本解为最优解，B为最优基。01NBCCBN01NBCCBN01ABCCB01bB01ABCCBbBbBCXZABABCCBB111101在上式中，称系数矩阵 为对应于基B的单纯形表，记为T(B)。ABbBABCCbBCBB111101ABbBABCCbBCBB1111或对目标函数与约束不等式运用矩阵变形得001bbBCB,002011nBbbbABCCTmbbbbB,020101如果记mnmmnnbbbbbbbbbAB2122221112111以及mnmmmnnnbbbbbbbbbbbbbbbbBT210222212011211100020100)(则(二二)单纯形法的计算步骤单纯形

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

14、基 第第5 5步步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。第第6 6步步，转入上述第2步。Tmssssbbbp,21rsrisisibbbbb000min,1121mrrjjsjjjpPPPPPB例例1：用单纯形方法求解线性规划问题 2121212132max0,092123xxZxxxxxx解解：首先引入松弛变量 ，把原问题化为标准形式 43,xx21432142132132max0,92123xxZxxxxxxxxxx 具体步骤如下：第1步，确定初始单纯形表5.1.1。x1x2x3x4-z02300 x3121310 x492101 第2步，判别。在初

15、始单纯形表中b01=2,b02=3，所以B1不是最优基，进行换基迭代。第3步，选主元。根据选主元法则，确定主元项 。第4步，换基，得一新基 。312b,422ppB 表5.1.1 第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。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1 310-1/53/5表5.1.2

16、表5.1.3 五、应用实例五、应用实例:农场种植计划模型农场种植计划模型 某农场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）如何制订种植计划，才能使总产值最大？表5.1.4 不同等级耕地种植不同作物的单产(单位:kg/hm2)I等耕地II

17、等耕地III等耕地水稻11 0009 5009 000大豆8 0006 8006 000玉米14 00012 00010 000表5.1.4 对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。根据题意，决策变量设置如表5.1.5所示,表中Xij表示在第j等级的耕地上种植第i种作物的面积。3种作物的产量可以用表5.1.6表示。作物种类总产量水稻大豆玉米表5.1.5 作物计划种植面积（单位:hm2)表5.1.6 3种作物的总产量（单位:kg）11x12x13x21x22x23x31x32x33x I等耕地II等耕地III等耕地水稻大豆玉米131211000 x9500 x900 x011

18、2322210 x006800 x6000 x8333231000 x10000 x12000 x14根据题意，约束方程如下,耕地面积约束最低收获量约束 非负约束 200 xxx300 xxx100 xxx332313322212312111000350000 x10000 x12000 x140000310 x006800 x6000 x8000190000 x9500 x9000 x113332312322211312111,2,3)1,2,3;(0jixij （1）追求最大总产量的目标函数为 调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表

19、5.1.7所示）。在该方案下，最优值，即最大总产量为6 892 200 kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。333231232221131211000100001200014+000680060008+0009500900011=max xxxxxxxxxZ表5.1.7 追求总产量最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻0021.111 1 大豆0021.666 7 玉米100300157.222 2 (2)追求最大总产值的目标函数为 进行求解运算，可以得到一个最优解（如表5.1.8所示）

20、。在该方案下，最优值，即最大总产值为6 830 500元。从表中可以看出，如果以追求总产值最大为种植计划目标，那么，水稻的种植面积在I、II、III等耕地上都占绝对优势。333231232221131211333231232221131211000860092001100092001000012800104001120013)000100001200014(0.80+)00068006000(81.50+)00095009000(111.20=max xxxxxxxxxxxxxxxxxxZ表5.1.8 追求总产值最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻58.75 300 200 大豆16.25 00 玉米25 00