厦门理工学院-运筹学第一章线性规划

1、 厦厦门门理理工工学学院院 运筹学A,B 某某工工厂厂计计划划生生产产甲甲、乙乙两两种种产产品品, ,已已知知生生产产单单位位产产品品所所需需的的设设备备台台时时及及两两种种原原材材料料的的消消 耗耗见见下下表表：甲产品甲产品乙产品乙产品提供量提供量设设 备备128台时台时材料材料A4016kg材料材料B0412kg利润利润23单位元单位元一一个个问问题题应应如如何何安安排排生生产产，使使得得利利润润最最大大？ 12xx解解： 设设生生产产甲甲、乙乙产产品品 、件件。12121212maxZ2328416412,0 xxxxxxx x 目目标标函函数数 约约束束条条件件 思思考考：与与解解方方

2、程程有有何何关关系系？(4,2) ,14TXz 最最优优决决策策：。一一、运运筹筹学学的的起起源源及及研研究究领领域域1939年年前前，苏苏联联数数学学家家康康托托洛洛维维奇奇得得到到生生产产组组织织与与计计划划问问题题的的数数学学模模型型：112211112211211222221122max.0(1,2,., )nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xbs taxaxaxbxjn 求求解解问问题题也也称称为为解解线线性性规规划划问问题题。绪绪 论论因因为为计计算算方方法法没没有有得得到到解解决决，未未受受到到人人们们的的重重视视。 第第二二次次世

3、世界界大大战战中中，大大量量的的军军事事问问题题（布布雷雷、制制空空、护护航航等等）、运运输输问问题题、计计划划问问题题、后后勤勤问问题题等等的的数数学学模模型型都都是是线线性性规规划划问问题题。SCOOP 大大战战推推动动线线性性规规划划问问题题求求解解方方法法的的研研究究。美美国国空空军军研研究究小小组组提提出出了了单单纯纯形形方方法法，使使得得线线性性规规划划问问题题能能在在计计算算机机上上得得到到有有效效地地解解决决。Scientific Computation of Optimum ProgramsOperational ResearchOR 这这就就形形成成了了学学科科“”, ,简

4、简记记为为“”，当当时时翻翻译译为为“作作战战研研究究”。1 19 97 75 5年年，瑞瑞典典皇皇家家科科学学院院授授予予线线性性规规划划创创始始人人苏苏联联数数学学家家康康托托洛洛维维诺诺贝贝尔尔经经济济学学奖奖。 随随着着计计算算机机的的发发展展，运运筹筹学学得得到到迅迅速速发发展展，它它在在工工程程、运运输输、控控制制、教教育育、医医疗疗、卫卫生生、交交通通、管管理理、投投资资、预预测测、城城市市规规划划等等领领域域得得到到广广泛泛应应用用。 1 19 95 57 7年年，我我国国学学者者受受“运运筹筹于于帷帷幄幄之之中中，决决胜胜于于千千里里之之外外”古古语语启启发发，改改名名为为“

5、运运筹筹学学”。1 1 最短路问题最短路问题 . .管道（线）铺设路线最短管道（线）铺设路线最短 . .货物运输时间（线路）最短货物运输时间（线路）最短2. 2. 分配问题分配问题 . .分房问题分房问题 . .有限资源的最佳配置有限资源的最佳配置3 网络计划技术网络计划技术 .有效组织工程实施有效组织工程实施 .地区交通网络的建设地区交通网络的建设4. 4. 决策树模型决策树模型 . .市场风险投资决策市场风险投资决策 . .技术引进决策技术引进决策 . .产品推销策略产品推销策略5 最小支撑树问题最小支撑树问题 .电话通讯网的架设电话通讯网的架设 .地区交通网络的建设地区交通网络的建设6.

6、 6. 网络流问题网络流问题 . .交通流量最大交通流量最大 . .物流运输费用最少物流运输费用最少7 7 网络图的其他一些应用问题网络图的其他一些应用问题 . .公交汽车线路的最优安排或公交汽车线路的最优安排或链接链接 . .车辆调度问题车辆调度问题 . .工厂选址问题工厂选址问题平板的最优激光铅化平板的最优激光铅化油田的最优勘探油田的最优勘探考古发掘物的顺序排列考古发掘物的顺序排列基因密码基因密码计算机切割的最优安排计算机切割的最优安排消防队和灾情点的调试计划消防队和灾情点的调试计划垃圾清除或街道清洗的调度计划垃圾清除或街道清洗的调度计划按订货以最小角边料切割纸或钢按订货以最小角边料切割纸

7、或钢材等材等运运筹筹学学是是一一门门研研究究系系统统优优化化的的科科学学。二二、运运筹筹学学研研究究所所需需的的基基本本知知识识及及研研究究对对象象 数数学学分分析析、高高等等代代数数、解解析析几几何何提提供供了了研研究究原原理理的的基基础础，计计算算机机理理论论提提供供了了计计算算手手段段。 运运筹筹学学是是应应用用学学科科，是是近近代代应应用用数数学学的的一一个个最最活活跃跃分分支支，利利用用数数学学方方法法为为决决策策者者提提供供科科学学依依据据的的学学科科。有有限限的的资资源源如如何何满满足足无无限限的的需需求求？提提高高经经济济效效益益改改进进技技术术，合合理理安安排排资资源源。第第

