线性规划与对偶

第四十六章

线性规划与对偶

46.1法卡斯引理的变体

如果a是m×n矩阵，如果b∈rm是向量，由线性代数可知，线性系统ax=b没有解，只要存在某种线性形式y∈（rm）使得ya=0和yb=06。这意味着y的线性消失在a1列，…，a的a列上，但不消失在b列上。由于线性形式y定义了方程y z=0的线性超平面h（用z∈rm），因此在几何上方程ax=b没有解，如果存在含有a1的线性超平面h，…，则方程ax=b没有解。不含b的d。这是一种分离定理，它表示向量a1，…，a和b可以被线性超平面h分离。

我们要做的是推广这种标准，首先是一个系统a x=b受约束x≥0，其次是一组不等式约束ax≤b和x≥0。确实有这样的标准以法卡斯·莱玛的名义存在。

关键是涉及多面体锥的分离结果，称为Farkas–Minkowski命题。我们有下面的基本分离引理。

提案46.1。设c rn为闭合的非空圆锥体。对于任意点a∈rn，如果a/∈c，则存在一个线性超平面h（到0），这样

1. c位于由h确定的两个半空间之一。

2. A/∈H

3. a位于由h决定的另一半空间。

我们说H严格地把C和A分开。

命题46.1是另一个分离定理的一个简单结果，该分离定理断言，给定任意两个非空闭凸集a和b，存在严格分离a和b的超平面h（这意味着a h=？，b h=？，a位于两个半空间中的一个确定由h决定，b位于由

一千四百六十九

h）；见Gallier[73]（第7章，推论7.4和命题7.3）。这个证明是不平凡的，涉及哈恩-巴纳赫定理的几何版本。

Farkas–Minkowski命题是46.1号命题，适用于多面体圆锥。

c=λ1a1+····+λnanλi≥0，i=1，…，n

其中a1，…，an是有限数量的向量ai∈rn。根据43.2，任何多面体锥都是闭的，所以46.1命题适用，我们得到了以下分离引理。

提案46.2.（farkas–minkowski）让c rn是非空多面体圆锥体c=圆锥体（a1，…，an）。对于任何点b∈rn，如果b/∈c，那么有一个线性超平面h（到0），这样

1. c位于由h确定的两个半空间之一。

2. B/∈H

3. B位于H所确定的另一半空间。

等价地，存在一个非零线性形式y∈（rn）这样

1. 当i=1，…，n时，yai≥0。

2. Yb<0.

本节末尾给出了不涉及46.1号提案的Farkas–Minkowski提案的直接证明。

注：应用于无限维实希尔伯特空间的Farkas–Minkowski命题有一个推广；见定理47.11（或Ciarlet[41]，第9章）。

命题46.2暗示了法卡斯引理的第一个版本。

提案46.3。（farkas-lemma，版本i）让a是m×n矩阵，让b∈rm

是任何向量。线性系统ax=b没有解x≥0，如果有一些非零线性形式y∈（rm）这样。

证据。首先，假设存在一个非零线性形式y∈（rm），使得yA≥0，yB<0。如果x≥0是ax=b的解，那么我们得到

Yax=Yb，

但如果yA≥0且x≥0，那么yAX≥0，但根据假设yB<0，这是一个矛盾。

接下来假设ax=b没有溶液x≥0。这意味着b不属于多面体圆锥体c=圆锥体（a1，…，an），由a.的列按命题跨越。

46.2，存在一个非零线性形式y∈（rm）这样：

46.1。法卡斯引理的变体

\1. j=1，…，n时，yaj≥0。

\2. Yb<0，也就是说Yb<0。

然后考虑形式a x≤b和x≥0的不等式系统的可解性。

提案46.4.（Farkas引理，第二版）让a是m×n矩阵，让b∈rm是任意向量。不等式系统ax≤b没有解x≥0，如果存在一些非零线性形式y∈（rm），那么，和yb<0。

证据。我们使用线性规划的技巧，它包括添加“松弛变量”zi，将不等式aix≤bi转换为等式aix+zi=bi，其中zi≥0在定义43.5之前已经讨论过。如果我们让z=（z1，…，zm），很明显系统a x≤b有一个解x≥0，如果方程

具有x≥0且z≥0的溶液。现在由Farkas I，上述系统没有x≥0和z≥0的解，如果存在一些非零线性形式y∈（rm），那么

Yb<0，即，和Yb<0。

在下一节中，我们使用FarkasII来证明线性规划中的对偶定理。观察到，通过对Farkas II中等价物的否定，我们得到了一个可解性的标准，即：

不等式系统a x≤b对于每一个非零线性形式y∈（rm）有一个解x≥0 iff，那么yb≥0。

我们现在证明了Farkas–Minkowski命题，而不使用46.1号命题。这种方法使用了距离函数从一个点到一个闭集的基本属性。

设x rn为任意非空集，设a∈rn为任意点。从A到X的距离d（a，x）定义为

d（a，x）=inf kA−xk。

这里x∈x，k k表示欧几里得范数。

提案46.5。设x rn为任意非空集，设a∈rn为任意点。如果x是封闭的，那么有一些z∈x，这样ka−zk=d（a，x）。

BallProof.br（sincea）=x x是非空的，选择任意∈rn kx−ak≤r，然后明确地选择x0∈x，并让r=ka−x0k。如果br（a）是关闭的

