下载文档原格式
运筹学单纯形法
运筹学单纯形法，又称单纯性法，是一种用于求解线性规划问题的数学方法，它在运筹学中发挥着重要作用。
它主要应用于决策及资源分配问题，可以帮助决策者更好地把握资源的优化配置，并寻求最优解。
单纯性法是以线性规划问题作为理论基础，它是将该问题转化为一系列形如Ax=b的线性方程组的运筹学方法。
在这个方程组通过调整方程中的系数和右面常数而变换为形如Cx≤d的不等式形式，而这种不等式系统称为单纯性约束条件。
单纯性法从不等式中寻找一系列基向量，并通过改变基向量来实现改变不等式的求解方程之间的关系，从而求出最优解的问题。
传统的单纯性法分为有界单纯性和无界单纯性两种情形。
无界单纯性以简单费用曲线方法、扩展的简单费用曲线方法和增广次数法三大类。
有界单纯性主要是对对角单纯性和非对角单纯性这两类单纯性系统分别使用不同的方法进行求解。
单纯性求解方法在线性规划问题求解中具有重要应用，它能通过求解线性规划问题中的一系列互不相关的子问题来求出最优解。
使用该方法，可以以最少的成本达到最优的收益，它包括费用最低优化、网络流优化、全格研究和数学优化模型等。
单纯形法原理及例题
单纯形法原理：
单纯形法是求解线性规划问题的一种数学方法，它是由美国数学家卢克·单纯形于1947年发明的。
用单纯形法求解线性规划的过程，往往利用线性规划的对偶形式，将原问题变换为无约束极大化问题，逐步把极大化问题转换为标准型问题，最后利用单纯形法的搜索方法求解满足所有约束条件的最优解。
例题：
问题：求解最小化目标函数z=2x1+x2的线性规划问题，约束条件如下：
x1+2x2≥3
3x1+x2≥6
x1,x2≥0
解：将上述线性规划问题转换为无约束极大化问题，可得：
极大化问题：
Max z=-2x1-x2
s.t. x1+2x2≤3
3x1+x2≤6
x1,x2≥0
将极大化问题转换为标准型问题，可得：
Max z=-2x1-x2
s.t. x1+2x2+s1=3
3x1+x2+s2=6
x1,x2,s1,s2≥0
运用单纯形法的搜索方法求解：
令x1=0,x2=0，则可得s1=3,s2=6，即(0,0,3,6)是单纯形的初始解；
令z=-2x1-x2=0，代入约束条件，可得x1=3,x2=3，则可得s1=0,s2=0，即(3,3,0,0)是新的单纯形解。
由于s1=s2=0，说明x1=3,x2=3是线性规划问题的最优解，且最小值为z=2*3+3=9。
单纯形法解的四种情况单纯形法是运筹学中求解线性规划问题的一种常用方法。
它的基本思想是利用线性规划问题的几何性质，通过不断优化目标函数值，使得问题的最优解逐渐逼近。
在运用单纯形法求解线性规划问题时，存在四种不同的情况，下面一一进行详细介绍。
一、唯一最优解当线性规划问题满足严格的可行性条件和凸性条件时，求解出的最优解就是唯一的。
在这种情况下，单纯形法通过一系列计算步骤，得出的就是该问题的最优解。
此时，算法的收敛速度也是最快的，因为每次迭代都会使得目标函数值有所改善，确定下一次迭代的方向也较为明确。
二、无解当线性规划问题没有可行解时，单纯形法会失败。
这通常是因为约束条件之间存在冲突，导致问题无法求解。
例如，如果一个约束条件要求变量的值大于等于某个数，而另一个约束条件要求该变量的值小于该数，那么就会导致问题无法求解。
这种情况下，单纯形法会一直进行迭代，直到达到指定的迭代次数或者发现无法得到更好的解为止。
三、无界当线性规划问题的目标函数可以无限地取得更小的值时，就被称为无界问题。
这种情况通常是由于约束条件中某个变量的值可以无限大或者无限小，导致目标函数的值可以无限地下降。
在这种情况下，单纯形法会一直迭代下去，但却无法得到最优解。
此时，需要对约束条件进行适当的调整，添加额外的限制条件以消除无界情况。
四、多解当线性规划问题可以有多个最优解时，就称为多解问题。
例如，当目标函数有多个极小值点，每个极小值点都是最优解。
在这种情况下，单纯形法只能找到其中一个最优解，而无法确定其他最优解的位置。
在实际应用中，多解问题较为常见，在解决此类问题时，需要进一步确定目标函数的相关参数，以便正确地找到所有的最优解。
综上所述，单纯形法在求解线性规划问题时，会出现四种不同的情况，即唯一最优解、无解、无界和多解。
对于每种不同的情况，需要采取不同的策略来进行处理。
因此，在运用单纯形法求解线性规划问题时，需要对这些情况进行充分的考虑，以便正确地解决问题。
