第一章离散最优化算法.doc

第一章 线性规划
　　线性规划是运筹学的重要分枝之一，诞生于第二次世界大战期间。战后得到了迅速发展。它的应用范围极为广泛。从农业上的作物轮作计划到大规模的军事行动计划；从港口间的船艇运行路线到物流的分配。研究者们把这些似乎无关的问题，统一个到同一个数学框架——线性规划。G．B．Dantzig给出简洁求解方法——单纯形方法（Dantzig，G．B，1963）
　　实际上，上个世纪三十年代中期，前苏联的数学家康特洛维奇已在生产组织和计划中，提出了一些数学方法。其中就含线性规划模型，并给出了其求解线性规划的一个方法，称之为解乘数法，尽管解乘数法在理论上和应用上都没有单纯形算法好，但他是首先用线性规划去解决实际生产问题的人之一。他在1939年的著作《生产组织与计划中的数学方法》中，讲述了九个应用问题。
　　由于高速的电子计算机的出现，线性规划的应用越来越广泛。人们发现对某些特殊的线性规划实例[16]，单纯形算法的迭代步数随变量个数的增加而以指数的速度增长。因此，从理论上看，单纯形算法所能解的线性规划，其变量个数不能太多。由此引起了对线性规划的算法研究的重视，自上世纪七十年代中期开始，出现了一系列新的方法。但这些算法都比较复杂，而且在变量个数不是太多的情况下，其计算的平均速度未必比单纯形算法好，所以本书对这些新的算法省略了。
　　本章重点地介绍了单纯形算法、修正的单纯形算法、对偶单纯形算法和原始——对偶算法。实际上只要掌握了单纯形算法及其原理，其它几个算法就容易理解了。本章最后提到了椭球算法，其目的是说明线性规划问题是有多项式时间算法的。
　　本章的内容与线性代数有关，对代数不太熟悉的读者，可以先复习一下线性代数的基本知识。
　　1．1 线性规划的基本概念
　　要回答什么是线性规划，先看几个线性规划的例子：
　　例1．1．1(运输问题) 设某种产品有m个产地：A1，A2，…，Am，其产量分别为a1，a2，…，am。该产品有n个需求地：B1，B2，…，Bn，其需求量分别为b1，b2，…，bn。已知从第i个产地Ai运单位产品到第j个需求地Bj的费用为Cij元。如何对产品进行调配，使在满足供需要求的情况下，使总的运费最小？这里我们假定，即供需平衡。
　　这一问题可化为下述数学模型：
(1．1—1)
(1．1—2)
(1．1—3)
xij≥0，i＝1，2，…，m，j＝1，2，…，n (1．1—4)
　　其中xij表示自产地Ai运往需求地Bj的产品数量；式(1．1—1)表示总的运费要求取最小值；式(1．1—2)表示从产地Ai运出去的数量等于Ai产地的产量；式(1．1—3)表示需求地Bj的需求量，等于运往Bj的数量；式(1．1—4)表示运送的数量非负。
　　这个模型表示在满足供需关系式求(1．1—2)～(1．1—4)条件下，求一组{xij}，使式(1．1—1)达到最小，这就是例1．1．1所要求的调运方案。
　　例1．1．2(资源分配) 某工厂现有m种资源，第i种资源的数量为bi，i＝1，2，…，m。用这m种资源可以生产n种产品。已知生产单位第j种产品需第i种资源的数量为aij，i＝1，2，…，m，j＝1，2，…，n。从中可获利cj元。问题是在现有资源的条件下，各种产品各生产多少才可能使总的利润最大？
　　若用xj表示第j种产品生产的数量，那么上述问题可表示为
(1．1—5)
，i＝1，2，…，m (1．1—6)
xj≥0，j＝1，2，…，n (1．1—7)
　　上述两个例子，虽然问题不同，但其数学模型的实质是相同的，都是在一组线性等式和（或）不等式约束下，求一个线性函数的极值（最大或最小值），这就是所谓的线性规划。
　　从外形上看，线性规划可以是各种各样的，我们把下述的线性规划称为标准形式：

