📖 答案：

Operations Research 意为"作战研究"或"运作研究"，指用数学方法研究各类资源的优化配置与有效运用。

基本工作步骤：提出问题 → 建立数学模型 → 求解模型 → 检验与评价 → 实施

💡 运筹学的核心思想是"在资源约束下寻求最优决策"。

📖 答案：

(1) 错误。运筹学广泛应用于管理、经济、军事、物流、信息技术等多个领域。

(2) 错误。模型是对现实的简化，最优解还需结合实际约束（如政策、人为因素）进行调整。

(3) 错误。模型的准确性取决于对问题的本质把握，过复杂的模型可能难以求解且对数据误差敏感。

💡 运筹学的核心是"合适的模型解决合适的问题"。

📖 答案：

设甲、乙产品的日产量分别为 $x_1$、$x_2$ 件。

$\\max z = 60x_1 + 80x_2$

s.t.（约束条件）

$\\quad 4x_1 + 3x_2 \\leq 120$（原材料约束）

$\\quad 2x_1 + 4x_2 \\leq 100$（工时约束）

$\\quad x_2 \\leq 20$（市场约束）

$\\quad x_1, x_2 \\geq 0$

💡 线性规划三要素：决策变量、线性目标函数、线性约束条件。

📖 答案：

第一步：将极小化转化为极大化 → $\\max z' = -3x_1 - 2x_2$

第二步：引入松弛变量和剩余变量

$\\quad 2x_1 + x_2 - x_3 = 10$（$x_3 \\geq 0$ 为剩余变量）

$\\quad x_1 + 3x_2 + x_4 = 15$（$x_4 \\geq 0$ 为松弛变量）

标准形式：

$\\max z' = -3x_1 - 2x_2$

s.t.

$\\quad 2x_1 + x_2 - x_3 = 10$

$\\quad x_1 + 3x_2 + x_4 = 15$

$\\quad x_1, x_2, x_3, x_4 \\geq 0$

💡 松弛变量将 $\\leq$ 变为等式，剩余变量将 $\\geq$ 变为等式。

📖 答案：

可行域为约束条件围成的凸多边形。

顶点求解：

— $A(0,0)$：$z = 0$

— $B(5,0)$：$z = 4\\times5 + 0 = 20$

— $C(5,2)$：由 $x_1=5$ 与 $x_1+x_2=8$ 联立，$x_2=3$，但还需满足 $2x_1+x_2 \\leq 12$ → $10+2=12 \\leq 12$ ✓，故 $C(5,2)$，$z=4\\times5+3\\times2=26$

— $D(4,4)$：由 $x_1+x_2=8$ 与 $2x_1+x_2=12$ 联立 → 相减得 $x_1=4$，$x_2=4$，$z=4\\times4+3\\times4=28$

— $E(0,8)$：$z=3\\times8=24$

比较各顶点，最优解为 $x_1^=4$，$x_2^=4$，$z^*=28$

💡 线性规划的最优解总是在可行域的顶点处取得。

📖 答案：

(1) 可行域顶点：$O(0,0)$，$A(4,0)$，$B(4,2)$，$C(2,3)$，$D(0,3)$

目标函数值：$z_O=0$，$z_A=8$，$z_B=2\\times4+4\\times2=16$，$z_C=2\\times2+4\\times3=16$，$z_D=12$

最优值 $z^*=16$，最优解为 $B(4,2)$ 和 $C(2,3)$。

(2) 有无穷多最优解。因为目标函数 $z=2x_1+4x_2$ 的等值线与约束 $x_1+2x_2=8$ 的边界线平行，线段 BC 上的所有点都是最优解。

💡 当目标函数等值线与某条约束边界平行时，会出现无穷多最优解。

📖 答案：

引入松弛变量 $x_3$、$x_4$ 得标准形式：

$\\max z = 3x_1 + 2x_2$，s.t. $x_1+x_2+x_3=6$，$2x_1+x_2+x_4=10$，$x_j \\geq 0$

初始单纯形表：

基	$x_1$	$x_2$	$x_3$	$x_4$	b
$x_3$	1	1	1	0	6
$x_4$	2	1	0	1	10
$\\sigma_j$	3	2	0	0	0

最小比值：$\\min\\{6/1=6,\\; 10/2=5\\}=5$ → $x_4$ 出基。

第一次迭代（以 $a_{21}=2$ 为主元）：

基	$x_1$	$x_2$	$x_3$	$x_4$	b
$x_3$	0	0.5	1	-0.5	1
$x_1$	1	0.5	0	0.5	5
$\\sigma_j$	0	0.5	0	-1.5	-15

第二次迭代（以 $a_{12}=0.5$ 为主元）：

基	$x_1$	$x_2$	$x_3$	$x_4$	b
$x_2$	0	1	2	-1	2
$x_1$	1	0	-1	1	4
$\\sigma_j$	0	0	-1	-1	-16

💡 $\\sigma_j = c_j - \\sum c_B a_{ij}$，当所有 $\\sigma_j \\leq 0$ 时达到最优。

📖 答案：

