最优化方法第二章线性规划的单纯形法

《最优化方法第二章线性规划的单纯形法》由会员分享，可在线阅读，更多相关《最优化方法第二章线性规划的单纯形法（53页珍藏版）》请在金锄头文库上搜索。

1、线性规划的单纯形法线性规划的单纯形法感谢：上海电力薛感谢：上海电力薛感谢：上海电力薛感谢：上海电力薛XXXX老师提供老师提供老师提供老师提供1美国数学家，美国全国，美国全国科学院院士。线性规划线性规划的奠基人。的奠基人。1914年年11月月8日生于美国俄勒冈州波特兰市。日生于美国俄勒冈州波特兰市。1946年在伯克利加利福尼亚大学数学系获哲年在伯克利加利福尼亚大学数学系获哲学博士学位。学博士学位。1947年年丹齐克在总结前人工作丹齐克在总结前人工作的基础上创立了的基础上创立了线性规划线性规划,并提出了解决线并提出了解决线性规划问题的性规划问题的单纯形法单纯形法。19371939年任年任美国劳工统

2、计局统计员美国劳工统计局统计员，19411952年任年任美国美国空军司令部数学顾问空军司令部数学顾问、战斗分析部和统计管理部主任。、战斗分析部和统计管理部主任。19521960年任美国年任美国兰德公司兰德公司数学研究员，数学研究员，19601966年任年任伯克利加伯克利加利福尼亚大学利福尼亚大学教授和运筹学中心主任。教授和运筹学中心主任。1966年后任年后任斯坦福大学斯坦福大学运筹学和计算机科学教授。运筹学和计算机科学教授。1971年当选为年当选为美国科学院院士美国科学院院士。1975年获年获美国科学奖章和诺伊曼理论奖金美国科学奖章和诺伊曼理论奖金。George Bernard Dantzig

3、 (1914) 2康托罗维奇，康托罗维奇，. 苏联经济学家，苏联科学院院士，苏联经济学家，苏联科学院院士，最优计划理论的创始人最优计划理论的创始人。1912年生，年生，1930年毕业于列宁格勒大学物理数学系，年毕业于列宁格勒大学物理数学系，1935年获年获数学博士学位。数学博士学位。1964年被选为苏联科学院院士。因提出资源最年被选为苏联科学院院士。因提出资源最大限度分配理论，大限度分配理论，1975年年与美籍荷兰学者与美籍荷兰学者T.C.库普曼斯一起获库普曼斯一起获得得诺贝尔经济学奖金诺贝尔经济学奖金。康托罗维奇的主要贡献是康托罗维奇的主要贡献是把线性规划用于经济管理把线性规划用于经济管理，

4、创立，创立了了最优计划理论最优计划理论。对有效利用资源和提高企业经济效益起了重。对有效利用资源和提高企业经济效益起了重大作用。他还提出经济效果的概念和衡量经济效果的统一指标大作用。他还提出经济效果的概念和衡量经济效果的统一指标体系体系,作为经济决策的定量依据作为经济决策的定量依据,来选择最合理的社会生产结构。来选择最合理的社会生产结构。主要著作有主要著作有生产组织与计划的数学方法生产组织与计划的数学方法(1939)、资源最资源最优利用的经济计算优利用的经济计算(1959)、最优计划的动态模型最优计划的动态模型(1964)等。等。 3佳林佳林库普曼斯库普曼斯(1910年年1985年年)，美国人，

5、美国人，1910年年8月月28日生于日生于荷兰荷兰，1940年离开荷兰移居年离开荷兰移居美国美国。1975年，他和年，他和康托罗维奇康托罗维奇同时获得同时获得诺贝尔经济学奖诺贝尔经济学奖。线线性规划经济分析法性规划经济分析法的创立者。的创立者。 4冯冯诺依曼（匈牙利语：诺依曼（匈牙利语：NeumannJnos；英语：；英语：JohnvonNeumann，1903年年12月月28日日1957年年2月月8日）是出日）是出生于生于匈牙利匈牙利的的美国美国籍籍犹太人犹太人数学家数学家，现，现代代电子计算机电子计算机创始人创始人之一。他在之一。他在计算机计算机科学科学、经济经济、物理学物理学中的中的量子