，i＝1，2，…，m
xj≥0，j＝1，2，…，n
　　我们称xj为变量，为目标函数，而＝bi和xj≥0，i＝1，2，…，m；j＝1，2，…，n为约束条件。
　　任何一个线性规划问题都可以化为标准形式。比如，若某个约束条件为，则可以引进一个非负变量yi，用和yi≥0代替；同样，对，可用和yi≥0代之。我们称这样的yi为松弛变量。若线性规划中某个变量xj不要求非负，则可做一个代换，用代入目标函数和约束条件中，并增加约束和。若目标函数为求最小，则改为求最大并把目标函数的系数变号，即求改为。
　　为表述简单，通常我们用向量形式表示：
max CTX
(LP) AX＝b
X≥0
　　其中C＝（c1，c2，…，cn）Ｔ，b＝（b1，b2，…，bm）T，
　　A＝（P1，P2，…，Pn）且P＝（a1j，a2j，…，amj）T
　　x≥0表示x的每一分量xj≥0，j＝1，2，…，n。
　　这c，bi和aij通常取自于实数域；但在实际中经常取自于有理数域或整数集。
　　有时为方便，把线性规划也写成下述形式：
max CTX

xj≥0，j＝1，2，…，n
　　或 max CTX
AiX＝bi (i＝1，2，…，m)
　　其中Ai＝(ai1，ai2，…，ain) 表示A的第i行。
　　满足约束条件的X称为可行解，使目标达到最大的可行解，称之为最优解，最优解对应的目标值，称之为最优值。
　　我们始终假定A是m×n阶矩阵，n≥m且A的秩为m。由A的m个线性无关的列组成的矩阵，如B＝(PJ1，PJ2，…PJm)，称为A的一个基，基中的列称为基列，基列对应的变量称为基变量；不在基里的列称为非基列，非基列对应的变量称为非基变量。对于A的任一个基B＝（PJ1，PJ2，…，PJm），那么A分为两部分：A=（B，N），相应地X和C也分为两部分XT＝(，)，CT＝(，)。其中N表示非基列部分，XB和XN分别表示基变量向量和非基变量向量，因此，给定一个基B，（LP）可重写为
Max{+}
BXB+NXN＝b
XB≥0，XN≥0．
　　对于基Ｂ，那么方程组BXB＝b有唯一的解XB＝B－1b，若B－1b≥0，则称B为可行基，那么对应的解XB＝B－1b和XN＝0称为基可行解。在所有基可行解中使目标值达到最大的基可行解称为基最优解，而对应的基称为最优基。
　　设Ｂ是可行基，那么由约束条件
BXB＋NXN＝b
　　可以得 XB＝B－1b－B－1NXN。将它代入目标函数，
　　则有
　　 (1．1—８)
　　（）称为关于基Ｂ的检验数向量。由些可见，当Pj为基B中的列时，则检验数，显然，对应可行基B的基可行解的目标值为。
　　由最优解和基最优解的定义可知，最优解对应的目标值，不小于基最优解对应的目标值，进而，我们将证明二者相等。为此需要如下的一些基本概念。
　　引理1．1．1 设Xo是线性规划问题（LP）的一个可行解，则Xo是基可行解，当且仅当Xo的非零分量所对应A的列线性无关。
　　证明 必要性由基可行解的定义立即可得。
　　充分性：不失一般性，设>0，>0，…，>0；而对一切j>k，＝0。由假设知，P1，P2，…，Pk是线性无关的。因为A的秩为m，所以k≤m。当k＝m，（P1，P2，…，Pm）就是一个基，而{Xo1，Xo2，…，Xom}就是的唯一解，从而由基可行解的定义知Xo为基可行解。当ko必是基可行解。
　　不妨设Xo的头k个分量Xo1，Xo2，…，Xok是非零的，而其余分量均为0。如果Xo不是基可行解，那么由引理1．1知P1，P2，…，Pk必线性相关，即存在不全为零的数δ1，δ2，…，δk，使
1．1－9
　　不妨假定存在某δi>0，令

　　定义

　　则x*是（LP）的一个可行解。事实上，由ε的选取保证了对一切j＝1，2，…，k，，其次，

　　因此x*是可行解。进而，由ε的选取知，必有某一下标r，使，从而，即可行解x*比xo的正分量的个数至少小1。这与xo的假设矛盾。这就证明了xo是基可行解。
　　由引理1．2可见，一个线性规划问题若有最优解，则必有基最优解。下面的定理告诉我们基最优解一定是最优解。
　　定理1．1．3 一个线性规划，若有最优解，则最优解一定能在基可行解中找到。
　　证明 设Xo是一最优解，并且它是所有最优解中含有非零分量个数最小的最优解。我们将证明Xo就是基可行解。
　　假如Xo不是基可行解，设它的非零分量为xo1，xo2，…，xok，那么由引理1．1知P1，P2，…，Pk线性相关，即存在非全为零的数δ1，δ2，…，δk，使