8、1章章 线性规划与单纯形法线性规划与单纯形法第第1节节 线性规划问题及其数学模型线性规划问题及其数学模型A,B 某某工工厂厂计计划划生生产产甲甲、乙乙两两种种产产品品, ,已已知知生生产产单单例例位位产产品品所所需需的的设设备备台台时时及及两两种种原原材材料料的的1 1 消消耗耗见见下下表表：甲产品甲产品乙产品乙产品提供量提供量设设 备备128台时台时材料材料A4016kg材料材料B0412kg利润利润23单位元单位元. 11 11 问问题题的的提提出出应应如如何何安安排排生生产产，使使得得利利润润最最大大？ 12xx解解： 设设生生产产甲甲、乙乙产产品品 、件件。12121212maxZ23

9、28416412,0 xxxxxxx x 目目标标函函数数 约约束束条条件件 (4,2) ,14TXz 经经计计算算得得最最优优决决策策：。 如果如果种产品，生产nAAA21种资源mBBB,21产品计划问题有关信息表产品计划问题有关信息表 12nAAA111212122212nnmmmnaaaaaaaaa12mBBB 12mbbb 12nccc可可提提供供量量产产品品种种类类单单位位利利润润资资源源种种类类ijjia设设单单位位第第 种种产产品品所所需需第第 种种资资源源量量11(1,2,.,)0(1,2,., )njjjnijjijjmaxZc xCXa xbimxjn 目目标标函函数数约约

10、束束方方程程jjAx设设生生产产产产品品件件，此此类类问问题题的的数数学学模模型型为为：112211112211211222221122max.0(1,2,., )nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xbs taxaxaxbxjn subject to 例例2 某地区有甲、乙、丙三个食盐产地，产某地区有甲、乙、丙三个食盐产地，产量分别为量分别为70、80、100万吨；有万吨；有A，B，C，D四个城市需要食盐，需求量为四个城市需要食盐，需求量为40，60，90，60万万吨。如何安排运输使费用最低？吨。如何安排运输使费用最低？ 每吨食盐运费如表每吨食盐

11、运费如表运价运价 A城城B城城C城城D城城甲厂甲厂3345乙厂乙厂6431丙厂丙厂2332解：设有解：设有 i 个厂地（个厂地（i1，2，3），），j个销地个销地 （j=1,2,3,4)。并设并设Xij-第第i个盐产地运往第个盐产地运往第j个盐销地的运量。个盐销地的运量。111213142122232431323334700100 xxxxxxxxxxxx8 8112131122232132333142434xxxxxxxxxxxx4 40 06 60 09 90 06 60 0运出量等于产量：运出量等于产量：运达量等于需求量：运达量等于需求量：目标函数为：目标函数为：111213142134

12、S=3 3456.2minxxxxxx运输问题的数学模型为：运输问题的数学模型为：111213142122232431323334700100 xxxxxxxxxxxx8 8112131122232132333142434xxxxxxxxxxxx4 40 06 60 09 90 06 60 0目标函数为：目标函数为：111213142134S=3 3456.2minxxxxxx 。已知各已知各产地的产地的和各销地的和各销地的以及各产地到各销地的以及各产地到各销地的 某种物资有若干产地和销地，现在需要某种物资有若干产地和销地，现在需要把把这种物资从各个产地运到各个销地，这种物资从各个产地运到各个

13、销地，问应如何组织调运，才能使，问应如何组织调运，才能使？根据具体问题组织调运。根据具体问题组织调运。 有关信息表有关信息表单位单位 运价运价 销销 或运距或运距 地地产地产地B1 B2 Bn产产 量量A1 A2 Amc11 c12 c1 n c21 c22 c2n cm1 cm2 cm na1 a2 am销销 量量 b1 b2 bnnjjmiiba11ijijxAB设设表表示示从从产产地地运运往往销销地地的的运运量量。运运输输问问题题数数学学模模型型的的建建立立1(1,2,.,)iinijijAaxaim 由由于于从从运运出出量量等等于于产产量量 ：1(1,2,., )jjmijjiBbxb

14、jn 又又由由于于销销地地接接收收量量等等于于需需求求量量 ：11mnijijijZc x 总总运运费费为为运运输输问问题题的的数数学学模模型型：11(1,2,.,).(1,2,., )0(1,2,.,;1,2,., )nijijmijjiijxajms txbinxim jn 11mnijijijminZc x 目目标标函函数数 minjjiba11产销平衡条件合理下料问题合理下料问题毛坯，问应如何选取合理的下料方法，使得既满足毛坯，问应如何选取合理的下料方法，使得既满足 对截出毛坯的数量要求，又使所用的原材料最少对截出毛坯的数量要求，又使所用的原材料最少（或废料最少）？（或废料最少）？ 在