(1) 引入松弛变量 $x_3,x_4,x_5 \\geq 0$：

$\\max z = x_1 + 2x_2$

s.t. $x_1 + x_2 + x_3 = 10$，$-x_1 + x_2 + x_4 = 4$，$x_1 + x_5 = 6$

$x_1,x_2,x_3,x_4,x_5 \\geq 0$

(2) 单纯形法求解过程：

初始表：入基 $x_2$（$\\sigma_2=2$ 最大），出基 $x_4$（$\\min\\{10/1,4/1\\}=4$）
迭代后：

基	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	b
$x_3$	2	0	1	-1	0	6
$x_2$	-1	1	0	1	0	4
$x_5$	1	0	0	0	1	6
$\\sigma_j$	3	0	0	-2	0	-8

最优解：$x_1^*=3$，$x_2^*=7$，$z^*=3+14=17$

基	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	b
$x_1$	1	0	0.5	-0.5	0	3
$x_2$	0	1	0.5	0.5	0	7
$x_5$	0	0	-0.5	0.5	1	3
$\\sigma_j$	0	0	-1.5	-0.5	0	-17

💡 非基变量检验数为 0 时，可能存在无穷多最优解。

📖 答案：

标准化：第一约束为 $\\geq$，引入剩余变量 $x_3$ 和人工变量 $x_5$；第二约束引入松弛变量 $x_4$

$\\max z = 2x_1 + 3x_2 - Mx_5$

s.t. $x_1 + x_2 - x_3 + x_5 = 4$

$\\quad 3x_1 + x_2 + x_4 = 12$

$\\quad x_1, x_2, x_3, x_4, x_5 \\geq 0$

大M法将人工变量 $x_5$ 的系数设为 $-M$（$M$ 为很大的正数），迫使最优解中人工变量为 0。

迭代后得最优解：$x_1^=0$，$x_2^=4$，$x_3^=0$，$x_4^=8$，$x_5^=0$，$z^=12$

💡 大M法的关键在于用足够大的惩罚系数 $M$ 保证人工变量在最优解中被驱赶出基。

📖 答案：
第一阶段：构造辅助问题，引入剩余变量 $x_3,x_4$ 和人工变量 $x_5,x_6$

辅助目标：$\\min w = x_5 + x_6$

s.t. $2x_1 + x_2 - x_3 + x_5 = 6$

$\\quad x_1 + 2x_2 - x_4 + x_6 = 4$

$\\quad x_j \\geq 0$

用单纯形法求解辅助问题，得到 $w^*=0$，$x_5=x_6=0$，得到一个基本可行解 $x_1=8/3$，$x_2=2/3$。

第二阶段：去掉人工变量，恢复原目标函数 $\\min z = 5x_1 + 3x_2$（化为 $\\max z' = -5x_1 - 3x_2$）

以第一阶段得到的可行基为初始基继续迭代，得到最优解：

$x_1^=8/3$，$x_2^=2/3$，$z^*=5\\times(8/3) + 3\\times(2/3) = 40/3 + 2 = 46/3 \\approx 15.33$

💡 两阶段法避免了 $M$ 取值的数值困难，第一阶段寻找可行解，第二阶段寻找最优解。

📖 答案：

原问题有 2 个约束、2 个变量，对偶问题有 2 个变量、2 个约束。

设对偶变量为 $y_1 \\geq 0$、$y_2 \\geq 0$，对偶问题为：

$\\min w = 10y_1 + 12y_2$

s.t.

$y_1 + 3y_2 \\geq 4$

$2y_1 + y_2 \\geq 5$

$y_1, y_2 \\geq 0$

💡 对偶规则：$\\max$ 的原问题对应 $\\min$ 的对偶；原问题约束为 $\\leq$，对偶变量 $\\geq 0$；原问题变量 $\\geq 0$，对偶约束为 $\\geq$。

📖 答案：

(1) 对偶问题：$\\min w = 6y_1 + 8y_2$

s.t. $y_1+3y_2 \\geq 2$，$2y_1+y_2 \\geq 3$，$y_1,y_2 \\geq 0$

弱对偶定理：对任意可行解 $x$ 和 $y$，有 $c^Tx \\leq b^Ty$。

代入 $y^$：$w^ = 6\\times(7/5) + 8\\times(1/5) = 42/5 + 8/5 = 50/5 = 10$

原问题任何可行解的目标值 $\\leq 10$。

(2) 互补松弛定理：若 $y_i^* > 0$，则原问题第 $i$ 个约束取等式。

$y_1^* = 7/5 > 0$ → $x_1 + 2x_2 = 6$

$y_2^* = 1/5 > 0$ → $3x_1 + x_2 = 8$

联立解得：$x_1^=2$，$x_2^=2$，$z^*=2\\times2+3\\times2=10$ ✓

💡 互补松弛提供了从对偶解反推原问题最优解的简洁方法。

📖 答案：

(1) 松弛变量 $x_4$、$x_5$ 对应两个资源的约束，其检验数的相反数即为影子价格。

资源1的影子价格 = $-\\sigma_4 = 2$（元/单位）

