优选第二章线性规划的标准型与单纯形法

运筹学复习要点运筹学复习要点第二章线性规划与单纯形法一、标准型：规定具有下述条件的线性规划问题为标准型式的线性规划问题：1、目标函数为求最大；2、约束条件为等式约束；3、决策变量为非负。

二、线性规划问题具有的特征：1、每一问题都用一组决策变量（x1, x2, . . . ,xn）表示某一方案；2这组决策变量的值就代表一个具体方案，一般这些变量值是非负的；3、存在一定的约束条件，它们可用线性等式或不等式表示；4、都有一个要求达到的目标，它们可用决策变量的线性函数表示，称目标函数。

根据问题不同，要求目标函数实现最大化或最小化。

三、图解法的结论：1、可行域一定是凸集，即该区域内任意两点间连线上的点仍在该区域内；2、线性规划最优解不可能在凸集内的点上实现；3、线性规划问题有可能存在无穷多最优解；4、如果可行域无界，则最优解可能是无界解；5、如果不存在可行域，则没有可行解，也一定不存在最优解；6图解法只适用于两个决策变量的情况。

四、单纯形法：其基本思路是首先确定一个初始基可行解，然后判断该基可行解是否为最优解。

如果是最优解，则求解过程结束；如果不是最优解，则在此基础上变换找出另一个基可行解，该基可行解的目标函数值应该优于原基可行解。

再判断新的基可行解是否为最优解，如果是最优解，则求解过程结束；如果不是最优解，则在此基础上变换再找出另一个新基可行解，如此进行下去，直到找到最优解为止。

五、最优性检验与解的形式：最优解的判别定理，若X(0) = (b′1, b′2, ……… ,b′m, 0, …… , 0)T为对应于基B的一个基可行解，且对于一切j = m + 1, …… , n，有σj6 0，则X(0)为最优解，称σj为检验数。

无穷最多解判别定理，若X(0) = (b′1, b′2, …… , b′m, 0, …… , 0)T为对应于基B的一个基可行解，且对于一切j = m + 1, …… , n，有σj6 0，又存在某个非基变量的检验数σm+k= 0，则线性规划问题有无穷多最优解。

线性规划与单纯形法线性规划（Linear Programming）是一种在资源有限的情况下，通过最优化目标函数来确定最佳解决方案的数学优化方法。

而单纯形法（Simplex Method）则是一种常用的求解线性规划问题的算法。

本文将介绍线性规划与单纯形法的基本概念和运算步骤，以及实际应用中的一些注意事项。

一、线性规划的基本概念线性规划的基本思想是在一组线性不等式约束条件下，通过线性目标函数的最小化（或最大化）来求解最优解。

其中，线性不等式约束条件可表示为：```a1x1 + a2x2 + ... + anxn ≤ b```其中，x1、x2、...、xn为决策变量，a1、a2、...、an为系数，b为常数。

目标函数的最小化（或最大化）可表示为：```min(c1x1 + c2x2 + ... + cnxn)```或```max(c1x1 + c2x2 + ... + cnxn)```其中，c1、c2、...、cn为系数。

二、单纯形法的基本思想单纯形法是由乔治·丹尼尔·丹齐格尔（George Dantzig）于1947年提出的求解线性规划问题的算法。

其基本思想是通过逐步迭代改进当前解，直至达到最优解。

三、单纯形法的运算步骤1. 初等列变换：将线性规划问题转化为标准型，即将所有约束条件转化为等式形式，并引入松弛变量或人工变量。

2. 初始化：确定初始可行解。

通常使用人工变量法来获得一个初始可行解。

3. 检验最优性：计算当前基础解的目标函数值，若目标函数值小于等于零，则该基础解即为最优解。

否则，进入下一步。

4. 基本可行解的变换：选择一个入基变量和一个出基变量，并进行基本变换，得到新的基础解。

5. 迭代求解：根据目标函数值是否小于等于零，判断是否达到最优解。

若达到最优解，则算法终止；若未达到最优解，则返回步骤3进行下一轮迭代。

四、单纯形法的实际应用注意事项1. 线性规划问题的约束条件必须是线性的，且可行解集合必须是有界的。

单纯形法标准型单纯形法是一种用于求解线性规划问题的有效方法，它通过不断地移动解向可行域的极端点来寻找最优解。

在实际应用中，线性规划问题往往需要转化为标准型，然后再利用单纯形法进行求解。

本文将对单纯形法标准型进行详细介绍，以便读者能够更好地理解和运用这一方法。

首先，我们来看一下线性规划问题的标准型是如何定义的。

线性规划问题的标准型可以表示为：Max z = c₁x₁ + c₂x₂ + ... + cₙxₙ。

Subject to:a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ≤ b₁。

a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ≤ b₂。

...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ≤ bₙ。

x₁, x₂, ..., xₙ≥ 0。

其中，c₁, c₂, ..., cₙ为目标函数的系数，aᵢⱼ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右端常数，x₁, x₂, ..., xₙ为决策变量。

接下来，我们将线性规划问题转化为标准型。

对于不等式约束，如果右端常数为负数，则可以通过乘以-1的方式将其转化为非负数。

对于大于等于的约束条件，可以引入松弛变量将其转化为小于等于的形式。

这样，原始的线性规划问题就可以转化为标准型，方便后续的求解。

然后，我们将介绍单纯形法的基本思想和步骤。

单纯形法的基本思想是从一个基本可行解出发，通过不断地移动到更优的基本可行解，直到找到最优解为止。

单纯形法的步骤包括，选择初始基本可行解、确定入基变量和出基变量、计算新的基本可行解、更新目标函数值等。

通过这些步骤，我们可以逐步逼近最优解，并最终找到最优解。

最后，我们需要注意单纯形法的一些特殊情况。

在实际应用中，可能会出现无界解、无可行解或者多个最优解的情况。

针对这些特殊情况，我们需要进行相应的处理，以确保线性规划问题能够得到正确的解。

总之，单纯形法标准型是线性规划问题的一种重要形式，通过将线性规划问题转化为标准型，并利用单纯形法进行求解，我们可以有效地找到最优解。