§1单纯形法的基本原理 单纯形法(Simplex Method)是1947 年由G.B.Dantig提出，是解LP问 题最有效的算法之一，且已成为整数 规划和非线性规划某些算法的基础。 基本思路： 基于LP问题的标准形式，先设法找到一个基可 行解，判断它是否是最优解，如果是则停止计算；否 则，则转换到相邻的目标函数值不减的一个基可行解 (两个基可行解相邻是指它们之间仅有一个基变量不 相同)。§1 单纯形法的基本原理 单纯形法（Simplex Method）是1947 年由 G.B. Dantzig 提出，是解 LP 问 题最有效的算法之一，且已成为整数 规划和非线性规划某些算法的基础。 基本思路： 基于 LP 问题的标准形式，先设法找到一个基可 行解，判断它是否是最优解，如果是则停止计算；否 则，则转换到相邻的目标函数值不减的一个基可行解. （两个基可行解相邻是指它们之间仅有一个基变量不 相同）