15、加工业中，经常遇到这类问题。在加工业中，经常遇到这类问题。 问题的一般提法是：已知某种尺寸的棒料或板材，问题的一般提法是：已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件需要将其切割成一定数量既定规格的几种零件 例例3 3 某厂接受了一批加工定货，客户要求加某厂接受了一批加工定货，客户要求加工工100100套钢架，每套由长套钢架，每套由长2.92.9米、米、2.12.1米和米和1.51.5米的米的圆钢各一根组成。现在仅有一批长圆钢各一根组成。现在仅有一批长7.47.4米的钢管毛米的钢管毛坯，问应如何下料，使所用的钢管根数最少？坯，问应如何下料，使所用的钢管根数最少？ 最简单的

16、处理方法：从一根钢管上截取最简单的处理方法：从一根钢管上截取2.92.9米、米、2.12.1米和米和1.51.5米的管料各一根时正好配成一套钢架，米的管料各一根时正好配成一套钢架，100100套钢架总共需要套钢架总共需要100100根钢管毛坯。每根钢管毛坯根钢管毛坯。每根钢管毛坯剩下剩下0.90.9米的残料，米的残料，100100根毛坯总共剩根毛坯总共剩9090米残料。米残料。这是最好的办法吗？这是最好的办法吗？截法12345678单位2.9米21110000根2.1米02103210根1.5米10130234根残料0.10.30.901.10.20.81.4米 合理套裁肯定会有更好的效果。先

17、设法列出合理套裁肯定会有更好的效果。先设法列出所有的下料方案，思路如下表。所有的下料方案，思路如下表。12345678xxxxxxxx用用量量根根81123456781234567812345678123456781280.10.30.901.10.20.81.42111000010002103210100. .10130234100,0iiMinZxMinZxxxxxxxxxxxxxxxxxxxxxxxxs txxxxxxxxxxx 或或ixi设设 为为按按第第 种种方方案案下下料料所所用用的的钢钢管管的的根根数数，则则残残料料最最少少 例例4 4 现准备采购甲、乙两种食品，表中给现准备采购

18、甲、乙两种食品，表中给出了已知价格及相关的营养成分。问应如何采出了已知价格及相关的营养成分。问应如何采购食品才能在保证营养要求的前提下，花费最购食品才能在保证营养要求的前提下，花费最省？省？ 四、四、 合理配料问题合理配料问题 问题的一般提法：由多种原料配置成含有问题的一般提法：由多种原料配置成含有 m种成分的产品，并种成分的产品，并求成本最低求成本最低的配料方案。的配料方案。营养问题已知数据表营养问题已知数据表 1 公斤食物所公斤食物所 含营养成含营养成 食品食品 分数量分数量 营养营养 成分成分 甲甲 乙乙 每每 天天 的的 最最 低低 需需 要要 量量 （单位）（单位） 维维 生生 素素

19、 淀淀 粉粉 蛋蛋 白白 质质 1 5 3 3 1 2 90 100 120 单单 价（元）价（元） 12 19 最右栏给出了按营养学标准每人每天的最低需要量。最右栏给出了按营养学标准每人每天的最低需要量。依题意可列出下面的线性规划：依题意可列出下面的线性规划：12,xx设设分分别别为为甲甲、乙乙两两种种食食品品的的采采购购量量，则则12Z = 1.2x + 1.9x购购买买两两种种食食品品的的总总费费用用为为： 运动员集训队食谱设计；运动员集训队食谱设计； 幼儿园、医院等特殊群体的营养配餐；幼儿园、医院等特殊群体的营养配餐；机关、学校、企业等企事业单位团体机关、学校、企业等企事业单位团体 伙

20、食设计；伙食设计；家庭食谱设计；家庭食谱设计； 饲料配比及化工产品中的混合问题等。饲料配比及化工产品中的混合问题等。 某配合饲料厂生产某配合饲料厂生产以鸡饲料为主的配合饲料，现准备研制一种以鸡饲料为主的配合饲料，现准备研制一种新的新的，所用原料的营养成所用原料的营养成分和饲养标准见表，希望这种新饲料分和饲养标准见表，希望这种新饲料能满足能满足肉用仔鸡的喂养需要肉用仔鸡的喂养需要又使又使总成本尽可能低，总成本尽可能低，应如何设计配比方案？应如何设计配比方案？需求量(%) 19.01.00.700.940.360.190.30123456xxxxxx 已 知 各 种 原 料 的 购 进 价已 知

21、各 种 原 料 的 购 进 价 1 公 斤 分 别公 斤 分 别为为:3.14(玉米玉米)、5.40(豆饼豆饼)、2.20（麦麸）、（麦麸）、12.00（鱼粉）、（鱼粉）、4.00（骨粉）、（骨粉）、5.00（鸡促进素）（鸡促进素）元。元。 设设每每100100公斤公斤饲料中配给的玉米、豆饼、麦饲料中配给的玉米、豆饼、麦麸、鱼粉、骨粉、鸡促进素分别为麸、鱼粉、骨粉、鸡促进素分别为123456,x xxxxx ( (公公斤斤) )数学模型为：数学模型为：3.14 5.40 2.20 12.00 4.00 5.00单单位位价价格格：，元元1234563.145.42.21245minzxxxxxx

