2022年第二章运筹学线性规划 .pdf

《2022年第二章运筹学线性规划 .pdf》由会员分享，可在线阅读，更多相关《2022年第二章运筹学线性规划 .pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章线性规划主要内容： 1、线性规划问题及数学模型2、线性规划问题的解及其性质3、图解法4、单纯形法5、大 M 法和两阶段法重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。要求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握其求解技巧；培养解决实际问题的能力。1 线性规划的数学模型及解的性质一、数学模型（一般形式）例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？造价（元 /m2） 钢材（ kg/m2） 水源（ kg/m

2、2） 砖(块 /m2) 人工（工日 /m2）砖混结构大板结构大模结构资源限量105 137 122 11000 万元12 30 25 2000 万千克110 190 180 15000 万块210 14700 万块4.5 3.0 3.5 400 万工日解：设三种体系的建筑面积依次为1x,2x,3x万平方米，则目标函数为321maxxxxz约束条件为3 ,2, 104005.335.414700210150001801901102000253012110001221371053211321321321jxxxxxxxxxxxxxxj例 2 某工厂要安排生产甲、乙两种产品。已知：煤耗（ T/T ）

3、电耗（ kwh/T ）油耗（ T/T ）单价（万元 /T）甲产品乙产品资源限量9 4 360T 4 5 200kwh 3 10 300T 7 12 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 问：如何安排两种产品的生产数量，才能使总产值最高？解：设21,xx分别为甲、乙两种产品的生产量：则目标函数为21127maxxxz约束条件为2,1,03001032005436049112121jxxxxxxxj从以上两例可以看出，它

4、们都属于一类优化问题。它们的共同特征：每一个问题都有一组决策变量（nxxx21,）表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量的取值是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为：目标函数nnxcxcxcz2211max(min)约束条件njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn, 2, 1, 0,22112222212111212111可行

5、解 ：满足约束条件的一组决策变量，称为可行解。最优解 ：使目标函数取得最大（小）值的可行解，称为最优解。最优值 ：目标函数的最大（小）值，称为最优值。二、标准型（一）问题的标准形式：nnxcxcxcz2211ma xnjxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn,2, 1,022112222212111212111名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 第二章线性规划第 5 页其中nmmibi,

6、2, 10注意：任何一个一般型都可转化为一个标准型。（二）标准型的表示方法：1、和式形式：njjjxcz1maxnjxmibxajnjijij, 2, 10, 2, 112、矩阵形式：CXzmax0XbAX其中ncccC,21- 价格系数向量mbbbb21- 资源向量（限定系数向量）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - mnmmnnaaaaaaaaaA,212222111211- 约束条件系数矩阵TnxxxX,21-

7、 决策变量3、向量形式：nnxcxcxcz2211max02211jnnxbPxPxPx其中jnjjjaaaP,2,1为约束条件系数矩阵A 的第 j 列。（三）一般型化为标准型的方法1、CXzmin引进新的目标函数ZZ, 则可化为CXZmax2、不等式约束ininiibxaxaa221名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - 第二章线性规划第 7 页引进新的非负决策变量, 使得1nxinniniibxxaxaxa1221

8、11nx称为松弛变量，在目标函数中，其价格系数为0。ininiibxaxaxa2211引进新的非负决策变量1nx,使得inniniibxxaxaxa122111nx称为剩余变量，在目标函数中，其价格系数为0。3、若0ib，即02211ininiibxaxaxa可变为02211ininiibxaxaxa4、若某个变量jx无非负限制，称为自由变量。令00jjjjjxxxxx例 3 将下列问题化为标准型21127maxxxz0,0300103200543604921212121xxxxxxxx解：标准型为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

9、 - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - 54321000127maxxxxxxz5, 4, 3,2, 103001032005436049521421321jxxxxxxxxxxj例 4 将下列问题化为标准型32173minxxxz无约束3213213213210,64542732xxxxxxxxxxxx解：令zz，标准型为：543210073maxxxxxxz无约束35421321532143210,64542732xxxxxxxxxxxxxxxx名师资料总结 - - -精品资料欢迎下载 - - - - - -

