在线性规划的单纯形法中,如何保证一次换基运算得到的还是一个基本可行解?

单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步选代后，必可求出最优解 。
为了用选代法求出线性规划的最优解，需要解决以下三个问题  ：
(1)最优解判别准则，即迭代终止的判别标准  ；
(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法 ；
(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降

首先标准化：
添加松弛变量x3,x4（为了让你看得更规则，添加了1，0的系数）：
max: z = 6 x1 + 4 x2
subject to: 2 x1 + 3 x2 + 1 x3 + 0 x4 = 100
4 x1 + 2 x2 + 0 x3 + 1 x4 = 120
x1,x2,x3,x4>=0
得到单纯形增广矩阵为：1，-6，-4，0，0，0
0， 2，3，1，0，100
0， 4，2，0，1，120
然后进行矩阵运算，化为: 1，0，0，1/2，5/4，200
0，1，0，-1/4，3/8，20
0，0，1，1/2，-1/4，20
（因为此题很简单，直接把矩阵前三列三行化为单位矩阵就可，不用搞什么基解，检验数，进基离基什么的。具体原理请参阅教材）。
然后得到解：最小值:200，x1=20,x2=20（矩阵最后一列）

线性目标函数在线性等式或线性不等式约束条件下的极值问题线性规划问题就是，内点法等等
；凸集论，最优解（满足约束条件同时使目标函数取极值的解）。
21，已有众多的软件可解决线性规划问题；单纯型法：可行解（满足约束条件的解），等等
3搜索法；优化理论相关概念

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解②若基本可行解不存在,即约束条件有矛盾,则问题无解③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善）,即得到问题的最优解⑤若迭代过程中发现问题的目标函数值无界,则终止迭代按照上面说的,如果基本可行解不存在,问题无解了而且初始解就是“初始可行解”当然不可能是非可行解

先将原题转化为标准模式，令z=-f，添加松弛变量x3,x4
max
z
=
2x1+3x2+0x3+0x4
st
x1
+
x2
+
x3
=
2
4x1
+6x2
+
x4
=
9
建立初始单纯形表
cj
2
3
0
0
cb
xb
b
x1
x2
x3
x4
θ
0
x3
2
1
1
1
0
0
x4
9
4
6
0
1
σj
2
3
0
0
将x2作为入基变量，求得θ为2,
3/2写入上表
cj
2
3
0
0
cb
xb
b
x1
x2
x3
x4
θ
0
x3
2
1
1
1
0
2
0
x4
9
4
6
0
1
3/2
σj
2
3
0
0
将x4作为离基变量，重新计算单纯形表
cj
2
3
0
0
cb
xb
b
x1
x2
x3
x4
θ
0
x3
1/2
1/3
0
0
-1/6
3
x4
3/2
2/3
1
0
1/6
σj
0
0
0
-1/2
存在非基变量x1的检验数σj=0，因此该题有无穷多最优解
其中一个最优解是x1=0,x2=3/2
得到max
z
=
9/2
得到min
f
=
-9/2

---