欢迎来到天天文库
浏览记录
ID:61835782
大小:987.50 KB
页数:21页
时间:2021-03-23
《运筹学经典课件第7次(1).ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、对偶单纯形法是求解对偶规划的一种方法×对偶单纯形法:利用对偶理论得到的一个求解线性规划问题的方法2.3对偶单纯形法在灵敏度分析中,有时用对偶单纯形法处理较简单。单纯形法(原始单纯形法)的两个条件:1、问题为标准型2、有初始基本可行解用单纯形法求解关于可行基B的典则形式检验数原始单纯形法的基本思路:XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b初始单纯形表:原始单纯形法的迭代过程:对偶单纯形法的基本思路:XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b
2、作对偶单纯形表:基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检
4、X3X2X1-2/300-1/30Z+2-5/301-1/30-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检210
5、00ZX1111005X4021105X50-4-601-90-1-200Z-10X1X2X3X4X5检X1X4X2013/20-1/49/400-211/21/210-1/201/411/400-1/20-1/4Z-31/4对偶单纯形表最优单纯形表注意:对偶单纯形法仅限于初始基B对应的典则形式中目标函数的系数(检验数)均≤0的情形。可用对偶单纯形法B的典则形式为什么叫对偶单纯形法?设B为基对偶单纯形法的基本思路:关于基B的典则形式:XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b
6、得对偶单纯形表:对偶单纯形表的另一形式:X常数项检验行XBX解检验行Z-CBB-1bXBB-1b设B为一个基对偶单纯形法的迭代过程:如何用?求解线性规划问题的方法与步骤:1、把原问题化为标准型2、找初始基,转第3步,转第4步3、把问题写成关于基B的典则形式,用单纯形法,对偶单纯形法,转第4步4、增加人工变量,用大M法或两阶段法求解对应B1的基本解:可用对偶单纯形法求解检验数全部≤0不可行对应B2的基本解用单纯形法求解可行对应B的基本解:存在检验数>0不可行单纯形法×对偶单纯形法?×大M法:两阶段法单纯形法单纯形
7、法练习:
此文档下载收益归作者所有