第五章 二次规划算法
§ 1二次规划问题
若非线性规划的目标函数为自变量的二次函数，约束条件又是线性的，就称这种规划为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解，由于许多方面的问题都可以抽象成二次规划的模型，下面的分析表明它和线性规划又有直接联系，因此受到较为广泛的关注。这方面的一个最直接的感受就是将一般的非线性规划归结为求解一系列的二次规划时（这大体相当于把非线性目标函数按Taylor公式展开取到二次项），其收敛速度要比改用线性规划快得多。
二次规划的数学模型可表示如下,
（1）
式中是对称矩阵，，秩，，为n维常向量。显然，二次规划的可行集为凸集。如果二次型的矩阵是半正定的，则是凸函数，因之问题（1）变成凸规划问题，从而其局部极值即为整体极值，并且Kuhn-Tucker条件不但是取极值的必要条件，而且还是充分条件。
对于问题（1），K-T条件具如下形式：
（2）
于是，若矩阵半正定，则求（1）的最优解问题归结为：若求得，，，满足（2），则相应的即为（1）的最优解。
为求解（2），文献[28]采用了引入目标函数的作法，实行单纯形迭代，并且规定迭代中和不得同时为基变量（为了满足（2）的第三个约束，通常称之为互补松弛条件），对于这样的特别处理，文献[28]称之为满足换基规定的单纯形法。文献[28]还进一步指出，在“规定”下进行单纯形迭代，一般说来，有可能迭代不下去。为此证明了在一定条件下，若迭代不下去，当前的解也是K-T条件（2）的解。
下边结合（2）的特殊结构对文献[28]中给出的“满足换基规定的单纯形法”做若干实质性的改进，并把它用于求解箱形约束的问题[35]，得到有限步收敛的简易结果。
§2．算法的改进
算法的改进可大体上归纳为以下三点：
（一）不必引入目标函数。
文献[28]引入目标函数，把问题（2）的求解归结为一个完整的线性规划问题，这当然是个进步，也是以往经常采用的作法。不过本问题这样做，除了增加n个变量外，还常常成为按“规定”迭代不能进行下去的一个原因。如果不引入目标函数，只是按照通常的作法，令，这里，则（2）变成：
（3）
于是问题归结为求出一个满足（3）的非负解。这当然比求有目标函数的最优解要少受限制和简易些。
（二）放宽因“规定”引起的限制。
为了满足（2）或（3）中的第三个约束，文献[28]做出如下规定：
若（或）已经是相应于第个极点的基变量，则（或）在第（）个极点的单纯形迭代中不能选为基变量，除非用（或）替换变量（或），此称为一种规定。
上述“规定”是充分的，即满足“规定”的最优解一定满足（2）中的互补松弛条件，因之是十分有意义的。从最终结果看一般也是必要的，除非某个基变量恰好取零值，否则便不是问题（1）的最优解。从这个意义上讲，完全取消“规定”是不可能的。
但是，我们觉得上述“规定”还是太严了些，其结果是迭代有可能进行不下去，虽然文献[28]下力气证明了即使迭代不下去也会得到满足（2）的解，但终归是在一定的条件下得到的结论，问题并没有完全彻底的解决。事实上，满足互补松弛条件只是对最终结果的要求，而迭代的中间过程，有时它不成立则是应当允许的，就是说在迭代中，如果出现和必须同为基变量，否则迭代便进行不下去的情形时，那就让这种情形发生好了，留待以后有机会再让其中的一个变量和离基就是了。于是我们得到如下的求解过程：
首先求出问题
（4）
的一个可行解（若（4）无可行解，则问题（1）无最优解），然后检查它是否满足
（5）
（注意，此时（2）中的互补松弛条件与（5）等价）若满足，则其中的即为（1）的K-T点，不然则把（5）看作是新增约束，继续迭代，直到求得一个满足（5）的可行解，或者证明不存在满足（5）的可行解（此时无K-T点）为止。
三．求解过程的优化。
由于（4）的特殊结构，可使其求解过程大大简化。具体分析如下：
1°首先，由于与在式中仅有符号相反之差别（在迭代过程中也是如此），故与最多仅有一个能做基变量，亦即至少有一个为0，从而可以略去，如果非要做基变量不可时，改变列的符号即得，此时一定为非基变量，去之无妨。今后约定仍用表示，实行上述变号后，则基变量也加负号成－。
2°（4）中第一式已有个现成的基变量，可充分利用之。即不必急于改变它们基变量的性质，而是先求出的一个可行解，不妨设其基变量为，则迭代结果总可得到下表：
表1
其中.对之可采取如下迭代步骤：
（i）若表1中，则已得到（4）的一个可行解，转（iii）。若不然，以（－1）乘的行，并去掉该行最左边的基变量，并把这些行叫做无基行，转（ii）。
（ii）先让进基，而主元优先选在（A）无基行中，（B）基变量所在行中。迭代中，由于我们略去了所在列，它与列仅符号相反。故对列，除了用正系数计算最小比值求得一元素，称之为准主元外，还应以负系数，取绝对值再求最小比值，确定另一准主元（这相当于在列选主元），稍有不同的是，若最后迭代主元选定为负系数，则迭代前应将该列元素全变号，且用代替。一般的，我们可以根据需要随时改变变量所在列的符号（若已为，则变号后又成为），进而找到更理想的主元。迭代结果若不存在无基行，转（iii），否则于当前的非基变量等所在列，选择主元，实行Gauss消元，直到不存在无基行为止，转（iii）。
迭代中，若对某无基行，出现常数项大于0，而该行其余系数小于或等于0，结束，此时问题（4）无可行解。
（iii）检查（4）的可行解是否满足（5），若满足，则已得问题（1）的K-T点，结束。若不然，则集合非空。任取一指标，考查基变量和所在行，若对（或）行除主元外已无正系数且的系数均为0（常数项除外），则（或）必为非0基变量，这时转而考查（或），若亦然，结束，问题（1）无K-T点。不然，于（或）行正系数所在列，确定准主元。若准主元不止一个，则于其中选择一主元，实行Gauss消元，优先选择满足（1°）落在（或）行的，（2°）迭代后不产生新的的，则集合中的元素至少减少1个，（3°）主元所在行的常数项不为0的，直到主元选在（或）行，迭代后返回（iii）。
如果迭代在各种选择之下均不可避免的出现循环，结束，说明集合永远非空，故问题无K-T点。
以上迭代程序表明，求解二次规划问题（1），有以下几种可能：
（A）（1）的可行集非空，矩阵半正定。此时问题（1）一定有解，且问题（4）的任一满足（5）的可行解均是（1）的最优解。
（B）矩阵非半正定，但问题（4）有满足（5）的可行解，则该可行解是问题（1）的K-T点，其最优解若存在则是诸K-T点中使目标函数达最小值者。
（C）问题（4）没有满足（5）的可行解，则问题（1）无K-T点，因此亦无最优解。
（D）问题（1）无满足的可行解。
§3．各种情形的例子
例1．已知
为半正定矩阵，，，
试求此二次规划问题（1）的解。
解：经简单计算可得相应的表1：
以（－1）乘第三行
三行成为无基行，右上角有圈的是准主元，方框内为主元
已得可行解，按（iii）宜选5为主元（行中的非基变量只有一个正系数）
不选因为（2°）
之（ⅱ）
至此可行解已满足（5），由之得最优解，，
例2．已知
（非半正定），，，
试求最优解。
解：对应的表1为：
至此，可行解已满足（5），故已得问题的K-T点：，
但由最终表格知可以进基，故若能离基，可得另一K-T点，迭代一步得：
由于上表第三行得非基变量的系数均为负值，故不可能等于0，这说明若作为非0基变量时，不能得到K-T点，故此问题有唯一的K-T点，故如问题有最优解则它即为。
例3．已知
，其余条件与例2同，则表1有形式：
至此，无基行（第一行）的系数全非正，而常数项又大于0，故说明对应问题（4）无可行解，进而原问题亦无最优解。
例4．已知
，，，
相应的表1为：
此行非基变量系数全为负，故必有，从而应在行的正系数所在列寻找主元
最末行非基变量系数全为负，故必有
至此，知必有，故问题没有满足（5）的可行解，这说明原问题无K-T点，从而亦无最优解。
§4 算法的理论分析
一、关于无基行
由于无基行中无基变量，因此在迭代中可能出现行中系数全非正（有基行不会发生此情形）的情形（若该行有的系数不为0，则应认为该行既有正系数又有负系数），这时，若无基行的常数项大于0，则问题（4）便无可行解，若常数项等于0，则该行非0系数对应的变量都必须取0值，结果该行成为恒等式，故可删去，取0值的变量亦应删去，称上述过程为置零处理（若系数均为正，而常数项为0，亦可实行置0处理）。经置零处理后，问题规模变小了，求解过程得以简化。上述分析可概括为下面的定理。
定理1、迭代中若对某无基行，出现系数全非正且的系数均为0而常数项大于0的情形，则问题（4）无可行解，从而问题（1）无最优解。若常数项为0，则经置零处理后，该无基行和取零值的变量均可去掉。
二、关于增加约束的处理
迭代中在求得（4）的一个可行解之后，需检查互补松弛条件约束（5）是否成立，亦即集合是否为空集，若非空，则任取，实行步骤（iii），则有以下结论：
定理2、对于任意的，实行步骤（iii）进行迭代的结果，则只有两种情形，一是主元选在（或）行，结果必有；否则必总有，从而问题（1）无K-T点。
证明：对问题（4）的可行解引入目标函数，则易见可得表如下所示：
按照单纯形法，显然在迭代之前应将基变量一行加于目标函数行。其结果得到的检验数行，除了基变量一列的那个值1外，便与基变量一行完全相同（迭代过程中也是如此），因此在行选正系数确定主元，等价于针对正检验数确定迭代主元。这样，按照单纯形法的理论，迭代结果只有两种可能，一是主元确定在一行，迭代后，检验数变成小于等于0（具体说除外，其余均为0），目标值变为0，就是说立得辅助问题的最优解，且。从而有。二是一行除基变量系数（仍为1）外，已无正系数，这说明检验数行已无正系数；从而亦可得到问题的最优解；不过此时有（若等于0，主元必可选在一行）；按照程序此时转而在一行实行上述过程，亦有两种结果，一是，从而亦成立；二是，这导致总有，说明问题（1）无满足（5）的点，进而无K-T点，自然就没有最优解。 证毕
依据定理2，对于任意，我们总可以通过Gauss消元，实现要么，要么。然而问题到此并未完全解决。迭代往往出现较为复杂的情形，就是说，虽然我们可能实现了，结果却可能导致另一。捺下个葫芦起来了个瓢，甚至出现循环现象，致使迭代无休止的进行。对此，有以下定理。
定理3、在任取，实行迭代程序的过程中，如果迭代在各种选择的情况下，均不可避免的出现循环，且始终保持非空，则问题（1）无K-T点。
证：注意到这样一个事实，即从任一个基可行解出发，通过Gauss消元，可以达到任一基可行解，从几何上看，这是显然的，因为从可行域的某一指定的顶点出发，实行一次Gauss消元，可达到其任一相邻顶点，然后再从相邻顶点出发，又可达到另一顶点，如此进行，总可达到任意一个顶点。注意到基可行解的有限性，故如果迭代不出现死循环，则可以跑遍每一个顶点。如果问题存在K-T点，则它必将在某—选择下经迭代后达到，从而导致不出现循环和集合为空集。这与定理假设矛盾，故问题无K-T点。
§5．对于箱形约束规划的应用
下面考虑将上面的分析结果应用于一种特殊情况，即所谓如下的箱形约束的问题。
（7）
这里和是维常向量，。
对于问题（7），K-T条件变成如下更简单的形式：
定理4、若对成立：
（8）
（9）
（10）
其中是向量的第个分量，则是问题（7）的K-T点。
由于（7）的约束可以写成
故（7）的K-T条件为：
（11）
注意到把（10）式的若干倍，加于（8）或（9），并不会改变（8）和（9）的符号。而若，则必有，这说明和至少有一个取0值，故仿前作法可将其中一个略去，这样（11）中的方程组可简化为
（此时相当于）（12）
其中对K-T点，若，则有，若，则。于是求K-T点归结为求满足（12）及约束的一个基本解。于是有如下的迭代程序：
（1°）对增广矩阵
（13）
实行Gauss消元，将其化成形如下边的典则形式：
（14）
若，则令，，此即（12），亦即（11）的解，进而为（7）的最优解，结束。若不然，则必有某，使或，转（2°）。
（2°）令 （15）
不妨设（若，则将从（15）的集合中去掉，考虑余集的最大值），以之为主元实行一次Gauss消元，并令（若（15）的最大值为）或（若（15）的最大值为）。重新计算各的值，返回（2°），直到（15）中的集合为空集为止，转（3°）。
（3°）对者，检查是否成立；对者，检查是否成立。否则以的系数为主元实行一次Gauss消元，返回（2°）。
例5．已知，，，，求最优解。
解：通过Gauss消元，把增广矩阵（13）化成典则形式（14）：
由此得，不满足约束，而，故应以为主元实行一次Gauss消元，并令，从而得
由此得，，，
它满足箱形约束，且由第二行算得：
，满足条件（12），故最优解为。
§ 1二次规划问题
若非线性规划的目标函数为自变量的二次函数，约束条件又是线性的，就称这种规划为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解，由于许多方面的问题都可以抽象成二次规划的模型，下面的分析表明它和线性规划又有直接联系，因此受到较为广泛的关注。这方面的一个最直接的感受就是将一般的非线性规划归结为求解一系列的二次规划时（这大体相当于把非线性目标函数按Taylor公式展开取到二次项），其收敛速度要比改用线性规划快得多。
二次规划的数学模型可表示如下,
（1）
式中是对称矩阵，，秩，，为n维常向量。显然，二次规划的可行集为凸集。如果二次型的矩阵是半正定的，则是凸函数，因之问题（1）变成凸规划问题，从而其局部极值即为整体极值，并且Kuhn-Tucker条件不但是取极值的必要条件，而且还是充分条件。
对于问题（1），K-T条件具如下形式：
（2）
于是，若矩阵半正定，则求（1）的最优解问题归结为：若求得，，，满足（2），则相应的即为（1）的最优解。
为求解（2），文献[28]采用了引入目标函数的作法，实行单纯形迭代，并且规定迭代中和不得同时为基变量（为了满足（2）的第三个约束，通常称之为互补松弛条件），对于这样的特别处理，文献[28]称之为满足换基规定的单纯形法。文献[28]还进一步指出，在“规定”下进行单纯形迭代，一般说来，有可能迭代不下去。为此证明了在一定条件下，若迭代不下去，当前的解也是K-T条件（2）的解。
下边结合（2）的特殊结构对文献[28]中给出的“满足换基规定的单纯形法”做若干实质性的改进，并把它用于求解箱形约束的问题[35]，得到有限步收敛的简易结果。
§2．算法的改进
算法的改进可大体上归纳为以下三点：
（一）不必引入目标函数。
文献[28]引入目标函数，把问题（2）的求解归结为一个完整的线性规划问题，这当然是个进步，也是以往经常采用的作法。不过本问题这样做，除了增加n个变量外，还常常成为按“规定”迭代不能进行下去的一个原因。如果不引入目标函数，只是按照通常的作法，令，这里，则（2）变成：
（3）
于是问题归结为求出一个满足（3）的非负解。这当然比求有目标函数的最优解要少受限制和简易些。
（二）放宽因“规定”引起的限制。
为了满足（2）或（3）中的第三个约束，文献[28]做出如下规定：
若（或）已经是相应于第个极点的基变量，则（或）在第（）个极点的单纯形迭代中不能选为基变量，除非用（或）替换变量（或），此称为一种规定。
上述“规定”是充分的，即满足“规定”的最优解一定满足（2）中的互补松弛条件，因之是十分有意义的。从最终结果看一般也是必要的，除非某个基变量恰好取零值，否则便不是问题（1）的最优解。从这个意义上讲，完全取消“规定”是不可能的。
但是，我们觉得上述“规定”还是太严了些，其结果是迭代有可能进行不下去，虽然文献[28]下力气证明了即使迭代不下去也会得到满足（2）的解，但终归是在一定的条件下得到的结论，问题并没有完全彻底的解决。事实上，满足互补松弛条件只是对最终结果的要求，而迭代的中间过程，有时它不成立则是应当允许的，就是说在迭代中，如果出现和必须同为基变量，否则迭代便进行不下去的情形时，那就让这种情形发生好了，留待以后有机会再让其中的一个变量和离基就是了。于是我们得到如下的求解过程：
首先求出问题
（4）
的一个可行解（若（4）无可行解，则问题（1）无最优解），然后检查它是否满足
（5）
（注意，此时（2）中的互补松弛条件与（5）等价）若满足，则其中的即为（1）的K-T点，不然则把（5）看作是新增约束，继续迭代，直到求得一个满足（5）的可行解，或者证明不存在满足（5）的可行解（此时无K-T点）为止。
三．求解过程的优化。
由于（4）的特殊结构，可使其求解过程大大简化。具体分析如下：
1°首先，由于与在式中仅有符号相反之差别（在迭代过程中也是如此），故与最多仅有一个能做基变量，亦即至少有一个为0，从而可以略去，如果非要做基变量不可时，改变列的符号即得，此时一定为非基变量，去之无妨。今后约定仍用表示，实行上述变号后，则基变量也加负号成－。
2°（4）中第一式已有个现成的基变量，可充分利用之。即不必急于改变它们基变量的性质，而是先求出的一个可行解，不妨设其基变量为，则迭代结果总可得到下表：
表1
其中.对之可采取如下迭代步骤：
（i）若表1中，则已得到（4）的一个可行解，转（iii）。若不然，以（－1）乘的行，并去掉该行最左边的基变量，并把这些行叫做无基行，转（ii）。
（ii）先让进基，而主元优先选在（A）无基行中，（B）基变量所在行中。迭代中，由于我们略去了所在列，它与列仅符号相反。故对列，除了用正系数计算最小比值求得一元素，称之为准主元外，还应以负系数，取绝对值再求最小比值，确定另一准主元（这相当于在列选主元），稍有不同的是，若最后迭代主元选定为负系数，则迭代前应将该列元素全变号，且用代替。一般的，我们可以根据需要随时改变变量所在列的符号（若已为，则变号后又成为），进而找到更理想的主元。迭代结果若不存在无基行，转（iii），否则于当前的非基变量等所在列，选择主元，实行Gauss消元，直到不存在无基行为止，转（iii）。
迭代中，若对某无基行，出现常数项大于0，而该行其余系数小于或等于0，结束，此时问题（4）无可行解。
（iii）检查（4）的可行解是否满足（5），若满足，则已得问题（1）的K-T点，结束。若不然，则集合非空。任取一指标，考查基变量和所在行，若对（或）行除主元外已无正系数且的系数均为0（常数项除外），则（或）必为非0基变量，这时转而考查（或），若亦然，结束，问题（1）无K-T点。不然，于（或）行正系数所在列，确定准主元。若准主元不止一个，则于其中选择一主元，实行Gauss消元，优先选择满足（1°）落在（或）行的，（2°）迭代后不产生新的的，则集合中的元素至少减少1个，（3°）主元所在行的常数项不为0的，直到主元选在（或）行，迭代后返回（iii）。
如果迭代在各种选择之下均不可避免的出现循环，结束，说明集合永远非空，故问题无K-T点。
以上迭代程序表明，求解二次规划问题（1），有以下几种可能：
（A）（1）的可行集非空，矩阵半正定。此时问题（1）一定有解，且问题（4）的任一满足（5）的可行解均是（1）的最优解。
（B）矩阵非半正定，但问题（4）有满足（5）的可行解，则该可行解是问题（1）的K-T点，其最优解若存在则是诸K-T点中使目标函数达最小值者。
（C）问题（4）没有满足（5）的可行解，则问题（1）无K-T点，因此亦无最优解。
（D）问题（1）无满足的可行解。
§3．各种情形的例子
例1．已知
为半正定矩阵，，，
试求此二次规划问题（1）的解。
解：经简单计算可得相应的表1：
以（－1）乘第三行
三行成为无基行，右上角有圈的是准主元，方框内为主元
已得可行解，按（iii）宜选5为主元（行中的非基变量只有一个正系数）
不选因为（2°）
之（ⅱ）
至此可行解已满足（5），由之得最优解，，
例2．已知
（非半正定），，，
试求最优解。
解：对应的表1为：
至此，可行解已满足（5），故已得问题的K-T点：，
但由最终表格知可以进基，故若能离基，可得另一K-T点，迭代一步得：
由于上表第三行得非基变量的系数均为负值，故不可能等于0，这说明若作为非0基变量时，不能得到K-T点，故此问题有唯一的K-T点，故如问题有最优解则它即为。
例3．已知
，其余条件与例2同，则表1有形式：
至此，无基行（第一行）的系数全非正，而常数项又大于0，故说明对应问题（4）无可行解，进而原问题亦无最优解。
例4．已知
，，，
相应的表1为：
此行非基变量系数全为负，故必有，从而应在行的正系数所在列寻找主元
最末行非基变量系数全为负，故必有
至此，知必有，故问题没有满足（5）的可行解，这说明原问题无K-T点，从而亦无最优解。
§4 算法的理论分析
一、关于无基行
由于无基行中无基变量，因此在迭代中可能出现行中系数全非正（有基行不会发生此情形）的情形（若该行有的系数不为0，则应认为该行既有正系数又有负系数），这时，若无基行的常数项大于0，则问题（4）便无可行解，若常数项等于0，则该行非0系数对应的变量都必须取0值，结果该行成为恒等式，故可删去，取0值的变量亦应删去，称上述过程为置零处理（若系数均为正，而常数项为0，亦可实行置0处理）。经置零处理后，问题规模变小了，求解过程得以简化。上述分析可概括为下面的定理。
定理1、迭代中若对某无基行，出现系数全非正且的系数均为0而常数项大于0的情形，则问题（4）无可行解，从而问题（1）无最优解。若常数项为0，则经置零处理后，该无基行和取零值的变量均可去掉。
二、关于增加约束的处理
迭代中在求得（4）的一个可行解之后，需检查互补松弛条件约束（5）是否成立，亦即集合是否为空集，若非空，则任取，实行步骤（iii），则有以下结论：
定理2、对于任意的，实行步骤（iii）进行迭代的结果，则只有两种情形，一是主元选在（或）行，结果必有；否则必总有，从而问题（1）无K-T点。
证明：对问题（4）的可行解引入目标函数，则易见可得表如下所示：
按照单纯形法，显然在迭代之前应将基变量一行加于目标函数行。其结果得到的检验数行，除了基变量一列的那个值1外，便与基变量一行完全相同（迭代过程中也是如此），因此在行选正系数确定主元，等价于针对正检验数确定迭代主元。这样，按照单纯形法的理论，迭代结果只有两种可能，一是主元确定在一行，迭代后，检验数变成小于等于0（具体说除外，其余均为0），目标值变为0，就是说立得辅助问题的最优解，且。从而有。二是一行除基变量系数（仍为1）外，已无正系数，这说明检验数行已无正系数；从而亦可得到问题的最优解；不过此时有（若等于0，主元必可选在一行）；按照程序此时转而在一行实行上述过程，亦有两种结果，一是，从而亦成立；二是，这导致总有，说明问题（1）无满足（5）的点，进而无K-T点，自然就没有最优解。 证毕
依据定理2，对于任意，我们总可以通过Gauss消元，实现要么，要么。然而问题到此并未完全解决。迭代往往出现较为复杂的情形，就是说，虽然我们可能实现了，结果却可能导致另一。捺下个葫芦起来了个瓢，甚至出现循环现象，致使迭代无休止的进行。对此，有以下定理。
定理3、在任取，实行迭代程序的过程中，如果迭代在各种选择的情况下，均不可避免的出现循环，且始终保持非空，则问题（1）无K-T点。
证：注意到这样一个事实，即从任一个基可行解出发，通过Gauss消元，可以达到任一基可行解，从几何上看，这是显然的，因为从可行域的某一指定的顶点出发，实行一次Gauss消元，可达到其任一相邻顶点，然后再从相邻顶点出发，又可达到另一顶点，如此进行，总可达到任意一个顶点。注意到基可行解的有限性，故如果迭代不出现死循环，则可以跑遍每一个顶点。如果问题存在K-T点，则它必将在某—选择下经迭代后达到，从而导致不出现循环和集合为空集。这与定理假设矛盾，故问题无K-T点。
§5．对于箱形约束规划的应用
下面考虑将上面的分析结果应用于一种特殊情况，即所谓如下的箱形约束的问题。
（7）
这里和是维常向量，。
对于问题（7），K-T条件变成如下更简单的形式：
定理4、若对成立：
（8）
（9）
（10）
其中是向量的第个分量，则是问题（7）的K-T点。
由于（7）的约束可以写成
故（7）的K-T条件为：
（11）
注意到把（10）式的若干倍，加于（8）或（9），并不会改变（8）和（9）的符号。而若，则必有，这说明和至少有一个取0值，故仿前作法可将其中一个略去，这样（11）中的方程组可简化为
（此时相当于）（12）
其中对K-T点，若，则有，若，则。于是求K-T点归结为求满足（12）及约束的一个基本解。于是有如下的迭代程序：
（1°）对增广矩阵
（13）
实行Gauss消元，将其化成形如下边的典则形式：
（14）
若，则令，，此即（12），亦即（11）的解，进而为（7）的最优解，结束。若不然，则必有某，使或，转（2°）。
（2°）令 （15）
不妨设（若，则将从（15）的集合中去掉，考虑余集的最大值），以之为主元实行一次Gauss消元，并令（若（15）的最大值为）或（若（15）的最大值为）。重新计算各的值，返回（2°），直到（15）中的集合为空集为止，转（3°）。
（3°）对者，检查是否成立；对者，检查是否成立。否则以的系数为主元实行一次Gauss消元，返回（2°）。
例5．已知，，，，求最优解。
解：通过Gauss消元，把增广矩阵（13）化成典则形式（14）：
由此得，不满足约束，而，故应以为主元实行一次Gauss消元，并令，从而得
由此得，，，
它满足箱形约束，且由第二行算得：
，满足条件（12），故最优解为。
