线性规划及其单纯形求解方法PPT学习教案

1、会计学1线性规划及其单纯形求解方法线性规划及其单纯形求解方法第1页/共42页第2页/共42页n运输问题运输问题 假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，m），第j 销地的需求量为bj(j=1, 2，n)，它们满足产销平衡条件 。 如果产地i到销地j的单位物资的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：minjjiba11第3页/共42页), 2 , 1;, 2 , 1(0), 2 , 1(), 2 , 1(11njmixmiaxnjbxijnjiijmijijminjijijxcz11min第4页/共42页第5页/共42页

2、), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjjxcZ1max第6页/共42页第7页/共42页), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjxZ1min第8页/共42页第9页/共42页 由此可以抽象出线性规划问题的数学模型，一般形式为： 在线性约束条件njijijmibxa1), 2 , 1(),( 以及非负约束条件 xj0（j=1，2，n）下，求一组未知变量xj (j=1，2， ，n)的值，使njjjxcZ1(min)max第10页/共42页 采用矩阵形式可描述为： 在约束条件 AX(，)b X0 下，求未知向量 ，使得Z=CXma

3、x(min) 其中,2121nTmcccCbbbbmnmmnnaaaaaaaaaA212222111211TnxxxX,21第11页/共42页mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111xj0（j = 1，2，n） 下，求一组未知变量xj（j = 1，2，n）的值，使njjjxcZ1max第12页/共42页其缩写形式为：在约束条件 njijijmibxa1), 2 , 1( x0（j = 1，2，n） 下，求一组未知变量（j = 1，2，n）的值，使得 常记为如下更为紧凑的形式 njjjxcZ1max), 2 , 1(0), 2 , 1

4、(max11njxmibxaxcZjnjijijnjjj或0XbAXCXZmax第13页/共42页第14页/共42页knknkkbxaxaxa)(2211kknnknkkbxxaxaxa)(2211n约束方程化为标准形式的方法约束方程化为标准形式的方法 若第k个约束方程为不等式，即 引入松弛变量 , K个方程改写为 则目标函数标准形式为0knxnjnjknjjjjxoxcxcZ11第15页/共42页第16页/共42页,21npppA), 2 , 1(,21njaaaPTmjjjj第17页/共42页 如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称 为基向

5、量，与基向量相对应的向量 为基变量，而其余的变量 为非基变量。 ,21212222111211mmmmmmmPPPaaaaaaaaaB), 2 , 1(mjPj), 2 , 1(mjxj), 2, 1(nmmjxi第18页/共42页 如果 是方程组 的解, 则 就是方程组 的一个解，它称之为对应于基B的基本解，简称基解。 满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。TmBxxxX,21bBXBTmxxxX0 , 0 , 0 ,21CXZ max第19页/共42页 线性规划问题的以上几个解的关系，可用下图来描述：第20页/共42页第21页/共42页n线性规划解的性

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

7、BCCbBCZ)(11bBXB10NX第24页/共42页n最优解的判定最优解的判定 当 时， 则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。 由于 与 等价，故可得。n最优解的判定定理最优解的判定定理 对于基B ，若 ，且 , 则对应于基B 的基本解为最优解， B为最优基。01NBCCBN01NBCCBN01ABCCB01bB01ABCCB第25页/共42页bBbBCXZABABCCBB111101在上式中，称系数矩阵 为对应于基B的单纯形表，记为T(B) 。ABbBABCCbBCBB111101ABbBABCCbBCBB1111或对目标函数与约束不等式运用矩阵变

8、形得第26页/共42页001bbBCB,002011nBbbbABCCTmbbbbB,020101如果记mnmmnnbbbbbbbbbAB2122221112111以及mnmmmnnnbbbbbbbbbbbbbbbbBT210222212011211100020100)(则第27页/共42页), 2 , 1(00njbj第28页/共42页 第第3 3步步，选主元。 在所有大于零的检验数中选取最大的一个b0s，对应的非基变量为xs，对应的列向量为若则确定brs为主元项。 第第4 4步步，在基B中调进Ps，换出Pjr，得到一个新的基 第第5 5步步，在单纯形表上进行初等行变换，使第s列向量变为单位

9、向量，又得一张新的单纯形表。 第第6 6步步，转入上述第2步。 Tmssssbbbp,21rsrisisibbbbb000min,1121mrrjjsjjjpPPPPPB第29页/共42页例例1：用单纯形方法求解线性规划问题 2121212132max0, 092123xxZxxxxxx解解：首先引入松弛变量 ，把原问题化为标准形式 43,xx21432142132132max0,92123xxZxxxxxxxxxx第30页/共42页 具体步骤如下： 第1步，确定初始单纯形表5.1.1。x1x2x3x4-z02300 x3121310 x492101 第2步，判别。在初始单纯形表中b01=2,

10、 b02=3，所以B1不是最优基，进行换基迭代。 第3步，选主元。 根据选主元法则，确定主元项 。 第4步 ，换基，得一新基 。312b,422ppB 表5.1.1第31页/共42页 第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表

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

12、.1.6 3种作物的总产量（单位:kg） 11x12x13x21x22x23x31x32x33x I等耕地II等耕地III等耕地水稻大豆玉米131211000 x9500 x900 x0112322210 x006800 x6000 x8333231000 x10000 x12000 x14第36页/共42页200 xxx300 xxx100 xxx332313322212312111000350000 x10000 x12000 x140000310 x006800 x6000 x8000190000 x9500 x9000 x113332312322211312111,2,3)1,2,3;

13、(0jixij第37页/共42页 （1）追求最大总产量的目标函数为 调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表5.1.7所示）。在该方案下，最优值，即最大总产量为6 892 200 kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。 333231232221131211000100001200014 +000680060008+ 0009500900011=max xxxxxxxxxZ第38页/共42页表5.1.7 追求总产量最大的计划方案（单位：hm2） I等耕地II等耕地III等耕地水稻0021.111 1 大豆0021.666 7 玉米100300157.222 2 第39页/共42页 (2) 追求最大总产值的目标函数为 进行求解运算，可以得到一个最优解（如表5.1.8所示）。在该方案下，最优值，即最大总产值为6 830 500元。从表中可以看出，如果以追求总产值最大为种植计划目标，那么，水稻的种植面积在I、II、III等耕地上都占绝对优势。 33323123222113121133323123222113121100086009