　　首先我们证明对这组δj必有
（1．1—10）
　　事实上，对充分小的正数ε，令
（1．1—11）

　　则显然X（1）和X（2）是两个可行解，从而

　　由此可得式（1．1—10）。
　　然后，模仿引理1．2的证明，不妨设有某个δj>0，取，则由式（1．10）定义的X(1)是可行解，并且X(1)的非零分量的个数比Xo的非零分量的个数至少小1。另一方面，由式（1．1—10）得

　　即X(1)也是最优解，由于X(1)比Xo的非零分量个数少，故与X(0)的假设矛盾。
　　这个定理说明，求（LP）的最优解，只需在（LP）的基可行解中找即可，而（LP）的可行基的个数最多为个，因此（LP）的最优解可在有限个可行解中找到。然而，——当n较大时，很大，实质上它是一个指数函数，因此，用遍数可行基的方法找出（LP）的最优解是不可行的。
　　基于定理1．1．3，G．B．Dantzig 于1947年提出了搜索基最优解的方法——单纯形算法。
　　1．2单纯形算法
　　单纯形方法分两个阶段，第一阶段是寻求一个可行基及基可行解；第二阶段是从一个可行基出发进行迭代，即从一个可行靠基迭代到下一个可行基，使其基可行解的目标函数值逐步增加，直到某一个可行基B，使其检验数向量为止。我们先叙述单纯形算法的第二阶段，然后再讨论如何寻求第一个可行基。
　　假如已知B＝(PJ1，PJ2，…，PJm)是（LP）的一个可行基，那么相应地A，C和X被划分为A＝（B，N）CT＝（CTB，CTN）XT＝（XTB，XTN）。对A的每一列Pj，令
， boj＝CTBB－1Pj－cj，j＝1，2，…，n
而，boo＝CTBB－1b，
　　单纯形方法计算步骤：
　　Step1 若对一切j＝1，2，…，n，boj≥0，则步骤终止。XB＝B－1b，XN＝0为（LP）的最优解，否则选取下标S，使S＝min{j|boj<0}。
　　Step2 若对一切i＝1，2，…，m，bis≤0，即B－1PS≤0，则步骤终止，（LP）无有界最优解，否则取及变量下标Jr，使

　　Step3 用PS列替换B中PJr列，得到新的可行基（PJ1，…，PJr－1，PS，PJr＋1，…PJm）。（把它仍记为B，然后用新的可行基重新计算B－1Pj，B－1P－Cj，B－1b及B－1b）或者置

，
　　返回Step1
　　上述单纯形方法可以列表计算，虽然列表计算对计算机来说并非最好，但用手工计算却清楚简单。下面举一个例子。
　　例1．1 max{2x1＋x2＋ox3＋ox4＋ox5}
　　 x1＋x2＋x3＝5
　　 －x1＋x2＋x4＝0
　　 6 x1＋2x2＋x5＝21
　　 xj≥0 j＝1，2，3，4，5
　　B(P3，P4，P5)是可行基。这里J1＝3，J2＝4，J3＝5，而N＝(P1，P2)，又＝（0，0，0），＝（2，1），＝（x3，x4，x5），＝（x1，x2），B－1A－CT＝(bo1，bo2，bo3，bo4，bo5)＝(－2，－1，0，0，0)其余数据见下表，此表也称之为单纯形表。

－2
－1
0
0
0
0

1
1
1
0
0
5

－1
1
0
1
0
0

6
2
0
0
1
21
　　Step1 bo1＝－2，bo2＝－1，故取s＝1，即bos＝bo1。
　　Step2 b11＝1>0，b31＝6>1，故

　　而Jr＝5，r＝3(一般Ji表示第i个约束方程中基变量的下标，如J3＝5表示第3个约束方程中基变量为x5)，用Pi列替换B中列P5，得到新的可行基为（P3，P4，P1），它对应的单纯形表为

0

0
0

7

0

1
0

0

0
1

1

0
0

　　Step1 b02<0，从而S＝2。
　　Step2 b12＝，b22＝，b32＝均是正的，故

