盐城师范学院
运筹学期末论文
题 目: 姓 名:
用单纯形法解决线性规划问题 陈 伟
二级学院: 数学科学学院 专 业: 班 级: 学 号: 成绩评定:
数学与应用数学 111 班 11211149
前 言
线性规划问题是数学以及日常生活中最基本的问题之一，如何快速有效的解决线性规划问题是数学家也在努力研究的科目之一。以前中学时我们解决线性规划问题一般采用的是图解法，即画出所给条件的可行域，找出目标函数的最优解。这种方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况。下面我们介绍另外一种方法—单纯形法，来解决图解法不能解决的问题。
1 单纯形法
1.1 单纯形法的基本思路
利用求线性规划问题基本可行解的方法求解较大规模的问题是不可行的。有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。 1.2 单纯形法的基本步骤
第1步求初始基可行解，列出初始单纯形表。
对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵（P1,P2，…，Pm），以此作为基求出问题的一个初始基可行解。
为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表（见表1—1）。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。
第2步：最优性检验
如表中所有检验数cj−zj≤0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在cj−zj>0时，如有Pj≤0，则问题为无界解，计算结束；否则转下一步。
第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。
（1）确定换入基的变量。只要有检验数大于零，对应的变量xj就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个，其对应的变量xk作
为进基变量。
(2)确定出基的变量。θ=min ai 丨aik>0 =ar， 确定xr是出基变量，ark为
ik
rk
bb
主元。
(3)用进基变量xk替换出基变量xr，得到一个新的基，对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表
(a) 把第r行乘以1/ark，之后的结果填入新表的第r行。对于i≠r行，把
−a
第r行乘以（ik alk）之后与原表中第i行。在xB列中的r行位置填入xk，其余行不变；在cB列中用ck代替r行原来的值，其余的行与原表中相同。
(b) 然后用xj的价值系数cJ减去cB列的各元素与xj列各元素的乘积，把计算结
果填入xj列的最后一行，得到检验数，计算并填入所得的值。
第4步：重复上述过程，就可以得到最优解或判断出无有限最优解
2 单纯形法求解线性规划问题的范例
max z=−3x1+x3
x1+x2+x3≤4−2x1+x2−x3≥1 s.t. 3x
2+x3=9xj≥0,(i=1.2.3)
解：将此问题化为标准形式，在约束条件中添加松弛变量和人工变量后得， max z=−3x1+x3+0x4+0x5−Mx6−Mx7 x1+x2+x3+x4=4−2x1+x2−x3−x5+x6=1 s.t. 3x2+x3+x7=9
xj≥0,(j=1.2.3…7) 列出单纯形表：
234
3 单纯形法小结
我觉得用单纯形法解决线性规划问题需要注意以下几点，首先将问题化为标准形式时需要观察约束系数矩阵中是否有单位矩阵，从而决定是否添加人工变量。第二个需要注意的点是在确定换入基和换出基时要细心计算，一旦换入基或者换出基搞错，那么下面就全都错了。最后在得出最终单纯形表时要观察可行基中是否有人工变量，如果有人工变量则该问题无最优解。另外，在计算表格中其它量的时候须细心认真，千万不要算错，否则可能就一步错步步错了。
盐城师范学院
运筹学期末论文
题 目: 姓 名:
用单纯形法解决线性规划问题 陈 伟
二级学院: 数学科学学院 专 业: 班 级: 学 号: 成绩评定:
数学与应用数学 111 班 11211149
前 言
线性规划问题是数学以及日常生活中最基本的问题之一，如何快速有效的解决线性规划问题是数学家也在努力研究的科目之一。以前中学时我们解决线性规划问题一般采用的是图解法，即画出所给条件的可行域，找出目标函数的最优解。这种方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况。下面我们介绍另外一种方法—单纯形法，来解决图解法不能解决的问题。
1 单纯形法
1.1 单纯形法的基本思路
利用求线性规划问题基本可行解的方法求解较大规模的问题是不可行的。有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。 1.2 单纯形法的基本步骤
第1步求初始基可行解，列出初始单纯形表。
对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵（P1,P2，…，Pm），以此作为基求出问题的一个初始基可行解。
为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表（见表1—1）。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。
第2步：最优性检验
如表中所有检验数cj−zj≤0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在cj−zj>0时，如有Pj≤0，则问题为无界解，计算结束；否则转下一步。
第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。
（1）确定换入基的变量。只要有检验数大于零，对应的变量xj就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个，其对应的变量xk作
为进基变量。
(2)确定出基的变量。θ=min ai 丨aik>0 =ar， 确定xr是出基变量，ark为
ik
rk
bb
主元。
(3)用进基变量xk替换出基变量xr，得到一个新的基，对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表
(a) 把第r行乘以1/ark，之后的结果填入新表的第r行。对于i≠r行，把
−a
第r行乘以（ik alk）之后与原表中第i行。在xB列中的r行位置填入xk，其余行不变；在cB列中用ck代替r行原来的值，其余的行与原表中相同。
(b) 然后用xj的价值系数cJ减去cB列的各元素与xj列各元素的乘积，把计算结
果填入xj列的最后一行，得到检验数，计算并填入所得的值。
第4步：重复上述过程，就可以得到最优解或判断出无有限最优解
2 单纯形法求解线性规划问题的范例
max z=−3x1+x3
x1+x2+x3≤4−2x1+x2−x3≥1 s.t. 3x
2+x3=9xj≥0,(i=1.2.3)
解：将此问题化为标准形式，在约束条件中添加松弛变量和人工变量后得， max z=−3x1+x3+0x4+0x5−Mx6−Mx7 x1+x2+x3+x4=4−2x1+x2−x3−x5+x6=1 s.t. 3x2+x3+x7=9
xj≥0,(j=1.2.3…7) 列出单纯形表：
234
3 单纯形法小结
我觉得用单纯形法解决线性规划问题需要注意以下几点，首先将问题化为标准形式时需要观察约束系数矩阵中是否有单位矩阵，从而决定是否添加人工变量。第二个需要注意的点是在确定换入基和换出基时要细心计算，一旦换入基或者换出基搞错，那么下面就全都错了。最后在得出最终单纯形表时要观察可行基中是否有人工变量，如果有人工变量则该问题无最优解。另外，在计算表格中其它量的时候须细心认真，千万不要算错，否则可能就一步错步步错了。