数学建模 / 英语

旅行商问题（TSP）- 形式化-2

MH Studio · YouTube · 8:37

YouTube · MH Studio原视频

选中时刻 · 0:00 · 章节点是时间参考，不表示实时播放进度。

视频中的要点

01TSP建模目标——2
02辅助顺序变量 $u_i$
03二元弧变量 $x_{i,j}$

来自学习笔记

u_i \ge 0,\quad i>1

辅助顺序变量 $u_i$

选中时刻

TSP 的第 2 种模型介绍

建议预备知识

基础整数规划
二元决策变量
旅行商问题
环游路线中子环路的概念
大M建模技巧
整数规划基础
图论基础（节点、边、环）
二元决策变量
基础整数规划符号
有向图与环
指派问题约束
线性规划松弛
分支定界术语
旅行商问题（TSP）
分支定界枚举法
优化中上下界的基本概念
指派问题作为松弛工具
启发式与超启发式方法简介

阅读与收藏

把讲解展开来看。

被收藏 0

已审核学习内容 · 视频分析 · 中文

阅读完整概览

这150秒讲座片段引入了旅行商问题的第二种整数规划模型，旨在自动打破子回路。在展示标题与章节提纲后，主讲人定义了一个新的非负变量 $u_i$ （ $i>1$ ），表示在抵达城市 i 之前所访问的城市数量，其关键假设是回路从城市1出发。二元弧变量 $x_{i,j}$ 被回顾为指示回路是否直接从城市 i 行进至城市 j。借助手绘的 i 到 j 示意图，讲座推导出条件规则： $x_{i,j}=1$ 蕴含 $u_i+1\le u_j$ ；而 $x_{i,j}=0$ 不对 $u_i$ 与 $u_j$ 施加任何直接关系。该“若—则”逻辑随后被线性化为大 M 不等式： $u_i+1\le u_j+M(1-x_{i,j})$ ，其中 M 需足够大以保证 $u_i\le M$ 。幻灯片推荐取 $M=n$ （即城市总数），并指出 $M=n-1$ 是更紧的最优估计，尽管在讲解中使用的是 n。该片段以最终的 MTZ 风格子环消除约束 $u_i+1\le u_j+n(1-x_{i,j})$ 对所有互异的 i, $j=2$ , $\dots$ ,n 结束，并表述为可自动消除子环。本片段中未出现数值演算示例，且在给定时长内未完成该约束能消除所有子环的完整形式化证明。本讲段介绍了旅行商问题（TSP）中的Miller-Tucker-Zemlin（MTZ）子环消除约束。它定义了用于记录城市访问顺序的辅助连续变量 $u_i$ ，并解释大M方法如何利用二元边变量 $x_{i,j}$ 来条件性地强制执行排序约束 $u_i + 1$ <= $u_j$ 。讲师特别强调这些约束需排除起始城市。随后分析了两个图示案例：一个是有效的完整回路，能得出一致的上下界和可行的u值；另一个是无效的子环构型，会生成一串循环的严格不等式，从而在数学上证明其不可行。本段时长为150秒的讲座内容讲解旅行商问题（TSP）模型-2中的子回路消除约束。首先，在一个5节点的示例图上验证：若存在一个不包含节点1的子回路，则辅助排序变量 $u_i$ 的取值将出现不一致，从而导致该子回路不可行。随后，视频呈现完整的整数规划模型：最小化所有弧的总成本，满足每个节点恰有一条入弧与一条出弧的约束、弧变量 $x_{i,j}$ 为二进制、子回路消除不等式 $u_i+1\le u_j+n(1-x_{i,j})$ ，以及 $u_i$ 的非负性约束。主讲人指出，该模型的主要优势在于能自动消除子回路，因而可直接使用 CPLEX 或 Gurobi 等标准求解器配合常规分支定界法求解；其劣势在于丧失了指派问题结构，致使线性松弛问题无法采用匈牙利法求解，且额外引入约 (n-1)^2 个约束。最后，视频以一道练习题收尾：要求用 CPLEX 求解模型-2，但本片段未执行具体数值求解。本段为67-第二次课内容，首先指出：可通过调用 CPLEX 求解器求解构型-2，并结合例题-1与例题-2的数据，在计算机上对 TSP 进行验证；随后转向对改进 TSP 分支定界法的概念性概述。主讲人指出两个关键方向：收紧下界与收紧上界。幻灯片明确说明，收紧下界采用指派问题方法，而收紧上界则采用启发式或超启发式方法。核心论断是：更优的界可大幅缩减分支定界法的枚举树规模。本片段未展示任何公式、数值实例或求解器输出。

在学习检查器中查看要点和时刻，或切换阅读标签查看完整笔记。

章节

0:00TSP 的第 2 种模型介绍 0:16定义辅助变量

u_i

0:49回顾变量

x_{i,j}

并寻求其与访问顺序之间的关系 1:20用于弧与城市访问顺序的“若—则”逻辑 2:04大-M 线性化及选取

M = n

2:25最终的破除子回路约束 2:30子环破除约束简介 3:00用完整回路验证该约束 4:40利用子回路演示不可行性 5:00在5节点示例上的子回路消除验证 6:25旅行商问题模型-2的完整表述 6:45优点：自动消除子回路，支持标准求解器 7:04缺点：丧失指派问题结构，且约束数量增多 7:26结课练习提示 7:30使用 CPLEX 对 TSP 构型-2进行测试 7:43改进 TSP 分支定界法 8:06通过指派问题方法获得下界 8:18通过启发式与超启发式方法获得上界

学习解说文稿

依据视频画面与讲解整理，并非逐字语音转写。

视频片段以题为“旅行商问题”的讲座开场，随后展示章节大纲，将本部分内容归入“精确方法”下的“建模—2”。主讲人指出，该建模方案旨在自动破除所有子回路，并在引入任何变量之前即明确了这一建模目标。

标题为“TSP：破除子回路约束”的幻灯片引入了一个新的辅助变量 $u_i$ 。它被定义为一个非负变量，表示在抵达城市 $i$ 之前所访问的城市数量，适用于 $i>1$ ；并明确假设整个回路从城市1出发。主讲人强调，这一起点城市假设至关重要，因为后续约束依赖于回路上城市访问的顺序概念。

接下来，讲座回顾标准的二元弧变量 $x_{i,j}$ ，其值为 1 当且仅当旅行路线直接从城市 $i$ 到城市 $j$ ，否则为 0。当前目标是将该弧变量与顺序变量 $u_i$ 和 $u_j$ 关联起来，因为子环消除需要确保路径选择与访问顺序之间的一致性。

一幅手绘示意图中，节点标有 $i$ 和 $j$ ，用以支持直观推导。若 $x_{i,j}=1$ ，即从 $i$ 到 $j$ 的弧被选用，则城市 $j$ 必在城市 $i$ 之后被访问，因此顺序变量须满足 $u_i+1\le u_j$ 。若 $x_{i,j}=0$ ，主讲人特别指出，此时无法在 $u_i$ 与 $u_j$ 之间推导出直接关系，因为模型不应在未选定该特定弧的情况下对城市的相对访问顺序施加约束。

该条件语句继而通过大-M 方法转化为线性不等式： $u_i+1\le u_j+M(1-x_{i,j})$ ，其中 $M$ 需足够大，以保证 $u_i\le M$ 成立。当 $x_{i,j}=1$ 时，项 $M(1-x_{i,j})$ 消失，顺序约束随之生效；当 $x_{i,j}=0$ 时，所添加的 $M$ 使该不等式松弛，从而不强制施加直接的顺序关系。

随后，讲座将大-M 常数具体化至旅行商问题情境。幻灯片指出，一个合理的估计值是 $M=n$ （即城市总数），并补充说明更紧的最优估计值为 $M=n-1$ 。主讲人说明，本次演示将在幻灯片中采用 $n$ ，因此最终呈现的模型采用 $M=n$ ，而非更紧的数值。

代入 $M=n$ 后，得到屏幕上显示的最终破除子回路约束： $u_i+1\le u_j+n(1-x_{i,j})$ ，适用于所有满足 $i,j=2,\dots,n$ 且 $i\ne j$ 的下标组合。主讲人指出，该约束可自动破除子回路。视频片段在呈现该公式及其作用后即结束；未包含对“所有可能子回路均被排除”的完整形式化证明，也未给出数值示例。

讲座首先介绍了旅行商问题中的子回路消除约束。公式 $u_i + 1 \le u_j + n(1 - x_{i,j})$ 针对所有 $i, j \in \{2, \dots, n\}$ 且满足 $i \neq j$ 的情况被引入。2，刻意排除城市 1，该城市作为回路的固定起点与终点。这种排除被描述为该约束的“关键所在”，可防止对配送中心施加人为限制。

辅助变量 $u_i$ 的作用被明确为记录所访问城市的顺序。术语 $n(1 - x_{i,j})$ 起到大M松弛的作用。当某条边被选中（即 $x_{i,j} = 1$ ）时，该项消失，从而严格强制执行 $u_i + 1 \le u_j$ ；反之，当该边未被选中（即 $x_{i,j} = 0$ ）时，加上 $n$ 可确保不等式平凡成立，实质上使该对城市对应的约束失效。数值 $n$ 被指出是大M常数的一个稳健估计值。

为验证该模型，构建了一个包含 $n=5$ 座城市的实例。有向图展示了一条有效的哈密顿回路： $1 \to 3 \to 2 \to 5 \to 4 \to 1$ 。子集 $\{2, 3, 4, 5\}$ 中的活跃边生成如下具体不等式： $u_2 + 1 \le u_3$ 、 $u_4 + 1 \le u_2$ 和 $u_5 + 1 \le u_4$ 此外，全局界 $u_i \le 4$ 成立，因为城市 1 是起点/终点。

讲师系统地通过从起点城市反向追踪路径，推导出各变量的上界。由于节点3直接连向节点1，故将 $u_3$ 赋以最大可能值4。将此上界沿不等式链逐级传递，得到 $u_2 \le 3$ 、 $u_4 \le 2$ 和 $u_5 \le 1$ 。由此确立了一个严格的无环顺序： $u_5 < u_4 < u_2 < u_3$ 。

随后在图上展示了可行的整数赋值方案。一种有效解设定为 $(u_2, u_3, u_4, u_5) = (3, 4, 2, 1)$ ；另一种则将整个序列整体下移至 $(2, 3, 1, 0)$ 。这两组赋值均完全满足所有推导出的不等式及上界约束，证实该模型能正确容纳合法的单回路行程，而不会剔除任何正当解。

分析继而转向一个无效构型，以检验该约束的剔除能力。一幅新图展示了两个互不连通的子回路：一个含2座城市的回路（ $1 \leftrightarrow 3$ ），以及另一个含3座城市的回路（ $2 \to 5 \to 4 \to 2$ ）。构成次级回路的边激活了约束 $u_4 + 1 \le u_2$ 、 $u_2 + 1 \le u_5$ 和 $u_5 + 1 \le u_4$ ，在 $u$ 变量之间形成闭合的依赖链。

通过串联这三个不等式，系统要求 $u_4 < u_2 < u_5 < u_4$ 。这种循环式的严格序关系构成根本性的数学矛盾，因为不存在实数严格小于其自身。尽管视频在明确陈述最终结论前结束，但该设定已确凿证明：MTZ约束使得任何子回路构型在数学上均不可行。

视频以一张标题为“TSP：子回路消除约束”的幻灯片开场，图中为一个五节点有向图。主讲人通过为节点3分配最大的排序值来开展具体验证，并写下 $u_3=3$ 。此步骤旨在检验某个给定的环状解是否能满足辅助排序约束。

由于剩余的环路未连接到节点3，讲师任意选择节点4并赋值为 $u_4=2$ ，同时指出该值必须小于3，因为指向节点1的节点应承载最大值。这在幻灯片所列其他不等式中引发了一连串推论。

利用幻灯片上显示的不等式 $u_5+1\le u_4$ ，赋值 $u_4=2$ 迫使 $u_5=1$ 成立；再利用 $u_2+1\le u_5$ ，数值 $u_5=1$ 迫使 $u_2=0$ 成立。这些是直接代入可见约束条件所得的结果，展示了排序变量如何在环路中传播。

