运筹学第三章：运输问题详解与求解方法

"本文档是运筹学教程第5版第三章——运输问题的学习笔记，讲解了运输问题的数学模型、特点以及如何用表上作业法求解，涉及最小元素法、沃格尔法、闭回路法和位势法。" 运输问题在运筹学中是一种常见的线性规划问题，它涉及到从多个来源（产地）向多个目的地（销地）分配资源，以最小化成本或最大化收益。运输问题的数学模型通常表现为一个线性规划问题，目标是最小化总运输成本。 模型由以下组成部分构成： 1. 目标函数：`minz= m∑i=1n∑j=1cijxij`，其中`cij`是产地i到销地j的单位运输成本，`xij`是运输量。 2. 约束条件：每个产地的供应量之和（`m∑i=1xij=ai`）需等于销地的需求量之和（`n∑j=1xij=bj`），且所有`xij`均为非负值。 3. 产销平衡：总供应量等于总需求量，即`m∑i=1ai=n∑j=1bj`。 运输问题有以下特点： 1. 存在有界最优解，即目标函数有下界，不会趋向负无穷。 2. 系数矩阵的特殊结构，每列有两个非零元素，对应变量在供应约束和需求约束中各出现一次。 3. 对于产销平衡问题，所有结构约束为等式，且总供应与总需求相等。 4. 解的性质包括满足所有约束、基变量的线性无关性以及非零变量的数量限制。 解决运输问题的一种方法是表上作业法，它通过迭代找到最优解。此方法包括以下步骤： 1. 初始化：找到运输问题的初始可行解，例如使用最小元素法或沃格尔法。 2. 检验数计算：使用闭回路法或位势法求解检验数，以确定是否可以改进当前解。 3. 改进解：如果找到负检验数，说明存在可优化的空间，通过调整运输量来降低总成本。 4. 迭代过程：持续检查和调整，直至无法找到负检验数，此时得到的解即为最优解。 沃格尔法是一种快速找到运输问题初始解的方法，通过随机选择起点并逐步构建解决方案。而位势法则用于计算检验数，通过构造位势函数，判断当前解是否可进一步优化。 运输问题在运筹学中占有重要地位，其理论和方法被广泛应用于物流、生产计划等领域，以帮助决策者制定最经济有效的资源分配策略。