22、则则目目标标函函数数为为六、六、 污水处理问题污水处理问题 例例6 靠近某河流有两个化工厂，流经第一化靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天工厂的河流流量为每天 500 万万m3，两工厂之间有，两工厂之间有一条流量为每天一条流量为每天 200 万万m3的支流（见图）：的支流（见图）： 第一化工厂每天排放污水第一化工厂每天排放污水2万万m3 ，第二化工，第二化工厂每天排放污水厂每天排放污水 1.4万万 m3 。污水从工厂。污水从工厂1 流到工流到工厂厂2 前会有前会有20%自然净化。自然净化。 而工厂而工厂1和工厂和工厂2处理污水的成本分别为处理污水的成本分别为1000元元/万万

23、m3和和800元元/万万m3。问两工厂各。问两工厂各应处理应处理多少污多少污水才能使处理污水的总费用最低？水才能使处理污水的总费用最低？ 解：设工厂解：设工厂1 1和工厂和工厂2 2每天分别处理污水每天分别处理污水x1 1和和x2 2万万 m3 3，则有：，则有：Min z=1000 x1+800 x2 (2-x1) / 500 0.0020.8 (2-x1) + 1.4-x2 / 700 0.002 x1 2, x2 1.4 x1, x20根据环保要求，河水中污水的含量应不大于根据环保要求，河水中污水的含量应不大于 0.2%。约束方程约束方程(1,2,., )jxjn 1 12211 112

24、21121 1222221 12212()()( , )( , ). .( , ),0nnnnnnmmmnnmnMaxMin Zc xc xc xa xa xa xba xa xa xbsta xaxa xbx xx 或目标函数（约束条件）10njijiixxcabx ， ， 为决策变量为价值系数，为技术系数为限额系数， 为变量的非负约束条件1.2线线性性规规划划问问题题的的几几何何解解法法图图解解法法几几何何解解法法直直观观，有有助助于于了了解解线线性性规规划划问问题题求求解解原原理理。先先熟熟悉悉如如下下平平面面：1 xy ）2 22 xy）22 yx 22y x yx xy 55x=14

25、y=x+3 5y=25-3x1ABCC: (1, 4.4)A: (5, 2)B: (1, 1.)Oxy问题问题1 1：x 有无最大（小）值？有无最大（小）值？问题问题2 2：y 有无最大（小）值？有无最大（小）值？问题问题3 3：z=2z=2x+y 有无最大（小）值？有无最大（小）值？1255334xyxyx在平面区域内在平面区域内可行解区域可行解区域55x=1x-4y+3=03x+5y-25=01ABCC(1.00, 4.40)A(5.00, 2.00)B(1.00, 1.00)Oxyzxyyxz22由.2轴上的截距在就是直线yzxyzxy2122 xy32 xyn求求z=2x+y的最的最大

26、值和最小值。大值和最小值。n所以所以z最大值最大值12nz最小值为最小值为31255334xyxyx12 解题步骤解题步骤4 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的约束等式，并找出在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。的点称为可行解。 2 标出目标函数值增加或者减小的方向。标出目标函数值增加或者减小的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动

27、，找与可行域最后目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。相交的点，该点就是最优解。图解法umax Z = 2X1 + X2 u X1 + 1.9X2 3.8u X1 - 1.9X2 3.8us.t. X1 + 1.9X2 10.2u X1 - 1.9X2 -3.8u X1 ，X2 0例例 用图解法求解线性规划问题用图解法求解线性规划问题x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X

28、1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z = 2X1 + X2max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种

29、情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域nmin Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此点是唯一最优解此点是唯一最优解 006346321212121xxxxxxxx、246x1x2246无界解无界解( (无最优解无最优解) )maxZ=x1+2x2例例 max Z min

30、Z1236xx124xx1236xxx1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)0,050305 .140221212121 xxxxxxxxmax Z=3x1+4x2例例 由图解法得到的几种情况由图解法得到的几种情况 根据以上例题，进一步分析讨论可知线性规划的可行域和根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况：最优解有以下几种可能的情况： 1.可行域为封闭的有界区域可行域为封闭的有界区域 (a)有唯一的最优解；有唯一的最优解； (b)有无穷多个最优解；有无穷多个最优解； 2.可行域为封闭的无界区域可行域为封闭的无

31、界区域 (c)有唯一的最优解；有唯一的最优解； (d)有无穷多个最优解；有无穷多个最优解； (e)目标函数无界目标函数无界(即虽有可行解，但在可行域中，目标函数即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少可以无限增大或无限减少)，因而没有有限最优解。，因而没有有限最优解。 3.可行域为空集可行域为空集 (f)没有可行解，原问题无最优解没有可行解，原问题无最优解几个结论：几个结论：1. 线性目标函数的最大（小）值一般在可行区域线性目标函数的最大（小）值一般在可行区域 的顶点处取得，也可能在边界处取得。的顶点处取得，也可能在边界处取得。2. 求线性目标函数的最优解，要注意分析求线性目

