数学建模 / 英语

运输问题简介

Best of My Knowledge · YouTube · 10:40

YouTube · Best of My Knowledge原视频

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

视频中的要点

01定义：运输问题
02线性规划（LPP）的概念
03示例：乳品加工厂与配送中心

来自学习笔记

\text{Objective: Minimize Cost of Distribution}

定义：运输问题

选中时刻

平衡与非平衡运输问题

建议预备知识

线性规划基础
最优化概念
线性规划的基本思想
对供应地和需求地求和的记号
解读网络图或二部图
运输问题中的发点、收点、供应量、需求量等基本概念
“成正比”的初级含义
线性规划基础
矩阵与表格表示法
对矩阵和线性规划概念的基本理解。
基可行解
运输矩阵结构

阅读与收藏

把讲解展开来看。

被收藏 0

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

阅读完整概览

本视频片段将运输问题介绍为一种特殊的线性规划问题（LPP）。其主要目标是最小化产品从多个源点向多个目的地配送过程中的成本。一张网络图以乳品厂为源点、配送中心为目的地，辅以相应的运输成本，形象地阐释了这一概念。这个120-秒的导引片段将运输问题定义为一种特殊的线性规划模型，用于最小化产品从各产地到各销地的配送成本。通过一个手绘网络图进行说明：该网络包含三个乳品厂作为产地、三个配送中心作为销地，以及从产地到销地的路线成本 $c_1$ 至 $c_9$ ；随后画面转向标准假设页面：总供应量等于总需求量、所有路线均可使用、单位成本完全已知、且路线成本与运量成正比。这段视频用手写白板讲解运输模型的基本假设与后续分类。前半页依次说明：物品可从所有供应点运到所有目的地；每条路线的单位运输成本确定且已知，并用 $S_1 \to D_1$ 举例；某条路线的运输成本与该路线发运量成正比；目标是使整个组织的总运输成本最小，而不是单个供应点或配送中心成本最小。后半页转入“可行解存在性”，给出判断方法：先比较总需求与总供应，若相等则运输问题存在可行解。随后把运输问题分为供需平衡型（需求等于供应）与供需不平衡型（需求不等于供应），并强调解题第一步就是检查供需是否相等。本片段介绍了运输问题的基本概念，包括如何根据总需求和总供给的关系将问题分为平衡与不平衡两类，并说明了通过添加虚拟行或列来平衡问题的方法。随后，详细讲解了如何构建运输问题的表格（矩阵）模型，明确了工厂、配送中心、供给、需求及单元格在矩阵中的位置与含义。最后，列举了求解该问题初始基本可行解的五种常用方法。本视频片段介绍了运输问题，概述了求初始基本可行解的方法，例如西北角法和VAM法；接着讲解了使用MODI法和踏石法进行最优性检验；最后定义了运输问题中的退化现象，给出了判定条件（ $m+n-1$ = 分配数），并以一个 $4\times 4$ 矩阵为例演示如何检验退化。本导论部分讲解运输问题中的退化概念。它定义了非退化基本可行解的条件：分配单元的数量必须等于 $m + n - 1$ （其中 m 为行数，n 为列数）。通过一个 $4\times 4$ 网格示例，其中包含 6 个分配，演示了如何识别退化情形（因为 $4 + 4 - 1 = 7 \ne 6$ ）。视频概述了标准求解流程图：首先求得一个基本可行解，然后检验其是否退化；若解为退化，则必须先予以处理，再应用 MODI 法或位势法等最优性检验方法。

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

章节

0:00运输问题简介 0:15与线性规划的关系 1:05图示表达与实例 2:00运输问题的定义及网络示例 2:30路线成本的含义与最小化目标 3:19切换至运输模型的假设 3:25假设1：供应量等于需求量 3:58假设2的起始部分 4:00运输模型中的基本假设 4:05单位运输成本已知 4:25成本与发运量成正比 4:39最小化整个组织的总成本 5:15可行解的存在性 5:38平衡与非平衡运输问题 6:00平衡与不平衡运输问题 6:19运输问题的表格（矩阵）形式 7:54寻找初始基本可行解的方法 8:00初始基本可行解的求解方法 8:40最优性检验方法 9:00运输问题中的退化现象 10:00退化条件与最优性检验 10:15运输问题的求解流程图 10:28在

4\times 4

网格中检验退化的示例

学习解说文稿

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

大家好！在本期视频中，我们将探讨运输问题（Transportation Problem）。如黑板所示，运输问题是线性规划（Linear Programming）的一种特殊类型，其目标是从多个源点向多个目的地配送产品时，使配送成本最小化。

让我们先理解什么是线性规划：它意味着我们拥有一些资源，并需对这些资源进行优化，以实现利润最大化或生产成本最小化。这类问题即称为线性规划问题（LPP）。

在运输问题中，它正是一种线性规划问题（LPP），其优化目标是使配送成本（即运输成本）最小化；这发生在我们将某类产品从多个源点运送到多个目的地的过程中。

为了更好地理解，我们来看一个图形表示。假设我们有一个生产产品的行业。这些产品随后进入仓库，再通过批发商到达零售商，最终送达消费者。

类似地，这里我举了一个例子：乳品加工厂。假设我们有三个乳品加工厂，我将它们标记为供应源（Source S1, S2, S3），即乳制品的生产地。这些产品将被运送到若干配送中心，我将其表示为需求点（Demand d1, d2, d3）。

因此，生产发生在这些供应源处，并需将产品运送到各需求点。例如，生产可能在德里、钦奈、印多尔等不同城市进行，而需将产品运往加尔各答、班加罗尔、博帕尔等不同城市。图中箭头上标注的 c1 到 c9 表示每条运输路径的运输成本。

该片段以一个手写定义开场：运输问题是一种特殊类型的线性规划问题（LPP），其目标是最小化产品从多个产地运送到多个销地的配送成本。

该定义下方展示了一个三行三列的网络图：左侧节点为产地 $S_1$ 、产地 $S_2$ 、产地 $S_3$ ，标识为乳品厂；右侧节点标注需求量 $d_1$ 、 $d_2$ 、 $d_3$ ，标识为配送中心，并附有加尔各答、班加罗尔和比哈尔等城市名称。

当笔迹描绘从 $S_1$ 到目标点 1 的路径时，2，以及3，主讲人指定单位运输成本 $c_1$ , $c_2$ , $c_3$ ，然后类似地， $c_4$ , $c_5$ , $c_6$ 对应于产地 2。其数学含义是：每条边存储了沿该路径每单位运量的成本。

随后，讲解者提出决策任务：选择由哪个源点向哪个目的地供货，使得所有目的地的需求均被满足，且总运输成本最小。

这一目标被板书中的“目标陈述（AIM）”概括为：寻找最优解，以最小化运输成本。其逻辑结构为：输入数据包括源点、目的地及各路径成本；优化目标是最小化总成本；约束条件是满足所有需求。

画面切换至“运输模型的假设”部分。假设 1 指出：各源点的总供应量等于各目的地的总需求量，简记为供应量 = 需求量。

讲解者将模型假设与现实情况作对比：实践中设备故障等因素可能导致供应减少，但本节所介绍的标准模型假设总供应量与总需求量严格相等。

视频片段在刚引入假设 2 时结束：物品可方便地从所有源点运往所有目的地。画面上还可看到但尚未展开讨论的假设 3——单位运输成本确定且精确已知；以及假设 4——路径运输成本与运量成正比。

这一段承接运输模型假设列表的第②条。白板上写着“Item can be transported conveniently from all sources to destinations”，讲解者将其读作：物品可以从所有供应点方便地运到所有目的地。这里的关键并非求解某个具体数值，而是先限定模型适用的网络结构：任意 supply 到任意 demand 均被视为可达。

接着进入第③条：“The Unit transportation cost of the item from all sources to destinations is certainly 且 precisely known.” 讲解者一边在“Unit transportation cost”下方划线，一边解释：当把物品从一个地点运往另一个地点时，每条路线上的单位运输成本都必须事先确切知晓。为使该假设更具体，板书旁给出记号 $S_1 \rightarrow D_1$ ，并口头说明：从 supply one 运往 demand center one 这条路线的单位运输成本是已知的。这一步将抽象假设落实到一条具体路线上。

然后是第④条：“The transportation cost on a given route is directly proportional to the number of units shipped on that route.” 讲解者将其转述为一种变化趋势：只要某条路线上发运的单位数量增加，该路线的运输成本也随之增加。画面中还在 cost 和 units 附近画出向上箭头，因此此处的数学含义并非固定成本，而是“同向增大”的正比关系。视频虽未写出代数式，但口头解释已清晰传达“directly proportional”的含义。

第⑤条进一步明确目标函数：“the objective is to minimize the total transportation cost for the organisation as a whole 且 not for individual supply 且 distribution centres.” 讲解者强调，优化对象既非某个供应点、也非某个配送中心自身的成本，而是整个组织层面的总运输成本。为帮助区分“整体”与“局部”，他在页面下方补充写出 $(Demand)$ 和 $(Supply)$ ，并将二者分别与第⑤条中的 individual supply 且 distribution centres 关联起来。由此可自然过渡至下一节：既然问题围绕 demand 与 supply 两侧展开，则首先需检验这两侧的总量关系。

