第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法
线性规划的历史 渊源要追溯到 渊源要追溯到Euler、Liebnitz、Lagrange等 、 、 等 George Dantzig, Non Neumann(Princeton)和 和 Leonid Kantorovich在1940’s创建了线性规划 在 ’ 创建了线性规划 1947年, George Dantzig于发明了单纯形法 年 于发明了单纯形法 1979年，L. Khachain找到了求解线性规划的一 年 找到了求解线性规划的一 种有效方法(第一个多项式时间算法 椭球内点法) 第一个多项式时间算法- 种有效方法 第一个多项式时间算法-椭球内点法 1984年，Narendra Karmarkan发现了另一种求 年 发现了另一种求 解线性规划的有效方法， 解线性规划的有效方法，已证明是单纯形法的强 有力的竞争者(投影内点法 投影内点法) 有力的竞争者 投影内点法 现在求解大规模、退化问题最有效的是原-对偶 现在求解大规模、退化问题最有效的是原 内点法