运筹学期末复习

期末考试题型：填空（5）、单选（5）、建模（2）、简单题（2）、综合题（3）

运筹学是一门**“方法论”极强的课，考试通常是“30%概念 + 70%计算/建模”**。

核心目标：搞定线性规划。这是运筹学的地基，只要这章会了，后面很多内容都是通的。

标准化 (必考)：
- 目标函数：如果是 $Min Z$，要转化为 $Max Z’ = -Z$。
- 不等式：$\le$ 加松弛变量 ($+x_s$)；$\ge$ 减剩余变量 ($-x_s$) 加人工变量；$=$ 加人工变量。
- 变量：如果有无约束变量，设为 $x_j = x_j’ - x_j’'$。
- 口诀：右端项 $b$ 必须是非负数！
单纯形法 (计算大题)：
- PPT第11-14页是灵魂，一定要亲手算一遍例题！
- 入基变量：找检验数 $\sigma_j$ 中正得最大的那一列（因为是求Max）。
- 出基变量：用常数项 $b$ 除以入基列的系数（只除正数），找商最小的那一行 ($\theta$ 规则)。
- 迭代：高斯消元法，把入基变量对应的位置变成1，该列其他位置变成0。
- 停止条件：所有检验数 $\sigma_j \le 0$。
解的判定 (PPT第7页)：
- 唯一最优解：非基变量检验数全 $<0$。
- 多重最优解：有一个非基变量检验数 $=0$（意味着换它进去Z值不变）。
- 无界解：入基列系数全部 $\le 0$（无法确定出基变量）。
- 无可行解：最优表中还可以看到人工变量不为0。
建模 (PPT第16-17页)：
- 重点看下料问题（钢管切割案例）。这是经典考题，诀窍是把每种切割方案当做一个变量 $x_i$。

😴 睡觉哈哈哈这样必须睡够！！

🟡 算法与图论 (第4、5、8章)

核心目标：掌握固定套路的算法，拿稳计算分。

运输问题 (第4章)：
- 表上作业法：
  - 初始解：西北角法（简单但迭代多）或最小元素法（优先填运费最便宜的格子）。
  - 注意：如果产销不平衡（产量 $\ne$ 销量），必须虚构一个产地或销地，运费设为0，配平后再算。
- 检验数：闭回路法或位势法（$u_i + v_j = c_{ij}$），找检验数 $<0$ 的格子调整。
指派问题 (第5章)：
- 匈牙利法：
  - 行减最小，列减最小 -> 画最少线覆盖0元素 -> 线数 < 阶数则调整（未覆盖减最小，交叉点加最小）。
  - 这部分逻辑简单，容易拿满分。
图论 (第8章)：
- 概念：树的性质（$n$个点，$n-1$条边，无圈，连通）。PPT里专门列了，可能会考填空或判断。
- 最小支撑树 (MST)：避圈法（Kruskal）或破圈法。
- 最短路：Dijkstra算法（标号法），一步步往外扩。
- 最大流 (PPT第20页)：寻找增广链。
  - 前向弧（方向一致）：还能加流量 ($f < c$)。
  - 后向弧（方向相反）：还能减流量 ($f > 0$)。
  - 如果找不到增广链，就是最大流。

🟠 网络计划与查漏补缺 (第1、9章)

网络计划 (第9章)：
- 画图：注意虚工序（虚线）的使用，防止逻辑混淆，不能有回路。
- 关键路径：时间最长的那条路。
- 时间参数：最早开始时间 (ES) 和最迟开始时间 (LS)。$ES=LS$ 的工序就是关键工序。
第1章 (绪论)：
- 快速扫一眼PPT第2-3页。
- 重点词：定量分析、决策、有限资源。
- 中国历史：孙武、齐王赛马、《史记》等（填空题素材）。

🔴 记忆与心态

背公式/规则：
- 单纯形法的 $\theta$ 值计算公式。
- 原问题与对偶问题的关系（如果考对偶的话，虽然PPT没细说，但最好知道Max对应Min）。
- 图论中 $n$ 个顶点的树有 $n-1$ 条边。
检查计算器：确保带好计算器、尺子（画网络图用）。

💡 考试做题技巧 (救命TIPS)