画面切换至新一页，标题为“可行解的存在性”。该页首先给出判断流程：面对一个运输问题，第一步是比较总需求与总供给。板书将关键条件写作 $\text{Total Demand} = \text{Total Supply}$ ，并在等号上方打勾；下一行写“Then feasible solution exist for transportation problem”。讲解者同步说明：若总需求等于总供给，则该运输问题存在可行解。此处视频明确给出的是“相等 ⇒ 存在可行解”这一方向。

在同一页下半部分，视频继续将运输问题分为两类：a) 平衡运输问题（Balanced Transportation）与 b) 非平衡运输问题（Unbalanced Transportation）。前者旁标注 $\text{Demand} = \text{Supply}$ ，后者旁标注 $\text{Demand} \neq \text{Supply}$ 。讲解者特别强调，今后遇到运输问题时，最先应做的就是提取 demand 与 supply 并加以比较；若总需求与总供给相等，则属于平衡情形。如此，前面对可行解存在性的判断标准便与后续的问题分类直接衔接起来。

视频开篇在白板上展示了运输问题的两种基本类型。首先定义了“平衡运输问题”（Balanced Transportation），其核心条件是总需求等于总供给，即 $\sum Demand = \sum Supply$ 。接着定义了“不平衡运输问题”（Unbalanced Transportation），其条件是总需求不等于总供给，即 $\sum Demand \neq \sum Supply$ 。

针对不平衡运输问题，讲解者指出可以通过添加“虚拟行或列”（dummy Row / column）将其转化为平衡运输问题，从而可以使用标准的求解方法。这一转换过程将在后续的具体问题求解中进一步阐明。

随后，视频进入“运输问题的公式化”（Formulation of Transportation Problem）环节。讲解者在白板上绘制了一个 $4 \times 4$ 的表格（也称为矩阵）。表格的左侧行标签为“Plants”（工厂），代表产品的制造地；上方列标签为“Distribution Centre”（配送中心），代表产品的需求地。

在表格的右侧，标注了 $S_1, S_2, S_3, S_4$ ，代表各个工厂的“Supply”（供给量）。在表格的下方，标注了 $D_1, D_2, D_3, D_4$ ，代表各个配送中心的“Demand”（需求量）。表格内部的每一个小方格被称为“Cell”（单元格）。

讲解者说明，这些单元格内通常会填入从特定工厂到特定配送中心的“运输成本”（transportation cost）。此外，如果某个单元格被特殊标记（如图中所示的带折角的方块），则表示该单元格是“已分配单元格”（Allocated Cell），意味着实际的货物运输发生在该路径上。