10、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - 第二章线性规划第 9 页令333xxx则标准型为：54332100773xzmaxxxxxx三、线性规划问题的解标准型CXzmax0XbAX,21212222111211nnmmnmmnnPPPaaaaaaaaaA记nPPP21秩:nmmArankimiiPPP,21imiiPPPB,211、基阵 ：若列向量是线性无关的，则称为LP 问题的一个基阵。基矩阵中每个列向量称为基向量。0,644542733254332131215332143321

11、xxxxxxxxxxxxxxxxxxxx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 22 页 - - - - - - - - - 由非基向量组成的矩阵称为非基矩阵，记为mnmN例如：531001030105400149A取100010001,5431PPPB线性无关，则10354491N003104019,4312PPPB线性无关，则11005042N2、基变量 ：基矩阵中各列向量对应的变量称为基变量，记为TimiiBxxxX,21。如5431,PPPB, 则基变量为

12、543,xxx。对应于非基向量的变量称为非基变量，记为TinminxxX,)1(3、基本解 ：设基矩阵为m21P, PPB，则非基矩阵nmPPN,1NBANBXXX那么，约束方程bXXNBNB即bNXBXNB- 有无穷解令0NX则bBXbBXBB1那么，约束方程组的解01bBX，将其称为LP问题的基本解。注意： 基本解不一定是可行解，若01bB,则称01bBX为LP问题的基本可行解，对应于基本可行解的基矩阵，称为可行基。4、最优解 ：对应于某一可行基，使目标函数获得最优值的基本可行解，称为最优解。最优解所对应的基矩阵称为最优基。举例说明：54321000127maxxxxxxz名师资料总结 -

13、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - - - - - - - - - 第二章线性规划第 11 页0,300103200543604954321521421321xxxxxxxxxxxxxx约束矩阵1001030105400149A若取基矩阵100010001,5431PPPB则非基矩阵10354491N基变量5431xxxXB,非基变量211xxXN30020036011bIbbB基本解为TX300,200,360,0,0是基本可行解名师资料总结 - - -精品资

14、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - 若取基矩阵1030540491,2132PPPB则1001002NTBxxxX213,2542xxXN24208412bBTX0,0,84,24,20- 基本可行解注意： 基本可行解与可行域的顶点坐标是一一对应的。2 图解法 - 主要解决二维线性规划问题一、按约束条件，绘出解的可行域图形21127maxxxz0,300103200543604921212121xxxxxxxx名师资料总结 - - -精品资料欢

15、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - 第二章线性规划第 13 页0 2 x1 x24 可行域：可行解的全体称为可行域。将等值线1212712Zxx沿法线方向向上平移至（20，24）点时截距最大，那么最优解为（20，24）T。二、解的情况最优解有以下几种情况：（1）有唯一的最优解。（2）有多个最优解。如上例中，若2154maxxxz，就有无穷多解。（3）有无界解：若有可行解，但无有限最优解，则称其为有无界解(这种情况在约束条件考虑不周全时出现)。如：

16、21ma xxxz0, 0242212121xxxxxx(4)无可行解（约束条件有矛盾）30010321xx(20,24) 3604921xx2005421xx0 40 50 100 x1 90 40 x2 2221xx121xx0 x1 x2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 如：212maxxxz0,221212121xxxxxx结论：约束集合一定是凸条边形（二维）；若有最优解，则一定可在多边形顶点获得。3

17、 单纯形法单纯形法的基本思路是：根据问题的标准，从可行域中某个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点） ；并且使目标函数达到最大值时，问题就得到了最优解。即初始顶点0X(可行域一顶点)寻找较好的顶点1X寻找更好的顶点2X)(最优解X0Z1Z2XZ一、单纯形法的求解步骤（1）寻找初始可行基0B,并计算初始基本可行解；010000bBXXXNB（2）检验基本可行解是否最优；（3）寻找更好的可得基；（4）重复（ 2） ， （3） 。1、初始可行基的确定i)若 A 中含有m阶单位矩阵I,则取IB0。此时，0100bbBXB0B是可行基ii) 若A中不含有m 阶单位矩阵，就采用人造基的

