运筹学单纯形计算课件.ppt

第*页第*页第1页，共41页，星期日，2025年，2月5日1、初始单纯形表第2页，共41页，星期日，2025年，2月5日2、换基操作第3页，共41页，星期日，2025年，2月5日例1用单纯形法解LP第4页，共41页，星期日，2025年，2月5日单纯形表迭代进2出5进1出3第5页，共41页，星期日，2025年，2月5日第6页，共41页，星期日，2025年，2月5日线性规划及单纯型法单纯形法进一步讨论第五节第7页，共41页，星期日，2025年，2月5日1、人工变量法（大M法）第8页，共41页，星期日，2025年，2月5日例1用大M法求解LP问题引入松弛变量和剩余变量第9页，共41页，星期日，2025年，2月5日例1用大M法求解LP问题再引入“人工变量”，构造初始表：人工变量第10页，共41页，星期日，2025年，2月5日用单纯形表迭代第11页，共41页，星期日，2025年，2月5日用单纯形表迭代第12页，共41页，星期日，2025年，2月5日求辅助问题的三种情况第13页，共41页，星期日，2025年，2月5日2、两阶段法基本思想第一阶段求解目标函数只有人工变量的辅助问题得到原问题的初始基可行解。第二阶段利用初始基可行解求原问题的最优解第14页，共41页，星期日，2025年，2月5日第15页，共41页，星期日，2025年，2月5日原辅助题问与题的关系第16页，共41页，星期日，2025年，2月5日例2用两阶段法求解LP问题引入松弛变量和剩余变量，化为等约束第17页，共41页，星期日，2025年，2月5日例2用两阶段法求解LP问题引入“人工变量”，第一阶段：第一阶段第18页，共41页，星期日，2025年，2月5日第一阶段计算第19页，共41页，星期日，2025年，2月5日第一阶段计算第20页，共41页，星期日，2025年，2月5日第二阶段计算第21页，共41页，星期日，2025年，2月5日3、关于解的判别第22页，共41页，星期日，2025年，2月5日3、关于解的判别第23页，共41页，星期日，2025年，2月5日步骤框图初始表计算非基变的量检验数无可行解无穷多最优解*基中有人工变量非基变量检验数=0用初等变换换基操作唯一最优解无界解第24页，共41页，星期日，2025年，2月5日例3解的判别第25页，共41页，星期日，2025年，2月5日例3解的判别有无界解第26页，共41页，星期日，2025年，2月5日解的判别无可行解第27页，共41页，星期日，2025年，2月5日4、向量矩阵描述第28页，共41页，星期日，2025年，2月5日单纯形表中的矩阵向量形式第29页，共41页，星期日，2025年，2月5日第*页第*页