　　而Jr＝J1＝3，r＝1，即用第2列替换基中第3列得新的基（P2，P4，P1），对应的单纯形表为
0
0

0

0
1

0

0
0
－2
1

1
0

0

　　此时所有检验数boj≥0，因此得到最优解：，最优值为。
　　让我们从几何图形上看看这个算法的计算过程。首先把例1．1改写为下述等价形式：
max z＝{2x1＋x2}
x1＋x2≤5
－x1＋x2≤0
6x1＋x2≤21
x1，x2≥0
　　它是两个变量的线性规划，故可用下述几何图形表示之

图1．2．1
　　图中由A1A2A3A4构成的多边形中的点其坐标均满足上述不等式组，也就是可行解的集合，这个多边形的每一个顶点对应于一个基可行解，单纯形算法就是从一个基可行解（顶点）到它相邻的基可行解（顶点），直到某一个基可行解（顶为最优解为止。在这个例子里是从原点A1开始，即对应于初始基可行解（0，0，5，0，21），初始可行基为（P3，P4，P5），迭代一步走到顶点A4，它对应基可行解为，可行基为（P3，P4，P1），再迭代一步走到顶点A3，它对应的基可行解为对应的可行基为（P2，P4，P1）。
　　图中的虚线表示目标函数Z＝zx1+x2在Z＝0时的线，随着z值增加，这条虚线就沿箭头所指方向平行移动。当移动到A3时，它与可行域有唯一的交点就是A3。再继续前移就与可行域无交点了，所以，此时z达到最大值。
　　由上述算法可见，单纯形算法每次迭代目标函数值增加－bos·θ，当θ>0时，则－bosθ>0。这样每次得到的基可行解都是不同的。由于基可行解的个数≤，所以单纯形算法在有限步内结束。然而当θ＝0时，即某些bio＝0，基可行解可能不变，也就是说几个可行基可能确定同一个基可行解。此时基可行解称为是退化的。由于单纯形算法是从一个可行基迭代到下一个可行基，而不是从一个基可行解迭代到下一个基可行解，所以当问题退化时，可能出现可行基循环，而循环过程中目标值不变，这样永远也得不到最优解，但是在我们的上述算法中，使用了Bland的最小下标法则，从而避免了可行基循环的发生，因此这个单纯形算法在有限步内是能找到最优解，或者判定无有界最优解。
　　定理（1．2．1） 上述单纯形算法能在有限步内结束，或者找出最优解，或者判定无有界最优解（证明见Bland．R．G．1977）。
　　上述单纯形算法是从可行基开始的，有的问题（如上述例子）有明显的可行基，但这仅是个别情形。一般地说，必须设法找出一个可行基，下面介绍寻求第一个可行基的两个种方法：人造基方法和大M方法。为叙述方便，假设标准形（LP）中约束条件的右端常数向量b≥0，因为若有某个分量bi<0，则在该式两端乘以－1便可。
　　所谓人造基方法，是先解（LP）的一个辅助问题：
（LPS）
　　其中e是每个分量都为1的m维列向量；y是新引进的一个m维的变量向量，也称为人造变向量，Im是m×xm的单位矩阵。由于b≥0，显然Im是（LPS）的一个可行基，因此可以用上述单纯形方法求解。设其最优解为（），若其对应的最优值小于0，那么原问题（LP）无解，因为若（LP）有可行解，那么（LPS）的最优值必为0。因此，基最优解（）的目标值必为0，此时必有＝0，而（，0）为（LPS）的基最优解。这里有两种可能：所有的都是非基变量；此时为原问题（LP）的基可行解，即有了（LP）的一个可行基，从而可以用单纯形算法求解（LP）；另一种情形是某些是基变量，此时由于＝0，可用所在的方程中的任一个非基变量xs简换，从而得到（LP）的新的基可行解，其目标值仍为0，用这样的方法可得到不含的基可行解，从而可利用单纯形算法开始求解（LP）。
　　例1．2 max{－x1＋x2－x3}
　　x1－x2＋6x3＝2
　　x1＋x2＋2x3＝1
　　xj≥0，j＝1，2，3
　　先解辅助问题
max{－x4－x5}
x1－x2＋6x3＋x4＝2
x1＋x2＋2x3＋x5＝1
xj≥0，j＝1，2，3，4，5．
　　显然B＝(P4，P5)为可行基，对应的单纯形表为
-2
0
-8
0
0
-3