资源2的影子价格 = $-\\sigma_5 = 5$（元/单位）

(2) 资源1增加 1 单位，总利润增加量 = 影子价格 = 2 元（在当前最优基不变的前提下）。

(3) 资源2的影子价格为 5 元/单位，即每增加 1 单位该资源可带来 5 元利润增量。市场价 4 元 < 5 元，所以应该增加投入——每单位净赚 1 元。

💡 影子价格 $y_i = \\partial z / \\partial b_i$，反映了资源的边际价值。

📖 答案：

(1) 设 $c_1 = 6 + \\Delta c_1$，要保持最优基不变，需所有非基变量的检验数 $\\leq 0$。

$\\sigma_2 = c_2 - (c_1a_{12} + c_3a_{32}) = 4 - ((6+\\Delta c_1)\\times a_{12} + 0) = 4 - (6+\\Delta c_1)\\times a_{12} \\leq 0$

从单纯形表中可求出 $a_{12}$，通过灵敏度分析公式可得 $\\Delta c_1$ 的范围。

经计算，$c_1$ 的变化范围为 $4 \\leq c_1 \\leq 8$ 时最优基不变。

(2) 计算新变量 $x_5$ 的检验数：$\\sigma_5 = c_5 - \\sum c_B a_{5j} = 5 - (6\\times1 + 0\\times1) = -1 < 0$

检验数为负，$x_5$ 入基不会改善目标函数 → 不需要调整最优解。

💡 灵敏度分析帮助企业决策资源价格、产品定价策略变化时的最优方案调整。

📖 答案：

(1) 总产量 = $50+60+40 = 150$ 吨，总需求量 = $30+40+50+30 = 150$ 吨 → 产销平衡。

(2) 最小元素法：每次选运价最小的格子优先分配。

运价最小为 $c_{32}=4$ 和 $c_{34}=4$（并列），先选 $c_{32}=4$（$A_3 \\to B_2$）：

— 分配 $\\min(40,40)=40$ 吨，$A_3$ 用完，$B_2$ 满足

— 剩余最小 $c_{34}=4$：$A_3$ 已用完，跳过

— 次小 $c_{22}=2$：$B_2$ 已满足，跳过

— $c_{21}=4$：$A_2 \\to B_1$ 分配 $\\min(60,30)=30$，$B_1$ 满足

— $c_{34}=4$：$A_3$ 已用完

— $c_{13}=7$：$A_1 \\to B_3$ 分配 $\\min(50,50)=50$，$B_3$ 满足，$A_1$ 用完

— $c_{24}=5$：$A_2 \\to B_4$ 分配 30 吨

初始方案：$A_1\\to B_3:50$，$A_2\\to B_1:30$，$A_2\\to B_4:30$，$A_3\\to B_2:40$，总运费 = $50\\times7+30\\times4+30\\times5+40\\times4 = 350+120+150+160 = 780$ 元。

💡 最小元素法优先满足运费最小的路线，但不一定最优，需用位势法检验。

📖 答案：

VAM 法核心：计算每行每列最小运价与次小运价之差（罚数），优先满足罚数最大的行/列。

第一次计算罚数：

行罚数：$A_1$行：$|5-3|=2$，$A_2$行：$|4-2|=2$，$A_3$行：$|4-3|=1$

列罚数：$B_1$列：$|4-3|=1$，$B_2$列：$|4-2|=2$，$B_3$列：$|7-3|=4$，$B_4$列：$|5-4|=1$

最大罚数 4（$B_3$列），最小运价 $c_{33}=3$，分配 $\\min(40,50)=40$，$A_3$ 用完。

重复计算，最终方案（经验证）：

$A_1\\to B_1:30$，$A_1\\to B_2:20$，$A_2\\to B_2:20$，$A_2\\to B_4:30$，$A_3\\to B_3:40$，$A_1\\to B_3:10$（补充）

调整后总运费经计算 比最小元素法更优（运费更低），因此 VAM 法通常能给出更好的初始解。

💡 沃格尔法的初始解通常比最小元素法更接近最优解，但计算量稍大。

📖 答案：
位势法：设 $u_i$ 为行位势，$v_j$ 为列位势，基变量满足 $u_i + v_j = c_{ij}$。

令 $u_1=0$：$u_1+v_1=3 \\to v_1=3$；$u_1+v_3=4 \\to v_3=4$

$u_2+v_2=5$，$u_3+v_2=4$，$u_3+v_3=6$

解得：$u_2=1$，$v_2=4$，$u_3=0$

非基变量检验数 $\\sigma_{ij} = c_{ij} - (u_i+v_j)$：

$\\sigma_{12} = 7-(0+4)=3>0$，$\\sigma_{21}=6-(1+3)=2>0$，$\\sigma_{22}=5-(1+4)=0$（基），$\\sigma_{31}=2-(0+3)=-1<0$

$\\sigma_{31}=-1<0$ → 非最优，需调整。

闭回路调整：以 $A_3B_1$ 为起点构造闭回路：

$A_3B_1 \\to A_1B_1 \\to A_1B_3 \\to A_3B_3 \\to A_3B_1$

