运筹学单纯形法迭代原理.pptx
《运筹学单纯形法迭代原理.pptx》由会员分享,可在线阅读,更多相关《运筹学单纯形法迭代原理.pptx(29页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、三三.单纯形法的基本思想单纯形法的基本思想1、顶点的逐步转移顶点的逐步转移 即从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)的迭代过程,转移的条件是使目标函数值得到改善(逐步变优),当目标函数达到最优值时,问题也就得到了最优解。第1页/共29页 根据线性规划问题的可行域是凸多边形或凸多面体,一个线性规划问题有最优解,就一定可以在可行域的顶点上找到。于是,若某线性规划只有唯一的一个最优解,这个最优解所对应的点一定是可行域的一个顶点;若该线性规划有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据?第2页/共29页 转移条件?转移结果?使目标函数
2、值得到改善 得到LP最优解,目标函数达到最优值 2需要解决的问题:(1)为了使目标函数逐步变优,怎么转移?(2)目标函数何时达到最优 判断标准是什么?第3页/共29页解解LPLP问题单纯形法的基本思路:问题单纯形法的基本思路:初始可行基:设法在约初始可行基:设法在约束矩阵束矩阵 中中 构造出一个构造出一个mm阶阶单位阵单位阵初始基本可行解初始基本可行解检验数检验数进基进基变量:检验数变量:检验数离基离基变量:最小比值准则变量:最小比值准则第4页/共29页1.1.确定初始基本可行解确定初始基本可行解 LP:?希望在化希望在化LPLP的标准形的标准形式时,式时,A A中都含有一中都含有一个个mm阶
3、单位阵。阶单位阵。第5页/共29页观察法观察法观察系数矩阵中观察系数矩阵中是否含有是否含有现成的单位阵?现成的单位阵?LPLPLPLP限制条件中限制条件中全部是全部是“”“”“”“”类型的约束类型的约束 将将新新增增的的松松弛弛变变量量(+)作作为为初初始始基基变变量量,对对应应的的系数列向量构成单位阵;系数列向量构成单位阵;LPLPLPLP限制条件限制条件有有“”“”“”“”类型的约束类型的约束左端新增左端新增剩余变量剩余变量(-)后,再加上一个非负的新后,再加上一个非负的新变量变量人工变量人工变量。LPLPLPLP限制条件限制条件有有“=”=”=”=”类型的约束类型的约束直接在左端加上直接
4、在左端加上人工变量人工变量。第6页/共29页在引入人工变量后,与原先的约束方程在引入人工变量后,与原先的约束方程不完全等价不完全等价,为此,为此,需要在需要在目标函数目标函数上做些上做些“修正修正”大大MM法法或或两阶段法两阶段法A 非基变量取0,算出基变量,搭配在一起构成初始基本可行解:第7页/共29页2.2.建立判别准则判断:判断:初始初始基本可行解基本可行解或或经过若干次迭代后得到的经过若干次迭代后得到的新新基基本可行解本可行解当前解当前解是否是否为最优解?为最优解?一般(经过若干次迭代),对于基B,用用非非基变量基变量表出表出基变量基变量的表达式的表达式 为:典式若 第8页/共29页用
5、用非基变量非基变量表示表示目标函数目标函数的表达式:的表达式:典式检验数第9页/共29页其中(1)最优性判别定理(2)有无穷多个“最优解”的判别定理 第10页/共29页3 3、进行基变换进行基变换(1 1)进进基基变变量量的的确确定定原则:正正检检验验数数(或或最最大大正正检检验验数)所对应的变量进基数)所对应的变量进基,目的是使目标函数得到改善。目的是使目标函数得到改善。(2 2)离基变量的确定)离基变量的确定在在保持解的保持解的可行性可行性的前提下,的前提下,使目标函数使目标函数较快增大较快增大。第11页/共29页 =当当 时,为使时,为使 ,需要,需要从而,最大可取到最小比值原则则该LP
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 单纯 形法迭代 原理
限制150内