0
2
-4
0
2
-1

0
0
0
1
1
0
1
-1
6
1
0
2
0
-2
4
1
-1
1
0

1

1
1
2
0
1
1
1
1
2
0
1
1
1
2
0

此时辅助问题已得最优解: ，并且x4和x5均为非基变量，从而是原问题的基可行解，而B＝(P3，P1)是原问题的可行基。对应于可行基B＝(P3，P1)的原问题单纯形表为
0

0

0
0

0

1

0
1

1
2
0

1
0

至此已求出原问题的解。上述过程的前三个表是求解辅助问题，称之为第一阶段，后两个表是在前一阶段找出的可行基的基础上，求解给定的问题，称之为第二阶段。这就是所谓的单纯形算法的两阶段方法。
　　上述两阶段方法也可合在一起去做，称之为大M方法。设M是充分大的正数，所谓大M方法是用单纯形算法直接求解问题：
maxCTx－MeTy
Ax＋Imy＝b
x，y≥0
　　由于M足够大，所以当（LP）有解时，y必须为0，即得到的最优解（）中，＝0，从而就是（LP）的最优解。如果的某些分量不为0，则原（LP）问题无解，算法就结束了。
　　上述的单纯形算法是列表计算的，因此要存储一个（m＋1）×（n＋1）的一个表。实际上，我们从单纯形算法可看出；我们只要保存一个逆矩阵B－1，那么整个这张表中的元素均可计算出来，如：目标值为B－1b，检验数boj＝CTBB－1Pj－cj，表中第j列
（b1j，b2j，…，bmj）T＝B－1Pj，j＝1，2，…，n
（b10，b20，…，bm0）T＝B－1b
　　因此，当需要哪一列时，很快就会计算出来，关键问题是当有一个可行解B和B－1时，如何导出下一个可行基的逆矩阵。若能简单地计算出，那么就可以减少许多不必要的计算，而又不增加太多的计算，同时减少了存储量。
　　我们先看一下如何由导出能简单地计算出，假设有可行基B＝(PJ1，PJ2…PJm)，当用Ps列替换PJr列后的基为，即＝（PJ1…PJr－1，PS，PJr＋1，…PJm）。设

　　则有

　　因此，若已知，则很容易求出。现在把单纯形表的表上算法，可改为逆矩阵形式的算法，也称之为修正的单纯形算法。
　　修正的单纯形算法：
　　设B＝（PJ1，PJ2…PJm）是可行基，B－1＝(bij)
　　Step1 计算T1：＝CTBB－1
　　Step2 若对一切j＝1，2，…，n，若有T1Pj－Cj≥0则算法终止，XB＝B－1b XN＝0，为最优解，否则，取bos＝T1PS－CS<0且对一切j5 计算B－1rs
　　置
　　计算，置B←回Step 1
　　例1．3 max {2x1＋x2}
　　 x1＋x2＋x3＝5
　　 －x1＋x2＋x4＝0
　　 6x1＋2x2＋x5＝21
　　 xj≥0，j＝1，2，…，5
　　用修正的单纯形算法求解。
　　B＝(P3，P4，P5)是可行基。B－1＝B＝I
　　Step1 ＝（0，0，0） CTBB－1＝（0，0，0）＝T1
　　Step2 bo1＝T1P1－C1＝－2，S＝1。
　　Step3 计算
b11>0 b13>0
　　Step4 计算

　　求
　　 Jr＝5，r＝3
　　Step5 求

置B←
　　Step1 其中＝(0，0，2)
　　Step2 bo1＝T1P1－C1＝0 bo2＝T1P2－C2＝ <0，S＝2
　　Step3 计算
（B－1P2）T＝(2/3，4/3，1/3)
　　Step4 计算
（B－1b）T＝(3/2，7/2，7/2)
　　求
r＝1，Jr＝3
　　Step5 计算

　　用代替B，回Step1
　　Step1 ＝(1，0，2)．T1＝B－1
　　Step2 T1P1－C1＝0 T1P2－C2＝0 T1P3－C3＝ T1P4－C4＝0 T1P5－C5＝ 所有boj≥0
　　最优解为
　　 XN＝(x3，x5)T＝（0，0）T
　　最优值 B－1b＝31/4
　　1．3 线性规划的对偶理论
　　线性规划问题（LP）之对偶，定义为
min yTb
　　(DLP)
yTA≥CT
　　显然，（DLP）也是一个线性规划，其中y是m一维的列向量，每一分量称之为对偶变量。下面看一下（LP）和（DLP）有什么关系。
　　设B是（LP）的一个可行基，那么（LP）可写为：