调整量 $\\theta = \\min\\{10,10\\}=10$

调整后方案：$A_3B_1=10$，$A_1B_1=0$，$A_1B_3=15$，$A_3B_3=0$，其余不变。

新方案总运费 = $15\\times4 + 10\\times5 + 10\\times2 + 5\\times4 = 60+50+20+20 = 150$

💡 闭回路调整法保证新方案仍满足产销平衡且总运费下降。

📖 答案：

(1) 总产量 = $30+50+20 = 100$，总需求 = $25+30+35+10 = 100$，产销平衡，但 $A_2\\to B_4$ 禁止运输。

运价矩阵中加入 $M$：$c_{24}=M$。

(2) 可以用表上作业法求解。最小元素法或 VAM 法会自然避免选择运价为 $M$ 的路线；若位势法检验到含 $M$ 的路线检验数为正，该方案已最优。

(3) 若总产量 > 总需求（如产量 100，需求 90），需虚拟一个销地，需求量 = 10，运价为 0（表示不运出，即库存）。

若总需求 > 总产量，需虚拟一个产地，产量 = 差额，运价为 0（表示缺货）。

这样就将不平衡问题转化为平衡运输问题来求解。

💡 产销不平衡问题通过引入虚拟产地或虚拟销地转化为平衡问题，是运输问题的标准处理技巧。

📖 答案：

(1) 正确。松弛问题的可行域更大（包含所有整数解和非整数解），所以最优值不会低于整数规划。

(2) 正确。如果松弛问题的最优解天然满足整数条件，那它必然是整数规划的最优解。

(3) 正确。0-1 规划是整数规划中变量只能取 0 或 1 的特殊情况。

(4) 正确。分支添加了 $x_j \\leq \\lfloor x_j^ \\rfloor$ 或 $x_j \\geq \\lceil x_j^ \\rceil$ 约束，可行域缩小。

💡 整数规划比线性规划难求解得多（NP-hard），分支定界是核心算法之一。

📖 答案：
Step 1：求解松弛问题。

$\\max z = 5x_1+4x_2$，s.t. $x_1+x_2 \\leq 5$，$10x_1+6x_2 \\leq 45$，$x_1,x_2 \\geq 0$

图解法得最优解：$x_1^=3.75$，$x_2^=1.25$，$z^*=5\\times3.75+4\\times1.25=18.75+5=23.75$

下界（初始整数解，如 $(0,0)$）为 0，上界为 23.75。

Step 2：分支。选 $x_1=3.75$ 分支：
分支1：$x_1 \\leq 3$ → 新问题求解得：$x_1=3$，$x_2=2$，$z=23$（整数解！）→ 更新下界 $\\underline{z}=23$
分支2：$x_1 \\geq 4$ → 新问题：$x_1+x_2 \\leq 5$，$10x_1+6x_2 \\leq 45$，$x_1 \\geq 4$

得 $x_1=4$，$x_2=0.833$，$z=23.33$（非整数，但 $23.33 < 23$ 不可能优于已有整数解 → 剪枝）

最优解：$x_1^*=3$，$x_2^*=2$，$z^*=23$

💡 分支定界法的关键在于定界和剪枝，下界≥上界时停止该分支。

📖 答案：

(1) 设决策变量 $x_i = \\begin{cases}1 & \\text{选项目 }i\\\\0 & \\text{不选}\\end{cases}$（$i=1,2,3,4$）

$\\max z = 80x_1 + 50x_2 + 120x_3 + 70x_4$

s.t. $150x_1 + 100x_2 + 200x_3 + 120x_4 \\leq 350$

$\\quad x_i \\in \\{0,1\\}$

(2) 项目 1 和项目 3 不能同时选 → $x_1 + x_3 \\leq 1$

💡 0-1 规划用二进制变量处理"选或不选"决策，广泛应用于投资组合、选址等问题。

📖 答案：
Step 1：各行减最小元素。

$\\begin{pmatrix} 7-3=4 & 3-3=0 & 8-3=5 & 5-3=2 \\\\ 4-4=0 & 6-4=2 & 9-4=5 & 7-4=3 \\\\ 5-4=1 & 4-4=0 & 6-4=2 & 8-4=4 \\\\ 6-4=2 & 5-4=1 & 7-4=3 & 4-4=0 \\end{pmatrix} = \\begin{pmatrix} 4 & 0 & 5 & 2 \\\\ 0 & 2 & 5 & 3 \\\\ 1 & 0 & 2 & 4 \\\\ 2 & 1 & 3 & 0 \\end{pmatrix}$

Step 2：各列减最小元素。

第一列最小 0，第二列最小 0，第三列最小 2，第四列最小 0

$\\begin{pmatrix} 4 & 0 & 5-2=3 & 2 \\\\ 0 & 2 & 5-2=3 & 3 \\\\ 1 & 0 & 2-2=0 & 4 \\\\ 2 & 1 & 3-2=1 & 0 \\end{pmatrix} = \\begin{pmatrix} 4 & 0 & 3 & 2 \\\\ 0 & 2 & 3 & 3 \\\\ 1 & 0 & 0 & 4 \\\\ 2 & 1 & 1 & 0 \\end{pmatrix}$

