【doc】闭回路算法.doc

【闭回路算法】是运筹学中解决运输问题的一种方法，主要应用于线性规划问题。运输问题涉及在不同产地和销地之间有效地分配资源，以最小化运输成本。闭回路算法是一种简化了的计算策略，相比单纯形法，它在解决这类问题时更加直接。 在运输问题的计算表格中，闭回路是由一系列数字格构成的路径，从方格(k,t)出发，沿着水平或垂直方向前进，每次遇到合适的数字格后转90度继续前进，直至回到起点(k,t)。这种路径称为闭回路。在表上作业法中，闭回路扮演着核心角色，它不仅用于计算检验数，还帮助优化运输方案。检验数是判断当前解决方案是否最优的关键指标。 闭回路算法通常包括两个主要步骤： 1. **确定初始方案的最小元素法**： - 找出计算表中单位运价最小的元素，将其设置为基变量，并在对应格子中标记。 - 如果有多个单位运价相同且最小，可以选择其中之一。 - 接下来，根据产量(a)和销量(b)的关系调整行或列，如：如果销量小于产量，则减少销量；如果产量大于销量，则减少产量。若两者相等，可选择将销量或产量归零，但不能同时为零（除非是最后一个操作）。 - 这个过程一直持续到所有行和列都被处理完。 2. **求检验数的闭回路法**： - 对每个空格，检查其所在行和列，找到数字格，将它们压入堆栈，并记录开始空格。 - 从堆栈中弹出一个数字格，创建新节点，连接到指针链表中，并确定新方向（与原方向垂直）。 - 如果当前方向能返回起点，闭回路找到，算法结束。 - 如果不能返回起点，但能找到数字格，将该数字格压入堆栈，更新当前节点的上一格。 - 若两者都无法做到，表示搜索失败，返回第二步继续搜索。 在计算机实现中，闭回路算法涉及数据结构如堆栈和链表，以及一些特定的函数，如PushIn、PopOut、FreeChain和Backable等，用于压栈、弹栈、释放链表和判断是否可以返回起点。此外，NumBox函数用于检查给定位置是否为数字格。 闭回路算法是解决运输问题的高效工具，通过寻找和处理闭回路来优化运输方案，从而达到最小化成本的目标。它与人类的手工做法相对应，但通过计算机实现可以快速、准确地完成计算，节省时间和资源。