32、标函数的最优解，要注意分析 线性目标函数所表示的几何意义线性目标函数所表示的几何意义 在在 y 轴上的截距（两维）。轴上的截距（两维）。3. 图解法只能解决平面问题，三维的线性规划问题图解法只能解决平面问题，三维的线性规划问题图解，困难就很大。图解，困难就很大。1.3线线性性规规划划问问题题的的标标准准形形式式一一、线线性性规规划划问问题题的的数数学学模模型型（1 1）一般形式）一般形式 0,),(),(),(. .)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax或11()( , )

33、1,2,. .01,2,njjjnijjijjMaxMin Zc xa xbims txjn 或或（）（）10njijiixxcabx ， ， 为决策变量为价值系数，为技术系数为限额系数， 为变量的非负约束条件（3 3）矩阵形式）矩阵形式0)(.)(XbAXtsCXZMinMax或其中其中 : 111212122212.nnmmmnaaaaaaAaaa 12,nxxXx 12,mbbbb 12,TnccCc 二二、线线性性规规划划问问题题的的标标准准型型maxZ = CXAX = bb0X0 （） 三三、线线性性规规划划问问题题标标准准化化 21kkkxxx12121212maxZ232841

34、6s.t412,0 xxxxxxx x 1 1） 12123142512345maxZ2328416s.t412,0 xxxxxxxxxx xxxx 解解： 1231231231231232310328. .31,0,m inZxxxxxxxxxs txxxxxx 符符 号号 不不 受受 限限 制制126712674126751267124567m ax2310328. .31,0Zxxxxxxxxxxxxxxs txxxxxxxxxx ., 12阶子式阶子式的的称为矩阵称为矩阵阶行列式，阶行列式，的的中所处的位置次序而得中所处的位置次序而得变它们在变它们在不改不改元素元素处的个处的个），位于

35、这些行列交叉），位于这些行列交叉列（列（行行中任取中任取矩阵矩阵在在定义定义kAkAknkmkkkAnm 回回顾顾矩矩阵阵、向向量量、解解线线性性方方程程组组方方面面的的知知识识1. ( )R A矩矩阵阵的的秩秩的的概概念念及及其其求求法法132202132015A 如如:已知已知A矩阵矩阵,研究其研究其k阶子式阶子式13202 12303 12101 13620 1220130215 二阶子式二阶子式: :共有共有 二阶子式二阶子式223418CC1320210201 1320230205 1220130215 共有共有 个三阶子式个三阶子式33344CC 132202132015A 201

36、0( ).ArDrDArAR A定义设在矩阵中有一个不等于的阶子式，且所有阶子式（如果存在的话）全等于 ，那末称为矩阵 的最高阶非零子式，数称为矩阵的秩，记作并规定零矩阵的秩等于零.)( 子子式式的的最最高高阶阶数数中中不不等等于于零零的的是是的的秩秩矩矩阵阵AARAnm . 个个阶阶子子式式共共有有的的矩矩阵阵knkmCCkAnm 或说：或说：例例1.174532321的秩的秩求矩阵求矩阵 A解：解：中，中，在在 A，阶子式只有一个阶子式只有一个的的又又AA3. 03221 ，且且0 A. 2)( AR. , 数数是是唯唯一一确确定定的的梯梯形形矩矩阵阵中中非非零零行行的的行行梯梯形形，行行

37、阶阶把把它它变变为为行行阶阶变变换换总总可可经经过过有有限限次次初初等等行行任任何何矩矩阵阵nmA 这就是矩阵的秩。这就是矩阵的秩。还可用矩阵的初等变换方法求秩：还可用矩阵的初等变换方法求秩：例例2.00000340005213023012的的秩秩求求矩矩阵阵 B解解行，行，其非零行有其非零行有是一个行阶梯形矩阵，是一个行阶梯形矩阵，3B.4阶子式全为零阶子式全为零的所有的所有B, 0400230312 而而. 3)( BR向量的线性相关性向量的线性相关性2. 可可逆逆矩矩阵阵AA若若矩矩阵阵 可可逆逆，则则为为非非奇奇异异矩矩阵阵；1ABBAEAAB 若若，则则 可可逆逆，且且 。-1A E

38、E A 行行初初等等变变换换求求逆逆矩矩阵阵：（）( () )mAR(A )m则则为为满满秩秩阵阵，即即 ；A 则则0 0；A则则中中列列（行行）向向量量线线性性无无关关。例例3 3 求方阵求方阵 的逆矩阵的逆矩阵. . 343122321A解解343122321 A, 2.1存在存在 A, 2341211 A, 3331212 AijAaij为为元元素素的的代代数数余余子子式式（1）伴随矩阵求逆矩阵法）伴随矩阵求逆矩阵法 AAA11同理可得同理可得, 2, 6, 6, 223222113 AAAA, 2, 5, 4333231 AAA,222563462 A得得故故 AAA11 222563

39、46221.11125323231 ()jiAA abAcd 0adbc0AadbcdbAca 11AAadbc 1dbadbcca 例例4 4 已知已知且，求解如：如：1234A 2A 4231A 1421231A 1A 322rr 2131rrrr 解解的逆矩阵。的逆矩阵。 求矩阵求矩阵例例5=441431321A123100()134010144001AI 101011001120110321 121011001100110321（2）初等行变换求逆矩阵法）初等行变换求逆矩阵法23133rrrr 1211103641000100211232rrr 1 0 04410 1 00110 0

40、1121所以，所以，A的逆矩阵为的逆矩阵为4410111210 ,: 22112121 mmmmkkkkkkA 使使全全为为零零的的数数如如果果存存在在不不给给定定向向量量组组注意注意1211122 1. ,0, 0.nnnnkkkkk 若若线线性性无无关关 则则只只有有当当时时 才才有有成成立立., 2. 线线性性相相关关性性无无关关就就是是不不是是线线对对于于任任一一向向量量组组定义定义3 3则称向量组则称向量组 是线性相关的，否则称它线性无关是线性相关的，否则称它线性无关A3. 线线性性相相关关与与线线性性无无关关( (线线性性独独立立) )., 0, 0, 3. 线线性性无无关关则则说

41、说若若线线性性相相关关则则说说若若时时向向量量组组只只包包含含一一个个向向量量 .4. 组组是是线线性性相相关关的的包包含含零零向向量量的的任任何何向向量量.,. 5 量量共共面面向向量量相相关关的的几几何何意意义义是是三三是是两两向向量量共共线线；三三个个向向义义量量对对应应成成比比例例，几几何何意意充充要要条条件件是是两两向向量量的的分分它它线线性性相相关关的的量量组组对对于于含含有有两两个个向向量量的的向向维维向向量量组组n TnTTeee1 , 0 , 0,0 , 1 , 0,0 , 0 , 121 ，解解.),( 21阶单位矩阵阶单位矩阵是是的矩阵的矩阵维单位坐标向量组构成维单位坐标

42、向量组构成neeeEnn .)(01 nERE ，知知由由()R E 即即等等于于向向量量组组中中向向量量个个数数，故故向向量量组组线线性性无无关关。例例6线性无关。线性无关。， 742520111321 .21321的的线线性性相相关关性性，及及，试试讨讨论论向向量量组组 解解已知已知例例7设设1 122330kkk 问题转为求解齐次方程组：问题转为求解齐次方程组： 751421201),(321 2325rr ， 000220201., 2),(,2),(2121321321线性无关线性无关向量组向量组线性相关；线性相关；，向量组，向量组可见可见 RR 75122020112rr 1312

43、rrrr 5502202012132 事实上，有事实上，有的解的解讨论线性方程组讨论线性方程组的秩，的秩，和增广矩阵和增广矩阵如何利用系数矩阵如何利用系数矩阵bAxBA .,2的的秩秩阵阵的的秩秩等等于于增增广广矩矩矩矩阵阵的的充充分分必必要要条条件件是是系系数数有有解解元元非非齐齐次次线线性性方方程程组组定定理理bABAbxAnnm nrrBRAR 4. 方方程程组组解解的的判判别别0AX 齐齐次次方方程程组组 解解的的判判别别（总总是是有有解解）AXb 非非齐齐次次方方程程组组解解的的判判别别小结小结有唯一解有唯一解bAx nBRAR nBRAR 有无穷多解有无穷多解. .bAx )()(

44、BRAR 无解无解变量的个数变量的个数例例8 8 求解齐次线性方程组求解齐次线性方程组解解 4630463012211234123412342202220430 xxxxxxxxxxxx 施行初等行变换：施行初等行变换：对系数矩阵对系数矩阵 A13122rrrr 122121221143A 0000342101221)3(223 rrr212rr 00003421035201即得与原方程组同解的方程组即得与原方程组同解的方程组 , 0342, 0352432431xxxxxx34(,)xx 可可任任意意取取值值 ,342,352432431xxxxxx ,342,3522413222221cx

45、cxccxccx形形式式，把把它它写写成成通通常常的的参参数数令令2413,cxcx .1034350122214321 ccxxxx例例9 9 求解非齐次线性方程组求解非齐次线性方程组 . 3222, 2353, 132432143214321xxxxxxxxxxxx解解对增广矩阵对增广矩阵B进行初等变换进行初等变换 322122351311321B13122rrrr 10450104501132123rr 200001045011321, 3)(, 2)( BRAR显显然然，故方程组无解故方程组无解例例10 求解非齐次方程组的通解求解非齐次方程组的通解.213213043214321432

46、1 xxxxxxxxxxxx解解 对增广矩阵对增广矩阵B进行初等变换进行初等变换 2132111311101111B 2121001420001111.00000212100211011 , 2 BRAR由由于于故方程组有解，且有故方程组有解，且有 2122143421xxxxx 42442342242102120021xxxxxxxxxxxx.02102112000011424321 xxxxxx.,42任任意意其其中中xx所以方程组的通解为所以方程组的通解为1.4线线性性规规划划问问题题解解的的概概念念(1)2m nmaxZ = CXAX = bb0X0A （）（ ）其其中中1.解解，可可

47、行行解解，最最优优解解LP1LPX满满足足约约束束条条件件（ ）的的称称为为的的解解；LP1LPX满满足足约约束束条条件件（ ）, ,( (2 2) )的的称称为为的的可可行行解解；LP使使目目标标函函数数达达到到最最大大值值的的可可行行解解称称为为的的最最优优解解。LP()m nR(A)m,Am,BAmB0Bmn 设设即即矩矩阵阵 的的秩秩为为且且是是矩矩阵阵的的一一个个 阶阶非非奇奇异异子子式式（），则则称称 为为的的一一个个基基。 一一般般而而言言12(),LP(,.,mAB NBBP PP 为为方方便便起起见见，设设矩矩阵阵其其中中为为的的一一个个基基, ,则则) )。称称: :121