最后，视频列出了求解运输问题时寻找“初始基本可行解”（Initial basic feasible solution）的五种常用方法：1) 西北角法（North-west Corner Method），2) 行最小值法（Row Minima Method），3) 列最小值法（Column Minima Method），4) 最小元素法或矩阵最小值法（Least Cost Method or Matrix Minima），5) 伏格尔近似法或罚数法（VAM (Vogel's Approximation) or Penalty Method）。

本视频片段介绍了求解运输问题的初始基本可行解的各种方法。黑板上列出了五种主要方法：1）西北角法，2）行最小元素法，3）列最小元素法，4）最小成本法（又称矩阵最小元素法），以及5）VAM法（即伏格尔近似法，也称罚值法或遗憾法）。这些方法可帮助我们求得运输问题的一个可行解。

然而，必须注意的是，通过上述方法所得的可行解并不总是最优（即最理想）的。因此，需进一步采用最优性检验方法来判断该解是否最优。黑板上展示了两种最优性检验方法：1）MODI法（修正分配法），也称为UV法；以及2）踏石法。利用这些方法，我们可以确定所获得的初始基本可行解是否确实为最优解。

随后，视频讲解了“运输问题中的退化”这一概念。当我们运用某种方法求得基本可行解后，需检验分配数（number of allocations）是否等于 $m + n - 1$ ，其中 m 为行数（no. of rows），n 为列数（no. of columns）。若分配数不等于 $m + n - 1$ ，则该问题存在退化现象。

例如，展示了一个 $4\times 4$ 矩阵，其中包含6个分配。此处， $m = 4$ 且 $n = 4$ 。因此， $m + n - 1 = 4 + 4 - 1 = 7$ 应成立。由于实际分配的数量为6，不等于7（ $7 \ne 6$ ），因此该运输问题中存在退化现象。在进行最优性检验之前，必须消除这一退化现象。

让我们理解运输问题中的退化概念。当我们准备应用 MODI 法或位势法等最优性检验时，必须确保初始基本可行解不发生退化。

当分配单元的数量恰好等于 $m + n - 1$ 时，该解即为非退化解，其中 $m$ 为行数， $n$ 为列数。若分配数量少于该值，则解为退化，须在继续进行最优性检验前先行处理。

考虑运输问题求解的逻辑流程图：首先，采用西北角法、行最小法、列最小法、最小成本法或伏格尔近似法（VAM）等方法，求出一个基本可行解；然后，检验分配数量是否等于 $m + n - 1$ 。

例如，取一个 $4 \times 4$ 阶表格，其中含有 6 个分配。所需数目为 $4 + 4 - 1 = 7$ 。由于 $7 \neq 6$ ，该解是退化的。在此情况下，您必须在应用MODI法或踏石法之前先解决退化问题。如果分配数为 7，则我们可以直接进行最优性检验。

知识卡片

定义：运输问题

运输问题是线性规划（LPP）的一种特殊类型。其主要目标是将产品从多个供应源（如工厂或乳品加工厂）运送到多个目的地（如仓库或配送中心），使得总运输成本最小。

\text{Objective: Minimize Cost of Distribution}

线性规划（LPP）的概念

线性规划是一种对有限资源进行优化配置的数学方法。其目标是使收益最大化，或使成本最小化。运输问题正是其中一种特定应用，其目标是最小化运输成本。

示例：乳品加工厂与配送中心

作为一个实际例子，需将产品从乳品加工厂（供应源 S1, S2, S3）运送到配送中心（需求点 d1, d2, d3）。每一对供应源与需求点之间都存在一个特定的运输成本（c_ij），图中用箭头上的数值表示。该问题的目标是找出一种配送方案，使得所有运输成本之和最小。

运输问题的定义

运输问题被介绍为一类特殊的线性规划问题，其核心是：在满足各目的地需求的前提下，将产品从多个源点运往多个目的地，并使总运输成本最小。

带路径成本的网络图示

一幅手绘的二部网络图将源点 $S_1$ 、 $S_2$ 、 $S_3$ 置于左侧，将具有需求量 $d_1$ 、 $d_2$ 、 $d_3$ 的目的地置于右侧；每条连接边均标有成本标签，如 $c_1$ 、 $c_2$ 、 $\dots$ 、 $c_9$ ，代表该路径上的单位运输成本。

c_{ij} \text{ = unit cost from source } i \text{ to destination } j

目标：最小化总运输成本

明确的目标是：决定各源点向各目的地的发货量，使得全部需求均被满足，且总运输成本尽可能小。板书上将其表述为：寻找最优解以最小化运输成本。

\text{Minimize total transportation cost subject to demand satisfaction}

假设1：模型是平衡的

第一个正式假设是，所有供应地的总供应量等于所有需求地的总需求量。主讲人指出，现实中可能出现不平衡情况，但本模型假设二者相等。

\sum_i \text{Supply}_i = \sum_j \text{Demand}_j

假设2：所有供应地到需求地的运输路线都是可行的

第二个假设指出，物品可从所有供应地便捷地运往所有需求地，即基础模型不排斥任何一条运输路线。

假设3：单位运输成本完全已知

第三个假设指出，从每个供应地到每个需求地的单位运输成本是确定且精确已知的。示例符号 $S_1 \rightarrow D_1$ 表示某一条运输路线，其成本被视为确定性数据。

c_{ij} \text{ is known for each route } i \rightarrow j

假设4：运输成本随发货数量线性变化

第四个假设指出，某条运输路线上的运输成本与所发货物数量成正比，因此该路线的总成本等于单位成本乘以数量。

\text{Route cost} \propto \text{number of units shipped}

运输模型假设②：所有供应点到所有目的地均可运输

视频在“运输模型中的假设”列表中首先说明第②条：物品可以从所有供应点（sources）方便地运到所有目的地（destinations）。它规定的是模型中的可达性前提，即不将某些路线视为不可用。

\text{Item can be transported conveniently from all sources to destinations}

运输模型假设③：单位运输成本确定且已知

第③条规定，从任一供应点到任一需求点的单位运输成本都是确定且精确已知的。讲解者用 $S_1 \rightarrow D_1$ 举例，说明从第1个供应点向第1个需求点供货时，这条路线上的单位运输成本必须事先知道。

\text{The Unit transportation cost of the item from all sources to destinations is certainly \text{且} precisely known}

用 $S_1 \rightarrow D_1$ 解释一条具体运输路线

板书中的 $S_1 \rightarrow D_1$ 不是新定理，而是对第③条假设的实例化： $S_1$ 表示第1个供应点， $D_1$ 表示第1个需求点，箭头表示从供应点到需求点的运输路线。讲解者借此说明“单位运输成本已知”是针对每条具体路线而言的。

S_1 \rightarrow D_1

运输模型假设④：路线成本与发运量成正比

第④条说明，某条给定路线上的运输成本与该路线上发运的单位数量成正比。讲解者把它解释成“数量增加，成本也增加”，并用向上箭头强化这种同向变化关系。视频没有写出正式代数式，但正比含义已被明确说明。

\text{The transportation cost on a given route is directly proportional to the number of units shipped on that route}

运输模型假设⑤：最小化整体总运输成本

第⑤条把目标定义为最小化整个组织的总运输成本，而不是各个供应中心和配送中心的成本。讲解者额外写下 $(Demand)$ 和 $(Supply)$ ，帮助说明运输问题同时涉及需求端和供给端，而优化目标是全局总成本。

\text{the objective is to minimize the total transportation cost for the organisation as a whole \text{且} not for individual supply \text{且} distribution centres}

常见误区：不要把目标理解成单个中心成本最小

视频特别强调，目标不是只让某一个供应点或某一个配送中心的成本最小，而是让整个流程的总运输成本最小。这一点通过把“整个组织”与“各个供应中心和配送中心”对照来讲清。

可行解存在性的判断方法

进入“可行解存在性”后，讲解者给出的第一步方法是：先计算并比较总需求与总供应。若二者相等，则称该运输问题存在可行解。板书把这一条件写成 $\text{Total Demand} = \text{Total Supply}$ ，并在其下写“Then feasible solution exist for transportation problem”。

\text{Total Demand} = \text{Total Supply} \Rightarrow \text{Then feasible solution exist for transportation problem}

平衡运输问题与不平衡运输问题

视频将运输问题分为两类：平衡运输问题对应 $\text{Demand} = \text{Supply}$ ，非平衡运输问题对应 $\text{Demand} \neq \text{Supply}$ 。分类依据是总需求与总供给是否相等。

解题的第一步：先检查需求量与供应量

讲解者在结尾强调，今后遇到运输问题时，最先要做的就是将需求量与供应量列出并加以比较。这一步既是判断问题属于平衡型还是非平衡型的依据，也是进入‘可行解存在性’讨论的前提。

平衡与不平衡运输问题

运输问题根据总需求和总供给的关系分为两类。如果所有工厂的总供给量等于所有配送中心的总需求量（ $\sum Demand = \sum Supply$ ），则称为平衡运输问题。如果不相等（ $\sum Demand \neq \sum Supply$ ），则称为不平衡运输问题。

\sum Demand = \sum Supply \quad \text{or} \quad \sum Demand \neq \sum Supply

虚拟行/列的使用

为了能够使用标准算法求解不平衡运输问题，通常需要将其转化为平衡问题。转化的方法是在表格中添加一个虚拟的行（如果总需求大于总供给）或虚拟的列（如果总供给大于总需求），其供给量或需求量恰好弥补差额，且对应的运输成本通常设为零。

运输问题表格（矩阵）结构

运输问题可以用一个二维表格或矩阵来直观表示。矩阵的行代表供给方（如工厂），列代表需求方（如配送中心）。矩阵右侧记录各行的供给量（Supply $S_i$ ），下方记录各列的需求量（Demand $D_j$ ）。矩阵内部的单元格代表从特定供给方到特定需求方的运输路径，通常用于填写单位运输成本或实际分配量。

初始基本可行解的求解方法

在建立运输问题的表格模型后，第一步是找到一个初始基本可行解。视频中列举了五种常用的启发式方法：西北角法、行最小值法、列最小值法、最小元素法（矩阵最小值法）以及伏格尔近似法（罚数法）。这些方法各有特点，用于快速确定一个满足供需约束的初始分配方案。

初始基本可行解的求解方法

这些是用于为运输问题寻找初始可行解的技术。视频列举了五种方法：西北角法、行最小元素法、列最小元素法、最小成本法（又称矩阵最小元素法）以及VAM法（即伏格尔近似法，也称罚值法或遗憾法）。

详细学习笔记

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

符号定义 · 28

LPP

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上可见文字“LPP（线性规划）”。
声音
观察依据
讲话者提到了“LPP”和“线性规划”。

符号

LPP

含义

线性规划问题

适用范围

优化

$S_i$

依据清楚

视频直接表达

来源依据

公式
观察依据
图中可见文字“供应源 S1”、“供应源 S2”、“供应源 S3”。
声音
观察依据
讲话者提到了“供应源”和“乳品厂”。

符号

$S_i$

含义

供应源 i（例如：乳品厂）

适用范围

运输问题

$d_j$

依据清楚

视频直接表达

来源依据

公式
观察依据
图中可见文字“需求量 d1”、“需求量 d2”、“需求量 d3”。
声音
观察依据
讲话者提到了“目的地”和“配送中心”。

符号

$d_j$

含义

目的地 j 的需求量（例如：配送中心）

适用范围

运输问题

c_{ij}

依据清楚

视频直接表达

来源依据

公式
观察依据
箭头连接各供应地与需求地，其上显示文字“c1”“c2”“c3”“c4”“c5”“c6”“c7”“c8”“c9”
声音
观察依据
说话人提到“配送成本”

待核验内容

每个 c_ij 的具体含义（例如：从供应地 i 到需求地 j 的单位运输成本）虽未明确说明，但属于此类问题的标准设定

符号

c_{ij}

含义

从供应地 i 运输到需求地 j 的成本

适用范围

运输问题

$S_i$

依据清楚

视频直接表达

来源依据

图示
观察依据
网络图的左列标注为源点 $S_1$ 、源点 $S_2$ 、源点 $S_3$ 。
声音
观察依据
讲解各供应源的供应量时，说话人将三个源点分别称为源点一、源点二和源点三。

符号

$S_i$

含义

运输中的供应源或供应点；本例中这些源点是乳品加工厂。

适用范围

在所展示的例子中， $i \in {1,2,3}$ 。

$d_j$

依据清楚

视频直接表达

来源依据

图示
观察依据
网络图的右列标注为需求 $d_1$ 、需求 $d_2$ 、需求 $d_3$ 。
声音
观察依据
说话人指出，需求 $d_1$ 可由多个供应源共同满足。

符号

$d_j$

含义

目的地 j 处的需求，以配送中心的需求量形式呈现。

适用范围

在所展示的例子中， $j \in {1,2,3}$ 。

Destination cities

依据清楚

视频直接表达

来源依据

图示
观察依据
目的地节点标注了城市名称：加尔各答、班加罗尔和比哈尔。
声音
观察依据
说话人将加尔各答、班加罗尔和比哈尔称为城市。

待核验内容

节点编号与城市标签之间的具体对应关系在图中视觉上较为密集，但始终一致地显示了三个目的地。

符号

Destination cities

含义

本例中用于三个需求点的具体名称。

c_{ij}

依据清楚

视频直接表达

来源依据

图示
观察依据
源点与目的地之间的边标记为 $c_1$ 至 $c_9$ 。
声音
观察依据
说话人指出，从 $S_1$ 到 1 的单位运输成本为 $c_1$ ，到 2 的单位运输成本为 $c_2$ ，到 3 的单位运输成本为 $c_3$ ，类似地， $c_4$ , $c_5$ , $c_6$ 分别对应产地 2。

待核验内容

视频中在边上使用单下标标记 $c_1$ ,…, $c_9$ ，而非显式的双下标记号。

符号

c_{ij}

含义

从源点 i 到目的地 j 的单位运输成本；在黑板示例中，这些值用边上的标记 $c_1$ ,…, $c_9$ 表示。

Supply = Demand

依据清楚

视频直接表达

来源依据

公式
观察依据
假设 1 页包含手写备注：供应量 = 需求量。
声音
观察依据
主讲人指出，各源点处可提供的物品总量等于总需求量，即需求量。

符号

Supply = Demand

含义

平衡运输模型的条件：总可供应量等于总需求量。

$S_1 \rightarrow D_1$

依据清楚

视频直接表达

来源依据

公式
观察依据
假设 3 页包含手写路线示例： $S_1 \to D_1$ 。

待核验内容

$D_1$ 仅出现在假设页上，且该页未对其单独定义。

符号

$S_1 \rightarrow D_1$

含义

在讨论已知单位运输成本时，表示从源点 1 到目的地 1 的路线所用的示例记号。

Supply = Demand

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上第①条假设旁用红笔写着 Supply = Demand。

符号

Supply = Demand

含义

运输模型中总供应量等于总需求量。

适用范围

运输问题的总量条件

$S_1 \to D_1$

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上第③条假设旁用红笔写着 $S_1 \to D_1$ 。
声音
观察依据
讲解者说“从S1即第一个供应点，向第一个需求中心运送货物时，其单位运输成本是已知的”。

符号

$S_1 \to D_1$

含义

从第1个供应点到第1个需求点的运输路线示例。

适用范围

运输路线记号

知识点 · 24

运输问题的定义

依据清楚

视频直接表达

来源依据

公式
观察依据
文字定义：“运输问题是线性规划问题（LPP）的一种特殊类型，其目标是使产品从若干供应地运往若干需求地的配送成本最小化。”
声音
观察依据
说话人朗读并解释运输问题的定义

定义

解释

运输问题是一种特殊的线性规划问题（LPP），其主要目标是最小化将产品从多个供应地（如工厂或乳品厂）配送至多个需求地（如仓库或配送中心）所产生的总成本

适用条件

它属于线性规划问题的一种
目标是使成本最小化
涉及多个供应地和多个需求地

先修条目

线性规划的概念

线性规划的概念

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人讲解：“线性规划指的是什么？我们手头有一些资源，对这些资源我们要进行优化，从而使得我们的利润最大化，或者尽量使我们的生产成本最小化。”

定义

解释

线性规划涉及对一组资源的优化；这种优化可以是使利润最大化，也可以是使生产成本最小化。

适用条件

涉及资源。
目标是优化（即：使利润最大化，或使成本最小化）。

运输问题的定义

依据清楚

视频直接表达

来源依据

公式
观察依据
第一页顶部写着：一种特殊类型的线性规划问题（LPP），其目标是使产品从多个源点运往多个目的地的总成本最小化。
声音
观察依据
主讲人解释，运输问题旨在最小化运输成本，同时满足各配送中心的需求。

定义

解释

运输问题被表述为一类特殊的线性规划问题，其目标是在满足各目的地需求的前提下，最小化将产品从多个供应地运送到多个目的地的总成本。

适用条件

存在多个供应地和多个目的地。
每条从供应地到目的地的运输路线都对应一个运输成本。
目标是在满足需求的约束下实现成本最小化。

先修条目

供应地、目的地及路线成本的网络表示

供应地、目的地及路线成本的网络表示

依据清楚

视频直接表达

来源依据

图示
观察依据
绘制了一个二部图风格的网络：左侧为供应地 $S_1$ 、 $S_2$ 、 $S_3$ ，右侧为需求点 $d_1$ 、 $d_2$ 、 $d_3$ ，两者之间由标有 $c_1$ ,…, $c_9$ 的边相连。
声音
观察依据
讲解者指向从 $S_1$ 到目的地 1、2、3 的路线，并分别赋予成本 $c_1$ 、 $c_2$ 、 $c_3$ ；随后以类似方式处理供应地 2。

方法

解释

黑板上采用网络图来表示运输模型：供应地置于一侧，目的地置于另一侧，每条可能的运输路线均以一条边表示，并在边上标注单位运输成本。

适用条件

供应地与目的地被视为两个相互独立的节点集合。
边表示可行的运输路线。
边上的标签表示单位成本。

运输问题的目标

依据清楚

视频直接表达

来源依据

公式
观察依据
第一页下半部分写着：目标——找出最优解，以最小化运输成本。
声音
观察依据
主讲人指出，目标是最小化运输成本，并得出一个最优解。

公式

解释

所陈述的目标是：在满足各目的地需求的前提下，找到一种从供应地到需求地的最优货物分配方案，使得总运输成本最小。

公式

\text{Minimize total transportation cost}

适用条件

各目的地的需求必须得到满足。
总运输成本应被最小化。

先修条目

运输问题的定义
供应地、目的地及路线成本的网络表示

假设1：供需平衡

依据清楚

视频直接表达

来源依据

公式
观察依据
假设1文字：各供应地可提供的物品总量（即供应量）等于各目的地的总需求量。
声音
观察依据
主讲人明确指出供应量等于需求量，并补充说明实际中可能出现扰动，但该模型假设二者相等。

定义

解释

第一个建模假设是：所有供应地的总供应量等于所有目的地的总需求量，从而使运输模型成为平衡型。

公式

\sum_i \text{Supply}_i = \sum_j \text{Demand}_j

适用条件

该模型是在标准假设下构建的。
对所有供应地的总供应量与所有目的地的总需求量进行比较。

先修条目

运输问题的定义

假设2：所有运输路线均可使用。

依据清楚

视频直接表达

来源依据

公式
观察依据
假设2文字：物品可方便地从所有产地运往所有销地。
声音
观察依据
讲话者在视频片段结束前开始朗读第二条假设。

待核验内容

本片段中仅包含假设2口头解释的开头部分。

定义

解释

第二条假设指出，物品可方便地从任一产地运往任一销地，这意味着基础模型中不存在路线限制。

适用条件

每一对产地—销地组合均被视为运输可行。

先修条目

供应地、目的地及路线成本的网络表示

假设3：单位运输成本已知。

依据清楚

视频直接表达

来源依据

公式
观察依据
假设3文字：物品从所有产地到所有销地的单位运输成本是确定且精确已知的。
图示
观察依据
路线示例 $S_1$ -> $D_1$ 写在此假设旁。

待核验内容

本片段中未完整展开假设3的音频解释。

定义

解释

第三条假设是：从任一产地到任一销地的每条运输路线的单位运输成本均被精确且确定地知晓。

公式

c_{ij} \text{ is known for each route } i \rightarrow j

适用条件

每条运输路线均有确定的单位成本。
成本在模型中被视为确定性数据。

先修条目

供应地、目的地及路线成本的网络表示

假设4：成本与运输量成正比

依据清楚

视频直接表达

来源依据

公式
观察依据
假设4文字说明：某条运输路线上的运输成本与运输的单位数量成正比。

待核验内容

本片段中未听到关于假设4的口头详细说明。

定义

解释

第四条假设指出，在某条运输路线上，运输成本随运输的单位数量成正比变化。

公式

\text{Route cost} \propto \text{number of units shipped}

适用条件

选定一条固定路线。
运输量发生变化，而单位成本保持不变。

先修条目

假设3：单位运输成本已知。

运输模型假设②：任意供应点到任意需求点均可运输

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上第②条写着：物品可从所有供应点方便地运往所有目的地。
声音
观察依据
讲解者读出：可从所有供应点方便地运往目的地。

定义

解释

该假设规定物品可以从所有供应点方便地运往所有目的地，意味着模型不考虑某些路线不可达的情况。

公式

\text{Item can be transported conveniently from all sources to destinations}

适用条件

适用于运输模型的基本假设
视频未说明不可达路线如何处理

运输模型假设③：单位运输成本确定且已知

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上第③条写着：所有供应点到需求点的单位运输成本均确定且精确已知。
声音
观察依据
讲解者说“单位运输成本我们是知道的，即每件物品从一个地点运送到另一个地点时的成本”，并举例“从S1（即供应点一）向需求中心一供货时，其单位运输成本我们是清楚的”。
图示
观察依据
讲解者用粉色笔在‘单位运输成本’下方划线，并指向 $S_1 \to D_1$ 。

定义

解释

该假设规定从任一供应点到任一需求点的单位运输成本都是确定且精确已知的。讲解者用 $S_1 \to D_1$ 举例，说明从第1个供应点到第1个需求点的单位运输成本必须事先知道。

公式

\text{The Unit transportation cost of the item from all sources to destinations is certainly \text{且} precisely known}

适用条件

适用于运输模型中的每一条路线
视频未说明成本随机波动时如何处理

先修条目

运输模型假设②：任意供应点到任意需求点均可运输

运输模型假设④：路线运输成本与发运量成正比

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上第④条写着：某条路线上的运输成本与该路线上的发运量成正比。
声音
观察依据
讲解者说“某条路线上的运输成本与该路线上的发运量成正比，即发运量一旦增加，运输成本也随之增加”。
图示
观察依据
讲解者在‘cost’和‘units’附近画红色向上箭头，表示二者同向增加。

定义

解释

该假设规定某条给定路线上的运输成本与该路线上发运的单位数量成正比。讲解者口头解释为：单位数量增加，运输成本也增加。

公式

\text{The transportation cost on a given route is directly proportional to the number of units shipped on that route}

适用条件

针对单条路线
视频未给出比例常数的具体符号

先修条目

运输模型假设③：单位运输成本确定且已知

定理与条件 · 5

标准运输模型假设总供应量等于总需求量

依据清楚

视频直接表达

来源依据

公式
观察依据
假设1所在页面指出总供应量等于总需求量，并在其旁标注‘Supply = Demand’。
声音
观察依据
讲话者指出，尽管机器故障等实际事件可能导致供应减少，但问题求解所采用的假设是供应量等于需求量。

命题

在本处介绍的运输模型中，假设 $\sum_i \text{Supply}_i = \sum_j \text{Demand}_j$ 。

前提

讨论内容为运输模型的标准假设。
供给是指各供应地的总可提供数量，需求是指各目的地的总需求量。

量词

对于整个供应地与目的地系统，总供给量被设定为等于总需求量。

运输问题旨在寻求一种最优的最低成本分配方案。

依据清楚

视频直接表达

来源依据

公式
观察依据
第一页上的目标陈述写道：找出最优解，以最小化运输成本。
声音
观察依据
主讲人指出，目标是最小化运输成本并得出一个最优解。

命题

运输问题的目标是确定一个最优的货物运输计划，在满足各目的地需求的前提下使总运输成本最小。

前提

存在明确的供应地、目的地以及各条运输路线的成本。
必须满足全部需求。

量词

在所有从供应地到目的地的可行分配方案中，选择总成本最小的一种。

若总需求等于总供给，则运输问题存在可行解

依据清楚

视频直接表达

来源依据

公式
观察依据
板书写明总需求等于总供给，随后一行写“此时运输问题存在可行解”。
声音
观察依据
讲解者说“如果总需求等于总供给，我们就说该运输问题存在可行解”。

待核验内容

视频未说明当总需求不等于总供给时可行解是否一定不存在，也未说明是否需要先化为平衡问题。

命题

如果总需求等于总供给，那么该运输问题存在可行解。

前提

给定一个运输问题
已计算总需求与总供给
二者相等

量词

对一个运输问题而言，若总需求等于总供给，则存在可行解。

平衡运输问题的定义

依据清楚

视频直接表达

来源依据

公式
观察依据
a) 平衡运输问题，旁注 Demand = Supply。
声音
观察依据
讲解者说“balance 中指的是 demand 与 supply 相等，即 total demand 等于 total supply”。