接着，讲师考察幻灯片上第三个显示的不等式 $u_4+1\le u_2$ 。在 $u_4=2$ 条件下，该不等式要求 $u_2$ 等于3，但这与先前推导出的值 $u_2=0$ 矛盾。因此，幻灯片明确揭示了同一变量内部的不一致性，口述结论为：该子环路在子环路消除约束下不可行。

本例阐释了约束 $u_i+1\le u_j+n(1-x_{i,j})$ 的一般逻辑：当某条弧被选中时， $x_{i,j}=1$ 成立，此时不等式简化为 $u_i+1\le u_j$ ，从而强制规定从 $i$ 到 $j$ 的严格序关系。将此类严格不等式沿闭合环路逐段串联，最终将导致某个 $u$ 值必须大于其自身，这是不可能的。

随后，演示切换至标题为“TSP：模型构建-2”的完整模型幻灯片。目标函数为 $\min \sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}$ ，即最小化所选弧上的总旅行成本。讲师指出，该目标函数及部分约束与模型构建-1相似，而新增要素是子环路消除约束及其关联的非负变量。

度约束表示为 $\sum_{\substack{i=1\\ i\neq j}}^{n} x_{i,j}=1$ 对每个节点 $j$ 且 $\sum_{\substack{j=1\\ j\neq i}}^{n} x_{i,j}=1$ 对每个节点 $i$ 。这些约束确保每个节点恰好有一条选中的入弧和一条选中的出弧。该模型还声明 $x_{i,j}\in\{0,1\}$ 和 $u_i\ge 0$ 对于 $i=2,\ldots,n$ 。

子环消除族在完整公式中重新表述为 $u_i+1\le u_j+n(1-x_{i,j})$ 对所有 $i,j=2,\ldots,n$ 满足 $i\neq j$ 。这是区分该公式化模型与早期指派式模型的核心加法。2与早期的指派式模型。

随后，讲师总结其实用优势：由于这些显式不等式能自动消除子环路，该模型可直接交由CPLEX或Gurobi等商用求解器处理，并采用常规的分支定界法求解；无需为此模型从零开发专用的子环路处理算法。

接着指出两点劣势：第一，新增的约束与辅助变量破坏了纯粹的指派问题结构，因而无法再用匈牙利法求解其线性规划松弛；第二，该模型引入了约 $(n-1)^2$ 个额外约束，使整体问题规模相较于模型构建-1有所增大。

视频结尾处是一张标题为“TSP：模型构建-2测试”的幻灯片，提示语为：“使用示例-1与示例-2的数据，借助CPLEX求解器求解TSP的模型构建-2。” 讲师明确说明本视频不会实际求解该TSP问题，因此此项练习仅在此处宣布，未在视频中展开演算。

视频片段以一张标题为“TSP：模型-2检验”的幻灯片开场，其文字要求观众使用例题-1和例题-2中的数据，并用Cplex求解器求解TSP的模型-2。主讲人将此表述为对人工分支定界讨论的转向：此处不再延续该方法，而是转向借助Cplex进行计算求解的路径。

幻灯片随后切换为“TSP：改进分支定界法”，讲座重点也从求解器使用转向分支定界算法本身的优化。主讲人指出，改进主要集中在两个方面：下界与上界。其数学含义在于，更紧致的一对上下界可缩小用于剪枝的间隙，从而减少枚举树中需要探索的节点数量。

在下界方面，幻灯片与讲解指出，指派问题方法是本课程此前已涵盖的方法。该方法被呈现为获取TSP分支定界中更紧致下界的一种途径。主讲人还提到，后续幻灯片中将出现另一种下界方法，但该方法未在此片段中展示。

在上界方面，讲座指出，通常采用启发式或超启发式方法来获得更紧致的上界。其原理在于，更优的可行回路可给出更小的上界，从而再次增强分支定界树中的剪枝效果。片段最后预告，后续幻灯片将讨论TSP的启发式方法。

知识卡片

TSP建模目标——2

本节介绍旅行商问题（TSP）的第二种整数规划建模方式。其明确目标是构建一个能自动消除子回路的模型。在教材章节结构中，该模型被归类于‘精确方法’下的‘建模-2’。

辅助顺序变量 $u_i$

新变量 $u_i$ 针对城市 $i>1$ 定义，表示在抵达城市 $i$ 之前已访问的城市数量。该变量非负，用于编码相对于某一固定起点城市的访问次序。视频特别强调：假设旅行从城市1出发，这一假设对子回路消除逻辑至关重要。

u_i \ge 0,\quad i>1

二元弧变量 $x_{i,j}$

主讲人回顾了 $x_{i,j}$ 作为常规旅行商问题（TSP）中的弧选择变量。它是一个二元变量，且当且仅当回路直接从城市1前往城市 $i$ 时取值为 $j$ ；否则取值为0。该模型旨在建立 $x_{i,j}$ 、 $u_i$ 与 $u_j$ 之间的关系。

x_{i,j} \in \{0,1\}

对已选用弧的条件顺序规则

若从城市 $i$ 到城市 $j$ 的弧被选用，则城市 $j$ 处的访问次序至少比城市 $i$ 处大一。由此得到蕴含式 $x_{i,j}=1 \Rightarrow u_i+1\le u_j$ 。若该弧未被选用，视频明确指出：无法在 $u_i$ 与 $u_j$ 之间断言任何直接关系。

x_{i,j}=1 \implies u_i+1 \le u_j

‘若—则’条件的大M线性化

该条件关系通过引入大M项，重写为单个线性不等式： $u_i+1\le u_j+M(1-x_{i,j})$ 。当 $x_{i,j}=1$ 时，约束退化为所期望的顺序关系；当 $x_{i,j}=0$ 时，含 $M$ 的项使不等式松弛，从而不强制施加直接顺序约束。幻灯片要求 $M$ 足够大，以确保 $u_i\le M$ 。

u_i+1 \le u_j + M(1-x_{i,j})

在TSP模型中选取 $M = n$

在此TSP建模中，大M常数由问题规模确定。幻灯片推荐取 $M=n$ （即城市总数），并指出 $M=n-1$ 是更紧致的最佳估计值。但演示最终在显示的约束中仍采用 $n$ 。

M=n,\quad M_{\text{best}}=n-1

最终的MTZ风格子环路消除约束

将 $M=n$ 代入后，得到视频中展示的最终约束： $u_i+1\le u_j+n(1-x_{i,j})$ ，其中 $i,j=2,\dots,n$ 互不相同。主讲人将此表述为一种条件，该条件通过对所选弧强制施加递增的序数值，自动消除子环路。该片段给出了结论，但因时间所限未完成完整的严格证明。

u_i+1 \le u_j+n(1-x_{i,j}) \qquad \forall i,j=2,\dots,n,\; i\ne j

MTZ子回路消除约束

用于防止旅行商问题中出现断开回路的核心整数规划约束。它借助辅助变量 $u_i$ ，对所访问城市施加严格的顺序约束，从而确保仅存在一条合法回路。

u_i + 1 \le u_j + n(1 - x_{i,j}) \quad \forall i, j = 2, \dots, n, \quad i \neq j

旅行商问题中的大M松弛

一种建模技巧：用一个大常数 $M$ （此处估计为 $n$ ）乘以二元变量 $(1 - x_{i,j})$ 的补。该方法依据某条特定边是否被纳入回路，动态启用或停用顺序约束。

起始城市的排除

子环约束严格定义在索引 $i, j \ge 2$ 上。城市1被有意地从 $u$ -变量排序中省略，以作为不受约束的配送中心，这对模型逻辑上的有效性至关重要。

合法路径的可行性

当边构成单一哈密顿环时，活跃约束形成一个有向无环不等式图。这使得可以通过一致的逆向代入法，为所有 $u$ 变量求得有效的整数界，如5-城市示例所示。

子环构型的不可行性

若所选边构成一个不包含起始城市的闭合环路，则约束将生成一条严格的循环不等式链（例如： $u_a < u_b < u_c < u_a$ ）。这一数学矛盾证明子环无法产生可行解。

子环路消除约束

公式化模型中的关键新约束是2 is $u_i+1\le u_j+n(1-x_{i,j})$ 对所有 $i,j=2,\ldots,n$ 且满足 $i\neq j$ 。若选中弧 $(i,j)$ ，则 $x_{i,j}=1$ ，且该约束变为 $u_i+1\le u_j$ ，从而强制该弧上节点的严格顺序。若该弧未被选中，则项 $n$ 使该不等式松弛，从而不对该节点对施加限制。

u_i+1\le u_j+n(1-x_{i,j})\quad \forall i,j=2,\ldots,n,\quad i\neq j

为何子环路不可行

已求解的5节点示例中，先赋值 $u_3=3$ ，再赋值 $u_4=2$ ，从而迫使 $u_5=1$ 来自 $u_5+1\le u_4$ 、 $u_2=0$ 来自 $u_2+1\le u_5$ 。但剩余不等式 $u_4+1\le u_2$ 迫使 $u_2=3$ ，与 $u_2=0$ 矛盾。因此，节点 $2,\ldots,n$ 之间的闭合子环路无法满足顺序约束。

u_4=2,\ u_5=1,\ u_2=0,\ \text{but also }u_2=3

完整模型——2

完整模型在以下约束下最小化 $\sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}$ ：每个节点恰有一条入弧和一条出弧；弧变量为二元变量；满足子环消除不等式；辅助变量 $u_i$ 对 $i=2,\ldots,n$ 非负。主讲人将此称为旅行商问题（TSP）的整体“模型二”。

\min \sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}

模型2中的度数约束

该模型保留了指派式度数约束： $\sum_{\substack{i=1\\ i\neq j}}^{n} x_{i,j}=1$ 对每个节点 $j$ ，且 $\sum_{\substack{j=1\\ j\neq i}}^{n} x_{i,j}=1$ 对每个节点 $i$ 。这些条件确保所选路线结构中每个城市恰好有一个前驱和一个后继。

\sum_{\substack{i=1\\ i\neq j}}^{n} x_{i,j}=1,\quad \sum_{\substack{j=1\\ j\neq i}}^{n} x_{i,j}=1

变量定义域

弧变量为二进制，即 $x_{i,j}\in\{0,1\}$ ；辅助顺序变量满足 $u_i\ge 0$ （对 $i=2,\ldots,n$ 成立）。这些定义域声明是子环路消除约束能作为混合整数规划形式起作用的关键组成部分。

x_{i,j}\in\{0,1\},\quad u_i\ge 0\ \ (i=2,\ldots,n)

模型2的主要优势

由于子环路通过显式不等式自动消除，该模型可直接使用CPLEX或Gurobi等标准整数规划软件，借助常规分支定界法求解。主讲人强调，无需专门为TSP构建特殊的分支定界方案。

模型2的主要劣势

新增的子环路消除系统破坏了纯粹的指派问题结构，因此匈牙利法无法用于其线性松弛问题。此外，它还额外引入约 $(n-1)^2$ 个约束，使模型规模大于模型1。

\text{Additional }(n-1)^2\text{ constraints}

课后练习

最后一页幻灯片要求观众使用例题-1和例题-2中的数据，并用Cplex求解器求解TSP的表述-2。讲师说明，本视频不实际执行该求解过程。

TSP模型-2的Cplex求解路径

开场幻灯片陈述了一项具体的计算任务：使用例题-1和例题-2中的数据，并用Cplex求解器求解TSP的模型-2。主讲人将此与分支定界法对比，表明本环节聚焦于在求解器环境中检验模型，而非手工构建枚举树。

改进TSP分支定界法的两种途径

讲座将TSP分支定界法的改进归纳为两类：更紧致的下界与更紧致的上界。核心论点是，同时提升界定过程的两侧，可大幅缩减枚举树的规模，因为更强的界能实现更有效的剪枝。

用于下界的指派问题方法

在下界方面，幻灯片明确指出，指派问题方法是用于获取更紧致界的方法。主讲人说明，该方法已在本课程幻灯片中介绍过，而另一种下界方法将在本片段之外的后续内容中引入。

求上界所用的启发式与超启发式方法