d（a，x）=xinfx ka−xk=x∈xinf br（a）ka−xk。γ

自x 7→k br（a）是紧凑的，x是封闭的，k=x br（a）也是紧凑的。但是在紧集k上定义的函数a−xk是连续的，而由连续函数定义的紧集的图像是紧凑的，因此由Heine–Borel定义的它有一个最小值，由一些z∈k x实现。

注：如果u是希尔伯特空间v的非空闭凸子集，则希尔伯特空间理论（投影定理）的标准结果断言，对于任何v∈v，都存在一个

唯一的p∈u，使得kv−pk=uinf∈u kv−uk=d（v，u），

和

HP−V，U−Pi≥0，适用于所有U∈U。

这里kwk=phw，wi，其中h−，−i是希尔伯特空间v的内积。

我们现在可以证明法卡—明可夫斯基命题（46.2号命题）。

Farkas–Minkowski命题的证明。设c=cone（a1，…，am）为多面体

假设线性超平面是一个圆锥点（非空），并假设that最接近b，因为b/b/∈∈c c and。根据命题43.2，多面体锥是z z∈cc，因此我们得到ud=（b，cz−）=b=06 kb−，我们要求zk；也就是说，z闭合，根据命题46.5，有一些

h与u正交，如图46.1所示。

首先让我们展示一下

hu，zi=hz−b，zi=0.（1）

如果z=0，这是微不足道的，所以假设z 6=0。如果hu，zi 6z=00∈，那么eitherc更接近bhtanu，zi z>是，一个矛盾。0或hu，zi<0。在这两种情况下，我们都可以找到一些点，案例1:hu，zi>0。

对于任何α，设z0=（1−α）z，使0<α<1。然后z0∈c，既然u=z−b，

z0−b=（1−α）z−（z−u）=u−αz，

所以

kz0−bk2=ku−αzk2=kuk2−2αhu，zi+α2 kzk2。

如果我们选取k 2α>20，使得α<2hu，zi/kzk2z，那么是−2αhu，zci+最接近α2 kzk2 b<。0，所以kz0−bk2<uk=kz−bk，与以下事实相矛盾：

病例2：胡，子<0.

46.1。法卡斯引理的变体

图46.1：垂直于z-b的超平面h将点b与c=圆锥体（a1，a2，a3）分开。

z0−letb=（1+z0=（1+α）zα−z（zfor any−u）=a使用+αz soα≥−1。那么z0∈c，既然u=z-b，我们有

kz0−bk2=ku+αzk2=kuk2+2αhu，zi+α2 kzk2，

如果

0<α<−2hu，zi/kzk2，

那么2αhu，zi+α2 kzk2<0，所以kz0−bk2<kuk2=kz−bk2，一个矛盾如上所述。

因此，hu，zi=0。我们有hu，ui=hu，z−bi=hu，zi−hu，bi−hu，bi，

既然u 6=0，我们有hu，ui>0，所以hu，ui=−hu，bi意味着

hu，bi<0.（2）

仍然需要证明，hu，aii≥0，对于i=1，…，m。选取任意x∈c，使x 6=z。我们声称

hb−z，x−zi≤0.（3）

否则，hbon的直线段[−z，x−zi>0，也就是说，z，xh]z相对于−b，x−bzithan<0，我们表明我们可以找到一些z。点Z0∈C

对于0≤α≤1的任何α，我们得到z0=（1−α）z+αx=z+α（x−z）∈c，由于z0−b=z−b+α（x−z），我们得到kz0−b k2=kz−b+α（x−z）k2=kz−bk2+2αhz−b，x−zi+α2 kx−zk2，因此对于任何α>0，这样

α<−2Hz−b，x−zi/kx−zk2，

假设我们有2αhzz−是b，x−zi+αc2 K的一个点，关闭tox−zk2<b.0，这意味着kz0−bk2<kz−bk2，相反-

由于hb−z，x−zi≤0，u=z−b，并且（1），hu，zi=0，我们有

0±Hb- z，x＝Zi= h，u，x＝Zi＝Hu，X+Hu，Zi= Hu，Xi，

也就是说

所有X的C，Hi，0，（3）

如要求。特别地，

hu，aii≥0，i=1，…，m.（4）

Yathen，by（i≥i2）=1 and，…，m（4），the linear form defined by，which expense the farkas–minkowski proposition.y=u>satives the properties Yb<0 and

0用于

还有其他方法来证明Farkas–Minkowski命题，例如使用最小不可行系统或Fourier–Motzkin消除；见Matousek和Gardner[120]（第6章，第6.6和6.7节）。

46.2线性规划中的对偶定理

设（p）为线性规划

最大化cx，以ax≤b和x≥0为准，

假设目标函数为m×n矩阵，假设（xp7→）有一个可行解，且在其上有界，cx有界于onax≤b，对于任意p（a，bx），它可能是有用的∈p（a，b）。我们可以从不等式中推导出cx的上界，如下所示：对于每个不等式

Ax≤Bi 1≤I≤m，

选取一个非负的标量yi，将上述不等式的两边乘以yi得到

yiaix≤yibi 1≤i≤m，

（由于yi≥0，不等式的方向保持不变），然后将这些m方程相加，得出

（y1a1+······+ymam）x≤y1b1+·····+ymbm。

如果我们可以选择yi≥0这样

c≤y1a1+·····+ymm，

那么，既然xj≥0，我们有