6、力学量子力学及及几几乎所有乎所有数学数学领域领域都作过重大贡献。都作过重大贡献。 冯冯诺伊曼从小就显示出诺伊曼从小就显示出数学天才数学天才，关于他的童年有不少传，关于他的童年有不少传说。大多数的传说都讲到冯说。大多数的传说都讲到冯诺伊曼自童年起在吸收知识和解题诺伊曼自童年起在吸收知识和解题方面就具有惊人的速度。方面就具有惊人的速度。六岁六岁时他能心算做时他能心算做八位数乘除法八位数乘除法，八八岁岁时掌握时掌握微积分微积分，十二岁十二岁就读懂领会了就读懂领会了波莱尔的大作波莱尔的大作函数论函数论要义。要义。冯冯诺伊曼记忆力惊人，读书过目成涌，自幼爱好历史诺伊曼记忆力惊人，读书过目成涌，自幼爱好历

7、史学，他的历史知识堪称渊博，宛如百科全书。学，他的历史知识堪称渊博，宛如百科全书。 5他的父亲由于考虑到他的父亲由于考虑到经济上经济上原因，请人劝阻年方原因，请人劝阻年方17的冯的冯诺诺依曼依曼不要专攻数学不要专攻数学，后来父子俩达成协议，冯，后来父子俩达成协议，冯诺依曼便去攻读诺依曼便去攻读化学化学。其后的四年间，冯。其后的四年间，冯诺依曼在布达佩斯大学注册为数学方诺依曼在布达佩斯大学注册为数学方面的学生，但并不听课，只是每年按时参加考试。面的学生，但并不听课，只是每年按时参加考试。1926年他在年他在苏黎世的获得苏黎世的获得化学化学方面的大学毕业方面的大学毕业学位学位，他也获得了布达佩斯，

8、他也获得了布达佩斯大学大学数学博士学位数学博士学位。当他结束学生时代的时候，他已经漫步当他结束学生时代的时候，他已经漫步在数学、物理、化学三个领域的某些前沿。在数学、物理、化学三个领域的某些前沿。1926年春，冯年春，冯诺依曼到诺依曼到哥廷根大学哥廷根大学任任希尔伯特希尔伯特的助手。的助手。中学时中学时，他的老师认为按传，他的老师认为按传统的办法教冯统的办法教冯诺依曼中学数学诺依曼中学数学课程将是毫无意义的，他接受了课程将是毫无意义的，他接受了大学教师大学教师的单独的数学训练。的单独的数学训练。1921年，已被大家当作数学家了。年，已被大家当作数学家了。他的他的第一篇论文第一篇论文是和菲克特合

9、写是和菲克特合写的，那时他还的，那时他还不到不到18岁岁。 l933年担任普林斯顿高级研究院教授，当时高级研究院聘有六名教授，其中就包括，其中就包括爱因斯坦，而年仅，而年仅30岁的冯岁的冯诺依曼是他诺依曼是他们当中最年轻的一位。们当中最年轻的一位。6冯冯诺伊曼是二十世纪最重要的数诺伊曼是二十世纪最重要的数学家之一，在学家之一，在纯粹数学纯粹数学和和应用数学应用数学方面方面都有杰出的贡献。他研究希尔伯特空间都有杰出的贡献。他研究希尔伯特空间上线性自伴算子谱理论，为上线性自伴算子谱理论，为量子力学量子力学打打下数学基础；下数学基础；运用紧致群解决了运用紧致群解决了希尔希尔伯特第五问题伯特第五问题；

