一罐可乐

1. 核心考点梳理#

线性规划（LP）建模是运筹学的基石，要求从实际管理问题中抽象出数学模型。建模三要素包括：

• 决策变量：明确需要决策的数量（如产品产量、投资额度等），需用符号（如 $x_j$）清晰定义并注明单位。
• 目标函数：确定优化的方向（极大化利润 $\max z$ 或极小化成本 $\min z$），必须是决策变量的线性组合。
• 约束条件：包括资源限制、技术标准、比例要求等，均须写为线性等式或不等式，切记不要漏掉非负约束。
• 比例约束的处理（难点）： 若要求产品 $A$ 中原料 1 的比例不低于 $40\%$，设 $x_{A1}$ 为产品 $A$ 中原料 1 的用量，$x_A$ 为产品 $A$ 的总产量（$x_A = \sum x_{Ai}$）。 则约束为：$\frac{x_{A1}}{x_A} \ge 0.4 \implies x_{A1} \ge 0.4 \sum x_{Ai} \implies 0.6 x_{A1} - 0.4 \sum_{i \neq 1} x_{Ai} \ge 0$。

2. 经典自测题#

【题目】 某化工厂计划利用磷酸（Phosphate）、硝酸（Nitrate）和钾肥（Potash）三种原料调配生产 F1 和 F2 两种复合肥。已知原料的日供应量限制、原料成本、每吨复合肥的销售单价及机器工时要求如下表所示：

品质与调配要求：

1. F1 中磷酸的比例不得低于 $30\%$，钾肥的比例不得高于 $40\%$。
2. F2 中硝酸的比例不得低于 $20\%$。
3. 调配过程中的质量损失忽略不计。

请建立以日净利润最大化为目标的线性规划数学模型。

3. 答案与详解#

【第一步：定义决策变量】 由于存在原料向不同产品的分配混合关系，使用双下标变量。 设 $x_{ij}$ 表示用于生产复合肥 $i$（$i=1$ 表示 F1，$i=2$ 表示 F2）的原料 $j$（$j=P$ 表示磷酸，$j=N$ 表示硝酸，$j=K$ 表示钾肥）的吨数。

• F1 的总产量为：$x_{1P} + x_{1N} + x_{1K}$
• F2 的总产量为：$x_{2P} + x_{2N} + x_{2K}$

【第二步：构建目标函数】 目标是最大化日净利润。 $\text{日净利润} = \text{总销售收入} - \text{总原料成本}$ $\text{总收入} = 800(x_{1P} + x_{1N} + x_{1K}) + 1000(x_{2P} + x_{2N} + x_{2K})$ $\text{总成本} = 300(x_{1P} + x_{2P}) + 200(x_{1N} + x_{2N}) + 150(x_{1K} + x_{2K})$ 化简可得目标函数： $\max z = 500x_{1P} + 600x_{1N} + 650x_{1K} + 700x_{2P} + 800x_{2N} + 850x_{2K}$

【第三步：构建约束条件】

1. 原料供应量限制：
   • 磷酸：$x_{1P} + x_{2P} \le 80$
   • 硝酸：$x_{1N} + x_{2N} \le 60$
   • 钾肥：$x_{1K} + x_{2K} \le 50$
2. 设备工时限制： $2(x_{1P} + x_{1N} + x_{1K}) + 3(x_{2P} + x_{2N} + x_{2K}) \le 120$
3. F1 品质约束：
   • 磷酸比例 $\ge 30\%$：$\frac{x_{1P}}{x_{1P} + x_{1N} + x_{1K}} \ge 0.3 \implies 0.7x_{1P} - 0.3x_{1N} - 0.3x_{1K} \ge 0$
   • 钾肥比例 $\le 40\%$：$\frac{x_{1K}}{x_{1P} + x_{1N} + x_{1K}} \le 0.4 \implies -0.4x_{1P} - 0.4x_{1N} + 0.6x_{1K} \le 0$
4. F2 品质约束：
   • 硝酸比例 $\ge 20\%$：$\frac{x_{2N}}{x_{2P} + x_{2N} + x_{2K}} \ge 0.2 \implies -0.2x_{2P} + 0.8x_{2N} - 0.2x_{2K} \ge 0$
5. 非负约束： $x_{ij} \ge 0 \quad (\forall i \in \{1, 2\}, j \in \{P, N, K\})$

1. 核心考点梳理#

