原创力文档- 1、本文档共36页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
§4.2两阶段法与大M法————初始可行基的求法
求解线性规划的步骤是：
已知一个初始基本可行解
从初始基本可行解出发，写出单纯型表，求出进基离基变量，做主元消去法，求出一个新的基本可行解且使目标函数值得到改善。
判断当前基本可行解是否是最优解
那末，当观察不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本可行解的方法
4.2.1
≥0
其中A是矩阵，≥0。若A中有阶单位矩阵，则初始基本可行解立即得到。比如，，那么
就是一个基本可行解。若A中不包含阶单位矩阵，就需要用某种方法求出一个基本可行解。
介绍两阶段法之前，先引入人工变量的概念。
设A中不包含阶单位矩阵，为使约束方程的系数矩阵中含有阶单位矩阵，把每个方程增加一个非负变量，令
（4.2.2）
≥0，≥0
即
（4.2.3）
≥0，≥0
显然，
是（4.2.3）
向量≥0是人为引入的，它的每个分量成为人工变量。人变量与前面介绍过的松弛变量是两个不同的概念。松弛变量的作用是把不等式约束改写成等式约束，改写前后的两个问题是等价的。因此，松弛变量是“合法”的变量。而人工变量的引入，改变了原来的约束条件从这个意义上讲，它们是“不合法”的变量。
第一阶段是用单纯形方法消去人工变量（如果可能的话）：
（4.2.4）
≥0，≥0
其中是分量全是1的维列向量，
是人工变量构成的维列向量。
由于是（4.2.4）的一个基本可行解，目标函数值在可行域上有下界，因此问题（4.2.4
求解（4.2.4），设得到的最优基本可行解是，此时必
有下列三种情形之一：
这时（4.2.1）无可行解。因为如果（4.2.1）存在可行解则
是（4.2.4）的可行解。在此点，问题（4.2.4
＜
而是目标函数值的最优值，矛盾。
2.且的分量都是非基变量。这时，个基变量都是原来的变量，又知是（4.2.4）的基本可行解，因此是（4.2.1）的一个基本可行解。
3且的某些分量是基变量。这时，可用主元消去法把原来变量中的某些非基变量引进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段。应指出，为替换出人工变量而采用的主元消去，在主元的选择上，并不要求遵守单纯形法确定离进基变量的规则。
第二阶段，就是从得到的基本可行解出发，用单纯形方法求（4.2.1
例4.2.1
≥2
≥1
≤3
≥0
先引进松弛变量，把问题化成标准形式。由于此标准形式中约束方程的系数矩阵并不包含3阶单位矩阵，因此还引进人工变量。下面先求解一阶段问题：
+=2
=1
=3
≥0
仍然用主元消去法，主元用框号标出。迭代过程如下：
1
1
-1
0
0
10
2
1
-1
0
-1
0
01
1
1
0
0
1
1
00
3
2
0
-1
-1
0
00
3
0
2
-1
1
0
1-1
1
1
-1
0
-1
0
01
1
0
1
0
1
1
0-1
2
0
2
-1
1
0
0-2
1
0
1
-
0
1
0
0
-1
0
0
0
1
0
0
0
0
0
-1-1
0
由于所有判别数≤0，因此达到最优解。在一阶段问题的最优解中，人工变量都是非基变量。这样，我们得到初始基本可行解
第一阶段结束后，修改最后的单纯形表。去掉人工变量和下面的列（也可保留，但人工变量不能再进基），把最后的判别数行按原来问题进行修正。其他不变。然后开始第二阶段迭代，即极大化目标函数。迭代过程如下：
0
1
0
1
0
0
0
0
文档评论（0）