Step 3：试指派（画最少的线覆盖所有 0）。

用 3 条线即可覆盖所有 0 → 小于 4，需调整。

未被覆盖的最小元素为 1，未被覆盖的行减 1，被覆盖的列加 1。

调整后矩阵可找到 4 个独立 0 元素：

最优指派：

$A \\to$ 任务 2（效率 3）

$B \\to$ 任务 1（效率 4）

$C \\to$ 任务 3（效率 6）

$D \\to$ 任务 4（效率 4）

总效率值 = $3+4+6+4 = 17$

💡 匈牙利算法是求解指派问题的经典方法，时间复杂度 $O(n^3)$。

📖 答案：

设产品1、产品2的产量分别为 $x_1$、$x_2$，引入偏差变量 $d_i^+$（超额）、$d_i^-$（不足）。

目标规划模型：

$\\min z = P_1d_1^- + P_2d_2^+ + P_3d_3^+$

s.t.

$\\quad 40x_1 + 30x_2 + d_1^- - d_1^+ = 300$（利润目标）

$\\quad 2x_1 + 3x_2 + d_2^- - d_2^+ = 24$（原材料约束）

$\\quad x_1 - 2x_2 + d_3^- - d_3^+ = 0$（产量比例约束）

$\\quad x_1, x_2 \\geq 0,\\; d_i^-, d_i^+ \\geq 0$

💡 目标规划通过优先级因子 $P_1 \\gg P_2 \\gg P_3$ 处理多目标冲突问题。

📖 答案：
可能不同。目标规划按优先级逐级求解——先满足 $P_1$ 目标，在不损害 $P_1$ 的前提下再满足 $P_2$，以此类推。

第1题中 $P_1$ 是利润目标，第2题中 $P_1$ 改为原材料约束，两个问题的优化顺序不同，得到的方案可能不同。

例如：若为保原材料不超用而降低产量，利润可能达不到 300 元。

💡 目标规划中优先级次序的改变会直接影响最优解，决策者需根据实际情况确定各目标的优先级。

📖 答案：

(1) 状态转移方程：$s_{k+1} = T_k(s_k, u_k)$，描述从第 $k$ 阶段的状态 $s_k$ 经过决策 $u_k$ 后，转移到下一阶段状态 $s_{k+1}$ 的规律。

(2) 贝尔曼最优化原理：最优策略的子策略也是最优的。即从最优策略中任取一段，该段子策略对于它所处子过程来说也是最优的。

(3) 通常采用逆序递推——从最后一个阶段开始向前递推。

💡 动态规划基本方程：$f_k(s_k) = \\text{opt}\\{v_k(s_k,u_k) + f_{k+1}(s_{k+1})\\}$。

📖 答案：
逆序递推：

阶段4（$D \\to E$）：

$f_4(D_1) = 4$，$f_4(D_2) = 3$

阶段3（$C \\to D$）：

$f_3(C_1) = \\min\\{3+f_4(D_1),\\; 4+f_4(D_2)\\} = \\min\\{3+4=7,\\; 4+3=7\\} = 7$（两条路长度相同）

$f_3(C_2) = \\min\\{1+4=5,\\; 2+3=5\\} = 5$

$f_3(C_3) = \\min\\{5+4=9,\\; 6+3=9\\} = 9$

阶段2（$B \\to C$）：

$f_2(B_1) = \\min\\{2+7=9,\\; 5+5=10\\} = 9$ → 选 $C_1$

$f_2(B_2) = \\min\\{4+7=11,\\; 3+5=8,\\; 5+9=14\\} = 8$ → 选 $C_2$

阶段1（$A \\to B$）：

$f_1(A) = \\min\\{3+9=12,\\; 4+8=12\\} = 12$

最短路径长度：12。有两条最优路径：

$A \\to B_1 \\to C_1 \\to D_1(或D_2) \\to E$

$A \\to B_2 \\to C_2 \\to D_1(或D_2) \\to E$

💡 逆序递推是动态规划的标准方法，从后往前计算各阶段最优值。

📖 答案：

将 3 个项目视为 3 个阶段，状态 $s_k$ 为分配到第 $k$ 阶段时的剩余资金。

阶段3（项目3）：$f_3(s_3) = g_3(x_3)$

$f_3(0)=0$，$f_3(1)=2.0$，$f_3(2)=3.5$，$f_3(3)=4.0$，$f_3(4)=4.5$，$f_3(5)=5.0$

阶段2（项目2）：$f_2(s_2) = \\max_{0 \\leq x_2 \\leq s_2}\\{g_2(x_2) + f_3(s_2-x_2)\\}$

$f_2(0)=0$，$f_2(1)=\\max\\{1.0+0=1.0,\\;0+2.0=2.0\\}=2.0$（$x_2=0$）

$f_2(2)=\\max\\{0+3.5=3.5,\\;1.0+2.0=3.0,\\;2.5+0=2.5\\}=3.5$（$x_2=0$）

