最优化方法线性规划的单纯形法.pptx
1康托罗维奇，.苏联经济学家，苏联科学院院士，最优计划理论的创始人。1912年生，1930年毕业于列宁格勒大学物理数学系，1935年获数学博士学位。1964年被选为苏联科学院院士。因提出资源最大限度分配理论，1975年与美籍荷兰学者T.C.库普曼斯一起获得诺贝尔经济学奖金。康托罗维奇的主要贡献是把线性规划用于经济管理，创立了最优计划理论。对有效利用资源和提高企业经济效益起了重大作用。他还提出经济效果的概念和衡量经济效果的统一指标体系,作为经济决策的定量依据,来选择最合理的社会生产结构。主要著作有生产组织与计划的数学方法(1939)、资源最优利用的经济计算(1959)、最优计划的动态模型(1964)等。第1页/共52页2佳林库普曼斯(1910年1985年)，美国人，1910年8月28日生于荷兰，1940年离开荷兰移居美国。1975年，他和康托罗维奇同时获得诺贝尔经济学奖。线性规划经济分析法的创立者。第2页/共52页3冯诺依曼（匈牙利语：NeumannJnos；英语：JohnvonNeumann，1903年12月28日1957年2月8日）是出生于匈牙利的美国籍犹太人数学家，现代电子计算机创始人之一。他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。冯诺伊曼从小就显示出数学天才，关于他的童年有不少传说。大多数的传说都讲到冯诺伊曼自童年起在吸收知识和解题方面就具有惊人的速度。六岁时他能心算做八位数乘除法，八岁时掌握微积分，十二岁就读懂领会了波莱尔的大作函数论要义。冯诺伊曼记忆力惊人，读书过目成涌，自幼爱好历史学，他的历史知识堪称渊博，宛如百科全书。第3页/共52页4他的父亲由于考虑到经济上原因，请人劝阻年方17的冯诺依曼不要专攻数学，后来父子俩达成协议，冯诺依曼便去攻读化学。其后的四年间，冯诺依曼在布达佩斯大学注册为数学方面的学生，但并不听课，只是每年按时参加考试。1926年他在苏黎世的获得化学方面的大学毕业学位，他也获得了布达佩斯大学数学博士学位。当他结束学生时代的时候，他已经漫步在数学、物理、化学三个领域的某些前沿。1926年春，冯诺依曼到哥廷根大学任希尔伯特的助手。中学时，他的老师认为按传统的办法教冯诺依曼中学数学课程将是毫无意义的，他接受了大学教师的单独的数学训练。1921年，已被大家当作数学家了。他的第一篇论文是和菲克特合写的，那时他还不到18岁。l933年担任普林斯顿高级研究院教授，当时高级研究院聘有六名教授，其中就包括爱因斯坦，而年仅30岁的冯诺依曼是他们当中最年轻的一位。第4页/共52页5冯诺伊曼是二十世纪最重要的数学家之一，在纯粹数学和应用数学方面都有杰出的贡献。他研究希尔伯特空间上线性自伴算子谱理论，为量子力学打下数学基础；运用紧致群解决了希尔伯特第五问题；他和默里创造了算子环理论，即现在所谓的冯诺伊曼代数。1940年以后，冯诺伊曼转向应用数学。在力学、经济学、数值分析和电子计算机方面作出了卓越贡献。第二次世界大战时冯诺伊曼因战事需要建立冲击波理论和湍流理论，发展了流体力学；从1942年起，他同莫根施特恩合作，写作博弈论和经济行为一书，使他成为数理经济学的奠基人之一。冯诺伊曼对世界上第一台电子计算机ENIAC的设计有决定性的影响，被称为“计算机之父”。他是现代数值分析计算数学的缔造者之一。第5页/共52页62 线性规划的标准型和基本概念线性规划的标准型和基本概念p 线性规划问题及其数学模型线性规划问题及其数学模型p 线性规划的图解法线性规划的图解法p 线性规划的标准形式线性规划的标准形式p 标准型线性规划的解的概念标准型线性规划的解的概念p 线性规划的基本理论线性规划的基本理论第6页/共52页n 问题的提出：问题的提出：在在生生产产管管理理的的经经营营活活动动中中，通通常常需需要要对对“有有限限的的资资源源”寻寻求求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达到最小。最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题有限资源的合理配置有两类问题l如何合理的使用有限的资源，使生产经营的效益达到最大；如何合理的使用有限的资源，使生产经营的效益达到最大；l在生产或经营的任务确定的条件下，合理的组织生产，安排经在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。营活动，使所消耗的资源数最少。p线性规划问题及其数学模型第7页/共52页例例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：及该厂每周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？第8页/共52页 定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。数学模型为数学模型为 s.t.s.t.（subject to)subject to)(such that)(such that)每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 5第9页/共52页10例2 2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500500万m m3 3，在两个工厂之间有一条流量为200200万m m3 3的支流。两化工厂每天排放某种有害物质的工业污水分别为2 2万m m3 3和1.41.4万m m3 3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%0.2%。两化工厂处理工业污水的成本分别为10001000元/万m m3 3和800800元/万m m3 3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小工厂1工厂2200万m3500万m3第10页/共52页11决策变量：x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：min z=1000 x1+800 x2约束条件：第一段河流（工厂1工厂2之间）：(2x1)/500 0.2%第二段河流：0.8(2x1)+(1.4x2)/7000.2%此外有：x12；x21.4化简有：min z=1000 x1+800 x2 x1 1 0.8x1+x2 1.6 x1 2 x21.4 x1、x20称之为上述问题的数学模型。第11页/共52页例例，某某铁铁器器加加工工厂厂要要制制作作100100套套钢钢架架，每每套套要要用用长长为为2.92.9米米，2.12.1米米和和1.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 问题归纳为如何混合使用这8种不同的下料方案，来制造100套钢架，且要使剩余的料头总长为最短。第12页/共52页设设x xj j表示用第表示用第j j种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,2j=1,28,8,数学模型数学模型 s.t.s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量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且为整数第13页/共52页n 线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1 1）用一组决策变量）用一组决策变量x x1 1，x x2 2，x xn n表示某一方案，且在一般情况下，表示某一方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2 2）有有一一个个目目标标函函数数，这这个个目目标标函函数数可可表表示示为为这这组组变变量量的的线线性性函函数。数。（3 3）存在若干个约束条件，约束条件用决策变量的线性等式或线）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。性不等式来表达。（4 4）要求目标函数实现极大化（）要求目标函数实现极大化（maxmax）或极小化（）或极小化（minmin）。）。满足上述满足上述4 4个特征的规划问题称为线性规划问题个特征的规划问题称为线性规划问题第14页/共52页 线性规划的一般数学模型线性规划的一般数学模型 目标函数目标函数 满足约束条件满足约束条件 通常称通常称 为决策变量，为决策变量，为价值系数，为价值系数，为消耗系数为消耗系数,为资源限制系数。为资源限制系数。第15页/共52页p 线性规划的图解法线性规划的图解法 适用于求解两个变量的线性规划问题n图解法的基本步骤例4,利用例1说明图解法的主要步骤，例1的数学模型为 s.t.第16页/共52页O51015x1x1=4x25101AB(2,5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5第17页/共52页n 图解法的几种可能结果图解法的几种可能结果 (1(1）有唯一最优解，如例）有唯一最优解，如例1 1。（2 2）有无穷多最优解）有无穷多最优解 如例如例1 1中的目标函数设为中的目标函数设为 maxZ=10 xmaxZ=10 x1 1+2x+2x2 2 则目标函数等值线则目标函数等值线10 x10 x1 1+2x+2x2 2=Z=Z 与第二约束与第二约束 5x5x1 1+x+x2 21515 的边界线平行。将等值线沿梯度的边界线平行。将等值线沿梯度Z=Z=（1010，2 2）正方向平移）正方向平移 至至B B点时与可行域点时与可行域OABCOABC的整条边界线的整条边界线ABAB重合。重合。这表明线段这表明线段ABAB上的每一点都使目标函数取得同样的最大值，上的每一点都使目标函数取得同样的最大值，因而都是最优解。因而都是最优解。第18页/共52页19O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5第19页/共52页例例5 5，试用图解法求解下列线性规划问题试用图解法求解下列线性规划问题 st.（3）无界解（或称无最优解）无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值Z+,极小化问题 则可使目标函数值Z-，有无界解的线性规划问题的可行域是无界区域，但反之则不必然。第20页/共52页-1O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1O33第21页/共52页（4 4）无可行解）无可行解 某些线性规划问题的可行域是空集，既不存在满足所有约某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。束条件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。要求，既不存在可行方案。第22页/共52页23例6maxz=x1+2x2x1+2x21 x1+x22 x1、x20无可行解。1112OA第23页/共52页24以上几种情况的图示如下：可行域有界唯一最优解 可行域有界多个最优解第24页/共52页25可行域无界唯一最优解可行域无界无穷多最优解第25页/共52页26可行域无界目标函数无界 可行域为空集无可行解第26页/共52页271.有最优解唯一最优解无穷多最优解2.最优解无界3.无可行解第27页/共52页28直观结论：（1）可行域可以是个凸多边形，可能无界，也可能为空；（2）若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；（3）若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解；（4）若可行域非空有界，则一定有最优解。第28页/共52页n 标准线性规划模型标准线性规划模型 线性规划问题的标准形式：线性规划问题的标准形式：s.t s.t 其中其中（2）（3）p线性规划的标准形式（1）第29页/共52页l紧凑格式：紧凑格式：s.t.s.t.l向量格式：向量格式：s.t.s.t.其中其中 称为价值向量，称为价值向量，为决策变量向量，为决策变量向量，为决策变量为决策变量x xj j所对应所对应的消耗系数向量，的消耗系数向量，为资源向量。为资源向量。第30页/共52页31l矩阵格式：其中为mn阶矩阵 为价值向量，为决策变量向量，为资源向量。第31页/共52页n非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化（1 1）极大化与极小化）极大化与极小化 ：若若 ，令，令 ，则有，则有 原目标函数原目标函数 。(2)(2)线性不等式与线性等式：线性不等式与线性等式：其中其中 为非负松弛变量，为非负松弛变量，其中其中 为非负剩余变量。为非负剩余变量。第32页/共52页33(4)非负变量与符号不受限制的变量 若 xi的符号不受限制，则可引进非负变量xi1,xi2，令 xi=xi1-xi2，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。(3)右端项为负 约束两端乘以（1）第33页/共52页例7，将下述线性规划问题化为标准型 解：令,其中符号不受限制符号不受限制第34页/共52页考虑一个标准的线性规划问题：s.t 其中为n维行向量，是n维列向量，是m维列向量，是mn阶矩阵，假定满足mn，且()=m，p标准型线性规划的解的概念第35页/共52页 线性规划问题解的概念：(1)可行解。满足约束条件的解可行解集称为线性规划问题的可行域。(2)最优解。使目标函数达到最优值的的可行解称为最优解，最优解常用 表示。(3)基。若是中mm阶非奇异矩阵，即|0，则称是线性规划问题的一个基。第36页/共52页基向量，基变量若是线性规划问题的一个基，那么一定是由m个线性无关的列向量组成，不失一般性，可设 称 为基向量，与基向量相对应的变量称为基变量。基的个数一个线性规划的基通常不是唯一的，但是基的个数不会超过 个。第37页/共52页(4)基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组=b的解称为线性规划问题的一个基本解（简称基解）。基本解的个数也不会超过 个。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5)基本可行解。满足非负条件的基本解称为基本可行解（简称基可行解）。与基本可行解对应的基称为可行基。基本可行解的非零向量的个数小于等于m，并且都是非负的。当基本可行解中有一个或多个基变量取零值时，称此解为 退化的基本可行解。第38页/共52页39 一个线性规划问题，如果它的一个线性规划问题，如果它的所有基本可所有基本可行解行解都是都是非退化非退化的，那么的，那么 称这个线性规划是称这个线性规划是非退非退化化的的.对对非退化线性规划非退化线性规划，可行基和基本可行解之，可行基和基本可行解之间是间是一一对应一一对应的。的。第39页/共52页线性规划问题各种解的关系可用文氏图表示，可行解基本解基本可行解第40页/共52页例8、求下列约束方程所对应的线性规划的所有基本解，基本可行解。s.t 解：化为标准形式 为24阶矩阵。且R(A)=2,所以该线性规划基的个数 =6个 取 ,为基变量，若令非基变量 ，约束方程组为 可得对应的基本解 是一个基本可行解。第41页/共52页按相同步骤，可求得线性规划其他4个基：对应基本解是一个基本可行解。对应基本解是一个基本可行解。对应基本解不是一个基本可行解。对应基本解是一个基本可行解。第42页/共52页若利用图解法画出线性规划的可行域，如图，CDOBA448第43页/共52页p 线性规划的基本理论线性规划的基本理论 由图解法的步骤，可以从几何的角度得出结论：（1）线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限个。（2）若线性规划问题有最优解，那么最优解一定可在可行域的某个顶点上找到。第44页/共52页45引理1：若线性规划问题存在可行域，则其可行域是一个凸集。证明：为了证明满足=，0的所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点连线上的一切点均满足线性约束条件既可。任取，满足则对任意的有n 线性规划的基本定理线性规划的基本定理 又因为均0，所以由此可知，即是凸集。第45页/共52页证明：必要性：因为是基本解，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是可行解，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。充分性：设是线性规划问题的可行解，且正分量所对应的列向量也线性无关，则必有km,若k=m，则刚好构成一个基，为相应的基本可行解。若km，则由线性代数知识，一定可以从其余的n-k个系数列向量中取出m-k个与构成最大线性无关向量组，其对应的基本可行解恰好为，不过此时的是一个退化的基本可行解。定理1：线性规划问题的可行解 是基本可行解的充要条件是的正分量所对应的系数列向量线性无关。第46页/共52页47 定理2：设线性规划问题的可行域，则是的一个 顶点的充分必要条件是为线性规划问题的基本可行解。证明思路：必要性：由定理1，若X是D的一个顶点，要证明X是线性规划的一个基本可行解，只要证明的正分量所对应的系数列向量线性无关。用反证法，倘若的正分量所对应的系数列向量线性相关，令第47页/共52页48的基变量所对应的系数列向量的基变量所对应的系数列向量线性相关线性相关，与与X X是基本可行解矛盾。是基本可行解矛盾。充分性：若是线性规划的一个基本可行解，要证明是可行域的一个顶点。反证法，设不是可行域的顶点 ，第48页/共52页49 定理定理3 3：若可行域：若可行域D D非空非空，那么一定存在，那么一定存在D D的的顶点顶点（极点（极点)。若线性规划问题存在若线性规划问题存在可行解可行解，则一定存在，则一定存在基本可行基本可行解解。证明思路：为可行解。若前k列线性无关，则为基本可行解。若相关，则选择充分小使至少有一个为0，其余。得到新可行解，非零分量减少一个。重复，直到线性无关为止。第49页/共52页50证明思路：为最优解。若前k列线性无关，则为基本可行解，证毕。若否，则如定理3，作，为可行解。选择充分小使至少有一个为0，其余。得到新最优解，非零分量减少一个。重复，直到线性无关为止。定理4：若线性规划问题存在最优解，则必存在基本可行解是最优解。第50页/共52页51练习：1、将下面线性规划化为标准形式并用图解法求解。2、用求全部基可行解的方法求解下列线性规划。第51页/共52页52感谢您的观看！第52页/共52页
