许香敏最优化方法.ppt

《许香敏最优化方法.ppt》由会员分享，可在线阅读，更多相关《许香敏最优化方法.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化方法许香敏许香敏中国石油大学数理系中国石油大学数理系Email:Email:xuxalumni.sfu.caxuxalumni.sfu.ca课程网页：课程网页：www.sfu.ca/xxub/gradoptimizationwww.sfu.ca/xxub/gradoptimization序序研究内容：在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法研究目的：主要解决最优计划、最优分配、最 优决策、最佳设计、最佳管理等最优化问题。应用领域：科学工程、国防、交通、管理、经济、金融、计算机等。1.1.最优化方法概述最优化方法概述2最优化方法(Optimization Techn

2、iques)隶属于运筹学.运筹学（Operations Research）是用数学方法研究各种系统的最优化问题，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。数学规划又包括线性规划，整数规划，非线性规划，目标规划和动态规划等，是运筹学的主要内容.一些背景知识3 运筹学这一名词最早出现于1938年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如()防空雷达的布置问题：()护航舰队的编队问题：为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为“Operation

3、al Research”，其他英语国家称为“Operations Research”，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。4二次大战以后，在军事运筹小组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。1947年美国数学家G.B.Dantzig在研究美国空军资源配置时,提出了求解线性规划的有效方法单纯形法。二十世纪五十年代初，应用计算机求解线性规划获得成功。至五十年代末，一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六

4、十年代中期，运筹学开始应用于一些服务性行业和公用事业。5我国运筹学的研究始于五十年代中期我国运筹学的研究始于五十年代中期，当时由，当时由钱学森钱学森教教授将运筹学从西方国家引入我国，以授将运筹学从西方国家引入我国，以华罗庚华罗庚教授为首的一大教授为首的一大批科学家在有关企事业单位积极推广和普及运筹学方法，在批科学家在有关企事业单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设和邮电等行业都有不少应建筑，纺织，交通运输，水利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我国年轻的数学用。关于邮递员投递的最佳路线问题就是由我国年轻的数学家家管梅谷管梅谷于于196219

5、62年首先提出的，在国际上统称为中国邮递员年首先提出的，在国际上统称为中国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。界水平。62.学习本课程所需的数学知识向量、向量的模（范数）、向量的运算、线性相关与无关、基.矩阵的运算及性质、矩阵的秩、特征值、正定性。向量函数、连续性、可微性、梯度、海森矩阵、向量函数（多元函数）的Taylor定理 73.课程基本内容：课程基本内容：线性规划线性规划无约束最优化方法无约束最优化方法约束最优化方法约束最优化方法多目标最优化方法多目标最优化方法84.学习要求及考评掌握主要的优化模型的数学计

6、算方法.了解现代优化方法及其数学原理.熟练掌握应用数学软件计算优化问题.最终成绩最终成绩 （讨论待定）（讨论待定）=作业作业 30%+30%+期末期末 70%?70%?=作业作业 30%30%+论文论文 70%70%？=作业作业 30%+30%+论文论文 30%+30%+期末期末 30%30%？95.参考书目主要参考书目：主要参考书目：理论方面：理论方面：(1)陈宝林，陈宝林，最优化理论与算法最优化理论与算法（第（第2版），版），清华大学出版社清华大学出版社,2005(2)何坚勇，何坚勇，最优化方法最优化方法,清华大学出版社，清华大学出版社，2007计算方面：计算方面：(3)曹卫华，郭正，曹卫

7、华，郭正，最优化技术方法及最优化技术方法及MATLAB的实现的实现，化学工业出版社，化学工业出版社，2005(4)朱德通，朱德通，最优化模型与实验最优化模型与实验,同济大学出版社，同济大学出版社，2003 10第一讲第一讲 线性规划的基本概念线性规划的基本概念l 线性规划问题及其数学模型线性规划问题及其数学模型l 线性规划的图解法线性规划的图解法l 线性规划问题的标准型线性规划问题的标准型l 标准型线性规划的解标准型线性规划的解l 线性规划的基本原理线性规划的基本原理1.1.问题的提出：问题的提出：在在生生产产管管理理的的经经营营活活动动中中，通通常常需需要要对对“有有限限的的资资源源”寻求寻

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

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