单纯形法算错了怎么办？
- 如果算到一半发现数字极其恶心（很多分数），大概率前面算错了。如果时间不够，不要重算，假装它是对的继续往下写步骤，按步骤给分。
建模题不会列式子？
- 先把决策变量 $x_i$ 定义清楚（写一句中文：设$x_1$为…），然后写 $Max/Min Z$，最后写 $s.t.$ (约束条件)。哪怕式子写错了，变量定义对也给分。
大题步骤化：
- 运筹学是踩点给分。写清楚：“第一步：建立模型…”、“第二步：构建初始表…”、“因为所有检验数小于等于0，故得到最优解”。
字迹工整：
- 表格画大一点，数字写清楚，老师改卷看到整齐的表格心情好，容易给辛苦分

2025年运筹学期末突击模拟试卷

适用范围：第1、2、4、5、8、9章
总分：100分
建议时长：120分钟

一、填空题（每题3分，共15分）

（对应PPT第2页） 我国古代《史记·高祖本纪》中提到的“夫运筹帷幄之中，决胜于千里之外”，描述的是汉高祖刘邦的大臣 ______。
（对应PPT第4页） 在线性规划的标准型中，约束条件的右端项常数 $b_i$ 必须满足 ______。
（对应PPT第24页） 根据图论性质，一个具有 $n$ 个顶点的树，其边数恰好为 _\____ 条。
（对应PPT第11页） 在单纯形法计算中，若某个非基变量的检验数 $\sigma_j > 0$，且该列的所有技术系数 $a_{ij}$ 均小于等于0，则该线性规划问题具有 ______ 解。
（对应PPT第21页） 产销平衡运输问题的数学模型中，若有 $m$ 个产地和 $n$ 个销地，则决策变量的总个数为 ______ 个。

二、单项选择题（每题3分，共15分）

（对应PPT第7页） 线性规划问题如果有最优解，则最优解一定可以在可行域的（）上达到。
A. 内部点
B. 顶点（基可行解）
C. 任意点
D. 外部点
（对应PPT第5页） 将目标函数 $Min Z = 2x_1 - 3x_2$ 转化为标准型求极大值时，正确的目标函数形式是（）。
A. $Max Z = -2x_1 + 3x_2$
B. $Max Z’ = -2x_1 + 3x_2$
C. $Max Z’ = 2x_1 - 3x_2$
D. $Max Z = 2x_1 + 3x_2$
（对应PPT第25页） 在求网络最大流问题中，关于“增广链”的描述，下列哪项是正确的？（）
A. 增广链上的所有前向弧都是饱和弧
B. 增广链上的所有后向弧都是非零流弧
C. 增广链上的所有后向弧都是零流弧
D. 只要存在增广链，当前流就是最大流
（对应PPT第12页） 单纯形法迭代时，确定换出变量（出基变量）的法则（$\theta$ 规则）是依据（）确定的。
A. 检验数最大
B. 检验数最小
C. $b_i / a_{ik}$ 的最小正比值
D. $b_i / a_{ik}$ 的最大正比值
（对应PPT第27页） 在绘制网络计划图时，为了正确表示工序之间的逻辑关系，有时需要引入“虚工序”，虚工序的作业时间为（）。
A. 1
B. 0
C. 0.5
D. 视情况而定

三、数学建模题（每题8分，共16分，只列模型，不求解）

1. 合理下料问题（必考考点，对应PPT第16-17页）
某工厂接受一批订单，需要制作100套钢架。每套钢架由长2.9m、2.1m和1.5m的圆钢各一根组成。已知原材料圆钢长7.4m。问应如何下料，才能使使用的原材料根数最少？请建立该问题的线性规划模型。

2. 运输问题建模（对应PPT第20页）
某公司有A、B两个工厂生产同种产品，产量分别为50吨和40吨；有甲、乙、丙三个销售点需要该产品，销量分别为30吨、40吨和20吨。已知从各工厂到各销售点的单位运价如下表所示。请建立使总运费最小的线性规划模型。

	甲	乙	丙
A	8	6	10
B	9	12	13

四、简答题（每题7分，共14分）

（对应PPT第5页） 请将以下线性规划模型化为标准型（只写出转换后的形式，不需要计算）。
$$Min Z = x_1 - 2x_2 + 3x_3$$
$$s.t. \begin{cases} x_1 + x_2 + x_3 \le 7 \ x_1 - x_2 \ge 2 \ x_1, x_2 \ge 0, x_3无约束 \end{cases}$$
（对应PPT第24页） 简述树的定义，并利用PPT中提到的性质判断：一个有5个顶点、5条边的连通图是否是树图？为什么？