命题

平衡运输问题是指 total demand 等于 total supply 的运输问题。

前提

讨论对象是运输问题
比较量为 total demand 与 total supply

量词

当且仅当需求等于供给时，视频将其称为 balanced transportation。

必须在最优性检验之前解决退化问题

依据清楚

视频直接表达

来源依据

声音
观察依据
如果不满足该条件，就会出现退化情形；我们必须先解决该退化问题，然后再进行最优性检验。
公式
观察依据
画面上写着： $4+4-1 = 7 \ne 6$

命题

若基本可行解中的分配数量不等于 $m + n - 1$ ，则该解为退化解，必须在进行最优性检验之前消除这一退化现象。

前提

已为运输问题找到一个基本可行解。

量词

适用于所有运输问题。

推导与证明 · 4

从网络图中读取路线成本

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：从 $S_1$ 到1的单位运输成本为 $c_1$ ，到2为 $c_2$ ，到3为 $c_3$ ；同理，对于供应地2，其对应成本分别为 $c_4$ 、 $c_5$ 、 $c_6$ 。
图示
观察依据
从左侧供应节点指向右侧目的地节点的各条边，其标签依次为 $c_1$ 至 $c_9$ 。

待核验内容

黑板上采用顺序编号的边标签，而非显式的双重下标记号，因此到c_{ij}的映射需依据口述模式推断。

