计算

2025-03-10 本文已影响0人 bowen_wu

页式存储计算

基本概念

逻辑地址（LA, Logical Address）：程序使用的地址，由 CPU 生成。
物理地址（PA, Physical Address）：内存实际的地址。
页（Page）：逻辑地址空间被划分成大小相等的块（通常 4KB）。
页框（Frame）：物理内存同样被划分成大小相等的块（通常 4KB）。
页表（Page Table）：存储逻辑页号（Page Number）到物理页框号（Frame Number）的映射关系。

逻辑地址拆分

逻辑地址（LA）由页号（Page Number）和页内偏移（Offset）组成：

$\text{逻辑地址} = \text{页号} (\text{Page Number}) + \text{页内偏移}(\text{Offset})$

物理地址计算

物理地址（PA）由物理页框号（Frame Number）和页内偏移（Offset）组成，计算公式为：

$\text{物理地址} = \text{物理页框号} (\text{Frame Number}) \times \text{页大小} + \text{页内偏移} (\text{Offset})$

计算步骤

1. 逻辑地址 → 逻辑页号 & 偏移量

逻辑页号 (P)：此处使用十进制计算
$P = \lfloor \frac{\text{LA}}{\text{页大小}} \rfloor$
页内偏移 (d)：此处使用十进制计算
$d = \text{LA} \% \text{页大小}$

2. 查询页表，找到逻辑页号 P 对应的物理页框号 F

通过查询页表，找到逻辑页号 $( P )$ 在物理内存中的映射，即对应的物理页框号 $( F )$ 。

3. 计算物理地址

计算物理地址 ( PA )：

$PA = (F \times \text{页大小}) + d$

逻辑地址十进制示例计算

已知：

页大小 = 4KB = $(2^{12})$
逻辑地址（LA） = 30000（十进制）
页表映射：
- 逻辑页号 7 → 物理页框号 3
- 逻辑页号 8 → 物理页框号 10

求物理地址（PA）

步骤 1：计算逻辑页号（P）和偏移量（d）

逻辑页号（P）：
$P = \lfloor \frac{30000}{4096} \rfloor = \lfloor 7.32 \rfloor = 7$
页内偏移（d）：
$d = 30000 \mod 4096 = 30000 - (7 \times 4096) = 30000 - 28672 = 1328$

步骤 2：查页表，逻辑页号 7 → 物理页框号 3

步骤 3：计算物理地址

$PA = (3 \times 4096) + 1328 = 12288 + 1328 = 13616$

结论：物理地址（PA） = 13616

逻辑地址二进制示例计算

已知条件：

页大小 = 1024 字节（ $(2^{10})$ 字节）
逻辑地址 = 110101001101（二进制）
页表映射：
- 逻辑页号 3 → 物理页框号 2
- 逻辑页号 4 → 物理页框号 5

目标：计算物理地址。

步骤 1：分析二进制逻辑地址

逻辑地址（LA） = 110101001101（二进制）
由于页大小为 1024 字节（ $(2^{10})$ ），我们知道页内偏移量占用的是地址的低 10 位。

步骤 2：提取逻辑页号和页内偏移

页大小 = 1024 字节（ $(2^{10})$ 字节），所以每个页面的偏移占用 10 位。

逻辑地址 110101001101 可以分为：

逻辑页号（高位部分）：前 2 位 11（即 3，二进制转换为十进制）。
页内地址（Offset）：后 10 位 0100110101（即 613，二进制转换为十进制）

因此：

逻辑页号（VPN） = 3
页内地址（Offset） = 613

步骤 3：查找页表

根据页表，查找 逻辑页号 3 对应的 物理页框号 2

步骤 4：计算物理地址

物理地址 = 物理页框号 × 页大小 + 页内偏移。

$\text{物理地址（PA）} = (\text{物理页框号} \times \text{页大小}) + \text{页内地址}$

将值代入公式：

$PA = (2 \times 1024) + 613 = 2048 + 613 = 2661$

结论

最终，物理地址 PA = 2661。

索引结构

已知条件

地址项大小 = 4B（即一个指针大小）
磁盘索引块大小 = 4KB
磁盘数据块大小 = 4KB
索引节点（inode）包含 8 个地址项
- 前 6 个是直接索引
- 第 7 个是一级间接索引
- 第 8 个是二级间接索引

计算文件最大长度

1. 直接索引

直接索引项个数 = 6
每个索引项指向 一个数据块。
可寻址数据量：
$6 \times 4KB = 24KB$

2. 一级索引