　　那么当B为最优基时，则CTBB－1A－CT≥0即此时得到了（LP）的最优解XB＝B－1b，XN＝0，目标值为CTBB－1b，若此时令yT＝CTBB－1，则yTA≥CT，即y是（DLP）的可行解，其目标值也为CTBB－1b，关于（LP）和（DLP）之间有下述结果：
　　定理1．3．1 设X和Y分别为（LP）和（DLP）的可行解，则有
　　1，CTX≤yTb；
　　2，若CTX≤yTb，则x和y分别为（LP）和（DLP）的最优解；反之亦然。
　　证明 由于x是（LP）的可行解，那么在（DLP）的约束两端乘以x，由不等号不变，从而有
YTb＝YTAX≥CTX
　　这就完成了结论1，的证明。
　　由于（LP）的任意可行解X和（DLP）的任意可行解y，结论1，总是成立的，特别对（LP）的最优解和（DLP）的最优解也应成立。所以（LP）的最大值也要小于等于（DLP）的最小值。因此，当（LP）有可行解X和（DLP）有可行解Y，使CTX＝YTb，那么CTX必定达到了（LP）的最大值，而YTb也必达到 了（DLP）的最小值。从而X和Y分别是（LP）和（DLP）的最优解。反之，由单纯形算法可得。
　　由定理1．3．1可立即得下述结论：
　　推论 若（LP）的最优值无界，则（DLP）无可行解；类似地，若（DLP）最优值无界，则（LP）无可行解。
　　定理1．3．2 设X和Y分别为（LP）和（DLP）的可行解，则X和Y分别为（LP）和（DLP）的最优解，当且仅当每一个xj>0有＝cj．
　　证明 必要性。 由X和Y分别为（LP）和（DLP）的最优解，所以由定理1．5有
O＝YTb－CTX＝YTAX－CTX＝。
　　由于Y是（DLP）的可行解，故YTPj－cj≥0。又因xj≥0。所以对每一个j＝1，2…n，由
（YTPj－cj）xj＝0
　　可知，若xj>0，则必有YTPj＝cj。
　　充分性 由xj>0推出YTPj＝cj，从而有
　　，
　　故由定理1．3．1知，X和Y分别是（LP）和（DLP）的最优解。
　　1．4 对偶单纯形算法
　　（LP）的一个基B，若满足B－1A－CT≥0则称B是（LP）的对偶可行基。显然，若在（DLP）中令YT＝B－1，则YT是（DLP）的可行解。
　　单纯形算法是从一个可行基开始，由一个可行基迭代到另一个可行基，直到某一个可行基，而也是对偶可行基为止。对偶单纯形算法从一个对偶可地基开始，从一个对偶可行基迭代到另一个对偶可行基，直到某一个对偶可行基，而也是可行基为止。由此可见，单纯形算法和对偶单纯形算法是从两条不同的路线到达了同一终点。具体算法如下：
　　假如已有（LP）的一个对偶可行基B，那么与单纯形算法类似，A，C和x被划分为A＝(B，N)，CT＝(，)，XT＝(，)，对A的每一列Pj，令
，，
　　B－1Pj－Cj＝boj，boo＝B－1b，记B＝（，，…，）。
　　由于B是对偶可行基，所以检验数boj≥0，j＝1，2，…，n。有了第一个对偶可行基后，对偶单纯形算法可叙述如下：
　　Step1 若对一切i＝1，2，…，m，bio≥0，则得最优解，算法结束。
　　Step2 设Jr＝min {Jio| bio <0}，若对一切j＝1，2，…，n有brj≥0，则问题无解，算法结束。
　　Step3 计算