对于上界，幻灯片指出启发式或超启发式方法是获得更紧上界的常规手段。课程强调：更优的可行解会降低上界，这与更强的下界相配合，共同缩小分支定界法的搜索空间。

详细学习笔记

按知识点查看条件、步骤和证据。补充解释与视频直接内容分别标明。

符号定义 · 15

$u_i$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字：“令 $u_i$ 为一个非负变量，表示在到达城市 i 之前所访问的城市数量，其中 $i > 1$ 。”
声音
观察依据
主讲人说明： $u_i$ 是一个新增的非负变量，表示在到达城市 i 之前所访问的城市数量。

符号

$u_i$

含义

城市 i 的辅助整数型变量；表示在从城市 1 出发的旅行假设下，到达城市 i 之前所访问的城市数量。

适用范围

当 $i > 1$ 时的非负变量；后续通过约束 $u_i \le M$ 加以限制，并用于 i, $j = 2$ , …, n 的情形。

$x_{i,j}$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片要求给出 $x_{i,j}$ 、 $u_i$ 和 $u_j$ 之间的关系。
声音
观察依据
主讲人回顾：x_{ij} 是一个二元变量，若从城市 i 直接前往城市 j，则其值为 1；否则为 0。

符号

$x_{i,j}$

含义

二元弧选择变量，用于指示旅行是否直接从城市 i 行至城市 j。

适用范围

二元变量， $x_{i,j} \in {0, 1}$ 。

i

依据清楚

视频直接表达

来源依据

公式
观察依据
$u_i$ 、 $x_{i,j}$ 及最终全称量词中的下标均使用 i。
图示
观察依据
手绘图中，标有 i 的节点连接至标有 j 的节点。

符号

含义

弧 $i \to j$ 中的城市编号或起始城市。

适用范围

在最终显示的约束条件中， $i = 2$ , …, n。

j

依据清楚

视频直接表达

来源依据

公式
观察依据
下标 i,j 出现在 $x_{i,j}$ 和 $u_j$ 中，最终的量词也使用 j。
图示
观察依据
手绘节点，标有 j，并连接到标有 i 的节点。

符号

含义

弧 $i\to j$ 中的城市索引或目的城市。

适用范围

在最终显示的约束中， $j=2$ , $\dots$ ,n。

M

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片显示 $u_i+1 \le u_j + M(1-x_{i,j})$ ，并说明“其中 M 是某个很大的数，满足 $u_i \le M$ ”。
声音
观察依据
说话人指出，该“若—则”情形可用大 M 约束建模，且 M 是一个非常大的数。

待核验内容

幻灯片将 M 视为通用的大数，随后建议取 $M=n$ ；本片段未形式化证明 n 在此情形下已足够。

符号

含义

大 M 常数，用于当 $x_{i,j}=0$ 时使子回路消除不等式失效。

适用范围

一个满足 $u_i \le M$ 的足够大的数；幻灯片推荐的取值是 n。

n

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出：“M 的一个良好估计值是 n，即城市的总数”，且最终约束中 i,j 的取值范围为 2, $\dots$ ,n。
声音
观察依据
说话人称，本例中 M 的最佳取值为 n，且后续幻灯片将采用 n。

符号

含义

旅行商问题（TSP）实例中的城市总数。

适用范围

正整数；用作所选的大M值，同时也作为城市的上标索引边界。

$u_i$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字将 $u_i$ 定义为一个非负变量，表示在到达城市 i 之前所访问的城市数量，其中 $i > 1$ 。
声音
观察依据
讲话者讨论为所有 u 变量寻找可行的取值。

符号

$u_i$

含义

一个非负整数变量，表示城市 i 在巡回路线中的位置（或在到达城市 i 之前所访问的城市数量），其中 $i > 1$ 。

适用范围

i 属于集合 {2, …, n}

$x_{i,j}$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字在子回路消除约束中使用 $x_{i,j}$ ，并指出：‘若 $x_{i,j} = 1$ ，则 $u_i + 1 \le u_j$ ’。

符号

$x_{i,j}$

含义

一个二元决策变量，用于指示从城市 i 到城市 j 的边是否被包含在巡回路线中。

适用范围

i, j ∈ {2, …, n}，且 $i \ne j$

n

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字指出：‘M 的一个良好估计值是 n，即城市的总数。’
声音
观察依据
讲话者提到的取值范围是从 2 到 n。

符号

含义

旅行商问题实例中城市的总数。

适用范围

n ∈ ℤ⁺，且 $n \ge 2$

M

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字提到：‘M 的一个良好估计值是 n’，以及‘M 的最佳估计值是 ( $n - 1$ )’。
图示
观察依据
图示幻灯片上的标注指向约束条件，分别标有“大M部分消失之处”和“大M部分出现之处”。

符号

含义

大M法中使用的一个很大的常数，用于在二元变量为零时松弛约束。

适用范围

M 是正整数

$x_{i,j}$

依据清楚

视频直接表达

来源依据

公式
观察依据
在标题为“TSP：建模-2”的幻灯片中，变量 $x_{i,j}$ 出现在目标函数 $\sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}$ 中、两个度数约束中、二元声明 $x_{i,j}\in$ \{0,1\} 中，以及通过项 $n(1-x_{i,j})$ 出现在打破子回路的约束中。

符号

$x_{i,j}$

含义

表示从节点 i 到节点 j 的有向弧是否被选中的二元路径选择变量。

适用范围

$x_{i,j} \in {0, 1}$ ，对所有 $i = 1$ , …, n

$d_{i,j}$

依据清楚

视频直接表达

来源依据

公式
观察依据
建模幻灯片上的目标函数写作 $\sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}$ 。

待核验内容

本视频片段未明确定义 $d_{i,j}$ ；其含义需根据标准旅行商问题（TSP）记号及其作为 $x_{i,j}$ 系数的用法推断。

符号

$d_{i,j}$

含义

与从节点 i 行进至节点 j 相关联的成本或距离系数。

适用范围

下标取值范围为 i, $j=1$ , $\ldots$ ,n

知识点 · 22

第二种旅行商问题模型的目标

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人介绍了旅行商问题的另一种建模方式，其核心思想是自动消除所有子回路。
图示
观察依据
标题页显示“旅行商问题”；提纲页列出精确方法，包含模型-1与模型-2。

定义

解释

本片段介绍旅行商问题的第二种整数规划模型。该模型旨在构建一个能自动消除子回路的模型，而非仅依赖显式的子回路消除约束。

公式

适用条件

适用于旅行商问题。
该模型旨在自动防止子回路产生。

用于表示城市顺序的辅助变量 $u_i$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字将 $u_i$ 定义为一个非负变量，表示在到达城市i之前已访问的城市数量，其中 $i>1$ ，且假设旅程从城市1出发。
声音
观察依据
主讲人强调：旅程从城市1出发是一个关键假设，它直接影响子回路消除约束的构造。

定义

解释

该模型为每个城市 $i>1$ 引入辅助变量 $u_i$ ，该变量记录在到达城市i之前已访问的城市数量，从而编码了城市在回路中的位置或顺序。该定义依赖于将城市1固定为起始城市。

公式

u_i \ge 0,\quad i>1

适用条件

为城市 $i>1$ 而定义。
假设旅行从城市1出发。
$u_i$ 是非负的。

先修条目

第二种旅行商问题模型的目标

二元弧变量 $x_{i,j}$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片要求给出 $x_{i,j}$ 、 $u_i$ 和 $u_j$ 之间的关系。
声音
观察依据
主讲人回顾 x_{ij} 是二元变量，当从城市 i 访问城市 j 时等于1，否则等于0。

定义

解释

主讲人回顾标准旅行商问题（TSP）中的弧变量 $x_{i,j}$ ：它是一个二元变量，用于指示所选旅行路线是否包含从城市 i 到城市 j 的有向移动。新模型将该弧变量与辅助顺序变量 $u_i$ 和 $u_j$ 关联起来。

公式

x_{i,j} \in \{0,1\},\quad x_{i,j}=1 \text{ if the tour goes from city } i \text{ to city } j

适用条件

$x_{i,j}$ 是二元变量。
$x_{i,j}=1$ 表示使用了从 i 到 j 的有向弧。
$x_{i,j}=0$ 表示未使用该直接弧。

先修条目

第二种旅行商问题模型的目标

由弧诱导的条件序关系

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出：若 $x_{i,j}=1$ ，则 $u_i+1 \le u_j$ 。
图示
观察依据
手绘节点 i 和 j 由一条蓝色线连接，此时主讲人正在讨论从城市 i 前往城市 j。
声音
观察依据
主讲人指出：若我们从城市 i 前往城市 j，则 $u_j$ 应大于或等于 $u_i$ 加一；若我们不直接前往，则无法确定二者之间的关系。

方法

解释

该推导明确了打破子回路所需的逻辑关系：若回路中使用了从节点一指向节点二的弧，则节点二的顺序值至少要比节点一的顺序值大一；若该弧未被使用，则模型不应强制要求 u 一与 u 二之间存在任何直接关系。

公式

x_{i,j}=1 \implies u_i+1 \le u_j

适用条件

适用于考虑从城市 i 到城市 j 的一条可能有向弧时。
该蕴含式仅在 $x_{i,j}=1$ 时激活。
当 $x_{i,j}=0$ 时，不声明 $u_i$ 与 $u_j$ 之间的任何直接关系。

先修条目

用于表示城市顺序的辅助变量 $u_i$
二元弧变量 $x_{i,j}$

条件关系的大 M 线性化

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出：上述情形可建模为 $u_i+1 \le u_j + M(1-x_{i,j})$ ，其中 M 是某个足够大的数，且满足 $u_i \le M$ 。
声音
观察依据
主讲人称这是经典的‘若—则’情形，可用大 M 约束进行建模。

公式

解释

该条件语句通过一个含大 M 项的线性不等式实现转化，其中大 M 项乘以 $1-x_{i,j}$ 。当 $x_{i,j}=1$ 时，M 项消失，序约束被强制执行；当 $x_{i,j}=0$ 时，只要 M 足够大，所增加的 M 项将使该不等式失去约束力。

公式

u_i+1 \le u_j + M(1-x_{i,j})

适用条件

M 必须足够大。
幻灯片指出要求 $u_i \le M$ 。
$x_{i,j}$ 是二元变量。

先修条目

由弧诱导的条件序关系
M

为旅行商问题（TSP）的子环消除选择大-M 常数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片提问 M 的合理估计值可能是什么，并回答：一个合理的估计值是 n，即城市的总数；事实上，最优估计值是 ( $n-1$ )。
声音
观察依据
主讲人指出，此时 M 的最优取值为 n；虽然最优估计值可能是 n 减一，但幻灯片中将采用 n。

待核验内容

视频区分了合理的估计值 n 与最优估计值 $n-1$ ，但本片段未给出 $n-1$ 具有最优性的证明。

方法

解释

在此模型中，大-M 常数依据城市数量选取。幻灯片推荐取 $M = n$ ，因为共有 n 座城市；同时指出 $M = n-1$ 是更紧致的最优估计值。演示后续采用 $M = n$ 。

公式

M=n \quad \text{(used in the slides)},\qquad M_{\text{best}}=n-1

适用条件

n 表示城市的总数。
M 必须满足对 u 变量的上界约束要求。
本片段在最终展示的约束中使用了 n，而非 $n-1$ 。

先修条目

条件关系的大 M 线性化
n
M

MTZ 风格的子环消除约束

依据清楚

视频直接表达

来源依据

公式
观察依据
最终幻灯片文字：因此，以下条件将自动消除子环： $u_i+1 \le u_j+n(1-x_{i,j})$ ，对所有 i, $j=2$ ,…,n 且 $i\ne j$ 成立。
声音
观察依据
主讲人总结道，这是基于“若…则…”逻辑构建的子环规避约束。

待核验内容

本片段展示了该约束，但未完成形式化证明以说明它能消除所有子环。

公式

解释

将 $M = n$ 代入大-M不等式，得到视频中展示的最终破除子回路约束。该约束针对城市 2 至 n 中所有互异城市的有序对 i 和 j 施加。该约束强制已使用的弧上的 u 值递增，从而防止出现不含固定起点城市 1 的闭合子回路。