cx≤（y1a1+·······+ymm）x≤y1b1+····+ymbm，

也就是说，对于任意可行解x∈p（a，b），我们找到（p）目标函数的值cx的上界。如果我们让y是线性形式y=（y1，…，ym），那么

y1a1+·····+ymm=ya，y1b1+·····+ymbm=yb，我们所做的是寻找一些y∈（rm）这样

c≤ya，y≥0，

所以我们有

cx≤yb，对于所有x∈p（a，b）。（）

然后自然地寻找yb的“最佳”值，即最小值，这导致了线性规划（p）对偶的定义，这是约翰·冯·诺依曼提出的概念。定义46.1.给定任意线性规划（P）

最大化cx，以ax≤b和x≥0为准，

对于m×n矩阵，（p）的对偶（d）是以下优化问题：

根据Ya≥c和Y≥0将Yb最小化，

其中y∈（rm），原线性规划（p）称为原线性规划。

下面是一个线性程序及其对偶的显式示例。

例46.1。考虑图46.2所示的线性程序。

最大化2x1+3x2

4x1+8x2≤12

2x1+x2≤3 3x1+2x2≤4 x1≥0，x2≥0。

其双线性程序如图46.3所示。

最小化12y1+3y2+4y3，以

4y1+2y2+3y3≥2 8y1+y2+2y3≥3 y1≥0，y2≥0，y3≥0。

可以检验：（x1，x2）=（1/2,5/4）是原线性规划的最优解，目标函数2x1+3x2的最大值等于19/4，（y1，y2，y3）=（5/16,0,1/4）是双线性规划的最优解，目标函数的最小值为第12y1+3y2+4y3节也等于19/4。

0 0 0.5 1 1.5 2 x

图46.2：实施例46.1线性程序的H-多面体。注x1→x和x2→y。

观察到在初等线性规划（P）中，我们寻找一个向量x∈rn，使形式cx最大化，并且约束由矩阵a的行在x上的作用决定。另一方面，在对偶线性规划（D）中，我们正在寻找

图46.3：实施例46.1的双线程序的H多面体是“粉色平面上方”和“蓝色平面前方”的空间区域。注y1→x、y2→y和y3→z。

对于线性形式y（r）m，最小化形式yb，约束由y在a列上的作用决定，这是（d）是对偶（p）的意义。在大多数演示中，（p）和（d）在相互对偶的空间中搜索解决方案的事实被过度使用换位所掩盖。

为了将双程序（d）转换为标准最大化问题，我们将目标函数y b更改为−b>y>并且将不等式y a≥c更改为−a>y>≤−c>。双线性程序（d）现在表示为（d0）

最大化−b>y>受−a>y>的影响≤−c>和y>大于等于0，

式中y∈（rm）。观察双程序（D0）的最大化形式（D00）的双程序返回原始程序（P）。

上述讨论建立了以下不等式，即弱对偶性。提案46.6.（弱对偶）给定任何线性规划（P）

最大化cx，以ax≤b和x≥0为准，

利用m×n矩阵，对于初等问题（p）的任何可行解x∈rn和对偶问题（d）的每一可行解y∈（rm），我们得到

Cx≤Yb。

我们说双线性规划（d）是有界的如果是有界的下面。

如果x是（p）的最优解，如果y是（d）的最优解，会发生什么？我们有cx≤y b，但是否存在“二元性差距”，也就是说，cx<y b可能存在？

答案是否定的，这是强对偶定理。事实上，强对偶定理比这更能说明问题。

定理46.7。（线性规划的强对偶性）让（p）成为任何线性规划

最大化cx，以ax≤b和x≥0为准，

具有m×n矩阵。初值问题（P）有一个可行解，在iff上有界，对偶问题（D）有一个可行解，在iff下有界。此外，如果（p）有一个可行解并且在其上有界，那么对于（p）的每一个最优解x和（d）的每一个最优解y，我们有

cx=y b.

证据。如果（p）有一个可行解，并且在其上有界，那么我们从44.1命题中知道（p）有一些最优解。设x为（p）的任何最优解。首先，我们将证明（d）有一个可行的解v。

=cx是目标函数x 7→cx的最大值。然后对于任何大于0的

不平等制度

没有溶液，因为否则，μ不会是目标函数cx的最大值。我们要应用Farkas II，所以首先我们将上述不平等系统转化为系统

根据命题46.4（Farkas II），存在一些线性形式（λ，z）∈（Rm+1）使得λ≥0，z≥0，

和

也就是说

，

也就是说，

另一方面，由于x≥0是系统ax≤b的最优解，由farkas ii再次（取等价的否定），由于λa≥0（与之前相同的λ），我们必须

λb≥0.（1）

我们声称z>0。否则，因为z≥0，我们必须有z=0，但是

暗示

λb<0，（2）

由于λb≥0乘（1），我们有一个矛盾。因此，我们可以除以z>0而不改变不等式的方向，我们得到

结果表明，v=λ/z是对偶问题（d）的一个可行解。然而，弱对偶性（命题46.6）意味着，对于对偶程序（d）的任何可行解y≥0，cx==yb，因此（d）在下面是有界的，应用于（d）的一个最大化问题，我们得出（d）有一些最优解。对于（d）的任何最优解y，因为v是（d）的可行解，因此我们必须

由于我们的推理对任何>0都有效，因此我们得出结论：cx==y b。

