运筹学基础：线性规划与单纯形法解析

"运筹学第一章：线性规划及单纯形法.pdf，是运筹学教程第5版第一章的学习笔记，主要关注线性规划问题的单纯形解法，并简要介绍MATLAB求解线性规划的两种方法。" 在运筹学中，线性规划是一种重要的优化技术，用于寻找一组决策变量的最佳值，以最大化或最小化某个目标函数，同时满足一系列线性的约束条件。线性规划问题的数学模型通常包含决策变量、目标函数和约束条件，其中所有这些元素都是线性的。 决策变量是问题中待确定的未知数，它们代表了可以采取的不同行动或策略。目标函数则表示需要优化的目标，可能是利润、成本、效率等，它是一个与决策变量成线性关系的函数。约束条件是必须满足的条件，它们是关于决策变量的线性等式或不等式。 线性规划问题的一般形式可表示为最大化（或最小化）目标函数 \( z = \sum_{j=1}^{n} c_jx_j \)，同时满足一组线性不等式或等式约束 \( \sum_{j=1}^{n} a_{ij}x_j \leq (=\ or \geq) b_i \) 和非负决策变量约束 \( x_j \geq 0 \)。这里的 \( A \) 是系数矩阵，\( b \) 是常数向量，而 \( C \) 是目标函数的系数向量。 为了将一般线性规划问题转化为标准形式，我们可以进行以下转化： 1. 如果目标函数为最小化，可以将其转换为最大化负目标函数 \( -z \)。 2. 对于约束条件 \( b < 0 \)，可以通过乘以 -1 将不等式方向反转。 3. 使用松弛变量或剩余变量将不等式约束转化为等式，确保所有约束都为等式形式。 4. 无约束的变量可以通过引入新的非负变量来处理，如 \( x = x' - x'' \)，其中 \( x', x'' \geq 0 \)。 5. 若有负的下限约束 \( x \leq 0 \)，可以通过引入新的非负变量 \( x' = -x \) 来转换。 当只有两个决策变量时，线性规划问题可以通过图解法直观地求解。这种方法揭示了线性规划问题的四种可能解：唯一最优解、无穷多最优解、无界解和无可行解。可行域是决策变量满足所有约束条件的区域，对于线性规划问题，如果存在可行域，那么它总是凸的。最优解存在于可行域的边界上，这是因为线性函数在凸集内部无法达到最值。 单纯形法是解决线性规划问题的一种经典算法，它通过迭代过程，每次将一个非基变量替换掉一个基变量，逐步逼近最优解。MATLAB 提供了工具箱来方便地求解线性规划问题，例如 `linprog` 函数，它可以采用不同的算法（包括单纯形法）来解决这类问题。 理解并掌握线性规划的基本概念、模型构建以及求解方法，对于解决实际工程、经济、管理等领域的问题具有重要价值。单纯形法虽然在理论上可能需要大量计算，但在实践中由于有效的算法优化，已经成为求解大规模线性规划问题的有效工具。