10、他和默里创造了算子环；他和默里创造了算子环理论，即现在所谓的理论，即现在所谓的冯冯诺伊曼代数诺伊曼代数。1940年以后，冯年以后，冯诺伊曼转向应用数学。在诺伊曼转向应用数学。在力学、经济学、力学、经济学、数值分析和电子计算机数值分析和电子计算机方面作出了卓越贡献。第二次世界大战方面作出了卓越贡献。第二次世界大战时冯时冯诺伊曼因战事需要建立诺伊曼因战事需要建立冲击波理论冲击波理论和和湍流理论湍流理论，发展了流，发展了流体力学；从体力学；从1942年起，他同莫根施特恩合作，写作年起，他同莫根施特恩合作，写作博弈论和博弈论和经济行为经济行为一书，使他成为数理经济学的奠基人之一。一书，使他成为数理经济

11、学的奠基人之一。冯冯诺伊曼对世界上诺伊曼对世界上第一台电子计算机第一台电子计算机ENIAC的设计有决定的设计有决定性的影响，被称为性的影响，被称为“计算机之父计算机之父”。他是现代他是现代数值分析数值分析计计算数学的缔造者之一。算数学的缔造者之一。72 线性规划的标准型和基本概念线性规划的标准型和基本概念p 线性规划问题及其数学模型线性规划问题及其数学模型p 线性规划的图解法线性规划的图解法p 线性规划的标准形式线性规划的标准形式p 标准型线性规划的解的概念标准型线性规划的解的概念p 线性规划的基本理论线性规划的基本理论8n 问题的提出：问题的提出： 在在生生产产管管理理的的经经营营活活动动中

12、中，通通常常需需要要对对“有有限限的的资资源源”寻寻求求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达到最小。最佳：有一个标准或目标，使利润达到最大或成本达到最小。 有限资源的合理配置有两类问题有限资源的合理配置有两类问题l如何合理的使用有限的资源，使生产经营的效益达到最大；如何合理的使用有限的资源，使生产经营的效益达到最大；l在生产或经营的任务确定的条件下，合理的组织生产，安排经在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。营

13、活动，使所消耗的资源数最少。 p线性规划问题及其数学模型线性规划问题及其数学模型9例例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生

14、产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万元。但根据万元。但根据市场需求调查的结果，甲药品每周的产量不应超过市场需求调查的结果，甲药品每周的产量不应超过4 4吨。问该厂应如何安吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？排两种药品的产量才能使每周获得的利润最大？10 定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。 数学模型为数学模型为 s.ts.t. . （subject to)subject to) (such that) (such that) 每吨产品的消耗每吨产

15、品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515单位利润（万元）单位利润（万元） 5 511例例2 2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500500万万m m3 3，在两个工厂之间有一条流量为在两个工厂之间有一条流量为200200万万m m3 3的支流。两化工厂每的支流。两化工厂每天排放某种有害物质的工业污水分别为天排放某种有害物质的工业污水分别为2 2万万m m3 3和和1.41.4万万m m3 3。从第一化工从第一化

16、工厂排出的工业污水流到第二化工厂以前，有厂排出的工业污水流到第二化工厂以前，有20%20%可以自然净化。环保可以自然净化。环保要求河流中工业污水含量不能大于要求河流中工业污水含量不能大于0.2%0.2%。两化工厂处理工业污水的成。两化工厂处理工业污水的成本分别为本分别为10001000元元/ /万万m m3 3和和800800元元/ /万万m m3 3。现在要问在满足环保要求的条现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小用最小工厂工厂1工厂工厂2200万万m3500万万m312决策变量

17、决策变量：x1、x2分别代表工厂分别代表工厂1和工厂和工厂2处理处理污水的数量污水的数量(万万m3)。则目标函数：min z=1000x1+800x2约束条件：第一段河流（工厂1工厂2之间）： (2x1)/500 0.2%第二段河流： 0.8(2x1) +(1.4x2)/7000.2%此外有： x12； x21.4化简有： min z=1000x1+800x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20称之为上述问题的数学模型。13例例，某某铁铁器器加加工工厂厂要要制制作作100100套套钢钢架架，每每套套要要用用长长为为2.92.9米米，2.12.1米米和和1