10、市场需求调查的结果，甲药品每周的产量不应超元。但根据市场需求调查的结果，甲药品每周的产量不应超过过4 4吨。问该厂应如何安排两种药品的产量才能使每周获得吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？的利润最大？定义定义:x1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。目标：目标：要使总利润最大化要使总利润最大化maxz=5x1+2x2约束：约束：每周资源总量的限制，每周资源总量的限制，30 x1+20 x21605x1+x215甲种药品每周产量不应超过甲种药品每周产量不应超过4吨的限制吨的限制x14计划生产数

11、不可能是负数，计划生产数不可能是负数，x10 x20每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量甲甲乙乙维生素维生素（公斤）（公斤）3020160设备设备（台）（台）5115单位利润单位利润(万元万元)5数学模型为数学模型为每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）3020160设备（台）设备（台）5115单位利润单位利润(万元万元)5这是一个如何合理的使用有限的资源，使生产经营的效益达到最这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。大的数学规划问题。在满足一组约束条件的限制下，寻求在满足一组约束条件的限

12、制下，寻求决策变量决策变量x1，x2的决策值，的决策值，使目标函数达到最大值。使目标函数达到最大值。例例：某某化化工工厂厂根根据据一一项项合合同同要要求求为为用用户户生生产产一一种种用用甲甲、乙乙两两种种原原料料混混合合配配制制而而成成的的特特种种产产品品。已已知知甲甲、乙乙两两种种原原料料都都含含有有A A、B B、C C三三种种化化学学成成分分，两两种种原原料料分分别别所所含含三三种种化化学学成成分分的的百百分分比比含含量量，以以及及按按合合同规定的产品中三种化学成分的最低含量如下表所示：同规定的产品中三种化学成分的最低含量如下表所示：已已知知甲甲、乙乙两两种种原原料料的的成成本本分分别别

13、是是每每公公斤斤3 3元元和和2 2元元，厂厂方方希希望望总成本达到最小，问如何配置该产品？总成本达到最小，问如何配置该产品？原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化学成分化学成分定义定义x1，x2分别为每公斤产品中甲，乙两种原料的数量，分别为每公斤产品中甲，乙两种原料的数量，目标：目标：使总成本最小化使总成本最小化minz=3x1+2x2约束：约束：配料平衡条件，配料平衡条件，x1+x2=1产品中产品中A、B、C三种化学成分的最低含量三种化学成分的最低含

14、量12x1+3x242x1+3x223x1+15x25非负性条件非负性条件x10,x20 原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分数学模型：数学模型：原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分这这是是一一个个原原料料配配制制问问题题，是是

15、在在生生产产任任务务确确定定的的条条件件下下，合合理的组织生产，使所消耗的资源数最少的数学规划问题。理的组织生产，使所消耗的资源数最少的数学规划问题。满满足足一一组组约约束束条条件件的的同同时时，寻寻求求变变量量x1和和x2的的值值使使目目标标函函数取得最小值。数取得最小值。例例:某某铁铁器器加加工工厂厂要要制制作作100100套套钢钢架架，每每套套要要用用长长为为2.92.9米米，2.12.1米米和和1.51.5米米的的圆圆钢钢各各一一根根。已已知知原原料料长长为为7.47.4米米，问问应应如如何何下下料料，可可使使材材料料最省？最省？分分析析：在在长长度度确确定定的的原原料料上上截截取取三

16、三种种不不同同规规格格的的圆圆钢钢，可可以以归归纳纳出出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 问题归纳为问题归纳为如何混合使用这如何混合使用这8 8种不同的下料方案，来制造种不同的下料方案，来制造100100套套钢架，且要使剩余的余料总长为最短。钢架，且要使剩余的余料总长为最短。设设表示