公式

u_i+1 \le u_j+n(1-x_{i,j}) \qquad \forall i,j=2,\dots,n,\; i\ne j

适用条件

对所有满足 i, $j = 2$ , $\dots$ ,n 且 $i \ne j$ 的 i,j 施加。
使用 $M = n$ 。
假设旅行从城市 1 出发。
$u_i$ 是非负序变量。
$x_{i,j}$ 是二元弧变量。

先修条目

用于表示城市顺序的辅助变量 $u_i$
二元弧变量 $x_{i,j}$
条件关系的大 M 线性化
为旅行商问题（TSP）的子环消除选择大-M 常数

子回路消除约束公式

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片显示公式： $u_i + 1 \le u_j + n(1 - x_{i,j}) \quad \forall i$ , $j = 2$ , $\dots$ , n, $\quad i \neq j$ 。
声音
观察依据
讲解者说明，该条件适用于所有不等于1的i、j，以避开起始城市。

公式

解释

该整数规划约束确保：若从城市i到城市j的边被选中（ $x_{i,j} = 1$ ），则城市j在回路中的位置必须严格大于城市i的位置（ $u_i + 1 \le u_j$ ）；若该边未被选中（ $x_{i,j} = 0$ ），则项 $n(1 - x_{i,j})$ 变为n，其值足够大（即大M），使得该不等式恒成立，从而松弛该约束。

公式

u_i + 1 \le u_j + n(1 - x_{i,j}) \quad \forall i, j = 2, \dots, n, \quad i \neq j

适用条件

适用于所有满足 $i \ne j$ 、且i与j均从2到n的城市对。
假设回路起始并终止于城市1。

先修条目

$u_i$
$x_{i,j}$
n

旅行商问题建模中的大M法

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字：“M的一个良好估计值是城市总数n（事实上，M的最佳估计值为( $n-1$ )）。”
图示
观察依据
标注明确指出‘大M部分’会根据 $x_{i,j}$ 的取值而出现或消失。

定义

解释

大-M法用于在整数规划中条件性地强制实施约束。在此旅行商问题（TSP）模型中，项 $n(1 - x_{i,j})$ 充当大-M成分。当 $x_{i,j} = 1$ 时，该项为 0，从而强制执行严格序约束 $u_i + 1 \le u_j$ ；当 $x_{i,j} = 0$ 时，该项变为 n，其值足够大，可确保无论 $u_i$ 与 $u_j$ 取何值，该不等式均成立，从而对该特定边实际禁用该约束。

适用条件

M 必须选得足够大，以保证当二元变量为 0 时，该约束恒成立。
在此特定模型中，M 被估计为 n，即城市的总数。

先修条目

M
$x_{i,j}$

子回路消除约束

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片标题：“TSP：子回路消除约束”。
公式
观察依据
显示的约束为： $u_i+1\le u_j+n(1-x_{i,j})\quad \forall i$ , $j=2$ , $\ldots$ ,n, $\quad i\neq j$ 。
声音
观察依据
讲师称其为“子回路规避约束”或“子回路消除约束”。

公式

解释

该约束使用辅助排序变量 $u_i$ 来确保所选弧上的顺序一致。若弧 (i,j) 被选中，则 $x_{i,j}=1$ ，此时不等式简化为 $u_i+1\le u_j$ ，强制后继节点的 u 值严格更大；若该弧未被选中，则 $x_{i,j}=0$ ，此时较大的加性项 n 使得该不等式自动成立，因此对该节点对不施加任何实质性限制。

公式

u_i+1\le u_j+n(1-x_{i,j})\quad \forall i,j=2,\ldots,n,\quad i\neq j

适用条件

适用于所有满足 i, $j\in$ \{2, $\ldots$ ,n\} 且 $i\neq j$ 的有序对 i,j。
$x_{i,j}$ 是二元变量。
$u_i$ 对于 $i=2$ , $\ldots$ ,n 是非负的。

先修条目

$u_i$
$x_{i,j}$
n

模型-2的目标函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片“TSP：模型-2”显示目标函数为： $\sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}$ 。
声音
观察依据
讲师说：“这就是整体模型。我们称其为模型二。”

公式

解释

优化目标是使所有选定有向弧的总旅行成本最小化。讲师指出，该目标与模型-1相似。

公式

\min \sum_{i=1}^{n}\sum_{j=1}^{n} d_{i,j}x_{i,j}

适用条件

求和遍历所有节点对 i, $j=1$ , $\ldots$ ,n。

先修条目

$x_{i,j}$
$d_{i,j}$

入度约束

依据清楚

视频直接表达

来源依据

公式
观察依据
模型幻灯片列出： $\sum_{i=1,\ i\neq j}^{n} x_{i,j}=1\quad \forall j=1$ , $\ldots$ ,n。
声音
观察依据
讲师指出，部分约束与模型一相似。

公式

解释

每个节点 j 必须恰好有一条来自其他某个节点 i 的被选中的入弧。这是在公式2中保留下来的分配型度数约束之一。

公式

\sum_{\substack{i=1\\ i\neq j}}^{n} x_{i,j}=1\quad \forall j=1,\ldots,n

适用条件

对每个节点 $j=1$ ,…,n 均成立。
通过要求 $i\ne j$ 排除了自环。

先修条目

$x_{i,j}$

定理与条件 · 9

固定起点城市假设

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片括号内文字：“假设旅行从城市 1 出发”。
声音
观察依据
主讲人称这是一个非常关键的假设，并指出它会影响破除子回路约束的形式。

待核验内容

该片段强调了该假设的重要性，但并未展示更换起点城市会导致模型失效的反例。

命题

破除子回路的建模假设旅行从城市 1 出发；该假设对于定义序变量 $u_i$ 及确保所得约束有效至关重要。

前提

旅行商问题（TSP）的回路用有向弧变量 $x_{i,j}$ 表示。
顺序变量 $u_i$ 针对 $i > 1$ 定义，以起始城市为参考。

量词

适用于以特定起始城市 1 编号的城市所呈现的模型。

弧的使用意味着顺序变量的增加

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片要点：若 $x_{i,j} = 1$ ，则 $u_i + 1 \le u_j$ 。
声音
观察依据
讲述者指出：当从城市 i 前往城市 j 时， $u_j$ 应大于或等于 $u_i$ 加一。

命题

若旅行路线直接从城市 i 到城市 j，则 j 处的顺序变量至少比 i 处的顺序变量大一。

前提

$x_{i,j}$ 是表示从城市 i 到城市 j 是否通行的二元变量。
$u_i$ 和 $u_j$ 分别表示到达城市 i 和城市 j 之前已访问的城市数量。

量词

对于一对被考虑的城市 i 和 j，且满足 $x_{i,j} = 1$ 。

未使用的弧不施加任何直接的顺序关系

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片要点：若 $x_{i,j} = 0$ ，则我们无法在 $u_i$ 和 $u_j$ 之间得出任何直接关系。
声音
观察依据
讲述者指出：若我们不直接从城市 i 前往城市 j，则无法确定 $u_i$ 与 $u_j$ 之间的关系。

命题

若 $x_{i,j}=0$ ，该模型并未断言 $u_i$ 与 $u_j$ 之间存在任何直接关系。

前提

$x_{i,j}$ 是二元变量。
唯一被断言的直接关系来自 $x_{i,j}=1$ 的情形。

量词

对于一对被考虑的城市 i 和 j，且满足 $x_{i,j}=0$ 。

最终约束自动消除子回路。

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片显示：因此，以下条件将自动消除子回路： $u_i+1 \le u_j+n(1-x_{i,j})$ ，对所有 i, $j=2$ , $\dots$ ,n 且 $i\ne j$ 成立。
声音
观察依据
主讲人称其为基于‘若—则’语句构建的避免子回路约束。

待核验内容

该片段断言了该约束的消除子回路效果，但因时长所限，并未包含完整的严格证明。

命题

约束 $u_i+1 \le u_j+n(1-x_{i,j})$ （对所有互异的 i, $j=2$ , $\dots$ ,n）在旅行商问题整数规划中被表述为可自动消除子回路。

前提

回路从城市1出发。
$u_i$ 是非负序变量，适用于 $i>1$ 的情形。
$x_{i,j}$ 是二元弧变量。
M 被选为 n。

量词

对所有 i, $j = 2$ , …, n，且 $i \ne j$ 。

任何不包含节点1的子回路都会导致 u 值不一致。

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出存在矛盾，因为 $u_2$ 将同时等于 0 和 3，并由此得出结论：在这些约束下，该子环不可行。
公式
观察依据
幻灯片展示了链式不等式： $u_4+1\le u_2$ ， $u_2+1\le u_5$ ， $u_5+1\le u_4$ ，以及指定的取值： $u_4=2$ ， $u_5=1$ ， $u_2=0$ ，还有 $u_2=3$ 。
字幕依据
观察依据
幻灯片文字：“因此，任何不包含节点-1的子回路都会导致变量 $u_i$ 的取值不一致。”

命题

若在节点2, $\ldots$ ,n 中选取一个闭合子回路，则子回路消除约束将迫使至少一个辅助变量 $u_i$ 取矛盾的值，从而使该子回路不可行。

前提

所选弧构成一个不包含节点1的子回路。
该子回路中所有弧均满足 $x_{i,j}=1$ 。
子回路消除约束 $u_i+1\le u_j+n(1-x_{i,j})$ 对所有 i, $j=2$ , $\ldots$ ,n,\ $i\neq j$ 施加。

量词

对于集合 \{2, $\ldots$ ,n\} 中任意一个不包含节点1的子回路。

模型-2可用常规整数规划求解器求解。

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师说：“因此，你可以使用 CPLEX 或 Gurobi 等商业求解器来求解旅行商问题（TSP）。也就是说，你无需专门构建一种分支定界方法来求解 TSP 问题。”
字幕依据
观察依据
优势说明指出：该模型可自动化生成，并能用常规的分支定界法求解。

命题

由于子回路会通过显式约束自动被消除，模型-2可借助标准商业求解器及常规分支定界法求解，而无需采用专用的 TSP 算法。

前提

该模型包含了子环消除约束和辅助变量 $u_i$ 。

量词

针对所呈现的完整公式-2模型。

公式-2的线性规划松弛不再是一个指派问题。

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师说：“我们失去了指派问题的结构，因此无法用匈牙利法求解该线性规划松弛问题。”
字幕依据
观察依据
缺点文字指出：“指派问题的结构遭到破坏。”

命题

在加入子环消除约束和辅助变量后，该松弛问题失去了指派问题的结构，因此无法用匈牙利法求解其线性规划松弛。

前提

我们考虑公式-2的线性规划松弛。

量词

针对完整公式的线性规划松弛。

更紧的界可减小枚举树的规模

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，通过确定更优的下界和更优的上界，可以大幅减少分支定界枚举树的规模。
字幕依据
观察依据
幻灯片标题为“旅行商问题：改进分支定界方法”，所列规则恰好对应两种改进界的方向。

命题

在旅行商问题的分支定界法中，同时改进下界和上界可大幅减小枚举树的规模。

前提

当前讨论的方法是旅行商问题的分支定界法
正在被改进的界是下界和上界

量词

关于界收紧时分支定界枚举树的一般性陈述

本讲座中标准的界改进配对

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人提到，到目前为止的幻灯片均采用指派问题方法计算下界，而上界通常借助启发式或超启发式方法获得。
字幕依据
观察依据
幻灯片列出：“下界：采用指派问题方法……”以及“上界：采用启发式或超启发式方法……”。

命题

针对本讲座所讨论的旅行商问题分支定界法，更紧的下界与指派问题方法相关联，更紧的上界与启发式或超启发式方法相关联。

前提

本视频的背景是这些幻灯片中介绍的旅行商问题（TSP）分支定界框架

量词

本讲中，约束类型与改进技术之间存在特定对应关系。

推导与证明 · 5