第 7 个地址项指向一个一级索引块。
索引块大小 = 4KB，每个地址项 4B：
$\frac{4KB}{4B} = 1024 \text{ 个索引项}$
每个索引项指向 一个数据块：
$1024 \times 4KB = 4MB$

3. 二级索引

第 8 个地址项指向一个二级索引块。
一个二级索引块 存放的是 一级索引块的地址：
- 一个二级索引块大小 = 4KB，可存 1024 个一级索引块地址。
- 每个一级索引块可管理 1024 个数据块。
- 总数据块数 = $( 1024 \times 1024 = 1,048,576 )$ 。
- 可寻址数据量：
  $1,048,576 \times 4KB = 4TB$

4. 计算单个文件的最大长度

索引级别	可访问的数据块数	可寻址数据量
直接索引 (6 项)	6	24KB
一级索引 (1 项)	1024	4MB
二级索引 (1 项)	$( 1024 \times 1024 = 1,048,576 )$	4TB
合计	1,049,606 个数据块	4TB + 4MB + 24KB = 4198424KB

因此，单个文件的最大长度 4198424KB。

访问不同逻辑块号的方式

假设逻辑块号 L：

如果 L < 6：
- 直接索引，从 inode 直接找到数据块地址。
如果 6 ≤ L < 6 + 1024：
- 一级索引，通过 第 7 个地址项 访问索引块，再找到数据块地址。
如果 L ≥ 6 + 1024：
- 二级索引：
  - 计算二级索引块的索引项编号：
    $\frac{L - 6 - 1024}{1024}$
  - 先通过 inode 的第 8 个地址项 找到 二级索引块。
  - 在二级索引块中找到 对应的一级索引块。
  - 在 一级索引块 中找到数据块地址。

地址空间与总线

编址方式

类型	特点	地址计算示例
字节编址	存储体的存储单元是字节存储单元，即最小寻址单元是一个字节（`1byte == 8bit`）	32位系统最大寻址4GB $(2^{32})$
字编址	存储体的存储单元是字存储单元，即最小寻址单位是一个字（字长与计算机相关）	地址0对应0-3字节（字是4B）

最大寻址空间 = 2^总线宽度

Cache映射机制

直接映射（Direct Mapped）

地址划分：

| Tag | Index | Block Offset |

参数计算：

行数 = Cache容量 / 行大小
Index位数 = log₂(行数)
Offset位数 = log₂(行大小)
Tag位数 = 地址总位数 - Index位数 - Offset位数

地址范围计算

基本公式： $地址范围 = 起始地址$ ~ (起始地址 + 容量 - 1)$
计算步骤
1. 将主存容量转换为字节数
2. 确定地址的十六进制表示范围
3. 验证地址总线宽度限制

示例

以64MB主存，32位地址总线，字节编址为例

步骤1：容量转换
64MB = 64 × 2²⁰ Bytes = 2⁶ × 2²⁰ = 2²⁶ Bytes

地址总数 = 2²⁶ = 67,108,864个地址

步骤2：地址范围表示
起始地址：0x00000000（32位全零）

结束地址：0x00000000 + 64MB - 1 = 0x03FFFFFF
（因为64MB = 0x04000000，减1得0x03FFFFFF）

64MB = 64 * 2^20 =  64 × 1,048,576 = 67,108,864（十进制）= 2 ^ 26
         = 0x04000000（十六进制）
         = 0000 0100 0000 0000 0000 0000 0000 0000（二进制）

步骤3：验证地址总线
32位总线最大寻址能力：2³² = 4GB

64MB = 0x04000000（二进制高6位为000000）

实际使用地址线：低26位（2²⁶=64MB）

按字编址（字长4B）

相同64MB主存：

地址总数 = 64MB / 4B = 16M = 2²⁴
地址范围 = 0x000000 ~ 0xFFFFFF（24位地址）

主存编址计算

存储单元
- 存储单元个数 = 最大地址 - 最小地址 + 1
总容量 = 存储单元个数 * 编址内容
根据存储器所要求的容量和选定的存储芯片的容量，就可以计算出所需芯片的总数。即总片数 = 总容量 / 每片的容量
2^10 = 1024(1KB) => 8K = 8 * 2 ^ 10bit
2^20 = 2^10 * 2^10(1MB)
2^30 = 2^10 * 2^10 * 2^10(1GB)
84000H => 表示十六进制
8FFFFH + 1 - 84000 = 90000H - 84000H = C000H = 12 * 16 ^ 3

