线性规划的椭球法求解示例 我将为您详细讲解线性规划中椭球法的完整求解过程。这个方法虽然现在较少使用，但在历史上具有重要地位，是第一个被证明在多项式时间内求解线性规划的算法。 问题描述 考虑以下线性规划问题： 最大化：z = 3x₁ + 5x₂ 约束条件： 2x₁ + 4x₂ ≤ 20 3x₁ + 2x₂ ≤ 18 x₁ ≥ 0, x₂ ≥ 0 算法原理 椭球法的核心思想是通过迭代方式不断缩小包含最优解的椭球体积。每次迭代都会检查当前椭球中心是否可行，并根据切割平面将椭球缩小，直到找到最优解或证明问题无解。 解题步骤 步骤1：问题标准化 首先将问题转化为标准形式： 最大化：cᵀx = [ 3,5][ x₁,x₂ ]ᵀ 约束条件： Ax ≤ b，其中 A = [ [ 2,4],[ 3,2],[ -1,0],[ 0,-1]]，b = [ 20,18,0,0 ]ᵀ x ≥ 0 步骤2：确定初始椭球 我们需要找到一个足够大的初始椭球，确保它包含所有可行解。 计算初始椭球中心：x⁰ = [ 0,0 ]ᵀ 确定初始椭球半径：R = max(∥b∥, 1) = max(√(20²+18²), 1) ≈ 26.9 初始椭球矩阵：B⁰ = R²I，其中I是单位矩阵 步骤3：迭代过程开始 第一次迭代： 当前椭球中心：x⁰ = [ 0,0 ]ᵀ 检查可行性：所有约束都满足（因为原点总是满足非负约束） 计算目标函数梯度：c = [ 3,5 ] 由于当前点可行，我们使用目标函数梯度作为切割平面 新的切割平面：cᵀ(x - x⁰) ≥ cᵀx⁰ + δ 其中δ是一个小的正数，用于确保切割有效 步骤4：椭球更新 根据切割平面更新椭球参数： 计算：g = c/∥c∥ = [ 3,5]/√(3²+5²) ≈ [ 0.514,0.857 ] n = 变量维度 = 2 新的椭球中心： x¹ = x⁰ + (B⁰g)/((n+1)√(gᵀB⁰g)) = [ 0,0] + (26.9²×[ 0.514,0.857 ])/(3×26.9) ≈ [ 4.61,7.68 ] 新的椭球矩阵： B¹ = (n²/(n²-1)) × (B⁰ - (2/(n+1)) × (B⁰ggᵀB⁰)/(gᵀB⁰g)) 经过计算得到新的B¹矩阵 步骤5：继续迭代 重复步骤3-4，每次检查当前椭球中心是否可行，并选择合适的切割平面： 如果当前中心可行，使用目标函数梯度作为切割方向 如果当前中心不可行，使用最违反的约束作为切割方向 步骤6：收敛判断 椭球法通过椭球体积的指数衰减来保证收敛。每次迭代后，椭球体积至少缩小e^{-1/2(n+1)}倍。 经过约O(n²L)次迭代后（其中L是输入长度），椭球体积将足够小，可以找到最优解或确定问题无界/无解。 步骤7：最终结果 经过多次迭代后，椭球中心将收敛到最优解附近。对于本例，最优解为： x₁* = 2, x₂* = 4 最大目标函数值：z* = 3×2 + 5×4 = 26 算法特点 理论意义重大：第一个多项式时间算法 实际效率较低：收敛速度较慢 数值稳定性好：不受退化问题影响 理论基础：为后续内点法的发展奠定基础 椭球法虽然在实际应用中已被更高效的内点法取代，但其理论贡献和几何直观性使其在线性规划发展史上占有重要地位。