48、,.,mP PP）为为基基向向量量；12122,.,.,mmBP PPx xxX）对对应应的的变变量量为为基基 变变量量, ,记记为为；12,.,mmnNnmxxxX 3 3）其其余余个个变变量量为为非非基基 变变量量, ,记记为为。2.基基，基基向向量量，基基变变量量，非非基基变变量量3.基基解解，基基可可行行解解，可可行行基基(),LPAB NB 设设矩矩阵阵其其中中 为为的的一一个个基基, ,满满足足非非负负约约束束的的基基解解，称称为为基基可可行行解解；1212(,.,.,mNmmnBP PPXxxx在在这这个个基基) )下下，非非基基变变量量（）取取零零值值的的解解称称为为基基解解；

49、与与基基可可行行解解对对应应的的基基称称为为可可行行基基。12(0)(0)(0)(0)12(,.,.,mTBmBP PPXxxx 此此时时，在在基基) )下下，基基解解为为（, ,0 0, ,0 0, ,. . . ., ,0 0）。)BBXb 对对应应于于基基 下下的的基基解解是是唯唯一一的的（；mnC 为为此此基基解解的的数数目目基基的的数数目目； 基基可可行行解解数数目目基基解解。甲产品乙产品可利用资源原材料23100 吨加工时间42120时单位利润64百元 例例11某企业生产甲、乙两种产品，数据见下表。某企业生产甲、乙两种产品，数据见下表。问：如何安排生产使利润达最大？问：如何安排生产