视觉说明

步骤

公式
解释
识别左侧的源节点 $S_1$ 、 $S_2$ 、 $S_3$ 和右侧的目标节点 1、2、3。
步骤依据
这些标签在图中清晰标出。
视频直接表达
公式
解释
追踪从 $S_1$ 到目标节点 1、2、3 的边，并将其标签分别读作 $c_1$ 、 $c_2$ 、 $c_3$ 。
步骤依据
说话者在沿路径指示时明确赋予了这些成本值。
视频直接表达
公式
解释
对 $S_2$ 重复相同的读取过程，得到其三条出边对应的成本 $c_4$ 、 $c_5$ 、 $c_6$ 。
步骤依据
说话者在介绍第一个源节点后，依次陈述了这些数值。
视频直接表达
公式
$c_{ij}$
解释
将每条边的标签解释为从源 i 到目标 j 的单位运输成本。
步骤依据
这与口头描述的每条路线上单位运输成本一致。
依据视频推导

结论

该图编码了源与目标之间所有路线对应的单位成本完整集合，这些数据即为运输模型所用。

正比关系的直观说明

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者说“随着单位数量增加，运输成本也将增加”。
图示
观察依据
讲解者在第④条中的 cost 和 units 附近画红色向上箭头。

待核验内容

视频没有写出代数形式，如 $C = c x$ 或 $C \propto x$ 。

直观解释

步骤

公式
解释
先陈述第④条假设：某条路线上的运输成本与该路线发运的单位数量成正比。
步骤依据
来自白板第④条文字。
视频直接表达
公式
解释
再把文字转成变化方向的理解：单位数量增加时，运输成本也增加。
步骤依据
来自讲解者的口头解释和向上箭头标注。
视频直接表达

结论

视频用文字和箭头说明“数量增加导致成本增加”的正比直觉，但未给出正式代数式。

检验退化性的示例

依据清楚

视频直接表达

来源依据

公式
观察依据
画面上写着：( $4+4-1$ ) ≠ 6
声音
观察依据
那么行数 m 是多少？我们有四行，对吧；而 n 是列数，这里也是四列；四加四减一得到七；这个七是否等于分配个数？而分配个数是1、2、3、4、5、6，共六个，不等于七；这意味着该运输问题中存在退化性。

数值验证

步骤

公式
$m = 4, n = 4$
解释
从给定矩阵中识别行数和列数。
步骤依据
对矩阵进行直观观察。
视频直接表达
公式
$m + n - 1 = 4 + 4 - 1 = 7$
解释
计算非退化解所需的分配单元个数。
步骤依据
应用退化性条件的公式。
视频直接表达
公式
$No. of allocations = 6$
解释
统计矩阵中实际已分配单元的个数。
步骤依据
对已标记单元进行直观计数。
视频直接表达
公式
$7 \neq 6$
解释
将预期分配单元个数与实际个数进行比较。
步骤依据
数值比较。
视频直接表达
公式Degeneracy exists
解释
由于两个数值不相等，得出该问题具有退化性的结论。
步骤依据
运输问题中退化的定义。
视频直接表达

结论

所给运输问题是退化的。

求解运输问题的逻辑流程。

依据清楚

视频直接表达

来源依据

声音
观察依据
首先，我们找出基本可行解，然后检查该解是否满足条件；若满足，则可直接进行最优性检验；若不满足，则出现退化情形，需先解决退化问题，再进行最优性检验。
公式
观察依据
用箭头连接各步骤的流程图结构。

直观解释

步骤

公式
$\text{Find Basic Feasible Solution}$
解释
首先使用西北角法、行最小元素法等方法，求出一个初始基本可行解。
步骤依据
以音视频形式列出的各类方法。
视频直接表达
公式
$\text{Check if Allocations} = m + n - 1$
解释
将分配数量与所需的 $m + n - 1$ 进行核对。
步骤依据
以音视频形式呈现的公式。
视频直接表达
公式
$\text{If Yes} \rightarrow \text{Apply Optimality Test (MODI / Stepping Stone)}$
解释
若条件满足，则直接进入最优性检验环节。
步骤依据
以音频方式解释该条件已被满足的情形。
视频直接表达
公式
$\text{If No} \rightarrow \text{Resolve Degeneracy} \rightarrow \text{Apply Optimality Test}$
解释
若条件不满足，则解是退化的；需先解决退化问题，再进行最优性检验。
步骤依据
对未满足条件的语音讲解及流程图中的视觉箭头指示。
视频直接表达

结论

标准步骤要求在进行最优性检验前，先检查是否存在退化。

例题详解 · 5

乳品加工厂运输实例

依据清楚

视频直接表达

来源依据

公式
观察依据
图示显示：'源点 S1（德里）'、'源点 S2（金奈）'、'源点 S3（印多尔）' 分别连接至 '需求点 d1（加尔各答）'、'需求点 d2（班加罗尔）'、'需求点 d3（博帕尔）'，其间标注了运输成本 c1 至 c9。
声音
观察依据
主讲人描述了一个场景：以乳品加工厂为供应源，以配送中心为目的地，并提到了德里、金奈、印多尔、加尔各答、班加罗尔、博帕尔等城市。

待核验内容

成本 c1 至 c9 的具体数值并未给出，仅以符号形式表示。

题目

将乳制品从三家加工厂（德里、金奈、印多尔）运送到三个配送中心（加尔各答、班加罗尔、博帕尔）的总成本最小化。

已知条件

供应源：S1（德里）、S2（金奈）、S3（印多尔）
目的地：d1（加尔各答）、d2（班加罗尔）、d3（博帕尔）
运输成本：c1、c2、c3、c4、c5、c6、c7、c8、c9

目标

找出使总运输成本最小的配送方案。

步骤

公式
解释
明确供应地（乳品加工厂）与目的地（配送中心）。
步骤依据
依据题目描述及图示。
视频直接表达
公式
解释
注意每一对供应地与目的地之间的运输成本（c_ij）。
步骤依据
这些成本由图中箭头上的标签表示。
视频直接表达
公式
解释
建立目标函数，使所有运输路线的（单位成本 × 运输量）之和最小。
步骤依据
这正是所定义的运输问题的核心。
依据视频推导

结果

使总成本最小的最优配送方案。

检验

本入门片段中未明确给出。

乳品加工厂到配送中心的示例

依据清楚

视频直接表达

来源依据

图示
观察依据
第一页下方的标签指出左侧分组为（乳制品厂），右侧分组为（配送中心）。
声音
观察依据
说话者将加尔各答、班加罗尔和比哈尔列为目的地城市，并讨论从多个源地供应需求 $d_1$ 。

待核验内容

本片段中未给出精确的数值型供应量与需求量，仅展示了符号化标签和路径成本。

题目

使用包含三个供应地和三个需求地的网络，来说明运输问题的建模方式及其目标函数的含义。

已知条件

