两阶段法分析与实现.doc
《两阶段法分析与实现.doc》由会员分享,可在线阅读,更多相关《两阶段法分析与实现.doc(13页珍藏版)》请在咨信网上搜索。
1、最 优 化 方 法课 程 设 计题 目: 两阶段法分析与实现 院 系: 数学与计算科学学院 专 业: 统计学 姓名学号: 张雨坤 1200720216 指导教师: 李丰兵 日 期: 2015 年 01 月 22 日摘 要常用得解线性规划问题得方法有图解法,单纯形法,对偶单纯形法,解乘数法,椭球法等。而本论文即主要阐述得就是从属于单纯形法得两阶段法。两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题,当第一阶段求解结果表明问题有可行解时,第二阶段就是从第一阶段得最终单纯形表出发,去掉人工变量,并按问题原来得目标函数,继续寻找问题得最优解,即就是一种为使人工变量被替换出成为非基变
2、量得方法。与大M法同时被广为使用,但相较于大M法,两阶段法能够求得更准确地结果。关键词:线性规划;单纯形法;两阶段法;大M法Abstract We usually solve the linear programming problems with graphic method, simplex method and dual simplex method, the multiplier method, ellipsoid method and so on、This paper mainly expounds the two stage method which belongs to simp
3、lex method、 The first stage of two stage method is used to solve a objective function which only contains artificial variables linear programming problem、 When the first phase of solving results show that the problem has a feasible solution, the second stage is from the first stage of the final simp
4、lex tableau, remove artificial variables, and according to the problems of the original objective function, continue to look for the optimal solution of the problem、 It is a kind of way to make artificial variables substituted the non variable method、 The big M method is also widely used at the same
5、 time, but pared with the big M method ,two-phase method can more accurate results、Keywords:;Linear programming;Simplex method;Twostagemethod;ThebigMmethod;目 录1、引言12、两阶段法描述12、1 基本可行解12、2 两阶段法概述12、3 两阶段法第一阶段22、4 两阶段法第二阶段、33、两阶段法求解引例43、1 两阶段法计算步骤43、2 例153、3 例283、4 引例分析94、算法比较94、1 大M法94、2 算法比较104、3 特殊情
6、况115、总结125、1 总结概括125、2 个人感言126、参考文献:131、引言在各种优化算法中,两阶段法(Twostagemethod)就是非常重要得一种。即如果线性规划模型中得约束条件系数矩阵不存在单位向量组,阶梯式应先加入人工变量,人工构成一个单位向量组,其只起过渡作用,不应影响决策变量得取值,两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解得一种方法、把增加人工变量得线性规划问题分为两个阶段去求解、第一阶段就是构造一个辅助得人工目标函数,即或.若原问题有可行解,则在本阶段得最终单纯形表中,必有与,并使人工变量均为非基变量、此时,划去人工变量所在得列与人工目标函数所在得行,
7、就得到原问题得初始可行基对应得单纯形表,进入第二阶段、2、两阶段法描述2、1 基本可行解当线性规划问题得玉树条件全部为“”时,可按下述方法比较方便得寻找可行解:设给定线性规划问题为在第个约束条件上加上松弛变量,化为标准形式由于这个系数矩阵中含一个单位矩阵,只要以这个单位矩阵作为基,就可以立即解除基变量值,因为有,由此就就是一个基可行解。当线性规划中约束条件为“”、“ ”时,化为标准形式后,一般约束条件得系数矩阵中不包括有单位矩阵。这就是为能方便地找出一个初始得基可行解,可添加人工变量来人为地构造一个单位矩阵作为基,称作人工基。先在不等式左端减去一个大于等于零得剩余变量(也称为松弛变量)化为等式
8、,然后再添加一个人工变量。2、2 解线性规划概述两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题,即令目标函数中其她变量得系数取0,人工便灵得系数取某个正得常数,(一般取1),在保持原问题约束条件不变得情况下求这歌目标函数极小化得解。显然在第一阶段中,当人工变量取值为0得时候,目标函数值也为0。这时候得最优解就就是原线性规划问题得一个可行解,。如果第一阶段求解结果最优解得目标函数值不为0,也即最优解得基变量中含有人工基变量,表明原线性规划问题无可行解.当第一阶段求解结果表明问题有可行解时,第二阶段就是从第一阶段得最终单纯性表出发,去掉人工变量,并按问题原来得目标函数,继续寻
9、找问题得最优解.2、3 两阶段法第一阶段两阶段法第一阶段就是先求解一个目标函数中只包含人工变量得线性规划问题,即令目标函数中其她变量得系数取0,人工便灵得系数取某个正得常数,(一般取1),在保持原问题约束条件不变得情况下求这歌目标函数极小化得解.显然在第一阶段中,当人工变量取值为0得时候,目标函数值也为0.这时候得最优解就就是原线性规划问题得一个可行解。如果第一阶段求解结果最优解得目标函数值不为0,也即最优解得基变量中含有人工基变量,表明原线性规划问题无可行解.两阶段法第一阶段就是求解第一个LP。首先我们可以知道,原LP得表达式为其可行域为而我们需要一个辅助得LP,其表达式为其可行域为我们计算
10、以上辅助LP有三种可能结果:1)、最优值,且人工变量皆为非基变量。从第一阶段得最优解中去掉人工变量后即为原LP得一个基本可行解。作为原LP得一个初始基本可行解,再求原问题,从而进入第二阶段。2)、最优值,且存在人工变量皆为基变量,取值为。把某个非基变量与该人工变量进行调换。 3)、最优值,说明至少有一个人工变量不为。原LP无可行解,不需要再做第二阶段计算。两阶段法第一阶段目得就就是判断原LP有无可行解,若有,则可得原LP得一个初始基本可行解,再对原LP进行第二阶段得计算。2、4 两阶段法第二阶段以第一阶段求得最优解作为初始基本可行解,再用第一阶段求得最优解时得约束条件与原问题得目标函数进行迭代
11、,直到求出最优解。3、两阶段法求解引例3、1、两阶段法计算步骤两阶段法具体计算步骤:第一步:求出线性规划得初始基可行解,列出初始单纯形表。第二步:进行最优性检验。第三步;从一个基可行解转换到另一个目标函数值更大得基可行解,列出新得单纯形表。第四步:重复第二、三步一直到计算终止.第五步:去除人工变量。根据求得初始基本可行解,求得最优解. 其中第三步具体方法如下:1)、确定换入基变量。只要检验数,对应得变量就可作为换入基得变量,当有一个以上检验数大于零时,一般从中找出最大得一个其对应变量作为换入基得变量(简称换入变量)。2)、确定换出基得变量,确定确定为换出基得变量(简称出基变量)。元素决定了从一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 阶段 分析 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。