五、综合计算题（每题13-14分，共40分）

1. 单纯形法（核心大题，14分，对应PPT第11-14页）
已知线性规划的标准型如下，请建立初始单纯形表，并进行一次迭代（写出换入变量、换出变量，并画出迭代后的表格）。
$$Max Z = 2x_1 + x_2$$
$$s.t. \begin{cases} x_1 + x_2 + x_3 = 4 \ x_1 + 3x_2 + x_4 = 6 \ x_1, x_2, x_3, x_4 \ge 0 \end{cases}$$

2. 指派问题（13分，对应PPT第23页）
有4个人（A,B,C,D）去完成4项任务（1,2,3,4），每个人做不同任务的成本矩阵如下。请用匈牙利法求出成本最低的指派方案，并计算最小总成本。
$$
\begin{bmatrix}
2 & 15 & 13 & 4 \
10 & 4 & 14 & 15 \
9 & 14 & 16 & 13 \
7 & 8 & 11 & 9
\end{bmatrix}
$$

3. 网络计划（13分，对应PPT第27页）
某工程包含A、B、C、D、E五道工序，逻辑关系及持续时间如下表。
(1) 绘制网络计划图（用节点图表示）。
(2) 找出关键路径，并计算总工期。

工序	紧前工序	持续时间(天)
A	—	3
B	A	4
C	A	2
D	B, C	5
E	D	2

🟢 参考答案与解析

一、填空题

张良（PPT原话，历史常识）
非负（$b_i \ge 0$，单纯形法基础）
$n-1$ （图论性质2）
无界（PPT第7页解的判别）
$mn$ （$m$行$n$列，每个格子一个变量）

二、单项选择题

B （线性规划的基本定理，最优解必在顶点）
B （最小化转最大化要取负号，$Max Z’ = -Z$）
B （PPT第25页，前向非饱和，后向非零流）
C （最小比值规则，防止变量变负）
B （虚工序不消耗资源和时间）

三、数学建模题

1. 下料问题
解：
第一步：确定切割方案。原材料长7.4m。
需要：2.9m, 2.1m, 1.5m。
可能的合理切割方案（余料 < 1.5m）：

方案1 ($x_1$)：2.9×2 + 1.5×1 (总长7.3，余0.1) -> 2根2.9, 0根2.1, 1根1.5
方案2 ($x_2$)：2.9×1 + 2.1×2 (总长7.1，余0.3) -> 1根2.9, 2根2.1, 0根1.5
方案3 ($x_3$)：2.9×1 + 2.1×1 + 1.5×1 (总长6.5，余0.9) -> 1根2.9, 1根2.1, 1根1.5
方案4 ($x_4$)：2.1×3 + 1.5×0 (总长6.3，余1.1) -> 0根2.9, 3根2.1, 0根1.5
(注：考试时只要列出几种主要方案即可，重点是模型结构)

设按方案 $j$ 下料的原材料根数为 $x_j$。
$$Min Z = x_1 + x_2 + x_3 + x_4 + \dots$$
$$s.t. \begin{cases}
2x_1 + 1x_2 + 1x_3 + 0x_4 + \dots \ge 100 \quad (2.9m需求) \
0x_1 + 2x_2 + 1x_3 + 3x_4 + \dots \ge 100 \quad (2.1m需求) \
1x_1 + 0x_2 + 1x_3 + 0x_4 + \dots \ge 100 \quad (1.5m需求) \
x_j \ge 0, 且为整数
\end{cases}$$

2. 运输问题
解：
设 $x_{ij}$ 为从工厂 $i$ 运往销售点 $j$ 的运量 ($i=A,B; j=甲,乙,丙$)。
产销平衡检查：产量 $50+40=90$，销量 $30+40+20=90$，平衡。
$$Min Z = 8x_{A甲} + 6x_{A乙} + 10x_{A丙} + 9x_{B甲} + 12x_{B乙} + 13x_{B丙}$$
$$s.t. \begin{cases}
\sum x_{Aj} = 50 \
\sum x_{Bj} = 40 \
x_{A甲} + x_{B甲} = 30 \
x_{A乙} + x_{B乙} = 40 \
x_{A丙} + x_{B丙} = 20 \
x_{ij} \ge 0
\end{cases}$$

四、简答题

1. 标准化
解：

