非线性规划中的序列线性整数规划法基础题 题目描述： 考虑非线性整数规划问题：min f(x) = (x₁-2)² + (x₂-3)²，满足约束条件 x₁ + x₂ ≤ 4，x₁, x₂ ≥ 0，且x₁, x₂为整数。要求使用序列线性整数规划法求解该问题。 解题过程： 方法原理介绍 序列线性整数规划法（SLIP）将非线性整数规划问题转化为一系列线性整数规划子问题。在每个迭代点，对非线性函数进行线性化近似，然后求解得到的线性整数规划问题，逐步逼近原问题的最优解。 初始化步骤 选择初始整数点x⁰ = (0,0)，这是可行域内的整数点。计算初始目标函数值f(x⁰) = (0-2)² + (0-3)² = 13。 第一次迭代 在x⁰处对f(x)进行线性化： 梯度∇f(x) = [ 2(x₁-2), 2(x₂-3) ] 在x⁰处梯度为∇f(x⁰) = [ -4, -6 ] 线性近似：f(x) ≈ f(x⁰) + ∇f(x⁰)ᵀ(x-x⁰) = 13 -4x₁ -6x₂ 建立线性整数规划子问题： min -4x₁ -6x₂ s.t. x₁ + x₂ ≤ 4 x₁, x₂ ≥ 0，且为整数 求解该线性整数规划： 目标函数系数均为负，应取尽可能大的x值 最优解为x¹ = (0,4)，目标值-24 移动限制和可行性保持 为避免线性化误差导致发散，需添加信任域约束|x-x⁰| ≤ Δ。设Δ=2，添加约束： |x₁-0| ≤ 2, |x₂-0| ≤ 2 修正后的子问题： min -4x₁ -6x₂ s.t. x₁ + x₂ ≤ 4 0 ≤ x₁ ≤ 2, 0 ≤ x₂ ≤ 2 x₁, x₂为整数 枚举可行点：(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) 最优解为x¹ = (2,2)，目标值-20 接受新解和信任域调整 计算实际改进：f(x⁰)=13, f(x¹)=(2-2)²+(2-3)²=1 改进显著，接受x¹为新迭代点 扩大信任域Δ=3，准备下一次迭代 第二次迭代 在x¹=(2,2)处线性化： 梯度∇f(x¹) = [ 0, -2 ] 线性近似：f(x) ≈ 1 + 0×(x₁-2) -2×(x₂-2) = 5-2x₂ 子问题： min -2x₂ s.t. x₁ + x₂ ≤ 4 |x₁-2| ≤ 3, |x₂-2| ≤ 3 x₁, x₂ ≥ 0，且为整数 求解得最优解x² = (2,3)（在边界x₁=2,x₂=3处） 收敛检验 计算f(x²)=(2-2)²+(3-3)²=0 与当前最优解比较：f(x¹)=1 > f(x²)=0，有改进 检查相邻整数点，确认x²=(2,3)为局部最优解 最终结果 经过2次迭代，得到最优解x* =(2,3)，最优值f* =0 验证约束：2+3=5>4？不满足！重新检查... 发现错误：x²=(2,3)不满足x₁+x₂≤4的约束 回到第二次迭代，在信任域内寻找可行解： 信任域内满足x₁+x₂≤4的整数点中，使-2x₂最小的为x²=(1,3) 计算f(1,3)=(1-2)²+(3-3)²=1 比当前最优解f=1没有改进，算法终止 最终最优解为x* =(2,2)，f* =1