假设某计算机系统的主存容量为 64MB，采用 字节编址 方式，地址总线宽度为 32位。请回答以下问题：
1. 计算主存的地址范围（用十六进制表示）。
2. 如果该系统的 Cache 采用 直接映射 方式，Cache 大小为 512KB，每个 Cache 行大小为 64B，请计算：
  - Cache 的总行数。
  - 地址中用于标识 Cache 行的位数。
  - 地址中用于标识 Cache 标签的位数。
3. 如果系统采用 分页存储管理，页大小为 4KB，请计算：
  - 主存中共有多少页。
  - 逻辑地址中页内偏移量占用的位数。
  - 逻辑地址中页号占用的位数。

答案

位示图法

用二进制位表示磁盘块是否空闲：

0：表示该块空闲
1：表示该块已占用

位示图法

磁盘优化分布存储计算

存取时间 = 寻道时间（平均定位时间，磁头移动到磁道所需的时间） + 等待时间（转动延迟，等待读写的扇区转到磁头下方所用的时间）

题目

示意图

磁盘单缓冲区与双缓冲区读取计算

题目

示意图

流水线执行时间计算

流水线周期为执行时间最长的一段
流水线执行时间计算公示：一条指令执行时间 + （指令条数 - 1）* 流水线周期
- 理论公式：(t₁ + t₂ + ... + t_k) + (n - 1) * t
- 实践公式：k * t + (n - 1) * t

流水线

吞吐率（Though Put rate, TP）

指在单位时间内流水线所完成的任务数量和输出的结果数量。公式：
$TP = \frac{指令条数}{流水线执行时间}$

流水线最大吞吐率公式：
$TP_{max} = \lim_{n \to \infty} \frac{n}{(k + n - 1)t} = \frac{1}{t}$

流水线加速比

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比（流水线加速比 > 1）。公式：

$S = \frac{不使用流水线执行时间}{使用流水线执行时间}$

循环校验码 CRC（Cyclic Redundancy Check）

在 k 位信息码之后拼接 r 位校验码。应用 CRC 码的关键是如何从 k 位信息位简便地得到 r 位校验位（编码），以及如何从 k + r 位信息码判断是否出错。可检错，不可纠错。循环冗余校验码编码规律如下：

把待编码的 N 位有效信息表示为多项式 M(X)
把 M(X) 左移 K 位，得到 M(X) * X^k，这样空出了 K 位，以便拼装 K 位余数（即校验位）（余数拼接在后面）
选取一个 K + 1 位的产生多项式 G(X)，对 M(X) * X^k 做模2除
把左移 K 位以后得有效信息与余数 R(X) 做模2加减，拼接为 CRC 码，此时的 CRC 码共有 N + K 位
把接收到的 CRC 码用约定的生成多项式 G(X) 去除，如果正确，则余数为0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有唯一的对应关系

CRC 例

模2除法

指在做除法运算的过程中不计其进（借）位的除法

模2除法

磁盘阵列（RAID，Redundant Array of Independent Disks）

$RAID 3/RAID 5 容量 = (n - 1) \times C_{\text{min}}，其中 n 是磁盘的总数量$
$RAID 3/RAID 5 磁盘利用率 = \frac{n - 1}{n}，其中 n 是磁盘的总数量$

无损分解

无损分解表法（分解矩阵法）

如果关系 R 被分解成子关系 R₁, R₂, ..., R_n，可以构造一个分解矩阵来检查是否无损。

步骤

创建矩阵，每一列代表一个属性，每一行代表一个子关系：
- 初始状态：如果属性属于某个子关系 R_i，标记为 R_i，否则标记为 NULL。
根据函数依赖更新矩阵：
- 若某一行的某些属性可以通过函数依赖推导出某个属性 X，则用同一行的标记替换 X 的值。
检查是否存在一行所有元素仍然唯一：
- 如果某一行的所有列的值都相同（即全为 R₁、R₂ 之一），则无损。
- 否则，有损。

示例

给定关系 R(A, B, C)，函数依赖：
$F = \{ A \rightarrow B, B \rightarrow C \}$

分解：
$R1(A, B), R2(B, C)$

属性	A	B	C
R₁	R₁	R₁	NULL
R₂	NULL	R₂	R₂

根据 A → B，R₁ 可决定 B，因此 B 变为 R₁
根据 B → C，R₁ 可决定 C，因此 C 变为 R₁
结果：

属性	A	B	C
R₁	R₁	R₁	R₁
R₂	NULL	R₂	R₂

有一整行是 R₁，因此是无损分解 ✅

基于函数依赖的无损判定（属性闭包法）

定理： 关系模式 R 在 R1(A1, A2, ...), R2(B1, B2, ...) 上的分解是无损的，当且仅当：
$(R_1 \cap R_2) \rightarrow R_1 \quad 或者 \quad (R_1 \cap R_2) \rightarrow R_2$

