过程一、对偶单纯形法的原理(15分钟)LP与DP在求解迭代过程中有三种情形:LPDP结论或继续计算的步骤可行解可行解表中解仍为最优解可行解非可行解单纯形法非可行解可行解对偶单纯形法非可行解非可行解引进人工变量二、对偶单纯形法求解过程(50分钟)1.用实例引入:2.总结对偶单纯形法求解过程:(1)将线性规划的约束化为等式,取对偶可行基B(全部检验数λj≤0(max)或λj≥0(min),模型为典式)建立初始单纯形表;(2)检验:当基本解可行时,即常数项列B-1b≥0,达到最优解;若基本解不可行,即B-1b中有负数,则要进行换基迭代;(3)换基迭代:先确定出基变量。l行对应的变量xl出基,l行称为主行;再选进基变量。求最小比值:θk所在列对应的变量xk出基,第k列称为主列。若第l行所有元素aij≥0,说明线性规划无可行解;用初等变换将主元素alk化为l,主列的其它元素化为零,得到新的单纯形表;重复(2)、(3),直到得出最优解或判断无可行解。三、课堂练习(30分钟)四、课堂小结,作业布置(5分钟)第13、14次课4学时授课章节第二章对偶理论与灵敏度分析第四节灵敏度分析授课方式理论课课堂教学目的及要求1.知识目标:理解求解线性规划的单纯形法中灵敏度分析的基本原理;2.能力目标:分析cj,bi,aij的变化;增加一个变量Xi的分析:(1)参数在什么范围内变化时,原最优解或最优基不变;(2)当参数已经变化时,最优解或最优基有何变化。当模型的参数发生变化后,可以不必对线性规划问题重新求解,而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解。课堂教学重点及难点重点:1.注意最优解与最优基不变的区别;2.掌握某个参数变化后,最优表中哪些数据会发生变化,如何变化;3.模型发生变化后不是重新求解,而是在原模型的最优表中求出变化后的数据,根据变化条件,选择合适的方法继续计算。
全文预览
