资源预览内容
第1页 / 共33页
第2页 / 共33页
第3页 / 共33页
第4页 / 共33页
第5页 / 共33页
第6页 / 共33页
第7页 / 共33页
第8页 / 共33页
第9页 / 共33页
第10页 / 共33页
亲,该文档总共33页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2017/9/1,1,想一想:图解法是否有局限性?,2017/9/1,2,1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。,13 单纯形法,一、单纯形法的基本思想1、顶点的逐步转移,即从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)的迭代过程,转移的条件是使目标函数值得到改善(逐步变优),当目标函数达到最优值时,问题也就得到了最优解。,2017/9/1,3,根据线性规划问题的可行域是凸多边形或凸多面体,一个线性规划问题有最优解,就一定可以在可行域的顶点上找到。 于是,若某线性规划只有唯一的一个最优解,这个最优解所对应的点一定是可行域的一个顶点;若该线性规划有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解。,顶点转移的依据?,2017/9/1,4,2需要解决的问题: (1)为了使目标函数逐步变优,怎麽转移? (2)目标函数何时达到最优 判断标准是什麽?,例1-1 ,某工厂计划生产A、B两种产品,具体资料见下表,其中,一件A产品获利2元,一件B产品获利3元,问如何安排计划实现工厂利润最大化?,二、单纯形法原理(用代数方法求解LP),2017/9/1,5,试写出线性规划模型并将其转化为标准型,2017/9/1,6,2017/9/1,7,第一步:引入非负的松弛变量和剩余变量 x3,x4,x5, 将该LP化为标准型,2017/9/1,8,第二步:寻求初始可行基,确定基变量,对应的基变量是:,第三步:写出初始基本可行解和相应的 目标函数值,x3 x4 x5,2017/9/1,9,两个关键的基本表达式:用非基变量表示基变量的表达式,初始基本可行解,2017/9/1,10,用非基变量表示目标函数的表达式,不生产任何产品,资源全部节余( x3=8 x4=16,x5=12),产品的总利润为0!,当前的目标函数值:,请解释结果的经济含义:,2017/9/1,11,第四步:分析两个基本表达式,看看目标函数是否可以改善?, 分析用非基变量表示目标函数的表达式,非基变量前面的系数均为正数,所以任何一个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数”;,2017/9/1,12, 从经济意义上讲.安排生产任一种产品都能使利润指标增加,所以只要在目标函数的表达式中还存在有“正的检验数”的非基变量,表明目标函数值还有增加的可能,就需要将非基变量与某个基变量进行对换.,怎么换?,2017/9/1,13, 选哪一个非基变量进基? 选x1为进基变量(换入变量) 问题讨论:能否选其他的非基变量进基?, 任意一个 任意一个正检验数对应的非基变量 最大正检验数对应的非基变量 排在最前面的正检验数对应的非基变量,为使变换后的目标函数值增加的幅度最大,一般选正检验数最大的那个非基变量做为换入变量,2017/9/1,14, 确定出基变量:, x2进基意味着其取值从0变成一个正数(经济意义生产B产品),能否无限增大?, 具体如何确定换出变量?, 现在的非基变量是哪些?,问题讨论, 当x2增加时, x3、 x4、x5如何变化?,2017/9/1,15,由用非基变量表示基变量的表达式,当x2增加时, x3, x4,x5会减小,但有限度?,必须大于等于0,以保持解的可行性!,取x1等于0,则:,寻找出基变量的方法:,2017/9/1,16,这说明当x2的值从0增加到3时,原来基变量x5首先变为0,另外两个基变量X3、X4仍然为正值。因此选x5为出基变量(换出变量)。,这种用来确定出基变量的规则称为 “最小比值原则”(或原则)。,2017/9/1,17, 基变换新的基变量x2, x3,x4;新的非基变量x1, x5 ;写出用非基变量表示基变量的表达式:,可得新的基本可行解 X(1)=(0,3,2,16,0)T,由,2017/9/1,18, 写出用非基变量表示目标函数的表达式:,可得相应的目标函数值为Z(1)=9,检验数仍有正的,即非基变量X1的系数为正值,目标函数值还可以增大,尚不是最优解。,返回重新进行讨论。,2017/9/1,19,第五步:上述过程何时停止?,分析用非基变量表示目标函数的表达式,如果让负检验数所对应的变量进基,目标函数值将下降!,当用非基变量表示目标函数的表达式中,非基变量的系数(检验数)全部非正时,当前的基本可行解就是最优解!,为什么?,2017/9/1,20,返回进行讨论。需要进行第二次迭代,得到一组新的基本可行解,新的基本可行解: X(2)=(2,3,0,8,0)T,得到的目标函数表达式为:,检验数仍有正值,返回继续讨论。需要进行第三次迭代,得到一组新的基本可行解,2017/9/1,21,目标函数的表达式中,非基变量的系数(检验数)全部非正,当前的基本可行解就是最优解!,新的基本可行解: X(3)=(4,2,0,0,4)T,得到的目标函数表达式为:,A产品生产4件,B产品生产2件使利润最大,三、表格单纯形法: 1、 初始单纯形表的建立 (1)表格结构:,限定系数,技术系数,(2)表格设计依据: 将-Z看作不参与基变换的基变量,把目标函数表达式改写成方程的形式,和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组:,2017/9/1,24,取出系数写成增广矩阵的形式:,-Z X1 X2 Xn Xn+1 Xn+2 Xn+m b,-Z,Xn+1,Xn+m所对应的系数列向量构成一个初始可行基,2017/9/1,25,用矩阵的初等行变换将该基变成单位阵,这时 变成0,相应的增广矩阵变成如下形式:,其中,,2017/9/1,26,(3)检验数的两种计算方法: 利用矩阵的行变换,把目标函数表达式中基变量前面的系数变为0; 使用计算公式,增广矩阵的最后一行就是用非基变量表示目标函数的表达式, (j=1,2,n)就是非基变量的检验数。,2、例1.8的表格单纯形法计算过程:,2017/9/1,27,2017/9/1,28,2017/9/1,30,X*=(4,2,0,0,4)T 相应的目标函数最优值是Zmax=14,从最优表可知: 该LP的最优解是,2017/9/1,31,分别用代数法和单纯行法求解线性规划问题,例2-1 ,某工厂计划生产A、B、C、D四种原料生产两种产品,具体资料见下表,其中,一件产品获利400元,一件产品获利600元,问如何安排计划实现工厂利润最大化?,2017/9/1,32,2017/9/1,33,X*=(2,5,0,2,16,0)T 相应的目标函数最优值是Zmax=38,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号