18、方法。即增加人工变量把原问题化为含有I的等价问题。（下一节重点讲）例：0203258332132121xxxxxxxx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - 第二章线性规划第 15 页因为系数数阵A 中不含有单位矩阵，需增加人工变量54,xx化为5, 2, 1020325835321421jxxxxxxxxj则1032501013A1001,540PPB注意： 松驰变量、剩余变量的价值系数取为0，而人工变量的价值系数

19、取值为大M。2、检验基本可行解01bBX对应的目标函数值01bBCCXZbBCbBCCBNB110非基变量价值系数基变量价值系数对任意可行解NBXXX变化bAX为bXXNBNB即bNXBXNBNBNBNXBbBXNXbBX11将其代入目标函数得：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - NNBBNBNBXCXCXXCCCXZNNNBXCNXBbBC11NBNBXNBCCbBC110NX当01NBCCBN时，Z的最大值是

20、bBCB1即01bBX为最优解。这里，我们称每个jBjjPBCc1为检验数。当IB时，基本可行解0bX检验数miijijjBjjacCPBCc11第i个基变量的价格系数第j个非基变量的价格系数如果0bX为最优解，则最优值为bCXB*判断定理 ： （对标准型maxZ 来讲）（1）若所有0j，则01bBX为最优解。（2）若所有0j,且有某个0k，则 LP 问题有无穷多个最优解。（3）若有某个0k，则01bBX不是最优解。（4）当IB时，若有一个0k，且对一切mi, 2, 1都有0ika,则有无界解 (或无最优解 )。3、基变换 ：确定新的基矩阵的过程名师资料总结 - - -精品资料欢迎下载 - -

21、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - 第二章线性规划第 17 页（1）换入变量的确定选择0j中的最大者所对应的变量kx作为换入变量，即kjj0max（2）换出变量的确定：用最小比值规则（规则）设lklikikiPBbBPBPBbB111110min则取lx为换出变量当IB时，lklikikiabaab0min则取lx为换出变量，lka称为主元素（3）新基矩阵的确定knllxxxxxx1121mkmnmlmlmmknllknllaaaaaaaaaaaaaaaaaa

22、B112122121222211111111211如：54321000127maxxxxxxz名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - 5, 2, 1, 03001032005436049521421321jxxxxxxxxxxj解：1001030105400149A取初始基矩阵100010001,5430PPPB那么TBxxxX543,0TNxxX21,0基可行解TbbBX300,200,360, 0, 0001检验

23、数：miijijjacc170731521411311acacacc1201232522412322acacacc0,21X不是最优解，换入变量为122x名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 22 页 - - - - - - - - - 第二章线性规划第 19 页lklikikikabaab0min3231030010300,5200,4360minab换出变量为5x（基变量中的第3 个变量），主元素为32a增广矩阵变换：3001001032000105436

24、000149301.00013. 02000105436000149103行除第243301.00013.0505.01005.22404.00108.7xxx新的基矩阵2431,100010001PPPB新基可行解TX0 ,50,240,30,0名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 22 页 - - - - - - - - - 检验数：31221411311acacacc4.33. 012735225415355acacacc2.11.0120X不是最优解。

25、二、单纯形表： （将上述过程列成表格, 便于理解）对每一个可行基，作一个单纯形表，包括基可行解检验数j和主元素。jC1C2CmC1mCnCBCBXb1x2xmx1mxnx1C1x1b2C2x2bmCmxmb10 0 11mana10 1 0 12mana20 0 0 1mmamna12mjBX列中填入基变量，这里是;,21mxxxBC列中填入基变量的价值系数，与基变量一一对应，这里是;,21mCCCb列中填入约束方程组右端的常数；jc行中填入各变量的价值系数;,21mCCC列的数字是在确定换入变量后，按规则计算出来的比值；j行为检验数行，对应各非基变量jx的检验数。例： （按上例）543210

26、00127maxxxxxxz名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 - - - - - - - - - 第二章线性规划第 21 页5,12, 03001032005436049521421321jxxxxxxxxxxj解：BCBXb7 12 0 0 0 1x2x3x4x5x0 3x360 0 4x200 0 5x300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 90 40 30 j7 12 0 3x240 0 4x50 12 2x3