17、用第表示用第j 种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,2,8,目标：目标：使余料总长度最小化使余料总长度最小化min z=0 x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8约束：约束：三种规格圆钢根数三种规格圆钢根数x1+2x2+x4+x6=1002x3+2x4+x5+x6+3x7=1003x1+x2+2x3+3x5+x6+4x8=100非负取整条件非负取整条件xj0(j=1,28)且取整数且取整数圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 3

18、0 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 数学模型数学模型s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x1至至x8的值的值,使目标函数取得最使目标函数取得最小值。小值。圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 0

19、2 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且为整数且为整数 与规划问题有关的数学模型总有两部分组成：与规划问题有关的数学模型总有两部分组成：l约束条件：约束条件：反映了有限资源对生产经营活动的种种约束，反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；或者生产经营必须完成的任务；l目标函数目标函数：反映生产经营者在有限资源条件下希望达到：反映生产经营者在有限资源条件下希望达到的生产或经营的目

20、标。的生产或经营的目标。2.2.线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1）用一组）用一组决策变量决策变量x1，x2，,xn表示某一方案，且在一般情况下，表示某一方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2）有一个）有一个目标函数目标函数，这个目标函数可表示为这组变量的，这个目标函数可表示为这组变量的线性线性函数。函数。（3）存在若干个）存在若干个约束条件约束条件，约束条件用决策变量的线性等式或线，约束条件用决策变量的线性等式或线性不等式来表达。性不等式来表达。（4）要求目标函数）要求目标函数实现最大化实现最大化（max）或

21、或最小化最小化（min）。）。满足上述满足上述4个特征的规划问题称为个特征的规划问题称为线性规划问题。线性规划问题。通常称通常称 为为决策变量决策变量，为为价值系数价值系数，为为消耗系数消耗系数,为为资源限制系数资源限制系数。线性规划的模型的一般形式线性规划的模型的一般形式:目标函数目标函数 满足约束条件满足约束条件min(max)min(max)1.2 1.2 线性规划的图解法线性规划的图解法 适用于适用于求解两个变量求解两个变量的线性规划问题的线性规划问题1.1.图解法的基本步骤图解法的基本步骤例例4 4:利用例利用例1 1说明图解法的主要步骤，说明图解法的主要步骤，例例1 1的数学模型为

22、的数学模型为O51015x1x1=4x2101AB(2,5)Cz5x1+x2=1530 x1+20 x2=1605x1+2x2=5 线性规划图解法的基本步骤线性规划图解法的基本步骤（1）建立以）建立以x1,x2为坐标轴的直角坐标系，画出线性规划问题为坐标轴的直角坐标系，画出线性规划问题的的可行域可行域,（2）求目标函数）求目标函数z=C1x1+C2x2的的梯度梯度z=（c1,c2）,（3）任取任取等值线等值线C1x1+C2x2=z0,沿梯度沿梯度z正方向平移正方向平移,（若是极小化问题，则沿（若是极小化问题，则沿负梯度方向负梯度方向z平移），平移），求等直线将离未离可行域时与可行域的交点。求等