三个供应地 $S_1$ 、 $S_2$ 、 $S_3$ 表示乳品加工厂。
三个需求地，其需求量分别为 $d_1$ 、 $d_2$ 、 $d_3$ ，表示配送中心。
路径成本标记为 $c_1$ 至 $c_9$ 。
需求地所在城市名称包括加尔各答、班加罗尔和比哈尔。

目标

理解供应地、需求地及单位路径成本如何共同定义运输问题及其最小化目标。

步骤

公式
解释
将供应地置于左侧，需求地置于右侧，构成一个二部运输网络。
步骤依据
这是黑板上直观绘制出的结构。
视频直接表达
公式
解释
为每条可行路径标注单位运输成本 $c_k$ 。
步骤依据
主讲人将 $c_1$ , $c_2$ , $c_3$ 分配给 $S_1$ ，并继续为 $S_4$ 分配 $c_5$ , $c_6$ for $S_2$ .
视频直接表达
公式
解释
说明某个目的地（例如 $d_1$ ）可从多个来源获得供应。
步骤依据
讲话者明确指出，需求 $d_1$ 可由多个来源供应。
视频直接表达
公式
解释
将目标表述为：寻找使运输成本最小化的最优解。
步骤依据
该表述写在同一页的‘目标（AIM）’陈述中。
视频直接表达

结果

该示例将乳品厂向配送中心的分发建模为一个成本最小化运输问题，每对源-目的地之间均附有路线成本。

检验

这一解释既与页面顶部的书面定义一致，也与底部的‘目标（AIM）’陈述一致。

用 $S_1 \to D_1$ 解释单位运输成本已知

依据清楚

视频直接表达

来源依据

公式
观察依据
白板上写有 $S_1 \to D_1$ 。
声音
观察依据
讲解者说“S1 表示从 source one 向 demand center one 运输时的单位运输成本”。

题目

说明什么是从某一供应点到某一需求点的单位运输成本已知。

已知条件

存在一个供应点 $S_1$
存在一个需求点 $D_1$
考虑从 $S_1$ 到 $D_1$ 的运输路线

目标

用具体路线示例解释第③条假设。

步骤

公式
$S_1 \rightarrow D_1$
解释
取从第1个供应点到第1个需求点的路线作为例子。
步骤依据
板书直接给出该记号。
视频直接表达
公式
解释
讲解者说明：当从 $S_1$ 向 $D_1$ 供货时，该路线上的单位运输成本必须已知。
步骤依据
音频中对 $S_1 \to D_1$ 的解释。
视频直接表达

结果

$S_1 \to D_1$ 用于表示一条具体运输路线，其单位运输成本在模型中应被视为确定且已知。

检验

该例子与第③条假设的文字描述一致。

检查 $4\times 4$ 矩阵中的退化性。

依据清楚

视频直接表达

来源依据

图示
观察依据
一个 $4\times 4$ 矩阵，其中有6个已分配的单元格。
公式
观察依据
画面上写着：( $4+4-1$ ) ≠ 6

题目

判断给定的 $4\times 4$ 运输问题是否退化。

已知条件

一个表示运输问题的 $4\times 4$ 矩阵。
已分配单元格的数量为6。

目标

检查分配数量是否等于 $m + n - 1$ 。

步骤

公式
$m = 4, n = 4$
解释
确定矩阵的维度。
步骤依据
目视观察。
视频直接表达
公式
$m + n - 1 = 4 + 4 - 1 = 7$
解释
计算非退化解所需的分配数量。
步骤依据
退化性条件的公式。
视频直接表达
公式
$Actual allocations = 6$
解释
统计矩阵中已分配单元格的数量。
步骤依据
直观计数。
视频直接表达
公式
$7 \neq 6$
解释
将计算所得数值与实际分配数量进行比较。
步骤依据
数值比较。
视频直接表达

结果

该问题为退化问题，因为分配数量（6）不等于 $m + n - 1$ （7）。

检验

通过直接套用退化条件公式，验证了该结论。

在 $4\times 4$ 网格中检查退化性

依据清楚

视频直接表达

来源依据

公式
观察依据
画面上写着： $4+4-1 = 7 \ne 6$
公式
观察依据
画面上写着：( $4+4-1$ ) ≠ 6
图示
观察依据
一个 $4\times 4$ 的网格，其中标有6个L形标记表示分配位置

题目

判断一个具有 6 个分配的 4x4 运输矩阵的基本可行解是否退化。

已知条件

行数（m）= 4
列数（n）= 4
分配数量 = 6

目标

检查分配数量是否等于 $m + n - 1$ 。

步骤

公式
$m + n - 1 = 4 + 4 - 1 = 7$
解释
计算非退化解所需的分配数量。
步骤依据
视频中给出的公式。
视频直接表达
公式
$7 \neq 6$
解释
将所需的分配数量与实际分配数量进行比较。
步骤依据
算术比较。
视频直接表达

结果

该解是退化的，因为分配数量（6）不等于 $m + n - 1$ （7）。

检验

对计算所得值7与给定分配数量6进行直观比较。

图示与动画 · 13

运输网络图

依据清楚

视频直接表达

来源依据

图示
观察依据
白板上手绘的网络图：左侧为三个供应地（S1、S2、S3），右侧为三个目的地（d1、d2、d3），各节点间以带标签的箭头连接，标签为成本（c1至c9）。

图中对象

供应点（S1、S2、S3）
需求点（d1、d2、d3）
运输路线（箭头）
运输成本（c1至c9）

不变量

供应点与需求点之间的连接结构。
每条路线上均标有对应的运输成本。

数学含义

以图示方式直观呈现货物从多个产地流向多个销地的过程，并为每一条直达运输路线标注相应的运输成本。

在运输网络中逐一点指

依据清楚

视频直接表达

来源依据

图示
观察依据
一只手持粉色笔的手，在一幅手绘网络图周围指点；图左侧有三个源节点，右侧有三个需求节点。
动画
观察依据
该笔从源节点移向目的节点，并沿各条边移动，同时讲话者依次念出成本 $c_1$ 、 $c_2$ 、 $c_3$ 等。

图中对象

源节点 $S_1$ 、 $S_2$ 、 $S_3$
目的节点标记为 1、2、3，对应的需求分别为 $d_1$ 、 $d_2$ 、 $d_3$
各条边标记为 $c_1$ ,…, $c_9$
城市标签，包括加尔各答、班加罗尔、比哈尔
底部显示 AIM 文字

变化过程

笔迹依次指示不同的起讫点路线。
关注点从单条边的成本转向整体目标陈述。

不变量

该图仍为一个三乘三的起讫点网络。
边上的标签继续表示路线成本。

数学含义

可视化讲解阐明了每条路线承载单位成本，以及整个网络如何代表一个运输分配问题。

从模型概览过渡到假设列表

依据清楚

视频直接表达

来源依据

动画
观察依据
第一页被掀开，并替换为一张新页，标题为“运输模型中的假设”。

图中对象

第一页，含网络示意图
第二页，标题为“运输模型中的假设”

变化过程

可见内容由图示示例变为一条条编号列出的假设。

不变量

主题仍是运输问题。

数学含义

翻页标志着从直观的模型构建转向正式的建模假设。

朗读假设列表

依据清楚

视频直接表达

来源依据

图示
观察依据
一份手写的编号列表列出了四项假设，其中‘Supply = Demand’和‘ $S_1$ -> $D_1$ ’用红笔书写。
动画
观察依据
笔尖先指向假设1，随后在视频末尾附近指向假设2。

待核验内容

假设4可见，但本片段中未作口头解释。

图中对象

标题：运输模型中的假设
编号条目1至4
红色批注：Supply = Demand 和 $S_1$ -> $D_1$

变化过程

笔尖强调第一项假设，同时说话人讲解供需平衡。
临近结尾时，注意力转向第二项假设。

不变量

该页面出现后，全部四项假设始终清晰可见。

数学含义

本页形式化了运输模型分析所依据的基本条件。

强调单位运输成本及其对应的具体路线示例

依据清楚

视频直接表达

来源依据

图示
观察依据
讲解者用粉色笔在“单位运输成本”下方划线，并将笔尖移至 $S_1 \to D_1$ 上。

图中对象

第三条假设的文字内容
$S_1 \to D_1$ 这一记号
粉色笔

变化过程

“单位运输成本”被划线强调
注意力转向 $S_1 \to D_1$

不变量

假设文本本身未作任何改动
$S_1 \to D_1$ 的位置保持不变

数学含义

在视觉上，将‘单位运输成本已知’这一抽象条件具象化为一条具体路线示例。

用向上箭头表示二者同向增加

依据清楚

视频直接表达

来源依据

图示
观察依据
在第四条中，讲解者在 cost 和 units 附近画出红色向上箭头。

图中对象

第④条假设文字
红色向上箭头

变化过程

cost 旁出现向上箭头
units 旁出现向上箭头

不变量

正比关系文字不变

数学含义

箭头将“directly proportional”解释为两个量同向增大。

将整体目标与 demand、supply 两端联系起来

依据清楚

视频直接表达

来源依据

图示
观察依据
讲解者在页面底部写出（Demand）和（Supply），并用连线将它们与第⑤条中的 individual supply 且 distribution centres 关联。

图中对象

第⑤条假设文字
（需求）
（供给）
连接线

变化过程

