2020/8/5,1,运 筹 学 Operations Research,1.6 单纯形法原理,单纯形法（simplex method）： 1947年，美国数学家G. B. Dantzig（旦茨基，但泽克，丹捷格，丹西格）,2020/8/5,2,运 筹 学 Operations Research,一 基本思想：,当可行域非空时, 从可行域的一个顶点（基可行解）开始, 判断其是否为最优解，若为否，转到另一个相邻的顶点（基可行解）, 且使目标函数值减小，. ，如此继续，直到找到最优解。,注：单纯形法和枚举法的区别。,2020/8/5,3,运 筹 学 Operations Research,对某些特殊情形，可很方便地找到其初始可行基.,二 初始可行基,对一般的线性规划问题，初始可行基的寻找可采 用大M法和两阶段法.,2020/8/5,4,类型1,运 筹 学 Operations Research,2020/8/5,5,运 筹 学 Operations Research,即标准形的约束方程组的系数矩阵为,2020/8/5,6,类型2,运 筹 学 Operations Research,如,2020/8/5,7,运 筹 学 Operations Research,标准形的约束方程组的系数矩阵为,思考: B为何是可行基？,2020/8/5,8,运 筹 学 Operations Research,线性规划问题的标准形,三 单纯形表,2020/8/5,9,运 筹 学 Operations Research,则,代入目标函数得,2020/8/5,10,运 筹 学 Operations Research,联立得,（用非基变量来表示基变量和目标函数）,改写为,2020/8/5,11,运 筹 学 Operations Research,两个问题：,（2）由单纯形表能看出什么？,（1）单纯形表和典式有何关系？,2020/8/5,12,运 筹 学 Operations Research,令,则典式即为,典式的等价形式,2020/8/5,13,运 筹 学 Operations Research,重要说明：非基变量，基变量，目标函数值与典式的等价形式之间的对应关系。,由典式得单纯形表为,检验数：,2020/8/5,14,运 筹 学 Operations Research,一种特殊形式的线性规划问题的单纯形表,给定线性规划问题,2020/8/5,15,运 筹 学 Operations Research,2020/8/5,16,运 筹 学 Operations Research,单纯形表为,2020/8/5,17,运 筹 学 Operations Research,例1 给定线性规划问题,2020/8/5,18,运 筹 学 Operations Research,解（1）：典式为,单纯形表为,2020/8/5,19,运 筹 学 Operations Research,例1 给定线性规划问题,2020/8/5,20,运 筹 学 Operations Research,（2）：典式为,单纯形表为,2020/8/5,21,运 筹 学 Operations Research,例1 给定线性规划问题,2020/8/5,22,运 筹 学 Operations Research,（3）：典式为,单纯形表为,2020/8/5,23,运 筹 学 Operations Research,例1 给定线性规划问题,2020/8/5,24,运 筹 学 Operations Research,（4）：典式为,单纯形表为,2020/8/5,25,运 筹 学 Operations Research,线性规划问题的标准形,典式为,四、最优性的检验,2020/8/5,26,运 筹 学 Operations Research,单纯形表为,2020/8/5,27,运 筹 学 Operations Research,下面分三种情形讨论：,2020/8/5,28,运 筹 学 Operations Research,2020/8/5,29,运 筹 学 Operations Research,Case 3 otherwise,转轴的目的：改变基（一个列向量离开基，一个列向量进入基）；在保证新基解的可行性的前提下，使得目标函数值增大.,2020/8/5,30,运 筹 学 Operations Research,转轴在单纯形表上的实现：,2020/8/5,31,运 筹 学 Operations Research,转轴后,2020/8/5,32,运 筹 学 Operations Research,在转轴后的单纯形表中，新的基解为：,由此，新的基解仍为可行解，保证了新基的可行性.,2020/8/5,33,运 筹 学 Operations Research,新的基可行解对应的目标函数值为：,