23、直线将离未离可行域时与可行域的交点。（4）若交点存在，则该点坐标就是最优解）若交点存在，则该点坐标就是最优解X*。例如：max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2282.2.图解法的几种可能结果图解法的几种可能结果 (1(1）有）有唯一最优解唯一最优解，如例，如例1 1 则目标函数等值线则目标函数等值线10 x1+2x2=z 与第二约束与第二约束 5x1+x215 的的边边界界线线平平行行。将将等等值值线线沿沿梯梯度度z=（10，2）正正方方向向平平移至移至B点时与可行域点时与可行域OABC的整条边界线的整条边界

24、线AB重合。重合。这这表表明明线线段段AB上上的的每每一一点点都都使使目目标标函函数数取取得得同同样样的的最最大值，因而都是最优解。大值，因而都是最优解。（2）有）有无穷多最优解无穷多最优解 如例如例1中的目标函数设为中的目标函数设为:max z=10 x1+2x2 例例5 5:试用图解法求解下列线性规划问题试用图解法求解下列线性规划问题（3 3）无界解无界解（或称无最优解）（或称无最优解）无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值若是极大化问题，则可使目标函数值z+,z+,极小化问题极小化问题 则可使目标函数值则可使目标函数值z-

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

26、无界解（或称无最优解）（或称无最优解）无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值若是极大化问题，则可使目标函数值z+,z+,极小化问题极小化问题 则可使目标函数值则可使目标函数值z-z-，有无界解的线性规划问题的可行域通常是有无界解的线性规划问题的可行域通常是无界区域，但反之则不必然。无界区域，但反之则不必然。1.1.标准线性规划模型标准线性规划模型 (1)线性规划问题的线性规划问题的标准形式标准形式：其其中中(1.1)(1.1)为为目目标标函函数数，(1.2)(1.2)为为约约束束条条件件，(1.3)(1.3)为为非非负负条条件件

27、，为称呼方便，有时将，为称呼方便，有时将(1.3)(1.3)也称为约束条件。也称为约束条件。（1.21.2）（1.31.3）1.3线性规划的标准形式线性规划的标准形式（1.11.1）其其中中C=(c1,c2,cn)称称为为价值向量价值向量，X=(x1,x2,xn)T为决策变量向量，为决策变量向量，Pj=(a1j,x2j,xmj)T为为决决策策变变量量xj所所对对应应的消耗系数向量的消耗系数向量，b=(b1,b2,bm)T为为资源向量资源向量。(2)紧凑格式：紧凑格式：(3)向量格式：向量格式：其中其中为为mn阶矩阵阶矩阵 (4)矩阵格式：矩阵格式：C=(c1,c2,cn)，X=(x1,x2,x

28、n)T，b=(b1,b2,bm)T。352.2.非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化（1 1）极大化与极小化）极大化与极小化 ：原目标函数原目标函数(2)(2)线性不等式与线性等式：线性不等式与线性等式：其中其中xn+i为非负为非负松弛变量松弛变量，其中其中xn+k为非负为非负剩余变量剩余变量。(3)非负变量与符号不受限制的变量非负变量与符号不受限制的变量若若xi的符号不受限制，则可的符号不受限制，则可引进非负变量引进非负变量xi1,xi2，令，令xi=xi1-xi2，使线性规划里所有的变量都转化为有非负限，使线性规划里所有的变量都转化为有非负限制的变量。制的变量。(4

29、)右端项有负值的问题：右端项有负值的问题：在在标标准准形形式式中中，要要求求右右端端项项必必须须每每一一个个分分量量非非负负。当当某某一一个个右右端端项项系系数数为为负负时时，如如bi0，则则把把该该等等式式约约束束两两端同时乘以端同时乘以1，得到：，得到：ai1 x1ai2 x2ain xn=bi。37例例6 6:将下述线性规划问题化为标准型将下述线性规划问题化为标准型 符号不受限制符号不受限制符号不受限制符号不受限制解解:令令,可将目标函数化为可将目标函数化为min型，型，令令,其中其中38考虑一个标准的线性规划问题：考虑一个标准的线性规划问题：1.4标准型线性规划的解标准型线性规划的解其

30、中其中为为n维行向量，维行向量，是是n维列向量，维列向量，是是m维列向量，维列向量，是是mn阶矩阵，假定满足阶矩阵，假定满足mn，且，且()=m.39(2)(2)最优解最优解:使目标函数（使目标函数（1.4)1.4)达到最优值的的可行解称为最优解，达到最优值的的可行解称为最优解，最优解常用最优解常用X*表示。表示。(3)基基:若若是是中中mm阶非奇异矩阵，即阶非奇异矩阵，即|0，则称是线性规则称是线性规划问题的一个基。划问题的一个基。可行解集可行解集 称为线性规划问题的称为线性规划问题的可行域可行域。线性规划问题解的概念：线性规划问题解的概念：(1)(1)可行解可行解:满足约束条件满足约束条件

