第2章 线性规划 计算软件 2.8 线性规划算法的复杂性.

Presentation on theme: "第2章 线性规划 计算软件 2.8 线性规划算法的复杂性."— Presentation transcript:

1 第2章 线性规划 计算软件 2.8 线性规划算法的复杂性

2 计算软件 CPLEX Lindo / Lingo Matlab 2019/1/11 山东大学 软件学院

3 启动CPLEX 在命令行输入cplex，出现CPLEX提示符“CPLEX>”，进入CPLEX状态。 2019/1/11
山东大学 软件学院

4 输入问题实例 输入enter命令，输入要优化的问题实例。 2019/1/11 山东大学 软件学院

5 开始进行优化 输入optimize命令，开始求解问题。 2019/1/11 山东大学 软件学院

6 显示解 输入display命令，显示求到的解。 输入quit，退出CPLEX。 2019/1/11 山东大学 软件学院

7 使用MATLAB求解线性规划 2019/1/11 山东大学 软件学院

8 使用MATLAB求解线性规划 输入参数说明： 输出参数说明： 若某个输入矩阵空缺，应使用空矩阵[]代替。
若某个输入参数开始及之后的所有参数空缺，则这些参数可省略不写。 输出参数说明： x – 找到的解； f_opt – 计算得到的解值； exit_flag – 返回标志； output – 计算信息。 2019/1/11 山东大学 软件学院

9 例子 2019/1/11 山东大学 软件学院

10 例子 依次输入如下命令： f = [ ]' A = [ ; ; ; ; ; ] B = [-1; -1; -1; -1; -1; -1] xm = [ ] [x, f_opt, exit_flag, output] = linprog(f, A, B, [], [], xm) 2019/1/11 山东大学 软件学院

11 计算结果 2019/1/11 山东大学 软件学院

12 线性规划算法的复杂性 单纯形算法的时间复杂度 解线性规划的多项式时间算法 单纯形算法的平滑分析 2019/1/11 山东大学 软件学院

13 单纯形算法不是多项式时间的 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 山东大学 软件学院

14 例子 2019/1/11 山东大学 软件学院

15 解LP的多项式时间算法 椭球法 L. G. Khachian, A polynomial algorithm for linear programming. Doklady Akad. Nauk USSR, 244(5): , 1979. 内点法 N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4): , 1984. 2019/1/11 山东大学 软件学院

16 最坏情形分析和平滑分析 最坏情形分析（Worst-case analysis） 平均情形分析（Average-case analysis）
分析算法在最坏情形下的时间复杂度。 缺点：最坏情形不代表“整体”情形。 平均情形分析（Average-case analysis） 假定算法的输入满足一定概率分布，分析在此种假定下算法的期望运行时间。 缺点：很难确定实际输入满足什么样的概率分布。 平滑分析（Smoothed analysis） 对算法的最坏情形输入施加一个随机的扰动，分析算法在此种情形下的期望运行时间。 继承了最坏情形分析和平均情形分析两者的优点。 2019/1/11 山东大学 软件学院

17 单纯形算法的平滑分析 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): , 2004. S和T证明了单纯形算法的平滑时间复杂度是多项式的。 从而在理论上回答了为什么单纯形算法的最坏时间复杂度是指数的，但该算法在实际中却表现非常好这样一个问题。 因为以上工作，Spielman和Teng获得了2008年Gödel奖和2009年的Fulkerson奖。Spielman因为平滑分析的工作获得了2010年的Nevanlinna奖。 2019/1/11 山东大学 软件学院

18 2019/1/11 山东大学 软件学院