　　取，用Ps替换对偶可行基B中的列，这就得到了一个新的对偶可行基。如此同时计算：
j＝0，1，2…，n
，0≤i≠r≤m，0≤j≤n
　　置B← bij←ij，0≤i≤m，0≤j≤n，返回Step1
　　对偶单纯形算法也分为两个阶段，第一阶段也是寻找第一个对偶可行基，第二阶段就是上述所表明的对偶可行基的迭代。关于如何寻求第一个对偶可行基，稍后再说明。这儿先用一个数值例子，具体地说明该对偶单纯形算法第二阶段的具体操作。
max{－2x1－x2}
－3x1－x2＋x3＝－3
－4x1－3x2＋x4＝－6
－x1－2x2＋x5＝－2
xj≥0 j＝1，2，…，5
　　显然，由约束条件的系数矩阵的第3，4，5列可构成该问题的一个对偶可行基B＝(P3，P4，P5)，对应于对偶可行基B的对偶单纯形表为：

2
1
0
0
0
0

－3
－1
1
0
0
－3

－4
－3
0
1
0
－6

－1
－2
0
0
1
－2
由表可见，由于对基B而言，所有检验数非负，所以B是对偶可行基。
　　Step 1 由于b10＝－3，b20＝－6，b30＝－2均小于0，而基变量下标最小者在第一行，即r＝1，Jr＝3。
　　Step 2 由于b11和b12分别为－3和－1，均小于0，故执行1。
　　Step 3 。用P1替换B中的P3列，得新的对偶可行基

　　对应的对偶单纯形表为

0

0
0
－2

1

0
0
1

0

1
0
－2

0

0
1
－1
　　类似地计算可知，下一步是用P2列替换中的第4列，得新的对偶可行基为（P1，P2，P5）。再计算所对应的对偶单纯形表

0
0

0

1
0

0

0
1

0

0
0
1
－1
1
1

　　此时所有的bio≥0，从而得最优解：，，x3＝x4＝0，x5＝1，最优值为。
　　下面说明如何找出初始对偶可行基，首先找出（LP）的一个基（比如用高斯消除法找出A的一个基）B，不妨设为B＝（P1，P2，…，Pm），则（LP）可变换为：

i＝1，2，…，m
xj≥0 j＝1，2，…，n
　　其中xi，i＝1，2，…，m，为基变量，xj，j＝m≠1，…，n，为非基变量，若对j＝m＋1，…，n，均有boj≥0，则B不是对偶可行基，故可用对偶单纯形法直接求解，当存在boj<0时，我们引进一个新的变量xn+1和一个新的约束条件：，构造一个新的线性规划（其中M为充分大的数）：

（ELP） i＝1，2，…，m

xj≥0 j＝1，2，…，n，n＋1
　　显然（ELP）有一个基，基变量为x1，…，xm及xn＋1。设bok＝min{boj|j＝m＋1，…，n}，则bok＜0。在（ELP）中用xk替换基变量xn＋1得一组新的基，而这组新的基为（ELP）的对偶可行基，因此可以用对偶单纯形算法求解（ELP）。解的结果必是下述三种可能性之一：
　　1． （ELP）无解，此时原（LP）也必无解．
　　事实上，若（LP）有解，则取，则即为（ELP）的解。
　　2．（ELP）的最优解中，xn＋1是基变量．
　　此时在最优解中去掉分量xn＋1即得（LP）的最优解。
　　3． （ELP）的最优解中，xn＋1为非基变量。
　　此时有几种可能的情形：
　　（a） 目标函数值与M有关且随M增大目标值增大。此时（LP）无有界最优解。
　　（b） 目标值与M无关，此时（LP）的最优解可按下法得到：
　　设（ELP）的最优解中非零分量的值为
xJi＝αi＋βiM i＝1，2，…，m＋1
　　由于是最优解，所以βi≥0。若存在αi<0，则取M为

　　于是所有xi≥0，并且也是（LP）的最优解。
　　（c） 其余情形取M＝0。
　　现举一个例子，用以说明情形（a）和（b）：
　　例如
max{2x1－6x2}

　　引入松弛变量x3和x4得相应的（LP）：
max{2x1－6x2}
－x1―x2＋x3＝－2
－x1＋3x2＋x4＝3
x1，x2，x３≥0
　　显然有一个基B＝（P3，P4），但它不是对偶可行基，为此构造相应的（ELP）：
max {2x1－6x2}
―x1―x2＋x3＝－2
－x1＋3x2＋x4＝3
x1＋x2＋x5≥M
xj≥0 i＝1，2，…，5。
　　于是＝（P3，P4，P5）是它的一个基，并由此按上法可得它的一个对偶可行基（P3，P4，P1）。即用x1替换基变量x5。对应的对偶单纯形表为：
0
8
0
0
2
2M
0
0
1
0
1
－2＋M
0
4
0
1
1
3＋M
1
1
0
0
0
M
显然已达到了最优解，最优值为2M，随M的增加而趋于无穷，最优解对应的可行域顶点如下图中的A（M，0）