如果我们假设对偶规划（d）有一个可行解，并且在下面有界，因为（d）的对偶是（p），我们得出（p）也是可行的，并且在上面有界。

强对偶定理也可以用单纯形方法证明，因为当它以（p）的最优解终止时，最后的表也产生（d）的最优解y，通过翻转它们的符号可以读出n+1，…，n+m列的降低成本。我们遵循CIARLET[41]中的证据（第10章）。定理46.8。考虑线性程序（P）

最大化cx，以ax≤b和x≥0为准，其等效版本（p2）为标准格式，

最大化C x BB

服从且x≥0，

乙

其中ab是m×（n+m）矩阵，bc是（rn+m）中的线性形式，xb∈rn+m，由

，

和（p）的对偶（d）由

根据Ya≥c和Y≥0将Yb最小化，

式中y∈（rm）。如果应用于线性程序（p2）的单纯形算法以最优解（u，k）终止，其中u是基本可行解，k是b的基

u，则是（d）的最优解，使得cu=y b。此外，y bbb是根据y=-（（ck）n+1…（ck）n+m的降低成本给出的。

证据。我们知道k是1，…，n+m的子集，由m个索引组成，因此ab的相应列是线性独立的。设N=1，…，N+M−K。单纯形法在（a）种情况下以最优解终止，即当

0表示所有j∈n，

其中abj=pk∈kγkjabk，或使用第45.3节的符号，

0表示所有j∈n。

上述不平等可以写成

，

或等同于

.（1）

目标函数的最佳解的值，由于满足方程b，目标函数的值为

（2）

那么，如果我们让，显然我们有，那么如果我们能证明y是对偶线性规划（d）的可行解，通过弱对偶，y是（d）的最优解。我们有

，（3）

到（1）我们得到

.（4）

设p为（n+m）×（n+m）置换矩阵，定义如下：

那么我们也有

利用方程（3）和（4），我们得出

，

也就是说，

相当于

，

那就是

y a≥c，y≥0，

正是这些条件说明Y是双方案（D）的可行解。

降低的成本由（c，i=1，…，n+m.给出，但是

乙

i=n+1，…，n+m每列abn+j是单位矩阵im的jth向量，所以

如要求。

上面的证明相当简短这一事实是有欺骗性的，因为这个证明依赖于这样一个事实，即使用透视规则的simplex算法版本可以防止循环，但是这种透视规则正确工作的证明是相当长的。其他证据见Matousek和Gardner[120]（第6章第6.3节）、Chvatal[40]（第5章）和Papadimitriou和Steiglitz[130]（第2.7节）。

观察到，由于最终表格的最后m行实际上是通过乘以b b得到的，因此由最后m列和最后m行组成的m×m矩阵是a−k1（基本上，simplex算法执行了高斯-乔丹约简的步骤）。这个事实允许在原始对偶方法中保存一些步骤。

将弱对偶性和强对偶性结合起来，得到了如下定理，证明了正是四种情况出现。

定理46.9。（线性规划对偶定理）设（p）为任意线性规划

最大化cx，以ax≤b和x≥0为准，

让（d）成为它的双重计划

根据Ya≥c和Y≥0将Yb最小化，

具有m×n矩阵。然后就出现了以下可能性之一：

(1) （p）和（d）都没有可行的解决方案。

(2) （p）是无界的，（d）没有可行的解。

(3) （p）没有可行解，（d）没有边界。

(4) （p）和（d）都有一个可行的解决方案。然后两者都有一个最优解，对于（p）的每一个最优解x和（d）的每一个最优解y，我们有

cx=y b.

定理46.9的一个有趣的推论是，存在一个确定线性程序（P）是否具有最优解的测试。事实上，（p）有一个最优解，如果满足以下约束集：

ax≤b ya≥c cx≥yb

x≥0，y≥0>m。

实际上，对于上述系统的任何可行解（x，y），x是（p）的最优解，y是（d）的最优解。

46.3补充松弛条件

强对偶定理的另一个有用的推论是下面的结果称为平衡定理。

定理46.10。（平衡定理）对于任何线性规划（p）及其对偶线性规划（d）（具有一组不等式ax≤b，其中a是m×n矩阵，目标

46.3。补充松弛条件

函数x 7→cx），对于（p）的任意可行解x和（d）的任意可行解y，x和y是iff的最优解。

yi=0，其中（d）

和

xj=0，对于所有j。（p）

证据。首先，假设（d）和（p）保持不变。（d）中的方程表示yi=0，除非，因此

同样地，（p）中的方程表示xj=0，除非，因此

因此，我们得到cx=yb。

根据弱二元性（命题46.6），我们有

cx≤yb=cx

对于（p）的所有可行解x，所以x是（p）的最优解。同样地，

Yb=cx≤Yb

对于（d）的所有可行解y，所以y是（d）的最优解。

现在假设x是（p）的最优解，y是（d）的最优解。那么，正如在第46.6号提案的证明中，

由于强对偶性，因为x和y是最优解，所以上述不等式实际上是相等的，因此我们特别有

由于X和Y是可行的，Xi为0，YJ为0，因此，如果我们必须具有XJ＝0。

同样，我们也有

，

如果，那么yi=0。

（d）和（p）中的方程通常称为互补松弛条件。在对偶问题的帮助下，这些条件可以用来求解原问题的最优解，反之亦然。实际上，如果我们猜测一个问题的解决方案，那么我们可以使用互补松弛条件来求解对偶的解决方案，然后检查我们的猜测是否正确。这就是原始对偶方法的本质。为了呈现这种方法，首先我们需要更仔细地观察已经在标准形式中的线性程序的对偶。