即：

公共属性集（ $( R_1 \cap R_2 )$ ）可以函数依赖地决定至少一个完整的子模式（R1 或 R2）。
这样，在 R1 ∪ R2 进行自然连接时，不会产生错误的笛卡尔积。

示例

给定关系 R(A, B, C)，函数依赖集：
$F = \{ A \rightarrow B, B \rightarrow C \}$

分解：
$R1(A, B), R2(B, C)$

验证无损：

公共属性 R1 ∩ R2 = {B}
检查 B 是否能决定 R1 或 R2：
- B → C ✅（可以决定 R2）
- 但 B 不能决定 A
- 因此，不满足无损分解条件 ❌（有损分解）

总结

方法	步骤	适用场景
属性闭包法	计算 $( (R_1 \cap R_2) \rightarrow R_1 )$ 或 $( (R_1 \cap R_2) \rightarrow R_2 )$ 是否成立	适用于两个子关系的无损判定
无损分解表法	构造矩阵，利用函数依赖推导，检查是否能合并行	适用于多个子关系的无损判定

最小生成树

最小生成树（Minimum Spanning Tree, MST）是指一个无向加权连通图的生成树，使得其所有边的权值之和最小。

Kruskal 算法

Kruskal 算法适用于稀疏图，基于贪心策略，每次选择最小的边，使用并查集 Union-Find判断连通性，避免形成环。

步骤

初始化：将所有边按权重从小到大排序。
遍历边列表：
- 选取当前最小的边，判断是否形成环（使用并查集）。
- 如果不成环，将边加入 MST，继续选取下一条边。
- 如果成环，跳过这条边。
终止条件：当 MST 包含 (V-1) 条边时，算法终止。

时间复杂度

排序边集： $(O(E \log E))$
并查集操作（路径压缩）： $(O(E \log V))$
总复杂度： $(O(E \log E))$

示例

给定无向加权图（共 9 个节点，12 条边）：

       (A)
      /   \
    4/     \8
    /       \
   (B)-----6----(C)
   |  \         /  \
  2|   \3    7/     \9
   |    \    /       \
   (D)--8--(E)---4---(F)
    \    |   |      /
    7\   |   |4    /10
      \  |   |   /
      (G)---1---(H)
         \   /
          \5/
          (I)

解

初始化：将所有边按权重从小到大排序。
遍历边列表：
- 选取当前最小的边，判断是否形成环（使用并查集）。
- 如果不成环，将边加入 MST，继续选取下一条边。
- 如果成环，跳过这条边。
终止条件：当 MST 包含 (n-1) = 8 条边时，算法终止。

计算过程

选取边	权重	说明
G-H	1	选入
B-D	2	选入
B-E	3	选入
A-B	4	选入
E-F	4	选入
E-G	5	选入
B-C	6	选入
C-E	7	选入（共8条，完成）

MST 由以上 8 条边组成，总权重为 32。

最短路径

Dijkstra 算法（适用于无负权图）

Dijkstra 采用贪心策略，使用优先队列（堆）优化，时间复杂度 $(O(E \log E))$

示例

求A到D的最短路径

       (A)
      /   \
    4/     \1
    /       \
   (B)-----2----(C)
   |  \        /  
  5|   \7    3/
   |    \    /      
   (D)--7--(E)

解

初始状态：
- A 作为起点，设 dist(A) = 0，其余 dist(∞)。
- 优先队列 记录当前最短路径可达的节点。
第一轮（从 A 开始）：
- A → C（1），更新 dist(C) = 1
- A → B（4），更新 dist(B) = 4
- 选取 C 作为下一个访问节点。
第二轮（从 C 开始）：
- C → B（2），新 dist(B) = min(4, 1+2) = 3
- C → E（3），更新 dist(E) = 4
- 选取 B 作为下一个访问节点。
第三轮（从 B 开始）：
- B → D（5），更新 dist(D) = 8
- B → E（7），不更新（已有 dist(E) = 4）
- 选取 E 作为下一个访问节点。
第四轮（从 E 开始）：
- E → D（7），不更新（已有 dist(D) = 8）
- 选取 D 作为下一个访问节点。

最终最短路径: A → C → B → D, 距离 = 8

网络与最大流量

最大流问题是网络流问题中的一种经典问题，目标是找出在一个网络中从源点（Source）到汇点（Sink）的最大流量。流量的大小受到网络中每条边容量的限制

最大流问题背景

