第2章 线性规划 计算软件 2.8 线性规划算法的复杂性
计算软件 CPLEX Lindo / Lingo Matlab 2019/1/11 山东大学 软件学院
启动CPLEX 在命令行输入cplex，出现CPLEX提示符“CPLEX>”，进入CPLEX状态。 2019/1/11 山东大学 软件学院
输入问题实例 输入enter命令，输入要优化的问题实例。 2019/1/11 山东大学 软件学院
开始进行优化 输入optimize命令，开始求解问题。 2019/1/11 山东大学 软件学院
显示解 输入display命令，显示求到的解。 输入quit，退出CPLEX。 2019/1/11 山东大学 软件学院
使用MATLAB求解线性规划 2019/1/11 山东大学 软件学院
使用MATLAB求解线性规划 输入参数说明： 输出参数说明： 若某个输入矩阵空缺，应使用空矩阵[]代替。 若某个输入参数开始及之后的所有参数空缺，则这些参数可省略不写。 输出参数说明： x – 找到的解； f_opt – 计算得到的解值； exit_flag – 返回标志； output – 计算信息。 2019/1/11 山东大学 软件学院
例子 2019/1/11 山东大学 软件学院
例子 依次输入如下命令： f = [1 1 1 1 1 1 1]' A = [-1 -1 0 0 0 0 0; -1 0 -1 0 0 0 0; -1 0 0 -1 0 0 0; 0 -1 0 0 -1 0 0; 0 0 -1 0 0 -1 0; 0 0 0 -1 0 0 -1] B = [-1; -1; -1; -1; -1; -1] xm = [0 0 0 0 0 0 0] [x, f_opt, exit_flag, output] = linprog(f, A, B, [], [], xm) 2019/1/11 山东大学 软件学院
计算结果 2019/1/11 山东大学 软件学院
线性规划算法的复杂性 单纯形算法的时间复杂度 解线性规划的多项式时间算法 单纯形算法的平滑分析 2019/1/11 山东大学 软件学院
单纯形算法不是多项式时间的 Theorem [KM82] For every d > 1 there is an LP with 2d equations, 3d variables, and integer coefficients with absolute value bounded by 4, such that simplex may take 2d – 1 iterations to find the optimum. 2019/1/11 山东大学 软件学院
例子 2019/1/11 山东大学 软件学院
解LP的多项式时间算法 椭球法 L. G. Khachian, A polynomial algorithm for linear programming. Doklady Akad. Nauk USSR, 244(5):1093-1096, 1979. 内点法 N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, 1984. 2019/1/11 山东大学 软件学院
最坏情形分析和平滑分析 最坏情形分析（Worst-case analysis） 平均情形分析（Average-case analysis） 分析算法在最坏情形下的时间复杂度。 缺点：最坏情形不代表“整体”情形。 平均情形分析（Average-case analysis） 假定算法的输入满足一定概率分布，分析在此种假定下算法的期望运行时间。 缺点：很难确定实际输入满足什么样的概率分布。 平滑分析（Smoothed analysis） 对算法的最坏情形输入施加一个随机的扰动，分析算法在此种情形下的期望运行时间。 继承了最坏情形分析和平均情形分析两者的优点。 2019/1/11 山东大学 软件学院
单纯形算法的平滑分析 Spielman和滕尚华首次提出了“平滑分析”的概念，并对单纯形算法进行了平滑分析。 Daniel A. Spielman, Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385-463, 2004. S和T证明了单纯形算法的平滑时间复杂度是多项式的。 从而在理论上回答了为什么单纯形算法的最坏时间复杂度是指数的，但该算法在实际中却表现非常好这样一个问题。 因为以上工作，Spielman和Teng获得了2008年Gödel奖和2009年的Fulkerson奖。Spielman因为平滑分析的工作获得了2010年的Nevanlinna奖。 2019/1/11 山东大学 软件学院
2019/1/11 山东大学 软件学院