1954年，美国数学家C.莱姆基提出了对偶单纯形法，这是一种创新的求解优化问题的方法。单纯形法的核心是通过迭代从一个可行解逐步接近最优解，直至检验数符合最优性条件。而对偶单纯形法则是从另一个角度出发，它从满足对偶可行性条件的解开始，通过迭代寻找原始问题的最优解。这种方法的关键在于，始终维护基解的对偶可行性，使得问题的不可行性逐渐消失。
具体来说，如果原始问题可以表述为最小化目标函数cx，即min{cx|Ax=b，x≥0}，那么其对偶问题则为最大化y与A的乘积，但限制在yA≤c，即max{yb|yA≤c}。当原始问题的一个基解达到了最优性，其检验数c乘以基解矩阵BB-1的转置减去A再减去c的值小于或等于零，即y=cBB-1（简称为单纯形算子）成为对偶问题的可行解。
对偶可行性的满足意味着检验数满足最优性条件。因此，在保持对偶可行性的前提下，一旦基解变为可行解，就表明已经找到了原始问题的最优解。这种转换策略使得对偶单纯形法成为求解复杂优化问题的强大工具。
单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。