46.4标准形式线性程序的对偶性

设（p）为标准形式的线性规划，其中，对于某些m×n秩矩阵（p），a x=b，we m和一些目标函数x 7→cx（当然，x≥0）。为了得到m）×n的对偶，将方程ax=b转换为包含（2矩阵）的以下不等式系统。

然后，如果用（y0，y00）表示2 m双变量，用y0，y00∈（rm），则上述程序的双变量为

最小化Y0B−Y00B

以和y0为准，y00≥0，

其中y0，y00∈（rm），相当于

根据（y0−y00）a≥c和y0，y00≥0，将（y0−y00）b最小化，

其中y0，y00∈（rm）。如果我们写y=y0−d）：y00，我们发现上面的线性程序等价于下面的线性程序（

根据Ya≥C将Yb最小化，

式中y∈（rm）。注意，y不必是非负的；它是任意的。

接下来，我们想知道对于已经是标准形式的线性程序，定理46.8的版本是什么。这很简单。

定理46.11。以标准形式考虑线性程序（p2）

最大化cx，以ax=b且x≥0为准，

46.4。标准形式线性规划的对偶性

它的对偶（d）由

根据Ya≥C将Yb最小化，

式中y∈（rm）。如果应用于线性程序（p2）的单纯形算法终止于最优解（u，k），其中u是基本可行解，k是u的基础，则y=ck a k1是（d）的最优解，因此cu=y b。此外，如果假设simplex算法从一个基本可行解（u0，k0）开始，其中

klast0=（n−m+1，…，n a的m列构成单位矩阵）（m最后一个微柱的指数），然后是最优解a）和a（n−m+1，…，ny）==cikm a（对于（d）的−k1是根据减少的成本

y=c（n−m+1，…，n）−（ck）（n−m+1，…，n）

由最后m列和最后m行组成的m×m矩阵为−k1。

证据。定理46.8的证明适用于a而不是ab，我们可以证明

CK A−K1 AN≥CN，

y=ck a−k1满足，cu=y b，和

y ak=ck a−k1 ak=ck，y an=ck a−k1 an≥cn。设p为n×n排列矩阵，定义如下：

那么我们也有

，

利用上述方程和不等式，我们得到

，

即y ap≥cp，相当于

y a≥c，

这表明y是（d）的可行解（记住，y是任意的，因此不需要约束y≥0）。

降低的成本由

（ck）i=ci−ck a−k1 ai，

因为对于j=n−m+1，…，n列aj是单位矩阵im的第（j+m−n）列，我们有

（ck）j=cj−（ck ak）j+m−n j=n−m+1，…，n，

也就是说，

y=c（n−m+1，…，n）−（ck）（n−m+1，…，n）

如要求。由于最终表格的最后m行是通过将[u0 a]乘以−k1得到的，A的最后m列构成im，因此最终表格的最后m行和最后m列构成−k1。

现在让我们来看一下定理46.10的互补松弛条件。如果我们回到（p）的版本

最大化cx

服从且x≥0，

以及（d）的版本

最小化Y0B−Y00B

以和y0为准，y00≥0，

式中，y0，y00∈（rm），由于不等式ax≤b和−ax≤−b一起意味着ax=b，我们对所有这些不等式约束都是相等的，因此条件（d）对y0和y00根本没有约束，而条件（p）则断言

xj=0表示所有j。

如果我们写y=y0−y00，上述条件等于

xj=0表示所有j。

因此，我们得到了定理46.10的以下版本。

定理46.12。（平衡定理，第2版）对于任何标准形式的线性规划（p2）（等式组a x≤b，其中a是m×n矩阵，目标函数x 7→cx）及其双线性规划（d），对于（p）的任何可行解x和（d）的任何可行解y，x和y都是最优解。使用IFF

xj=0，对于所有j。（p）

因此，应用于标准形式的线性规划（p2）及其对偶（d）的松弛条件仅对原始问题的变量xj施加松弛条件。

上述事实在原始对偶方法中起着至关重要的作用。

46.5双单纯形算法

以标准形式给出线性程序（p2）

最大化cx，以ax=b且x≥0为准，

其中a是m阶m的m×n矩阵，如果没有明显的可行解，但c≤0，那么我们可以使用一种称为双单纯形算法的方法，而不是使用第45.2节中描述的寻找可行解的方法。该方法使用基本解（u，k），其中au=b和uj=0表示所有uj∈/k，但不要求u≥0，因此u可能不可行。但是，Y=CKA−K1对于双方案是可行的。

根据Ya≥C将Yb最小化，

式中y∈（r）m.由于c≤0，观察到这是对偶的一个可行解。

如果发现（p2）的基本解u使u≥0，那么y=cka−k1时cu=yb，我们发现（p2）的最佳解u和（d）的最佳解y。对偶单纯形法是通过尝试使U零的负分量和减少对偶程序的目标函数来实现的。

双单纯形法从ax=b的基本解（u，k）开始，这是不可行的，但y=cka-k1是双可行的。在许多情况下，原线性规划是由一组不等式ax≤b和一些bi<0所规定的，因此通过加上松弛变量很容易找到这样的基本解u，如果加上c≤0，那么由于松弛变量的相关成本为0，我们认为y=0是可行的。双重解决方案。