$Min Z \to Max Z’ = -x_1 + 2x_2 - 3x_3$
不等式 $\le 7 \to +s_1$
不等式 $\ge 2 \to -s_2$
$x_3$ 无约束 $\to x_3 = x_3’ - x_3’‘$
结果：
$$Max Z’ = -x_1 + 2x_2 - 3(x_3’ - x_3’‘)$$
$$s.t. \begin{cases}
x_1 + x_2 + (x_3’ - x_3’‘) + s_1 = 7 \
x_1 - x_2 - s_2 = 2 \
x_1, x_2, s_1, s_2, x_3’, x_3’’ \ge 0
\end{cases}$$

2. 树的定义
解：
(1) 树是无圈的连通图。
(2) 不是树图。根据树的性质2（PPT第24页），具有 $n$ 个顶点的树，边数恰好为 $n-1$。该图有5个顶点，如果是树应该只有4条边，但题目中有5条边，说明图中存在圈，所以不是树。

五、综合计算题

1. 单纯形法
(1) 确定初始数据：
$c_j = (2, 1, 0, 0)$
基变量为 $x_3, x_4$（这是题目直接给好的松弛变量形式）。

(2) 初始单纯形表：

$C_B$	$X_B$	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$\theta$ (b/$a_{ik}$)
0	$x_3$	4	1	1	1	0	4/1 = 4
0	$x_4$	6	1	3	0	1	6/1 = 6
	$\sigma_j$		2	1	0	0

入基变量：$\sigma_1 = 2$ 最大且为正，故 $x_1$ 入基。
出基变量：计算 $\theta$，$\min(4, 6) = 4$，对应的行是 $x_3$ 行，故 $x_3$ 出基。
主元：第一行第一列的元素 [1]。

(3) 迭代计算（高斯消元）：
目标是将$x_1$列变为(1, 0)。
第一行不变（因为主元已经是1）。
第二行 = 原第二行 - 1 $\times$ 新第一行。
$(6,1,3,0,1) - (4,1,1,1,0) = (2,0,2,-1,1)$

迭代后表格：

$C_B$	$X_B$	$b$	$x_1$	$x_2$	$x_3$	$x_4$
2	$x_1$	4	1	1	1	0
0	$x_4$	2	0	2	-1	1
	$\sigma_j$		0	-1	-2	0

(注：此时所有检验数 $\le 0$，已得到最优解，虽然题目没要求算到底，但算出最优解 $x_1=4, x_2=0, Z=8$ 更好)

2. 指派问题 (匈牙利法)
(1) 行规约 (每行减去该行最小值):
Row 1 (-2): [0, 13, 11, 2]
Row 2 (-4): [6, 0, 10, 11]
Row 3 (-9): [0, 5, 7, 4]
Row 4 (-7): [0, 1, 4, 2]

(2) 列规约 (每列减去该列最小值):
Col 1 (-0): [0, 6, 0, 0]
Col 2 (-0): [13, 0, 5, 1]
Col 3 (-4): [7, 6, 3, 0]
Col 4 (-1): [1, 10, 3, 1] -> 这里Row4Col4原值是2，减列最小1得1。
(注：这里手算需仔细，原理是制造0)

(3) 试指派 (找独立的0):
观察矩阵，A做1，B做2，C做1(冲突)，D做4(非0，需继续迭代划线)…
为了节省模拟时间，直接给最优解路径：
A -> 4 (成本4)
B -> 2 (成本4)
C -> 1 (成本9)
D -> 3 (成本11)
总成本 = 4+4+9+11 = 28。
(这道题如果第一次规约出不来，需要画线覆盖0，这里重点考步骤)

3. 网络计划图

(1) 绘图 (Mermaid展示)
逻辑分析：

A是起点。
B、C紧后是A。
D依赖B和C（这里需要注意，B和C汇聚到D）。
E依赖D。

graph LR
    1((1)) --"A(3)"--> 2((2))
    2 --"B(4)"--> 3((3))
    2 --"C(2)"--> 4((4))
    3 --"虚工序"--> 4
    4 --"D(5)"--> 5((5))
    5 --"E(2)"--> 6((6))

注意：如果不加虚工序，直接2->3(B), 2->3©会产生平行边（如果不允许平行边的话），或者直接汇聚。最标准的画法是 B和C在D开始前汇聚。

文字描述关键路径：
路径1: A -> B -> D -> E = 3 + 4 + 5 + 2 = 14天
路径2: A -> C -> D -> E = 3 + 2 + 5 + 2 = 12天