18、.51.5米米的的圆圆钢钢各各一一根根。已已知知原原料料长长为为7.47.4米米，问问应应如如何何下下料料，可可使使材材料最省？料最省？分分析析：在在长长度度确确定定的的原原料料上上截截取取三三种种不不同同规规格格的的圆圆钢钢，可可以以归归纳纳出出8 8种不同的下料方案：种不同的下料方案：圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.1.1.41.4 问

19、题归纳为如何混合使用这问题归纳为如何混合使用这8 8种不同的下料方案，来制造种不同的下料方案，来制造100100套套钢架，且要使剩余的料头总长为最短。钢架，且要使剩余的料头总长为最短。14设设x xj j表示用第表示用第j j种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,28,j=1,28, 数学模型数学模型 s.ts.t. . 这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产， 使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻

20、求变量x x1 1至至x x8 8的值的值, ,使目标函数取得最使目标函数取得最 小值。小值。 圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.11.11.41.4且为整数且为整数15n 线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1 1）用一组决策变量）用一组决策变量x x1 1，x x2 2，x xn n表示

21、某一方案，且在一般情况下，表示某一方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2 2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3 3）存在若干个约束条件，约束条件用决策变量的线性等式或线）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。性不等式来表达。（4 4）要求目标函数实现极大化（）要求目标函数实现极大化（maxmax）或极小化（或极小化（minmin）。）。满足上述满足上述4 4个特征的规划问题称为线性规划问题个特征的规划问题称为线性规划问题16 线性规划的一般数学模型线性

22、规划的一般数学模型 目标函数目标函数 满足约束条件满足约束条件 通常称通常称 为决策变量，为决策变量， 为价值系数，为价值系数， 为消耗系数为消耗系数, , 为资源限制系数。为资源限制系数。 17p 线性规划的图解法线性规划的图解法 适用于求解两个变量的线性规划问题适用于求解两个变量的线性规划问题n图解法的基本步骤图解法的基本步骤例例4,4,利用例利用例1 1说明图解法的主要步骤，说明图解法的主要步骤， 例例1 1的数学模型为的数学模型为 s.t. 18O51015x1x1=4x25101AB(2,5)CZ5x1+x2=1530x1+20x2=1605x1+2x2=519n 图解法的几种可能结