给定ax=b（可行与否）的基本解（u，k），y=c k a−k1是双可行的iff cka−k1a≥c，由于cka−k1ak=ck，不等式cka−k1a≥c等于cka−kaan≥cn，即：

CN−CKA−K1an≤0，（1）

式中n=1，…，n−k.方程（1）等于

Cj−ckγkj≤0，所有j∈n，（2）

式中γkj=a−k1aj。回想一下，符号cj用于表示cj−ckγkj，这被称为变量xj的降低成本。

在simplex算法中，我们需要确定哪个列a k离开基k，哪个列aj进入新的基k+，以（d）的可行解，即0，其中n+=1，…，n−k+。我们使用

第45.2号提案决定第k列应离开基础。

假设（u，k）是ax=b的解，其中y=cka-k1是双可行的。

案例（a）。如果u≥0，则u是（p2）的最优解。

案例（b）。有一些k∈k，使得uk<0。在这种情况下，选择一些k−k，使uk−<0（根据一些轴规则）。

案例（B1）。假设0代表所有j/∈k（实际上，代表所有j，因为代表所有j∈k）。如果是这样，我们认为（p2）是不可行的。

实际上，让v是一些基本可行的解。我们有v≥0和av=b，也就是说，

因此，通过将两边乘以−k1，并根据定义γkj=a−k1aj，我们得到

但回想一下，假设Uk−<0，而Vj≥0和γk j−≥0，所有j的指数k−的分量在左边为零或正，在右边为负，这是一个矛盾。因此，（p2）确实不可行。

案例（B2）。我们有些J有0。

我们选择AJ列，输入其中0的基础。由于我们假设所有j∈n的cj−ckγkj≤0（2），考虑

，

还有那套

我们选取一些指数j+∈n（礹+）作为进入基的列的指数（使用一些支点规则）。

回想一下，假设所有j/∈k的ci−ckγk i≤0，所有i∈k的ci−ckγki=0。

从0开始，对于任何索引0，我们都有0，从0开始

提案45.2

，

我们有0。对于任何指数i，如0，通过选择j+k，

，

所以

，

同样，Ci−ck+γki+≤0。因此，如果我们让k+=（k−k−）j+，那么是双重可行的。与单纯形算法一样，θ+由

，

而u+也可以用单纯形算法计算

u−θj+γij+如果i∈k

+=_θj i+，如果i=j+。

用户界面

0，如果i/∈k j+

主程序和双程序的目标函数的变化（这是相同的，因为选择了Uk=A−K1b和Y=CKA−K1，这样cu=ckuk=yb）与单纯形算法中的变化相同，即

我们有θ+>0和0，所以如果为0，则双程序的目标函数将严格减小。

案例（B3）。礹+=0.

可能出现礹+=0，即，=0的可能性。在这种情况下，目标函数不变。这是退化的情况，类似于单纯形算法中出现的退化。我们仍然选择J+∈N（μ+），但是我们需要一个防止循环的轴规则。存在此类规则；见Bertsimas和Tsitiklis[21]（第4.5节）和Papadimitriou和Steiglitz[130]（第3.6节）。

读者肯定注意到，双单纯形算法与单纯形算法非常相似，除了单纯形算法保留了（u，k）可行的性质，而双单纯形算法保留了y=cka-k1是双可行的性质。人们可能会怀疑，双单纯形算法是否等同于应用于双问题的单纯形算法。事实上，在对偶问题上，对偶单纯形算法和单纯形算法之间存在一对一的对应关系。Papadimitriou和Steiglitz【130】（第3.7节）中描述了这种对应关系。

如果我们使用（完整的）tableaux来描述这些方法，那么最好地说明单纯形算法和双单纯形算法之间的比较。

回想一下，（完整）表格是一个（m+1）×n+1）矩阵，其组织如下：

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
网络错误	网络错误网络错误	网络错误	网络错误网络错误	网络错误	网络错误网络错误
网络错误

······

顶行包含目标函数的当前值和降低的成本，第一列（除了顶行）包含当前基本解决方案UK的组件，其余列（除了顶行）包含向量。观察到与k中指数j对应的γkj构成单位矩阵im的置换。表格和新的基础k+=（k-k-）j+包含计算新的英国+、新的和新的降低成本所需的所有数据。

在执行单纯形算法时，所有k∈k都有Uk≥0（所有j/∈k都有Uj=0），输入列j+通过选择其中一个列索引来确定，这样cj>0。然后，通过查看其中0（沿J+列）的最小比率来确定离开列的索引k−。

另一方面，在执行双单纯形算法时，所有j/∈k的Cj≤0（所有k∈k的Ck=0），输出列k−通过选择其中一个行索引来确定，这样uk<0。进入列的索引j+通过查看比率−cj/γkj−的最大值来确定，其中0（沿行k−）。

关于单纯形算法和双单纯形算法的比较，可以在Bertsimas和Tsitiklis[21]以及Papadimitriou和Steiglitz中找到更多细节。

〔130〕。

下面是一个双单纯形方法的例子。

例46.2。考虑以下标准形式的线性程序：

最大化−4x1−2x2−x3

网络错误			网络错误网络错误网络错误	网络错误网络错误网络错误	网络错误网络错误网络错误	网络错误网络错误网络错误网络错误网络错误

0__