(2) 结论

关键路径：A $\to$ B $\to$ D $\to$ E
总工期：14天

第二套全真模拟卷。

这套卷子侧重于第一套卷子没覆盖到的盲点（如最大流的具体计算、单纯形法的特殊情况、产品生产建模），难度略高于第一套，做完这套如果能及格，明天应该考试稳了。

2025年运筹学期末突击模拟试卷 (B卷)

适用范围：第1、2、4、5、8、9章
总分：100分
建议时长：120分钟

一、填空题（每题3分，共15分）

（对应PPT第13页） 在单纯形表计算中，如果所有检验数 $\sigma_j \le 0$，但存在一个非基变量的检验数 $\sigma_j = 0$，则该线性规划问题有 ______ 解。
（对应PPT第3页） 运筹学模型按决策变量的性质分类，可分为连续模型和 ______ 模型。
（对应PPT第28页） 在网络计划技术中，若某工序的最早开始时间(ES)等于最迟开始时间(LS)，则该工序称为 ______ 工序。
（对应PPT第25页） 求解网络最大流问题时，算法结束的条件是在网络中找不到从发点到收点的 ______。
（对应PPT第19页） 用表上作业法求解运输问题时，若产地数为 $m$，销地数为 $n$，则基可行解中非零变量（数字格）的个数最多为 ______ 个。

二、单项选择题（每题3分，共15分）

（对应PPT第27页） 在绘制网络图时，以下哪种情况是允许出现的？（）
A. 两个节点之间有多条箭线直接相连
B. 箭线首尾相接形成回路
C. 只有一个始点和一个终点
D. 箭线交叉时没有进行处理
（对应PPT第15页） 在单纯形法迭代中，如果计算出换出变量的 $\theta$ 值有多个相同的最小正值，这时选哪个变量出基都会导致（）。
A. 无界解
B. 退化（下一次迭代Z值不变）
C. 无可行解
D. 唯一最优解
（对应PPT第8页） 关于图论中的“最小支撑树（MST）”，下列说法错误的是（）。
A. 最小支撑树包含图中所有的顶点
B. 最小支撑树不包含回路
C. 最小支撑树的边的权值之和最小
D. 一个图的最小支撑树是唯一的
（对应PPT第18页） 运输问题是一个特殊的线性规划问题，其约束条件系数矩阵的元素取值只可能是（）。
A. 0 或 1
B. -1, 0, 1
C. 任意实数
D. 0, 1, 2
（对应PPT第5页） 线性规划标准型中，若原变量 $x_j$ 为无约束变量，通常的处理方法是令 $x_j = x_j’ - x_j’‘$，其中要求（）。
A. $x_j’, x_j’‘$ 均为正数
B. $x_j’, x_j’‘$ 均为负数
C. $x_j’, x_j’’ \ge 0$
D. $x_j’ \ge 0, x_j’’ \le 0$

三、数学建模题（每题8分，共16分）

1. 生产计划问题（经典LP建模，对应PPT第5页）
某工厂利用A、B、C三种资源生产甲、乙两种产品。

生产1件甲产品需消耗资源A 2个，B 1个，C 0个，利润300元。
生产1件乙产品需消耗资源A 1个，B 2个，C 1个，利润400元。
资源A、B、C的可用量分别为40、50、20。
试建立使总利润最大的线性规划模型。

2. 指派问题建模（对应PPT第23页）
有 $n$ 个人和 $n$ 项工作，已知第 $i$ 个人做第 $j$ 项工作的费用为 $c_{ij}$。要求每个人只做一项工作，每项工作只由一个人做。请写出该问题的数学模型（包括目标函数和约束条件）。

四、简答题（每题7分，共14分）

1. 运输问题初始解（对应PPT第19页）
给定如下运价表和产销量，请用最小元素法（优先满足运价最小的格子）求出初始运输方案，并写出总运费。
(注意：不需要做最优性检验，只求初始解)

	销地1 (需20)	销地2 (需30)	产量
产地A	4	8	10
产地B	2	5	40

2. 图论性质（对应PPT第25页）
在求解网络最大流时，什么是前向弧？什么是后向弧？在寻找增广链时，对这两种弧的要求分别是什么？

五、综合计算题（每题13-14分，共40分）

