管理运筹学的单纯形法
商学院王中昭这个方法是解决线性规划问题的一个有效方法本章的学习内容1、单纯形法的基本思路和原理2、单纯形法的表形式3、求目标函数值最小问题的单纯形法4、一些特殊情况解法只能解决只包含两个决策变量的线性规划问题，针对包含两个以上决策变量的线性规划问题本章介绍由美国数学家邓齐格(漂亮的长筒袜) 1947提出的应用最广泛的接受线性规划的代数算法——单纯形法。 这可能是操作系统发展史上最辉煌的一笔，该算法是对操作算法的革命。 第3章介绍的线性规划问题的计算机解法是基于单纯形法的原理编程的。 解决多变量线性规划问题。 在随后的研究中，还发明了解线性修订画的其他方法，如前苏联科学家发明的内点法、印度科学家发明的k算法等。 单纯形法的基本思路：从可行区域的一个顶点出发，判断该顶点是否为最优解，否则，寻找另一个使该目标函数值更好的顶点称为迭代，判断该点是否为最优解。 直到某个顶点是其最优解，是优化其目标函数值的解，或者判断出线性规划问题没有最优解为止。 在这里，可行领域的顶点不再像解法那样直接可见。 单纯形法中可行域的顶点称为基本可行解，最初找到的可行域的顶点称为初始基本可行解。 第二章例1介绍单纯形法。 在第2章的例1中，如果加上目标函数： max Z=50X1 100X2约束条件： x1x2300、2x1x2400、X2250、X10、X20 .松弛变量，则目标函数： max z=s2、S30这里，pj是系数矩阵a的第j列，在a中存在非零的3阶子式，所以可知a的秩为3。 因为a的等级m比这个方程式的变量个数n小，所以从线性代数的知识中可以看出有无数个解。 为了找到早期的基本可行解，介绍了线性规划的一些基本概念。 已知(基) a是约束条件的mn系数矩阵，秩为m。 当b是a中mm阶非奇异部分矩阵(即逆矩阵，|B|0 )时，b可以说是线性规划问题的一个基础。 也就是说，任何m阶可逆矩阵都可以作为基础。 基向量：基b中的每一列称为基向量。 基底b有m个基底向量。 在这个例子中，对于基底b来说，三个列向量都是基底向量。 并且，b只有这3个基向量。 非基底向量：将a中除基底b以外的各列称为基底b的非基底向量。 基变量：与基向量pi相对应的变量Xi称为基变量，基变量有m个。 在该例题中X1、X2、S1都是B1的基变量，但S1、S2、S3是B2的基变量。 非基底变量：与非基底向量pj相对应的变量Xj被称为非基底变量，非基底变量有n-m个。 在这个例题中，S2、S3是B1的非基底变量。 另一方面，X1、X2是B2的非基底变量。 基本解：根据线性代数的知识，如果在约束方程的系数矩阵中发现了基，则将该基的非基变量设为零。 解这个方程得到唯一的解，这个解被称为线性规划的基本解。 可行解)满足)因为在该基本解中S1=-100、S3=- 150，所以不满足该线性规划S10、S30的制约条件显然不是问题的可行解。 一个基本解既是可行解，也可以不是可行解。 这些主要区别在于所有变量的解是否满足非负条件。 满足非负条件的一个基本解称为基本可行解，这样的基称为可行基。 可行解、基本解、基本可行解和最优解的关系：关于基本解，可行解和基本可行解的概念：注意先模型为标准型再判断。 可行解：满足包含非阴性约束条件的解称为可行解，但不一定包括基。
基本解：为了使非基底变量为0，先找到基底再求解。 这个解不一定满足非负性。 基本可行解：同时满足非负性和基本解的解称为基本可行解。 所有变量的解都在零以上，由此可知该基本解是基本可行解。 因此，要判断一个基底是否是可行的基底，只有在求出其基本解后，该基本解的所有变量的解都在零以上时，才能判断该解是基本可行的解，该基底是可行的基底。 在解决之前能找到可行的基础吗？ 线性规划的标准型都要求bj在零以上，所以如果寻找的话