子回路消除约束的推导

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片逐步推进：先要求建立 $x_{i,j}$ 、 $u_i$ 、 $u_j$ 之间的关系，再引出条件不等式，接着转化为大-M 形式，然后设定 $M = n$ ，最后得到带量词的子回路消除约束。
声音
观察依据
主讲人讲解了变量回顾、if-then 逻辑、大-M 建模、M 的选取，以及最终的约束。
图示
观察依据
手绘的一条连接节点 i 与 j 的线段，示意从城市 i 直接前往城市 j 的情形。

待核验内容

推导确立了目标约束，但未完成对所有子回路均被消除的完整形式化证明。

严格证明

步骤

公式
$x_{i,j} \in \{0,1\},\quad u_i \ge 0\;(i>1)$
解释
回顾模型中所用变量： $x_{i,j}$ 表示是否使用从 i 到 j 的弧； $u_i$ 记录在抵达城市 i 之前已访问的城市数量。
步骤依据
幻灯片上展示的定义，并由主讲人加以解释。
视频直接表达
公式
$x_{i,j}=1 \implies u_i+1 \le u_j$
解释
若旅行路线直接从城市 i 到城市 j，则 j 在 i 之后到达，因此其顺序值至少比 i 大一。
步骤依据
将 $u_i$ 和 $u_j$ 解释为抵达各自城市前的访问次数后，所得出的逻辑推论。
视频直接表达
公式
$x_{i,j}=0 \implies \text{no direct relation between }u_i\text{ 且 }u_j$
解释
若从 i 到 j 的弧未被使用，则模型不应强制规定这两座城市之间的特定访问次序。
步骤依据
在幻灯片和音频中明确指出。
视频直接表达
公式
$u_i+1 \le u_j+M(1-x_{i,j})$
解释
使用一个大M项将条件语句转化为线性不等式。当 $x_{i,j}=1$ 时，项 $M(1-x_{i,j})$ 为零，排序约束起作用；当 $x_{i,j}=0$ 时，该项使该不等式松弛。
步骤依据
标准的大M线性化方法，用于处理“若—则”型约束，由主讲人指出。
视频直接表达
公式
$M=n$
解释
将大M常数选为城市的总数。幻灯片注明n-1是更紧的最优估计，但演示中采用n。
步骤依据
幻灯片建议及主讲人对M选取的解释。
视频直接表达
公式
$u_i+1 \le u_j+n(1-x_{i,j}) \qquad \forall i,j=2,\dots,n,\; i\ne j$
解释
代入 $M=n$ ，并对从2到n的所有不同城市的有序对施加该不等式，从而得到最终的消除子环路约束。
步骤依据
幻灯片上最终显示的公式。
视频直接表达

结论

视频通过编码已使用弧上城市序号所需的递增关系，并用取值为n的大M常数对条件关系进行线性化，推导出一种MTZ风格的子环路消除约束。

完整环游下可行的 u 值推导

依据清楚

视频直接表达

来源依据

图示
观察依据
图示展示了一个完整环游：1->3->2->5->4->1。所列约束为 $u_5+1$ <= $u_4$ 、 $u_4+1$ <= $u_2$ 、 $u_2+1$ <= $u_3$ ，以及 $u_2$ , $u_3$ , $u_4$ , $u_5$ <=4。
声音
观察依据
讲解者逐步推演逻辑：从节点 3 出发到达节点 1， $u_3$ 的最大可能取值为 4；接着有 $u_2$ <=3、 $u_4$ <=2、 $u_5$ <=1，从而得出 $u_5 < u_4 < u_2 < u_3$ 。

直观解释

步骤

公式
$u_3 \le 4$
解释
由于环游从节点 3 出发并最终回到节点 1（起点/终点城市），节点 3 是返回起点前访问的最后一个城市。当城市总数 $n=5$ 时，其余任一城市的最大位置编号为 4。
步骤依据
将 $u_i$ 定义为抵达城市 i 之前已访问的城市数量，并说明完整环游的结构。
视频直接表达
公式
$u_2 + 1 \le u_3 \implies u_2 \le 3$
解释
从 2 到 3 的边属于该环游（即 $x_{2,3}=1$ ），因此子环路约束在此处直接生效，无需大-M松弛。由于 $u_3$ <= 4，故 $u_2$ 至多为 3。
步骤依据
将子环路消除约束公式应用于 $x_{2,3}=1$ 的情形，并代入 $u_3$ 的上界。
视频直接表达
公式
$u_4 + 1 \le u_2 \implies u_4 \le 2$
解释
从 4 到 2 的边属于该环游（即 $x_{4,2}=1$ ）。应用该约束并利用 $u_2$ 的上界，可得 $u_4$ <= 2。
步骤依据
将子环路消除约束公式应用于 $x_{4,2}=1$ 的情形，并代入 $u_2$ 的上界。
视频直接表达
公式
$u_5 + 1 \le u_4 \implies u_5 \le 1$
解释
从5到4的边在回路中（ $x_{5,4}=1$ ）。应用该约束并代入 $u_4$ 的上界，可得 $u_5$ <= 1。
步骤依据
将子回路消除约束公式应用于 $x_{5,4}=1$ ，并代入 $u_4$ 的上界。
视频直接表达
公式
$u_5 < u_4 < u_2 < u_3$
解释
综合回路中各条边所导出的不等式，可确立这些城市的访问位置之间严格的先后顺序。
步骤依据
由 $u_i + 1$ <= $u_j$ 所隐含的严格不等式的传递性。
视频直接表达

结论

对于给定的完整回路，这些约束成功地强制u变量形成一种严格且有效的排序，从而允许可行的整数赋值，例如（ $u_2=3$ , $u_3=4$ , $u_4=2$ , $u_5=1$ ）或（ $u_2=2$ , $u_3=3$ , $u_4=1$ , $u_5=0$ ）。

子回路结构不可行性的推导

依据清楚

视频直接表达

来源依据

图示
观察依据
图中显示两个互不相交的子回路：1->3->1 和 2->5->4->2。所列约束为 $u_4+1$ <= $u_2$ 、 $u_2+1$ <= $u_5$ 、 $u_5+1$ <= $u_4$ 。
声音
观察依据
讲解者开始分析子回路结构，并指出到达城市1的节点是节点3。

待核验内容

视频在讲解者完成对2-5-4子回路矛盾推导前中断。

直观解释

步骤

公式
$u_4 + 1 \le u_2$
解释
边4->2存在于该子回路中，因此 $x_{4,2}=1$ ，大M项消失。
步骤依据
对一条激活边应用子回路消除约束。
视频直接表达
公式
$u_2 + 1 \le u_5$
解释
边2->5存在于该子回路中，因此 $x_{2,5}=1$ ，大M项消失。
步骤依据
子回路消除约束在一条活跃边上的应用。
视频直接表达
公式
$u_5 + 1 \le u_4$
解释
边 $5\to 4$ 存在于子回路中，因此 $x_{5,4}=1$ ，大M项消失。
步骤依据
子回路消除约束在一条活跃边上的应用。
视频直接表达
公式
$u_4 + 1 < u_4$
解释
将三个不等式串联可得 $u_4 + 1$ <= $u_2$ <= $u_5 - 1$ <= $u_4 - 1 + 1 = u_4$ ，化简为 $u_4 + 1$ <= $u_4$ ，这是一个数学矛盾。
步骤依据
不等式的传递性导致关于实数的不可能命题。
依据视频推导

结论

子回路消除约束对任何不包含起始城市的闭合回路，均会生成一组循环的严格不等式，从而证明此类构型在数学上不可行。

数值验证：一个子回路违反了顺序约束

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师设定 $u_3=3$ ，然后选取节点 4 并设定 $u_4=2$ ，再由所展示的不等式推导出 $u_5=1$ 和 $u_2=0$ ，最后指出另一条边给出 $u_2=3$ ，从而产生矛盾。
公式
观察依据
可见的不等式为： $u_4+1\le u_2$ ， $u_2+1\le u_5$ ， $u_5+1\le u_4$ ，且有界约束 $u_2$ , $u_3$ , $u_4$ , $u_5\le 4$ 。
图示
观察依据
该图显示了一个 2-环，其节点为 1 和 3 和一个 3-环，节点为 2，4，和 5。

待核验内容

所画出的 3-环中各弧的确切方向在图上显示得较小，但所展示的不等式识别出相关有序对为 (4,2)、(2,5) 和 (5,4)。

数值验证

步骤

公式
$u_3=3$
解释
讲师首先将最高值分配给从节点1出发、在1-3回路中到达的节点。
步骤依据
以口头陈述方式表达，并写在幻灯片上节点3旁边。
视频直接表达
公式
$u_4=2$
解释
从剩余的不连通回路中，讲师任意选取节点4，并为其分配一个小于3的可行值。
步骤依据
以口头陈述方式表达，并写在幻灯片上节点4旁边。
视频直接表达
公式
$u_5=1$
解释
利用不等式 $u_5+1\le u_4$ 以及已赋值的 $u_4=2$ ，可推出 $u_5$ 必为1。
步骤依据
由所展示的约束 $u_5+1\le u_4$ 和已赋值的 $u_4=2$ 推导得出。
视频直接表达
公式
$u_2=0$
解释
利用不等式 $u_2+1\le u_5$ 以及已赋值的 $u_5=1$ ，可推出 $u_2$ 必为0。
步骤依据
由所展示的约束 $u_2+1\le u_5$ 和已赋值的 $u_5=1$ 推导得出。
视频直接表达
公式
$u_2=3$
解释
利用不等式 $u_4+1\le u_2$ 以及已赋值的 $u_4=2$ ，可推出 $u_2$ 至少为3；而在讲师口头推演链中，此结论被直接视为 $u_2=3$ 。
步骤依据
由所展示的约束 $u_4+1\le u_2$ 和已赋值的 $u_4=2$ 推导得出。
视频直接表达
公式
$u_2=0\ \text{且}\ u_2=3$
解释
同一变量 $u_2$ 被迫取两个不同的值，这是不可能的。
步骤依据
直接比较前述两个推导出的赋值。
视频直接表达

结论

围绕子回路2-4-5所作的赋值尝试导致矛盾，因此该子回路在子回路消除约束下不可行。

为何大M项使未选弧失效

依据清楚

依据视频推导

来源依据

公式
观察依据
一般约束形式为 $u_i+1\le u_j+n(1-x_{i,j})$ 。
公式
观察依据
二元声明 $x_{i,j}\in$ \{0,1\} 显示在模型表述幻灯片上。

直观解释

步骤

公式
$x_{i,j}=1\Rightarrow u_i+1\le u_j+n(1-1)=u_j$
解释
当弧(i,j)被选中时，大M项消失，约束退化为从i到j的序关系要求。
步骤依据
将 $x_{i,j}\in$ \{0,1\} 代入所展示的子回路消除约束。
依据视频推导
公式
$x_{i,j}=0\Rightarrow u_i+1\le u_j+n$
解释
当弧(i,j)未被选中时，右侧增加n，使得该不等式在所示示例规模下变为非紧约束。
步骤依据
将 $x_{i,j}\in$ \{0,1\} 代入所展示的子回路消除约束。
依据视频推导
公式
$\text{cycle of active arcs} \Rightarrow u_{a_1}+1\le u_{a_2},\ldots,u_{a_k}+1\le u_{a_1}$
解释
若某循环中所有弧均处于激活状态，则沿该循环串联简化后的不等式，将迫使u值严格递增，并最终回到起始节点。
步骤依据
沿一个闭合有向循环串联激活弧对应的不等式。
依据视频推导
公式
$u_{a_1}>u_{a_1}$
解释
沿循环串联后将导致矛盾，因此完全激活的子回路无法满足这些约束。
步骤依据
大于关系（>）的传递性应用于链式不等式。
依据视频推导

结论

该约束强制在选定的弧上形成严格序关系；若存在一个闭合的选定环路，则会导致某个变量严格大于自身，这是不可能的。

例题详解 · 5

完整回路的验证

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片展示了一个含5个节点的图，其中存在哈密顿回路1-3-2-5-4-1，并列出了对应的活跃约束。
声音
观察依据
主讲人说：‘我们以一个完整回路为例……’，并逐步演示如何为 u 变量寻找可行值。

题目

验证当所选边构成一条覆盖所有城市的单一有效回路时，子回路消除约束是否允许 u 变量存在可行的整数解。