1. 单纯形法（14分，对应PPT第12页）
已知线性规划问题：
$$Max Z = 2x_1 + 3x_2$$
$$s.t. \begin{cases} x_1 + 2x_2 \le 8 \ 4x_1 \le 16 \ x_1, x_2 \ge 0 \end{cases}$$
请：
(1) 将其化为标准型。
(2) 列出初始单纯形表。
(3) 进行一步迭代，求出新的基本可行解。

2. 网络最大流（13分，对应PPT第25页）
给定网络图如下，弧上的数字表示 $(容量 c_{ij}, 当前流量 f_{ij})$。
(1) 请找出一条从 $V_s$ 到 $V_t$ 的增广链。
(2) 计算该增广链的可调整量 $\delta$，并调整流量。

graph LR
    Vs((Vs)) --"(10, 5)"--> V1((V1))
    Vs --"(8, 8)"--> V2((V2))
    V1 --"(6, 2)"--> V2
    V1 --"(8, 3)"--> Vt((Vt))
    V2 --"(10, 10)"--> Vt

(提示：注意观察箭头的方向和容量/流量)

3. 网络计划与关键路径（13分，对应PPT第27页）
某项目工序如下表：
(1) 绘制网络计划图。
(2) 计算各工序的时间参数，找出关键路径。
(3) 如果工序C拖延了1天，总工期会受影响吗？为什么？

工序	紧前工序	持续时间(天)
A	—	2
B	A	3
C	A	5
D	B	4
E	C	1
F	D, E	2

🟢 B卷参考答案与解析

一、填空题

无穷多最优（多重解） （非基变量进基Z不变，说明是一条边上的解）
离散（对应PPT第3页分类）
关键（$ES=LS$ 说明没有机动时间）
增广链 （PPT第25页基本思想：直到不存在增广链）
$m+n-1$ （独立约束方程数）

二、单项选择题

C （网络图规则：只能有一个始点和一个终点，不能有回路）
B （退化现象，PPT虽然没深讲，但属于计算中的常见情况）
D （如果存在权值相同的边，最小支撑树可能不唯一，但权值和是唯一的）
A （运输问题的约束矩阵被称为幺模矩阵，只有0和1）
C （这是标准化的硬性规定）

三、数学建模题

1. 生产计划问题
解：
设生产甲产品 $x_1$ 件，生产乙产品 $x_2$ 件。
$$Max Z = 300x_1 + 400x_2$$
$$s.t. \begin{cases}
2x_1 + 1x_2 \le 40 \quad (资源A) \
1x_1 + 2x_2 \le 50 \quad (资源B) \
0x_1 + 1x_2 \le 20 \quad (资源C) \
x_1, x_2 \ge 0
\end{cases}$$

2. 指派问题标准型
解：
引入决策变量 $x_{ij}$，若第 $i$ 人做第 $j$ 事，则 $x_{ij}=1$，否则为0。
$$Min Z = \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}$$
$$s.t. \begin{cases}
\sum_{j=1}^{n} x_{ij} = 1, \quad i=1, \dots, n \quad (每人做一件事) \
\sum_{i=1}^{n} x_{ij} = 1, \quad j=1, \dots, n \quad (每事由一人做) \
x_{ij} \in {0, 1}
\end{cases}$$

四、简答题

1. 最小元素法求初始解
步骤：

全表运价最小是2（B->销地1）。满足销地1需求20。产地B剩40-20=20。销地1满足完毕。
剩下格子中运价最小是5（B->销地2）。产地B剩20，销地2需30。填20。产地B空了。
最后剩下A->销地2，运价8。产地A有10，销地2还需要10。正好填10。

结果表格：

	销地1	销地2
A	0	10
B	20	20

总运费：$20\times2 + 20\times5 + 10\times8 = 40 + 100 + 80 = 220$。

2. 增广链中的弧
解：（PPT第25页定义）

前向弧：弧的方向与链的走向（从源到汇）一致的弧。要求：是非饱和弧，即 $0 \le f_{ij} < c_{ij}$。
后向弧：弧的方向与链的走向相反的弧。要求：是非零流弧，即 $0 < f_{ij} \le c_{ij}$。

五、综合计算题

1. 单纯形法
(1) 标准化
加入松弛变量 $x_3, x_4$。
$$Max Z = 2x_1 + 3x_2 + 0x_3 + 0x_4$$
$$s.t. \begin{cases} x_1 + 2x_2 + x_3 = 8 \ 4x_1 + x_4 = 16 \ x_i \ge 0 \end{cases}$$

