欢迎来到天天文库
浏览记录
ID:50266030
大小:827.00 KB
页数:23页
时间:2020-03-11
《对偶单纯形法经典运筹学.ppt》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、对偶单纯形法是求解对偶规划的一种方法×对偶单纯形法:利用对偶理论得到的一个求解线性规划问题的方法2.3对偶单纯形法单纯形法(原始单纯形法)的两个条件:1、问题为标准型2、有初始基本可行解用单纯形法求解对偶单纯形法的优点:1、不需要人工变量;2、当变量多于约束时,用对偶单纯形法可减少迭代次数;3、在灵敏度分析中,有时需要用对偶单纯形法处理简化。B可逆原始单纯形法的基本思路:关于可行基B的典则形式检验数XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b初始单纯形表:原始单纯形法的迭代过程:对偶单纯形法的基本思路:XBXN常数项检验行0CN-CBB-1NZ-CBB-1bX
2、BEB-1NB-1b作对偶单纯形表:基B的典则形式X1X2X3X4X5检-2-1000ZX3-3-1100-3X4-4-3010-6X5120013不可行检验行≤0分析:若X3或X4所在的行的aij均非负,则问题一定无可行解否则,做换基迭代X1X2X3X4X5检-2-1000ZX3-3-1100-3X4-4-3010-6X51200131、确定出基变量:设br=min{bi
3、bi<0}则取br所在行的基变量为出基变量即取X4为出基变量2、确定入基变量:原则:保持检验行系数≤0X1X2X3X4X5检X3X2X5X1X2X3X4X5检X3X2X1-2/300-1/30Z+2-5/301-1/30-
4、14/310-1/302-5/3002/31-1000-3/5-2/5Z+12/5001-1-100101/54/56/5100-2/5-3/53/5对偶单纯形法步骤:1、找出一个初始对偶可行解。把原问题写成该基的典则形式时,目标函数的系数均≤02、判断:(1)若B-1b≥0,则得到最优解结束(2)若B-1b≥0,则问题无可行解。3、换基迭代:(1)确定出基变量:(2)确定入基变量即找出一个基B,否则转下一步不是典则形式X1X2X3X4X5检21000ZX1111005X4021105X50-4-601-90-1-200Z-10X1X2X3X4X5检X1X4X2013/20-1/49/400-
5、211/21/210-1/201/411/400-1/20-1/4Z-31/4注意:对偶单纯形法仅限于初始基B对应的典则形式中目标函数的系数(检验数)均≤0的情形。可用对偶单纯形法B的典则形式为什么叫对偶单纯形法?X解检验行Z-CBB-1bXBB-1b设B为可行基XBXN解检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b原始单纯形法的基本思路:X解检验行Z-CBB-1bXBB-1b设B为可行基原始单纯形法的迭代过程:对偶单纯形法的基本思路:如何用?求解线性规划问题的方法与步骤:1、把原问题化为标准型2、找初始基,转第3步,转第4步3、把问题写成关于基B的典则形式,用单纯形法,对
6、偶单纯形法,转第4步4、增加人工变量,用大M法或两阶段法求解对应B1的基本解:可用对偶单纯形法求解检验数全部≤0不可行对应B2的基本解用单纯形法求解可行对应B的基本解:存在检验数>0不可行单纯形法×对偶单纯形法?×大M法:两阶段法单纯形法单纯形法作业:
此文档下载收益归作者所有