已知条件

城市数量 $n = 5$ 。
回路中的边：(1,3), (3,2), (2,5), (5,4), (4,1)。
约束条件适用于 i, $j \ge 2$ 。

目标

找出一组满足所有活跃约束和边界条件的 $u_2$ 、 $u_3$ 、 $u_4$ 、 $u_5$ 的可行取值。

步骤

公式
$u_5 + 1 \le u_4, \quad u_4 + 1 \le u_2, \quad u_2 + 1 \le u_3$
解释
识别子集 {2,3,4,5} 内各城市之间边所对应的活跃约束。
步骤依据
边 (5,4)、(4,2) 和 (2,3) 满足 $x_{i,j} = 1$ ，使一般约束简化为 $u_i + 1 \le u_j$ 。
视频直接表达
公式
$u_2, u_3, u_4, u_5 \le 4$
解释
应用 u 变量的上界约束。
步骤依据
由于共有 5 座城市，且城市 1 为起点/终点，因此在到达任一其他城市前最多可访问 4 座城市。
视频直接表达
公式
$u_2 = 3, u_3 = 4, u_4 = 2, u_5 = 1$
解释
给出一组整数值的有效赋值。
步骤依据
代入这些值后，满足 $1+1\le 2$ 、 $2+1\le 3$ 、 $3+1\le 4$ ，且所有结果均 ≤4。
视频直接表达
公式
$u_2 = 2, u_3 = 3, u_4 = 1, u_5 = 0$
解释
再给出另一组整数值的有效赋值。
步骤依据
代入这些值后，满足 $0+1\le 1$ 、 $1+1\le 2$ 、 $2+1\le 3$ ，且所有结果均 ≤4。
视频直接表达

结果

存在可行解，例如 ( $u_2=3$ , $u_3=4$ , $u_4=2$ , $u_5=1$ ) 或 ( $u_2=2$ , $u_3=3$ , $u_4=1$ , $u_5=0$ )，这表明约束条件并未排除有效的完整环游路线。

检验

所提供的两组取值均严格满足所列所有不等式及上界约束。

利用子回路构型进行验证

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片展示了一个含5个节点的图，其中包含两个互不相交的环：1-3-1和2-5-4-2，并标出了第二个环所对应的活跃约束。
声音
观察依据
主讲人说：“现在我们来看另一个例子，其中不存在完整回路……”，随后开始分析子回路。

待核验内容

视频在主讲人明确指出矛盾之前就结束了，但其设定已明显暗示了矛盾的存在。

题目

当所选边构成若干互不相交的子回路，而非一条有效的单一回路时，分析u变量的可行性。

已知条件

$n = 5$ 座城市。
子回路的边为：(1,3)、(3,1)以及(2,5)、(5,4)、(4,2)。
约束条件适用于i, $j \ge 2$ 。

目标

判断对于该构型，是否存在一组可行的 $u_2$ 、 $u_3$ 、 $u_4$ 、 $u_5$ 取值。

步骤

公式
$u_4 + 1 \le u_2, \quad u_2 + 1 \le u_5, \quad u_5 + 1 \le u_4$
解释
识别城市集合{2,4,5}中构成子回路的边所对应的活跃约束。
步骤依据
边(4,2)、(2,5)和(5,4)满足 $x_{i,j}=1$ ，从而使一般约束简化为 $u_i + 1 \le u_j$ 。
视频直接表达
公式
$u_4 + 1 < u_4$
解释
将这些不等式串联起来，推导出矛盾。
步骤依据
将三个不等式相加，得到 $u_4 + u_2 + u_5 + 3$ <= $u_2 + u_5 + u_4$ ，化简为 3 <= 0；等价地，依据严格序关系 $u_4 < u_2 < u_5 < u_4$ 。
依据视频推导

结果

不存在可行解，因为约束条件强制形成一个严格循环序（ $u_4 < u_2 < u_5 < u_4$ ），这在数学上构成矛盾。

检验

所推导出的矛盾证明：任何不包含起始城市的闭合回路均违反子回路消除约束。

对一个含子环路的5节点旅行商问题（TSP）进行逐步验证

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片显示节点1和3构成一个环路，节点2、4和5构成另一个环路。
公式
观察依据
所展示的不等式为 $u_4+1\le u_2$ , $u_2+1\le u_5$ , $u_5+1\le u_4$ ，且 $u_2$ , $u_3$ , $u_4$ , $u_5\le 4$ 。
声音
观察依据
讲师叙述了赋值过程，并指出矛盾源于子环路。

待核验内容

在3-环路中，每个箭头的精确绘图朝向在屏幕上较小，但代数不等式标识了解释中所用的有序对。

题目

给定一个候选解，其中节点2、4和5构成子环路，请验证子环路消除约束是否允许对 u 值进行一致赋值。

已知条件

选定的弧包含节点2、4和5之间的环路。
所展示的相关约束为 $u_4+1\le u_2$ , $u_2+1\le u_5$ , $u_5+1\le u_4$ 。
所展示的界为 $u_2$ , $u_3$ , $u_4$ , $u_5\le 4$ 。
讲师先赋值 $u_3=3$ ，再赋值 $u_4=2$ 。

目标

判断该子回路是否满足所有显示的约束条件。

步骤

公式
$u_4=2$
解释
从断开的回路中任意选择节点4，并赋予其一个小于3的可行值。
步骤依据
由主讲人陈述并写在幻灯片上。
视频直接表达
公式
$u_5=1$
解释
由 $u_5+1\le u_4$ 和 $u_4=2$ ，推出 $u_5=1$ 。
步骤依据
代入所显示的不等式。
视频直接表达
公式
$u_2=0$
解释
由 $u_2+1\le u_5$ 和 $u_5=1$ ，推出 $u_2=0$ 。
步骤依据
代入所显示的不等式。
视频直接表达
公式
$u_2=3$
解释
由 $u_4+1\le u_2$ 和 $u_4=2$ ，主讲人得出矛盾的要求 $u_2=3$ 。
步骤依据
如视频口述所示，代入所显示的不等式。
视频直接表达
公式
$\text{Contradiction}$
解释
同一变量 $u_2$ 被迫同时等于0和3，这是不可能的。
步骤依据
两个推导出的数值之间直接矛盾。
视频直接表达

结果

节点2、4和5构成的子回路在子回路消除约束下不可行。

检验

矛盾式 $u_2=0$ 与 $u_2=3$ 表明问题不可行；幻灯片还指出，任何不包含节点1的子回路都会导致某些 $u_i$ 的取值不一致。

片段末尾的练习提示

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
幻灯片标题：“TSP：模型构建—2检验”
字幕依据
观察依据
题目文字：“Q. 利用例题-1和例题-2中的数据，使用 CPLEX 求解器求解 TSP 的模型构建-2。”
声音
观察依据
讲师说：“本视频中，我们不会求解旅行商问题（TSP）。”

待核验内容

本片段未展示例题-1和例题-2中所引用的数据。

题目

利用例题-1和例题-2中的数据，使用 CPLEX 求解器求解 TSP 的模型构建-2。

已知条件

将要使用的模型是模型构建-2。
幻灯片上标明的求解器为 CPLEX。
所需输入数据来自本片段之外的例题-1和例题-2。

目标

使用商业求解器，求解引入新模型后的 TSP 实例。

步骤

公式
$\text{No solution steps shown in this clip}$
解释
本片段仅呈现练习提示，并说明此处不进行求解。
步骤依据
可见的问题幻灯片，加上讲师的结束语。
视频直接表达

结果

本片段中未提供数值答案。

检验

幻灯片明确将该任务表述为一项需使用 CPLEX 完成的测试练习，且讲师说明本视频不会求解旅行商问题（TSP）。

用Cplex测试模型-2

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
幻灯片文字给出的任务是：“使用例-1和例-2中的数据，并用Cplex求解器求解TSP的模型-2。”
声音
观察依据
主讲人表示，接下来将演示如何使用Cplex求解器来求解TSP问题。

待核验内容

本片段中未展示任何数值实例数据、模型方程或求解器输出。

题目

使用例-1和例-2中的数据，借助Cplex求解器求解TSP的模型-2。

已知条件

例-1中的数据
例-2中的数据
TSP的模型-2
Cplex求解器

目标

验证TSP模型可借助Cplex进行计算求解，而无需依赖人工分支定界法。

步骤

公式
解释
明确计算路径：幻灯片要求使用 CPLEX 求解旅行商问题（TSP）的建模-2。
步骤依据
幻灯片上直接陈述，并由主讲人的开场介绍加以强调。
视频直接表达
公式
解释
使用此前介绍的例题-1和例题-2数据作为基于求解器测试的输入实例。
步骤依据
幻灯片明确指出这些例题为数据来源。
视频直接表达

结果

视频片段说明了任务，但未展示求解结果。

检验

本片段中未呈现任何验证过程；仅可见问题陈述与预期方法。

图示与动画 · 10

标题与章节提纲

依据清楚

视频直接表达

来源依据

图示
观察依据
标题幻灯片显示“旅行商问题”，日期为31月2020日。
图示
观察依据
提纲幻灯片列出了“关于TSP”、“精确方法（含公式-1与公式-2）”、“启发式方法”以及“结论”。

图中对象

标题幻灯片
章节概览幻灯片
建模方法—2要点

变化过程

演示文稿从标题幻灯片过渡到章节概览。
概览在“精确方法”下标出“建模方法—2”。

不变量

主题仍是旅行商问题。
该片段被设定为一整套讲座序列中的组成部分。

数学含义

开场视觉内容表明，本片段是讲座某一部分的起始，该部分旨在介绍旅行商问题的第二种精确建模方法，其核心在于自动消除子回路。

$u_i$ 的定义幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片标题为“旅行商问题：子回路消除约束”。
公式
观察依据
红色高亮文字将 $u_i$ 定义为在抵达城市 i 之前已访问的城市数量，其中 $i > 1$ ，且假设旅程从城市 1 出发。

图中对象

$u_i$ 的定义文字
红色强调
幻灯片标题

变化过程

本幻灯片引入辅助变量 $u_i$ 。
关于在到达城市 i 之前所访问的城市数量的表述被视觉突出显示。

不变量

目标仍是构建一个能自动消除子回路的整数规划模型。
城市1被固定为假定的起始城市。

数学含义

视觉强调表明 $u_i$ 是该模型区别于普通弧变量旅行商问题模型的关键新成分。

手绘的从 i 到 j 的弧线示意图

依据清楚

视频直接表达

来源依据

图示
观察依据
两个手绘的红色圆圈，分别标有 i 和 j，并由一条蓝色线段连接。
公式
观察依据
项目符号列出：若 $x_{i,j}=1$ ，则 $u_i+1 \le u_j$ ；若 $x_{i,j}=0$ ，则 $u_i$ 与 $u_j$ 之间无法建立直接关系。

待核验内容

图示中蓝色线段看似无向，但口述内容与符号上下文均将从城市 i 到城市 j 的行程视为有向。

图中对象

节点 i
节点 j
蓝色连接线
条件性项目符号

变化过程

当讲解者讨论从城市 i 移动到城市 j 时，该图示随之出现。
幻灯片补充了两种情形： $x_{i,j}=1$ 和 $x_{i,j}=0$ 。

不变量

标签 i 和 j 代表城市。
正在解释的关系涉及弧的使用与顺序变量。

数学含义

该草图支持直观推导：若使用从 i 到 j 的移动，则强制 j 在旅行顺序中出现在 i 之后；若不使用该移动，则不产生直接的顺序约束。

从大 M 法到最终子回路消除约束的演进过程

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片依次显示 $u_i+1 \le u_j+M(1-x_{i,j})$ ，然后令 $M=n$ ，最终得到约束式 $u_i+1 \le u_j+n(1-x_{i,j})$ ，其中对所有 i, $j=2$ , $\dots$ ,n 且 $i\ne j$ 成立。

图中对象

通用的大 M 不等式
大 M 估计说明文字
最终的量化不等式

变化过程

条件关系被替换为一个含大M的单一线性不等式。
M估计为n，而n减1被指出是更紧的估计。
最终约束以全称量词形式给出，其中i、j取遍2, $\dots$ ,n且 $i\ne j$ 。

