拉格朗日乘子与单纯形乘子关系探讨

The Relationship Between Lagrangian Multiplier and Simplex Multiplier

拉格朗日乘子法是求解含等式约束极值问题的有效方法,其核心思想是通过引入拉格朗日乘子将条件极值问题转化为无条件极值问题,而单纯形方法是求解带不等式约束的线性规划问题的经典方法,其矩阵描述中含有单纯形乘子参数,即影子价格.在线性规划的基本可行解非退化的假设下,证明了单纯形乘子就是拉格朗日乘子.通过数值实验验证了理论分析,特别地,通过实际例子说明了当最优解是退化基可行解时,拉格朗日乘子可能包含了单纯形乘子.

Lagrange multiplier method is an effective method for solving optimization problems with equality constraints.Its core idea is to transform the conditional optimization problem into unconditional optimization problem by introducing Lagrange multiplier.The simplex method is a classical method for solving linear programming problems with inequality constraints.Its matrix description contains simplex multiplier parameters,namely shadow price in some situations.Under the assumption that the optimal basic feasible solution of linear programming is non degenerate,we prove that the simplex multiplier is Lagrange multiplier.Finally,the theoretical analysis is verified by numerical experiments.In particular,we show that the Lagrange multiplier may include simplex multipliers when the optimal solution is a degenerate basis feasible solution.