对偶线性规划是线性规划的一个重要分支，它提供了原问题（主问题）的另一种视角，通过构建一个与原问题相关的对偶问题，可以更有效地解决某些类型的优化问题。在给定的英文教材中，《对偶线性规划理论》一书深入探讨了对偶线性规划的核心概念、算法及其应用，特别是对偶单纯形法。
### 对偶单纯形法
对偶单纯形法是一种用于求解线性规划问题的算法，特别适用于初始基可行解不可行但相对成本系数为正的情况。该方法通过寻找并退出一个基变量，然后引入一个新的非基变量，来更新基变量集，确保相对成本系数保持正数，并使基本解逐渐接近可行性。这一过程使得目标函数值不会小于原基的目标函数值，从而在最小化问题中，即使处于可行域之外，也能逐步提高目标值，逼近可行性区域。
### 定理详解
教材中给出的定理涉及对偶单纯形法的关键步骤：
设\( LP \): Min\(\{ c \cdot x | Ax = b, x \geq 0 \}\)为标准形式下的线性规划问题，其中\( A \)是\( n \times m \)矩阵，假设\( B \)是\( LP \)的基本索引集，但不一定是可行的基本索引集。令\("B" = I_m AB^{-1}AN - b_0^r - z\)"，其中\( r \geq 0 \)，且\( bi < 0 \)。在\( \T(B)B,N,const. \)表中的第\( i \)行有形式为\( 0,...,0,1,0,...,0,a_{i1},...,a_{ij},...,a_{ik},...,a_{in-m},b_i \)，其中\( a_{ij} < 0 \)且\( r_i / a_{ij} \)满足特定条件。
基于这些前提，若选择\( N \)中的\( j \)替换\( B \)中与\( i \)对应的索引，从而得到新的基本索引集\( B_1 \)，则\( B_1 \)依然为基本索引集。且\( B_1 \)对应于\( j \)的成本系数为正，并满足\( z' \geq z \)。
### 证明解析
证明过程依赖于高斯消元法，确保\( B_1 \)的列在矩阵\( A \)中形成单位矩阵，证明了\( B_1 \)的基本性质。通过改变第\( i \)行对应的基本解分量，从负值变为正值，同时调整新的成本系数，以保持其非负性。
对于新成本系数\( a'_{1k} \)，有两种情况考虑：当\( a'_{1k} \geq 0 \)，则\( rk - r_j / (a_{ij} / a_{ik}) \geq rk \geq 0 \)；当\( a'_{1k} < 0 \)，由\( j \)的选择条件可知\( rk / a_{ik} \leq r_j / a_{ij} \)，结合\( a_{ik} < 0 \)，可得\( rk - r_j / (a_{ij} / a_{ik}) \geq rk \)。
此定理及证明展示了对偶单纯形法的关键步骤，即如何通过适当选择进入和退出的基变量，更新基变量集，同时确保算法的正确性和效率。对偶单纯形法不仅适用于解决线性规划问题，而且在理论研究和实际应用中都具有重要意义，尤其是在处理大规模、复杂优化问题时，通过对偶单纯形法能够更有效地找到最优解或近似最优解，从而提高解决问题的效率和准确性。