31、(1.5)(1.5)，(1.6)(1.6)的解的解称为线性规划问题的可行解。称为线性规划问题的可行解。40一个线性规划的基通常不是唯一的，一个线性规划的基通常不是唯一的，但是基的个数也不会超过但是基的个数也不会超过Cnm个。个。一旦确定了线性规划的基，则相应的基向量、基变量和非基变量也就确定。一旦确定了线性规划的基，则相应的基向量、基变量和非基变量也就确定。若是线性规划问题的一个基，那么若是线性规划问题的一个基，那么一定是由一定是由m个线性无关的列个线性无关的列向量组成向量组成，不失一般性，可设，不失一般性，可设称称为为基向量基向量，与基向量与基向量Pj相对应的变量相对应的变量xj(j=1,2

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

33、基本解称为基本可行解的基本解称为基本可行解(简称简称基可行解基可行解)。与基本可行解对应的基成为与基本可行解对应的基成为可行基可行基。基本可行解的非零向量的个数小于等于基本可行解的非零向量的个数小于等于m，并且都是非负的。并且都是非负的。由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要少于基的数目。少于基的数目。当基本可行解中有一个或多个基变量是取零值时，称此解为当基本可行解中有一个或多个基变量是取零值时，称此解为退化的基本可行解退化的基本可行解。42 线性规划问题各种解的关系可用文氏图表示，线性规划问题各种解的关系可

34、用文氏图表示，可行解基基本本解解基本可行 解43例例7 7：求下列约束方程所对应的线性规划的所有基本解，基本可行解。：求下列约束方程所对应的线性规划的所有基本解，基本可行解。解：解：化为标准形式后化为标准形式后 为为2 24 4阶矩阵。阶矩阵。且且R(A)=2,R(A)=2,所以该线性规划基的个数所以该线性规划基的个数 =6=6个个 若令非基变量若令非基变量 ，约束方程组为约束方程组为 可得对应的基本解可得对应的基本解 是一个基本可行解。是一个基本可行解。x1,x2为基变量，为基变量，44对应基本基本解对应基本基本解对应基本基本解对应基本基本解对应基本基本解对应基本基本解按相同步骤，可求得线性

35、规划其他按相同步骤，可求得线性规划其他4 4个基个基：对应基本基本解对应基本基本解45若利用图解法画出线性规划的可行域，如图，若利用图解法画出线性规划的可行域，如图，COBA448461.51.5 线性规划的基本原理线性规划的基本原理 由由图图解解法法的的步步骤骤，可可以以从从几几何何的的角角度度得得出出以以下下两两个个结论：结论：（1 1）线性规划问题的可行域是一个有界或无界的）线性规划问题的可行域是一个有界或无界的凸多边凸多边形形，其，其顶点个数是有限顶点个数是有限个。个。（2 2）若线性规划问题有最优解，那么）若线性规划问题有最优解，那么最优解一定可在可最优解一定可在可行域的某个顶点行域

36、的某个顶点上找到。上找到。47（1）凸凸集集：设设K是是n维维欧欧式式空空间间的的一一个个点点集集，若若任任意意两两点点X(1)K,X(2)K的连线上的一切点的连线上的一切点X(1)+(1-)X(2)K(01),则称则称K为凸集。为凸集。n1.1.几个基本概念几个基本概念 线性约束条件线性约束条件凸集例顶点个数有限有限无限有限无限非凸集例48（1）凸凸集集：设设K是是n维维欧欧式式空空间间的的一一个个点点集集，若若任任意意两两点点X(1)K,X(2)K的连线上的一切点的连线上的一切点X(1)+(1-)X(2)K(01),则称则称K为凸集。为凸集。n1.1.几个基本概念几个基本概念 连接几何形体

37、中任意两点的线段仍完全在该几何形体之中。连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。线性约束条件线性约束条件凸集定义的几何解释凸集定义的几何解释49（2）凸凸组组合合：设设X(1)，X(2)，X(k)是是n维维欧欧式式空空间间En中中的的k个个点点，若若存存在在1,2,k满满足足0i1,(i=1,2,k),且且1+2+k=1，使使X=1X(1)+2X(2)+k X(k)，则称则称X为为X(1)，X(2)，X(k)的的凸组合凸组合。凸组合的几何意义凸组合的几何意义凸凸集集K中中任任意意两两点点X(1)，X(2)连连线线上上的的任任一

38、一点点X都都是是X(1)与与X(2)的一个凸组合。的一个凸组合。50X X(1)(1)X X(3)(3)X X(2)(2)XXX=X=XX+(1-+(1-)X)X(2)(2)，(0(0 1)1)x x1 1x x2 2OOX=X=XX(1)(1)+(1-+(1-)X)X(3)(3)，(0(0 1)1)51X X(1)(1)X X(3)(3)X X(2)(2)XXX=uX=u1 1X X(1)(1)+u+u2 2X X(2)(2)+u+u3 3X X(3)(3)x x1 1x x2 2OOX=X=XX(1)(1)+(1-+(1-)X)X(3)(3)，(0(0 1)1)52（2）凸凸组组合合：设设

39、X(1)，X(2)，X(k)是是n维维欧欧式式空空间间En中中的的k个个点点，若若存存在在1,2,k满满足足0i1,(i=1,2,k),且且1+2+k=1，使使X=1X(1)+2X(2)+k X(k)，则则称称X为为X(1)，X(2)，X(k)的的凸组合凸组合。凸凸集集K中中任任意意两两点点X(1)，X(2)连连线线上上的的任任一一点点X都都是是X(1)与与X(2)的一个凸组合。的一个凸组合。(3)顶顶点点：设设K为为凸凸集集，XK,若若X不不能能用用X(1)K,X(2)K两两点点(X(1)X(2)的的一一个个凸凸组组合合表表示示为为X=X(1)+(1-)X(2),其其中中01，则称，则称X为

40、为K的的一个一个顶点顶点。或或若若凸凸集集K中中的的点点X不不能能成成为为K中中任任何线段的内点，则称何线段的内点，则称X为为K的一个顶点。的一个顶点。53定理定理1：若线性规划问题存在可行域，则其可行域若线性规划问题存在可行域，则其可行域D=X/AX=b,x0是一个凸集。是一个凸集。证明：证明：为了证明满足为了证明满足=，0 0的所有点（可行解）组成的几何体的所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点是凸集，只要证明中任意两点任意两点X(1)，X(2)连线上的一切点均连线上的一切点均满足满足线性约束条件线性约束条件既可。既可。n 2.线性规划的基本定理线性规划的基本定理

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

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

43、应的系数列向量线性无关。55定理定理2：设线性规划问题的可行域设线性规划问题的可行域，则是的一个顶点的，则是的一个顶点的充分必要条件充分必要条件是为线性规划问题的基本可行解。是为线性规划问题的基本可行解。证明思路：必要性：证明思路：必要性：由引理由引理1，若，若X是是D的一个顶点，要证明的一个顶点，要证明X是线性是线性规划的一个基本可行解，只要证明的正分量所对应的系规划的一个基本可行解，只要证明的正分量所对应的系数列向量线性无关。数列向量线性无关。用反证法用反证法，倘若的正分量所对应的系数列向量线性相关，倘若的正分量所对应的系数列向量线性相关，则可以在中找到两点，使，与是的顶点则可以在中找到两

44、点，使，与是的顶点矛盾矛盾.充分性：充分性：若是线性规划的一个基本可行解，要证明是可行域若是线性规划的一个基本可行解，要证明是可行域的一个顶点，的一个顶点，仍用反证法仍用反证法，倘若不是可行域的顶点，倘若不是可行域的顶点，可以证明的基变量，可以证明的基变量，可以证明的基变量，可以证明的基变量所对应的系数列向量线性相关，与所对应的系数列向量线性相关，与所对应的系数列向量线性相关，与所对应的系数列向量线性相关，与X X是基本可行解矛盾。是基本可行解矛盾。是基本可行解矛盾。是基本可行解矛盾。56例例8:8:已知线性规划问题的约束条件为已知线性规划问题的约束条件为 试讨论可行域顶点和基本可行解之间的对

45、应关系。试讨论可行域顶点和基本可行解之间的对应关系。解解:可行域可行域为四维凸多面体，可以推得在四维空间中有为四维凸多面体，可以推得在四维空间中有3个顶点，个顶点，=(0,0,10,10)，=(0,10,0,10)，=(10,0,0,0)。这这3个顶点与线性规划的个顶点与线性规划的5个基本可行解的对应关系如下：个基本可行解的对应关系如下：顶点对应以顶点对应以x3,x4为基变量的基本可行解；为基变量的基本可行解；顶点对应以顶点对应以x2,x4为基变量的基本可行解；为基变量的基本可行解；顶顶点点对对应应x1,x2;x1,x3和和x1,x4为为基基变变量量的的退退化化基基本本可可行行解解.57一个线

46、性规划问题，如果它的所有基本可行解都是非退化一个线性规划问题，如果它的所有基本可行解都是非退化的，那么称这个的，那么称这个线性规划是非退化线性规划是非退化的，只有在这种情况下，的，只有在这种情况下，顶点和基本可行解顶点和基本可行解之间才是一一对应的。之间才是一一对应的。定理定理3(线性规划的基本定理线性规划的基本定理):若可行域若可行域D非空有界，那么线性规划问题的目标函数非空有界，那么线性规划问题的目标函数一定可以一定可以在可行域在可行域D的顶点上达到最优值。的顶点上达到最优值。证明思路证明思路：因为可行域非空有界，所以线性规划一定有最优解，因为可行域非空有界，所以线性规划一定有最优解，倘若

47、倘若X(0)不是顶点，且目标函数在该点处取到最优值不是顶点，且目标函数在该点处取到最优值z*，则必能找到可行域的一个顶点则必能找到可行域的一个顶点X(m)，使目标函数在的值也，使目标函数在的值也等于等于z*。58定理定理3(线性规划的基本定理线性规划的基本定理):若可行域若可行域D非空有界，那么线性规划问题的目非空有界，那么线性规划问题的目标函数一定可以标函数一定可以在可行域在可行域D的顶点上达到最优值。的顶点上达到最优值。说明说明:定理定理3并不排除在一个非顶点上有一个最优解的可能性。并不排除在一个非顶点上有一个最优解的可能性。但是在一个但是在一个给定的线性规划问题的所有最优解中，至少给定的

48、线性规划问题的所有最优解中，至少有一个是顶点。有一个是顶点。如果可行域无界，则线性规划问题可能无最优解。如果可行域无界，则线性规划问题可能无最优解。如果目标函数同时在两个顶点上达到最优解，那么不难如果目标函数同时在两个顶点上达到最优解，那么不难证明在这两个证明在这两个点的凸组合上也达到最优解，这时线性规点的凸组合上也达到最优解，这时线性规划问题有无穷多最优解。划问题有无穷多最优解。59定理定理1 1：若线性规划问题存在可行域，则其可行域若线性规划问题存在可行域，则其可行域是一个凸集。是一个凸集。定理定理2：设线性规划问题的可行域设线性规划问题的可行域，则是的一个，则是的一个顶点的顶点的充分必要条件充分必要条件是为线性规划问题的基本可行解。是为线性规划问题的基本可行解。定理定理3：若可行域若可行域D非空有界，那么线性规划问题的目标非空有界，那么线性规划问题的目标函数一定可以函数一定可以在可行域在可行域D的顶点上达到最优值。的顶点上达到最优值。60LinearProgramminginMATLAB61