• 单纯形表判别：
  • 唯一最优解：所有非基变量检验数 $\sigma_j < 0$（极大化问题）。
  • 无穷多最优解：所有 $\sigma_j \le 0$，且存在某个非基变量的 $\sigma_k = 0$。
  • 无界解：存在某个非基变量的 $\sigma_k > 0$，但该变量对应列的约束系数全部非正（$\le 0$）。
  • 无可行解：迭代结束时基变量中仍含有非零的人工变量。
• 对偶变换法则（对称与非对称）： 极大化问题的对偶是极小化问题，原约束的符号决定对偶变量的符号，原变量的符号决定对偶约束的符号。
• 对偶单纯形法步骤： 适用于检验数全部非正（$\sigma_j \le 0$ 对偶可行），但右端项存在负数（$b_i < 0$ 原问题不可行）的情形。
  1. 换出变量：选右端项负值绝对值最大行对应的基变量。
  2. 换入变量：使用比值判别 $\theta = \min_{j} \{ \frac{\sigma_j}{a'_{rj}} \mid a'_{rj} < 0 \}$，最小比值列对应的非基变量换入。
  3. 旋转运算：进行矩阵初等行变换，使主元变为 1，同列其他元素消为 0。

2. 经典自测题#

已知原线性规划问题为： $\max z = 2x_1 + 3x_2$ $\text{s.t. } \begin{cases} x_1 + 2x_2 \le 8 & \text{（资源 1）} \\ 4x_1 \le 16 & \text{（资源 2）} \\ x_1, x_2 \ge 0 \end{cases}$

引入松弛变量 $x_3, x_4$ 得到最终最优单纯形表如下：

根据此表回答以下问题：

1. 写出该最优单纯形表对应的最优解及最优基逆矩阵 $B^{-1}$。
2. 写出该原规划问题的对偶问题，并直接从最优表中读出对偶问题的最优解。
3. 灵敏度分析（价值系数 $c_j$ 变动）：确定非基变量 $x_1$ 的价值系数 $c_1$ 的变动范围，使得当前最优解保持不变。
4. 灵敏度分析（资源数量 $b_i$ 变动）：若资源 1 数量 $b_1$ 由 8 减少为 3，分析最优解的变化。若发生改变，求出新的最优解。
5. 灵敏度分析（新增产品）：若现在可以开发新产品 $x_5$，其利润 $c_5 = 5$，生产技术系数向量为 $P_5 = [3, 2]^T$（即消耗资源 1 三个单位，不消耗资源 2）。问是否应该投产该新产品？
6. 灵敏度分析（新增约束）：若增加一个新约束条件 $x_1 + x_2 \le 3$，当前最优解是否发生变化？若变化，使用对偶单纯形法求出新最优解。

3. 答案与详解#

【第 1 问：最优解与基逆矩阵】

• 由最终表可得最优解为：$X^* = (x_1^*, x_2^*, x_3^*, x_4^*)^T = (0, 4, 0, 16)^T$，最优目标函数值 $z^* = 12$。
• 基逆矩阵 $B^{-1}$ 为最终表中初始松弛变量（$x_3, x_4$）列对应的系数矩阵： $B^{-1} = \begin{bmatrix} 0.5 & 0 \\ 0 & 1 \end{bmatrix}$

【第 2 问：对偶问题及其最优解】 原问题对应的对偶问题为： $\min w = 8y_1 + 16y_2$ $\text{s.t. } \begin{cases} y_1 + 4y_2 \ge 2 \\ 2y_1 \ge 3 \\ y_1, y_2 \ge 0 \end{cases}$ 由最优单纯形表检验数行中松弛变量对应的检验数绝对值，可直接读出对偶问题的最优解（影子价格）： $y_1^* = -\sigma_3 = 1.5, \quad y_2^* = -\sigma_4 = 0$ 最优对偶目标值 $w^* = 8(1.5) + 16(0) = 12 = z^*$。

【第 3 问：非基变量价值系数变动】 非基变量 $x_1$ 的检验数公式为：$\sigma_1 = c_1 - C_B B^{-1} P_1$。 现设 $c_1$ 变动为 $c_1 + \Delta c_1$。要保持最优解不变，只需更新后的检验数 $\sigma'_1 \le 0$： $\sigma'_1 = \sigma_1 + \Delta c_1 \le 0 \implies -0.5 + \Delta c_1 \le 0 \implies \Delta c_1 \le 0.5$ 即只要新利润 $c_1' \le 2 + 0.5 = 2.5$，当前最优解保持不变。

【第 4 问：资源数量变动与对偶单纯形法】 当资源 1 的数量 $b_1$ 发生变化，资源向量变为 $b' = [3, 16]^T$，其变动量为 $\Delta b = [-5, 0]^T$。 计算变动后的基变量值： $X'_B = B^{-1} b' = \begin{bmatrix} 0.5 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 3 \\ 16 \end{bmatrix} = \begin{bmatrix} 1.5 \\ 16 \end{bmatrix}$ 因为 $X'_B = (x_2', x_4')^T = (1.5, 16)^T \ge 0$，仍然满足原可行性。 所以当前最优基不变，新的最优解为 $X^* = (0, 1.5)^T$，最优值变为 $z^* = 2(0) + 3(1.5) = 4.5$。

【第 5 问：新增产品决策】 计算新产品 $x_5$ 的检验数： $\sigma_5 = c_5 - C_B B^{-1} P_5$ 其中基变量价值系数向量为 $C_B = (c_2, c_4) = (3, 0)$。 $\sigma_5 = 5 - (3, 0) \begin{bmatrix} 0.5 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 3 \\ 2 \end{bmatrix} = 5 - (3, 0) \begin{bmatrix} 1.5 \\ 2 \end{bmatrix} = 5 - 4.5 = 0.5$ 因为 $\sigma_5 = 0.5 > 0$，说明引入新产品 $x_5$ 可以增加总利润。因此应该投产新产品。

【第 6 问：引入新约束与对偶单纯形法】

1. 将当前最优解 $x_1^* = 0, x_2^* = 4$ 代入新约束 $x_1 + x_2 \le 3$： $0 + 4 = 4 > 3$ 不满足新约束。最优解需要改变。
2. 将新约束化为标准型，引入松弛变量 $x_5 \ge 0$： $x_1 + x_2 + x_5 = 3$
3. 利用最终单纯形表中的变换关系，将基变量 $x_2$ 从新约束中消去。 从最终表的第一行可知：$x_2 = 4 - 0.5x_1 - 0.5x_3$。代入新约束： $x_1 + (4 - 0.5x_1 - 0.5x_3) + x_5 = 3 \implies 0.5x_1 - 0.5x_3 + x_5 = -1$ 将此新约束作为最后一行并入单纯形表，得到新的单纯形表：

4. 使用对偶单纯形法进行迭代：
   • 确定换出变量：行 3 右端项为 $-1 < 0$，选基变量 $x_5$ 换出。
   • 确定换入变量：检查第 3 行中系数为负的列，只有 $x_3$ 列对应系数为 $-0.5 < 0$。 计算比值：$\theta = \min \{ \frac{\sigma_3}{a'_{33}} \} = \frac{-1.5}{-0.5} = 3$。所以选择 $x_3$ 换入。
   • 旋转变换：以 $a'_{33} = -0.5$ 为主元，将第 3 行乘以 $-2$，再消去第 1 行的 $x_3$ 项：
     • 新第 3 行：$-1x_1 + 0x_2 + 1x_3 + 0x_4 - 2x_5 = 2$
     • 新第 1 行（第一行减去 $0.5 \times$ 新第三行）：$1x_1 + 1x_2 + 0x_3 + 0x_4 + 1x_5 = 3$
     • 新检验数行（检验数行加上 $1.5 \times$ 新第三行）：$-2x_1 + 0x_2 + 0x_3 + 0x_4 - 3x_5$ 对应 RHS 为 $12 + 1.5 \times 2 = 15$。由于我们是极大化问题，检验数更新为 $\sigma'_j = \sigma_j - \frac{\sigma_k}{a'_{rk}}a'_{rj}$，此处更新后的单纯形表为：

此时右端项常数全部非负（$3, 16, 2 \ge 0$），且所有检验数保持非正（$\le 0$），迭代结束。 新的最优解为：$X^{**} = (x_1^{**}, x_2^{**})^T = (0, 3)^T$，最优目标函数值降为 $z^{**} = 9$。

1. 核心考点梳理#

运输问题通常采用表上作业法求解，关键操作步骤如下：

• 初始可行解确定：考查最小元素法（优先分配运价最低的格子，能最快获得较优初始解）或西北角法。
• 最优性检验：
  • 位势法（常用）：建立方程 $u_i + v_j = c_{ij}$（仅针对基变量/有运量的格子），令首个行位势 $u_1 = 0$，解出所有行位势 $u_i$ 和列位势 $v_j$。
  • 计算非基变量检验数：对所有空格计算 $\sigma_{ij} = c_{ij} - (u_i + v_j)$。
  • 最优解判别：
    • 若为极小化（$\min$）运费问题：所有非基变量检验数 $\sigma_{ij} \ge 0$ 时为最优。
    • 若为极大化（$\max$）利润问题：所有非基变量检验数 $\sigma_{ij} \le 0$ 时为最优。
• 解的调整：若非最优，选择最不满足条件的非基变量（$\min$ 问题选负检验数绝对值最大者；$\max$ 问题选正检验数最大者）作为换入变量，绘制闭回路（Loop），以闭回路偶数顶点上的最小运量为调整量 $\theta$ 进行增减。

2. 经典自测题#

【题目】 已知某公司有 3 个产地（A、B、C） and 3 个销地（X、Y、Z），产销平衡关系及单位运价表如下：

1. 使用最小元素法确定初始可行解，求出初始总运费。
2. 使用位势法对初始解进行最优性检验，求出所有空格的检验数。
3. 若当前非最优解，请写出完整的闭回路调整过程，并求出最优运输方案及最低总运费。

3. 答案与详解#

【第 1 问：最小元素法求初始解】

1. 全表最低运价为 $c_{C, X} = 4$，分配运量：$x_{C, X} = \min(25, 15) = 15$。销地 X 需求满足，产地 C 剩余产量为 10。
2. 剩余未满足格子中最低运价为 $c_{C, Y} = 5$，分配运量：$x_{C, Y} = \min(10, 35) = 10$。产地 C 产量耗尽，销地 Y 还需 25。
3. 剩余未满足格子（A、B 行）中最低运价为 $c_{B, Y} = 11$、$c_{B, Z} = 11$、$c_{A, Y} = 8$。最低为 $c_{A, Y} = 8$，分配运量：$x_{A, Y} = \min(20, 25) = 20$。产地 A 产量耗尽，销地 Y 还需 5。
4. 剩余未满足格子只有 B 行的 $x_{B, Y}$ 和 $x_{B, Z}$。
   • 分配 $x_{B, Y} = 5$，销地 Y 满足。
   • 分配 $x_{B, Z} = 25$，销地 Z 满足。B 产量耗尽。

得到初始运量表如下（括号内为运量）：

初始总运费： $\text{Cost} = 8(20) + 11(5) + 11(25) + 4(15) + 5(10) = 160 + 55 + 275 + 60 + 50 = 600 \text{ 元}$

【第 2 问：位势法计算检验数】 根据基变量格子建立位势方程 $u_i + v_j = c_{ij}$：

• 由 $x_{A, Y} \neq 0 \implies u_A + v_Y = c_{A, Y} = 8$
• 由 $x_{B, Y} \neq 0 \implies u_B + v_Y = c_{B, Y} = 11$
• 由 $x_{B, Z} \neq 0 \implies u_B + v_Z = c_{B, Z} = 11$
• 由 $x_{C, Y} \neq 0 \implies u_C + v_Y = c_{C, Y} = 5$
• 由 $x_{C, X} \neq 0 \implies u_C + v_X = c_{C, X} = 4$

令首个行位势 $u_A = 0$：

• $0 + v_Y = 8 \implies v_Y = 8$
• $u_B + 8 = 11 \implies u_B = 3$
• $3 + v_Z = 11 \implies v_Z = 8$
• $u_C + 8 = 5 \implies u_C = -3$
• $-3 + v_X = 4 \implies v_X = 7$

行位势为：$u = (0, 3, -3)$，列位势为：$v = (7, 8, 8)$。 计算各空格（非基变量）检验数 $\sigma_{ij} = c_{ij} - (u_i + v_j)$：

• $\sigma_{A, X} = c_{A, X} - (u_A + v_X) = 6 - (0 + 7) = -1$
• $\sigma_{A, Z} = c_{A, Z} - (u_A + v_Z) = 10 - (0 + 8) = 2$
• $\sigma_{B, X} = c_{B, X} - (u_B + v_X) = 7 - (3 + 7) = -3$
• $\sigma_{C, Z} = c_{C, Z} - (u_C + v_Z) = 12 - (-3 + 8) = 7$

【第 3 问：闭回路调整与最优解】

1. 确定调整格子：存在负检验数 $\sigma_{B, X} = -3 < 0$，说明当前方案非最优。应将 $x_{B, X}$ 换入。
2. 构建闭回路：从空格 $(B, X)$ 出发，寻找仅由有运量格子作为拐角的闭回路： $(B, X) \rightarrow (B, Y) \rightarrow (C, Y) \rightarrow (C, X) \rightarrow (B, X)$
3. 确定调整量 $\theta$：
   • 奇数项格子（减少运量）：$x_{B, Y} = 5$，$x_{C, X} = 15$。
   • 偶数项格子（增加运量）：$x_{B, X} = 0$，$x_{C, Y} = 10$。
   • 调整量限制：$\theta = \min(x_{B, Y}, x_{C, X}) = \min(5, 15) = 5$。
4. 调整运量：
   • 新 $x_{B, X} = 5$
   • 新 $x_{B, Y} = 5 - 5 = 0$（出基）
   • 新 $x_{C, Y} = 10 + 5 = 15$
   • 新 $x_{C, X} = 15 - 5 = 10$

调整后的运量表如下：

5. 重新进行最优性检验： 基变量为 $x_{A, Y}, x_{B, X}, x_{B, Z}, x_{C, X}, x_{C, Y}$。设新位势 $u'_i, v'_j$，令 $u'_A = 0$：

   • $u'_A + v'_Y = 8 \implies v'_Y = 8$
   • $u'_C + v'_Y = 5 \implies u'_C = -3$
   • $u'_C + v'_X = 4 \implies v'_X = 7$
   • $u'_B + v'_X = 7 \implies u'_B = 0$
   • $u'_B + v'_Z = 11 \implies v'_Z = 11$

   计算空格检验数 $\sigma'_{ij} = c_{ij} - (u'_i + v'_j)$：

   • $\sigma'_{A, X} = 6 - (0 + 7) = -1$ （仍有负检验数！）
   • $\sigma'_{A, Z} = 10 - (0 + 11) = -1$
   • $\sigma'_{B, Y} = 11 - (0 + 8) = 3$
   • $\sigma'_{C, Z} = 12 - (-3 + 11) = 4$

   说明仍非最优。选择最负的 $\sigma'_{A, X} = -1$（或 $\sigma'_{A, Z} = -1$）进行调整。 假设选 $(A, X)$ 换入，构建闭回路： $(A, X) \rightarrow (A, Y) \rightarrow (C, Y) \rightarrow (C, X) \rightarrow (A, X)$ 奇数项：$x_{A, Y} = 20, x_{C, X} = 10$。调整量 $\theta' = \min(20, 10) = 10$。 调整后：

   • 新 $x_{A, X} = 10$
   • 新 $x_{A, Y} = 20 - 10 = 10$
   • 新 $x_{C, Y} = 15 + 10 = 25$
   • 新 $x_{C, X} = 10 - 10 = 0$

   得到新的运量表：

(注：此处因为退化引入 $x_{C, Z} = 0$ 维持基变量数 $m+n-1 = 5$)。 计算位势 $u''_A = 0 \implies v''_X = 6, v''_Y = 8 \implies u''_C = -3, u''_B = 1 \implies v''_Z = 10$。 计算非基变量检验数：

• $\sigma''_{A, Z} = 10 - (0 + 10) = 0 \ge 0$
• $\sigma''_{B, Y} = 11 - (1 + 8) = 2 \ge 0$
• $\sigma''_{C, X} = 4 - (-3 + 6) = 1 \ge 0$

由于所有检验数均非负，因此该运输方案已达到最优。 最优运输方案： A 运往 X：10 吨，运往 Y：10 吨；B 运往 X：5 吨，运往 Z：25 吨；C 运往 Y：25 吨。 最低总运费： $\text{Cost}^* = 6(10) + 8(10) + 7(5) + 11(25) + 5(25) = 60 + 80 + 35 + 275 + 125 = 575 \text{ 元}$

1. 核心考点梳理#

整数规划（IP）限制部分或全部决策变量只能取整数。

• 分支定界法（Branch and Bound）：
  1. 初次松弛：去掉所有整数约束，作为普通 LP 求解。
  2. 定界：若松弛最优解符合整数要求，即为最优解；若不满足，其目标值即为原 IP 的目标上界（极大化问题）。
  3. 分支：选择其中一个非整数的最优解分量 $x_k = v$，分裂为两个互斥子问题约束：$x_k \le \lfloor v \rfloor$ 和 $x_k \ge \lceil v \rceil$。
  4. 剪枝条件：子问题无可行解；子问题松弛最优目标值小于当前已知的可行整数解目标值（丢弃）；子问题求得整数解（更新下界并剪枝）。
• 0-1 变量的应用：
  • 固定费用问题（Fixed Charge Problem）： 若生产某产品存在固定准备费 $k_j$，变动成本为 $c_j$，产量为 $x_j$，最大产能为 $M$。 引入 0-1 变量 $y_j \in \{0, 1\}$ 表示是否生产该产品。 则目标函数成本项为：$k_j y_j + c_j x_j$。 且必须加入关联约束条件：$x_j \le M \cdot y_j$。

2. 经典自测题#

【题目】 某跨国制造企业计划在 A、B、C 三个备选城市中选择建设生产工厂，以满足未来总计 1500 吨的产品市场总需求。决策信息如下：

• 若在城市 $i$ 建厂（$i=A, B, C$），会产生一次性的固定建设投资成本 $F_i$，且该厂有最大生产产能限制 $C_i$。
• 每个城市的单位变动生产及运输总成本为 $v_i$。具体数值见下表：

同时，考虑到公司的地缘战略平衡：

1. A 和 B 两个城市中至少要选择一个建厂。
2. 如果选择在 C 建厂，则必须同时在 A 建厂。

请建立以总成本最小化为目标的 0-1 混合整数规划模型。

3. 答案与详解#

【第一步：定义决策变量】 模型需要同时决策“是否建厂（逻辑决策）”以及“建厂后的生产量（数量决策）”：

• 设 0-1 变量 $y_i \in \{0, 1\}$ 表示建厂决策： $y_i = \begin{cases} 1, & \text{选择在城市 } i \text{ 建厂} \\ 0, & \text{不选择在城市 } i \text{ 建厂} \end{cases} \quad (\forall i \in \{A, B, C\})$
• 设连续变量 $x_i$ 表示在城市 $i$ 的实际产品产量（吨）。

【第二步：构建目标函数】 最小化总建设固定成本与变动生产成本之和： $\min z = 50000y_A + 60000y_B + 40000y_C + 20x_A + 15x_B + 25x_C$

【第三步：构建约束条件】

1. 满足市场总需求约束： $x_A + x_B + x_C \ge 1500$
2. 厂区产量与建厂逻辑及产能上限关联约束： 根据固定费用问题特征，若不建厂（$y_i=0$）则产量必须为 0；若建厂（$y_i=1$）则产量不能超产能上限 $C_i$：
   • 城市 A：$x_A \le 1000 y_A$
   • 城市 B：$x_B \le 1200 y_B$
   • 城市 C：$x_C \le 800 y_C$
3. 厂区选址互斥与依赖约束：
   • A 和 B 中至少选择一个：$y_A + y_B \ge 1$
   • 若在 C 建厂则必须在 A 建厂（即当 $y_C = 1$ 时必有 $y_A = 1$，反之无限制）：$y_C \le y_A$
4. 变量范围约束： $x_A, x_B, x_C \ge 0$ $y_A, y_B, y_C \in \{0, 1\}$

1. 核心考点梳理#

目标规划针对多目标决策问题，允许目标存在偏差。

• 偏差变量的基本性质：$d^+ \ge 0, d^- \ge 0$，且满足极重要红线 $d^+ \cdot d^- = 0$。
• 绝对约束（硬约束）：不允许有任何违背的资源约束，依然保持不等式形式（如 $x_1 + x_2 \le 100$）。
• 目标约束（软约束）：允许未达标或超标，必须加入正负偏差变量化为等式： $f(x) + d^- - d^+ = g$
• 目标函数形式：一律为极小化偏差 $\min z = \sum P_k (w_k^- d_k^- + w_k^+ d_k^+)$。

2. 经典自测题#

【题目】 某家装制造公司生产甲、乙两种实木板材。生产需要消耗木材原料和木工加工工时。已知各项资源限制及产品参数如下：

• 硬性资源限制：公司每日可支配木材原料最大供应量为 120 公斤。生产每单位甲板材需要 2 公斤，每单位乙板材需要 3 公斤。
• 正常生产工时：公司每天有 80 小时的正常工时限制，生产每单位甲需要 1 小时，每单位乙需要 1 小时。超出 80 小时的部分视为加班工时。

公司管理层为下一阶段生产制订了四个不同优先级的目标：

• 第一优先级目标 ($P_1$)：日净销售利润应至少达到 1500 元。生产每单位甲可获利 30 元，每单位乙可获利 50 元。
• 第二优先级目标 ($P_2$)：木材原料的消耗总量控制在 100 公斤以内（尽量避免超额）。
• 第三优先级目标 ($P_3$)：为保障工人福利，尽量避免安排加班工时（即尽量使总工时控制在 80 小时内）。
• 第四优先级目标 ($P_4$)：为了稳定市场占有率，甲板材的日产量应尽可能不少于 20 单位，乙板材的日产量应尽可能不少于 15 单位，且两者的重要性权重之比为 $2:1$。

请建立该问题的多目标目标规划模型。

3. 答案与详解#

【第一步：定义决策变量】

• 设决策变量 $x_1, x_2$ 分别表示甲、乙两种板材的日产量（单位）。
• 引入偏差变量：
  • $d_1^-, d_1^+$ 表示利润目标的负、正偏差。
  • $d_2^-, d_2^+$ 表示木材原料消耗目标（100 公斤）的负、正偏差。
  • $d_3^-, d_3^+$ 表示加工总工时目标（80 小时）的负、正偏差。
  • $d_4^-$ 和 $d_5^-$ 分别表示甲和乙日产量的不足量（负偏差）。

【第二步：构建绝对约束（硬约束）】 木材原料的绝对最大日供应量为 120 公斤： $2x_1 + 3x_2 \le 120$

【第三步：构建目标约束（软约束）】

1. 利润目标约束（目标值 1500 元）： $30x_1 + 50x_2 + d_1^- - d_1^+ = 1500$
2. 木材理想消耗目标约束（目标值 100 公斤）： $2x_1 + 3x_2 + d_2^- - d_2^+ = 100$
3. 加工工时限制约束（目标值 80 小时）： $x_1 + x_2 + d_3^- - d_3^+ = 80$
4. 甲、乙产量目标约束（目标值分别为 20 和 15）：
   • 甲产量约束：$x_1 + d_4^- - d_4^+ = 20$
   • 乙产量约束：$x_2 + d_5^- - d_5^+ = 15$

【第四步：构建目标函数】 根据各级优先因子的诉求，极小化各目标的偏差：

• $P_1$：利润不少于 1500 元，即极小化不足量 $d_1^-$。
• $P_2$：木材不超 100 公斤，即极小化超额量 $d_2^+$。
• $P_3$：避免加班，即极小化超额工时 $d_3^+$。
• $P_4$：甲产量不少于 20，乙产量不少于 15。权重比为 $2:1$，即极小化不足量 $2d_4^- + 1d_5^-$。

由此可得目标函数： $\min z = P_1 d_1^- + P_2 d_2^+ + P_3 d_3^+ + P_4(2d_4^- + d_5^-)$

【第五步：范围约束】 $x_1, x_2 \ge 0, \quad d_k^-, d_k^+ \ge 0 \quad (k=1,2,3,4,5)$

1. 核心考点梳理#

• 最短路问题应用（Dijkstra 算法）：
  • 单源最短路经典求解法，设 $d(i)$ 为节点 $i$ 的临时/永久标记值。
  • 主要用于路径规划、设备更新决策（将设备使用年限作为节点，年更新与维护总费作为弧权）。
• 最大流问题（寻找增广链与标号法）：
  • 标号法步骤：
    1. 寻找一条从源点 $s$ 到汇点 $t$ 的增广链，若无，当前流即为最大流。
    2. 在增广链上计算最大可改进流量 $\theta = \min \{ \theta_f, \theta_b \}$（前向弧可增加量与后向弧可减少量）。
    3. 前向弧流量增加 $\theta$，后向弧流量减少 $\theta$，更新网络。
• 最小费用最大流问题：
  • 在有容量限制的网络中，每条弧同时具有单位运输费用 $w_{ij}$。
  • 求解方法（Successive Shortest Path）： 每次在以单位运费为路权的伴随无向网络（残留网络）上寻找一条从 $s$ 到 $t$ 的最短路。在此路径上用容量上限限制进行流量增广，更新网络流结构，重复此过程直至无法找到增广路径，所得流即为最小费用最大流。

2. 经典自测题#

【自测题 1 - 最短路问题】 已知网络中各节点及弧权值（距离）如下表（无值代表无连接）：

使用 Dijkstra 算法 求从起点 1 到终点 6 的最短距离及路径。

【自测题 2 - 最大流问题】 给定如下容量网络，其中弧上的数字 $(c_{ij})$ 表示该路段的容量上限：

• $s \rightarrow 1$ 容量 10，$s \rightarrow 2$ 容量 5。
• $1 \rightarrow 2$ 容量 2，$1 \rightarrow 3$ 容量 6，$1 \rightarrow 4$ 容量 4。
• $2 \rightarrow 4$ 容量 8。
• $3 \rightarrow t$ 容量 8。
• $4 \rightarrow 3$ 容量 3，$4 \rightarrow t$ 容量 7。 请使用增广链方法求出源点 $s$ 到汇点 $t$ 的最大流总量及各弧流量方案。

【自测题 3 - 最小费用最大流问题】 在自测题 2 的网络拓扑结构及容量基础上，增加每条边上的单位输送费用 $[w_{ij}]$：

• $s \rightarrow 1$ 容量 10，费用 2；$s \rightarrow 2$ 容量 5，费用 8。
• $1 \rightarrow 2$ 容量 2，费用 1；$1 \rightarrow 3$ 容量 6，费用 5；$1 \rightarrow 4$ 容量 4，费用 3。
• $2 \rightarrow 4$ 容量 8，费用 2。
• $3 \rightarrow t$ 容量 8，费用 4。
• $4 \rightarrow 3$ 容量 3，费用 1；$4 \rightarrow t$ 容量 7，费用 6。 求从 $s$ 到 $t$ 的最小费用最大流方案及最小总运费。

3. 答案与详解#

【最短路自测题解答】 使用 Dijkstra 算法迭代步骤：

1. 初始化：$P$ 集合（已确定最短路顶点）为 $\{1\}$，$d(1)=0$；其余 $d(i)=\infty$。
2. 第 1 轮： 从 $1$ 出发更新邻接点：
   • $d(2) = \min(\infty, 0 + 4) = 4$
   • $d(3) = \min(\infty, 0 + 2) = 2$ 选取临时标记中最小者：$d(3)=2$。将 $3$ 并入 $P$，有 $P=\{1, 3\}$。
3. 第 2 轮： 以新确定点 $3$ 更新邻接点：
   • $d(4) = \min(\infty, 2 + 8) = 10$
   • $d(5) = \min(\infty, 2 + 10) = 12$ 临时标记点中最小者为 $d(2)=4$。将 $2$ 并入 $P$，有 $P=\{1, 3, 2\}$。
4. 第 3 轮： 以点 $2$ 更新邻接点：
   • $d(4) = \min(10, 4 + 5) = 9$
   • 当前最小者为 $d(4)=9$。将 $4$ 并入 $P$，有 $P=\{1, 3, 2, 4\}$。
5. 第 4 轮： 以点 $4$ 更新邻接点：
   • $d(5) = \min(12, 9 + 2) = 11$
   • $d(6) = \min(\infty, 9 + 6) = 15$ 当前最小者为 $d(5)=11$。将 $5$ 并入 $P$，有 $P=\{1, 3, 2, 4, 5\}$。
6. 第 5 轮： 以点 $5$ 更新邻接点：
   • $d(6) = \min(15, 11 + 3) = 14$ 确定终点 6 最短距离为 14。

• 最省路径：$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$，最短距离为 14。

【最大流自测题解答】 使用寻找增广链的方法：

1. 初始可行流：设初始各弧流量为 0。
2. 寻找第一条增广链：$s \rightarrow 1 \rightarrow 3 \rightarrow t$
   • 前向弧容量限制：$\min(c_{s1}, c_{13}, c_{3t}) = \min(10, 6, 8) = 6$。
   • 发送流量 $\theta_1 = 6$。
   • 当前各弧流量：$f(s, 1)=6$，$f(1, 3)=6$，$f(3, t)=6$。
3. 寻找第二条增广链：$s \rightarrow 1 \rightarrow 4 \rightarrow t$
   • 前向弧剩余容量：$\min(10-6, 4, 7) = \min(4, 4, 7) = 4$。
   • 发送流量 $\theta_2 = 4$。
   • 流量更新后：$f(s, 1)=10$，$f(1, 4)=4$，$f(4, t)=4$。此时弧 $s \rightarrow 1$ 和 $1 \rightarrow 4$ 均饱和。
4. 寻找第三条增广链：$s \rightarrow 2 \rightarrow 4 \rightarrow t$
   • 剩余容量：$\min(c_{s2}, c_{24}, c_{4t}-f(4, t)) = \min(5, 8, 7-4) = \min(5, 8, 3) = 3$。
   • 发送流量 $\theta_3 = 3$。
   • 流量更新后：$f(s, 2)=3$，$f(2, 4)=3$，$f(4, t)=7$（饱和）。
5. 寻找第四条增广链：$s \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow t$
   • 剩余容量：$\min(5-3, 8-3, 3, 8-6) = \min(2, 5, 3, 2) = 2$。
   • 发送流量 $\theta_4 = 2$。
   • 流量更新后：$f(s, 2)=5$（饱和），$f(2, 4)=5$，$f(4, 3)=2$，$f(3, t)=8$（饱和）。
6. 此时源点 $s$ 出发的弧 $s \rightarrow 1$ 和 $s \rightarrow 2$ 全饱和，无法继续增广。