单纯形法.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流单纯形法.精品文档.单纯形法 单纯形法是于1947年由G.B.Dantzig提出的，用于求解一般线性规划问题的方法。下面介绍单纯形法的具体应用过程。一、 把线性规划模型化成标准型线性规划模型1标准型线性规划模型min s.t. , i=1,2,m , j=1,2,n其中，为目标函数，为决策变量，min表示取最小值，s.t.表示约束条件。2各种形式的线性规划模型都可化成标准型(1)若模型的目标是求目标函数的最大值，例如：max 那么，令，化成min (2)如果约束条件中具有不等式，则可引进一个松弛变量，并用下面两个约束条件取代这个不等式：(3) 如果约束条件中具有不等式，则可引进一个剩余变量，并用下面两个约束条件取代这个不等式：(4)如果约束条件中出现，则可引进新变量，并令，将它代入问题的目标函数和约束条件中消去，于是原来的约束条件就化成。(5)如果决策变量的符号不受限制，即>0，=0或<0，则引进两个新变量和，并以代入问题的目标函数和约束条件中消去，同时在约束条件中添加0和0两个约束条件。二、 求初始基本可行解，列出单纯形表对于标准型线性规划模型，在决策变量中选择m个变量作为初始基本变量，要求这m个变量在约束条件的线性方程组中的系数矩阵为非奇异矩阵。即假设初始基本变量的下标集为，也就是为基本变量，那么要求把目标函数值也看成一个变量，并令，那么，就成为方程。假设初始非基本变量的下标集为，那么可以把标准型线性规划模型中的等式约束方程和目标函数方程经过适当整理后写成下列形式的由m+1个方程构成的方程组：由于|B|0，故由行列式性质可知行列式，因此，可以应用消去法将方程组变形，得到下列形式的方程组：把以上方程组的系数列成表（变量w在前m个方程中系数总为0，在最后一个方程中系数总为1，故一般不列出w的系数），就是关于基B的单纯形表，记为T（B）。单纯形表T(B) 0 1 0 r 0 在单纯形表T(B)中，基本解为(i=1,m)，(j=1,n-m)，目标值为。三、 用单纯形表求最优解(1) 观察单纯形表T(B)。若T(B)中，都成立，则T(B)的基本解为基本最优解，目标值为最优值。(2) 若T(B)中不成立，都成立，则确定指标t，使得。然后看T(B)中是否都成立。若成立，则该线性规划模型的目标函数值在可行域内无下界。若不成立，则确定指标k，使得然后转（4）。(3) 若T(B)中都成立，不成立，则确定指标k，使得。然后看是否成立。若成立，则该模型无可行解；若不成立，则确定指标t，使得(4) 然后以为枢轴元素进行转轴得新的单纯形表T(B)，转(1)。转轴的过程如下表所示：单纯形表T(B) 0 1 （） 0 r 0 单纯形表T(B) 0 1 0 r 0 四、 举例说明求以下线性规划模型的最优解：min s.t. 解：先把该模型化成标准型线性规划模型。令，则该模型变为如下的标准型线性规划模型：min s.t. 由于，所以可以选择、为初始基本变量。线性方程组用消去法可以化为由此可列出下面的单纯形表： 3 1 0 （-2） 0 1360-60r 0.1 0 0108以=2为枢轴元素进行转轴，可得如下的单纯形表： 0 1 3/2 1 0 -1/227030r 0 0 0.05105由于，（），所以最优解为=30，=270，=0即=60，最优值为105。