新增“需求（Demand）”与“供给（Supply）”两个词
出现连接第⑤条与这两个词的连线

不变量

第⑤条原文保持不变

数学含义

在视觉上说明运输问题同时涉及需求端和供给端，而目标是最小化整体成本，而非仅优化某一端的成本。

从假设页切换到可行解存在性页

依据清楚

视频直接表达

来源依据

动画
观察依据
画面切换至新一页，标题为“可行解的存在性（Existence of feasible solution）”

图中对象

旧页面显示假设列表
新页面标题为“可行解的存在性（Existence of feasible solution）”

变化过程

页面内容整体替换
主题由“假设（assumptions）”转向“可行性（feasibility）”

不变量

仍采用手写白板讲解形式

数学含义

结构上进入下一节：首先判断该运输问题是否存在可行解。

用勾号突出相等条件

依据清楚

视频直接表达

来源依据

图示
观察依据
总需求 = 总供给的等号上方有勾号，讲解者用笔反复指向该行。

图中对象

总需求 = 总供给
勾号
粉色笔

变化过程

笔尖多次指向等式
等号上方的勾号被强调

不变量

下方的 Total Demand ≠ Total Supply 未被打勾

数学含义

在视觉上将“相等”标为满足可行解存在条件的关键分支。

用花括号强调平衡条件

依据清楚

视频直接表达

来源依据

图示
观察依据
讲解者在 Demand = Supply 两侧画红色花括号，并指向该等式。

图中对象

需求 = 供给
红色花括号
粉色笔

变化过程

等式两侧被括号圈出
讲解者反复指向该条件

不变量

b) 非平衡运输问题中 Demand ≠ Supply 保持未加同类强调

数学含义

视觉上突出平衡运输问题的判定核心就是需求与供给相等。

运输问题表格的绘制与标注

依据清楚

视频直接表达

来源依据

动画
观察依据
讲解者在白板上逐步绘制并标注了运输问题的表格结构，包括行、列、供给、需求以及单元格的含义。

图中对象

$4\times 4$ 网格表格
工厂标签
配送中心标签
供给标签
需求标签
单元格图例
已分配单元格图例

变化过程

从零开始绘制表格
添加行与列标签
添加供给与需求符号
解释单元格的含义

不变量

表格保持 $4\times 4$ 结构

数学含义

直观展示了运输问题数学模型的表格化表示方法。

绘制并标记运输矩阵

依据清楚

视频直接表达

来源依据

图示
观察依据
绘制一个 $4\times 4$ 的网格，并在其中6个单元格内标记小方块以表示分配。

图中对象

$4\times 4$ 网格
已分配单元格

变化过程

网格已绘制完成。
六个单元格被标记为已分配。

不变量

在整个片段中，网格始终保持为 $4\times 4$ 。

数学含义

直观图示有助于统计分配数量，以检验是否退化。

易错点 · 3

混淆现实世界中的供需不平衡与标准模型的假设

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，现实中几乎任何情况都可能发生，例如机器故障会中断生产并减少供应，但在该模型中，我们假设供应量等于需求量。

误区

有人可能认为，由于实际系统可能遭遇扰动，运输模型必须始终允许供应与需求不相等。

说明

本视频区分了实际中的可变性与建模假设：此处讨论的标准运输模型假设总供应量等于总需求量。

误以为运输问题只最小化单个供应点或单个配送中心的成本

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者强调目标是使整个组织的总运输成本最小化，而不是仅最小化某一个供应点或某一条运输路线的成本。
图示
观察依据
讲解者将 (Demand) 和 (Supply) 与 individual supply 且 distribution centres 连起来，帮助区分整体与局部。

误区

把目标理解成只优化某一个 supply centre 或某一个 distribution centre 的成本。

说明

视频明确指出目标是最小化整个组织的 total transportation cost，而不是 individual supply 且 distribution centres 的成本。

忽略先检查总供需是否相等

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者说“每次我们解题时，首先要做的就是查看〔Demand〕和〔Supply〕”。

误区

拿到运输问题后直接求解，而不先比较总需求与总供应。

说明

视频强调每次做运输问题时，第一步都应先看需求与供应是否相等。

概念关系 · 15

运输问题的定义 → 线性规划的概念

依据清楚

视频直接表达

来源依据

公式
观察依据
书面定义写道：‘运输问题是一类特殊的线性规划问题（LPP）’。
声音
观察依据
讲解者说：‘运输问题是一类特殊的线性规划问题’。

特例

解释

运输问题被表述为一般线性规划问题的一种具体应用或子类。

运输问题的定义 → 供应地、目的地及路线成本的网络表示

依据清楚

视频直接表达

来源依据

公式
观察依据
页面顶部的定义提到了供应点与需求点，下方图示则将它们具体化为 $S_i$ 和 $d_j$ ，并标出了各条路线的成本。

应用

解释

运输问题的抽象定义通过一张具体的网络图得以应用，图中展示了供应点、需求点以及各条路线的成本。

供应地、目的地及路线成本的网络表示 → 运输问题的目标

依据清楚

视频直接表达

来源依据

图示
观察依据
在梳理完各条路线的成本后，笔尖移至同一页底部的“目标（AIM）”陈述处。

先修

解释

理解路线成本网络是解读“最小化总运输成本”这一优化目标的前提。

运输问题的目标 → 假设1：供需平衡

依据清楚

视频直接表达

来源依据

动画
观察依据
页面内容从“目标（AIM）”陈述切换至“运输模型的假设”列表。

证明依赖

解释

优化目标随后被置于明确的建模假设之下，首条即为总供应量与总需求量的平衡。

假设3：单位运输成本已知。 → 假设4：成本与运输量成正比

依据清楚

视频直接表达

来源依据

公式
观察依据
假设3指出单位运输成本已知；假设4指出路线成本与运输单位数量成正比。

先修

解释

路线运费与运货量成正比，这一前提假设该路线的单位运费已经确定。

运输模型假设③：单位运输成本确定且已知 → 用 $S_1 \to D_1$ 解释单位运输成本已知

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者在读第③条后立刻用 $S_1 \to D_1$ 举例。
公式
观察依据
$S_1 \to D_1$ 写在第③条旁边。

应用

解释

$S_1 \to D_1$ 是对“单位运输成本已知”这一抽象假设的具体应用示例。

运输模型假设④：路线运输成本与发运量成正比 → 正比关系的直观说明

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者把第④条解释为数量增加则成本增加。
图示
观察依据
向上箭头配合口头解释出现。

证明依赖

解释

直观推导依赖第④条“正比”假设，用来说明两个变量同向变化。

运输模型假设⑤：目标是整体总运输成本最小化 → 运输问题可行解存在条件

依据清楚

视频直接表达

来源依据

动画
观察依据
页面从假设（assumptions）切换到可行解的存在性（Existence of feasible solution）。
声音
观察依据
讲解者先总结需求与供应是问题核心，再进入下一主题：可行解的存在性。

先修

解释

视频把运输问题理解为围绕需求与供应的整体成本最小化，随后才进入基于总需求与总供应比较的可行性判断。

运输问题可行解存在条件 → 运输问题的两类：平衡与不平衡

依据清楚

视频直接表达

来源依据

公式
观察依据
同一页上先写‘可行解的存在性’与‘总需求 = 总供给’，再写‘运输问题的类型’及‘供需平衡/不平衡’条件。
声音
观察依据
讲解者先说明当供需相等时可行解存在，再说明运输问题的类型分为平衡型与非平衡型。

包含

解释

可行解存在性的判断标准，直接引出了依据供需是否相等对运输问题进行的分类。

运输问题的两类：平衡与不平衡 → 平衡运输问题的定义

依据清楚

视频直接表达

来源依据

公式
观察依据
a) 平衡运输问题对应需求 = 供给，b) 非平衡运输问题对应需求 ≠ 供给。

对比

解释

在同一分类框架下，平衡型与非平衡型通过需求与供给是否相等形成对照。

平衡运输问题与不平衡运输问题 → 通过添加虚拟行或虚拟列实现运输问题的平衡

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者说明将不平衡问题转化为平衡问题的方法是添加虚拟行或虚拟列。

应用

解释

添加虚拟行/列的方法应用于不平衡运输问题，以将其转化为平衡问题。

运输问题的表格（矩阵）形式 → 寻找初始基本可行解的方法

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者在介绍完表格后，紧接着列出了求解方法。

先修

解释

建立运输问题的表格是应用各种初始基本可行解方法的前提。

问题定位 · 23

运输问题的定义是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
运输问题的定义书写在黑板上。
声音
观察依据
讲解者对运输问题作出定义。

涉及知识点

运输问题的定义

运输问题与线性规划之间有何关联？

依据清楚

视频直接表达

来源依据

公式
观察依据
定义指出，运输问题（TP）是一种‘特殊的线性规划问题（LPP）’。
声音
观察依据
讲解者说明运输问题（TP）是线性规划（LP）的一种特殊类型。

涉及知识点

运输问题的定义
线性规划的概念
s0-rel-tp-lpp

线性规划中的运输问题是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
页面顶部的定义文字可见。

涉及知识点

运输问题的定义
供应地、目的地及路线成本的网络表示

