用单纯形法解决线性规划问题

1、盐城师范学院运筹学期末论文题目： 用单纯形法解决线性规m 姓名：RLJi二级学院：数学科学学院专 业：数学与应用数学班级：111班学号：11211149成绩评定：前 言线性规划问题是数学以及日常生活中最基本的问题之一，如何快速有效的解决 线性规划问题是数学家也在努力研究的科目之一。以前中学时我们解决线性规划问 题一般采用的是图解法，即画出所给条件的可行域，找出目标函数的最优解。这种 方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况。 下面我们介绍另外一种方法一单纯形法，来解决图解法不能解决的问题。1单纯形法1.1单纯形法的基本思路利用求线性规划问题基本可行解的方法求解较大

2、规模的问题是不可行的。有选 择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个 相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域 中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是 最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数 值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过 有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。1.2单纯形法的基本步骤第1步求初始基可行解，列出初始单纯形表。对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程

3、的系数矩阵中包含一个单位矩阵（PLP2,，Pm）,以此作为基求出问题的一个初 始基可行解。为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函 数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格， 称为单纯形表（见表l-l）o迭代计算中每找出一个新的基可行解时，就重画一张单 纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终 单纯形表。第2步：最优性检验表11单纯形表Cjci q】，”qcnCj基 bX1 Xni XjXnC1X1bi1 o a】ja inC2X2b20 o. . 0 a2j a2nCmXmbm0 1 amj amnq

4、Zj0 oCj-岛qa可q?=l cn aij如表中所有检验数q-ZjWO,且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在Cj-Zj。时，如有10,则问题为无界解， 计算结束；否则转下一步。第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的 单纯形表。确定换入基的变量。只要有检验数大于零，对应的变量Xj就可作为进基的 变量，当有一个以上检验数大于零时，一般从中找出最大一个，其对应的变量Xk作 为进基变量。确定出基的变量。0 = min3 I aik 。=务，确定是出基变量，敞为 主元。用进基变量Xk替换出基变量X】.，得到一个新的基，对应这个基可以

5、找出一个 新的基可行解，并相应地可以画出一个新的单纯形表把第r行乘以1/a,之后的结果填入新表的第r行。对于i主r行，把 第r行乘以(aik/alk)之后与原表中第i行。在Xb列中的r行位置填入Xk，其余行 不变；在Cb列中用Ck代替r行原来的值，其余的行与原表中相同。然后用Xj的价值系数Cj减去Cb列的各元素与不列各元素的乘积，把计算结果填入Xj列的最后一行，得到检验数，计算并填入所得的值。第4步：重复上述过程，就可以得到最优解或判断出无有限最优解2单纯形法求解线性规划问题的范例max z = -3Xi + x3Xi + x2 + x3 13x2 + X3 = 9Xj 0, (i = 1.2

6、.3)解：将此问题化为标准形式，在约束条件中添加松弛变量和人工变量后得,max z = -3xi + x3 + 0 x4 + 0 x5 一 Mx6 一 Mx7X1 + X2 + X3 + X4 = 42xi + x2 - x3 - x5 + x6 = 13x2 + X3 + X7 = 9X) o, g = 1.2.3 .7)列出单纯形表：q -30100-M-Mcb基bXlX2X3X4X5X6X70X441111000-MX61-21-10-110-MX790310001q Zj-2M - 34M10-M000X4330211-100X21-21-10-110-MX7660403-31Cj Z

7、j6M-304M+103M-4M00X400001-1/21/2-1/20X23011/30001/3-3Xl1102/301/2-1/21/6Cj Zj00303/2-M-3/2-M+1/20X400001-1/21/2-1/20X25/2-1/2100-1/41/41/41X33/23/20103/4-3/41/4Cj Zj-9/2000-4/3-M+3/4-M-1/4则当X2 = 5/2, x3 = 3/2, x4=0时目标函数有最优解max z =3/2.3单纯形法小结我觉得用单纯形法解决线性规划问题需要注意以下凡点，首先将问题化为标准形 式时需要观察约束系数矩阵中是否有单位矩阵，从而决定是否添加人工变量。第二 个需要注意的点是在确定换入基和换出基时要细心计