50、使利润达最大？解：设生产甲、乙产品各解：设生产甲、乙产品各12,xx 件件，1）建立模型：）建立模型：121212122310064.42120,0 xxMaxZxxs txxx x ，2）标准化：）标准化：1212312412346423100.42120,0MaxZxxxxxs txxxx x x x 12342 3 1 0,4 2 0 1APPPP 100,6 4 0 0120bC 1234(,)TXxxxx 1x2x3Q (20,20)1223100 xx1242120 xx2Q (50,0)5100Q (0,)31Q (30,0)4Q (0,60)120,0 xx (0,0)O(20

51、,20,0,0)200()TXZ 最最优优解解为为最最优优值值为为百百元元 。12640 xx 12400643xx 1264200 xx 3 3）图图解解4）基基，基基向向量量，基基变变量量，非非基基变变量量12342310,4201AP P P P （）112213314423524634(,),(,),(,)LPBP PBP PBP PBP PBP PBP PE 可可以以验验证证：) ), ,= =( () ), ,= =( (= =( () ), ,都都为为此此的的基基；12380.42B 比比如如334414232314BNBNXxxXxxXxxXxx=(,)=(,)，=(,)=(,

52、)；=(,)=(,)，=(,)=(,)；112212341324BNBNXxxXxxXxxXxx=(,)=(,)，=(,)=(,)；=(,)=(,)，=(,)=(,)；556624133412BNBNXxxXxxXxxXxx= =( (, ,) )，= =( (, ,) )；= =( (, ,) )，= =( (, ,) )。对对应应的的基基变变量量、非非基基变变量量分分别别为为5)基基解解，基基可可行行解解，可可行行基基1123456T,20 20 0 0BB B B B B BX对对应应基基下下的的基基解解为为：= =( (, , ， ，) )；12342310,4201AP P P P

53、（）100,120b 2T30 0 40 0BX= =( (， ， ，) )；350,0,0, 80BX T T=()=()；5616003BBXX100100=(0=(0， ，) )；3 3=(0,0,100,120)=(0,0,100,120)。31254,Q Q Q Q Q O基基解解分分别别对对应应图图解解上上的的点点。135,Q Q Q O其其中中点点为为基基可可行行解解。4T(0,60,80,0)BX= =；1256,B B B B对对应应的的为为可可行行基基。6） 基基最最优优解解，最最优优基基若若基基解解又又是是最最优优解解，则则称称之之为为基基最最优优解解，与与之之相相对对应

54、应的的基基称称为为最最优优基基。1(20,20,0,0)TB*1XXB = B 最最优优解解为为几几何何方方法法得得到到最最优优基基为为。620420200()z 最最优优值值百百元元将以上结论列表如下：将以上结论列表如下：基基基向基向量量基变量基变量基解基解可行基可行基 最优解最优解243121402041312030211001 121314232434,PPPPPPPPPPPP121314232434,xxxxxxxxxxxx(50,0,0,80)(0,60,20,0(20,20,0,0)(30,0,40,0)100160(0,0,)33(0,0,100,120)TTTTTT 2 0 0

55、1 8 04 0 030最优解最优解基最优解基最优解mnC 基基只只有有 （有有限限个个）；BX = b且且对对应应一一个个基基的的基基可可行行解解是是唯唯一一的的（）；一一个个线线性性规规划划问问题题的的基基可可行行解解只只有有有有限限个个。解解区区域域第第2节节 线性规划问题解的理论线性规划问题解的理论2.1基基本本概概念念(1)(2)(1)(2)1.,(01)nnnnKnXXKXXKK 凸凸集集设设是是 维维欧欧氏氏空空间间的的一一个个点点集集，若若任任意意两两点点（1 1有有则则称称: :）为为凸凸集集。实实心心圆圆，实实心心球球体体，实实心心立立方方体体等等都都为为凸凸集集，圆圆环环

56、不不是是凸凸集集。直直观观上上，凸凸集集没没有有凹凹入入部部分分，内内部部没没有有空空洞洞 线段线段 (1)(2)XX向向量量与与的的线线性性组组合合(1)(2)()2.,.,.,(01,1,2,.,;1)mnmimii=1XXXnKmim 1 12 2凸凸组组合合设设是是 维维欧欧氏氏空空间间的的 个个点点，若若存存在在使使得得：(1)(2(1)(2)()().,.,mmmXXXXXXXX 1 12 2则则称称 为为的的凸凸组组合合。线线性性组组合合(1)(2)(3)3XXXX 1 12 2(1)(2)3.,KXKXXXK 顶顶点点（极极点点）设设 是是凸凸集集，；若若不不能能用用不不同同的

57、的两两点点的的线线性性组组合合表表示示为为如如圆圆周周上上的的点点，球球体体表表面面上上的的点点，都都不不能能成成为为任任意意两两内内点点连连线线上上的的点点，它它们们是是顶顶点点。(1)(2),(01)XXXKXK（1 1 ）则则称称 为为 的的一一个个顶顶点点（极极点点）。顶点顶点不不能能成成为为两两内内点点连连线线上上的的点点，称称为为顶顶点点。2.2LP几几个个定定理理（解解的的性性质质）LPDD定定理理1 1 若若存存在在可可行行域域 ，则则 是是凸凸集集。 ,0DX AXb X 证证设设线线性性规规划划问问题题的的可可行行域域为为：(1)(2),DXX对对中中任任意意两两个个解解，

58、(1)(2)(1)(2)(1),(01)AXAXXAXAXbbb 有有（1 1 ）= =（1 1 ）(1)(2)AXAXb （）D则则 为为凸凸集集。 证证毕毕。( )R Am 一一般般设设AX = bX0 为方便起见，为方便起见，XD 则则LPXX正正分分量量( (非非零零分分定定理理2 2 量量) )的的可可行行解解 为为基基可可行行解解的的充充要要条条件件是是：的的所所对对应应的的系系数数列列向向量量线线性性无无关关（独独立立）。121,.,nXx xx T T证证（） 设设（） 为为基基可可行行解解。X中中非非基基变变量量取取零零值值（由由定定义义知知）X中中非非零零分分量量对对应应的

59、的变变量量为为基基变变量量又又基基变变量量对对应应的的系系数数列列向向量量为为基基向向量量基基可可行行解解非非零零分分量量对对应应的的列列向向量量线线性性无无关关12X,.,kx xx T T设设基基可可行行解解为为 （, , 0 0, ,0 0, ,. . . ., ,0 0 ） 基基变变量量 非非基基变变量量 的的取取值值X 中中非非零零分分量量对对应应的的系系数数列列向向量量线线性性无无关关也许含有零也许含有零( ),R Amkm 又又且且 122X,.,0kc cc T T （ ） 为为方方便便起起见见，设设可可行行解解为为（, ,0 0, ,0 0, ,. . . ., ,0 0）1

60、212,.,.,kkx xxP PP对对应应的的系系数数列列向向量量线线性性无无关关12,.,kmkP PP可可从从其其余余列列向向量量中中取取到到 个个列列向向量量与与构构成成一一个个基基km 当当 时时：X 则则可可行行解解 是是基基可可行行解解可可行行解解的的非非零零分分量量对对应应的的列列向向量量线线性性无无关关基基可可行行解解km 当当时时：12,.,kP PP列列向向量量组组恰恰好好构构成成一一个个基基XX则则：对对应应的的基基解解仍仍为为 ，即即可可行行解解 为为基基可可行行解解。正常数正常数LPX定定理理3 3 的的基基可可行行解解 对对应应于于可可行行域域的的顶顶点点。Xm证