第五章 变量有上限的线性规划问题
§1 以往算法介绍实际遇到的线性规划问题，大多是具有上界限制的问题（既有上界限制，又有下界限制的问题，容易化成只有上界限制的问题）。它的一般形式如下：
此问题的解法，以往不外两种：一是用松弛变量把限制（3）化成等式约束，使之变成具有(m+n)个约束方程，2n个变量的普通线性规划问题，然后求解。但这样做存储和计算都增加很多，故不认为是一种好的方法。二是根据新的判别条件，把检验数分成两种不同情形，有区别地作换基迭代。其优点是可以不扩大系数矩阵，算法具体步骤介绍如下：
引入松弛变量将（1）——（3）化成
（4）
则（4）为（m+n）个约束，2n个变量的(LP)。假定（4）中不含多余的约束，即其基变量的个数为（m+n）。其中，与同时均为基变量时，其个数记为。为基变量而为非基变量时,其个数记为。为非基变量（这时必为基变量）时，其个数记为，则应有关系：
从而有，即和都为基变量时，其总个数分别恰为m，这说明基可行解X中其余分量或为0，或为。据此可重新定义基可行解为：存在指标集合，满足
10满秩
20当时，或者
30
同样，当时，称为基变量；时，称为非基变量。令，当时,；当时，。于是典式具有如下形式：
(5)
据典式（5）易见；若对可行解有；，则对任意可行解有
可见是最优解。
不然，若有某。则令，其余不变，代入典式（5）得
可见，为保证可行性，Q应满足
它等价于
，当 （6）
当
显然，当。以及且对所有的，均有时，由（6）可令，从而，即此时原问题（1）——（3）无最优解。
否则，令
（若所有，置）
（若所有，则置）
取
①若，则以为主元，实行高斯消元。这时进基，离基，故。
②若，则于所在行的常数项减后，以为主元实行高斯Gauss消元。这时进基，离基，故
③若，则于常数项列减，i=1，目标函数减，这时仍为非基变量，但故k。
同样，若有，则令，其余不变，代入典式得：
则Q满足
它等价于
，当 （7）
当
令
（若所有，置）
（若所有，则置）
取
④若，则以为主元实行Gauss消元，然后于新基变量所在行常数项加，此时离基，故
⑤若，则于原基变量所在行的常数项减，然后以为主元实行Gauss消元，最后于新基变量这行的常数项上加d，此时=，故
⑥若，则于常数列加，目标函数加。此时仍为非基变量，故
根据以上分析，可以给出具体迭代步骤，这里略去（详见[13]）。
容易看出，若问题是非退化的，目标函数在迭代中严格下降，故有限步收敛。寻找初始基可行解的方法以往由两种：
增加人工变量，作
这个问题有明显的基可行解：
然后运用两阶段法，或者证明原问题（1）——（3）无解。或者得到它的一个基可行解。
利用通常的单纯形法，求解
若所求得的解，使（或者根本无可行解），则问题（1）——（3）也无可行解。相反，记
10、若，则已获问题（1）——（3）的基可行解。相反，任选，利用前面介绍的算法，继续求解问题：
设求得的解为
20、若，则问题无可行解。相反，修改，转步骤10
§2 一种新的解法前面介绍的方法，虽说不必扩大系数矩阵。但我们已经看到离基变量总共有六种选择，这时程序的复杂性和每步迭代的计算量都增加，而且寻找初始基可行解也不容易，下面我们给出一种解法，这种解法也不用扩大系数矩阵，而且迭代程序还十分简单，几与没有限制（3）的情形相同。方法的关键在于充分利用（3）的特殊性。
显然，如用x′表示的松弛变量，则（3）化成
（8）
这样亦可形式地把看成的松弛变量，从而有，并且与显然有相同的限制（3），知道了，可立即由（8）算出，反之亦然。
有了以上说明，新算法的说明可表述如下。
A）不考虑约束（3），用单纯形法对问题（1）—（2）实行寻优迭代，其间如单纯形表出现某检验数，而该列变量的系数，设与此对应的可行解为X，则有
（ⅰ）当，且对所有，均有时，原问题（1）—（3）无最优解；否则，选其它正检验数迭代，若已无其它正检验数，则当de〈+时，转（ⅱ）；当de=+时，转（ⅲ）。
（ⅱ）把这一列的数（包括）全变号，对常数项列的减去，该列目标函数减去，并对变量打撇，其余不变，继续迭代，直到求得最优表为止。设最终单纯形表的解为（注意若出现（ⅱ），则第e个分量为松弛变量的值）。转（B）。
（ⅲ）若存在某行，满足，且常数项，则将该行非基变量系数全变号，基变量打撇，常数项换成。然后以->0为主元实行Gauss消元，继续用单纯形法迭代求优，转（B）。否则，即对每一或者有di<i，或者有部分，转（B）之20。
（B）考察，
10若，则结合（8）可立得原问题（1）---（3）的最优解。否则，转20
20设，取
(9)
然后于最终单纯形表里将变量这列唯一的1变号，相应常数项变成=－，并对变量打撇，其余不变。这时若j=1，，则原问题（1）—（3）无解，终止。若不然，对无正检验数的情形，用对偶单纯形法迭代求优（若无最优解，则原问题（1）---（3）亦然）；设为，对，重复（B）以下过程。对由（ⅲ）转来的有正检验数情形可实行处理[20]（即将ik行的-倍加于检验数行），然后实行单纯形迭代（有正检验数时）或对偶单纯形迭代（无正检验数时），直到求得最优解（或断定无解），设为X1，对之重复（B）以下过程。
理论分析现对上述程序的正确性加以说明解释。
首先，步骤（A）中（ⅰ）的判断成立，我们有定理 如表1所示，设检验数如果de=+∞，且对所有=+则原问题（1）—（3）无解。
证明，设相应于（1）---（2）的典式
(10)
满足定理所述之条件。若由（10）确定的基可行解还满足（3），则它亦是（1）-（3）的可行解。令，其余非基变量仍为0，可解得：
因，故它构成（1）---（2）的一个可行解，又因，以及当时，故知此可行解亦满足（3）。从而是（1）---（3）的一个可行解，它使目标函数取值，故当时，目标函数值在可行解集合上无下界，因此问题（1）---（3）无最优解。
若由（10）确定的基可行解不满足限制（3），故必有某常数项，将限制约束
加到（10）中，由假定应有(因时，无限制），故单纯形表具如下形式：
（表1）
将行的（-1）倍加入行中，并在行中引入人工基变量及正参数M。则目标函数变成：，消掉一列中的-M后，则单纯形表具有如下形式：
1
0
f
0
(表2)
对（10）中不满足限制（3）的变量均照此办理，则不难看出处理后的一列数根本没变，即仍有,，这说明所得辅助问题无最优解，故原问题（1）---（3）无最优解。 证毕为了说明（A）之（ⅱ）处理正确，考虑增加约束
(11)
这时的单纯形表可设为
1 0 0
0 1 0
0 0 1* 0 1
f
0 0 0
(表3)
以为主元，迭代一次得
1 0 0 -
0 1 0 …-
0 0 1* 0 1
-
- d
f
0… 0 0 … -
(表4)
结果进基，离基，此时恰是新增约束（11）所表达的内容，现若再去掉新增约束这一行，则表4一列诸值恰好等于表1中列诸值变号，而常数项列由变成，目标函数由变成，这时表4中这列已全为0，可去之，今用相应松弛变量那一列取代它的位置。不去不添两方便，于是去掉新约束行（11）的表4可简化为：
1 0 -
0 1 -
-
-
f
0 0 -
-
（表5）
表5中是非基变量，它等于零，再由（11），可见表5与表4完全等价。这正是（A）之（ⅱ）所云者。
类似的，对表1增加约束：
(12)
可说明(ⅲ)的简化处理正确。
当出现（B）之20时，仍把问题看成在前一步最优解的基础上增加一个新限制
（13）
继之用单纯形法或对偶单纯形法处理，并且基于前面所述类似理由，亦不必增加新的行和列及其间的迭代过程便简化成如20所说的样子。
注意到采取上述处理的结果，对于非退化情形目标函数是严格上升的，而问题（1）---（3）的正则解又是有限的，故迭代必终止于有限步。
亦可按每步迭代使目标函数增值最大的原则选择20中的变量，以便减少迭代次数。
综上所述，新的算法是基于这样一种思想：首先找出无上限约束（3）的规划问题（1）-（2）的最优解（问题（1）—（2）通常称为（1）—（3）的松弛问题），这当然是很简便的，即使出现（A）之（ⅱ），也只需改动一下单纯形表中的个别数据，然后看此解是否满足（3），若满足，则其即为（1）——（3）的最优解，若不然，则它实质是（1）----（3）的一个正则解。而步骤（B）实质就是进行对偶单纯形迭代，这样整个迭代步骤也就清楚了（即对偶单纯形法的迭代步数），其特点是，初始正则解用普通单纯形法求得，从而避免了以往求初始的正则解带来的麻烦，也避免引进参数，而迭代中又不必扩大系数矩阵，必要时，除对单纯形表做个别改动外，与原来的单纯形法和对偶单纯形法处理无异。此外，由于本方法只涉及（3）中起作用限制，剔除了多余的约束，故实现了最大限度的简化，如将它与1中介绍的算法对照、比较。易见§1所述的三种可能值，在我们这里都至多由于增添一个约束而带来的单纯形表的小小变动而加以解决了。
例
初始表及迭代过程如下：
x1 x2 x3 x4 x5
x3
x4
x5
1 1 1 0 0
-1 1 0 1 0
6* 2 0 0 1
5
0
21
f
2 1 0 0 0
0
x3
x4
x1
0 2/3* 1 0 -1/6
0 4/3 0 1 1/6
1 1/3 0 0 1/6
3/2
7/2
7/2
f
0 1/3 0 0 -1/3
-7
x2
x4
x1
0 1 3/2 0 -1/4
0 0 -2 1 1/2
1 0 -1/2 0 1/4
9/4 （超上限）
1/2
11/4
0 0 -1/2 0 -1/4
-31/4
x2
x4
x1
0 -1 3/2* 0 -1/4
0 0 -2 1 1/2
1 0 -1/2 0 1/4
1/4 （实行（B）之20）
1/2
11/4
0 0 -1/2 0 -1/4
-31/4
x3
x4
x1
0 -2/3 1 0 -1/6
0 -4/3 0 1 1/6
1 -1/3 0 0 1/6
1/6
5/6
17/6
f
0 -1/3 0 0 -1/3
-23/3
由最终表知x1=17/6,x2，=0x2=2,x3=1/6,x4=5/6,x5=0，最优值f=-23/3。
作为练习，请试用1的方法解此例。
§1 以往算法介绍实际遇到的线性规划问题，大多是具有上界限制的问题（既有上界限制，又有下界限制的问题，容易化成只有上界限制的问题）。它的一般形式如下：
此问题的解法，以往不外两种：一是用松弛变量把限制（3）化成等式约束，使之变成具有(m+n)个约束方程，2n个变量的普通线性规划问题，然后求解。但这样做存储和计算都增加很多，故不认为是一种好的方法。二是根据新的判别条件，把检验数分成两种不同情形，有区别地作换基迭代。其优点是可以不扩大系数矩阵，算法具体步骤介绍如下：
引入松弛变量将（1）——（3）化成
（4）
则（4）为（m+n）个约束，2n个变量的(LP)。假定（4）中不含多余的约束，即其基变量的个数为（m+n）。其中，与同时均为基变量时，其个数记为。为基变量而为非基变量时,其个数记为。为非基变量（这时必为基变量）时，其个数记为，则应有关系：
从而有，即和都为基变量时，其总个数分别恰为m，这说明基可行解X中其余分量或为0，或为。据此可重新定义基可行解为：存在指标集合，满足
10满秩
20当时，或者
30
同样，当时，称为基变量；时，称为非基变量。令，当时,；当时，。于是典式具有如下形式：
(5)
据典式（5）易见；若对可行解有；，则对任意可行解有
可见是最优解。
不然，若有某。则令，其余不变，代入典式（5）得
可见，为保证可行性，Q应满足
它等价于
，当 （6）
当
显然，当。以及且对所有的，均有时，由（6）可令，从而，即此时原问题（1）——（3）无最优解。
否则，令
（若所有，置）
（若所有，则置）
取
①若，则以为主元，实行高斯消元。这时进基，离基，故。
②若，则于所在行的常数项减后，以为主元实行高斯Gauss消元。这时进基，离基，故
③若，则于常数项列减，i=1，目标函数减，这时仍为非基变量，但故k。
同样，若有，则令，其余不变，代入典式得：
则Q满足
它等价于
，当 （7）
当
令
（若所有，置）
（若所有，则置）
取
④若，则以为主元实行Gauss消元，然后于新基变量所在行常数项加，此时离基，故
⑤若，则于原基变量所在行的常数项减，然后以为主元实行Gauss消元，最后于新基变量这行的常数项上加d，此时=，故
⑥若，则于常数列加，目标函数加。此时仍为非基变量，故
根据以上分析，可以给出具体迭代步骤，这里略去（详见[13]）。
容易看出，若问题是非退化的，目标函数在迭代中严格下降，故有限步收敛。寻找初始基可行解的方法以往由两种：
增加人工变量，作
这个问题有明显的基可行解：
然后运用两阶段法，或者证明原问题（1）——（3）无解。或者得到它的一个基可行解。
利用通常的单纯形法，求解
若所求得的解，使（或者根本无可行解），则问题（1）——（3）也无可行解。相反，记
10、若，则已获问题（1）——（3）的基可行解。相反，任选，利用前面介绍的算法，继续求解问题：
设求得的解为
20、若，则问题无可行解。相反，修改，转步骤10
§2 一种新的解法前面介绍的方法，虽说不必扩大系数矩阵。但我们已经看到离基变量总共有六种选择，这时程序的复杂性和每步迭代的计算量都增加，而且寻找初始基可行解也不容易，下面我们给出一种解法，这种解法也不用扩大系数矩阵，而且迭代程序还十分简单，几与没有限制（3）的情形相同。方法的关键在于充分利用（3）的特殊性。
显然，如用x′表示的松弛变量，则（3）化成
（8）
这样亦可形式地把看成的松弛变量，从而有，并且与显然有相同的限制（3），知道了，可立即由（8）算出，反之亦然。
有了以上说明，新算法的说明可表述如下。
A）不考虑约束（3），用单纯形法对问题（1）—（2）实行寻优迭代，其间如单纯形表出现某检验数，而该列变量的系数，设与此对应的可行解为X，则有
（ⅰ）当，且对所有，均有时，原问题（1）—（3）无最优解；否则，选其它正检验数迭代，若已无其它正检验数，则当de〈+时，转（ⅱ）；当de=+时，转（ⅲ）。
（ⅱ）把这一列的数（包括）全变号，对常数项列的减去，该列目标函数减去，并对变量打撇，其余不变，继续迭代，直到求得最优表为止。设最终单纯形表的解为（注意若出现（ⅱ），则第e个分量为松弛变量的值）。转（B）。
（ⅲ）若存在某行，满足，且常数项，则将该行非基变量系数全变号，基变量打撇，常数项换成。然后以->0为主元实行Gauss消元，继续用单纯形法迭代求优，转（B）。否则，即对每一或者有di<i，或者有部分，转（B）之20。
（B）考察，
10若，则结合（8）可立得原问题（1）---（3）的最优解。否则，转20
20设，取
(9)
然后于最终单纯形表里将变量这列唯一的1变号，相应常数项变成=－，并对变量打撇，其余不变。这时若j=1，，则原问题（1）—（3）无解，终止。若不然，对无正检验数的情形，用对偶单纯形法迭代求优（若无最优解，则原问题（1）---（3）亦然）；设为，对，重复（B）以下过程。对由（ⅲ）转来的有正检验数情形可实行处理[20]（即将ik行的-倍加于检验数行），然后实行单纯形迭代（有正检验数时）或对偶单纯形迭代（无正检验数时），直到求得最优解（或断定无解），设为X1，对之重复（B）以下过程。
理论分析现对上述程序的正确性加以说明解释。
首先，步骤（A）中（ⅰ）的判断成立，我们有定理 如表1所示，设检验数如果de=+∞，且对所有=+则原问题（1）—（3）无解。
证明，设相应于（1）---（2）的典式
(10)
满足定理所述之条件。若由（10）确定的基可行解还满足（3），则它亦是（1）-（3）的可行解。令，其余非基变量仍为0，可解得：
因，故它构成（1）---（2）的一个可行解，又因，以及当时，故知此可行解亦满足（3）。从而是（1）---（3）的一个可行解，它使目标函数取值，故当时，目标函数值在可行解集合上无下界，因此问题（1）---（3）无最优解。
若由（10）确定的基可行解不满足限制（3），故必有某常数项，将限制约束
加到（10）中，由假定应有(因时，无限制），故单纯形表具如下形式：
（表1）
将行的（-1）倍加入行中，并在行中引入人工基变量及正参数M。则目标函数变成：，消掉一列中的-M后，则单纯形表具有如下形式：
1
0
f
0
(表2)
对（10）中不满足限制（3）的变量均照此办理，则不难看出处理后的一列数根本没变，即仍有,，这说明所得辅助问题无最优解，故原问题（1）---（3）无最优解。 证毕为了说明（A）之（ⅱ）处理正确，考虑增加约束
(11)
这时的单纯形表可设为
1 0 0
0 1 0
0 0 1* 0 1
f
0 0 0
(表3)
以为主元，迭代一次得
1 0 0 -
0 1 0 …-
0 0 1* 0 1
-
- d
f
0… 0 0 … -
(表4)
结果进基，离基，此时恰是新增约束（11）所表达的内容，现若再去掉新增约束这一行，则表4一列诸值恰好等于表1中列诸值变号，而常数项列由变成，目标函数由变成，这时表4中这列已全为0，可去之，今用相应松弛变量那一列取代它的位置。不去不添两方便，于是去掉新约束行（11）的表4可简化为：
1 0 -
0 1 -
-
-
f
0 0 -
-
（表5）
表5中是非基变量，它等于零，再由（11），可见表5与表4完全等价。这正是（A）之（ⅱ）所云者。
类似的，对表1增加约束：
(12)
可说明(ⅲ)的简化处理正确。
当出现（B）之20时，仍把问题看成在前一步最优解的基础上增加一个新限制
（13）
继之用单纯形法或对偶单纯形法处理，并且基于前面所述类似理由，亦不必增加新的行和列及其间的迭代过程便简化成如20所说的样子。
注意到采取上述处理的结果，对于非退化情形目标函数是严格上升的，而问题（1）---（3）的正则解又是有限的，故迭代必终止于有限步。
亦可按每步迭代使目标函数增值最大的原则选择20中的变量，以便减少迭代次数。
综上所述，新的算法是基于这样一种思想：首先找出无上限约束（3）的规划问题（1）-（2）的最优解（问题（1）—（2）通常称为（1）—（3）的松弛问题），这当然是很简便的，即使出现（A）之（ⅱ），也只需改动一下单纯形表中的个别数据，然后看此解是否满足（3），若满足，则其即为（1）——（3）的最优解，若不然，则它实质是（1）----（3）的一个正则解。而步骤（B）实质就是进行对偶单纯形迭代，这样整个迭代步骤也就清楚了（即对偶单纯形法的迭代步数），其特点是，初始正则解用普通单纯形法求得，从而避免了以往求初始的正则解带来的麻烦，也避免引进参数，而迭代中又不必扩大系数矩阵，必要时，除对单纯形表做个别改动外，与原来的单纯形法和对偶单纯形法处理无异。此外，由于本方法只涉及（3）中起作用限制，剔除了多余的约束，故实现了最大限度的简化，如将它与1中介绍的算法对照、比较。易见§1所述的三种可能值，在我们这里都至多由于增添一个约束而带来的单纯形表的小小变动而加以解决了。
例
初始表及迭代过程如下：
x1 x2 x3 x4 x5
x3
x4
x5
1 1 1 0 0
-1 1 0 1 0
6* 2 0 0 1
5
0
21
f
2 1 0 0 0
0
x3
x4
x1
0 2/3* 1 0 -1/6
0 4/3 0 1 1/6
1 1/3 0 0 1/6
3/2
7/2
7/2
f
0 1/3 0 0 -1/3
-7
x2
x4
x1
0 1 3/2 0 -1/4
0 0 -2 1 1/2
1 0 -1/2 0 1/4
9/4 （超上限）
1/2
11/4
0 0 -1/2 0 -1/4
-31/4
x2
x4
x1
0 -1 3/2* 0 -1/4
0 0 -2 1 1/2
1 0 -1/2 0 1/4
1/4 （实行（B）之20）
1/2
11/4
0 0 -1/2 0 -1/4
-31/4
x3
x4
x1
0 -2/3 1 0 -1/6
0 -4/3 0 1 1/6
1 -1/3 0 0 1/6
1/6
5/6
17/6
f
0 -1/3 0 0 -1/3
-23/3
由最终表知x1=17/6,x2，=0x2=2,x3=1/6,x4=5/6,x5=0，最优值f=-23/3。
作为练习，请试用1的方法解此例。
