第2.2讲-线性规划-改进单纯形与对偶单纯形1

【线性规划】是运筹学中的一个基本概念，它涉及到在满足一组线性约束条件的情况下，求解一个线性目标函数的最大值或最小值问题。在本讲中，主要探讨了两种方法：改进单纯形法和对偶单纯形法。 单纯形法是由George Dantzig提出的，用于解决线性规划问题的一种迭代算法。传统的单纯形法通过在当前解的基础上，选择一个新的基变量进入基，同时将一个非基变量退出基，逐步接近最优解。在实际应用中，为了提高效率，进行了改进，例如通过引入更好的变量选择策略和优化计算过程，以减少迭代次数。 对偶单纯形法则是线性规划问题的另一种解法，它解决了原问题的对偶问题。原问题的目标函数和约束条件被转换为对偶问题的约束和目标，其中原问题的变量分为基本变量和非基本变量，而在对偶问题中则有对应的资源限制和资源价格。对偶问题的最优解可以提供原问题的下界，而原问题的最优解提供对偶问题的上界，当两者相等时，即找到了两个问题的共同最优解。 在MATLAB中，有内置的优化工具箱可以用于解决线性规划问题，包括`linprog`函数，它支持包括单纯形法在内的多种算法来求解线性规划问题。用户可以设置初始解、优化选项以及目标函数和约束条件，然后调用该函数进行计算。 在给定的部分内容中，提到了线性系统的矩阵表示。对于线性规划问题，通常会将其写成标准形式： \[ N x_N + B x_B = b \] 其中，\( N \) 是关于非基变量 \( x_N \) 的系数矩阵，\( B \) 关于基变量 \( x_B \) 的系数矩阵，\( b \) 是常数向量。在求解过程中，可能会遇到增广矩阵的形式： \[ \begin{bmatrix} N & B \\ I & 0 \end{bmatrix} \begin{bmatrix} x_N \\ x_B \end{bmatrix} = \begin{bmatrix} b \\ 0 \end{bmatrix} \] 这里，\( I \) 是单位矩阵，\( 0 \) 是零矩阵，这样的增广矩阵有助于进行行变换，找到最优解。 对偶问题的建立通常涉及到拉格朗日乘子（或资源价格），其目标函数是原问题的负目标函数加上拉格朗日乘子与约束的乘积，约束则变成了对偶问题的目标函数。例如，给定的原问题是最大化 \( 40x_1 + 60x_2 \)，约束为 \( 2x_1 + x_2 \leq 70, x_1 + x_2 \leq 40, x_1 + 3x_2 \leq 90 \)，相应的对偶问题则是最小化 \( -40x_1 - 60x_2 \)，并增加新的变量 \( x_3, x_4, x_5 \) 来表示拉格朗日乘子，使得对偶问题的约束与原问题的约束一一对应。 在求解过程中，通过计算资源价格（对偶变量）和检验数，可以判断当前解是否是最优解，并确定下一步的移动方向。如果某检验数为正，表示存在改善当前解的可能，相应的非基变量会被选入基，替换掉一个基变量。 本讲内容涵盖了线性规划的基本概念、改进单纯形法和对偶单纯形法的应用，以及如何在MATLAB中利用这些方法解决实际问题。通过深入理解这些知识，可以有效地解决涉及资源分配、生产计划等实际工程和管理问题。