网络图：一个有向图，其中每条边有一个容量（Capacity）限制，表示该边能承载的最大流量
流量：每条边上流动的量不能超过边的容量
目标：从源点到汇点的流量最大化

Ford-Fulkerson 算法

Ford-Fulkerson 算法用于解决最大流问题，基本思想是寻找增广路径并通过增加流量来增加源点到汇点的流量，直到没有增广路径为止。增广路径是指从源点到汇点的一条路径，其中路径上的每条边都有剩余容量，可以通过该路径增加流量。

基本步骤

初始化：为每条边的流量赋初值 0，并将每条边的剩余容量初始化为其原始容量。
寻找增广路径：使用深度优先搜索（DFS）或广度优先搜索（BFS）来寻找一条增广路径，从源点到汇点。
增广流量：沿增广路径增加流量，并更新每条边的流量和残量容量。
重复步骤 2 和 3，直到找不到增广路径为止。

算法终止条件：

当没有增广路径时，算法结束，当前流量就是最大流量。

时间复杂度

最坏情况下时间复杂度为 $(O(E \cdot \text{max flow}))$ ，其中 $(E)$ 是边的数量，最大流量是流量的上限。

Ford-Fulkerson 算法的核心概念

残量网络：是一个通过更新流量和剩余容量得到的图。残量容量指的是边的最大容量减去当前的流量。
增广路径：是一条从源点到汇点的路径，其中路径上的每一条边的剩余容量都大于 0。

示例

     (S)
    /   \
   10    5
  /       \
(A)---15--->(B)
 | \      /  |
 5  10  10  10
 |    \ /    |
(C)---->(D)-->(T)

求从源点 S 到汇点 T 的最大流量

解

步骤 1：初始化

所有流量初始为 0。
计算从 S 到 T 的最大流量。

步骤 2：寻找增广路径

第一次增广路径

从 S 通过 A → D → T 找到增广路径：
- 最小剩余容量：10
- 更新流量：
  - S → A 流量 10
  - A → D 流量 10
  - D → T 流量 10

第二次增广路径

继续寻找增广路径 S → B → T：
- 最小剩余容量：5
- 更新流量：
  - S → B 流量 5
  - B → T 流量 5

第三次增广路径

继续寻找增广路径 S → A → C → T：
- 最小剩余容量：5
- 更新流量：
  - S → A 流量 5
  - A → C 流量 5
  - C → T 流量 5

步骤 3：最大流计算

最终流量：

S → A：10 + 5 = 15
S → B：5
A → D：10
D → T：10
B → T：5
C → T：5

最大流量 = 15。

线性规划（Linear Programming, LP）

在一组约束条件下来寻找目标函数的极致（极大值和极小值）问题
线性规划问题的数学模型通常由线性目标函数、线性约束条件、变量非负条件组成（实际问题中的变量一般都是非负的）
线性规划问题就是面向实际应用，求解一组非负变量，使其满足给定的一组线性约束条件，并使某个线性目标函数达到极值。满足这些约束条件的非负变量组的集合称为可行解域。可行解域中使目标函数达到极值的解称为最优解
线性规划问题的最优解要么是0个，要么是1个，要么是无穷个
在实际应用中，可以直接求约束条件方程组的解，既是交叉点，将这些解代入到目标函数中判断是否极值即可

图解法（适用于二维问题）

适用于变量个数 不超过 2 的情况，步骤如下：

绘制约束直线：将不等式转换为等式，在坐标平面上绘制边界线。
确定可行解区域：根据约束条件找到满足所有不等式的区域。
计算目标函数值：找到可行区域的顶点，并计算目标函数值。
选取最优解：最大化或最小化目标函数。

示例

求最大化 $Z = 3x_1 + 5x_2$

约束条件： $2x_1 + 3x_2 \leq 12$ ， $x_1 + x_2 \leq 5$ ， $x_1, x_2 \geq 0$

解1

适用于变量少的情况，我们绘制不等式的边界线：

第一条约束：
$2x_1 + 3x_2 = 12$
- 当 $( x_1 = 0 )$ 时， $( x_2 = 4 )$ （交 y 轴）
- 当 $( x_2 = 0 )$ 时， $( x_1 = 6 )$ （交 x 轴）
第二条约束：
$x_1 + x_2 = 5$
- 当 $( x_1 = 0 )$ 时， $( x_2 = 5 )$
- 当 $( x_2 = 0 )$ 时， $( x_1 = 5 )$
求可行区域：取两直线交点解方程：
$\begin{cases} 2x_1 + 3x_2 = 12 \\ x_1 + x_2 = 5 \end{cases}$
解得：
$x_1 = 3, \quad x_2 = 2$
计算目标函数值：
$Z = 3x_1 + 5x_2$
- $( (0,0) \Rightarrow Z = 3(0) + 5(0) = 0 )$
- $( (5,0) \Rightarrow Z = 3(5) + 5(0) = 15 )$
- $( (0,4) \Rightarrow Z = 3(0) + 5(4) = 20 )$ ✅（最大值）
- $( (3,2) \Rightarrow Z = 3(3) + 5(2) = 9 + 10 = 19 )$

