运筹学课件ch1单纯形法.ppt_第1页
运筹学课件ch1单纯形法.ppt_第2页
运筹学课件ch1单纯形法.ppt_第3页
运筹学课件ch1单纯形法.ppt_第4页
运筹学课件ch1单纯形法.ppt_第5页
已阅读5页,还剩46页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1,第二节 单纯形法,单纯形法是求解线性规划的主要算法,1947 年由美国斯坦福大学教授丹捷格(G.B.Danzig) 提出。 尽管在其后的几十年中,又有一些算法问世, 但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率。,2,1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型表示为,标准型的特征:Max型、等式约束、非负约束,一、单纯形法的预备知识,3,非标准形式如何化为标准,1) Min型化为Max型,加负号,因为,求一个函数 的极小点,等价于求该 函数的负函数的极大点。,注意: Min型化为Max型求解后,最优解不变,但最优值差负号。,4,.约束方程的转换:由不等式转换为等式。,称为松弛变量,称为剩余变量,5,例1 某工厂可生产甲、乙两种产品,需消耗煤、电、油三种资源。现将有关数据列表如下: 试拟订使总收入最大的生产方案。,2) 不等式约束化为等式约束,6,2) 不等式约束化为等式约束,分析:以例1中煤的约束为例,之所以“不等”是因为左右两边有一个差额,称为“松 弛量”,若在左边加上这个松弛量,则化为等式。而这 个松弛量也是变量,记为X3 ,则有,X3称为松弛变量。问题:它的实际意义是什么?, 煤资源的“剩余”。,7,练习:请将例1的约束化为标准型,解:增加松弛变量,则约束化为,易见,增加的松弛变量的系数恰构成一个单位阵I。,8,一般地,记松弛变量的向量为 Xs,则,问题:松弛变量在目标中的系数为何?, 0。,3) 当模型中有某变量 xk 没有非负要求,称 为自由变量, 则可令,化为标准型。,9,2.基本概念,(1)可行解与最优解,直观上,可行解是可行域中的点,是一个可行的方案; 最优解是可行域的角点,是一个最优的方案。,10,(2)基矩阵与基变量,基矩阵(简称基):由系数阵A中的线性无关的列组成的m阶子矩阵,记为B;其余列构成非基矩阵,记为N。,基向量:基B中的列;其余的列称非基向量。,基变量:与基向量Pj对应的决策变量xj,记其组成的 向量为XB;与非基向量对应的变量称非基变 量,记其组成的向量为XN。,基矩阵的特点: 1. 基B是可逆矩阵,即,2. 基B是一个 方阵,A= ( B N ),11, 6个。,一般地,mn 阶矩阵A中基的个数最多有多少个?,问题:本例的A中一共有几个基?,12,【例4】线性规划,求所有基矩阵。,【解】约束方程的系数矩阵为25矩阵,容易看出r(A)=2,2阶子矩阵有C52=10个, 其中第1列与第3列构成的2阶矩阵不是一个基, 基矩阵只有9个,即,13,(3)基本解与基本可行解,可见:一个基本解是由一个基决定的。 注意:基本解仅是资源约束的解,并未要求其非负,因此其未必可行。,称非负的基本解为基本可行解(简称基可行解)。,14,例3中,求相应于基B1和B2的基本解,它们是否基本可行解?,15,对来说,x1,x2是基变量,x3,x4,x5是非基变量,令x3=x4=x5=0,因|B1|,由克莱姆法则知,x1、x2有唯一解x12/5,x2=1则 基本解为,在例4中,Xi0,是基本可行解,16,在 中x10,因此不是可行解,也就不是基本可行解。,反之,可行解不一定是基本可行解 例如 满足所有约束式,但不是 任何基矩阵的基本解。,基本解为,17,上二组概念间的联系:,几种解之间的关系:,问题:基本可行解是可行域中的哪些点?,使目标函数值最优的基本可行解是最优解,18,3.基本定理,(1)线性规划的可行域是一个凸多面体。,(2)线性规划的最优解(若存在的话)必能在可行 域的角点获得。,(3)线性规划可行域的角点与基本可行解一一对应。,19,二、单纯形法的步骤,单纯形法是一种迭代的算法,它的思想是在可行域的角点基本可行解中寻优。由于角点是有限个(为什么?),因此,算法经有限步可终止。,确定一个初始基可行解,检验这个基可行解是否最优,寻找一个更好的基可行解,停止,20,1.确定初始基可行解,由于基可行解是由一个可行基决定的,因此,确定初始基可行解X0相当于确定一个初始可行基B0。,方法:若A中含I,则B0=I; 若A中不含I,则可用人工变量法构 造一个I。,问题:若B0=I,则X0=?,21,2. 最优性检验,问题:用什么检验?, 目标。,问题:非最优的特征为何?,22,因为:,将XB代入Z, 有,Z*为最优值的条件是,23,3. 寻找更好的基可行解,由于基可行解与基对应,即寻找一个新的基可行解,相当于从上一个基B0变换为下一个新的基B1,因 此,本步骤也称为基变换。,(基变换),24,以例1为例,可按上述单纯形法的步骤求出其最优解,其大致的过程如下。,(1)先将模型化为标准型,(2) 确定初始基可行解、检验,25,基B=(P3,P4,P5)=,=B-1,非基N=(P1,P2)=,确定进基向量为P2,计算检验数,确定进基向量,Max (0),26,计算检验比,确定出基向量,Min (0),P5出基,B1=(P3,P4,P2),确定新基,27,(3)换基、计算下一个基可行解、再检验,直至最优,问题:当模型规模较大时,计算量很大。,事实上,单纯形法的实现是在单纯形表上完成的。,28,练习:对于下面的线性规划,(1)用图解法求解; (2)将模型化为标准型; (3)用单纯形法步骤求出其最优解,并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点。,29,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式,是单纯形法的具体实现。,回顾单纯形法步骤,30,单纯形表,A,b,分别将系数C,矩阵A和资源限制b填入, 得到单纯形表的初表,计算检验数,进行最优性检验,若非优,就做初等行变换,形成新基的单纯形表, =C-CBB-1A,31,单纯形表的主要结构:,问题:第一张表的B-1=?,单位阵I。,检验数的公式是什么?,32,例5:用单纯形法求解例1,问题:标准模型的A中是否含I?,松弛变量系数恰好构成I。,33, , 中表示进基列与出基行的交叉元,下一张表将实行以它为主元的初等行变换(称高斯消去)。方法是:先将主元消成1,再用此1将其所在列的其余元消成0。,34, ,(请解释其实际意义),此行元素除以主元10,30 0.3 1 0 0 0.1,此行元素除以主元2.5,35,练习:用单纯形法求解下面的线性规划,36, ,注:1. 表上每一列的含义:,2. 每张表上B-1的位置在哪?对应于初表中I 的位置。,37,最优基解XB=(x3,x1,x2) 最优基B=(p3,p1,p2)在哪里?,38,例6: 填表:,初表,终表,39,练习:用单纯形法求解下面的线性规划,40, ,问题:本题的单纯形终表检验数有何特点?, 非基变量x2 的检验数等于零。,41,注:(1)解的几种情况在单纯形表上的体现(Max型): - 唯一最优解:终表非基变量检验数均小于零; - 多重最优解:终表非基变量检验数中有等于零的; - 无界解:任意表有正检验数相应的系数列均非正。,不同类型的解的判别:,42,(2) Min型单纯形表与Max型的区别仅在于:检验数反号,即 - 令负检验数中最小的对应的变量进基;min - 当检验数均大于等于零时为最优。,Min型的单纯形法,43,大M法,方法: 在一个标准的线性规划问题的约束条件中加进人工变量Xr并给定该人工变量在目标函数中的系数为(-M)(M为任意大的正数),对于min型 有何不同?,最优性最优基中不含人工变量 若基变量中不含有非零的人工变量,表示原问题有解。若对于MAX型,当 0 ,而还有人工变量(非零)时,则表示原问题无可行解。,设规划模型约束条件为AXb或者AX=b,此时需加入人工变量,以便在A矩阵中得到一个mm的单位矩阵,使初始基可行。,44,例8 现有线性规划问题,试用大M法求解。,45,解 在上述问题的约束条件中加入松弛变量x4,剩余变量x5,人工变量x6,x7,得到,这里M是一个任意大的正数。,思考:能不能将第二个等式乘以-1?,不能。基解要可行,不能为负,46,因本例的目标函数是要求min,所以用所有cj-zj0来判别目标函数是否实现了

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论