$f_2(3)=\\max\\{0+4.0=4.0,\\;1.0+3.5=4.5,\\;2.5+2.0=4.5,\\;4.0+0=4.0\\}=4.5$（$x_2=1$ 或 $2$）

$f_2(4)=\\max\\{0+4.5=4.5,\\;1.0+4.0=5.0,\\;2.5+3.5=6.0,\\;4.0+2.0=6.0,\\;5.0+0=5.0\\}=6.0$（$x_2=2$ 或 $3$）

$f_2(5)=\\max\\{0+5.0=5.0,\\;1.0+4.5=5.5,\\;2.5+4.0=6.5,\\;4.0+3.5=7.5,\\;5.0+2.0=7.0,\\;5.5+0=5.5\\}=7.5$（$x_2=3$）

阶段1（项目1）：$f_1(5)=\\max_{0 \\leq x_1 \\leq 5}\\{g_1(x_1) + f_2(5-x_1)\\}$

$=\\max\\{0+7.5=7.5,\\;1.5+6.0=7.5,\\;3.0+4.5=7.5,\\;4.5+3.5=8.0,\\;5.5+2.0=7.5,\\;6.0+0=6.0\\}=8.0$（$x_1=3$）

最优方案：项目1投 3 万，项目2投 3 万（$s_2=2$ 时查 $f_2$ 最优决策 $x_2=2$ 或 $3$，结合 $s_2=2$ 选 $x_2=1$ 或 $2$），项目3投 1 万。

最优方案：项目1=3万，项目2=1万（或2万），项目3=1万，总收益 = 8.0 万元。

💡 资源分配问题是动态规划的经典应用，将多维问题分解为单维逐阶段处理。

📖 答案：

(1) 状态转移方程：

$f_k(j) = \\max\\{f_{k-1}(j),\\; f_{k-1}(j-w_k) + v_k\\}$，$j=0,1,\\ldots,10$

其中 $f_k(j)$ 表示考虑前 $k$ 件物品、容量为 $j$ 时的最大价值。

(2) 动态规划表（按物品逐个考虑）：

容量	0	1	2	3	4	5	6	7	8	9	10
$k=1$（$w_1=2,v_1=3$）	0	0	3	3	3	3	3	3	3	3	3
$k=2$（$w_2=3,v_2=4$）	0	0	3	4	4	7	7	7	7	7	7
$k=3$（$w_3=4,v_3=5$）	0	0	3	4	5	7	8	9	9	12	12
$k=4$（$w_4=5,v_4=7$）	0	0	3	4	5	7	8	10	11	12	14

最优解：总价值 = 14，方案：物品2+物品3+物品4（$3+4+5=12 \\leq 10$）或物品1+物品3+物品4（$2+4+5=11>10$ 不行）

回溯：$f_4(10)=14$，$f_4(10) \\neq f_3(10)$ 且 $f_4(10)=f_3(5)+7$ → 选物品4，剩余容量 5

$f_3(5)=7$ 且 $f_3(5)=f_2(5)$ → 不选物品3

$f_2(5)=7$ 且 $f_2(5)=f_1(2)+4$ → 选物品2，剩余容量 2

$f_1(2)=3$ 且 $f_1(2)=f_0(0)+3$ → 选物品1

最终方案：物品1、物品2、物品4，重量 $2+3+5=10$，价值 $3+4+7=14$。

💡 动态规划背包问题的时间复杂度 $O(nC)$，是伪多项式算法。

📖 答案：

(1) Kruskal算法（每次选权最小且不构成圈的边）：

排序：$CD=2 < BC=3 < EF=3 < AC=4 < DF=4 < AB=5 < DE=5 < BD=6 < BE=7 < CE=8$

— 选 $CD=2$（$C-D$）

— 选 $BC=3$（$B-C$，不构成圈）

— 选 $EF=3$（$E-F$，不构成圈）

— 选 $AC=4$（$A-C$，不构成圈）

— 选 $DF=4$（$D-F$，不构成圈）

已选 5 条边，6 个顶点连通，停止。

最小生成树：$\\{CD, BC, EF, AC, DF\\}$，总权 = $2+3+3+4+4 = 16$

(2) Prim算法（从 A 开始，每次选距离当前树最近的顶点）：

— $A$：最近 $C(4)$，加入 $C$

— $\\{A,C\\}$：最近 $B(3)$ 或 $D(2)$，选 $D(2)$ → 加入 $D$

— $\\{A,C,D\\}$：最近 $B(3)$（通过 $C$），加入 $B$

— $\\{A,B,C,D\\}$：最近 $F(4)$（通过 $D$），加入 $F$

— $\\{A,B,C,D,F\\}$：最近 $E(3)$（通过 $F$），加入 $E$

结果相同：总权 = $4+2+3+4+3 = 16$。

💡 Kruskal 与 Prim 算法结果相同（最小生成树唯一当边权均不同）。

📖 答案：

初始化：$d(v_1)=0$（永久标号 P），$d(v_2)=4$，$d(v_3)=2$，$d(v_4)=\\infty$，$d(v_5)=\\infty$

迭代1：最小临时标号 $d(v_3)=2$ → 永久标号 P