我们用（u，k）初始化双单纯形程序，其中u=−3和k=（4,5,6）。

 

−4_

1.在明确计算降低成本之前，初始表是

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
			网络错误网络错误网络错误	网络错误网络错误网络错误	网络错误网络错误网络错误	网络错误网络错误网络错误

因为u有负坐标，所以情况（b）适用，我们将设置k−=4。我们现在必须确定案例（b1）或案例（b2）是否适用。通过扫描表格中的前三列，观察每一列都有一个负的条目，可以完成这一确定。因此，情况（b2）是适用的，我们需要确定降低的成本。观察C=−4、−2、−1,0,0,0），这反过来意味着C（4,5,6）=（0,0,0）。方程式（2）表明，非零削减成本为

，

我们的舞台变成了

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
			网络错误网络错误	网络错误网络错误	网络错误网络错误	网络错误网络错误

由于k−=4，我们的轴列是表的第一行。为了确定J+的候选项，我们扫描此行，定位负条目并计算

因为μ+出现在j=2时，我们设置j+=2。我们的新基础是K+=（2,5,6）。我们必须规范化tableau的第一行，即乘以−1，然后将此规范化行的两倍添加到第二行，并从第三行减去规范化行，以获得更新的tableau。

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
网络错误网络错误	网络错误	网络错误			网络错误网络错误	网络错误网络错误

−−

它仍然需要更新降低的成本和目标函数的值，方法是将规范化行的两倍添加到顶层。

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
网络错误	网络错误	网络错误网络错误			网络错误网络错误	网络错误网络错误
网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误

我们现在重复案例（b2）的过程，并设置k−=6（因为这是唯一一个u+的负输入）。我们的Pivot行现在是更新后的TableAux的第三行，新的祄+变成了

，

这意味着j+=3。因此，新的基础是k+=（2,5,3），我们更新了表格，取第3行，将第3行标准化后的两倍添加到第1行，将第3行标准化后的三倍添加到第2行。

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
网络错误	网络错误	网络错误网络错误	网络错误网络错误		网络错误网络错误
网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误

−−

它仍然需要更新目标函数，并通过将标准化行的五倍添加到顶层来降低成本。

网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误
网络错误	网络错误	网络错误网络错误	网络错误网络错误		网络错误网络错误	网络错误
网络错误	网络错误	网络错误	网络错误	网络错误	网络错误	网络错误

−−

由于u+没有负项，双单纯形方法终止，目标函数

4x1−2x2−x3最大化为at（0，

46.6原始对偶算法

设（p2）为标准形式的线性程序

最大化cx，以ax=b且x≥0为准，

其中a是m×n矩阵的秩m，（d）是由

根据Ya≥C将Yb最小化，

式中y∈（rm）。

首先，我们可以通过改变每一个bi<0的方程来假设b≥0。

. 如果我们恰好有对偶程序（d）的一些可行解y，我们从定理46.12知道，（p2）的可行解x是（p）中方程的最优解。如果我们用j表示1，…，n的子集，其中的等式

yaj=cj

那么根据定理46.12，（p2）的可行解x是iff的最优解。

xj=0表示所有j/∈j。

设j=p和n 1，…，n−j。上面建议寻找x∈rn，这样

xxjaj=b

J·J·J

所有j的xj≥0∈j xj=0所有j/∈j，

或同等

ajxj=b，xj≥0，（1）

且xn=0n−p。

为了搜索这样一个x，只需要寻找一个可行的xj，为此，我们可以使用受限的原始线性程序（rp），定义如下：

最大化−（ξ1+····+ξm）

服从和x，ξ≥0。

由于假设b≥0，且目标函数在0上有界，该线性规划有一个最优解（x j，ξ）。

如果ξ=0，则由u j=x j和un=0n p给出的向量u rn是（p）的最优解。

否则，ξ>0，我们无法解决（1）。然而，我们可以尝试使用ξ来改进y。为此，考虑（rp）的双（drp）：

最小化zb，以zaj≥0 z≥−1>m为准。

观察程序（DRP）与原始双程序（D）具有相同的目标功能。我们通过定理46.11知道（rp）的最优解（x j，ξ）产生（drp）的最优解z，这样

事实上，如果k是与（）关联的基础，并且如果我们

然后根据定理46.11我们得到

，

其中（ck）（p+1，…，p+m）表示与最后m列对应的最终表格中降低成本的行向量。

如果我们写y（θ）=y+θz，

则（d）的目标函数的新值为

Y（θ）b=Yb+θz_b，（2）

由于z b<0，我们有机会改进（d）的目标函数，也就是说，如果y（θ）对（d）是可行的，那么减小θ>0的值就足够小。这是iff y（θ）a≥c iff的情况。

ya+θz a≥c.（3）

既然y是（d）的可行解，我们有yA≥c，所以如果z a≥0，那么（3）满足，y（θ）是（d）的解，对于所有θ>0，这意味着（d）是无界的。但这意味着（p）是不可行的。

让我们仔细看看不等式z a≥0。对于j j，由于z是（drp）的最优解，我们知道z aj≥0，所以如果z aj≥0对于所有j n，则（p）是不可行的。

否则，有一些j∈n=1，…，n−j这样

Z AJ<0，

然后根据j的定义，我们得到所有j∈n的yaj>cj，如果我们选取θ>0，那么

，

然后降低（d）的目标函数y（θ）b=yb+θz_b（因为z_b<0）。因此我们选择最好的θ，即

