基于线性规划的“最优货物装载”建模与求解示例
1. 问题描述
假设你有一辆卡车的货厢，其载重量上限为 \(W\) 千克，容积上限为 \(V\) 立方米。有 \(n\) 种不同的货物可供选择，每种货物 \(i\) ( \(i = 1, 2, ..., n\) ) 具有以下属性：
- 单件重量： \(w_i\) 千克
- 单件体积： \(v_i\) 立方米
- 单件利润： \(p_i\) 元
每种货物可装载的数量为整数，但可以装载 0 件或多件，且无数量限制。目标是在不超过卡车载重和容积限制的前提下，选择每种货物的装载件数，使总利润最大。
这是一个典型的多维约束整数线性规划问题，也称为“背包问题”的多维扩展（二维背包问题）。
2. 建立数学模型
设决策变量：
\[x_i = \text{装载货物 } i \text{ 的件数}, \quad i = 1, 2, ..., n \]
则数学模型为：
目标函数（最大化总利润）：
\[\text{Maximize} \quad \sum_{i=1}^{n} p_i x_i \]
约束条件：
\[\begin{cases} \sum_{i=1}^{n} w_i x_i \le W & \quad \text{(载重约束)} \\ \sum_{i=1}^{n} v_i x_i \le V & \quad \text{(容积约束)} \\ x_i \ge 0, \quad x_i \in \mathbb{Z} & \quad \text{(非负整数约束)} \end{cases} \]
3. 求解思路
整数线性规划是 NP-Hard 问题，通常先用线性规划松弛（去掉整数约束）求解连续版本，再结合分支定界或动态规划等方法求整数解。这里我们分三步进行：
- 线性规划松弛： 去掉 \(x_i\) 的整数约束，变成连续线性规划（LP）。
- 求解松弛后的 LP： 如果得到整数解，就是原问题的最优解；否则得到上界和分数解。
- 分支定界： 对分数解的分支变量进行分支，不断搜索整数解。
4. 具体求解步骤
我们以一个具体例子演示：
数据： \(W = 50\) 千克， \(V = 100\) 立方米，货物种类 \(n = 3\)
| 货物 \(i\) | 重量 \(w_i\) (kg) | 体积 \(v_i\) (m³) | 利润 \(p_i\) (元) |
|---|---|---|---|
| 1 | 10 | 20 | 60 |
| 2 | 20 | 30 | 100 |
| 3 | 30 | 40 | 120 |
步骤 1：线性规划松弛模型
松弛为连续变量：
\[\text{Max} \quad 60x_1 + 100x_2 + 120x_3 \]
\[ \begin{cases} 10x_1 + 20x_2 + 30x_3 \le 50 \quad &\text{(重量约束)} \\ 20x_1 + 30x_2 + 40x_3 \le 100 \quad &\text{(体积约束)} \\ x_1, x_2, x_3 \ge 0 \end{cases} \]
步骤 2：图解或单纯形法求解松弛 LP
由于只有 3 个变量，可以画三维图，但更简便的是用单纯形法（这里用线性规划求解器或手工推演）：
- 将不等式转换为等式引入松弛变量 \(s_1, s_2 \ge 0\)：
\[ \begin{cases} 10x_1 + 20x_2 + 30x_3 + s_1 = 50 \\ 20x_1 + 30x_2 + 40x_3 + s_2 = 100 \end{cases} \]
-
目标函数： \(z = 60x_1 + 100x_2 + 120x_3\)。
-
初始基可行解： 选 \(s_1, s_2\) 为基变量， \(x_1 = x_2 = x_3 = 0\)， \(s_1 = 50, s_2 = 100\)，利润 \(z = 0\)。
-
单纯形法迭代：
- 选择进基变量： 目标函数系数最大是 \(x_3\) 的 120。
- 计算离基变量： 对重量约束 \(30x_3 \le 50 \Rightarrow x_3 \le 5/3\)，对体积约束 \(40x_3 \le 100 \Rightarrow x_3 \le 2.5\)，取最小 \(5/3\)，所以 \(s_1\) 离基。
- 用 \(x_3\) 替换 \(s_1\) 在基中，得到新的基变量为 \(x_3, s_2\)。
- 新方程：
\[ \begin{aligned} x_3 &= \frac{5}{3} - \frac{1}{3}x_1 - \frac{2}{3}x_2 - \frac{1}{30}s_1 \\ s_2 &= 100 - 20x_1 - 30x_2 - 40\left(\frac{5}{3} - \frac{1}{3}x_1 - \frac{2}{3}x_2 - \frac{1}{30}s_1\right) \\ &= \frac{100}{3} - \frac{20}{3}x_1 - \frac{10}{3}x_2 + \frac{4}{3}s_1 \end{aligned} \]
- 代入目标函数：
\[ z = 60x_1 + 100x_2 + 120\left(\frac{5}{3} - \frac{1}{3}x_1 - \frac{2}{3}x_2 - \frac{1}{30}s_1\right) = 200 + 20x_1 + 20x_2 - 4s_1 \]
- 非基变量 \(x_1, x_2, s_1\) 系数均为正，但基变量已全为非负，当前解为最优。
- 最优解：
\[ x_1 = 0, \quad x_2 = 0, \quad x_3 = \frac{5}{3} \approx 1.667, \quad s_1 = 0, \quad s_2 = \frac{100}{3} \approx 33.333 \]
最大利润 \(z^* = 200\) 元。
步骤 3：分支定界
松弛最优解 \(x_3 = 1.667\) 不是整数，需分支。
- 原问题整数规划记作 \(P_0\)，上界 \(UB = 200\)，分数解 \(x_3 = 1.667\)。
- 分支： 对 \(x_3\) 分两支：
- 子问题 \(P_1\)： \(x_3 \le 1\)
- 子问题 \(P_2\)： \(x_3 \ge 2\)
求解 \(P_1\)：
增加约束 \(x_3 \le 1\)，松弛 LP 为：
\[\text{Max } 60x_1 + 100x_2 + 120x_3 \]
\[ \begin{cases} 10x_1 + 20x_2 + 30x_3 \le 50 \\ 20x_1 + 30x_2 + 40x_3 \le 100 \\ x_3 \le 1 \\ x_1, x_2, x_3 \ge 0 \end{cases} \]
求解（可用单纯形法，这里省略步骤），得最优解：
\[x_1 = 1, \quad x_2 = 1.2, \quad x_3 = 1, \quad z = 232 \]
但 \(x_2 = 1.2\) 仍不是整数，当前上界 \(UB_1 = 232\)。
求解 \(P_2\)：
增加约束 \(x_3 \ge 2\)，松弛 LP 为：
\[\text{Max } 60x_1 + 100x_2 + 120x_3 \]
\[ \begin{cases} 10x_1 + 20x_2 + 30x_3 \le 50 \\ 20x_1 + 30x_2 + 40x_3 \le 100 \\ x_3 \ge 2 \\ x_1, x_2, x_3 \ge 0 \end{cases} \]
从重量约束 \(30x_3 \le 50 \Rightarrow x_3 \le 1.667\)，与 \(x_3 \ge 2\) 矛盾，无可行解。剪枝。
继续对 \(P_1\) 分支：
当前分数解 \(x_2 = 1.2\)，分支：
- \(P_{11}\)： \(x_2 \le 1\)
- \(P_{12}\)： \(x_2 \ge 2\)
求解 \(P_{11}\)：
约束 \(x_3 \le 1, x_2 \le 1\)。
用单纯形法求解松弛 LP，得：
\[x_1 = 2, \quad x_2 = 1, \quad x_3 = 0, \quad z = 220 \]
这是整数解，记录为候选解，目标值 \(LB = 220\)（当前最优整数解）。
求解 \(P_{12}\)：
约束 \(x_3 \le 1, x_2 \ge 2\)。
求解 LP：
\[x_1 = 0, \quad x_2 = 2, \quad x_3 = 0.333, \quad z = 200 + 40 = 240? \text{ 实际计算：} 100\times2 + 120\times0.333 = 200 + 40 = 240? \]
等，准确计算： 利润 = \(100\times2 + 120\times\frac{1}{3} = 200 + 40 = 240\) 元，但检查约束：
重量： \(20\times2 + 30\times\frac{1}{3} = 40 + 10 = 50\) 正好满足
体积： \(30\times2 + 40\times\frac{1}{3} = 60 + 13.333 = 73.333 \le 100\)，可行。
此时 \(z = 240\)，但 \(x_3 = 0.333\) 分数，上界 240 > 当前 LB = 220，需继续分支。
对 \(P_{12}\) 分支：
对 \(x_3\) 分两支：
- \(P_{121}\)： \(x_3 = 0\)
- \(P_{122}\)： \(x_3 \ge 1\) 但与 \(x_3 \le 1\) 结合为 \(x_3 = 1\)
求解 \(P_{121}\)： \(x_3 = 0, x_2 \ge 2, x_3 \le 1\) 自动满足。
则约束：
\[10x_1 + 20x_2 \le 50, \quad 20x_1 + 30x_2 \le 100, \quad x_2 \ge 2 \]
尝试 \(x_2 = 2\)：
第一个约束 \(10x_1 + 40 \le 50 \Rightarrow x_1 \le 1\)
第二个约束 \(20x_1 + 60 \le 100 \Rightarrow x_1 \le 2\)
取 \(x_1 = 1\)，利润 = \(60 + 200 = 260\) 元？ 但重量约束：10+40=50正好，体积约束：20+60=80<100。 利润 = 260，是整数解（1,2,0）。
但检查： 此时目标函数 260 比上界 240 大？ 这不可能，因为 260 是可行解，但松弛 LP 上界 240 是连续松弛最优值，整数解的目标值不会超过松弛上界，所以计算有误。
我们重新计算 \(P_{121}\)：
重量： \(10x_1 + 20x_2 \le 50\)
体积： \(20x_1 + 30x_2 \le 100\)
目标： \(60x_1 + 100x_2\)
用 \(x_2 = 2\)：
重量： \(10x_1 \le 10 \Rightarrow x_1 \le 1\)
体积： \(20x_1 \le 40 \Rightarrow x_1 \le 2\)
取 \(x_1 = 1\)，利润 = 60+200=260。 但检查重量：10+40=50正好，体积：20+60=80<100，可行。等等，这里确实利润 260 大于之前 LP 上界 240，说明之前的 LP 上界计算在某个分支有误，因为分支加了约束，上界会变化。
我们快速验证原始 LP 上界是否真的 200？ 上面我们算的原始 LP 最优是 200，而整数解 260 大于 200 是不可能，除非原始数据或约束有误。 实际上原始 LP 最优值是 200 没错，但整数解 260 违反了什么？ —— 我们看原始约束：
重量： \(10\times1 + 20\times2 + 30\times0 = 10+40=50\) 满足
体积： \(20\times1 + 30\times2 + 40\times0 = 20+60=80 \le 100\) 满足
利润： 60+200=260 确实比 200 大。 这违反线性规划最优性吗？ 不违反，因为原始 LP 最优解是连续解 \(x_3=1.667, x_1=x_2=0\) 利润 200，但整数解 (1,2,0) 利润 260 更高，说明我们原始 LP 求解有误！
发现错误：原始 LP 求解时，我们只迭代了一次就认为最优，但 \(z = 200 + 20x_1 + 20x_2 - 4s_1\) 中，非基变量 \(x_1, x_2\) 系数为正，说明增加 \(x_1\) 或 \(x_2\) 还能增加利润，所以不是最优，必须继续迭代。 实际上原始 LP 最优解应该是：
我们重新用单纯形法或直接观察：
目标函数： \(60x_1+100x_2+120x_3\)
约束1： \(10x_1+20x_2+30x_3 \le 50\)
约束2： \(20x_1+30x_2+40x_3 \le 100\)
用图解法（二维投影）或单纯形法准确求解：
由于只有 2 个有效约束，最优解在交点之一。 解两个约束等式的交点：
- \(10x_1+20x_2+30x_3 = 50\)
- \(20x_1+30x_2+40x_3 = 100\)
消元：
(2) - 2*(1) 得： \((20x_1+30x_2+40x_3) - 2(10x_1+20x_2+30x_3) = 100 - 100 = 0\)
得到： \(-10x_2 - 20x_3 = 0 \Rightarrow x_2 + 2x_3 = 0 \Rightarrow x_2 = -2x_3\)，由于非负约束，所以 \(x_2 = 0, x_3 = 0\)。
代入(1)： \(10x_1 = 50 \Rightarrow x_1 = 5\)，代入(2)： \(20*5=100\) 满足。 解为 (5,0,0)，利润 300 元。 但检查重量： \(10*5=50\) 满足，体积： \(20*5=100\) 满足。 这是 LP 最优解，且是整数解！ 所以一开始 LP 求解出错了。
纠正：
原来第一次单纯形迭代时，选择 \(x_3\) 进基，但离基变量应选约束最紧的，我们应重新计算比值，但更重要的是，系数判断错误。 实际上，在初始基 \(s_1, s_2\) 时，非基变量在目标函数的系数为正，应进基，但进基变量选择 \(x_1, x_2, x_3\) 中目标系数与约束系数比值最大者，而不是只看目标系数。
我们快速用单纯形表重算：
初始表：
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(s_1\) | 10 | 20 | 30 | 1 | 0 | 50 |
| \(s_2\) | 20 | 30 | 40 | 0 | 1 | 100 |
| z | -60 | -100 | -120 | 0 | 0 | 0 |
进基变量： 选 \(x_3\)（-120 最负，即系数 120 最大），比值 50/30≈1.667, 100/40=2.5，选最小 1.667，所以 \(s_1\) 离基。
主元行除以 30，然后消元，最终得到最优表：
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_3\) | 1/3 | 2/3 | 1 | 1/30 | 0 | 5/3 |
| \(s_2\) | 20/3 | 10/3 | 0 | -4/3 | 1 | 100/3 |
| z | -20 | -20 | 0 | 4 | 0 | 200 |
此时 \(x_1, x_2\) 系数仍为负（-20），还可进基。 选 \(x_1\) 进基，比值：
对 \(x_3\) 行： (5/3)/(1/3)=5
对 \(s_2\) 行： (100/3)/(20/3)=5
一样，任选 \(s_2\) 离基。
主元 20/3，消元后得：
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_3\) | 0 | 1/2 | 1 | 1/20 | -1/20 | 0 |
| \(x_1\) | 1 | 1/2 | 0 | -1/5 | 3/20 | 5 |
| z | 0 | -10 | 0 | 3 | 3 | 300 |
此时 \(x_2\) 系数 -10，还可进基。 进基 \(x_2\)，比值：
对 \(x_3\) 行： 0/(1/2)=0
对 \(x_1\) 行： 5/(1/2)=10
最小非负比值 0，选 \(x_3\) 离基。
主元 1/2，消元得：
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_2\) | 0 | 1 | 2 | 1/10 | -1/10 | 0 |
| \(x_1\) | 1 | 0 | -1 | -1/4 | 1/4 | 5 |
| z | 0 | 0 | 20 | 4 | 2 | 300 |
所有非基变量在目标行系数非负，最优解：
\(x_1 = 5, x_2 = 0, x_3 = 0, s_1 = 0, s_2 = 0\)，利润 = 300。
这正好是整数解，所以原问题的最优整数解就是 \(x_1=5, x_2=0, x_3=0\)，最大利润 300 元。
5. 结论
通过修正计算，我们得到：
- 线性规划松弛最优解是整数解，因此就是原整数规划的最优解。
- 最优装载方案： 只装货物 1 共 5 件，利润 300 元，重量 50 kg 用满，体积 100 m³ 用满。
- 如果松弛解不是整数，则继续用分支定界法搜索。
6. 核心要点
- 多维背包问题可通过整数线性规划建模。
- 通常先求解线性规划松弛，得到上界。
- 若松弛解非整数，用分支定界法枚举整数解。
- 单纯形法求解 LP 时要仔细迭代，避免比值判断错误。
- 整数解可能等于或小于松弛解的目标值。