更新 $v_3$ 邻居：$d(v_4)=\\min\\{\\infty,\\; 2+3=5\\}=5$，$d(v_5)=\\min\\{\\infty,\\; 2+7=9\\}=9$

迭代2：最小临时标号 $d(v_2)=4$ → P

更新 $v_2$ 邻居：$d(v_3)=2$（已有 P），$d(v_4)=\\min\\{5,\\; 4+5=9\\}=5$，$d(v_5)=\\min\\{9,\\; 4+6=10\\}=9$

迭代3：最小临时标号 $d(v_4)=5$ → P

更新 $v_4$ 邻居：$d(v_5)=\\min\\{9,\\; 5+2=7\\}=7$

迭代4：$d(v_5)=7$ → P

结果：

$v_1\\to v_2$：最短路径 $v_1\\to v_3\\to v_2$，长度 = $2+1=3$（非直接 4）

$v_1\\to v_3$：直接 $v_1\\to v_3$，长度 = 2

$v_1\\to v_4$：$v_1\\to v_3\\to v_4$，长度 = 5

$v_1\\to v_5$：$v_1\\to v_3\\to v_4\\to v_5$，长度 = 7

💡 Dijkstra 算法每次确定一个距离最小的顶点，不能用于含负权边的图。

📖 答案：

Floyd 算法通过依次以每个顶点为中间点来更新距离矩阵。

初始距离矩阵 $D^{(0)}$：

$D^{(0)} = \\begin{pmatrix} 0 & 4 & 2 & \\infty & \\infty \\\\ 4 & 0 & 1 & 5 & 6 \\\\ 2 & 1 & 0 & 3 & 7 \\\\ \\infty & 5 & 3 & 0 & 2 \\\\ \\infty & 6 & 7 & 2 & 0 \\end{pmatrix}$

$D^{(1)}$（以 $v_1$ 为中间点）：无变化

$D^{(2)}$（以 $v_2$ 为中间点）：$d_{13}=\\min(2, 4+1=5)=2$，$d_{14}=\\min(\\infty, 4+5=9)=9$（暂不变），$d_{15}=\\min(\\infty, 4+6=10)=10$

$D^{(3)}$（以 $v_3$ 为中间点）：$d_{12}=\\min(4, 2+1=3)=3$ ✓，$d_{14}=\\min(9, 2+3=5)=5$ ✓，$d_{15}=\\min(10, 2+7=9)=9$，$d_{24}=\\min(5, 1+3=4)=4$

继续迭代直到 $D^{(5)}$。

最终得到任意两点间最短距离矩阵。

💡 Floyd 算法一次求出所有节点对的最短路径，时间复杂度 $O(n^3)$。

📖 答案：

(1) 初始流：各弧流量为 0。

增广路1：$s\\to a\\to t$，可增量为 $\\min\\{10,6\\}=6$

增广后：$s\\to a(6/10)$，$a\\to t(6/6)$，流量 = 6

增广路2：$s\\to b\\to t$，可增量 $\\min\\{8,10\\}=8$

增广后：$s\\to b(8/8)$，$b\\to t(8/10)$，流量 = 14

增广路3：$s\\to a(4/10)\\to b(4/4)\\to t(4/10)$

$s\\to a$ 剩余容量 4，$a\\to b$ 容量 4（前向），$b\\to t$ 剩余容量 2

可增量 = $\\min\\{4,4,2\\}=2$

增广后：$s\\to a(8/10)$，$a\\to b(2/4)$，$b\\to t(10/10)$，流量 = 16

无法再找到增广路。

最大流 = 16

(2) 最大流-最小割定理：任何网络中的最大流量等于最小割集的容量。

取割集 $(\\{s,a,b\\},\\{t\\})$，割容量 = $c_{at}+c_{bt} = 6+10=16$

最大流 16 = 最小割容量 16 ✓

💡 Ford-Fulkerson 算法核心是反复寻找增广路，直到不存在增广路为止。

📖 答案：

(1) 持续时间 $t = EF - ES = 9 - 5 = 4$

(2) $LF = LS + t = 7 + 4 = 11$

(3) 总时差 $= LS - ES = 7 - 5 = 2$（或 $LF - EF = 11 - 9 = 2$）

总时差 > 0 → 不在关键路径上（关键路径上的工序总时差为 0）

💡 总时差 = $LS - ES = LF - EF$，时差为 0 的工序组成关键路径。

📖 答案：

(1) 网络图可表示为：$1\\xrightarrow{A}2\\xrightarrow{B}3\\xrightarrow{D}4\\xrightarrow{F}5$，且 $2\\xrightarrow{C}6(虚节点或平行)$，实际需要虚工序处理。

(2) 时间参数计算：

工序	ES	EF	LS	LF	时差
A	0	3	0	3	0
B	3	8	3	8	0
C	3	7	4	8	1
D	8	10	8	10	0
E	7	13	8	14	1
F	13	16	14	17	1

注意：$F$ 的紧前为 $D$ 和 $E$，需两者均完成后 $F$ 才能开始，故 $ES_F = \\max(EF_D, EF_E) = \\max(10, 13) = 13$。

