最优化课程论文【范本模板】.pdf

求解线性规划的单纯形法

摘要：线性规划就是用数学为工具,来研究一定限制条件下,如何实现某一线性目标
最优化。单纯形法是求解线性规划的主要算法,文章从单纯形法的思想出发，详细论述
了单纯形法的主体步骤，并借助单纯形表通过例题加以说明。求解思路是：通过添加
人工变量使得标准化后的系数矩阵一定含有单位矩阵，从而得到一组基变量和初始基
本可行解。由于人工变量是人为添加的，为了不改变原问题，在目标函数中消去人
工变量，并将人工变量由初始的基变量化成非基变量,使之取值为零,然后用普通单
纯形法求解.
关键词：线性规划；单纯形法；单纯形表；步骤
1。迭代原理
从一个初始的基本可行解出发，经过判断,如果是最优解，则结束；否则经过基变
换得到另一个目标函数值改善的基本可行解，如此一直进行下去，直到找到最优解。
2．迭代步骤
第1步：求初始基可行解，列出初始单纯形表.
第2步：最优性检验。
第3步：从一个基本可行解转换到相邻的目标函数值更大的
基本可行解,列出新的单纯形表。
第4步:重复第2、3步，一直到计算结束为止.
2.1确定初始基本可行解
由于可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个
初始可行基B0。确定方法：若系数矩阵A中含单位矩阵I，则取B0＝I；若A中不含I，
则可用人工变量法构造一个I.
2。2最优性检验
用目标来检验解的优劣.在A中取定一个基矩阵B，则决策向量X可分块为！”，
相应的价格向量C也分块为(CBCN），把这个分块矩阵的形式乘出来，就是Z＝CX＝
（＝CBXB＋CNXN，不妨设B表示A中的前m列，则可记A＝（BN），其中N
为非基矩阵，约束中的AX＝b可表示为（BN)）！”＝b,即XB＝B－1b－B－1NXN经整
理得Z＝CB(B－1b－B－1NXN）＋CNXN，＝CBB－1b＋（CN－CBB－1N）XN在这个式
子中不难分析出，后边一项XN的系数CN－CBB－1N,当这个向量均为≤0分量时,这时
只有当XN取0时,使Z值最大,也就是当XN统统取0时的这个基本可行解是最优的，
而当这个系数向量其中有某分量是＞0的时候，我们可以分析得到，当前XN统统取0
的这个基本可行解不是最优，因此，我们可以用XN的系数向量CN－CBB－1N的符号
来判断当前基可行解是不是最优,把这个系数向量叫做检验数向量，记为δ,当δ≤0
时，当前解为最优解.最优性检验的方法:（1）计算每个变量xj的检验数δj＝Cj
－CBB－1Pj,其中Pj为A中的第j列；(2）若所有δj≤0，则当前解为最优；否则，
如果至少有一个δj＞0，当前解不是最优，转入第三步。
2.3寻找更好的基本可行解
由于基本可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换
为下一个新的基B1，因此，本步骤也可称为基变换。在基变换的过程中要遵循这样的
原则：保证改善目标,再者保证基变换后的解可行。具体变换的方法就是将系数矩阵A

1
＝(P1,P2,……Pi……Pk……Pn）中非基向量部分的某一列和基向量中的某一列互换,
而且每次只换一列,在基向量的行列中出去一个进一个,这个基变换的过程就是确定
进基出基。具体方法：首先决定进基，令正检验数中最大的那个所对应的Pk进基;
然后决定出基，令检验比θi中最小的对应的行Ps出基，其中θi＝(B-1b)i/（B
—1Pk）i，（B—1Pk）i＞0，也就是对应分量之比。
在用单纯形法求解线性规划问题之前,有一个预备步骤就是将模型变为标准型,虽然可
以由基本的计算求出线性规划问题的最优解,但是为了更加简单、清楚，这个算法的
过程我们通过表格的形式来实现,即所谓的单纯形表。
例:用单纯形法求解下面线性规划问题(以max为例）
maxZ＝7X1＋12x2
s.t。:
9x1＋4x2≤360
4x1＋5x2≤200
3x1＋10x2≤300
x1，x2≥0
解：化为标准型:
maxZ＝7X1＋12X2＋0X3＋0X4＋0X5
s。t.:
9x1＋4x2＋x3＝360
4x1＋5x2＋x4＝200
3x1＋10x2＋x5＝300
x1，x2，x3，x4,x5≥0
单纯形表：

第一个基是I,初始表填完后，第一个基本可行解X＝(0，0,360,200，300）T,这个
解是否为最优呢？要计算检验数进行检验。以第一个检验数δ1为例来加以说明
δ1＝C1－CBB－1P1＝7－（0，0,0）
（943)T＝7同理求出其余几个检验数分别为12、0、0、0。如果检验数的符号均
≤0，则当前这个基本可行解最优,否则不是最优。我们看到这张表不是最优，还需继
续进行。那么继续进行就需转到第三个步骤基变换，主要是确定进基和出基，确定进
基是在正检验数中选择最大的那个，我们这道题是12，这个12所对应的向量是P2，
对应的