27、0 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.1 30.77 20 100 j3.4 1.2 0 3x84 7 1x20 12 2x24 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16 j-1.36 -0.52 最优解为TX0, 0,84,24,20最优值为4282412207Z4 单纯形法的进一步讨论一、人工变量法1、大 M 法在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对结目标函数值不受影响，为此我们假定人工变量在目标函数中的系数为（-M ） （ M 为任意大的正数） ，这样目标函数实

28、现最大化时，必需把人工变量换出。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 22 页 - - - - - - - - - 例 5 3213maxxxxZ0,1232411232131321321xxxxxxxxxxx试用大 M 法求解解：化为标准型7654321003maxMxMxxxxxxZ7,2 , 1, 012324112731653214321jxxxxxxxxxxxxxjCB XBb 3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6

29、x7 0 x4 11 -M x63 -M x71 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 1 11 3/2 -1 j3-6M 1+M 1+3M -M 0 x410 -M x61 -1 x31 3 -1 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1 - 1 - j1 -1+M -M 1-3M 0 x412 -1 x21 -1 x31 3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1 4 - - j1 -1 -M-1 -M-1 3 x14 -1 x21 -1 x39 1

30、 0 0 1/3 -2/3 2/3 -5/3 0 1 0 0 -1 1 -2 0 0 1 2/3 -4/3 4/3 -7/3 j-1/3 -1/3 -M+1/3 -M-1/3 最优解TX9, 1 ,4，最优值2Z2、两阶段法前面介绍了大M 法，但在电子计算机求解含有人工变量的线性规划问题时，只能用很大的数代替M，这就可能造成计算上的错误。故再介绍两阶段法。第一阶段：不考虑原问题是否存在基可行解；给原问题加入人工变量，并构成仅含人工变量的目标函数和要求实现最小化，然后用单纯形法求解上述模型，若得到0，这说明原问题存在基可行解，可以进行第二阶段计算。否则，原问题无可行解，应停止计算。第二阶段：将第

31、一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换为原问题的目标函数系数，作为第二阶段计算的初始表。例 6 3213maxxxxz名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - 第二章线性规划第 23 页0,1232411232131321321xxxxxxxxxxx试用两阶段法求解。解：第一阶段：7676maxminxxxx7,2 , 10132324112731653214321jxxxxxxxxxxxxjCB

32、XBb 0 0 0 0 0 1 1 x1 x2 x3 x4 x5 x6 x7 0 x4 11 1 x63 1 x71 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 1 11 3/2 1 j6 -1 -3 1 0 x410 1 x61 0 x31 3 -2 0 0 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1 - 1 - j0 -1 1 3 0 x412 0 x21 0 x31 3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1 j0 0 1 1 最优解为TX0,0,0 ,12, 1

33、 , 1 ,0第二阶段：CB XBb 3 -1 -1 0 0 x1 x2 x3 x4 x5 0 x4 12 -1 x21 -1 x31 3 0 0 1 -2 0 1 0 0 -1 -2 0 1 0 0 4 - - j1 -1 3 x14 -1 x21 -1 x31 1 0 0 1/3 -2/3 0 1 0 0 -1 0 0 1 2/3 -4/3 - 1 - j-1/3 -1/3 原问题的最优解为：TX9, 1 ,4,最优值为2Z二、退化（极少出现）单纯形法计算中用规划确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现了退化解，当出现退化时，进

34、行多次迭代，而基从,21BB，又返回到1B，即出现计算过程的循环，使永远达不到最优解。为解决这个问题我们介绍勃兰特规则：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 22 页 - - - - - - - - - （ 1） 当 存 在 两 个 或 两 个 以 上 最 大 检 验 数 时 ， 选 取0j中 下 标 最 小 的 非 基 变 量kx为 换 入 变 量 ， 即0minjjk；（2）当按规则计算时，存在两个或两个以上最小比值时，选取下标最小的基变量为换出变量。三、单纯形法小结类型Max min 检验数jBjjPBCC1jBjjPBCc1判别一切0j，最优一切0j，最优确定进基变量kx0maxjk0minjk确定出基变量lxiklikikiabaab0miniklikikiabaab0min有唯一最优解一切0j一切0j名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 22 页 - - - - - - - - -