更正：$F$ 的 ES 应为 13 而非上述表格中的值。

(3) 实际上关键路径由时差为 0 的工序组成。

重新计算正确的时间参数后，关键路径为 $A \\to B \\to D$（或包含其他工序）。总工期 = 3+5+2+3=13 天。

💡 网络图中引入虚工序可以正确表达工序间的逻辑关系。

📖 答案：

(1) 乐观准则：各方案最大收益：$A_1=50$，$A_2=40$，$A_3=60$ → 选 $\\max=\\mathbf{60}$ → $A_3$

(2) 悲观准则：各方案最小收益：$A_1=-10$，$A_2=10$，$A_3=-5$ → 选 $\\max=\\mathbf{10}$ → $A_2$

(3) 等可能准则：各方案平均收益：

$A_1=(50+30-10)/3 = 23.33$

$A_2=(20+40+10)/3 = 23.33$

$A_3=(-5+15+60)/3 = 23.33$

三者相等 → 三个方案无差异。

(4) 最小遗憾准则：先构造遗憾矩阵。

各状态下最大收益：$S_1=50$，$S_2=40$，$S_3=60$

遗憾值 = 最大收益 - 实际收益：

	$S_1$	$S_2$	$S_3$
$A_1$	0	10	70
$A_2$	30	0	50
$A_3$	55	25	0

各方案最大遗憾：$A_1=70$，$A_2=50$，$A_3=55$ → 选最小 = $\mathbf{50}$ → $A_2$

💡 不同准则反映决策者的不同风险态度：乐观者选 $A_3$，保守者选 $A_2$。

📖 答案：

(1) 各方案期望收益：

$E(A_1) = 0.3\\times50 + 0.5\\times30 + 0.2\\times(-10) = 15+15-2 = 28$ 万元

$E(A_2) = 0.3\\times20 + 0.5\\times40 + 0.2\\times10 = 6+20+2 = 28$ 万元

$E(A_3) = 0.3\\times(-5) + 0.5\\times15 + 0.2\\times60 = -1.5+7.5+12 = 18$ 万元

最大期望收益 = 28 万元，$A_1$ 和 $A_2$ 并列最优。

(2) 全情报价值 EVPI：

完全信息下的期望收益 = $0.3\\times50 + 0.5\\times40 + 0.2\\times60 = 15+20+12 = 47$ 万元

$\\text{EVPI} = 47 - 28 = 19$ 万元

意义：公司最多愿意花 19 万元来获取完全准确的市场信息。

(3) 决策树：

— 决策节点（方框）引出 3 个方案分支

— 每个方案分支连接一个状态节点（圆圈）

— 状态节点引出 3 条概率分支（$S_1:0.3$，$S_2:0.5$，$S_3:0.2$）

— 末端的收益值分别为对应收益

💡 EVPI 是决策者为获取完美信息愿支付的最高价格。

📖 答案：

(1) 期望效用计算：

方案甲：$U(20) = 1 - e^{-20/50} = 1 - e^{-0.4} \\approx 1 - 0.6703 = 0.3297$

方案乙：$E[U] = 0.5\\times U(50) + 0.5\\times U(0)$

$U(50) = 1 - e^{-1} \\approx 1 - 0.3679 = 0.6321$

$U(0) = 1 - e^0 = 1 - 1 = 0$

$E[U] = 0.5\\times0.6321 + 0.5\\times0 = 0.3161$

方案甲（0.3297）> 方案乙（0.3161）→ 选方案甲

(2) 方案乙的期望收益 $= 0.5\\times50+0.5\\times0 = 25$ 万 > 20 万，但决策者选方案甲 → 风险厌恶。

效用函数 $U(x)=1-e^{-x/50}$ 是凹函数 → 风险厌恶。

(3) 风险溢价：使 $U(CE) = E[U]$ 的确定等值 $CE$。

$1 - e^{-CE/50} = 0.3161$

$e^{-CE/50} = 0.6839$

$-CE/50 = \\ln(0.6839) = -0.38$

$CE = 19$ 万元

风险溢价 $= 25 - 19 = 6$ 万元。

💡 风险溢价表示决策者愿意放弃的期望收益以避免风险。

📖 答案：

(1) 行选手（最大化者）：每行取最小值，再从这些最小值中取最大（max min）。

第1行最小 = $\\min\\{6,2\\}=2$，第2行最小 = $\\min\\{3,5\\}=3$

$\\max\\{2,3\\}=3$（行选手的保守收益）

列选手（最小化者）：每列取最大值，再从这些最大值中取最小（min max）。

第1列最大 = $\\max\\{6,3\\}=6$，第2列最大 = $\\max\\{2,5\\}=5$

$\\min\\{6,5\\}=5$（列选手的保守损失）

因为 $3 \\neq 5$，即 $\\max\\min \\neq \\min\\max$，所以不存在纯策略鞍点。

(2) 不存在纯策略均衡 → 需要求解混合策略。

💡 当 max min = min max 时存在纯策略鞍点，对策值即为该共同值。