知识卡片

普通读书笔记卡 · 3688

单纯形法最坏情况非多项式

理解等级:中级
  • 椭球法和内点法能在多项式时间求解线性规划;
  • 单纯形法最坏情况下不具多项式时间保证,却在实践中通常表现良好。

评估求解器时应区分理论最坏界与实际运行表现。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第29章 线性规划 · 查看原书依据

      There are two classes of algorithms, known as ellipsoid algorithms and interior-point algorithms, that solve linear programs in polynomial time. In addition, the simplex algorithm is widely used. Although it does not run in polynomial time in the worst case, it tends to perform well in practice. We will not give a detailed algorithm for

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[10000,15000))。 - 结论依据:原文对线性规划建模、标准形式、可行性与几何性质的论述;对应公式图已核对。 - 原始内容:There are two classes of algorithms, known as ellipsoid algorithms and interior-point algorithms, that solve linear programs in polynomial time. In addition, the simplex algorithm is widely used. Although it does not run in polynomial time in the worst case, it tends to perform well in practice. We will not give a detailed algorithm for