1、最优化方法孔翔宇孔翔宇北方民族大学数学与信息科学学院北方民族大学数学与信息科学学院2研究内容：在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法研究目的：主要解决最优计划、最优分配、最 优决策、最佳设计、最佳管理等最优化问题。应用领域：科学工程、国防、交通、管理、经济、金融、计算机等。1.1.最优化方法概述最优化方法概述3最优化方法(Optimization Techniques)隶属于运筹学.运筹学（Operations Research）是用数学方法研究各种系统的最优化问题，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。数学规划又包括线性规划，整数规
2、划，非线性规划，目标规划和动态规划等，是运筹学的主要内容.一些背景知识4 运筹学这一名词最早出现于1938年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如()防空雷达的布置问题：()护航舰队的编队问题：为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为“Operational Research”，其他英语国家称为“Operations Research”，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。5二次大战以后，在军事运筹小
3、组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。1947年美国数学家G.B.Dantzig在研究美国空军资源配置时,提出了求解线性规划的有效方法单纯形法。二十世纪五十年代初，应用计算机求解线性规划获得成功。至五十年代末，一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事业。672.学习本课程所需的数学知识向量、向量的模（范数）、向量的运算、线性相关与无关、基.矩阵的运算及性质、矩阵的秩、特征值、正定性。向量函数、连续性、可微性、梯
4、度、Hessen矩阵、向量函数（多元函数）Taylor定理 83.课程基本内容：课程基本内容：线性规划线性规划 无约束最优化方法无约束最优化方法 约束最优化方法约束最优化方法 多目标最优化方法（选学）多目标最优化方法（选学）动态优化方法（选学）动态优化方法（选学）94.学习要求掌握主要的优化模型的数学计算方法.了解现代优化方法及其数学原理.熟练掌握应用数学软件计算优化问题.105.参考书目主要参考书目：主要参考书目：理论方面：理论方面：(1)解可新、韩健，解可新、韩健，最优化方法最优化方法，天津大学出版社，天津大学出版社,2004(2)何坚勇，何坚勇，最优化方法最优化方法,清华大学出版社，清华
5、大学出版社，2007计算方面：计算方面：(3)马昌凤，马昌凤，最优化方法及其最优化方法及其MATLAB程序设计程序设计，科学出版社，科学出版社，2010(4)朱德通，朱德通，最优化模型与实验最优化模型与实验,同济大学出版社，同济大学出版社，2003 其它参考书：其它参考书：(5)卢名高、刘庆吉编著，卢名高、刘庆吉编著，最优化应用技术最优化应用技术，石油工业出版社，石油工业出版社,2002(6)唐焕文，秦学志唐焕文，秦学志,实用最优化方法实用最优化方法，大连理工大学出版社，大连理工大学出版社，2004(7)钱颂迪，钱颂迪，运筹学运筹学，清华大学出版社，清华大学出版社，1990(8)袁亚湘、孙文瑜
6、著，袁亚湘、孙文瑜著，最优化理论与方法最优化理论与方法，科学出版社，科学出版社，2005 第一讲第一讲 线性规划的基本概念线性规划的基本概念l 线性规划问题及其数学模型线性规划问题及其数学模型l 线性规划的图解法线性规划的图解法l 线性规划问题的标准型线性规划问题的标准型l 标准型线性规划的解标准型线性规划的解l 线性规划的基本原理线性规划的基本原理1.1.问题的提出：问题的提出：在生产管理的经营活动中，通常需要对在生产管理的经营活动中，通常需要对“有限的资源有限的资源”寻求寻求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设
7、备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达最佳：有一个标准或目标，使利润达到最大或成本达到最小。到最小。有限资源的合理配置有有限资源的合理配置有两类两类问题问题l如何合理的使用有限的资源，使生产经营的如何合理的使用有限的资源，使生产经营的效益达到效益达到最大最大；l在生产或经营的任务确定的条件下，合理的组织生产，在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所安排经营活动，使所消耗的资源数最少消耗的资源数最少。1.11.1线性规划问题及其数学模型线性规划问题及其数学模型例例:某制药厂生产甲、乙两种药品，生产这两种药品要消某制药厂生产甲、乙两种药品，生产这两种
8、药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素维生素（公斤）（公斤）30302020160160设备设备（台）（台）5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万万元。但根据市场需求调查的结果，甲药品每周的产量不应超元。但根据市场需求调查的结果，甲药品每周的产量不应超过过4 4吨。问该厂
9、应如何安排两种药品的产量才能使每周获得吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？的利润最大？定义定义:x1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。目标：目标：要使总利润最大化要使总利润最大化 max z=5x1+2x2约束：约束：每周资源总量的限制，每周资源总量的限制，30 x1+20 x2160 5x1+x2 15甲种药品每周产量不应超过甲种药品每周产量不应超过4吨的限制吨的限制 x14计划生产数不可能是负数，计划生产数不可能是负数，x10 x20每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总
10、量甲甲乙乙维生素维生素（公斤）（公斤）3020160设备设备（台）（台）5115单位利润单位利润(万元万元)5 数学模型为数学模型为121212112max =5+23020160515.40,0zxxxxxxs txxx每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）3020160设备（台）设备（台）5115单位利润单位利润(万元万元)5这是一个如何合理的使用有限的资源，使生产经营的效益达到最这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。大的数学规划问题。在满足一组约束条件的限制下，寻求在满足一组约束条件的限制下，寻求决
11、策变量决策变量x1，x2的决策值，的决策值，使目标函数达到最大值。使目标函数达到最大值。例：例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有混合配制而成的特种产品。已知甲、乙两种原料都含有A A、B B、C C三种三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤已知甲、乙两种原料
12、的成本分别是每公斤3 3元和元和2 2元，厂方希望元，厂方希望总成本达到最小，问如何配置该产品？总成本达到最小，问如何配置该产品？原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化学成分化学成分定义定义 x1，x2分别为每公斤产品中甲，乙两种原料的数量，分别为每公斤产品中甲，乙两种原料的数量，目标：目标：使总成本最小化使总成本最小化 min z=3x1+2x2约束：约束：配料平衡条件，配料平衡条件，x1+x2=1产品中产品中A、B、C三种化学成分的最低含量三种化学成
13、分的最低含量 12x1+3x24 2x1+3x22 3x1+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单位成本（元）单位成本（元）化学成分化学成分121212121212m
14、in 3211234.23231500,0zxxxxxxs txxxxxx这是一个原料配制问题，是在生产任务确定的条件下，合这是一个原料配制问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x1和和x2的值使目标函的值使目标函数取得最小值。数取得最小值。例例:某铁器加工厂要制作某铁器加工厂要制作100100套钢架，每套要用长为套钢架，每套要用长为2.92.9米，米，2.12.1米和米和1.51.5米的圆钢各一根。已知原料长为米的圆钢各一根。已知原料
15、长为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 问题归纳为问题归纳为如何混合使用这如何混合使用这8 8
16、种不同的下料方案，来制造种不同的下料方案，来制造100100套钢架，且要使剩余的余料总长为最短。套钢架，且要使剩余的余料总长为最短。设设 表示用第表示用第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=100 2x3+2x4+x5+x6+3x7=100 3x1+x2+2x3+3x5+x6+4x8=100非负取整条件非负取整条件 xj0(j=1,28)
17、且取整数且取整数圆钢（米）圆钢（米）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.4jx 数学模型数学模型 s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时
18、，寻求变量x1至至x8的值的值,使目标函数取得最使目标函数取得最 小值。小值。2345678124634567 123568min 0.10.20.30.80.91.11.42 100 22 3 10032 3 4 100 0 1,2jzxxxxxxxxxxxxxxxxxxxxxxxj，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.
19、4且为整数且为整数 与规划问题有关的数学模型总有两部分组成：与规划问题有关的数学模型总有两部分组成：l约束条件：约束条件：反映了有限资源对生产经营活动的种种约束，反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；或者生产经营必须完成的任务；l目标函数目标函数：反映生产经营者在有限资源条件下希望达到：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。的生产或经营的目标。2.2.线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1）用一组）用一组决策变量决策变量x1，x2，,xn表示某一方案，且在一般情况下，表示某一方案，且在一般情况
20、下，变量的取值是非负的。变量的取值是非负的。（2）有一个）有一个目标函数目标函数，这个目标函数可表示为这组变量的，这个目标函数可表示为这组变量的线性线性函数。函数。（3）存在若干个）存在若干个约束条件约束条件，约束条件用决策变量的线性等式或线，约束条件用决策变量的线性等式或线性不等式来表达。性不等式来表达。（4）要求目标函数）要求目标函数实现最大化实现最大化（max）或）或最小化最小化（min）。）。满足上述满足上述4个特征的规划问题称为个特征的规划问题称为线性规划问题。线性规划问题。121212112max =5+23020160515.40,0zxxxxxxs txxx通常称通常称 为为决
21、策变量决策变量，为为价值系数价值系数，为为消耗系数消耗系数,为为资源限制系数资源限制系数。线性规划的模型的一般形式线性规划的模型的一般形式:目标函数目标函数 满足约束条件满足约束条件nnxcxcxcz 2211 0,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxatsnxxx,21nccc,211112,mnaaambbb,211.2 1.2 线性规划的图解法线性规划的图解法 适用于适用于求解两个变量求解两个变量的线性规划问题的线性规划问题1.1.图解法的基本步骤图解法的基本步骤例例4 4:利用例利用例1 1
22、说明图解法的主要步骤，说明图解法的主要步骤，例例1 1的数学模型为的数学模型为2125maxxxz 0,41551602030.2112121xxxxxxxtsO51015x1x1=4x2101AB(2,5)Cz5x1+x2=1530 x1+20 x2=1605x1+2x2=5z 2125maxxxz 0,41551602030.2112121xxxxxxxts)2,5(,21 xzxzz 线性规划图解法的基本步骤线性规划图解法的基本步骤（1）建立以）建立以x1,x2为坐标轴的直角坐标系，画出线性规划问题为坐标轴的直角坐标系，画出线性规划问题 的的可行域可行域,（2）求目标函数）求目标函数 z
23、=C1x1+C2x2 的的梯度梯度z=（c1,c2）,（3）任取）任取等值线等值线 C1x1+C2x2=z0,沿梯度沿梯度z正方向平移正方向平移,（若是极小化问题，则沿（若是极小化问题，则沿负梯度方向负梯度方向z平移），平移），求等直线将离未离可行域时与可行域的交点。求等直线将离未离可行域时与可行域的交点。（4）若交点存在，则该点坐标就是最优解）若交点存在，则该点坐标就是最优解X*。28例如：max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x21213zzzxx，（，）2.2.图解法的几种可能结果图解法的几种可能结果 (1
24、(1）有）有唯一最优解唯一最优解，如例，如例1 1 则目标函数等值线则目标函数等值线10 x1+2x2=z 与第二约束与第二约束 5x1+x215 的边界线平行。将等值线沿梯度的边界线平行。将等值线沿梯度z=（10，2）正方向平）正方向平移至移至B点时与可行域点时与可行域OABC的整条边界线的整条边界线AB重合。重合。这表明线段这表明线段AB上的每一点都使目标函数取得同样的最上的每一点都使目标函数取得同样的最大值，因而都是最优解。大值，因而都是最优解。（2）有）有无穷多最优解无穷多最优解 如例如例1中的目标函数设为中的目标函数设为:max z=10 x1+2x2 例例5 5:试用图解法求解下列
25、线性规划问题试用图解法求解下列线性规划问题（3 3）无界解无界解（或称无最优解）（或称无最优解）无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值若是极大化问题，则可使目标函数值z+,z+,极小化问题极小化问题 则可使目标函数值则可使目标函数值z-z-，有无界解的线性规划问题的可行域通常是有无界解的线性规划问题的可行域通常是无界区域，但反之则不必然。无界区域，但反之则不必然。0,0332223min21212121xxxxxxxxz-1 O24x1x224z=(3,2)-2x1+x2=2x1-3x2=3-1 O3312-3,-2zzzxx，
26、（）0,0332223min21212121xxxxxxxxz（4）无可行解无可行解 某些线性规划问题的可行域是空集，既不存在满足所有约某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。束条件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。要求，既不存在可行方案。1.1.标准线性规划模型标准线性规划模型 (1)线性规划问题的线性规划问题的标准形式标准形式：其中其中(1.1)(1.1)为为目标函数目标函数，(1.2)(1.2
27、)为为约束条件约束条件，(1.3)(1.3)为为非负条非负条件件，为称呼方便，有时将，为称呼方便，有时将(1.3)(1.3)也称为约束条件。也称为约束条件。（1.21.2）（1.31.3）1.3 线性规划的标准形式线性规划的标准形式（1.11.1）1 12211 11221121 122222 1 122 12min.,0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx其中其中C=(c1,c2,cn)称为称为价值向量价值向量，X=(x1,x2,xn)T为为决策变量向量，决策变量向量，Pj=(a1j,x2j,xmj)T为为决策变量
28、决策变量xj所对应所对应的消耗系数向量的消耗系数向量，b=(b1,b2,bm)T为为资源向量资源向量。1min njjjzc x1.0,1,2,njjjjP xbs txjnmin zCX1,1,2,.0,1,2,nijjijja xbimstxjn(2)紧凑格式：紧凑格式：(3)向量格式：向量格式：35min 0zCXAXbX111212122212.nnmmmnaaaaaaAaaa其中其中 为为mn阶矩阵阶矩阵 (4)矩阵格式：矩阵格式：C=(c1,c2,cn)，X=(x1,x2,xn)T，b=(b1,b2,bm)T。2.2.非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化1m
29、ax njjjzc x若,-,zz则令1min min(-)-min-njjjzzzc x1max min -njjjzzc x11 nnijjiijijjn ijxa xba xb11-nnkjjkknjkjkjjxa xba xb（1 1）极大化与极小化）极大化与极小化 ：原目标函数原目标函数(2)(2)线性不等式与线性等式：线性不等式与线性等式：其中其中 xn+i 为非负为非负松弛变量松弛变量，其中其中 xn+k 为非负为非负剩余变量剩余变量。37 (3)非负变量与符号不受限制的变量非负变量与符号不受限制的变量 若若 xi的符号不受限制，则可的符号不受限制，则可引进非负变量引进非负变量x
30、i1,xi2，令，令 xi=xi1-xi2，使线性规划里所有的变量都转化为有非负限制，使线性规划里所有的变量都转化为有非负限制的变量。的变量。(4)右端项有负值的问题：右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如某一个右端项系数为负时，如 bi0，则把该等式约束两，则把该等式约束两端同时乘以端同时乘以1，得到：，得到：ai1 x1ai2 x2 ain xn=bi 。38例例6 6:将下述线性规划问题化为标准型将下述线性规划问题化为标准型 123123123123123max -2-3 7 -2 3 -
31、250,0,zxxxxxxxxxxxxxxx1245124 56124571245124567min -23-3 -7-23 -22 5,0zxxxxxxxxxxxxxxxxxxx x x x x x解解:令令,可将目标函数化为可将目标函数化为min型，型，zz 令令,其中其中345-xxx450,0.xx39考虑一个标准的线性规划问题：考虑一个标准的线性规划问题：min (1.4)(1.5).0 (1.6)zCXAXbstX1.4 标准型线性规划的解标准型线性规划的解其中其中为为n维行向量，维行向量，是是n维列向量，维列向量，是是m维列向量，维列向量，是是mn阶矩阵，假定满足阶矩阵，假定满足
32、mn，且，且()=m.40(2)(2)最优解最优解:使目标函数（使目标函数（1.4)1.4)达到最优值的的可行解称为最优解，达到最优值的的可行解称为最优解，最优解常用最优解常用X*表示。表示。(3)基基:若若是是中中mm阶非奇异矩阵，即阶非奇异矩阵，即|0，则称是线性规，则称是线性规划问题的一个基。划问题的一个基。min (1.4)zCX (1.5)0 (1.6)AXbX 可行解集可行解集 称为线性规划问题的称为线性规划问题的可行域可行域。/,0 DXAXbX线性规划问题解的概念：线性规划问题解的概念：12(,)TnXx xx (1)(1)可行解可行解:满足约束条件满足约束条件(1.5)(1.
33、5)，(1.6)(1.6)的解的解称为线性规划问题的可行解。称为线性规划问题的可行解。41一个线性规划的基通常不是唯一的，一个线性规划的基通常不是唯一的，但是基的个数也不会超过但是基的个数也不会超过 Cnm 个。个。一旦确定了线性规划的基，则相应的基向量、基变量和非基变量也就确定。一旦确定了线性规划的基，则相应的基向量、基变量和非基变量也就确定。若是线性规划问题的一个基，那么若是线性规划问题的一个基，那么一定是由一定是由m个线性无关的列个线性无关的列向量组成向量组成，不失一般性，可设，不失一般性，可设 称称 为为基向量基向量，与基向量与基向量 Pj相对应的变量相对应的变量 xj(j=1,2，m
34、)称为称为基变量基变量。11121212221212.(,).mmmmmmmaaaaaaBP PPaaa12(,),(1,2,)jjjmjpaaajm42(4)基本解基本解。设。设B是线性规划的一个基，若是线性规划的一个基，若令令n-m个非基变量等于个非基变量等于0，则，则所得的方程组所得的方程组=b的解称为线性规划问题的一个基本解（简称的解称为线性规划问题的一个基本解（简称基解基解）。）。有一个基就可以求得一个基本解。有一个基就可以求得一个基本解。由基的有限性可知，基本解的个数也不会超过由基的有限性可知，基本解的个数也不会超过Cnm 个。个。由于基本解中的非零分量可能是负数，所以基本解不一定
35、是可行的。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5)基本可行解基本可行解。满足非负条件满足非负条件的基本解称为基本可行解的基本解称为基本可行解(简称简称基可行解基可行解)。与基本可行解对应的基成为与基本可行解对应的基成为可行基可行基。基本可行解的非零向量的个数小于等于基本可行解的非零向量的个数小于等于m，并且都是非负的。，并且都是非负的。由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要少于基的数目。少于基的数目。当基本可行解中有一个或多个基变量是取零值时，称此解为当基本可行解中有一个或多个基变量
36、是取零值时，称此解为 退化的基本可行解退化的基本可行解。43 线性规划问题各种解的关系可用文氏图表示，线性规划问题各种解的关系可用文氏图表示，可行解基本解基本解基本可行 解44例例7 7：求下列约束方程所对应的线性规划的所有基本解，基本可行解。：求下列约束方程所对应的线性规划的所有基本解，基本可行解。1221228.2 ,0 xxstxx x1232412342 8 2 ,0 xxxxxx xxx11212B=(P,P),01取12341210A=(P,P,P,P)010124C8b=2 解：解：化为标准形式后化为标准形式后 为为2 24 4阶矩阵。阶矩阵。且且R(A)=2,R(A)=2,所以
37、该线性规划基的个数所以该线性规划基的个数 =6 =6个个 34x=x0122x2x8 x21(4,2,0,0)TX 若令非基变量若令非基变量 ，约束方程组为约束方程组为 可得对应的基本解可得对应的基本解 是一个基本可行解。是一个基本可行解。x1,x2为基变量，为基变量，45对应基本基本解对应基本基本解对应基本基本解对应基本基本解对应基本基本解对应基本基本解按相同步骤，可求得线性规划其他按相同步骤，可求得线性规划其他4 4个基个基：21410B=(P,P)01对应基本基本解对应基本基本解32321B=(P,P)1042420B=(P,P)1153410B=(P,P)01T5X=(0,0,8,2)
38、12341210A=(P,P,P,P)0101T2X=(8,0,0,2)T3X=(0,2,4,0)T4X=(0,4,0,-2)8b=2 46若利用图解法画出线性规划的可行域，如图，若利用图解法画出线性规划的可行域，如图，12212282 ,0 xxxx x1234(4,2,0,0),(8,0,0,2),(0,2,4,0)(0,0,8,2).XBXAXCXOCOBA4481228xx1228xx22x 471.51.5 线性规划的基本原理线性规划的基本原理 由图解法的步骤，可以从几何的角度得出以下两个由图解法的步骤，可以从几何的角度得出以下两个结论：结论：（1 1）线性规划问题的可行域是一个有界
39、或无界的）线性规划问题的可行域是一个有界或无界的凸多边凸多边形形，其，其顶点个数是有限顶点个数是有限个。个。（2 2）若线性规划问题有最优解，那么）若线性规划问题有最优解，那么最优解一定可在可最优解一定可在可行域的某个顶点行域的某个顶点上找到。上找到。48（1）凸集）凸集：设：设K是是n维欧式空间的一个点集，若任意两点维欧式空间的一个点集，若任意两点X(1)K,X(2)K的连线上的一切点的连线上的一切点X(1)+(1-)X(2)K(01),则称则称K为凸集。为凸集。n1.1.几个基本概念几个基本概念 凸集例顶点个数有限有限无限有限无限非凸集例49 连接几何形体中任意两点的线段仍完全在该几何形体
40、之中。连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。凸集定义的几何解释凸集定义的几何解释50（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)+2 X(2)+k X(k)，则称则称X为为X(1)，X(2)，X(k)的的凸组合凸组合。凸组合的几何意义凸组合的几何意义 凸集凸集K中任意两点中任意两点X(1)，X(2)连线上的任一点连线上的任一点X都是都是X(1)与与X(2)的一个凸组合
41、。的一个凸组合。515253(3)顶点顶点：设：设K为凸集，为凸集，XK,若若X不能用不能用X(1)K,X(2)K两点两点(X(1)X(2)的一个凸组的一个凸组合表示为合表示为X=X(1)+(1-)X(2),其中其中01，则称则称X为为K的一的一个个顶点顶点。或若凸集或若凸集K中的点中的点X不能成为不能成为K中任中任何线段的内点，则称何线段的内点，则称X为为K的一个顶点。的一个顶点。54定理定理1：若线性规划问题存在可行域，则其可行域若线性规划问题存在可行域，则其可行域D=X/AX=b,x0 是一个凸集。是一个凸集。证明：证明：为了证明满足为了证明满足=，0 0的所有点（可行解）组成的几何体的
42、所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点是凸集，只要证明中任意两点任意两点X(1)，X(2)连线上的一切点均连线上的一切点均满足满足线性约束条件线性约束条件既可。既可。n 2.线性规划的基本定理线性规划的基本定理 任任取取，满满足足则则对对任任意意的的有有(1)(2)(1)(2)AX=AX+(1-)X=AX+(1-)AX=b+(1-)b=b又因为均又因为均0 0，所以，所以由此可知，由此可知，即是凸集。即是凸集。(1)(2)X,X,1-(1)(2)X=X+(1-)X0,(1)(2)X=X+(1-)XD,55证明：必要性：证明：必要性：因为是基本解，由基本解的定义，的非零分
43、量所因为是基本解，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是可行解，由基本可行解的定对应的系数列向量线性无关，又因为是可行解，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。关。充分性：充分性：设是线性规划问题的可行解，且正分量设是线性规划问题的可行解，且正分量所对应的列向量也线性无关，则必有所对应的列向量也线性无关，则必有km,km,若若k=mk=m，则，则刚好构成一个基，为相应的基本刚好构成一个基，为相应的基本可行解。若可行解。若kmkm，则由线性代数知识，一定可以从其余的，则由线性
44、代数知识，一定可以从其余的n-kn-k个系数列个系数列向量中取出向量中取出m-km-k个与构成最大线性无关向量组，其对应的个与构成最大线性无关向量组，其对应的基本可行解恰好为，不过此时的是一个退化的基本可行解。基本可行解恰好为，不过此时的是一个退化的基本可行解。引理引理1 1：线性规划问题的可行解线性规划问题的可行解 是基本可是基本可行解的行解的充要条件充要条件是的正分量所对应的系数列向量线性无关。是的正分量所对应的系数列向量线性无关。12nX=(x,x,x)T11kx,x,x11kX=(x,x,x,0,0)T11kP,P,P11kP,P,P11kP,P,P56 定理定理2：设线性规划问题的可
45、行域设线性规划问题的可行域，则是的一个顶点的，则是的一个顶点的充分必要条件充分必要条件是为线性规划问题的基本可行解。是为线性规划问题的基本可行解。证明思路：必要性：证明思路：必要性：由引理由引理1，若，若X是是D的一个顶点，要证明的一个顶点，要证明X是线是线性规划的一个基本可行解，只要证明的正分量所对应性规划的一个基本可行解，只要证明的正分量所对应的系数列向量线性无关。的系数列向量线性无关。用反证法用反证法，倘若的正分量所对应的系数列向量线性相关，倘若的正分量所对应的系数列向量线性相关，则可以在中找到两点，使，与是的顶则可以在中找到两点，使，与是的顶点矛盾点矛盾.101 2/,.,njjjjD
46、XP xbxjn 11kx,x,x11kP,P,P(1)(2)X,X(1)(2)11X=X+X22充分性：充分性：若是线性规划的一个基本可行解，要证明是可行域若是线性规划的一个基本可行解，要证明是可行域的一个顶点，的一个顶点，仍用反证法仍用反证法，倘若不是可行域的顶点，倘若不是可行域的顶点11mP,P,P57例例8:8:已知线性规划问题的约束条件为已知线性规划问题的约束条件为 试讨论可行域顶点和基本可行解之间的对应关系。试讨论可行域顶点和基本可行解之间的对应关系。12314123410 10,0 xxxxxx x x x解解:可行域可行域1 1 101001A 12314/10,10,0,1,
47、2,3,4,jDXxxxxxxj 为四维凸多面体，可以推得在四维空间中有为四维凸多面体，可以推得在四维空间中有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 为基变量的退化基本可行解为基变量的退化基本可行解.58 一个线性规划问题，如果它的所有基
48、本可行解都是非退化一个线性规划问题，如果它的所有基本可行解都是非退化的，那么称这个的，那么称这个线性规划是非退化线性规划是非退化的，只有在这种情况下，的，只有在这种情况下，顶点和基本可行解顶点和基本可行解 之间才是一一对应的。之间才是一一对应的。定理定理3(线性规划的基本定理线性规划的基本定理):若可行域若可行域D非空有界，那么线性规划问题的目标函数非空有界，那么线性规划问题的目标函数一定可以一定可以 在可行域在可行域D的顶点上达到最优值。的顶点上达到最优值。证明思路证明思路：因为可行域非空有界，所以线性规划一定有最优解，因为可行域非空有界，所以线性规划一定有最优解，倘若倘若X(0)不是顶点，
49、且目标函数在该点处取到最优值不是顶点，且目标函数在该点处取到最优值z*，则必能找到可行域的一个顶点则必能找到可行域的一个顶点X(m)，使目标函数，使目标函数在在X(m)的的值也等于值也等于z*。59说明说明:定理定理3并不排除在一个非顶点上有一个最优解的可能性。并不排除在一个非顶点上有一个最优解的可能性。但是在一个但是在一个 给定的线性规划问题的所有最优解中，至少给定的线性规划问题的所有最优解中，至少有一个是顶点。有一个是顶点。如果可行域无界，则线性规划问题可能无最优解。如果可行域无界，则线性规划问题可能无最优解。如果目标函数同时在两个顶点上达到最优解，那么不难如果目标函数同时在两个顶点上达到
50、最优解，那么不难证明在这两个证明在这两个 点的凸组合上也达到最优解，这时线性规点的凸组合上也达到最优解，这时线性规划问题有无穷多最优解。划问题有无穷多最优解。60定理定理1 1：若线性规划问题存在可行域，则其可行域若线性规划问题存在可行域，则其可行域是一个凸集。是一个凸集。0/,DXAX b X 定理定理2：设线性规划问题的可行域设线性规划问题的可行域，则是的一个，则是的一个 顶点的顶点的充分必要条件充分必要条件是为线性规划问题的基本可行解。是为线性规划问题的基本可行解。1/,0,1,2,.,njjjjDXPxb xjn定理定理3：若可行域若可行域D非空有界，那么线性规划问题的目标非空有界，那