不变量

$x_{i,j}$ 仍为二进制变量。
$u_i$ 仍为城市 $i>1$ 的顺序变量。
从城市1出发构成环游的假设仍然有效。

数学含义

图示序列展示了标准建模模式：识别一个“若-则”逻辑条件，用大M法将其线性化，选取与问题相关的M值，并写出由此导出的一族约束。

完整回路图与约束条件的构建

依据清楚

视频直接表达

来源依据

动画
观察依据
节点 1 至 5 依次排列，随后由有向边构成一条哈密顿回路；图旁同步显示列出约束条件与边界值的文字框。
动画
观察依据
在各节点上叠加以具体数值表示的 $u_2$ 、 $u_3$ 、 $u_4$ 、 $u_5$ ，用以演示可行解。

图中对象

节点 1、2、3、4、5
构成回路的有向边
约束条件文字框
变量取值叠层标注

变化过程

节点与边被绘制为一条完整回路。
约束不等式根据当前激活的边逐一列出。
u 变量的可行整数值显示在各个节点上。

不变量

底层图结构仍保持为一个5个节点的完全图表示。
子回路约束的一般形式在幻灯片顶部保持不变。

数学含义

视觉演进过程将抽象的代数约束直接映射到回路的几何结构上，展示选择特定边如何激活特定不等式，从而对 u 变量施加约束。

子回路图的构建与矛盾约束的生成

依据清楚

视频直接表达

来源依据

动画
观察依据
前一张图清空，新绘制的边构成两个互不连通的独立回路：一个在节点1与3之间，另一个在节点2、4与5之间。
动画
观察依据
一组新的约束文本框出现，仅反映{2,4,5}子回路内部的边。

图中对象

节点1、2、3、4、5
构成两个互不相交回路的有向边
约束文本框

变化过程

重新绘制边，以表示一个包含多个子回路的断裂回路。
活跃约束列表随之更新，以反映新选择的边。

不变量

节点位置保持固定。
通用子回路约束公式始终显示在顶部。

数学含义

视觉上的偏移突显了：当选定的边发生变化时，不等式系统也随之改变，从而在 u 变量之间形成循环依赖，最终导致不可行性。

用于子环验证的含两个互不相交环的图

依据清楚

视频直接表达

来源依据

图示
观察依据
展示了一个含五个带编号圆形节点的图；节点1和3构成一个小环，节点2、4和5构成另一个环。
动画
观察依据
绿色指针在节点与边之间移动，同时讲师赋值并高亮显示相关不等式。

待核验内容

在当前缩放比例下，3-环中每条箭头的确切指向难以辨认，但所显示的不等式标识了论证中使用的有序对。

图中对象

五个带编号的节点
构成 2-环的有向边，节点为 1 和 3
构成 3-环的有向边，节点为 2，4，且5
绿色指针
显示的不等式： $u_4+1\le u_2$ , $u_2+1\le u_5$ , $u_5+1\le u_4$
约束 $u_2$ , $u_3$ , $u_4$ , $u_5 \le 4$

变化过程

指针首先指向节点3，此时讨论 $u_3 = 3$ 。
随后指针移至节点4，此时为 $u_4 = 2$ 赋值。
接着指针依次移至节点5和节点2，以逐项评估该不等式链。
出现矛盾标签 $u_2 = 3$ ，与先前推导出的 $u_2 = 0$ 并存。

不变量

在整个验证环节中，底层图结构保持不变。
屏幕上始终显示该子回路消除族及三条具体不等式。

数学含义

可视化演示表明：在闭合子回路周围赋值序变量，将导致取值冲突，从而证明该子回路无法满足约束条件。

从局部验证过渡到完整模型构建幻灯片

依据清楚

视频直接表达

来源依据

动画
观察依据
约在85秒时，幻灯片标题由“TSP：子回路消除约束”切换为“TSP：模型构建-2”。
字幕依据
观察依据
新幻灯片列出了完整的最小化模型，并随后在底部展开说明其优缺点。

图中对象

标题栏显示“TSP：模型构建-2”
目标函数
两个度数约束
子环消除约束
二元性声明
非负性声明
优势说明文字
劣势说明文字

变化过程

视图从基于图的验证示例切换为完整的代数形式表述。
底部文字先展示优势，随后展示劣势。

不变量

子环消除不等式仍是承自上一张幻灯片的核心新增约束。

数学含义

讲解从一个具体的矛盾示例出发，过渡到完整的数学模型，最后总结采用该模型的实际影响。

静止的问题幻灯片，伴有指针移动

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
一张蓝色标题栏幻灯片，标题为“TSP：建模-2测试”，其上仅有一行问题文字，内容为使用 CPLEX 求解器求解 TSP 的建模-2。
动画
观察依据
一个绿色指针点在幻灯片文字上移动，而幻灯片其余部分保持静止。

图中对象

幻灯片标题栏
问题文字
绿色指针点

变化过程

光标圆点在文本区域内移动位置。

不变量

幻灯片内容在此时间段内保持不变。
屏幕上未添加任何公式或数值数据。

数学含义

该画面作为提示性幻灯片，引出基于求解器的旅行商问题（TSP）模型检验。

双条目改进型幻灯片

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
幻灯片切换为“TSP：改进分支定界法（B & B）方法”，并包含两个带星号的条目，分别对应下界与上界。
动画
观察依据
绿色光标圆点移至条目行附近，而幻灯片其余部分保持固定。

图中对象

幻灯片标题栏
下界条目
上界条目
绿色光标圆点

变化过程

随着讲解者讨论这两个条目，光标圆点在二者之间移动。

不变量

仅列出了两类改进方向。
幻灯片上未出现任何方程或算法伪代码。

数学含义

该幻灯片以视觉方式将讲座内容组织为两类改进分支：收紧下界与收紧上界。

易错点 · 8

将起始城市视为无关紧要

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片明确写道“假设环游从城市1出发”。
声音
观察依据
主讲人称这是一个非常关键的假设，并指出它会影响破除子环游的约束。

误区

人们可能认为 $u_i$ 的定义与选择哪座城市作为起点无关。

说明

视频强调该模型假设环游从城市1出发，而这一选择对本处所呈现的破除子环游约束至关重要。

假设未使用的弧仍施加顺序约束

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出：若 $x_{i,j}=0$ ，则无法直接判断 $u_i$ 与 $u_j$ 之间的关系。
声音
观察依据
说话人指出，若不直接从 i 走到 j，则无法确定 $u_i$ 与 $u_j$ 之间的关系。

误区

有人可能推断：无论弧是否被使用，每一对城市都必须满足 $u_i+1\le u_j$ 。

说明

仅当 $x_{i,j}=1$ 时，才断言直接的顺序关系；当 $x_{i,j}=0$ 时，该模型刻意避免在 $u_i$ 与 $u_j$ 之间施加直接关系。

认为任何足够大的 M 都同样合适

时间近似

依据视频推导

来源依据

公式
观察依据
幻灯片区分了较优估计 $M=n$ 与最优估计 $M=n-1$ 。
声音
观察依据
说话人强调应依据城市数量选择 M，而非任意设定。

待核验内容

该片段未详细讨论数值条件或求解器性能。

误区

有人可能认为：只要某个大-M 值有效，将其进一步增大便不会影响建模效果。

说明

分析人员补充道：该视频至少表明，M 的取值必须与问题规模相关，并特别指出 n 减一比 n 更紧；在实际的整数规划建模中，过大的 M 通常会削弱线性松弛效果，进而可能损害求解效率。

将子回路消除约束应用于起始城市

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片文字说明该约束适用于“对所有 i, $j = 2$ , …, n”。
声音
观察依据
主讲人强调：“我们正避免将行程起始城市纳入其中……这正是该约束的关键之一。”

误区

认为子回路消除约束应适用于所有城市，包括起始城市（城市1）。

说明

该约束被刻意限定为仅对 i, j >= 2 定义。排除起始城市可防止生成包含车场（depot）的循环不等式，从而确保仅正确建模从车场出发或返回车场的有效路径，而不会对车场的‘位置’施加人为限制。

误以为子环路约束始终生效

时间近似

补充解释

来源依据

公式
观察依据
该约束包含项 $n(1-x_{i,j})$ ，仅当 $x_{i,j}=1$ 时此项消失。
声音
观察依据
讲师解释道，一旦将该约束加入模型，它便会自动消除子环路。

误区

人们可能认为不等式 $u_i+1\le u_j+n(1-x_{i,j})$ 对任意节点对 i,j 都强制要求 $u_i+1\le u_j$ ，而不论弧 (i,j) 是否被使用。

说明

该不等式仅在 $x_{i,j}=1$ 时具有约束力；当 $x_{i,j}=0$ 时，所添加的项 n 会放松该约束，使其不对这条未使用的弧施加顺序限制。

假设 Formulation-2 仍保持指派问题结构

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
缺点说明文字：“指派问题结构遭到破坏。”
声音
观察依据
讲师指出，这意味着匈牙利法无法用于该线性规划松弛问题。

误区

由于两个度数约束形似指派约束，人们可能误以为整个模型仍具备指派问题结构。

说明

新增的子环路消除约束及辅助变量破坏了纯粹的指派结构，因此匈牙利法等专用于指派问题的算法不再适用于该松弛问题。

使用求解器不等同于手动执行分支定界法。

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人将当前主题与使用分支定界法进行对比，并指出接下来将展示如何利用 Cplex 求解器求解旅行商问题（TSP）。

误区

人们可能误以为用 Cplex 求解 TSP 只是此前所讨论的手动分支定界过程的另一种呈现方式。

说明

讲座明确区分了二者：本节介绍一种基于求解器的 Formulation-2求解路径，与此前手工构建的分支定界讨论截然不同。

下界与上界所起的作用不同。

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出存在两个方面：下界与上界；而更优的界可大幅缩减枚举树的规模。
字幕依据
观察依据
幻灯片将下界改进与上界改进列为两个独立的项目符号条目。

误区

人们可能认为仅改进其中任一界就已足够，或误以为下界与上界是可互换的工具。

说明

讲座将二者视为两条独立的改进轴线：下界通过指派问题方法加以收紧，而上界则通过启发式或元启发式方法加以收紧。

概念关系 · 19

第二种旅行商问题模型的目标 → 用于表示城市顺序的辅助变量 $u_i$

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人将该模型引入作为自动消除子环路的方法，并为此定义了 $u_i$ 。
公式
观察依据
幻灯片目标之后紧接着给出 $u_i$ 的定义。

应用

解释

辅助变量 $u_i$ 被专门引入，以使自动子回路消除建模成为可能。

用于表示城市顺序的辅助变量 $u_i$ → 由弧诱导的条件序关系

依据清楚

视频直接表达

来源依据

公式
观察依据
$u_i$ 的定义出现在条件语句 $u_i+1\le u_j$ 当 $x_{i,j}=1$ 之前。

证明依赖

解释

该条件序关系仅在 $u_i$ 和 $u_j$ 被解释为访问计数/访问顺序变量后才有意义。

二元弧变量 $x_{i,j}$ → 由弧诱导的条件序关系

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片先要求写出 $x_{i,j}$ 、 $u_i$ 与 $u_j$ 之间的关系，再陈述涉及 $x_{i,j}=1$ 的蕴含式。

证明依赖

解释

该“若-则”关系以 $x_{i,j}$ 为触发条件，决定是否对 $u_i$ 与 $u_j$ 施加序约束。

由弧诱导的条件序关系 → 条件关系的大 M 线性化

依据清楚

视频直接表达

来源依据

公式
观察依据
条件要点之后是幻灯片文字：“上述情形可建模为”，随后给出大 M 不等式。

等价

解释

大 M 不等式被呈现为前述“若-则”逻辑条件的线性模型。

条件关系的大 M 线性化 → 为旅行商问题（TSP）的子环消除选择大-M 常数

依据清楚

视频直接表达

来源依据

公式
观察依据
通用的大 M 不等式之后，幻灯片提出如何估计 M，并给出答案 $M=n$ ，同时注明 n-1 是最优取值。

应用

解释