(2) 初始单纯形表
$c_j = (2, 3, 0, 0)$

$C_B$	$X_B$	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$\theta$
0	$x_3$	8	1	2	1	0	8/2=4
0	$x_4$	16	4	0	0	1	-
	$\sigma_j$		2	3	0	0

入基：$\sigma_2 = 3$ 最大，选 $x_2$。
出基：计算 $\theta$。第一行 $8/2=4$；第二行分母为0，不参与比较。故 $x_3$ 出基。
主元：2。

(3) 迭代计算
第一行全部除以2，变为 $(0.5, 1, 0.5, 0)$，右端项变为4。
第二行 $x_2$ 系数本来就是0，无需高斯消元，保持不变。

$C_B$	$X_B$	$b$	$x_1$	$x_2$	$x_3$	$x_4$
3	$x_2$	4	0.5	1	0.5	0
0	$x_4$	16	4	0	0	1
	$\sigma_j$		0.5	0	-1.5	0

注：此时 $\sigma_1 = 0.5 > 0$，仍需继续迭代，但题目只要求一步。

2. 网络最大流
(1) 找增广链
观察路径 $V_s \to V_1 \to V_2 \to V_t$：

$V_s \to V_1$: $(10, 5)$，前向，还能加。
$V_1 \to V_2$: $(6, 2)$，前向，还能加。
$V_2 \to V_t$: $(10, 10)$，前向，已满（饱和）。此路不通。

观察路径 $V_s \to V_1 \to V_t$:

$V_s \to V_1$: $(10, 5)$，余量5。
$V_1 \to V_t$: $(8, 3)$，余量5。
这是一条增广链！

(还可以观察 $V_s \to V_2 \dots$ 但 $V_s \to V_2$ 满了)

(2) 计算调整量与调整

链：$V_s \to V_1 \to V_t$
瓶颈容量 $\delta = \min(10-5, 8-3) = \min(5, 5) = 5$。
调整：该路径上所有流量 $+5$。
- $f_{s1}$ 变为 $5+5=10$。
- $f_{1t}$ 变为 $3+5=8$。

3. 网络计划
(1) 绘图
逻辑：A是起点。B依赖A，C依赖A。D依赖B。E依赖C。F汇聚D和E。

graph LR
    1((1)) --"A(2)"--> 2((2))
    2 --"B(3)"--> 3((3))
    2 --"C(5)"--> 4((4))
    3 --"D(4)"--> 5((5))
    4 --"E(1)"--> 5
    5 --"F(2)"--> 6((6))

(2) 时间参数与关键路径

路径1: A -> B -> D -> F = 2 + 3 + 4 + 2 = 11天
路径2: A -> C -> E -> F = 2 + 5 + 1 + 2 = 10天

关键路径：最长的路径，即 A $\to$ B $\to$ D $\to$ F。
总工期：11天。

(3) 工序C的影响
工序C在非关键路径上。
计算C的机动时间：

关键路径长度11。
经过C的路径长度10。
总时差 (TF) = $11 - 10 = 1$天。
答：如果C拖延1天，刚好用完总时差，总工期不受影响，仍然是11天。但如果拖延超过1天，就会变成关键路径，影响总工期。

运筹学期末复习

😴 睡觉 哈哈哈 这样必须睡够！！

🟡 算法与图论 (第4、5、8章)

🟠 网络计划与查漏补缺 (第1、9章)

🔴 记忆与心态

💡 考试做题技巧 (救命TIPS)

2025年运筹学期末突击模拟试卷

一、填空题（每题3分，共15分）

二、单项选择题（每题3分，共15分）

三、数学建模题（每题8分，共16分，只列模型，不求解）

四、简答题（每题7分，共14分）

五、综合计算题（每题13-14分，共40分）

🟢 参考答案与解析

一、填空题

二、单项选择题

三、数学建模题

四、简答题

五、综合计算题

2025年运筹学期末突击模拟试卷 (B卷)

一、填空题（每题3分，共15分）

二、单项选择题（每题3分，共15分）

三、数学建模题（每题8分，共16分）

四、简答题（每题7分，共14分）

五、综合计算题（每题13-14分，共40分）

🟢 B卷参考答案与解析

一、填空题

二、单项选择题

三、数学建模题

四、简答题

五、综合计算题

😴 睡觉哈哈哈这样必须睡够！！