.（4）

接下来，我们将y更新为y+=y（θ+）=y+θ+z，并使用新的子集创建新的受限primal

j+=j∈1，…，n y+aj=cj，

然后重复这个过程。下面是原始对偶算法的步骤。

第1步。找到双程序（D）的一些可行解Y。稍后我们将展示这是永远可能的。

第2步。计算

j+=j∈1，…，n yaj=cj。

第3步。设置j=j+并使用simplex算法解决问题（rp），从上一轮确定的最优解开始，以k为基得到最优解（x j，ξ）。

第4步。

如果ξ=0，则停止（p）的最优解u，使u j=x j和u的其他组分为零。

否则就让

，

是（x j，ξ）与基k对应的（drp）的最优解。

如果所有j/∈j的z aj≥0，则停止；程序（p）没有可行的解。Else计算

，

和

j+=j∈1，…，n y+aj=cj。

回到步骤3。

下面的命题表明，在每次迭代中，我们都可以用在前一次迭代中获得的最优解来启动程序（RP）。

提案46.13。每个j j，使aj在最优解的基础上，ξ属于下一个指标集j+。

证据。这样一个指数j∈j对应于一个变量ξj，使得ξj>0，因此通过互补松弛度，双程序（drp）的约束z aj≥0必须是一个等式，即z aj=0。但是，我们有

y+aj=yaj+θ+z aj=cj，

说明J∈J+。

如果（u，ξ）以k为基础是程序（rp）的最优解，命题

46.13加上定理46.11的最后一个性质，我们可以用（u，ξ）k作为初始解（以k为基）重新启动步骤3中的（rp）。对于每个j∈j−j+，删除j列，对于每个j∈j+−j，新列aj通过将ab−k1和aj相乘来计算，但它是矩阵[1:m；p+1:p+m]，由最后表格中的最后m列组成，新的减少的cj由cj−z aj给出。重复使用以前的最优解（RP）可以显著提高效率。

另一个重要的观察是，对于任何指数j0∈n，比如θ+=（yaj0−cj0）/（−z aj0），我们都有

y+aj0=yaj0+θ+z aj0=cj0，

所以j0∈j+。这一事实用于确保原始对偶算法以有限的步骤终止（使用防止循环的轴规则）；见Papadimitriou和Steiglitz[130]（定理5.4）。

如何选取对偶规划（D）的一些初始可行解Y仍有待讨论。如果j=1，…，n的cj≤0，那么我们可以选择y=0。

我们应该注意，在许多应用中，自然的原始优化问题实际上是最小化一些目标函数cx=c1x1+·····+cnxn，而不是最大化。例如，Papadimitriou和Steiglitz[130]中考虑的许多优化问题都是最小化问题。

当然，最小化cx等同于最大化−cx，所以我们的演示也包括最小化。但是，如果我们处理的是最小化问题，那么权重Cj通常是非负的，因此从最大化的角度来看，我们将所有j的−Cj≤0，并且我们可以使用y=0作为起点。

回到最大化形式的原问题和最小化形式的对偶问题，我们仍然需要处理一些j的cj>0的情况，在这种情况下，（d）可能没有任何明显的y可行。最好是我们想找到这样一个非常便宜的Y。

处理这种情况有一个诀窍。我们选取一些非常大的正数m，把新的方程加在方程组ax=b上。

x1+·····+xn+xn+1=m，

新变量xn+1被约束为非负。如果程序（P）有一个可行的解，则存在这样一个M。事实上，它可以证明，对于任何基本可行解u=（u1，…，un），每个ui_都被一些仅依赖于a和b的表达式所限定；参见papadimitriou和steiglitz[130]（引理2.1）。证明并不困难，它依赖于这样一个事实：矩阵的逆矩阵可以用某些行列式（调节器）来表示。不幸的是，这个绑定包含m！作为一个因素，这使得它非常不切实际。在添加了上面的新方程之后，我们得到了新的方程组。

，

x≥0，xn+1≥0，新的目标函数由

上述线性程序的对偶是

根据yaj+ym+1≥cj j j=1，…，n ym+1≥0，将yb+ym+1m最小化。

如果一些j的cj>0，观察y给出的线性形式

（yei=max1≤j≤n cj>0≤

0如果1米

是一个可行的解决方案，新的双方案。实际上，我们可以选择m是一个接近所用计算机上可表示的最大整数的数字。

下面是T.Molla的数学588课堂笔记中给出的原始对偶算法的一个例子。

例46.3。考虑以下标准形式的线性程序：最大化−x1−3x2−3x3−x4

以且x1、x2、x3、x4≥0为准。

	X1	X2	X4	蔡1	蔡2	蔡3
1/2	零	1	零	5/2	3/2	零
x4=1/2 x1=1/2	零一	三 1/3	一零	1/2 1/6		零零
ξ3=1/2	零	一	零	3/2	1/2	一

	X1	X3	X4	蔡1	蔡2	蔡3
1/2	零	3/2	零	5/2	3/2	零
x4=1/2 x1=1/2	零一		一零	1/2 1/6		零零
ξ3=1/2	零		零	3/2	1/2	一

	X1	X3	X4	蔡1	蔡2	蔡3
零	零	零	零	1	1	1
x4=2 x1=1/3 x3=1/3	零一零	零零一	一零零	4 2/3 一	2 1/3 1/3	三 -21//33