你怎么不牵我!

# 线性规划问题 (Linear Programming, LP )

线性规划问题的规范形式

{mincTxs.t.Axbx0\begin{cases} min & \textbf{c}^T\textbf{x}\\ s.t. & \textbf{Ax}\geq\textbf{b}\\ & \textbf{x}\geq\textbf{0} \end{cases}

线性规划问题的标准形式

{mincTxs.t.Ax=bx0\begin{cases} min & \textbf{c}^T\textbf{x}\\ s.t. & \textbf{Ax}=\textbf{b}\\ & \textbf{x}\geq\textbf{0} \end{cases}

上述两种形式可以相互转化。譬如x1+x23x_1+x_2\geq 3 可以通过引入一个新的非负变量x30x_3\geq 0 使得变为x1+x2x3=3x_1+x_2-x_3= 3

我们考虑标准形式的 LP,假设rank(A)=mrank(A)=mAAm×nm\times n 的),故AA 中有mm 个线性无关的列向量,它们构成了满秩方阵Bm×mB_{m\times m}。再把AA 中其余各列
组成的子阵记为NN,即A=(B,N)A=(B,N),再把x=(x1,x2,...,xn)T\textbf{x}=(x_1,x_2,...,x_n)^T 分为两部分:记为xB\textbf{x}_BxN\textbf{x}_N,则有:

BxB+NxN=bB\textbf{x}_B+N\textbf{x}_N=\textbf{b}

可以解得

xB=B1bB1NxN\textbf{x}_B=B^{-1}\textbf{b}-B^{-1}N\textbf{x}_N

那么我们可以把xN\textbf{x}_N 当作是自由变量,可以取任意值xˉN\bar{\textbf{x}}_N,然后代入得到xˉB\bar{\textbf{x}}_B 后就得到了原方程的一组解。

定义:设BB 是秩为mm 的约束矩阵ARm×nA\in R^{m\times n} 中的一个mm 阶满秩方阵,则称BB 为一个基(或基阵)BBmm 个线性无关的列向量称为基向量,变量x\textbf{x} 中与之对应的mm 个分量称为基变量,其余分量称为非基变量。令所有非基变量为 0,得到的解x=(xBxN)=(B1b0)\textbf{x}=\begin{pmatrix}\textbf{x}_B\\ \textbf{x}_N\end{pmatrix}=\begin{pmatrix}B^{-1}\textbf{b}\\0\end{pmatrix} 称为相对BB基本解,当B1b0B^{-1}\textbf{b}\geq 0 时,称基本解x\textbf{x}基本可行解,这时对应的基BB 称为可行基

定理:可行解x\textbf{x} 是基本可行解,当且仅当它的正的分量对应的AA 中的列向量线性无关。

证明:若x\textbf{x} 是基本可行解,那么它只有非负分量而且对应的向量为基向量,故线性无关。

反之,由于x\textbf{x} 是可行解,故有x0\textbf{x}\geq 0Ax=bA\textbf{x}=\textbf{b}。不失一般性假设x\textbf{x} 的前kk 个分量为正:

x=(xˉ1,xˉ2,...,xˉk,0,...,0)Txiˉ>0,i=1,...,k\textbf{x}=(\bar{x}_1,\bar{x}_2,...,\bar{x}_k,0,...,0)^T\\ \bar{x_i}>0,i=1,...,k

那么显然有kmk\leq m,可以讨论:

  • k=mk=m,则自然x\textbf{x} 就是对应于B=(a1,a2,...,ak)B=(a_1,a_2,...,a_k) 的一个基本可行解,其中aia_i 就是分量xˉi\bar{x}_i 对应的AA 中的列向量。
  • k<mk<m,此时需要人为再添加几个列向量。因为rank(A)=mrank(A)=m,那么AA 中至少有mm 个线性无关的列向量,故可以从AA 中选取mkm-k 个线性无关的列向量,与之前的kk 个列向量组成了BB。此时,xB=(xˉ1,...,xˉk,0,...,0)T\textbf{x}_B=(\bar{x}_1,...,\bar{x}_k,0,...,0)^T 是基本可行解。

对于一个基本可行解xˉ\bar{\textbf{x}},如果它的所有基分量都取正值,那么称它为非退化的,否则如果有的基分量是 0,就称它为退化的
一个可行基对应一个基本可行解,反之若一个基本可行解是非退化的,那么也唯一对应着一个可行基。

一般地说,如果一个基本可行解是退化的,那么它可由不止一个可行基得到。一个标准形式的 LP 问题最多有(nm)\begin{pmatrix}n\\m\end{pmatrix} 个可行基,从而基本可行解的个数不会超过(nm)\begin{pmatrix}n\\m\end{pmatrix} 个,解集空间的凸多面体顶点数也不超过(nm)\begin{pmatrix}n\\m\end{pmatrix} 个。一个 LP 问题,如果它的所有基本可行解都是非退化的,就说该问题是非退化的,否则称之为退化的。

定理:一个标准形式的 LP 问题若有可行解,则至少有一个基本可行解。

证:设x0=(x10,...,xn0)T\textbf{x}^0=(x_1^0,...,x_n^0)^T 是一个可行解,则有Ax0=b,x00A\textbf{x}_0=\textbf{b},\textbf{x}^0\geq 0。不失一般性,设x0\textbf{x}^0 的正分量为前kk 个。如果它们对应的AA 中的列向量A1,...,AkA_1,...,A_k 已经线性无关了,则根据前述定理,x0\textbf{x}^0 已经是一个基本可行解了。

否则,若不线性无关,那么存在不全为零的数δj,j=1,...,k\delta_j,j=1,...,k 使得:

j=1kδjAj=0\sum_{j=1}^k\delta_jA_j=\textbf{0}

δj=0,j=k+1,...,n\delta_j=0,j=k+1,...,n 得到向量δ=(δ1,...,δk,0,...,0)T\delta=(\delta_1,...,\delta_k,0,...,0)^T, 故有:

Aδ=0A\delta=\textbf{0}

由于xj0>0,j=1,...,kx_j^0>0,j=1,...,k,故可以选择一个足够小的正数ε\varepsilon 使得:

x0±εδ0\textbf{x}^0\pm\varepsilon\delta\geq 0

故有

A(x0±εδ)=Ax0+εAδ=bA(\textbf{x}^0\pm\varepsilon\delta)=A\textbf{x}^0+\varepsilon A\delta=\textbf{b}

而我们可以通过选择ε\varepsilon,使得x0+εδ\textbf{x}^0+\varepsilon\deltax0εδ\textbf{x}^0-\varepsilon\delta 中,有一个可以比x0\textbf{x}^0 的非零分量少一个。故一旦正分量对应的AA 中列向量不线性无关,我们就可以重复这个过程,直到非零分量剩下一个时就肯定是线性无关的了(或在某一次操作后就线性无关了)。证毕。

定理:一个标准形式的 LP 问题若有有限的最优值,则一定存在一个基本可行解是最优解。

证:设x0\textbf{x}^0 是一个最优解,则可以根据上个证明中的过程构造出两个可行解,并且它们的目标函数值为:

cT(x0εδ)=cTx0εcTδcT(x0+εδ)=cTx0+εcTδ\textbf{c}^T(\textbf{x}^0-\varepsilon\delta)=\textbf{c}^T\textbf{x}^0-\varepsilon\textbf{c}^T\delta\\ \textbf{c}^T(\textbf{x}^0+\varepsilon\delta)=\textbf{c}^T\textbf{x}^0+\varepsilon\textbf{c}^T\delta

因为cTx0\textbf{c}^T\textbf{x}^0 是最优解,故有:

cT(x0±εδ)cTx0\textbf{c}^T(\textbf{x}^0\pm\varepsilon\delta)\geq\textbf{c}^T\textbf{x}^0\\

εcTδ=0\varepsilon\textbf{c}^T\delta=0,故得到的两个新的可行解x0±εδ\textbf{x}^0\pm\varepsilon\delta 的目标函数值也是最优的。同理可以取ε\varepsilon 使得其中非零分量减少一个,重复操作直到其成为一个基本可行解。证毕。

# LP 问题的单纯形法

既然在上一部分已经证明了最优解都可以转化为基本可行解,故我们只需要讨论基本可行解就足够了,不会漏掉最优情况。
这里有两个问题需要解决:一是如何找到一个基本可行解,二是如何判断基本可行解是否最优了,以及如何迭代转化基本可行解。前一个问题留在下一章解决。

假设已经找到了一个非退化的基本可行解xˉ\bar{\textbf{x}},即找到了一个基BB,此时可以将方程组Ax=bA\textbf{x}=\textbf{b} 转化为与之等价的方程组:

xB+B1NxN=B1b\textbf{x}_B+B^{-1}N\textbf{x}_N=B^{-1}\textbf{b}

不失一般性假定B=(A1,...,Am)B=(A_1,...,A_m),记向量:

Ajˉ=B1Ajbˉ=B1b\bar{A_j}=B^{-1}A_j\\ \bar{\textbf{b}}=B^{-1}\textbf{b}

则可以把方程组转化为:

xB+B1NxN=bˉ\textbf{x}_B+B^{-1}N\textbf{x}_N=\bar{\textbf{b}}

这个方程组被称为对应于基BB典则方程组,简称典式
相应的,可以改写目标函数值为:

cTx=cBTxB+cNTxN=cBT(bˉB1NxN)+cNTxN=cBTbˉj=m+1n(cBTAˉjcj)xj\begin{aligned} \textbf{c}^T\textbf{x} &=\textbf{c}_B^T\textbf{x}_B+\textbf{c}_N^T\textbf{x}_N\\ &=\textbf{c}_B^T(\bar{\textbf{b}}-B^{-1}N\textbf{x}_N)+\textbf{c}_N^T\textbf{x}_N\\ &=\textbf{c}_B^T\bar{\textbf{b}}-\sum_{j=m+1}^n(\textbf{c}_B^T\bar{A}_j-c_j)x_j \end{aligned}

其中不失一般性地假设了x\textbf{x} 的前mm 个分量对应xB\textbf{x}_B,后nmn-m 个分量对应了xN\textbf{x}_N。可以注意到:

(Aˉ1,...,Aˉm)=B1(A1,...,Am)=B1B=I(\bar{A}_1,...,\bar{A}_m)=B^{-1}(A_1,...,A_m)=B^{-1}B=I

Aˉi\bar{A}_i 其实就是一个只有第ii 个分量为 1,其他分量都为 0 的列向量。故有:

cBTAˉjcj=0,j=1,...,m\textbf{c}_B^T\bar{A}_j-c_j=0,j=1,...,m

引入记号:

ζj=cBTAˉjcj,j=1,...,n\zeta_j=\textbf{c}_B^T\bar{A}_j-c_j,j=1,...,n

向量表示为:

ζT=cBTB1AcT=(ζB,ζN)T=(0,ζN)T\zeta^T=\textbf{c}_B^TB^{-1}A-\textbf{c}^T=(\zeta_B,\zeta_N)^T\\ =(0,\zeta_N)^T

从而目标函数值为:

cTx=cBTbˉζTx\textbf{c}^T\textbf{x}=\textbf{c}_B^T\bar{\textbf{b}}-\zeta^T\textbf{x}

定理 (最优性准则):如果ζ0\zeta\leq 0,则xˉ=(bˉ0)\bar{\textbf{x}}=\begin{pmatrix}\bar{\textbf{b}}\\0\end{pmatrix} 是原问题的最优解。

证:对于任意一个可行解x\textbf{x},一定有x0\textbf{x}\geq 0,那么就有:

cTxˉ=cBTbˉcBTbˉζTx=cTx\textbf{c}^T\bar{\textbf{x}}=\textbf{c}_B^T\bar{\textbf{b}}\leq\textbf{c}_B^T\bar{\textbf{b}}-\zeta^T\textbf{x}=\textbf{c}^T\textbf{x}

定理:如果向量ζ\zeta 的第kk 个分量ζk>0\zeta_k>0(显然m+1knm+1\leq k\leq n),且向量Aˉk=B1Ak0\bar{A}_k=B^{-1}A_k\leq 0,则原问题无界。

证:令d=(Aˉk0)+ek\textbf{d}=\begin{pmatrix}-\bar{A}_k\\0\end{pmatrix}+e_k,其中eke_k 是第kk 个分量为 1,其余分量为 0 的列向量。
因为Aˉk0\bar{A}_k\leq 0,所以有d0\textbf{d}\geq 0。而:

Ad=(B,N)(Aˉk0)+Aek=Ak+Ak=0\begin{aligned} A\textbf{d} &=(B,N)\begin{pmatrix}-\bar{A}_k\\0\end{pmatrix}+Ae_k\\ &=-A_k+A_k\\ &=\textbf{0} \end{aligned}

对于充分大的数θ\theta,观察xˉ+θd\bar{\textbf{x}}+\theta\textbf{d},此时有:

A(xˉ+θd)=Axˉ+θAd=bxˉ+θd0A(\bar{\textbf{x}}+\theta\textbf{d})=A\bar{\textbf{x}}+\theta A\textbf{d}=\textbf{b}\\ \bar{\textbf{x}}+\theta\textbf{d}\geq 0

所以xˉ+θd\bar{\textbf{x}}+\theta\textbf{d} 是原问题的可行解,那么目标函数值为:

cT(xˉ+θd)=cTxˉ+θ(cBT,cNT)(Aˉk0)+θcTek=cTxˉθ(cBTAˉkck)=cTxˉθζk\begin{aligned} \textbf{c}^T(\bar{\textbf{x}}+\theta\textbf{d})&=\textbf{c}^T\bar{\textbf{x}}+\theta(\textbf{c}_B^T,\textbf{c}_N^T)\begin{pmatrix} -\bar{A}_k\\ 0 \end{pmatrix}+\theta\textbf{c}^Te_k\\ &=\textbf{c}^T\bar{\textbf{x}}-\theta(\textbf{c}_B^T\bar{A}_k-c_k)\\ &=\textbf{c}^T\bar{\textbf{x}}-\theta\zeta_k \end{aligned}

又因为ζk>0\zeta_k>0,故可以无限大地选择θ\theta,使得目标函数无限小,故无界,证毕。

定理:对于非退化的基本可行解xˉ\bar{\textbf{x}},若有ζ\zeta 中有任一分量ζk>0\zeta_k>0,且其对应的列向量Aˉk\bar{A}_k 至少有一个正分量,则能找到一个新的基本可行解x^\hat{\textbf{x}},使得cTx^<cTxˉ\textbf{c}^T\hat{\textbf{x}}<\textbf{c}^T\bar{\textbf{x}}

证:只需要找出x^\hat{\textbf{x}} 是什么。
类似前述证明,令

d=(Aˉk0)+ek\textbf{d}=\begin{pmatrix}-\bar{A}_k\\0\end{pmatrix}+e_k

则有Ad=0A\textbf{d}=\textbf{0}。令:

x^=xˉ+θd=(bˉθAˉk0)+θek\hat{\textbf{x}}=\bar{\textbf{x}}+\theta\textbf{d}=\begin{pmatrix}\bar{\textbf{b}}-\theta\bar{A}_k\\0\end{pmatrix}+\theta e_k

我们选取合适的θ\theta。首先为了x^0\hat{\textbf{x}}\geq 0, 可以选

θ=min{bˉiaˉikaˉik>0,i=1,...,m}=bˉraˉrk\theta=min\{\frac{\bar{b}_i}{\bar{a}_{ik}}|\bar{a}_{ik}>0,i=1,...,m\}\\ =\frac{\bar{b}_r}{\bar{a}_{rk}}

从而类似前述证明,x^\hat{\textbf{x}} 是一个可行解。
先考虑x^\hat{\textbf{x}} 的各个分量:

x^i=bˉibˉraˉrkaˉik,i=1,...,m,irx^r=0x^k=θ=bˉraˉrkx^j=0,j=1,...,n,jk\begin{aligned} & \hat{x}_i=\bar{b}_i-\frac{\bar{b}_r}{\bar{a}_{rk}}\bar{a}_{ik},i=1,...,m,i\neq r\\ & \hat{x}_r=0\\ & \hat{x}_k=\theta=\frac{\bar{b}_r}{\bar{a}_{rk}}\\ & \hat{x}_j=0,j=1,...,n,j\neq k \end{aligned}

为证明其是一个基本解,则需要证明

A1,...,Ar1,Ak,Ar+1,...,AmA_1,...,A_{r-1},A_k,A_{r+1},...,A_m

是线性无关的。(即把第rr 个分量换出去,把第kk 个换进来)。
反设不是线性无关的,由于先前的A1,...,Ar,...,AmA_1,...,A_r,...,A_m 是线性无关的,那么就会有:

Ak=i=1,irmyiAiA_k=\sum_{i=1,i\neq r}^my_iA_i

同时有:

Ak=BAˉk=i=1maˉikAiA_k=B\bar{A}_k=\sum_{i=1}^m\bar{a}_{ik}A_i

将上述两式相减可得:

aˉrkAr+i=1,irm(aˉikyi)Ai=0\bar{a}_{rk}A_r+\sum_{i=1,i\neq r}^m(\bar{a}_{ik}-y_i)A_i=0

已知有aˉrk>0\bar{a}_{rk}> 0,故与 “A1,...,Ar,...,AmA_1,...,A_r,...,A_m 线性独立” 矛盾了。
最后,由非退化假设bˉ>0\bar{b}>0,因而θ>0\theta>0,故:

cTx^=cTxˉθζk<cTxˉ\textbf{c}^T\hat{\textbf{x}}=\textbf{c}^T\bar{\textbf{x}}-\theta\zeta_k<\textbf{c}^T\bar{\textbf{x}}

证毕。

由以上定理我们知道相应于基本可行解xˉ\bar{\textbf{x}} 的向量ζT=cBTB1AcT\zeta^T=\textbf{c}_B^TB^{-1}A-\textbf{c}^T 有重要的作用,我们称他为基本可行解xˉ\bar{\textbf{x}}检验数向量,它的各个分量称为检验数

上述定理给了一个从一个基本可行解xˉ\bar{\textbf{x}} 变成一个更好的的基本可行解x^\hat{\textbf{x}} 的办法,即用xkx_k 代替原来的基变量xrx_r 成为新的基。

定理:对于任何一个非退化的线性规划问题,从任何基本解开始,经过有限次换基迭代,或得到一个最优的基本可行解,或作出该问题无界的判定。

当线性规划原问题是退化问题时,由线性规划问题的几何解释可知,通过该可行域某个极点的超平面超过 n 个,所以该点为一个退化的极点。根据摄动法原理,可在退化问题约束方程的右边项做微小的扰动,使得超平面有一个微小的位移,原来相交于一点的若干个超平面略微错开一些,退化极点变成不退化极点。决策者可根据问题的实际情况,适当增加或减少某些资源的数量,使得其迭代变为非退化的,以得到问题的最优解。

单纯形法步骤:

  1. 找一个初始的可行基BB
  2. 求出对应的典式及检验数向量ζ\zeta
  3. ζk=max{ζjj=1,...,n}\zeta_k=max\{\zeta_j|j=1,...,n\}
  4. ζk0\zeta_k\leq 0,则停止迭代,得到最优解x=(xBxN)=(bˉ0)\textbf{x}=\begin{pmatrix}\textbf{x}_B\\ \textbf{x}_N\end{pmatrix}=\begin{pmatrix}\bar{\textbf{b}}\\0\end{pmatrix}
  5. Aˉk0\bar{A}_k\leq 0 则停止,原问题无界。
  6. bˉraˉrk=min{bˉiaˉik    aˉik>0,i=1,...,m}\frac{\bar{b}_r}{\bar{a}_{rk}}=min\{\frac{\bar{b}_i}{\bar{a}_{ik}}\;|\;\bar{a}_{ik}>0,i=1,...,m\}
  7. AkA_k 代替ABrA_{B_r},得到新的基转第二步。

# LP 问题的初始解

不失一般性,可以在方程左右乘以 (-1) 使得b0\textbf{b}\geq 0,设原问题为:

{min  z=cTxs.t.Ax=b(b0)x0\begin{cases} min\; &z=\textbf{c}^T\textbf{x}\\ s.t. & A\textbf{x}=\textbf{b}\quad(\textbf{b}\geq 0)\\ & \textbf{x} \geq 0 \end{cases}

我们要找一个初始的基本可行解,一个很自然的想法就是为啥不直接对(A,b)(A,\textbf{b}) 行变换,然后行变换出来一个单位矩阵后,就得到了一个基本可行解。但实际上无法确认究竟行变换后b\textbf{b} 是否能保证不为负数。譬如我不能先入为主就认为x1,x2,x30,x4,x5=0x_1,x_2,x_3\neq 0,x_4,x_5=0 是一组可行解,很可能做完行变换后b\textbf{b} 就不是非负的了。

为了解决 "得到一个初始的基本可行解" 这个问题,我们引入mm 个人工变量:

xα=(xn+1,...,xn+m)T\textbf{x}_\alpha=(x_{n+1},...,x_{n+m})^T

并研究以下 LP 问题:

{min  g=i=n+1n+mxis.t.Ax+xα=bx0,xα0\begin{cases} min\; & g=\sum_{i=n+1}^{n+m}x_i\\ s.t. & A\textbf{x}+\textbf{x}_\alpha=\textbf{b}\\ & \textbf{x}\geq 0,\quad\textbf{x}_\alpha\geq 0 \end{cases}

不难发现,原问题有可行解当且仅当上述 LP 问题有最优解g=0g=0。此时即xα=0\textbf{x}_\alpha=0
而上述 LP 问题已经有了一个天然的初始基本可行解,即后mm 个变量。

但是有一种情况就是有最优解g=0g=0,人工添加的xα=0\textbf{x}_\alpha=0,但是某个人工添加的变量xn+ix_{n+i} 取值为 0,但却是基变量。

此时会发现有一行(即xn+ix_{n+i} 对应的那一行)有bˉi=0\bar{b}_i=0,因为那一行的基变量的系数只有xn+ix_{n+i} 是 1,其他基变量的系数都是 0。
而不是基变量的变量取值是 0,又因为最优解下xn+ix_{n+i} 取值也是 0,故那一行结果bˉi=0\bar{b}_i=0
这样的话,我们就可以考虑那一行中,如果x1,...,xnx_1,...,x_n 中有系数不是 0 的,就把他换进基,把xn+ix_{n+i} 换出去。因为bˉi=0\bar{b}_i=0,可以证明这样的换基是不改变目标函数的。
如果全是 0,说明原线性约束亏秩,可以直接把这一行删除掉,是无用约束。

# LP 问题的对偶性

定义:一个规范形式的 LP 问题:

{min  cTxs.t.Axbx0\begin{cases} min\; & \textbf{c}^T\textbf{x}\\ s.t. & A\textbf{x}\geq \textbf{b}\\ & \textbf{x}\geq 0 \end{cases}

它的对偶问题为:

{max  bTys.t.ATycy0\begin{cases} max\; & \textbf{b}^T\textbf{y}\\ s.t. & A^T\textbf{y}\leq \textbf{c}\\ & \textbf{y}\geq 0 \end{cases}

当一个 LP 问题为标准形式:

{min  cTxs.t.Ax=bx0\begin{cases} min\; & \textbf{c}^T\textbf{x}\\ s.t. & A\textbf{x}= \textbf{b}\\ & \textbf{x}\geq 0 \end{cases}

它的对偶问题为:

{max  bTys.t.ATyc\begin{cases} max\; & \textbf{b}^T\textbf{y}\\ s.t. & A^T\textbf{y}\leq \textbf{c}\\ \end{cases}

对偶问题其实有很直观的理解。考虑如下一个例子:

{min  2x1+3x2s.t.x1+x21x22x1,x20\begin{cases} min\;& 2x_1+3x_2\\ s.t. & x_1+x_2\geq 1\\ & x_2\geq 2\\ & x_1,x_2\geq 0 \end{cases}

我们很显然把第一个不等式乘以 2 加上第二个不等式就得到了2x1+3x242x_1+3x_2\geq 4
我们就得到了一个目标函数的一个下界,而这个下界是可能取不到的,譬如这个例子就是。
但是目标函数一定是大于等于这个下界的。
所以对偶问题实际上就是在寻找一个原问题的下界。

理解一下,ATyA^T\textbf{y} 就是把各个不等式加权加起来,而且要求结果是小于等于c\textbf{c} 的就表示加起来后,右边大于等于的东西要严格小于等于目标函数值。然后bTy\textbf{b}^T\textbf{y} 就是加权后右边大于等于的东西,他一定是目标函数的下界。而取 max 实际上就是取下界中最大的一个。

定理:如果一个 LP 问题有最优解,那么它的对偶问题也有最优解,且它们最优解相等。

证:考虑标准形式的 LP 问题和其对偶问题,对于任意的可行解x,y\textbf{x},\textbf{y}

Ax=byTAx=yTbATyc,  x0yTAxcTxyTb=yTAxcTx\begin{aligned} & \because A\textbf{x}= b\\ & \therefore \textbf{y}^TA\textbf{x}=\textbf{y}^T\textbf{b}\\ & \because A^T\textbf{y}\leq \textbf{c},\;\textbf{x}\geq 0\\ & \therefore \textbf{y}^TA\textbf{x}\leq\textbf{c}^T\textbf{x}\\ & \therefore \textbf{y}^T\textbf{b}=\textbf{y}^T A\textbf{x}\leq\textbf{c}^T\textbf{x}\\ \end{aligned}

证明了对偶问题的目标函数总是小于原目标函数的。
现假设原问题有了一个最优解为x^\hat{\textbf{x}},它对应的基为B^\hat{B}(即x^B=B^1b\hat{\textbf{x}}_B=\hat{B}^{-1}\textbf{b}),那么yT=cB^TB^1\textbf{y}^T=\textbf{c}_{\hat{B}}^T\hat{B}^{-1} 就是其对偶问题的一个可行解:

ATyc=AT(cB^TB^1)Tc=ζ0A^T\textbf{y}-\textbf{c}=A^T(\textbf{c}_{\hat{B}}^T\hat{B}^{-1})^T-\textbf{c}=\zeta\leq 0\\

此时它们的目标函数值相同:

yTb=cB^TB^1b=cB^Tx^B\textbf{y}^T\textbf{b}= \textbf{c}_{\hat{B}}^T\hat{B}^{-1}\textbf{b}=\textbf{c}_{\hat{B}}^T\hat{\textbf{x}}_B

故此时对偶问题一定是取到了可能的最上界,即为最优值。证毕。

定理:若x,w\textbf{x},\textbf{w} 分别是原问题及其对偶问题的可行解,那么它们分别是原问题、对偶问题的最优解的充要条件为cTx=wTb\textbf{c}^T\textbf{x}=\textbf{w}^T\textbf{b}

其实原始的 LP 问题和其对偶问题只有以下几种解的情况:

  1. 两个问题都有最优解,且最优解相等。
  2. 一个问题无界,另一个问题无可行解。
  3. 两个问题都无可行解。

定理:对偶问题的对偶问题就是原问题。

定理 (互补松紧性):设x,w\textbf{x},\textbf{w} 分别是原问题和对偶问题的可行解,那么它们分别是原问题、对偶问题的最优解的充要条件是:

yT(Axb)=0xT(cATy)=0 \textbf{y}^T(A\textbf{x}-\textbf{b})=0\\ \textbf{x}^T(\textbf{c}-A^T\textbf{y})=0

证:考虑规范形式,就会有:

x,y,(Axb),(cATy)0yT(Axb)0,xT(cATy)0yT(Axb)+xT(cATy)=xTcyTb\begin{aligned} & \because\textbf{x},\textbf{y},(A\textbf{x}-\textbf{b}),(\textbf{c}-A^T\textbf{y})\geq 0\\ & \therefore \textbf{y}^T(A\textbf{x}-\textbf{b})\geq 0,\textbf{x}^T(\textbf{c}-A^T\textbf{y})\geq 0\\ & \because\textbf{y}^T(A\textbf{x}-\textbf{b})+\textbf{x}^T(\textbf{c}-A^T\textbf{y})=\textbf{x}^T\textbf{c}-\textbf{y}^T\textbf{b} \end{aligned}

所以xTc=yTbyT(Axb)=0,xT(cATy)=0\textbf{x}^T\textbf{c}=\textbf{y}^T\textbf{b}\Leftrightarrow\textbf{y}^T(A\textbf{x}-\textbf{b})=0,\textbf{x}^T(\textbf{c}-A^T\textbf{y})=0,证毕。