第一次接触伏格尔法是在运筹学课程设计里做运输问题时。当时我拿同一张3个产地、4个销地的运输表分别用西北角法、最小元素法和伏格尔法算初始调运方案再配合位势法检验。结果是西北角法初始费用710后续还要闭回路调整最小元素法初始费用720检验数里有两个负数同样要迭代伏格尔法一张表算完初始方案总费用670位势法一验所有检验数非负直接就是最优解。从那天起我就意识到伏格尔法不是“西北角法换了个填表顺序”而是一个真正把机会成本考虑进去的启发式算法。这篇文章就围绕伏格尔法展开把运输问题的建模、罚数逻辑、手算全过程、位势法验证、退化处理和代码实现一起讲透适合正在学运筹学的学生、准备考研刷题的人以及需要手工排调拨计划的一线计划员。1. 先理解运输问题在求什么别把伏格尔法当成孤立的填表技巧1.1 一个具体的调运场景先给一个贯穿全文的例子。假设某公司有3个产地产量分别是50、60、40有4个销地需求量分别是30、40、50、30。单位运输成本如下表产地\销地B1B2B3B4产量A1346750A2653860A3485940销量30405030150总产量506040150总销量30405030150产销平衡。我们要决定每个产地往每个销地送多少货让总运输成本最低。这个“往哪送、送多少”的问题就是运输问题。很多人第一次做这种题第一反应是“哪个格子便宜就往哪个格子塞”。听起来合理但实际做起来会发现只顾着填便宜的格子往往会让后面的贵格子被迫承担大量运输。运输问题真正的难点不是“找便宜格”而是“在全局约束下组合出总成本最低的方案”。1.2 数学模型它到底在求什么如果用数学语言写运输问题长这样。设x_ij表示从产地 i 运往销地 j 的数量c_ij是对应的单位运价则目标函数是总运输成本min Z ΣΣ c_ij * x_ij (对所有 i、j 求和)约束条件有两个Σ_j x_ij a_i 每个产地 i 的运出量等于其产量 Σ_i x_ij b_j 每个销地 j 的收货量等于其需求量 x_ij ≥ 0 运量不能为负这个模型本身不复杂但它揭示了一个关键信息运输问题是带线性约束的优化问题。由于约束矩阵的特殊结构它不需要用通用单纯形法去硬解而是可以用“表上作业法”这套手算流程来求解。表上作业法分两大步第一步先生成一个初始可行方案第二步反复检验并改进直到最优。伏格尔法就是“生成初始可行方案”阶段最值得掌握的方法。它不是直接求最终答案而是给后续迭代提供一个质量尽量高的起点。起点越接近最优解后续调整轮数就越少这就是伏格尔法最大的实用价值。1.3 表上作业法的完整链条表上作业法的完整流程可以概括为四步用某个方法生成初始调运方案常用的是西北角法、最小元素法和伏格尔法。用位势法或闭回路法计算检验数判断当前方案是否最优。如果存在负检验数找闭回路调整运量获得更好的方案。重复第2、3步直到所有检验数非负。注意一个常被忽略的点第1步的任何初始方案都必须满足“基变量个数等于 mn-1”m为产地数n为销地数。这是后面位势法能正常计算的前提。伏格尔法手算时通常能自然满足这个条件但在某些特殊情况下会退化需要补零处理这个我放在后面专门讲。2. 罚数是伏格尔法的眼睛为什么它能避开最小元素法的短视2.1 最小元素法的“捡芝麻丢西瓜”困境先说说为什么最小元素法经常不靠谱。最小元素法的操作很简单每次都找当前全表里运价最小的格子尽可能多分配。按这个逻辑上表中A1到B1的运价是3A2到B3的运价也是3先填这两格再填运价4的格子。问题是一个格子被优先满足后它所在的“产地行”或“销地列”可能被整体划去导致后续某些格子失去选择余地。举一个极端情况的例子如果某个产地到某销地的运价是全场最低的1但把这个产地全部产能填过去后另一个销地只能从一个运价高达100的产地进货那总成本就崩了。最小元素法只看“当前格子便宜不便宜”不看“这个选择会不会把后面逼入绝境”。伏格尔法恰恰是在这一点上做了改进。它不再盯着单个格子看而是看“每一行、每一列如果不优先处理未来要多花多少钱”。这个“多花的钱”就是罚数。2.2 罚数到底在算什么罚数的计算规则很简单对每一行找到该行当前未划去格子中的最小运价和次小运价两者相减差就是该行的罚数对每一列也一样。为什么最小和次小的差有意义想象一下某一行现在还能选的格子里最便宜的是5第二便宜的是9。如果这一行不在本轮被优先分配之后便宜的5可能被别人抢走那时这一行只能去选9每单位就多付4块钱。这个4就是“如果拖延要付出的代价”也就是机会成本。反过来说如果某行的最小运价是5次小是5.1差只有0.1那这行早处理晚处理都差不多优先级就不高。伏格尔法每次选出当前所有行列中罚数最大的那个行或列优先处理它对便宜格的需求本质上是优先消除“最可能吃亏”的风险。2.3 最大罚数决定了“先动谁”理解了罚数伏格尔法的操作逻辑就顺了。每一步都做三件事计算所有未划去行、未划去列的罚数找出所有罚数中的最大值在罚数最大的那一行或列里选择运价最小的格子尽可能多地分配运量。如果最大罚数同时出现在几个行或列里任选一个即可。不要在这种地方纠结后面我会专门说为什么并列选择对最终结果没有实质影响。这里顺便回应一个常见疑问罚数计算一定要基于“当前还未被划去”的格子。因为已经被划去的行或列意味着产能或需求已经满足后续不会再参与运输当然不能继续作为候选。很多刚上手的人会忘记重新计算罚数导致后续分配脱离实际约束。3. 手工计算全流程一张3×4运输表从零算到尾3.1 初始数据与第一轮分配回到1.1节的表。开始前准备一张草稿表建议用铅笔写因为划行划列经常要改。初始所有行、所有列都在候选范围内。第一轮先计算所有行和列的罚数。行罚数A1行当前最小运价3次小4罚数1A2行当前最小3次小5罚数2A3行当前最小4次小5罚数1列罚数B1列当前最小3次小4罚数1B2列当前最小4次小5罚数1B3列当前最小3次小5罚数2B4列当前最小7次小8罚数1最大罚数是2同时出现在A2行和B3列。任选A2行处理。A2行内最小运价格是A2B3运价3。A2产量60B3销量50分配量取两者较小值也就是50。把50填入A2B3此时B3的需求被满足划去B3列A2还剩10的产量继续参与后续分配。3.2 划行划列后必须重新算罚数第一轮分配完成后表格发生变化B3列被划去剩余可选的列是B1、B2、B4。很多人在这里犯的第一个错误是继续用一开始算好的罚数往下做这是不对的一定要按当前剩余格重新计算。第二轮罚数如下行罚数A1行可选3、4、7最小3次小4罚数1A2行可选6、5、8最小5次小6罚数1A3行可选4、8、9最小4次小8罚数4列罚数B1列3、6、4最小3次小4罚数1B2列4、5、8最小4次小5罚数1B4列7、8、9最小7次小8罚数1最大罚数是4来自A3行。A3行内最小运价格是A3B1运价4。A3产量40B1销量30分配30。B1需求清零划去B1列A3剩余10。第三轮继续重算。剩余未划去的列只剩B2、B4。行罚数A1行4、7罚数3A2行5、8罚数3A3行8、9罚数1列罚数B2列4、5、8罚数1B4列7、8、9罚数1最大罚数是3A1行和A2行并列。选A1行。A1行内最小运价格是A1B2运价4。A1产量50B2销量40分配40。B2需求清零划去B2列A1剩余10。3.3 收尾分配与方案核验三轮之后表中只剩B4列没有满足需求量30。此时A1、A2、A3各自还剩10的产量正好给B4补上各自分配10。最终方案如下产地\销地B1B2B3B4A1-40-10A2--5010A330--10总费用计算A1: 40*4 10*7 160 70 230 A2: 50*3 10*8 150 80 230 A3: 30*4 10*9 120 90 210 总计 230 230 210 670基变量个数核验记录运量的格子有6个分别是A1B2、A1B4、A2B3、A2B4、A3B1、A3B4。mn-134-16数量刚好非退化。此时可以放心做最优性检验。4. 拿到初始方案之后位势法检验才是判断最优的裁判4.1 位势法的原理与快速手算伏格尔法只能保证初始方案质量较高不能保证它就是最优。想确认要不要继续调整必须用位势法算检验数。位势法的原理不复杂对每个产地i设一个位势值u_i对每个销地j设一个位势值v_j让所有基变量格子满足 u_i v_j c_ij。因为基变量个数正好是mn-1所以可以解出全部位势值。手算时通常先令某个u为0再逐个推。以本文伏格尔法得到的方案为例基变量格子A1B2运价4A1B4运价7A2B3运价3A2B4运价8A3B1运价4A3B4运价9令u10从A1B2得v24从A1B4得v47再从A2B4得u21从A2B3得v32从A3B4得u32从A3B1得v12。求非基变量格子的检验数公式是检验数 c_ij - (u_i v_j)A1B13-(02)1非负A1B36-(02)4非负A2B16-(12)3非负A2B25-(14)0非负A3B28-(24)2非负A3B35-(22)1非负所有检验数都大于等于0当前方案就是最优方案。所以本文例子中伏格尔法一步到位直接给出了最优解。4.2 出现负检验数时的闭回路调整如果检验数里有负数说明当前方案还有改进空间需要通过闭回路调整。做法是从负检验数格子出发沿水平或垂直方向找一条只经过基变量格子的闭合回路然后按“奇偶交替加减”的方式调整运量。调整量取回路上偶数顶点处的最小运量调整后总费用会下降然后重新做位势法检验直到所有检验数非负。这一步要提醒的是闭回路的寻找虽然听着抽象但手算时就是对着表格画回头路。我一般建议初学的人把基变量格用圆圈标出来从待检验格出发沿行或列找“能拐弯”的基变量格直到回到起点。大多数情况下闭回路是唯一的。4.3 三种初始方案在同一张表上的实际表现我用同一个例子算了一遍三种方法的初始方案对比太直观了初始方案生成方法初始总费用检验结果后续工作量西北角法710至少存在1个负检验数需要闭回路调整最小元素法720存在2个负检验数-3、-1需要闭回路迭代伏格尔法670全部检验数非负无需调整最小元素法的初始方案反而比西北角法贵这个现象在运输问题里并不罕见。它说明了一个道理退一步讲即使某个启发式方法名字里有“最小”“最优”它生成的也只是初始可行解质量高低要由检验数说了算。伏格尔法在这个例子里能直接封顶是因为罚数机制考虑了全局的机会成本但这不是绝对的换了别的数据它仍然可能不是最优。所以哪怕你用了伏格尔法位势法检验这步也绝对不能省。5. 退化、罚数并列与产销不平衡高频边缘问题一次讲清5.1 基变量不够怎么办补零前面说过每个初始可行方案都要求基变量个数等于mn-1。伏格尔法在大多数情况下能自然满足这个要求但如果某次分配后某个产地的剩余产量和某个销地的剩余需求恰好同时变为0行和列就会同时被划去基变量个数因此少1这就是退化。遇到退化不要慌处理办法是补零在同时被划去的某一行或某一列中找一个空格填上0把它视为基变量。这个0不占用实际运量但能让基变量个数恢复到mn-1保证位势法有足够的方程可解。补零格怎么选优先选运价较低的格子或者选方便后面计算检验数的位置。如果一时看不出哪个好任选一个能解出位势值的位置都行。因为0运量不改变总费用只影响计算结构。5.2 罚数并列时怎么选都不会错伏格尔法手算时经常遇到最大罚数并列的情况。本文例子的第一轮就出现了A2行的罚数是2B3列的罚数也是2。我处理时选了A2行后面第三轮又遇到A1行和A2行罚数都是3还是随便选的。根据我的经验罚数并列时选哪个不影响最终最优解。原因在于初始方案只决定“从哪个起点出发”不是“直接落在哪里”。哪怕你选的并列支路导致初始费用稍差位势法后面的迭代也会把方案一步步拉回最优。所以我建议并列时选最容易算的那个或者选你当前觉得最顺手的那个不用为了“最优起点”反复试。考试和实际排计划时间都要花在刀刃上。5.3 产销不平衡问题怎么处理很多人做的运输问题不一定是产销平衡的。处理思路是加虚拟节点总产量大于总销量时增加一个虚拟销地其需求量为产量与销量之差所有产地到虚拟销地的运价设为0。虚拟销地吸收的量等于实际没有被运出去的库存。总销量大于总产量时增加一个虚拟产地其产量为销量与产量之差虚拟产地的运价也设为0。虚拟产地向某个销地供应的量表示该销地实际未被满足的需求。顺带说一个实操经验虚拟行列的运价是0在伏格尔法计算罚数时会很显眼容易被优先分配。这本身不算错因为它只是一个初始方案。但如果你希望手算时少一些干扰可以先用伏格尔法只处理真实行列最后把虚拟行列的差额直接补上。两种做法的最终最优解一致选择哪种视你的习惯而定。6. 用Python实现伏格尔法重复劳动交给代码6.1 数据如何组织如果数据规模变大手工算伏格尔法会很折磨人。几十行几十列的表光罚数重算就够喝一壶。这种时候不如写一段小代码。实现伏格尔法的核心是维护三样东西成本矩阵、剩余产量数组、剩余需求数组再加上两个布尔数组标记哪些行和列还没被划去。每次迭代先计算未划去行列的罚数找最大罚数对应的行或列再在该行或列中选最小成本格分配运量最后更新剩余产量、需求以及行/列状态。循环直到所有需求都满足、所有产量都被分配完。6.2 核心代码我用Python写了一个可以直接运行的版本逻辑和手工计算完全对应import numpy as np def vogel_approx(cost, supply, demand): cost np.array(cost, dtypefloat) supply supply.copy() demand demand.copy() m, n cost.shape shipment np.zeros((m, n), dtypefloat) active_rows [True] * m active_cols [True] * n while True: if not any(active_rows) or not any(active_cols): break row_penalty [] for i in range(m): if not active_rows[i]: row_penalty.append(-1) continue vals [cost[i][j] for j in range(n) if active_cols[j]] if len(vals) 2: row_penalty.append(0) else: sorted_vals sorted(vals) row_penalty.append(sorted_vals[1] - sorted_vals[0]) col_penalty [] for j in range(n): if not active_cols[j]: col_penalty.append(-1) continue vals [cost[i][j] for i in range(m) if active_rows[i]] if len(vals) 2: col_penalty.append(0) else: sorted_vals sorted(vals) col_penalty.append(sorted_vals[1] - sorted_vals[0]) max_penalty -1 selected_type None selected_row -1 selected_col -1 for i in range(m): if active_rows[i] and row_penalty[i] max_penalty: max_penalty row_penalty[i] selected_type row selected_row i for j in range(n): if active_cols[j] and col_penalty[j] max_penalty: max_penalty col_penalty[j] selected_type col selected_col j if selected_type row: i selected_row avail_cols [j for j in range(n) if active_cols[j]] min_cost min(cost[i][j] for j in avail_cols) j next(j for j in avail_cols if cost[i][j] min_cost) else: j selected_col avail_rows [i for i in range(m) if active_rows[i]] min_cost min(cost[i][j] for i in avail_rows) i next(i for i in avail_rows if cost[i][j] min_cost) amount min(supply[i], demand[j]) shipment[i][j] amount supply[i] - amount demand[j] - amount if supply[i] 0: active_rows[i] False if demand[j] 0: active_cols[j] False total_cost np.sum(shipment * cost) return shipment, total_cost if __name__ __main__: cost [ [3, 4, 6, 7], [6, 5, 3, 8], [4, 8, 5, 9], ] supply [50, 60, 40] demand [30, 40, 50, 30] shipment, total_cost vogel_approx(cost, supply, demand) print(shipment) print(总费用:, total_cost)6.3 运行结果与退化场景提醒跑上面这段代码输出如下[[ 0. 40. 0. 10.] [ 0. 0. 50. 10.] [30. 0. 0. 10.]] 总费用: 670.0和手工计算完全一致。代码中的if supply[i] 0和if demand[j] 0会分别处理行和列的划去。如果某次分配时两者同时归零两个状态会同时被置为False此时基变量个数就会不够。真实场景中如果遇到这种情况建议在代码里增加一个判断当供需同时归零时手动记录一个0运量格子作为退化基变量。否则后续如果继续做位势法检验基变量个数不满足mn-1求解位势值时方程会不够。6.4 一点使用体会我在实际研究里习惯把伏格尔法输出的初始方案再交给线性规划库求最终最优解相当于用伏格尔法做一个高质量初始点。但如果你就是纯手工做题我的经验是全程用铅笔在表格里演算划行划列错了还能改回来。还有一个小技巧每次分配完一个格子后先在旁边草稿纸上列出当前所有行和列的剩余可选格再算罚数不容易漏算。另外别被“伏格尔法初始费用低”这个优点冲昏头脑。它仍然只是启发式方法理论上存在初始方案不是最优的可能。凡是遇到运输问题的考试题、面试题、实际排产题位势法检验或线性规划验证一道都不能少。表格数据一旦超过8行8列手工伏格尔法加位势法的组合就会非常吃力这时候直接用代码处理才是常态。说到底伏格尔法是一个让你理解运输问题结构的好工具也是一个能大幅减少迭代次数的好起点但它始终不是决策的终点。