选取 $M=n$ 将通用大 M 建模特化为含 n 座城市的旅行商问题（TSP）。

为旅行商问题（TSP）的子环消除选择大-M 常数 → MTZ 风格的子环消除约束

依据清楚

视频直接表达

来源依据

公式
观察依据
在陈述 $M=n$ 后，幻灯片展示最终约束式： $n(1-x_{i,j})$ 。

证明依赖

解释

最终的子回路消除约束是将选定值 $M=n$ 代入大 M 不等式所得。

MTZ 风格的子环消除约束 → 第二种旅行商问题模型的目标

依据清楚

视频直接表达

来源依据

公式
观察依据
最后一页幻灯片文字指出，该条件将自动消除子回路。

应用

解释

最后一个约束是第二种旅行商问题（TSP）模型实现其既定目标——自动消除子回路——的具体机制。

旅行商问题建模中的大M法 → 子回路消除约束公式

依据清楚

视频直接表达

来源依据

公式
观察依据
约束公式中的项 $n(1 - x_{i,j})$ 直接利用大常数 M（估算为 n）这一概念来松弛该不等式。

应用

解释

大-M 法是构建条件式子回路消除约束的底层机制，使得该约束仅在某条边被选中时才强制执行排序关系。

子回路消除约束公式 → 完整环游下可行的 u 值推导

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人借助图中各条边所生成的约束具体实例，逻辑推导出 u 变量的上下界及矛盾。

证明依赖

解释

证明完整回路可行、子回路不可行的全部推导过程，完全依赖于应用子回路消除约束所定义的代数规则。

子回路消除约束 → 模型-2的目标函数

依据清楚

视频直接表达

来源依据

公式
观察依据
同一不等式 $u_i+1\le u_j+n(1-x_{i,j})$ 既出现在验证幻灯片上，也再次出现在完整公式化幻灯片中。
声音
观察依据
讲师指出，Formulation-2 中的新内容是避免子环路或消除子环路的约束。

应用

解释

在验证示例中引入的子环路消除约束，已与目标函数和度数约束一同纳入完整的 Formulation-2 模型中。

入度约束 → 缺点：指派结构的丧失

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
缺点说明指出，指派问题的结构被破坏了。
公式
观察依据
该模型保留了两个度数约束，但增加了子回路消除约束以及 $u_i$ 变量。

对比

解释

尽管入度和出度约束类似于指派问题，但加入子回路消除系统却与该结构相悖，并使得专用于指派问题的方法不再适用。

子回路消除约束 → 建模形式-2的优势

依据清楚

视频直接表达

来源依据

字幕依据
观察依据
优点说明指出，该模型可自动化构建，并能使用常规的分支定界法求解。
声音
观察依据
讲师提到 CPLEX 和 Gurobi 是能够处理采用此模型的旅行商问题的求解器。

应用

解释

正是显式的子回路消除约束，使得该模型可直接交由标准的整数规划求解器，采用常规分支定界法进行求解。

问题定位 · 20

变量 $u_i$ 在 TSP 子回路消除模型中表示什么含义？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片将 $u_i$ 定义为在到达城市 i 之前所访问的城市数量。

涉及知识点

用于表示城市顺序的辅助变量 $u_i$

为什么该 TSP 模型假设旅程从城市1出发？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人称‘旅程从城市1出发’这一假设至关重要。

涉及知识点

用于表示城市顺序的辅助变量 $u_i$
固定起点城市假设

当使用从城市 i 到城市 j 的弧时， $x_{i,j}$ 、 $u_i$ 和 $u_j$ 之间存在怎样的关系？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片要求给出 $x_{i,j}$ 、 $u_i$ 和 $u_j$ 之间的关系，并随后给出一个条件蕴含式。

涉及知识点

二元弧变量 $x_{i,j}$
用于表示城市顺序的辅助变量 $u_i$
由弧诱导的条件序关系

如何将‘若 $x_{i,j}=1$ ，则 $u_i+1 \le u_j$ ’这一条件蕴含式转化为线性约束？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片将该情形建模为 $u_i+1 \le u_j+M(1-x_{i,j})$ 。

涉及知识点

由弧诱导的条件序关系
条件关系的大 M 线性化

在 TSP 的大-M 子回路消除约束中，M 应取何值？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出 M 可取 n，而最优估计值为 n-1。

涉及知识点

为旅行商问题（TSP）的子环消除选择大-M 常数
M
n

第二个旅行商问题（TSP）模型中展示的最终破圈约束是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
最终显示的约束为 $u_i+1 \le u_j+n(1-x_{i,j})$ ，其中对所有 i, $j=2$ , $\dots$ ,n 且 $i\ne j$ 成立。

涉及知识点

MTZ 风格的子环消除约束
子回路消除约束的推导

当 $x_{i,j} = 0$ 时，该模型是否对 $u_i$ 和 $u_j$ 施加了顺序关系？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出：若 $x_{i,j} = 0$ ，则无法在 $u_i$ 与 $u_j$ 之间建立直接关系。

涉及知识点

由弧诱导的条件序关系
未使用的弧不施加任何直接的顺序关系

为什么MTZ子环消除约束要排除起始城市（即i, $j \ge 2$ ）？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人解释了将下标限制在2到n范围内的原因。

涉及知识点

子回路消除约束公式
将子回路消除约束应用于起始城市

大M常数在TSP子环破除公式中是如何被使用的？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了 $n(1-x_{i,j})$ 这一项，并讨论了如何估计M。

涉及知识点

旅行商问题建模中的大M法
子回路消除约束公式

u变量约束如何从数学上证明子环不可能出现？

依据清楚

视频直接表达

来源依据

图示
观察依据
图示展示了一个不连通的环，以及由此产生的链式不等式。

涉及知识点

子回路结构不可行性的推导
利用子回路构型进行验证

TSP模型-2中的子回路消除约束是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片标题为“TSP：子回路消除约束”，其上明确显示了不等式 $u_i+1\le u_j+n(1-x_{i,j})$ 。

涉及知识点

子回路消除约束
辅助变量的非负性

为什么不含节点1的子回路在这些约束下变得不可行？

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师推导出 $u_2=0$ 和 $u_2=3$ ，并指出这是由子回路导致的矛盾。
图示
观察依据
该图在节点2、4和5上展示了一个独立的环。

涉及知识点

任何不包含节点1的子回路都会导致 u 值不一致。
数值验证：一个子回路违反了顺序约束
对一个含子环路的5节点旅行商问题（TSP）进行逐步验证

覆盖情况与待核验内容

已覆盖 · 标题与提纲介绍了第二个旅行商问题（TSP）模型，及其自动破除子圈的目标。

已覆盖 · 幻灯片定义了辅助变量 $u_i$ ，并强调关键假设：旅行从城市 1 出发。

已覆盖 · 主讲人回顾了二元弧变量 $x_{i,j}$ ，并着手探寻 $x_{i,j}$ 、 $u_i$ 与 $u_j$ 之间的关系。

已覆盖 · 手绘的 i–j 示意图配合展示了已使用弧与未使用弧所对应的条件顺序逻辑。

已覆盖 · 该条件关系通过大-M 约束线性化，其中 M 取为 n；同时指出 n - 1 是更紧的取值。

已覆盖 · 最终量化后的破圈约束被展示出来，并被确认为自动消除子圈的条件。

已覆盖 · 介绍MTZ子环破除约束、定义相关变量、讲解大M方法，以及特别说明为何排除起始城市。

已覆盖 · 通过完整回路示例进行逐步验证，推导u变量的上下界，并展示可行的整数赋值。

已覆盖 · 针对子环构型进行设定与逻辑推导，阐明循环边如何导致矛盾的不等式链。

已覆盖 · 子回路消除约束的验证示例，包括图示、分配的 u 值、矛盾推导及解释。

已覆盖 · 完整模型——2幻灯片，含目标函数、约束条件、变量声明，以及口述的优缺点分析。

已覆盖 · 结课练习提示：要求使用 CPLEX 求解模型-2，数据来自此前示例；本片段不展示求解结果。

已覆盖 · 开场幻灯片介绍了使用 CPLEX 求解 TSP 构型-2，并将其与分支定界法进行对比。

已覆盖 · 第二张幻灯片解释了改进 TSP 分支定界法的两种途径：通过指派问题方法获得更紧的下界，以及通过启发式或超启发式方法获得更紧的上界。

探索视频中的知识

已审核的主题路径

问题形式化

旅行商问题（TSP）- 形式化-2

把讲解展开来看。

章节

学习解说文稿

知识卡片

TSP建模目标——2

辅助顺序变量 uiu_iui​

二元弧变量 xi,jx_{i,j}xi,j​

对已选用弧的条件顺序规则

‘若—则’条件的大M线性化

在TSP模型中选取 M=nM = nM=n

最终的MTZ风格子环路消除约束

MTZ子回路消除约束

旅行商问题中的大M松弛

起始城市的排除

合法路径的可行性

子环构型的不可行性

子环路消除约束

为何子环路不可行

完整模型——2

模型2中的度数约束

变量定义域

模型2的主要优势

模型2的主要劣势

课后练习

TSP模型-2的Cplex求解路径

改进TSP分支定界法的两种途径

用于下界的指派问题方法

求上界所用的启发式与超启发式方法

详细学习笔记

uiu_iui​

xi,jx_{i,j}xi,j​

i

j

M

n

uiu_iui​

xi,jx_{i,j}xi,j​

n

M

xi,jx_{i,j}xi,j​

di,jd_{i,j}di,j​

第二种旅行商问题模型的目标

用于表示城市顺序的辅助变量uiu_iui​

二元弧变量 xi,jx_{i,j}xi,j​

由弧诱导的条件序关系

条件关系的大 M 线性化

为旅行商问题（TSP）的子环消除选择大-M 常数

MTZ 风格的子环消除约束

子回路消除约束公式

旅行商问题建模中的大M法

子回路消除约束

模型-2的目标函数

入度约束

固定起点城市假设

弧的使用意味着顺序变量的增加

未使用的弧不施加任何直接的顺序关系

最终约束自动消除子回路。

任何不包含节点1的子回路都会导致 u 值不一致。

模型-2可用常规整数规划求解器求解。

公式-2的线性规划松弛不再是一个指派问题。

更紧的界可减小枚举树的规模

本讲座中标准的界改进配对

子回路消除约束的推导

完整环游下可行的 u 值推导

子回路结构不可行性的推导

数值验证：一个子回路违反了顺序约束

为何大M项使未选弧失效

完整回路的验证

利用子回路构型进行验证

对一个含子环路的5节点旅行商问题（TSP）进行逐步验证

片段末尾的练习提示

用Cplex测试模型-2

标题与章节提纲

uiu_iui​ 的定义幻灯片

手绘的从 i 到 j 的弧线示意图

从大 M 法到最终子回路消除约束的演进过程

完整回路图与约束条件的构建

子回路图的构建与矛盾约束的生成

用于子环验证的含两个互不相交环的图

辅助顺序变量 $u_i$

二元弧变量 $x_{i,j}$

在TSP模型中选取 $M = n$

$u_i$

$x_{i,j}$

$u_i$

$x_{i,j}$

$x_{i,j}$

$d_{i,j}$

用于表示城市顺序的辅助变量 $u_i$

二元弧变量 $x_{i,j}$

$u_i$ 的定义幻灯片

第二种旅行商问题模型的目标 → 用于表示城市顺序的辅助变量 $u_i$

用于表示城市顺序的辅助变量 $u_i$ → 由弧诱导的条件序关系

二元弧变量 $x_{i,j}$ → 由弧诱导的条件序关系

变量 $u_i$ 在 TSP 子回路消除模型中表示什么含义？

当使用从城市 i 到城市 j 的弧时， $x_{i,j}$ 、 $u_i$ 和 $u_j$ 之间存在怎样的关系？

如何将‘若 $x_{i,j}=1$ ，则 $u_i+1 \le u_j$ ’这一条件蕴含式转化为线性约束？

当 $x_{i,j} = 0$ 时，该模型是否对 $u_i$ 和 $u_j$ 施加了顺序关系？

为什么MTZ子环消除约束要排除起始城市（即i, $j \ge 2$ ）？