23、果图解法的几种可能结果 (1(1）有唯一最优解，如例）有唯一最优解，如例1 1。（2 2）有无穷多最优解）有无穷多最优解 如例如例1 1中的目标函数设为中的目标函数设为 maxZmaxZ=10x=10x1 1+2x+2x2 2 则目标函数等值线则目标函数等值线10x10x1 1+2x+2x2 2=Z =Z 与第二约束与第二约束 5x5x1 1+x+x2 21515 的边界线平行。将等值线沿梯度的边界线平行。将等值线沿梯度Z =Z =（1010，2 2）正方向平移）正方向平移 至至B B点时与可行域点时与可行域OABCOABC的整条边界线的整条边界线ABAB重合。重合。 这表明线段这表明线段AB

24、AB上的每一点都使目标函数取得同样的最大值，上的每一点都使目标函数取得同样的最大值， 因而都是最优解。因而都是最优解。20O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530x1+20x2=16010x1+2x2=521例例5 5，试用图解法求解下列线性规划问题试用图解法求解下列线性规划问题 st.（3 3） 无界解（或称无最优解）无界解（或称无最优解） 无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值若是极大化问题，则可使目标函数值Z+,Z+, 极小化问题极小化问题 则可使目标函数值则可使目标函数值Z-Z-， 有

25、无界解的线性规划问题的可行域是无界区域，但反之则不必有无界解的线性规划问题的可行域是无界区域，但反之则不必然。然。22-1O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1O3323（4 4）无可行解）无可行解 某些线性规划问题的可行域是空集，既不存在满足所有约束条某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。件的点，这时问题无可行解，当然更谈不上最优解了。 在实际中出现这种情况可以认为资源条件无法满足人们的要求，在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。既不存在可行方案。 24例6

26、max z=x1+2x2 x1 + 2x21 x1 + x22 x1、x20无可行解。1112OA25以上几种情况的图示如下：可行域有界唯一最优解 可行域有界多个最优解26可行域无界唯一最优解可行域无界无穷多最优解27可行域无界目标函数无界 可行域为空集无可行解281. 有最优解 唯一最优解 无穷多最优解2. 最优解无界3. 无可行解29直观结论：直观结论：（1）可行域可以是个凸多边形，可能无界，也可能为）可行域可以是个凸多边形，可能无界，也可能为空；空；（2）若线性规划问题的最优解存在，它一定可以在）若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；可行域的某一个顶点上得到；

27、（3）若在两个顶点上同时得到最优解，则该两点连）若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即线上的所有点都是最优解，即LP有无穷多最优解；有无穷多最优解；（4）若可行域非空有界，则一定有最优解）若可行域非空有界，则一定有最优解。30n 标准线性规划模型标准线性规划模型 线性规划问题的标准形式：线性规划问题的标准形式： s.ts.t 其中其中（2 2） （3 3）p线性规划的标准形式线性规划的标准形式（1 1）31l紧凑格式：紧凑格式： s.ts.t. .l向量格式：向量格式： s.ts.t. . 其中其中 称为价值向量，称为价值向量， 为决为决策变量向量，策变量向量， 为

28、决策变量为决策变量x xj j所对应的消耗系数所对应的消耗系数向量，向量， 为资源向量。为资源向量。32l矩阵格式：矩阵格式：其中其中为为mn阶矩阶矩阵阵 为价值向量，为价值向量， 为决策变量向量，为决策变量向量， 为资源向量。为资源向量。33n非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化（1 1）极大化与极小化）极大化与极小化 ： 若若 ，令，令 ，则有，则有 原目标函数原目标函数 。(2)(2)线性不等式与线性等式：线性不等式与线性等式： 其中其中 为非负松弛变量，为非负松弛变量， 其中其中 为非负剩余变量。为非负剩余变量。 34 (4) (4) 非负变量与符号不受限制的变

29、量非负变量与符号不受限制的变量 若若 x xi i的符号不受限制，则可引进非负变量的符号不受限制，则可引进非负变量x xi1i1,x,xi2i2，令，令 x xi i = x= xi1i1-x-xi2i2，这样就可以使线性规划里所有的变量都转化为有非负限这样就可以使线性规划里所有的变量都转化为有非负限制的变量。制的变量。 (3) (3) 右端项为负右端项为负 约束两端乘以（约束两端乘以（1 1）35例例7 7，将下述线性规划问题化为标准型，将下述线性规划问题化为标准型 解：解：令令, ,其中其中符号不受限制符号不受限制符号不受限制符号不受限制36考虑一个标准的线性规划问题：考虑一个标准的线性规

30、划问题： s.t s.t 其中为其中为n n维行向量，维行向量， 是是n n维列向量，维列向量， 是是m m维列向量，维列向量， 是是mnmn阶矩阵，假定满足阶矩阵，假定满足mnmn，且，且( ()=m)=m，p标准型线性规划的解的概念标准型线性规划的解的概念37 线性规划问题解的概念：线性规划问题解的概念： (1) (1) 可行解可行解。满足约束条件的解。满足约束条件的解可行解集称为线性规划问题的可行域。可行解集称为线性规划问题的可行域。(2) (2) 最优解最优解。使目标函数达到最优值的的可行解称为最优解，。使目标函数达到最优值的的可行解称为最优解，最优解常用最优解常用 表示。表示。(3)

31、 (3) 基基。若是中。若是中mmmm阶非奇异矩阵，即阶非奇异矩阵，即| |0|0，则称是则称是线性规线性规划问题的一个基。划问题的一个基。 38基向量，基变量基向量，基变量若是线性规划问题的一个基，那么一定是由若是线性规划问题的一个基，那么一定是由m m个线性无关的列向量组成，不失一般性，可设个线性无关的列向量组成，不失一般性，可设 称称 为为基向量基向量，与基向量相对应的变量称为与基向量相对应的变量称为基变量基变量。基的个数基的个数一个线性规划的基通常不是唯一的，但是一个线性规划的基通常不是唯一的，但是基的个数基的个数不会超不会超过过 个。个。39( (4) 4) 基本解基本解。设。设B

32、B是线性规划的一个基，若令是线性规划的一个基，若令n-mn-m个非基变量等于个非基变量等于0 0，则所得的方程组，则所得的方程组=b=b的解称为线性规划问题的一个的解称为线性规划问题的一个基本解基本解（简称基解）。（简称基解）。基本解的个数也不会超过基本解的个数也不会超过 个。个。 由于基本解中的非零分量可能是负数，所以基本解不一定是可由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。行的。(5) (5) 基本可行解基本可行解。满足非负条件的基本解称为基本可行解。满足非负条件的基本解称为基本可行解 （简称基可行解）。（简称基可行解）。与基本可行解对应的基称为与基本可行解对应的基称为可

33、行基可行基。 基本可行解的非零向量的个数小于等于基本可行解的非零向量的个数小于等于m m，并且都是并且都是非负非负的。的。当基本可行解中有一个或多个当基本可行解中有一个或多个基变量取零值基变量取零值时，称此解为时，称此解为 退化的基本可行解退化的基本可行解。40 一个线性规划问题，如果它的一个线性规划问题，如果它的所有基本可行解所有基本可行解都是都是非退化非退化的，那么的，那么 称这个线性规划是称这个线性规划是非退化非退化的的. . 对对非退化线性规划非退化线性规划，可行基和基本可行解之间，可行基和基本可行解之间是是一一对应一一对应的。的。 41 线性规划问题各种解的关系可用文氏图表示，线性规

34、划问题各种解的关系可用文氏图表示， 可行解基基本本解解基本可行解42例例8 8、求下列约束方程所对应的线性规划的所有基本解，、求下列约束方程所对应的线性规划的所有基本解， 基本可行解。基本可行解。 s.t s.t 解：化为标准形式解：化为标准形式 为为2424阶矩阵。阶矩阵。 且且R(A)=2,R(A)=2,所以该线性规划基的个数所以该线性规划基的个数 =6=6个个 取取 , , 为基变量，为基变量， 若令非基变量若令非基变量 ， 约束方程组为约束方程组为 可得对应的基本解可得对应的基本解 是一个基本可行解。是一个基本可行解。 43按相同步骤，可求得线性规划其他按相同步骤，可求得线性规划其他4

35、 4个基个基：对应基本解对应基本解是一个基本可行解。是一个基本可行解。 对应基本解对应基本解是一个基本可行解。是一个基本可行解。 对应基本解对应基本解不是一个基本可行解。不是一个基本可行解。 对应基本解对应基本解是一个基本可行解。是一个基本可行解。 44若利用图解法画出线性规划的可行域，如图，若利用图解法画出线性规划的可行域，如图，CDOBA44845p 线性规划的基本理论线性规划的基本理论 由图解法的步骤，可以从几何的角度得出结论：由图解法的步骤，可以从几何的角度得出结论：（1 1）线性规划问题的可行域是一个有界或无界的凸多边）线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限

36、个。形，其顶点个数是有限个。（2 2）若线性规划问题有最优解，那么最优解一定可在可）若线性规划问题有最优解，那么最优解一定可在可行域的某个顶点上找到。行域的某个顶点上找到。46引理引理1 1：若线性规划问题存在可行域，则其可行域：若线性规划问题存在可行域，则其可行域是一个凸集。是一个凸集。证明：为了证明满足证明：为了证明满足= =，0 0的所有点（可行解）组成的几何体的所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点连线上的一切点均满是凸集，只要证明中任意两点任意两点连线上的一切点均满足线性约束条件既可。足线性约束条件既可。任取，满足任取，满足则对任意的有则对任意的有n 线性规划

37、的基本定理线性规划的基本定理 又因为均又因为均0 0，所以，所以由此可知，即是凸集。由此可知，即是凸集。47证明：证明：必要性必要性：因为是：因为是基本解基本解，由基本解的定义，的非零分量所，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是对应的系数列向量线性无关，又因为是可行解可行解，由基本可行解的定，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。关。 充分性充分性：设是线性规划问题的：设是线性规划问题的可行解可行解，且正分量，且正分量所对应的列向量也所对应的列向量也线性无关线性无关，则必

38、有，则必有kmkm, ,若若k=mk=m，则，则刚好构成一个基，为相应的基本刚好构成一个基，为相应的基本可行解。若可行解。若kmkm，则由线性代数知识，一定可以从其余的，则由线性代数知识，一定可以从其余的n-kn-k个系数列个系数列向量中取出向量中取出m-km-k个与构成最大线性无关向量组，其对应的个与构成最大线性无关向量组，其对应的基本可行解基本可行解恰好为，不过此时的是一个退化的基本可行解。恰好为，不过此时的是一个退化的基本可行解。 定理定理1 1：线性规划问题的可行解：线性规划问题的可行解 是基本是基本可行解的充要条件是的正分量所对应的系数列向量线性无可行解的充要条件是的正分量所对应的系

39、数列向量线性无关。关。48 定理定理2 2：设线性规划问题的可行域：设线性规划问题的可行域，则是的一个，则是的一个 顶点顶点的充分必要条件是为线性规划问题的的充分必要条件是为线性规划问题的基本可行解基本可行解。 证明思路：证明思路：必要性必要性：由定理：由定理1 1，若，若X X是是D D的一个的一个顶点顶点，要证，要证明明X X是线性规划的一个是线性规划的一个基本可行解基本可行解，只要证明的正分量，只要证明的正分量所对应的系数列向量所对应的系数列向量线性无关线性无关。 用用反证法反证法，倘若的正分量所对应的系数列向量，倘若的正分量所对应的系数列向量线性相关线性相关，令，令49的基变量所对应的

40、系数列向量的基变量所对应的系数列向量的基变量所对应的系数列向量的基变量所对应的系数列向量线性相关线性相关线性相关线性相关，与与与与X X是基本可行解矛盾。是基本可行解矛盾。是基本可行解矛盾。是基本可行解矛盾。充分性充分性：若是线性规划的一个：若是线性规划的一个基本可行解基本可行解，要证明，要证明是可行域的一个是可行域的一个顶点。顶点。反证法反证法，设不是可行域的顶点，设不是可行域的顶点 ，50 定理定理3 3：若可行域：若可行域D D非空非空，那么一定存在，那么一定存在D D的的顶点顶点（极点（极点) )。 若线性规划问题存在若线性规划问题存在可行解可行解，则一定存在，则一定存在基本可行解基本

41、可行解。 证明思路：证明思路：为可行解。为可行解。若前若前k列线性无关，则为基本可行解。列线性无关，则为基本可行解。若相关，则若相关，则选择充分小选择充分小 使使 至少有一个为至少有一个为0，其余，其余 。得到新可行解，非零分量减少一个。重复，直到线性无关为止。得到新可行解，非零分量减少一个。重复，直到线性无关为止。51证明思路：证明思路：为最优解。为最优解。若前若前k列线性无关，则为基本可行解，证毕。列线性无关，则为基本可行解，证毕。若否，则如定理若否，则如定理3，作，作 ， 为可行解。为可行解。选择充分小选择充分小 使使 至少有一个为至少有一个为0，其余，其余 。得到新最优解，非零分量减少一个。重复，直到线性无关为止。得到新最优解，非零分量减少一个。重复，直到线性无关为止。定理定理4 4：若线性规划问题存在：若线性规划问题存在最优解最优解，则必存在，则必存在基基本可行解本可行解是是最优解最优解。52练习：1、将下面线性规划化为标准形式并用图解法求解。2、用求全部基可行解的方法求解下列线性规划。53