图1．4．1
　　如果在上例中把目标函数改为
max {－2x1＋6x2}
　　那么对应的最优对偶单纯形表为
0
0
0
2
0
6
0
0
1
0
1
－2＋M
1
0
0

0
1
0

　　最优值与M无关，且它的最优解为，，x3＝－2＋M，x4＝x5＝0，即对应顶点C，当取M＝2时，，，x3＝x4＝x5＝0，即对应顶点D。它就是所给问题的最优解。
　　前面介绍的单纯形算法和对偶单纯形算法都是行运算的，即某行乘上一个倍数加到另一行里。有时为了方便，我们可以把行操作变为列操作。
　　例如给定线性规划
Max x0＝CTX
(LP) AX＝B
X≥0
　　的一个可行基B＝（，，…，），令N＝（，，…，）
　　那么（LP）改写为：

　　或者写成分量形式：

i＝1，2，…，m
j＝m＋1，…，n
j＝1，2，…，n
　　一般地可表示为下述形式：
　　max x0

　　 i＝1，2，…，m
　　(LP) i＝m＋1，…，n
　　 xj≥0 j＝1，2，…，n
　　其中bio＝0，i＝m＋1，…，n；＝0，当i≠j且i＝m＋1，…，n；而＝－1，i＝m＋1，…，n。我们将单纯形算法在这张表上实施就变为列的操作：
　　当某个<0时，将引入基；然后选取一个离开基的变量，即取>0使

　　然后更新单纯形表：即从方程

　　中解出

　　将的表示式代入到目标涵数和其它方程中。亦即在下一个单纯形表中的元素为：
　　 ，i＝0，1，2，…，n
　　 j＝0，m＋1，…，n且j≠r ，i＝0，1，2，…，n
　　列举一个数值例子说明单纯形算法的列操作为过程：
max x0＝－x2＋3x3－2x5，
x1＋3x2－x3＋2x5＝7
－2x2＋4x3＋x4＝12
－4x2＋3x3＋8x5＋x6＝10
xj≥0
　　其中基变量为x1，x4，x6，非基变量为x2，x3，x5．

bio
－x2
－x3
－x5

－x2
－x4
－x5
x0
0
1
－3
2
9

2
x1
7
3
－1
2
10

0
x2
0
－1
0
0
0
－1
0
0
x3
0
0
－1
0
3

0
x4
12
－2
4
0
0
0
－1
0
x5
0
0
0
－1
0
0
0
－1
x6
10
－4
3
8
1

8

xi
bio
－x1
－x4
－x5
x0
11

x1
0
－1
0
0
x2
4

x3
5

x4
0
0
－1
0
x5
0
0
0
－1
x6
11
1

10
　　最优解为：
　　x1＝x4＝x5＝0
　　x2＝4
　　x3＝5
　　x6＝11
　　目标值x0＝11
　　同样，对偶单纯形算法也可以仿此进行列操作形式。
　　为了书写方便和后续需要，我们把（VLP）写为向量形式。
max x0

（VLP） xj≥0 j＝1，2，…，n
　　其中X＝(x0，x1，… ，xn)T，
　　而k＝j－m，j＝m＋1，…，n。
　　用tk＝表示非基变量；d＝n－m．
　　保证单纯形和对偶单纯形算法的收敛性，还有字典序技术。这儿只介绍字典序对偶单纯形算法。首先介绍一下字典序的概念．
　　设α＝（β0，β1，…，βn）是一个实向量，若α的第一个非零分量为正的，则称α为字典序正的，记为；若，则称α为字典序负的。若两个向量α1和α2，当，则称α1字典序大于α2，并记为；若，那么对任意的δ＞0，则。若α1，α2，…，αm为m个向量，当，j＝1，2，…，m且j≠i，则记；若，并且，那么

　　现在描述字典序的对偶单纯形算法：
　　Step 0 设B是（LP）的一个基，那么由B可得（LP）的表示形式为（VLP），求出

　　若，则转step 1 ；否则令

　　由这个方程解出