第四章 灵敏度分析
线性规划中所使用的数据,大多是些估计值,有的不够准确，这就需要研究当对某些数据作稍许改变时，最优解是否变化?如何变化?更何况实际情况还常有变动，特别经济问题是如此,象产品价格的变动,资源限制数的增减，约束条件的增减，变量的增减等等。这势必影响最优解和最优值。可见充分利用原最优表，分析最优解对某些数据变化的反应程度即灵敏度是十分必要的，同时也避免了因条件的些许改变而去从头求解，故灵敏度的分析亦称最优化后分析。
§1 一般分析
假定线性规划问题
(1)
的最优表已经得到：
…
基变量
min
不难看出，表中各块与参数的关系为：
1 与b,C无关
2 与C无关
3 与b无关
4目标函数值与b,C,A均有关
由此可知，当某些参数变化时，并不一定要重新计算整个单纯形表，而可以从原最优单纯形表出发，作适当修改后再求新的最优解.现将灵敏度分析的步骤大致归纳如下：
(Ⅰ)修改原最优单纯形表来反映参数的变化。
（Ⅱ）考察上述修改是否使最优解有所变化：
（ⅰ）检查表中最后一列基变量的值是否依旧非负，即验明解的可行性。
（ⅱ）检查所有检验数是否非正，即验明解的最优性。
（Ⅲ）把修改后的表作为初始单纯形表，重新迭代求优。
以下分别研究当参数之一发生变化时的情形。
(一)变化后的情况
设，此时原最优单纯形表仅最后一列需要修改，
(2)
显然，若，则对应的解仍为最优解，否则可用对偶单纯形法继续求解。
变化的情况
设，这时单纯形表中仅最后一行需要改变为：
(3)
(4)
若由（3）所表示的新检验数全部0，则原来的最优解仍是最优解，仅目标函数有如（4）式的变化。若新检验数有的为正时，则依修改后的表为基础，用单纯形法迭代求解。
变化后的情况
（ⅰ）非基变量的系数变化时，这时若时，则最优解与最优值均不变。若，则需将原最优单纯形表中对应的列修改为
(5)
然后用单纯形法迭代求优。
（ⅱ）当基变量的系数发生变化时，仍按（5）修改对应的列，并从最左边去掉基变量 。从联合算法的角度看，这是仅缺少一个基变量的情况，故可按第三章§5,针对未标出基变量这行，求一基变量，继之迭代求优。详见下一节.
设某线性规划问题的最优单纯形表为
x
x3
x1
x6
x2
0 0 1 -1 -1/4 0
1 0 0 0 1/4 0
0 0 0 -2 1/2 1
0 1 0 1/2 -1/8 0
0
4
4
2
f
0 0 0 -3/2 -1/8 0
-14
今将一列的值换为，问最优解和最优值将发生怎样的变化？
将表中一列值换成，并去掉左边的基变量，实行联合算法的迭代步骤，即可解决问题，具体如下：
x
x3
x6
x2
-9/4 0 1 -1 -1/4 0
5/4 0 0 0 1/4 0
-7/2 0 0 -2 1/2 1
11/8 1 0 1/2 -1/8 0
0
4
4
2
f
-21/8 0 0 -3/2 -1/8 0
-14
x3
x5
x6
x2
-1 0 1 -1 0 0
5 0 0 0 1 0
-6* 0 0 -2 0 1
2 1 0 1/2 0 0
4
16
-4
4
f
-2 0 0 -3/2 0 0
-12
x3
x5
x1
x2
0 0 1 -2/3 0 -1/6
0 0 0 -5/3 1 5/6
1 0 0 1/3 0 -1/6
0 1 0 -1/6 0 1/3
14/3
38/3
2/3
8/3
f
0 0 0 -5/6 0 -1/3
-32/3
故变化后的最优解为
最优值。
此问题若以为主元实行Gauss消元。其结果，得到的基本解，既不是基可行解，也不是正则解，故以往只能靠引入人工变量和正参数大M来求解。
§2 增加或减少一个约束条件
增加一个约束条件设增加的一个约束条件为
(6)
则应在原问题的最优表中按（6）提供的数据，增加一行，然后用消去法，把这行中基变量的系数消为0，从而化为仅缺少一个基变量且的问题，故可用联合算法迭代求优。
减少一个约束条件当需要减少一个约束时，并不是将最优表中，与该约束相应的行去掉就可以的，因为此约束的影响已通过Gauss消元施加在其它各行里了。那么，如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢？
设初始单纯形表中含有一个单位矩阵，不妨假定它是由辅助变量（松弛变量，剩余变量或人工变量等）形成，而最优单纯形表为：
… …
… …
… …
… …
… …
f
… …
现在要去掉原约束条件AX=b中的一个约束，不妨设为第t个约束，则对上表应采取如下步骤：
1、考虑原第t个约束所加辅助变量这一列，即（n+t）列，若为基变量，则去掉最优表中第t个约束行和（n+t）列即可（此时最优解与最优值均不变）。否则，若存在某<0，取
(7)
若，则取
(8)
然后以为主元实行Gauss消元，并去掉主元所在之行与n+t列。
2、考察新检验数是否仍非正，是，则已得去掉原第t个约束后的最优解；否，用单纯形法迭代求优。
某工厂去年根据市场需求和自身生产能力可以生产A，B两种产品，当时的条件如下表所示:
产品
单位消耗资源
A B
(千克) (千克)
资源可供应量
电(度)
设备(台时)
劳动力(小时)
流动资金(百元)
3
1
15
0.8 0.3
210
50
630
24
单位利润(百元)
4 3
据之可确定问题的初始单纯形表和最优表如下：
X1 X2 Y1 Y2 Y3 Y4
Y1
Y2
Y3
Y4
5 3 1 0 0 0
1 1 0 1 0 0
7 15 0 0 1 0
0.8 0.3 0 0 0 1
210
50
630
24
-f
4 3 0 0 0 0
0
X1 X2 Y1 Y2 Y3 Y4
X1
X2
Y3
Y1
1 0 0 -3/5 0 2
0 1 0 8/5 0 -2
0 0 0 -99/5 1 16
0 0 1 9/5 0 -4*
18
32
24
24
-f
0 0 0 -12/5 0 -2
-168
今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制。试问应如何调整生产，才能获得最大利润？
由初始表知关于流动资金的约束方程是第4个，相应松驰变量是，故考虑最优表 一列，由（7）得：
故应以为主元，实行Gauss消元后，并去掉4行，6列得
X1 X2 Y1 Y2 Y3
X1
X2
Y3
1 0 1/2 -3/2 0
0 1 -1/2 5/2 0
0 0 4 -27 1
30
20
120
-f
0 0 -1/2 -3/2 0
-180
这已经是最优表，按它进行调整，可增加利润180-168=12（百元）
注意：由（7）知，主元所在之行未必一定是原约束中要去掉的那一行，如在例2中，若因进口设备而欲将第二个约束去掉，计算结果，主元是，因而消元之后，去掉的却是第三行。此外,之所以先考虑(7)式是因为去掉约束，一般将使目标函数值减少，但绝不会增大。
方法的原理是很简单的，通过比较，不难看出，初始表中将要去掉的约束行所加辅助变量那一列仅有一个1而其余都是0,而在最优表中该列一般将发生变化,说明将要去掉的约束行的影响已经通过迭代施加到别的行中.注意,若从一开始就去掉那个约束,则所加辅助变量那一列全为0,并且在迭代中保持不变;因此,只有经过上面的处理，使所加辅助变量那一列又全变回为0,要去掉之约束在单纯形迭代中对其它约束施加的影响（即指此行的若干倍加于其它诸行），才被消除。此外，按照（7）或（8）选主元是为了保证所得解的可行性。
如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量一列,它由单位列向量最后变成的第t列,检验数由0变为C.因此,这时只需在最优表中增加一辅助列,对该列重复10和20的过程即可.
当然，对于有限资源利用型的问题（如例2），亦可采用如下处理办法：将要去掉的约束之常数项换成，按§1中有关常数项变化后的情形处理，最后令，不过这样作由于出现参数，给上机运算带来困难，故还是采用前述办法好些。
至于增加或减少变量的情形，处理起来比较简单容易，这里不多叙而留作练习。
§3*基向量变化的灵敏度分析
1方法介绍对于线性规划问题 (9)
设B是最优基，是一基变量，是的系数构成的基向量。现在假定变为，的目标函数系数变为，则对于式（9）的最优单纯形表中，用替换单位列向量，用替换相应的检验数0，然后实行一次Guass消元，使重新变换为原来的单位列向量，仍变为0。经上述变动后的表简称为初始表，记号照旧。这时虽然仍为基变量，但因常数项和检验数都发生了变化，故解的最优性及可行性都需加以检验并作相应的处理。以往的做法是：如果常数项仍非负，即可行性不变，则用单纯形法迭代求优；若常数项出现负值，同时检验数出现正值，即可行性和最忧性都被破坏，则必须引入人工变量及参数“大M”，建立新的单纯形表，重新计算，其中对引入参数“大M”，将导致很大的计算量和严重的甚至使计算失败的误差。因此，人们都竭力避免在实际计算中引入参数“大M”，而只用其理论成果进行某些分析推理。通常在寻找初始基可行解时，多采用“两阶段法”而不用“大M法”，其道理也在于此。可见以往引入“大M”的处理方法乃是不得己的，迫切需要改进。通过分析研究，我们发现，对于可行性和最优性均遭破坏的情形，既不必引入人工变量，也不用借助参数“大M”，只需使用把单纯形法和对偶单纯形法结合起来的联合算法，便可求出问题的最优解或断定无解，具体程序表述如下。
（1）于初始表中，以-1乘常数项为负数的行，并去掉该行左边的基变量，这样的行以后简称为无基行。若无基行有多个，可用下述方法使之只剩一个：取一无基行，比如常数项最小的，分别以该行的适当倍数加于其他无基行，使后者的常数项变为0，然后相继（可按行从小到大的顺序）在每一常数为0的无基行中取一非0元（如取列下标最小的）为主元，实行一次Guass消元，该无基行即变为有基行。如此进行，直到常数项为0的那些无基行全变为有基行为止。这样最后只剩下一个无基行，设它的行号为r，则其常数项，然后转（2）或（3）。
（2）针对正检验数所在列按照通常的规则或最速下降规则确定主元实行单纯形迭代、求优。迭代中若主元一直没能选在无基行（即该行元素不构成最小比值），且又遇到以下两情形之一，致使单纯形迭代无法进行时，则分别处理。
（a）所有检验数均非正，说明已满足最优性条件，故可用对偶法的选主元规则于第r行选一基变量，即取
(10)
（若式（10）中的集合为空集，结束，问题无可行解）然后以为主元实行Guass消元，便得一对偶可行解，继用对偶单纯形法迭代求优。
（b）虽有正检验数，但该j列系数。这时若，结束，问题无最优解；否则必有，故可采取下述所谓Q-处理：令，其中是事先取定的一个适当小的正数，然后把r行的Q倍加于目标函数行（此举使新检验数），其余不变，返回（2）。
（3）令，若R为空集，结束。问题无可行解。否则取，然后于t列按单纯形迭代计算最小比值，确定主元，若最小比值不唯一，则优先考虑s=r者，不然，就取行下标最小的。最后以为主元，实行Guass消元，若s=r，则迭代后已没有无基行，转（4），否则，返回（3）。
（4）按正常的单纯形法继续迭代、求优。
以上程序大体就是联合算法的程序。
2 理论依据步骤（1）的正确性是显然的。
步骤（2）中所述的情形（b）中关于无解的判断在联合算法一节中已经证明。
在情形（b）中所采取的把无基行的倍加于目标函数行的Q-处理，虽说不会改变问题的最优解，但由于此举使目标函数上升，从而破坏了其单调下降的性质，若上述过程不断出现，能否由之引发循环，致使迭代不能有限步达到最优解？文献[20]中的定理表明，如果问题有最优解，则Q-处理只能进行有限次，从而不会妨碍通常单纯形迭代的有限步收敛性。事实上，若进行无限多次，则相当于把r行的倍加于目标函数行，这相当于引入如第三章§5表2 的辅助问题，故有限步应有结果，即若，无解,已无无基行。
步骤（3）的合理性已在单阶段算法部分予以说明例3 设问题是第二章§5例1，其最优解表为
x1 x2 x3 x4 x5
x5
x2
x1
0 0 -1/3 0 1
0 1 1/6 1 0
1 0 7/6 0 0
7/3
29/6
17/6
f
0 0 -13/3 -2 0
34/3
现假定基变量的系数向量变为，目标函数系数变为，其余不变。求变化后的最优解。
解：
因可行基为
容易算得
于是
而原检验数变成
代入（11）得
x1 x2 x3 x4 x5
x5
x1
0 2/3 -1/3 0 1
0 -1/3 1/6 1 0
1 2/3 7/6 0 0
7/3
29/6
17/6
f
0 5/3 -13/3 -2 0
34/3
对于表（12），若以为主元迭代一次，将出现正检验数和负常数项。但从联合算法的角度看，表（12）只不过是属于缺少一个基变量且适宜用单纯形法迭代的情形，故很容易求解，具体过程如下
x1 x2 x3 x4 x5
x5
x1
0 2/3* -1/3 0 1
0 -1/3 1/6 1 0
1 2/3 7/6 0 0
7/3
29/6
17/6
f
0 5/3 -13/3 -2 0
34/3
x2
x1
0 1 -1/2 0 3/2
0 0 0 1* 1/2
1 0 3/2 0 -1
7/2
6
1/2
f
0 0 -7/2 -2 -5/2
11/2
x2
x4
x1
0 1 -1/2 0 3/2
0 0 0 1 1/2
1 0 3/2 0 -1
7/2
6
1/2
f
0 0 -7/2 0 -3/2
35/2
据此,基向量等变化的最优解为，最优值为
线性规划中所使用的数据,大多是些估计值,有的不够准确，这就需要研究当对某些数据作稍许改变时，最优解是否变化?如何变化?更何况实际情况还常有变动，特别经济问题是如此,象产品价格的变动,资源限制数的增减，约束条件的增减，变量的增减等等。这势必影响最优解和最优值。可见充分利用原最优表，分析最优解对某些数据变化的反应程度即灵敏度是十分必要的，同时也避免了因条件的些许改变而去从头求解，故灵敏度的分析亦称最优化后分析。
§1 一般分析
假定线性规划问题
(1)
的最优表已经得到：
…
基变量
min
不难看出，表中各块与参数的关系为：
1 与b,C无关
2 与C无关
3 与b无关
4目标函数值与b,C,A均有关
由此可知，当某些参数变化时，并不一定要重新计算整个单纯形表，而可以从原最优单纯形表出发，作适当修改后再求新的最优解.现将灵敏度分析的步骤大致归纳如下：
(Ⅰ)修改原最优单纯形表来反映参数的变化。
（Ⅱ）考察上述修改是否使最优解有所变化：
（ⅰ）检查表中最后一列基变量的值是否依旧非负，即验明解的可行性。
（ⅱ）检查所有检验数是否非正，即验明解的最优性。
（Ⅲ）把修改后的表作为初始单纯形表，重新迭代求优。
以下分别研究当参数之一发生变化时的情形。
(一)变化后的情况
设，此时原最优单纯形表仅最后一列需要修改，
(2)
显然，若，则对应的解仍为最优解，否则可用对偶单纯形法继续求解。
变化的情况
设，这时单纯形表中仅最后一行需要改变为：
(3)
(4)
若由（3）所表示的新检验数全部0，则原来的最优解仍是最优解，仅目标函数有如（4）式的变化。若新检验数有的为正时，则依修改后的表为基础，用单纯形法迭代求解。
变化后的情况
（ⅰ）非基变量的系数变化时，这时若时，则最优解与最优值均不变。若，则需将原最优单纯形表中对应的列修改为
(5)
然后用单纯形法迭代求优。
（ⅱ）当基变量的系数发生变化时，仍按（5）修改对应的列，并从最左边去掉基变量 。从联合算法的角度看，这是仅缺少一个基变量的情况，故可按第三章§5,针对未标出基变量这行，求一基变量，继之迭代求优。详见下一节.
设某线性规划问题的最优单纯形表为
x
x3
x1
x6
x2
0 0 1 -1 -1/4 0
1 0 0 0 1/4 0
0 0 0 -2 1/2 1
0 1 0 1/2 -1/8 0
0
4
4
2
f
0 0 0 -3/2 -1/8 0
-14
今将一列的值换为，问最优解和最优值将发生怎样的变化？
将表中一列值换成，并去掉左边的基变量，实行联合算法的迭代步骤，即可解决问题，具体如下：
x
x3
x6
x2
-9/4 0 1 -1 -1/4 0
5/4 0 0 0 1/4 0
-7/2 0 0 -2 1/2 1
11/8 1 0 1/2 -1/8 0
0
4
4
2
f
-21/8 0 0 -3/2 -1/8 0
-14
x3
x5
x6
x2
-1 0 1 -1 0 0
5 0 0 0 1 0
-6* 0 0 -2 0 1
2 1 0 1/2 0 0
4
16
-4
4
f
-2 0 0 -3/2 0 0
-12
x3
x5
x1
x2
0 0 1 -2/3 0 -1/6
0 0 0 -5/3 1 5/6
1 0 0 1/3 0 -1/6
0 1 0 -1/6 0 1/3
14/3
38/3
2/3
8/3
f
0 0 0 -5/6 0 -1/3
-32/3
故变化后的最优解为
最优值。
此问题若以为主元实行Gauss消元。其结果，得到的基本解，既不是基可行解，也不是正则解，故以往只能靠引入人工变量和正参数大M来求解。
§2 增加或减少一个约束条件
增加一个约束条件设增加的一个约束条件为
(6)
则应在原问题的最优表中按（6）提供的数据，增加一行，然后用消去法，把这行中基变量的系数消为0，从而化为仅缺少一个基变量且的问题，故可用联合算法迭代求优。
减少一个约束条件当需要减少一个约束时，并不是将最优表中，与该约束相应的行去掉就可以的，因为此约束的影响已通过Gauss消元施加在其它各行里了。那么，如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢？
设初始单纯形表中含有一个单位矩阵，不妨假定它是由辅助变量（松弛变量，剩余变量或人工变量等）形成，而最优单纯形表为：
… …
… …
… …
… …
… …
f
… …
现在要去掉原约束条件AX=b中的一个约束，不妨设为第t个约束，则对上表应采取如下步骤：
1、考虑原第t个约束所加辅助变量这一列，即（n+t）列，若为基变量，则去掉最优表中第t个约束行和（n+t）列即可（此时最优解与最优值均不变）。否则，若存在某<0，取
(7)
若，则取
(8)
然后以为主元实行Gauss消元，并去掉主元所在之行与n+t列。
2、考察新检验数是否仍非正，是，则已得去掉原第t个约束后的最优解；否，用单纯形法迭代求优。
某工厂去年根据市场需求和自身生产能力可以生产A，B两种产品，当时的条件如下表所示:
产品
单位消耗资源
A B
(千克) (千克)
资源可供应量
电(度)
设备(台时)
劳动力(小时)
流动资金(百元)
3
1
15
0.8 0.3
210
50
630
24
单位利润(百元)
4 3
据之可确定问题的初始单纯形表和最优表如下：
X1 X2 Y1 Y2 Y3 Y4
Y1
Y2
Y3
Y4
5 3 1 0 0 0
1 1 0 1 0 0
7 15 0 0 1 0
0.8 0.3 0 0 0 1
210
50
630
24
-f
4 3 0 0 0 0
0
X1 X2 Y1 Y2 Y3 Y4
X1
X2
Y3
Y1
1 0 0 -3/5 0 2
0 1 0 8/5 0 -2
0 0 0 -99/5 1 16
0 0 1 9/5 0 -4*
18
32
24
24
-f
0 0 0 -12/5 0 -2
-168
今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制。试问应如何调整生产，才能获得最大利润？
由初始表知关于流动资金的约束方程是第4个，相应松驰变量是，故考虑最优表 一列，由（7）得：
故应以为主元，实行Gauss消元后，并去掉4行，6列得
X1 X2 Y1 Y2 Y3
X1
X2
Y3
1 0 1/2 -3/2 0
0 1 -1/2 5/2 0
0 0 4 -27 1
30
20
120
-f
0 0 -1/2 -3/2 0
-180
这已经是最优表，按它进行调整，可增加利润180-168=12（百元）
注意：由（7）知，主元所在之行未必一定是原约束中要去掉的那一行，如在例2中，若因进口设备而欲将第二个约束去掉，计算结果，主元是，因而消元之后，去掉的却是第三行。此外,之所以先考虑(7)式是因为去掉约束，一般将使目标函数值减少，但绝不会增大。
方法的原理是很简单的，通过比较，不难看出，初始表中将要去掉的约束行所加辅助变量那一列仅有一个1而其余都是0,而在最优表中该列一般将发生变化,说明将要去掉的约束行的影响已经通过迭代施加到别的行中.注意,若从一开始就去掉那个约束,则所加辅助变量那一列全为0,并且在迭代中保持不变;因此,只有经过上面的处理，使所加辅助变量那一列又全变回为0,要去掉之约束在单纯形迭代中对其它约束施加的影响（即指此行的若干倍加于其它诸行），才被消除。此外，按照（7）或（8）选主元是为了保证所得解的可行性。
如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量一列,它由单位列向量最后变成的第t列,检验数由0变为C.因此,这时只需在最优表中增加一辅助列,对该列重复10和20的过程即可.
当然，对于有限资源利用型的问题（如例2），亦可采用如下处理办法：将要去掉的约束之常数项换成，按§1中有关常数项变化后的情形处理，最后令，不过这样作由于出现参数，给上机运算带来困难，故还是采用前述办法好些。
至于增加或减少变量的情形，处理起来比较简单容易，这里不多叙而留作练习。
§3*基向量变化的灵敏度分析
1方法介绍对于线性规划问题 (9)
设B是最优基，是一基变量，是的系数构成的基向量。现在假定变为，的目标函数系数变为，则对于式（9）的最优单纯形表中，用替换单位列向量，用替换相应的检验数0，然后实行一次Guass消元，使重新变换为原来的单位列向量，仍变为0。经上述变动后的表简称为初始表，记号照旧。这时虽然仍为基变量，但因常数项和检验数都发生了变化，故解的最优性及可行性都需加以检验并作相应的处理。以往的做法是：如果常数项仍非负，即可行性不变，则用单纯形法迭代求优；若常数项出现负值，同时检验数出现正值，即可行性和最忧性都被破坏，则必须引入人工变量及参数“大M”，建立新的单纯形表，重新计算，其中对引入参数“大M”，将导致很大的计算量和严重的甚至使计算失败的误差。因此，人们都竭力避免在实际计算中引入参数“大M”，而只用其理论成果进行某些分析推理。通常在寻找初始基可行解时，多采用“两阶段法”而不用“大M法”，其道理也在于此。可见以往引入“大M”的处理方法乃是不得己的，迫切需要改进。通过分析研究，我们发现，对于可行性和最优性均遭破坏的情形，既不必引入人工变量，也不用借助参数“大M”，只需使用把单纯形法和对偶单纯形法结合起来的联合算法，便可求出问题的最优解或断定无解，具体程序表述如下。
（1）于初始表中，以-1乘常数项为负数的行，并去掉该行左边的基变量，这样的行以后简称为无基行。若无基行有多个，可用下述方法使之只剩一个：取一无基行，比如常数项最小的，分别以该行的适当倍数加于其他无基行，使后者的常数项变为0，然后相继（可按行从小到大的顺序）在每一常数为0的无基行中取一非0元（如取列下标最小的）为主元，实行一次Guass消元，该无基行即变为有基行。如此进行，直到常数项为0的那些无基行全变为有基行为止。这样最后只剩下一个无基行，设它的行号为r，则其常数项，然后转（2）或（3）。
（2）针对正检验数所在列按照通常的规则或最速下降规则确定主元实行单纯形迭代、求优。迭代中若主元一直没能选在无基行（即该行元素不构成最小比值），且又遇到以下两情形之一，致使单纯形迭代无法进行时，则分别处理。
（a）所有检验数均非正，说明已满足最优性条件，故可用对偶法的选主元规则于第r行选一基变量，即取
(10)
（若式（10）中的集合为空集，结束，问题无可行解）然后以为主元实行Guass消元，便得一对偶可行解，继用对偶单纯形法迭代求优。
（b）虽有正检验数，但该j列系数。这时若，结束，问题无最优解；否则必有，故可采取下述所谓Q-处理：令，其中是事先取定的一个适当小的正数，然后把r行的Q倍加于目标函数行（此举使新检验数），其余不变，返回（2）。
（3）令，若R为空集，结束。问题无可行解。否则取，然后于t列按单纯形迭代计算最小比值，确定主元，若最小比值不唯一，则优先考虑s=r者，不然，就取行下标最小的。最后以为主元，实行Guass消元，若s=r，则迭代后已没有无基行，转（4），否则，返回（3）。
（4）按正常的单纯形法继续迭代、求优。
以上程序大体就是联合算法的程序。
2 理论依据步骤（1）的正确性是显然的。
步骤（2）中所述的情形（b）中关于无解的判断在联合算法一节中已经证明。
在情形（b）中所采取的把无基行的倍加于目标函数行的Q-处理，虽说不会改变问题的最优解，但由于此举使目标函数上升，从而破坏了其单调下降的性质，若上述过程不断出现，能否由之引发循环，致使迭代不能有限步达到最优解？文献[20]中的定理表明，如果问题有最优解，则Q-处理只能进行有限次，从而不会妨碍通常单纯形迭代的有限步收敛性。事实上，若进行无限多次，则相当于把r行的倍加于目标函数行，这相当于引入如第三章§5表2 的辅助问题，故有限步应有结果，即若，无解,已无无基行。
步骤（3）的合理性已在单阶段算法部分予以说明例3 设问题是第二章§5例1，其最优解表为
x1 x2 x3 x4 x5
x5
x2
x1
0 0 -1/3 0 1
0 1 1/6 1 0
1 0 7/6 0 0
7/3
29/6
17/6
f
0 0 -13/3 -2 0
34/3
现假定基变量的系数向量变为，目标函数系数变为，其余不变。求变化后的最优解。
解：
因可行基为
容易算得
于是
而原检验数变成
代入（11）得
x1 x2 x3 x4 x5
x5
x1
0 2/3 -1/3 0 1
0 -1/3 1/6 1 0
1 2/3 7/6 0 0
7/3
29/6
17/6
f
0 5/3 -13/3 -2 0
34/3
对于表（12），若以为主元迭代一次，将出现正检验数和负常数项。但从联合算法的角度看，表（12）只不过是属于缺少一个基变量且适宜用单纯形法迭代的情形，故很容易求解，具体过程如下
x1 x2 x3 x4 x5
x5
x1
0 2/3* -1/3 0 1
0 -1/3 1/6 1 0
1 2/3 7/6 0 0
7/3
29/6
17/6
f
0 5/3 -13/3 -2 0
34/3
x2
x1
0 1 -1/2 0 3/2
0 0 0 1* 1/2
1 0 3/2 0 -1
7/2
6
1/2
f
0 0 -7/2 -2 -5/2
11/2
x2
x4
x1
0 1 -1/2 0 3/2
0 0 0 1 1/2
1 0 3/2 0 -1
7/2
6
1/2
f
0 0 -7/2 0 -3/2
35/2
据此,基向量等变化的最优解为，最优值为