图中箭头上标注的 $c_1$ 、 $c_2$ …… 等标签表示什么？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人将 $c_1$ 、 $c_2$ 、 $c_3$ 分配给从 $S_1$ 出发的各条路线，并继续用 $c_4$ 、 $c_5$ 、 $c_6$ 表示从 $S_2$ 出发的各条路线。

涉及知识点

供应地、目的地及路线成本的网络表示
从网络图中读取路线成本

求解运输问题的目标是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
第一页底部的“目标陈述”（AIM statement）。

涉及知识点

运输问题的目标
运输问题旨在寻求一种最优的最低成本分配方案。

为什么运输模型要假设供应量等于需求量？

依据清楚

视频直接表达

来源依据

公式
观察依据
假设1的文字内容及“供应量 = 需求量”的注释。
声音
观察依据
主讲人解释说，尽管现实中可能出现供需失衡等实际干扰，该模型仍假设供应量等于需求量。

涉及知识点

假设1：供需平衡
标准运输模型假设总供应量等于总需求量
混淆现实世界中的供需不平衡与标准模型的假设

运输模型的标准假设有哪些？

依据清楚

视频直接表达

来源依据

公式
观察依据
第二页上列出了四条编号的假设。

待核验内容

本片段中仅清晰讨论了假设1和假设2的开头部分。

涉及知识点

假设1：供需平衡
假设2：所有运输路线均可使用。
假设3：单位运输成本已知。
假设4：成本与运输量成正比

运输模型的第③条假设是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
第③条假设文字清晰可见。
声音
观察依据
讲解者逐句读出并解释该条。

涉及知识点

运输模型假设③：单位运输成本确定且已知

为什么板书要写 $S_1 \to D_1$ ？

依据清楚

视频直接表达

来源依据

公式
观察依据
$S_1 \to D_1$ 写在第③条旁边。
声音
观察依据
讲解者用它举例说明单位运输成本已知。

涉及知识点

运输模型假设③：单位运输成本确定且已知
用 $S_1 \to D_1$ 解释单位运输成本已知

“运输成本与发运量成正比”在这里是什么意思？

依据清楚

视频直接表达

来源依据

公式
观察依据
第④条写明‘与该路径上运送的单位数量成正比’。
图示
观察依据
向上箭头表示同向增加。

涉及知识点

运输模型假设④：路线运输成本与发运量成正比
正比关系的直观说明

运输问题的目标是最小化谁的成本？

依据清楚

视频直接表达

来源依据

公式
观察依据
第⑤条写明目标是使整个组织的总运输成本最小化。
声音
观察依据
讲解者强调不是针对各个独立的供应中心和分销中心。

涉及知识点

运输模型假设⑤：目标是整体总运输成本最小化
误以为运输问题只最小化单个供应点或单个配送中心的成本

什么时候可以说运输问题存在可行解？

依据清楚

视频直接表达

来源依据

公式
观察依据
Total Demand = Total Supply 后面写着 Then feasible solution exist for transportation problem。
声音
观察依据
讲解者明确说相等时可行解存在。

涉及知识点

运输问题可行解存在条件
若总需求等于总供给，则运输问题存在可行解

覆盖情况与待核验内容

已覆盖 · 本段内容整体介绍了运输问题、其定义、它与线性规划的关系，并通过一张网络图提供了直观示例。

已覆盖 · 第一页介绍运输问题，展示了一个包含三个产地和三个销地的网络图，并标出各条路线的成本，同时说明了最小化目标。

已覆盖 · 画面从网络示例过渡到假设列表。

已覆盖 · 第二页列出了四项假设；讲解者解释了供需平衡，并在片段结束前开始阐述第二项假设。

已覆盖 · 讲解第②条假设：所有供应点到所有目的地都可方便运输。

已覆盖 · 讲解第③条假设，并用 $S_1 \to D_1$ 举例说明单位运输成本已知。

已覆盖 · 讲解第④条假设：路线成本与发运量成正比，并用向上箭头作直观说明。

已覆盖 · 讲解第⑤条假设：目标是最小化整体总运输成本，并区分整体与个别供应、配送中心。

已覆盖 · 页面切换，无新增数学内容。

已覆盖 · 进入可行解存在性，说明总需求等于总供应时存在可行解。

已覆盖 · 列出运输问题类型：供需平衡型与供需不平衡型，并强调先检查供需是否相等。

已覆盖 · 片段末尾仍停留在运输问题类型页面，无新的可辨数学内容。

已覆盖 · 讲解平衡与不平衡运输问题的定义及转化方法。

已覆盖 · 详细讲解并绘制运输问题的表格（矩阵）形式。

已覆盖 · 列出寻找初始基本可行解的五种方法。

已覆盖 · 求初始基可行解的各类方法简介。

已覆盖 · 最优性检验方法简介。

已覆盖 · 运输问题中退化现象的解释与示例。

已覆盖 · 本片段完整涵盖退化的定义、判定条件 $m+n-1$ 、该条件的检验示例，以及运输问题求解的逻辑流程。

探索视频中的知识

打开视频知识图谱 →

运输与指派问题讲解定位 0:00
查看关联依据
已审核中文素材 v3：知识卡片（概念卡片）「定义：运输问题」从 0:00 起——运输问题是线性规划（LPP）的一种特殊类型。其主要目标是将产品从多个供应源（如工厂或乳品加工厂）运送到多个目的地（如仓库或配送中心），使得总运输成本最小。 $\text{Objective: Minimize Cost of Distribution}$
线性规划模型讲解定位 0:17
查看关联依据
已审核中文素材 v3：知识卡片（概念卡片）「线性规划（LPP）的概念」从 0:17 起——线性规划是一种对有限资源进行优化配置的数学方法。其目标是使收益最大化，或使成本最小化。运输问题正是其中一种特定应用，其目标是最小化运输成本。

运输问题简介

把讲解展开来看。

章节

学习解说文稿

知识卡片

定义：运输问题

线性规划（LPP）的概念

示例：乳品加工厂与配送中心

运输问题的定义

带路径成本的网络图示

目标：最小化总运输成本

假设1：模型是平衡的

假设2：所有供应地到需求地的运输路线都是可行的

假设3：单位运输成本完全已知

假设4：运输成本随发货数量线性变化

运输模型假设②：所有供应点到所有目的地均可运输

运输模型假设③：单位运输成本确定且已知

用S1→D1S_1 \rightarrow D_1S1​→D1​解释一条具体运输路线

运输模型假设④：路线成本与发运量成正比

运输模型假设⑤：最小化整体总运输成本

常见误区：不要把目标理解成单个中心成本最小

可行解存在性的判断方法

平衡运输问题与不平衡运输问题

解题的第一步：先检查需求量与供应量

平衡与不平衡运输问题

虚拟行/列的使用

运输问题表格（矩阵）结构

初始基本可行解的求解方法

初始基本可行解的求解方法

详细学习笔记

LPP

SiS_iSi​

djd_jdj​

c_{ij}

SiS_iSi​

djd_jdj​

Destination cities

c_{ij}

Supply = Demand

S1→D1S_1 \rightarrow D_1S1​→D1​

Supply = Demand

S1→D1S_1 \to D_1S1​→D1​

运输问题的定义

线性规划的概念

运输问题的定义

供应地、目的地及路线成本的网络表示

运输问题的目标

假设1：供需平衡

假设2：所有运输路线均可使用。

假设3：单位运输成本已知。

假设4：成本与运输量成正比

运输模型假设②：任意供应点到任意需求点均可运输

运输模型假设③：单位运输成本确定且已知

运输模型假设④：路线运输成本与发运量成正比

标准运输模型假设总供应量等于总需求量

运输问题旨在寻求一种最优的最低成本分配方案。

若总需求等于总供给，则运输问题存在可行解

平衡运输问题的定义

必须在最优性检验之前解决退化问题

从网络图中读取路线成本

正比关系的直观说明

检验退化性的示例

求解运输问题的逻辑流程。

乳品加工厂运输实例

乳品加工厂到配送中心的示例

用 S1→D1S_1 \to D_1S1​→D1​ 解释单位运输成本已知

检查4×44\times 44×4矩阵中的退化性。

在4×44\times 44×4网格中检查退化性

运输网络图

在运输网络中逐一点指

从模型概览过渡到假设列表

朗读假设列表

强调单位运输成本及其对应的具体路线示例

用向上箭头表示二者同向增加

将整体目标与 demand、supply 两端联系起来

从假设页切换到可行解存在性页

用勾号突出相等条件

用花括号强调平衡条件

运输问题表格的绘制与标注

绘制并标记运输矩阵

用 $S_1 \rightarrow D_1$ 解释一条具体运输路线

$S_i$

$d_j$

$S_i$

$d_j$

$S_1 \rightarrow D_1$

$S_1 \to D_1$

用 $S_1 \to D_1$ 解释单位运输成本已知

检查 $4\times 4$ 矩阵中的退化性。

在 $4\times 4$ 网格中检查退化性

运输模型假设③：单位运输成本确定且已知 → 用 $S_1 \to D_1$ 解释单位运输成本已知

图中箭头上标注的 $c_1$ 、 $c_2$ …… 等标签表示什么？

为什么板书要写 $S_1 \to D_1$ ？