结论：
最优解为 $( x_1 = 0, x_2 = 4 )$ ，最大值 $( Z = 20 )$ 。

解2

可以画图（将所有的约束条件画出来），之后将目标函数（等值线）画出来，之后平移等值线，使其仍然经过可行区域内的点，直到刚好接触可行区域的边界，接触的点即为最优解：

最大化问题：等值线最远接触的点
最小化问题：等值线最早接触的点

伏格尔法（Vogel’s Approximation Method, VAM）

伏格尔法是一种用于求解运输问题初始可行解的启发式方法。它通过最小化惩罚成本（即每行或每列的最小和次小运输成本的差值）来选择分配方案，通常比北西角法（NWCM）或最小成本法（LCM）提供更优的初始解。

伏格尔法求解步骤

计算每行和每列的惩罚值
- 惩罚值 = 该行或列的最小运输成本和次小运输成本的差值。
选择最大惩罚值的行或列
- 在最大惩罚值的行或列中，找到成本最小的格子进行分配。
进行货物分配
- 在选定的单元格分配尽可能多的货物（即 供应或需求中的最小值）。
- 更新供应和需求，如果某行或某列的需求或供应归零，则划掉该行或该列。
继续重复上述步骤
- 重新计算剩余行列的惩罚值，重复 步骤 2 和 3，直到所有需求和供应满足。

示例

某公司有 3 个工厂（供应点） 和 4 个仓库（需求点），需要将产品从工厂运输到仓库，目标是 最小化运输成本。已知每个工厂的最大供应量，每个仓库的 需求量 以及单位运输成本，数据如下：

工厂 S1、S2、S3 分别能供应 7、10、5 个单位的货物。
仓库 D1、D2、D3、D4 需要分别 5、8、7、2 个单位的货物。
运输成本矩阵 表示从工厂到仓库的单位运输成本（单位：元）。

供应/需求	D1	D2	D3	D4	供应
S1	19	30	50	10	7
S2	70	30	40	60	10
S3	40	8	70	20	5
需求	5	8	7	2

在满足 每个工厂的供应能力 和 每个仓库的需求量 的前提下，最小化运输成本。

解

Step 1：计算行和列惩罚值

惩罚值 = 该行（或列）的最小值和次小值的差值

行惩罚值计算：

S1: (19, 10) → 9
S2: (30, 40) → 10
S3: (8, 20) → 12 ✅（最大）

列惩罚值计算：

D1: (19, 40) → 21
D2: (8, 30) → 22
D3: (40, 50) → 10
D4: (10, 20) → 10

最大惩罚值 = 22（D2 列）

Step 2：选择最小成本格进行分配

D2 列最小成本 = 8（S3, D2）
分配量 = min(供应 5, 需求 8) = 5

更新后：

供应/需求	D1	D2	D3	D4	供应
S1	19	30	50	10	7
S2	70	30	40	60	10
S3	40	8 (5)	70	20	0 (删除)
需求	5	3	7	2

S3 供应完成，删除该行

Step 3：重新计算惩罚值

最大惩罚值 = 51（D1 列）
D1 列最小成本 = 19（S1, D1）
分配量 = min(供应 7, 需求 5) = 5

更新后：

供应/需求	D1	D2	D3	D4	供应
S1	19 (5)	30	50	10	2
S2	70	30	40	60	10
需求	0	3	7	2

D1 需求完成，删除该列。

Step 4：继续分配

D4 列最小运输成本 = 10（S1, D4）
分配量 = min(供应 2, 需求 2) = 2

更新后：

供应/需求	D2	D3	D4	供应
S1	30	50	10 (2)	0 (删除)
S2	30	40	60	10
需求	3	7	0 (删除)

S1 供应完成，删除该行。

Step 5：继续分配

D2 列最小运输成本 = 30（S2, D2）
分配量 = min(供应 10, 需求 3) = 3

更新后：

供应/需求	D2	D3	供应
S2	30 (3)	40	7
需求	0	7

D2 需求完成，删除该列。

Step 6：最后分配

剩余 S2 → D3，直接分配 7：

供应/需求	D3	供应
S2	40 (7)	0

