对偶基础

对偶问题基本形式：

原问题	对偶问题
$min z=cx \\ s.t. \ Ax\geq b \\ \phantom{100} \ x\geq 0$	$max w=yb \\ s.t.\ yA\leq c \\ \phantom{100} \ y\geq 0$

部分非基础型转换：

（1）

$max z=cx \\ s.t. \ Ax\geq b \\ \phantom{100} \ x\geq 0$ $\Rightarrow$ $max z=cx \\ s.t. \ -Ax\leq -b \\ \phantom{100} \ x\geq 0$ $\Rightarrow$ $min w=-yb \\ s.t. \ -yA\geq c \\ \phantom{100} \ y\geq 0$ $\Rightarrow^{y^{'}=-y}$ $min w = y^{'}b \\ s.t.\ y^{'}A\geq c \\ \phantom{100} \ y^{'}\leq 0$

（2）

$min z=cx \\ s.t. \ Ax\leq b \\ \phantom{100} \ x\geq 0$ $\Rightarrow$ $min z=cx \\ s.t. \ -Ax\leq -b \\ \phantom{100} \ x\geq 0$ $\Rightarrow$ $max w = -yb \\ s.t.\ -yA\leq c \\ \phantom{100} \ y\geq 0$ $\Rightarrow^{y^{'}=-y}$ $max w = y^{'}b \\ s.t.\ y^{'}A\leq c \\ \phantom{100} \ y^{'}\leq 0$

对偶关系对照表：

原问题（或对偶问题）	对偶问题（或原问题）
目标函数：max Z	目标函数：min w
约束条件： m个	对偶变量： m个
约束条件： ≤	对偶变量： $y_i \geq 0$
约束条件： ≥	对偶变量： $y_i \leq 0$
约束条件： =	对偶变量： $y_i$ 为自由变量
右端常数与目标系数互换	右端常数与目标系数互换
极大化 + ≤	极小化 + ≥ + 变量非负
极小化 + ≥	极大化 + ≤ + 变量非负
极大化 + ≥	极小化 + ≥ + 变量非正
极小化 + ≤	极大化 + ≤ + 变量非正

检验数

定义：目标函数用非基变量表达时的变量系数（非基变量为0，可以直接得到目标值）

$\begin{aligned} Ax&=b\\ BX_B+NX_N&=b\\ x_B+B^{-1}NX_N&=B^{-1}b\\ X_B=B^{-1}b-&B^{-1}NX_N(=0)\\ X_B&=B^{-1}b \end{} \Rightarrow \begin{align*} \begin{split} &Z=C_BX_B+C_NX_N\\ &=C_B(B^{-1}b-B^{-1}Nx_N)X_B+C_NX_N\\ &=C_BB^{-1}b+(C_N-C_BB^{-1}N)X_N \end{split} \end{align*}$

原问题：

$\begin{align*} max\ Z =C_BX_B+C_NX_N&+0X_S\\ BX_B+NX_N+EX_S&=b\\ X_B,X_N,X_S&\geq0 \end{align*}$

	$X_B$	$X_N$	$X_S$	b
$X_B$	B	N	E	b
C	$C_B$	$C_N$	0	0

	$X_B$	$X_N$	$X_S$	b
$X_B$	B	N	E	b
$\lambda$	0	$C_N-C_BB^{-1}N$	$-C_BB^{-1}$	$-C_BB^{-1}b$

$C_BB^{-1}$ 是单纯形乘子

若此时已经达到最优：

$\begin{aligned} \left\{\begin{matrix} C_N-C_BB^{-1}N&\leq0(C-C_BB^{-1}A\leq0) \\ -C_BB^{-1}\leq0 \end{}\right. \end{} \\ \Rightarrow^{C_BB^{-1} = Y} \begin{aligned} \left\{\begin{matrix} C-YA\leq0 \\ Y\geq0 \end{}\right. \end{} \Rightarrow \left\{\begin{matrix} YA\geq C\\ Y\geq0 \end{matrix}\right.$

即，此时目标函数中非基变量和松弛变量的系数均为负数，无改进空间

由于 $Y\geq0$ ，求最大值无界，只能求得最小值，

$Yb=C_BB^{-1}b=C_BX_B+C_NX_N=C_BX_B=C_BB^{-1}b$

从而，最小化问题的最小值 = 最大化问题的最大值

对偶性质：

原问题（LP）：对偶问题（DP）：

$max\ Z=CX \\ s.t. \ AX\geq b \\ \phantom{100} \ X\geq 0$ $min\ w=Yb \\ s.t. \ YA\geq C(A^TY^T\geq C^T) \\ \phantom{100} \ X\geq 0$

性质一：对称性

对偶问题的对偶是原问题

性质二：弱对偶性

设 $X^{\circ},Y^{\circ}$ 分别为LP(max)与 DP(min)的可行解，则 $CX^{\circ}\leq Y^{\circ}b$

证明：

$\left\{\begin{matrix} AX^{\circ}\leq b \Rightarrow^{\times Y^{\circ}} Y^{\circ}AX^{\circ}\leq Y^{\circ}b \\ Y^{\circ}A\geq C \Rightarrow ^{\times X^{\circ}} Y^{\circ}AX^{\circ}\geq C X^{\circ} \end{}\right. \Rightarrow C X^{\circ}\leq Y^{\circ}AX^{\circ}\leq Y^{\circ}b$

（1）最大化问题 → 最小化问题下界

最小化问题 → 最大化问题上界

（2）一个问题 可行，且无界 $\Rightarrow$ 对偶问题 无可行解 （如，最大化问题无上界，且最小化问题大于最大化问题最优解，因此最小化问题无解）

一个问题 无可行解 $\Rightarrow$ 对偶问题为 无界解 或无解

（3）原问题可行且对偶问题不可行 $\Rightarrow$ 原问题是无界解

性质三：最优准则定理

设 $X^{\circ},Y^{\circ}$ 分别为LP(max)与 DP(min)的可行解，则当 $X^{\circ},Y^{\circ}$ 分别是LP,DP最优解时，当且仅当 $CX^{\circ}=Y^{\circ}b$

证明：

设B为最优基， $X^{\circ},Y^{\circ}$ 为最优解，则有：

$Y^{\circ} = C_BB^{-1}$ 且 $CX^{\circ} = C_BB^{-1}b= Y^{\circ} b$

反之，当 $CX^{\circ} = Y^{\circ} b$ 时，有性质2得，任意 $\bar X,\bar Y$ 满足 $C\bar X\leq \bar Yb$

因此， $C\bar X\leq CX^{\circ} = Y^{\circ} b\leq \bar Yb$ , 即 $CX^{\circ}$ 为LP上界， $Y^{\circ} b$ 为DP下界

注：最优单纯形表中， $C_BB^{-1}$ 正好是松弛变量检测数的“相反数”，

正好是对偶问题的“最优解”

性质四：互为对偶的两个问题，其中一个有最优解，另一个也有最优解，且最优值相同

证明：

设LP问题有最优解 $X^{\circ}$ ，则对于最优基B，必有：

检测数 $C-C_BB^{-1}A\leq0$ ，以及松弛变量检测数 $C_BB^{-1}\leq0$ ，

即当 $Y^{\circ}=C_BB^{-1}$ 时，有： $\left\{\begin{matrix} Y^{\circ}A\geq C\\ Y^{\circ}\geq0 \end{matrix}\right.$ ， $Y^{\circ}$ 为对偶问题可行解

由于 $CX^{\circ}=C_BX_B=C_BB^{-1}b=Y^{\circ}b$ ，由性质3可知是最优解

推论：若LP与DP都有可行解，则两者都有最优解

若一个问题无最优解，则另一个问题也无最优解（无解/无界解）

性质五：互补松弛定理

设 $X^{\circ},Y^{\circ}$ 分别为LP与 DP的可行解， $X_S,Y_S$ 是松弛变量可行解，则 $X^{\circ},Y^{\circ}$ 是最优解当且仅当

$\left\{\begin{matrix} Y_SX^{\circ}=0 \\ Y^{\circ}X_S=0 \end{matrix}\right.$

证明：

因为， $X^{\circ},Y^{\circ}$ 为最优解，由性质3的， $CX^{\circ}=Y^{\circ}b$

正向：由于 $X_S,Y_S$ 为松弛变量

$\left\{\begin{matrix} AX^{\circ}+X_S=b \\ Y^{\circ}A-Y_S=C \end{matrix}\right.$ 上下分别同时乘以 $Y^{\circ},X^{\circ}$

$\left\{\begin{matrix} Y^{\circ}AX^{\circ}+Y^{\circ}X_S=Y^{\circ}b \\ Y^{\circ}AX^{\circ}-Y_SX^{\circ}=CX^{\circ} \end{matrix}\right. \Rightarrow Y^{\circ}X_S=-Y_SX^{\circ}$

又因为， $Y^{\circ},X_S,Y_S,X^{\circ}\geq0$ ，因此 ${\color{Red} Y_SX^{\circ}=0 , Y^{\circ}X_S=0}$

反之：

$\because Y^{\circ}X_S=0,Y_SX^{\circ}=0 \\$

$\therefore \left\{\begin{matrix} Y^{\circ}AX^{\circ}=Y^{\circ}b\\ Y^{\circ}AX^{\circ}=CX^{\circ} \end{matrix}\right.$ （仅当最优解时相等)

由性质三可得， $X^{\circ},Y^{\circ}$ 为LP,DP的最优解

例：已知原问题最优解 $X=(6,2,0)^T$ ，球对偶问题最优解

原问题：对偶问题：

$max\ z=3x_1+4x_2+x_3\\ \left\{\begin{matrix} x_1+2x_2+x_3\leq10\\ 2x_1+2_2+x_3\leq16\\ x_1,x_2,x_3\geq0 \end{matrix}\right.$ $min\ w=10y_1+16y_2\\ \Rightarrow\left\{\begin{matrix} y_1+2y_2\geq3\\ 2y_1+2y_2\geq4\\ y_1+y_2\geq1\\ y_1,y_2\geq0 \end{matrix}\right.$

由最优解，可得对偶问题前两个松弛变量为0

$x_1\; x_2\; x_3\; x_{s1}\; x_{s2}$

6 2 0 0 0

0 0 1 1

$y_{s1}\; y_{s2}\; y_{s3}\;y_1\; y_2$

再通过求解对偶问题前两个方程，即

$\left\{\begin{matrix} y_1+2y_2-y_{s1}=3\\ 2y_1+2y_2-y_{s2}=4 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} y_1+2y_2=3\\ 2y_1+2y_2=4 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} y_1=1\\ y_2=1 \end{matrix}\right.$ (对偶最优解)