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

运筹学期末论文盐城师范学院运筹学期末论文题 目: 用单纯形法解决线性规划问题 姓 名: 陈 伟 二级学院: 数学科学学院 专 业: 数学与应用数学 班 级: 111 班 学 号: 11211149 成绩评定: 前 言线性规划问题是数学以及日常生活中最基本的问题之一，如何快速有效的解决线性规划问题是数学家也在努力研究的科目之一。以前中学时我们解决线性规划问题一般采用的是图解法，即画出所给条件的可行域，找出目标函数的最优解。这种方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况。下面我们介绍另外一种方法单纯形法，来解决图解法不能解决的问题。1 单纯形法1.1 单纯形法的基本思路利用求线性规划问题基本可行解的方法求解较大规模的问题是不可行的。有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。1.2 单纯形法的基本步骤第1步求初始基可行解，列出初始单纯形表。对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵（P1,P2，Pm），以此作为基求出问题的一个初始基可行解。为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表（见表11）。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。第2步：最优性检验 表11单纯形表 Cj c1 , cm , cj , cn Cj 基 b x1 xm xj xn c1 x1 b1 c2 x2 b2 , , , cm xm bm 1 0 a1j a1n 0 0 a2j a2n , 0 , , 0 1 amj amncj-zj 0 0 cj-i=1mciaij ci-i=1ncnaij 如表中所有检验数cj-zj0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在cj-zj0时，如有Pj0，则问题为无界解，计算结束；否则转下一步。第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。（1）确定换入基的变量。只要有检验数大于零，对应的变量xj就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个，其对应的变量xk作为进基变量。(2)确定出基的变量。=minbiaik丨aik0=brark， 确定xr是出基变量，ark为主元。(3)用进基变量xk替换出基变量xr，得到一个新的基，对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表(a)把第r行乘以1/ark，之后的结果填入新表的第r行。对于ir行，把第r行乘以（-aikalk）之后与原表中第i行。在xB列中的r行位置填入xk，其余行不变；在cB列中用ck代替r行原来的值，其余的行与原表中相同。(b)然后用xj的价值系数cJ减去cB列的各元素与xj列各元素的乘积，把计算结果填入xj列的最后一行，得到检验数，计算并填入所得的值。第4步：重复上述过程，就可以得到最优解或判断出无有限最优解2 单纯形法求解线性规划问题的范例 max z=-3x1+x3 s.t. x1+x2+x34-2x1+x2-x313x2+x3=9xj0,(i=1.2.3)解：将此问题化为标准形式，在约束条件中添加松弛变量和人工变量后得， max z=-3x1+x3+0x4+0x5-Mx6-Mx7 s.t. x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xj0,(j=1.2.37) 列出单纯形表： cj-30100-M-MCb基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-2M-34M10-M000x4330211-100x21-21-10-110-Mx7660403-31cj-zj6M-304M+103M-4M00x400001-1/21/2-1/20x23011/30001/3-3x11102/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 单纯形法小结 我觉得用单纯形法解决线性规划问题需要注意以下几点，首先将问题化为标准形式时需要观察约束系数矩阵中是否有单位矩阵，从而决定是否添加人工变量。第二个需要注意的点是在确定换入基和换出基时要细心计算，一旦换入