所有需求和供应满足，完成！

最终分配方案

供应/需求	D1	D2	D3	D4
S1	5	-	-	2
S2	-	3	7	-
S3	-	5	-	-

计算运输成本

$Z = (5 \times 19) + (2 \times 10) + (3 \times 30) + (7 \times 40) + (5 \times 8) = 95 + 20 + 90 + 280 + 40 = 525$

总结

计算每行每列惩罚值
选择最大惩罚值的行/列
在该行/列选择最小成本格进行分配
更新需求和供应
重复步骤，直到所有需求和供应满足

博弈论

状态转移矩阵

示例

状态：晴天（S）和雨天（R），用数字表示为 1（晴天）和 2（雨天）。

状态转移矩阵 P 如下：
$P = \begin{bmatrix} P(S \rightarrow S) & P(S \rightarrow R) \\ P(R \rightarrow S) & P(R \rightarrow R) \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}$

平稳分布（steady-state distribution）

如果没有初始概率，即没有给定任何状态（如晴天或雨天）的概率分布，马尔可夫链在经过一定的时间后会趋向平稳分布（steady-state distribution）。这意味着，不管一开始的状态如何，系统最终会稳定在一个固定的概率分布上，称为平稳分布

如何求平稳分布

平稳分布指的是当系统到达一定状态后，各个状态的概率不再变化。即，平稳分布满足以下条件：

$\pi P = \pi$

其中， $(\pi)$ 是平稳分布的概率向量， $(P)$ 是转移矩阵。

平稳分布的求解步骤

我们将求解这个平稳分布：

$\begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix} \begin{bmatrix} P(S \rightarrow S) & P(S \rightarrow R) \\ P(R \rightarrow S) & P(R \rightarrow R) \end{bmatrix} = \begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix}$

代入转移矩阵：

$\begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} \pi_1 & \pi_2 \end{bmatrix}$

即得到以下方程：

$\begin{aligned} \pi_1 &= 0.8\pi_1 + 0.4\pi_2 \\ \pi_2 &= 0.2\pi_1 + 0.6\pi_2 \end{aligned}$

此外，还需要满足概率和为 1：

$\pi_1 + \pi_2 = 1$

解方程即可。因此，平稳分布为：

$\pi = \begin{bmatrix} \frac{2}{3} & \frac{1}{3} \end{bmatrix}$

这意味着，无论初始天气是什么，经过足够多的天数后，系统会趋向于：

晴天的概率是 2/3
雨天的概率是 1/3

排队论

决策论

六个要素

决策者
可供选择的方案（包括行动、策略）
衡量选择方案的准则（目的、目标、正确性）
事件（被决策的对象）
每一事件的发生将会产生的某种结果
决策者的价值观

不确定性决策五种方案

悲观主义准则（小中取大max(min)）：先取每个方案最小的收益，再取所有最小收益中最大的那个
乐观主义准则（大中取小max(max)）：先取每个方案最大的收益，再取所有最大收益中最大的那个
折中主义准则：设定折中系数a，用每个方案的最大收益 * a + 最小收益 * (1 - a)，选择每个方案中计算结果最大的那个。a = 1时是乐观主义，a = 0时是悲观主义
等可能性准则：设定每个可能的结果的发生都是等可能得，这样就知道每个结果发生的概率，即将不确定型的问题转换为风险决策问题
后悔值准则（最小最大后悔值min(max)）：在不同的环境中（之前都是方案），投资方案获得的最大收益 - 当前选择的收益 = 后悔值，将所有后悔值中每个方案的最大后悔值选出，再从这些最大的后悔值中选择最小的即可

决策树

数学模型 Mathematical Model

数学建模

数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象和简化，建立能近似刻画并解决实际问题的模型的一种强有力的数学手段
用数学语言（如方程、图形、算法等）对现实世界问题中的对象、关系或过程进行抽象描述的工具
核心目的是通过数学方法模拟、预测或优化现实系统的行为
数学建模应该有一个统一的评价机制
数学建模没有反馈机制

核心要素：

变量（Variables）：输入（自变量）、输出（因变量）
关系（Relationships）：方程、不等式、概率分布等
参数（Parameters）：模型中的固定量

数学建模过程

模型准备
模型假设
模型建立
模型求解
模型分析
模型检验
模型应用

数学建模方法

直接分析法
类比法
数据分析法
构想法

4大分析方法

