基于线性规划的二次规划问题求解示例
问题描述
某工厂生产两种产品，其单位利润分别为 \(c_1 = 3\) 和 \(c_2 = 5\)，但利润随产量增加而边际递减，需考虑成本函数 \(\frac{1}{2}x_1^2 + x_2^2\)。生产需满足资源约束：
- 原材料：\(2x_1 + 3x_2 \leq 10\)
- 工时：\(x_1 + 2x_2 \leq 6\)
- 非负性：\(x_1, x_2 \geq 0\)
目标函数为总利润最大化：
\[\max \, z = 3x_1 + 5x_2 - \frac{1}{2}x_1^2 - x_2^2 \]
该问题为凸二次规划（目标函数为凹函数，Hessian矩阵负定），可用线性规划逼近或直接求解。
解题过程
步骤1：问题标准化
将最大化问题转化为最小化问题，并写成标准形式：
\[\min \, f(x) = -3x_1 - 5x_2 + \frac{1}{2}x_1^2 + x_2^2 \]
约束条件：
\[\begin{cases} 2x_1 + 3x_2 \leq 10 \\ x_1 + 2x_2 \leq 6 \\ x_1, x_2 \geq 0 \end{cases} \]
步骤2：构造拉格朗日函数
引入松弛变量 \(s_1, s_2 \geq 0\) 将不等式转为等式：
\[2x_1 + 3x_2 + s_1 = 10, \quad x_1 + 2x_2 + s_2 = 6 \]
拉格朗日函数为：
\[L(x, \lambda) = \frac{1}{2}x_1^2 + x_2^2 - 3x_1 - 5x_2 + \lambda_1(2x_1 + 3x_2 + s_1 - 10) + \lambda_2(x_1 + 2x_2 + s_2 - 6) \]
其中 \(\lambda_1, \lambda_2 \geq 0\) 为对偶变量。
步骤3：KKT条件
根据Karush-Kuhn-Tucker条件，最优解需满足：
- 梯度条件：
\[\frac{\partial L}{\partial x_1} = x_1 - 3 + 2\lambda_1 + \lambda_2 = 0 \]
\[\frac{\partial L}{\partial x_2} = 2x_2 - 5 + 3\lambda_1 + 2\lambda_2 = 0 \]
- 互补松弛条件：
\[\lambda_1(2x_1 + 3x_2 - 10) = 0, \quad \lambda_2(x_1 + 2x_2 - 6) = 0 \]
- 可行性条件：原约束和非负性成立。
步骤4：分情况讨论约束活跃性
-
情况1：两个约束均不活跃（\(\lambda_1 = \lambda_2 = 0\)）
梯度条件化为 \(x_1 = 3, x_2 = 2.5\)，但代入约束1得 \(2 \times 3 + 3 \times 2.5 = 13.5 > 10\)，不可行。 -
情况2：仅约束1活跃（\(\lambda_1 > 0, \lambda_2 = 0\)）
由约束1等式和梯度条件：
\[2x_1 + 3x_2 = 10, \quad x_1 - 3 + 2\lambda_1 = 0, \quad 2x_2 - 5 + 3\lambda_1 = 0 \]
解得 \(x_1 = 1, x_2 = 8/3 \approx 2.67, \lambda_1 = 1\)。检查约束2：\(1 + 2 \times 2.67 = 6.34 > 6\)，不可行。
-
情况3：仅约束2活跃（\(\lambda_1 = 0, \lambda_2 > 0\)）
类似解得 \(x_1 = 2, x_2 = 2, \lambda_2 = 1\)。检查约束1：\(2 \times 2 + 3 \times 2 = 10 \leq 10\)（恰好满足），但此时约束1也活跃，需转入情况4。 -
情况4：两个约束均活跃（\(\lambda_1 > 0, \lambda_2 > 0\)）
解方程组：
\[2x_1 + 3x_2 = 10, \quad x_1 + 2x_2 = 6 \]
得 \(x_1 = 2, x_2 = 2\)。代入梯度条件：
\[2 - 3 + 2\lambda_1 + \lambda_2 = 0 \implies 2\lambda_1 + \lambda_2 = 1 \]
\[4 - 5 + 3\lambda_1 + 2\lambda_2 = 0 \implies 3\lambda_1 + 2\lambda_2 = 1 \]
解得 \(\lambda_1 = 1, \lambda_2 = -1\)（不满足非负性），无效。
步骤5：重新检验情况3的可行性
在情况3中，约束2活跃（\(x_1 + 2x_2 = 6\)），但约束1未活跃（\(2x_1 + 3x_2 < 10\)），需强制 \(\lambda_1 = 0\)。梯度条件：
\[x_1 - 3 + \lambda_2 = 0, \quad 2x_2 - 5 + 2\lambda_2 = 0 \]
结合 \(x_1 + 2x_2 = 6\)，解得 \(x_1 = 2.5, x_2 = 1.75, \lambda_2 = 0.5\)。检查约束1：\(2 \times 2.5 + 3 \times 1.75 = 10.25 > 10\)，不可行。
步骤6：最终有效解
尝试边界点：
- 交点 \((2, 2)\)：目标值 \(3 \times 2 + 5 \times 2 - 0.5 \times 4 - 4 = 6 + 10 - 2 - 4 = 10\)
- 点 \((0, 3)\)（约束2活跃）：目标值 \(0 + 15 - 0 - 9 = 6\)
- 点 \((5, 0)\)（不可行，约束2违反）
- 点 \((0, 0)\)：目标值 \(0\)
比较得最优解为 \(x_1 = 2, x_2 = 2\)，最大利润为 \(10\)。
总结
本例通过KKT条件系统分析约束活跃性，逐步排除无效情况，最终找到满足所有条件的最优解。二次规划问题在凸性保证下，局部最优即全局最优。