线性规划问题解法：单纯形法与矩阵表示

"该资源是关于运筹学中单纯形法的PPT课件，主要讲解了线性规划问题的解以及单纯形法的矩阵表示，包括如何利用人工变量法求初始基。" 线性规划问题是一种优化问题，旨在最大化或最小化线性函数（目标函数），同时满足一组线性不等式或等式（约束条件）。在这个问题中，"单纯形法"是一种求解线性规划问题的有效算法，由乔治·丹齐格在1947年提出。单纯形法通过迭代过程，在可行解的空间（也称为“单纯形”）内寻找最优解。 1. 解的基本概念： 线性规划问题的解涉及到"基"和"非基"的概念。一个基是由线性约束方程组系数矩阵A的非奇异子矩阵B构成，这里的B是一个基础解系统，其大小与约束方程的个数相等。非基变量是指不在基础解系统中的变量，它们在满足约束条件时可以取零值。而基变量则是指在当前基中的变量，它们的值决定了整个系统的解。 2. 单纯形法： 单纯形法的核心在于构建一个表格来表示线性规划问题，这个表格通常被称为"单纯形表"。在表格中，行代表约束，列代表变量，分为基变量和非基变量。每个单元格的值表示变量在相应约束下的系数。通过一系列的迭代，每次选择一个非基变量替换掉一个基变量，以改善目标函数的值，直到找到最优解或者证明无解或无穷多解。 3. 求初始基的人工变量法： 在开始单纯形法之前，可能需要构造一个初始基。如果原始问题的初始解不可行，可以通过引入人工变量来构造一个可行的基础解。人工变量在目标函数中带有负无穷的系数，确保在找到实际解之前它们会被排除出基。 单纯形法的矩阵表示，如描述中所示，包括以下部分： - B: 基矩阵，由基变量的系数构成的子矩阵。 - N: 非基变量的系数矩阵。 - I: 单位矩阵，用于保持非基变量的系数不变。 - b: 约束方程的常数项。 - CB: 非基变量在目标函数中的系数列。 - CN: 基变量在目标函数中的系数列。 - CBB-1b: 这部分表示目标函数在基变量下的表达式，通过基矩阵的逆B-1转换得到。 通过这些矩阵的组合和变换，单纯形法能够系统地求解线性规划问题，找到最优解的坐标和目标函数的值。这种方法虽然计算量较大，但在实践中已被广泛采用，尤其对于小到中规模的问题，效率较高。随着计算技术的发展，更先进的算法如内点法已逐渐替代单纯形法，但单纯形法在理解线性规划和优化理论方面仍占有重要地位。