分析类型	主要应用阶段	阶段任务描述	典型方法/工具
一致性分析	模型构建阶段	验证模型内部逻辑自洽性	逻辑约束检查、定义域验证
似然性分析	模型求解阶段	统计模型中参数的概率分布	最大似然估计、MCMC采样
灵敏性分析	模型验证阶段	检验参数变化对结果的影响	Sobol指数、蒙特卡洛模拟
准确性分析	模型验证/应用阶段	评估结果与真实值的误差	RMSE、交叉验证、混淆矩阵

数学建模六大原则

问题导向原则
简化与精确平衡原则
可验证性原则
透明性原则
鲁棒性原则
迭代优化原则

匈牙利算法（Hungarian Algorithm）

问题类型：任务分配问题（Assignment Problem），即在 n 个工人和 n 个任务之间找到最小总成本或最短总工时的完美匹配

算法核心思想

通过矩阵变换，逐步生成零元素，并利用零元素的位置找到最优分配。

关键步骤：

行归约：每行减去该行最小值
列归约：每列减去该列最小值（若尚未归约）
覆盖所有零：用最少的水平/垂直线覆盖所有零
调整矩阵：若覆盖线数 < n，调整未被覆盖的元素，生成新的零
重复：直到覆盖线数 = n，此时零的位置即为最优分配

成本

可变成本总额与销售数量有关 => 每个物品可变成本 = 可变成本总额/销售数量
总成本 = 固定成本 + 销售数量 * 每个物品可变成本 + 税金

三点估算法 Three-Point Estimation

项目管理中常用的一种任务时长或成本评估方法，它结合了乐观、悲观和最可能值，来更准确地估算任务进度或预算
三点估算法的三个估算值
- O（Optimistic Estimate）乐观时间：如果一切顺利，任务最快能多久完成？（最理想的情况）
- M（Most Likely Estimate）最可能时间：在正常情况下，任务通常需要多久完成？（最常发生的情况）
- P（Pessimistic Estimate）悲观时间：如果很多事情出错，最坏的情况下需要多久完成？（最糟的情况）

PERT 估算法（项目评估与审查技术）

用于获得加权平均时间（期望时间）

E = (乐观时间 + 4 * 最可能时间 + 悲观时间) / 6

更加偏向最可能情况（M）
适用于不确定性较大的任务估算

流水车间调度问题 Flow Shop Scheduling

目标通常是最小化总完成时间（Makespan）
基本的原则：把多个任务中，第1步耗时最短的安排在最开始执行，再把最后1步耗时最短的安排在最后完成

知识点

为近似计算 XYZ 三维空间内由三个圆柱 $x^2 + y^2 \leq 1$ ， $y^2 + z^2 \leq 1$ ， $x^2 + z^2 \leq 1$ 相交部分 $V$ 的体积，以下四种方案中，_____ 最容易理解，最容易编程实现。

A. 在 $z = 0$ 平面中的圆 $x^2 + y^2 \leq 1$ 上，近似计算二重积分
B. 画出 $V$ 的形状，将其分解成多个简单形状，分别计算体积后，再求和
C. 将 $V$ 看作多个区域的交集，利用有关并集、差集的体积计算交集体积
D. $V$ 位于某正立方体 $M$ 内，利用 $M$ 内均匀分布的随机点落在 $V$ 中的比例进行计算

本题考查应用数学-随机模拟的基础知识。

由于三个圆柱相交部分很难画图，很难想象其形状，也很难确定其边界参数，因此，方案 A、B、C 的计算都有相当难度。方案 D 的计算非常容易，在计算机上利用伪随机数，很容易取得正立方体 $\{-1 \leq x,y,z \leq 1\}$ 内均匀分布的随机点，也很容易判断该点是否位于 $V$ 内。对大量的随机点，很容易统计在该正立方体中的随机点位于 $V$ 中的比例。该比例值的 8 倍就近似地等于 $V$ 的体积。
1路和2路公交车都将在10分钟内均匀随机地到达同一站台，则它们相隔4分钟内到达该站的概率?

解题步骤：
1. 问题建模
  - 设1路车到达时间为随机变量X ~ U(0,10)
  - 设2路车到达时间为随机变量Y ~ U(0,10)
  - X和Y独立同分布
2. 求解目标：计算P(|X - Y| ≤ 4)
3. 几何概率法
  在10×10的单位正方形中：
  - 总面积 = 10 × 10 = 100
  - 满足|X - Y| ≤ 4的区域：
    - 介于直线Y = X + 4和Y = X - 4之间的带状区域
  - 不满足区域：
    - 左上角三角形：面积 = (6×6)/2 = 18
    - 右下角三角形：面积 = (6×6)/2 = 18
  - 满足区域面积 = 总面积 - 不满足区域 = 100 - 36 = 64