[学习笔记] - 线性规划

发表于 分类于 本文字数： 7.6k 阅读时长 ≈ 28 分钟

线性规划（LP）

minc1x1+⋯+cnxns.t.a11x1+⋯+a1nxn≤b1am1x1+⋯+amnxn≤bmx1,⋯ ,xn≥0\begin{aligned} min &\qquad c_1x_1 + \cdots + c_nx_n & \\ s.t. &\qquad a_{11}x_1 + \cdots + a_{1n}x_n \leq b_1 \\ &\qquad a_{m1}x_1 + \cdots + a_{mn}x_n \leq b_{m} \\ &\qquad x_1, \cdots, x_n \geq 0 \end{aligned}

形式化定义

mincTxs.t.Ax≤bx≥0\begin{aligned} min &\qquad \mathbf{c}^T\mathbf{x} & \\ s.t. &\qquad A\mathbf{x} \leq \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}

最优化基本概念参照([学习笔记] - 非线性规划)

标准LP问题

从实际中总结出来的LP形式不完全一样

  • 目标函数是最大值或最小值
  • 约束条件是等式约束或不等式约束
  • 变量有上界或下界或无界

minz=cTxs.t.Ax=bx≥0\begin{aligned} min &\qquad z = \mathbf{c}^T\mathbf{x} & \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}

标准化

  • 目标函数的转换：max⁡z→min⁡(−z)\max z \rightarrow \min (-z)
  • 约束条件的转换（引入松弛变量xn+ix_{n+i}）

∑j=1naijxj≤bi⇒{∑j=1naijxj+xn+i=bixn+i≥0∑j=1naijxj≥bi⇒{−∑j=1naijxj+xn+i=−bi∑j=1naijxj−xn+i=bixn+i≥0\begin{aligned} \sum^n_{j=1}a_{ij}x_{j} \leq b_{i} &\Rightarrow \begin{cases} \sum^n_{j=1}a_{ij}x_j + x_{n+i} = b_i \\ x_{n+i} \geq 0 \end{cases} \\ \sum^n_{j=1}a_{ij}x_{j} \geq b_{i} &\Rightarrow \begin{cases} -\sum^n_{j=1}a_{ij}x_j + x_{n+i} = -b_i \\ \sum^n_{j=1}a_{ij}x_j - x_{n+i} = b_i \\ x_{n+i} \geq 0 \end{cases} \end{aligned}

  • 变量的非负约束

a≤xi≤b⇔{xi′=xi−axi′+xn+i=b−axi′≥0xi自由变量⇔{xi=xi′−xi′′xi′,xi′′≥0xi≤0⇔{xi′=−xixi′≥0\begin{aligned} a \leq x_i \leq b &\Leftrightarrow \begin{cases} x'_i = x_i - a \\ x'_i + x_{n+i} = b - a \\ x'_i \geq 0 \end{cases} \\ x_i\text{自由变量} &\Leftrightarrow \begin{cases} x_i = x'_i - x''_i \\ x'_i, x''_i \geq 0 \end{cases} \\ x_i \leq 0 &\Leftrightarrow \begin{cases} x'_i = -x_i \\ x'_i \geq 0 \end{cases} \end{aligned}

基本性质

  • 可行解：称满足线性规划的约束条件的解x=(x1,x2,⋯ ,xn)T\mathbf{x} = (x_1, x_2, \cdots, x_n)^T，为线性规划问题的可行解
  • 可行域：所有可行解组成的集合称为可行域，记为DD
    • 可行域为凸集
    • D=∅D = \varnothing，无解或不可行
    • D≠∅D \neq \varnothing，但目标函数在DD上无下界，无解
    • D≠∅D \neq \varnothing，且目标函数有限的最优解，有最优解
  • 最优解：满足线性规划目标函数的可行解，且是目标函数达到最小的可行解
  • 基：设A=(aij)mnA=(a_{ij})_{mn}是约束方程组的系数矩阵，其秩为m(m<n)m(m < n)，若BB是矩阵AA中m×mm \times m阶非奇异子阵，则BB是基
  • 基向量：BB的列向量pi\mathbf{p}_i为线性规划问题的基向量
  • 基变量：与基向量pi\mathbf{p}_i对应的决策变量xi\mathbf{x}_i为线性规划问题的基变量
  • 非基变量：基变量以外的决策变量

最优基本可行解

在线性规划中，设矩阵AA的秩为mm，又假设A=[B,N]A = [B, N]，其中BB是mm阶可逆矩阵，如果AA的前mm列是线性相关的，可以通过基本变换，使前mm列成为线性无关，x\mathbf{x}可以记作

x=[xBxN]\mathbf{x} = \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix}

其中xB\mathbf{x}_B为BB中的列对应，xN\mathbf{x}_N为NN的列对应，这样可以改写Ax=bA\mathbf{x} = \mathbf{b}为

[B,N][xBxN]=bBxB+NxN=b\begin{aligned} [B, N]\begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix} &= \mathbf{b} \\ B\mathbf{x}_B + N\mathbf{x}_N &= \mathbf{b} \end{aligned}

两边同乘B−1B^{-1}，移项后可以得到

xB=B−1b−B−1NxN\mathbf{x}_B = B^{-1}\mathbf{b} - B^{-1}N\mathbf{x}_N

令xN=0\mathbf{x}_N = 0，得到解

x=[xBxN]=[B−1b0]\mathbf{x} = \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix} = \begin{bmatrix} B^{-1}\mathbf{b} \\ 0 \end{bmatrix}

  • 基本解：称上述x\mathbf{x}为方程组Ax=bA\mathbf{x} = \mathbf{b}的一个基本解
  • 基矩阵：BB，简称为基
  • 基变量：xB\mathbf{x}_B的各分量
    • 一组基：基变量的全体xB1,xB2,⋯ ,xBm\mathbf{x}_{B_1}, \mathbf{x}_{B_2}, \cdots, \mathbf{x}_{B_m}
  • 非基变量：xN\mathbf{x}_N的各分量

如果B−1b≥0B^{-1}\mathbf{b} \geq 0，则

  • 基本可行解：称x\mathbf{x}为方程组Ax=b,x≥0A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0的基本可行解
    • 一组可行基：基变量的全体xB1,xB2,⋯ ,xBm\mathbf{x}_{B_1}, \mathbf{x}_{B_2}, \cdots, \mathbf{x}_{B_m}
  • 可行基矩阵：称BB为可行基矩阵
  • 非退化的：若B−1b>0B^{-1}\mathbf{b} > 0，即基变量的取值均为正数，则基本可行解是非退化的
  • 退化的基本可行解：满足B−1b≥0B^{-1}\mathbf{b} \geq 0且至少有一个分量是零

基本可行解的存在问题

  • 定理：如果Ax=b,x≥0A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0有可行解，则一定存在基本可行解，其中AA是m×nm \times n矩阵，AA的秩为mm
  • 定理：令K={x∣Ax=b,x≥0},AK = \lbrace \mathbf{x}|A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0 \rbrace, A是m×nm \times n矩阵，AA的秩为mm，则KK的极点集与Ax=b,x≥0A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0的基本可行解集等价
  • 定理：如果线性规划存在有限最优解，则目标函数的最优值可在某个极点上达到

当线性规划问题存在最优解时，一定存在一个基本可行解，且它是最优解，线性规划问题变为求最优基本可行解

单纯形方法

由基本可行解的存在可知道，求解线性规划问题归结于找最优基本可行解，单纯形的方法的基本思想，就是从一个基本可行解出发，求一个使目标函数值有所改善的基本可行解，这样不断的改善基本可行解，力图达到最优基本可行解，考虑问题

minf=defcxs.t.Ax=bx≥0\begin{aligned} min &\qquad f \xlongequal{def} \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq 0 \end{aligned}

  • AA是m×nm \times n矩阵，秩为mm
  • c\mathbf{c}是nn维行向量
  • x\mathbf{x}是nn维列向量
  • b≥0\mathbf{b} \geq 0是mm维列向量
  • 符号=def\xlongequal{def}表示右端的表达式是左端的定义式，也就是目标函数ff的具体形式就是cx\mathbf{c}\mathbf{x}

记

A=(p1p2⋯pn)A = \begin{pmatrix} \mathbf{p}_1 & \mathbf{p}_2 & \cdots & \mathbf{p}_n \end{pmatrix}

现在通过列调换之后，将AA分解为(B,N)\begin{pmatrix}B, N\end{pmatrix}，使得BB是基矩阵，NN是非基矩阵，设

x(0)=[B−1b0]\mathbf{x}^{(0)} = \begin{bmatrix} B^{-1}\mathbf{b} \\ \mathbf{0} \end{bmatrix}

是基本可行解，则在x(0)\mathbf{x}^{(0)}处的目标函数值

f0=cx(0)=(cBcN)[B−1b0]=cBB−1b\begin{aligned} f_0 &= \mathbf{c}\mathbf{x}^{(0)} = \begin{pmatrix} \mathbf{c}_B & \mathbf{c}_N \end{pmatrix} \begin{bmatrix} B^{-1}\mathbf{b} \\ \mathbf{0} \end{bmatrix} \\ &= \mathbf{c}_B B^{-1}\mathbf{b} \end{aligned}

  • cB\mathbf{c}_B是c\mathbf{c}中与基变量对应的分量组成的mm维行向量
  • cN\mathbf{c}_N是c\mathbf{c}中与非基变量对应的分量组成的n−mn - m维行向量

设

x=[xBxN]\mathbf{x} = \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix}

是任意一个可行解，由Ax=bA\mathbf{x} = \mathbf{b}得到

xB=B−1b−B−1NxN\mathbf{x}_B = B^{-1}b - B^{-1}N\mathbf{x}_N

在点x\mathbf{x}处的目标函数值为

f=cx=(cBcN)[xBxN]=cBxB+cNxN=cB(B−1b−B−1NxN)+cNxN=cBB−1b−(cBB−1N−cN)xN=f0−∑i∈R(cBB−1pi−ci)xi=f0−∑i∈R(zi−ci)xi\begin{aligned} f &= \mathbf{c}\mathbf{x} = \begin{pmatrix} \mathbf{c}_B & \mathbf{c}_N \end{pmatrix} \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix} \\ &= \mathbf{c}_B\mathbf{x}_B + \mathbf{c}_N\mathbf{x}_N \\ &= \mathbf{c}_B(B^{-1}\mathbf{b} - B^{-1}N\mathbf{x}_N) + \mathbf{c}_N\mathbf{x}_N \\ &=\mathbf{c}_BB^{-1}\mathbf{b} - (\mathbf{c}_BB^{-1}N - \mathbf{c}_N)\mathbf{x}_N \\ &=f_0 - \sum_{i \in R}(\mathbf{c}_BB^{-1}\mathbf{p}_i - c_i)x_i \\ &= f_0 - \sum_{i \in R}(z_i - c_i)x_i \end{aligned}

  • RR是非基变量下标集

zi=cBB−1piz_i = \mathbf{c}_BB^{-1}\mathbf{p}_i

由上面的式子可以知道，选取适当的自由未知量xi,(i∈R)x_i, (i \in R)就有可能使得

∑i∈R(zi−ci)xi>0\sum_{i \in R}(z_i - c_i)x_i > 0

从而得到使目标函数值减小的新的基本可行解，为此

  • 在原来的n−mn - m个非基变量中，使得n−m−1n - m - 1个变量仍然取00
  • 令一个非基变量xkx_k增大（即取正值），来实现目的

我们需要找到方法来确定下标kk，当xi,(i∈R)x_i, (i \in R)取值相同时，zi−ciz_i - c_i（正数）越大，目标函数值下降越多，因此选择xkx_k，使得

zk−ck=max⁡i∈R(zi−ci)z_k - c_k = \max_{i \in R} (z_i - c_i)

假设zk−ck>0z_k - c_k > 0，xkx_k由零变为正数后，得到方程组Ax=bA\mathbf{x} = \mathbf{b}的解

xB=B−1b−B−1pkxk=b‾−ykxk\begin{aligned} \mathbf{x}_B &= B^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{p}_kx_k \\ &= \overline{\mathbf{b}} - \mathbf{y}_kx_k \end{aligned}

  • b‾,yk\overline{\mathbf{b}}, \mathbf{y}_k是mm维列向量
    • b‾=B−1b\overline{\mathbf{b}} = B^{-1}\mathbf{b}
    • yk=B−1pk\mathbf{y}_k = B^{-1}\mathbf{p}_k

xB=[xB1xB2⋮xBm]=[b‾1b‾2⋮b‾m]−[y1ky2k⋮ymk]xkxN=(0⋯0xk0⋯0)T\begin{gathered} \mathbf{x}_B = \begin{bmatrix} x_{B_1} \\ x_{B_2} \\ \vdots \\ x_{B_m} \end{bmatrix} = \begin{bmatrix} \overline{b}_1 \\ \overline{b}_2 \\ \vdots \\ \overline{b}_m \end{bmatrix} - \begin{bmatrix} y_{1k} \\ y_{2k} \\ \vdots \\ y_{mk} \end{bmatrix}x_k \\ \mathbf{x}_N = \begin{pmatrix} 0 & \cdots & 0 & x_k & 0 & \cdots & 0 \end{pmatrix}^T \end{gathered}

得到新的点，目标函数值为

f=f0−(zk−ck)xkf = f_0 - (z_k - c_k)x_k

那么如何确定xkx_k的取值呢

  • xkx_k取值越大函数值下降越多
  • xkx_k的取值受到可行性的限制，不能无限增大
  • 对于某个ii
    • 当yik≤0y_{ik} \leq 0时，xkx_k取任何正值时，总成立xBi≥0x_{B_i} \geq 0
    • 当yik>0y_{ik} > 0时，为保证

xBi=b‾i−yikxk≥0x_{B_i} = \overline{b}_i - y_{ik}x_k \geq 0

就需要

xk≤b‾iyikx_k \leq \frac{\overline{b}_i}{y_{ik}}

所以，为了使得xB≥0\mathbf{x}_B \geq 0，则使

xk=min⁡(b‾iyik∣yik>0)=b‾ryrkx_k = \min(\frac{\overline{b}_i}{y_{ik}} \Big | y_{ik} > 0) = \frac{\overline{b}_r}{y_{rk}}

原来的基变量xBr=0x_{B_r} = 0，得到新的可行解

x=(xB1⋯xBr−10xBr+10⋯xk0⋯0)T\mathbf{x} = \begin{pmatrix} x_{B_1} & \cdots & x_{B_{r-1}} &0& x_{B_{r+1}} & 0 & \cdots &x_k& 0&\cdots&0 \end{pmatrix}^T

这个解一定是基本可行解，经过上述的转换

  • xkx_k由原来的非基变量变成了基变量
  • xBrx_{B_r}由原来的基变量变成了非基变量
  • 目标函数值减少了(zk−ck)xk(z_k - c_k)x_k

重复以上过程，就可以进一步改善基本可行解，直到所有的(zi−ci)(z_i - c_i)均为非正数，即任意的非基变量取正值都不能使得目标函数值减小为止

在线性规划中，通常称zi−ciz_i - c_i为判别数或检验数

  • 在极小化问题中，对于某个基本可行解，所有zi−ci≤0z_i - c_i \leq 0，则这个基本可行解是最优解
  • 在极大化问题中，对于某个基本可行解，所有zi−ci≥0z_i - c_i \geq 0，则这个基本可行解是最优解

zi−ci=cBB−1pi−ci,i=1,⋯ ,nz_i - c_i = \mathbf{c}_BB^{-1}\mathbf{p}_i - c_i, \quad i = 1,\cdots,n

单纯形方法步骤

首先要确定一个初始基本可行解，设初始基为BB

  • 解BxB=bBx_B = \mathbf{b}，求得xB=B−1b=b‾x_B = B^{-1}\mathbf{b} = \overline{\mathbf{b}}，令xN=0x_N = 0，计算目标函数值f=cBxBf = \mathbf{c}_B\mathbf{x}_B
  • 求单纯形乘子w\mathbf{w}，解wB=cB\mathbf{w}B = \mathbf{c}_B，得到w=cBB−1\mathbf{w} = \mathbf{c}_BB^{-1}，对于所有非基变量，计算判别数zi−ci=wpi−ciz_i - c_i = \mathbf{w}\mathbf{p}_i - c_i，令

zk−ck=max⁡i∈R(zi−ci)z_k - c_k = \max_{i \in R} (z_i - c_i)

若zk−ck≤0z_k - c_k \leq 0，则对于所有非基变量zi−ci≤0z_i - c_i \leq 0对应基变量的判别数总是零，因此停止计算，现行基本可行解即为最优解

  • 解Byk=pkB\mathbf{y}_k = \mathbf{p}_k，得到yk=B−1pk\mathbf{y}_k = B^{-1}\mathbf{p}_k，若yk≤0\mathbf{y}_k \leq 0，即yk\mathbf{y}_k的每个分量均为非正数，则停止计算，问题不存在有限最优解
  • 确定下标rr，使得

b‾ryrk=min⁡(b‾iyik∣yik>0)\frac{\overline{b}_r}{y_{rk}} = \min(\frac{\overline{b}_i}{y_{ik}} \Big | y_{ik} > 0)

  • xBrx_{B_r}为离基变量，xkx_k为进基变量，用pk\mathbf{p}_k替换pBr\mathbf{p}_{B_r}，得到新的基矩阵BB，返回步骤一

单纯形方法收敛性

令

zk−ck=max⁡(zj−cj)z_k - c_k = \max(z_j - c_j)

每次迭代都会是以下三种情况

  • zk−ck≤0z_k - c_k \leq 0，这时现行基本可行解就是最优解
  • zk−ck>0z_k - c_k > 0且yk≤0y_k \leq 0，无界情形
  • zk−ck>0z_k - c_k > 0且yky_k有正分量，可以求出新的可行解，若xk=br‾yrk>0x_k = \frac{\overline{b_r}}{y_{rk}} > 0，则函数值下降

当极小化线性规划问题存在最优解的时候，对于非退化情形，每次迭代中，均有：

xB=B−1b=b‾>0\mathbf{x}_B = B^{-1}\mathbf{b} = \overline{\mathbf{b}} > 0

从而，自然的

xk=b‾ryrk>0x_k = \frac{\overline{b}_r}{y_{rk}} > 0

对于非退化情形，经过迭代，函数值减小，每次迭代得到的基本可行解互不相同，基本解个数有限，所以有限次迭代必能达到最优解

对于非退化问题，单纯形方法经有限次迭代能达到最优基本可行解，或得出无界结论

单纯形方法表格法

  • AA：写作(B,N)(B, N)
  • x\mathbf{x}：写作[xBxN]\begin{bmatrix}\mathbf{x}_B\\\mathbf{x}_N\end{bmatrix}
  • c\mathbf{c}：写作(cB,cN)(\mathbf{c}_B, \mathbf{c}_N)

线性规划可以等价形式

minfs.t.f−cBxB−cNxN=0BxB+NxN=bxB≥0,xN≥0\begin{aligned} min &\qquad f \\ s.t. &\qquad f - \mathbf{c}_B\mathbf{x}_B - \mathbf{c}_N\mathbf{x}_N = 0 \\ &\qquad B\mathbf{x}_B + N\mathbf{x}_N = \mathbf{b} \\ &\qquad \mathbf{x}_B \geq \mathbf{0}, \mathbf{x}_N \geq \mathbf{0} \end{aligned}

对上述条件2两端乘B−1B^{-1}得到，等于对方程组进行行变换，将基变量的系数变为单位矩阵

xB+B−1NxN=B−1b\mathbf{x}_B + B^{-1}N\mathbf{x}_N = B^{-1}\mathbf{b}

利用cB\mathbf{c}_B左乘两端，加到条件1上，可以得到

f+0⋅xB+(cBB−1N−cN)xN=cBB−1bf + 0 \cdot \mathbf{x}_B + (\mathbf{c}_BB^{-1}N - \mathbf{c}_N)\mathbf{x}_N = \mathbf{c}_BB^{-1}\mathbf{b}

线性规划可以等价形式

minfs.t.xB+B−1NxN=B−1bf+0⋅xB+(cBB−1N−cN)xN=cBB−1bxB≥0,xN≥0\begin{aligned} min &\qquad f \\ s.t. &\qquad \mathbf{x}_B + B^{-1}N\mathbf{x}_N = B^{-1}\mathbf{b} \\ &\qquad f + 0 \cdot \mathbf{x}_B + (\mathbf{c}_BB^{-1}N - \mathbf{c}_N)\mathbf{x}_N = \mathbf{c}_BB^{-1}\mathbf{b} \\ &\qquad \mathbf{x}_B \geq \mathbf{0}, \mathbf{x}_N \geq \mathbf{0} \end{aligned}

化为表格

ff xB\mathbf{x}_B xN\mathbf{x}_N 右端
xB\mathbf{x}_B 0 Im\mathbf{I}_m B−1NB^{-1}N B−1bB^{-1}\mathbf{b}
ff 1 0 cBB−1N−cN\mathbf{c}_BB^{-1}N - \mathbf{c}_N cBB−1b\mathbf{c}_BB^{-1}\mathbf{b}

其中

  • B−1NB^{-1}N：B−1(pN1,pN2,⋯ ,pNn−m)=(yN1,yN2,⋯ ,yNn−m)B^{-1}(\mathbf{p}_{N_1},\mathbf{p}_{N_2},\cdots,\mathbf{p}_{N_{n-m}}) = (\mathbf{y}_{N_1},\mathbf{y}_{N_2},\cdots,\mathbf{y}_{N_{n-m}})
  • B−1bB^{-1}\mathbf{b}：(b‾1,b‾2,⋯ ,b‾m)T(\overline{b}_1,\overline{b}_2,\cdots,\overline{b}_m)^T

令xN=0\mathbf{x}_N = 0，则基变量xB=B−1b\mathbf{x}_B = B^{-1}\mathbf{b}

cBB−1N−cN=cBB−1(pN1,pN2,⋯ ,pNn−m)−(cN1,cN2,⋯ ,cNn−m)=(zN1,zN2,⋯ ,zNn−m)−(cN1,cN2,⋯ ,cNn−m)=(zN1−cN1,zN2−cN2,⋯ ,zNn−m−cNn−m)\begin{aligned} \mathbf{c}_BB^{-1}N - \mathbf{c}_N &= \mathbf{c}_BB^{-1}(\mathbf{p}_{N_1},\mathbf{p}_{N_2},\cdots,\mathbf{p}_{N_{n-m}}) - (c_{N_1},c_{N_2},\cdots,c_{N_{n-m}}) \\ &= (z_{N_1},z_{N_2},\cdots,z_{N_{n-m}}) - (c_{N_1},c_{N_2},\cdots,c_{N_{n-m}}) \\ &= (z_{N_1} - c_{N_1},z_{N_2} - c_{N_2},\cdots,z_{N_{n-m}} - c_{N_{n-m}}) \end{aligned}

从而可以得到

xB1x_{B_1} ⋯\cdots xBrx_{B_r} ⋯\cdots xBmx_{B_m} ⋯\cdots xjx_j ⋯\cdots xkx_k
xB1x_{B_1} 1\color{green}1 ⋯\color{green}\cdots 0\color{green}0 ⋯\color{green}\cdots 0\color{green}0 ⋯\cdots y1jy_{1j} ⋯\cdots y1ky_{1k} ⋯\cdots b‾1\overline{b}_1
⋮\vdots ⋮\color{green}\vdots ⋮\color{green}\vdots ⋮\color{green}\vdots ⋮\vdots ⋮\vdots ⋮\vdots
xBrx_{B_r} 0\color{green}0 ⋯\color{green}\cdots 1\color{green}1 ⋯\color{green}\cdots 0\color{green}0 ⋯\cdots yrjy_{rj} ⋯\cdots yrk\color{red}y_{rk} ⋯\cdots b‾r\overline{b}_r
⋮\vdots ⋮\color{green}\vdots ⋮\color{green}\vdots ⋮\color{green}\vdots ⋮\vdots ⋮\vdots ⋮\vdots
xBmx_{B_m} 0\color{green}0 ⋯\color{green}\cdots 0\color{green}0 ⋯\color{green}\cdots 1\color{green}1 ⋯\cdots ymjy_{mj} ⋯\cdots ymky_{mk} ⋯\cdots b‾m\overline{b}_m
ff 00 ⋯\cdots 00 ⋯\cdots 00 ⋯\cdots zj−cjz_j - c_j ⋯\cdots zk−ckz_k - c_k ⋯\cdots cBb‾\mathbf{c}_B\overline{\mathbf{b}}

假设b‾=B−1b≥0\overline{\mathbf{b}} = B^{-1}\mathbf{b} \geq 0，则上表已经有一个基本可行解，即

xB=b‾,xN=0\mathbf{x}_B = \overline{\mathbf{b}}, \quad \mathbf{x}_N = \mathbf{0}

  • 若cBB−1N−cN≤0\mathbf{c}_BB^{-1}N - \mathbf{c}_N \leq 0，则现行基本解为最优解
  • 若cBB−1N−cN>0\mathbf{c}_BB^{-1}N - \mathbf{c}_N > 0，需用主元消去法求改进的基本可行解
    • 如果在表的最后一行中，有zk−ck=max⁡(zj−cj)z_k - c_k = \max(z_j - c_j)，则选择xkx_k，所对应的列为主列
    • 令b‾ryrk=min⁡(b‾iyik∣yik>0)\frac{\overline{b}_r}{y_{rk}} = \min(\frac{\overline{b}_i}{y_{ik}} \Big | y_{ik} > 0)，则第rr行为主行
    • 主列和主行交叉处的元素yrky_{rk}称为主元
    • 用主元yrky_{rk}除第rr行（主行），再把rr行的若干倍分别加到各行，使主列中各元素（除rr行）为00
    • 也就是把主列化为单位向量，xkx_k由非基变量变成基变量，xBrx_{B_r}由基变量变成非基变量
    • 基变量的系数矩阵BB在表中总是单位矩阵，因此右端列b‾\overline{b}就是新的基变量取值
    • 然后进行下一次迭代即可

两阶段法

使用单纯形方法，需要给定一个初始基本可行解，我们需要知道怎么求初始基本可行解，考虑下面的线性规划标准形问题（b≥0\mathbf{b} \geq \mathbf{0}）

mincTxs.t.Ax=bx≥0\begin{aligned} min &\qquad \mathbf{c}^T\mathbf{x} & \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}

  • 若AA中包含mm阶单位矩阵，则初始基本可行解可以立刻得到
    • A=[Im,N]A = [\mathbf{I}_m, N]
    • x=[xBxN]=[b0]x = \begin{bmatrix}\mathbf{x}_B\\\mathbf{x}_N\end{bmatrix} = \begin{bmatrix}\mathbf{b}\\\mathbf{0}\end{bmatrix}
  • 若AA中不包含mm阶单位矩阵，则采用以下方法

设AA中不包含mm阶单位矩阵，为了使约束方程的系数矩阵中含有mm阶单位矩阵，将每一个方程增加一个非负变量，令

Ax+xa=bx≥0,xa≥0\begin{aligned} A\mathbf{x} + x_a = \mathbf{b} \\ x \geq 0, x_a \geq 0 \end{aligned}

即

(A,Im)[xxa]=bx≥0,xa≥0\begin{aligned} \begin{pmatrix} A, \mathbf{I}_m \end{pmatrix} \begin{bmatrix} x \\ x_a \end{bmatrix} = \mathbf{b} \\ x \geq 0, x_a \geq 0 \end{aligned}

显然

[xxa]=[0b]\begin{bmatrix} x \\ x_a \end{bmatrix} = \begin{bmatrix} \mathbf{0} \\ \mathbf{b} \end{bmatrix}

是一个基本可行解，上述的意义在于，从(A,Im)[xxa]=b\begin{pmatrix}A, \mathbf{I}_m\end{pmatrix} \begin{bmatrix}x\\x_a\end{bmatrix} = \mathbf{b}已知的基本可行解出发，能够求出一个使xa=0x_a = \mathbf{0}的基本可行解，那么就可以得到原来线性规划问题的基本可行解

向量xa≥0x_a \geq 0称为人工变量

  • 松弛变量：将不等式约束改为等式约束，改写前后问题等价
  • 人工变量：改变了原来约束条件，改写前后问题不等价

两阶段法·第一阶段

  • 利用单纯形方法消去人工变量
    • 把人工变量都变成非基变量
    • 求出原来的问题的基本可行解

mineTxas.t.Ax+xa=bx,xa≥0\begin{aligned} min &\qquad \mathbf{e}^Tx_a \\ s.t. &\qquad Ax + x_a = \mathbf{b} \\ &\qquad x, x_a \geq 0 \end{aligned}

  • e=(1,1,⋯ ,1)T\mathbf{e} = \begin{pmatrix}1,1,\cdots,1\end{pmatrix}^T，分量全是11的mm维列向量
  • xa=(xn+1,xn+2,⋯ ,xn+m)Tx_a = (x_{n+1}, x_{n+2}, \cdots, x_{n+m})^T，人工变量构成的mm维列向量

x=0,xa=bx = 0, x_a = b是线性规划的一个基本可行解，目标函数在可行域上有下界，则必然存在最优基本可行解
求解线性规划，设得到的最优基本可行解是(x‾T,x‾aT)T(\overline{x}^T, \overline{x}^T_a)^T，此时必有下列三种情形之一

  • x‾aT≠0\overline{x}^T_a \neq 0，此时线性规划无可行解
  • x‾aT=0\overline{x}^T_a = 0且xax_a的分量都是非基变量，此时mm个基变量都是原来的变量，则[xxa]=[x‾0]\begin{bmatrix}x\\x_a\end{bmatrix} = \begin{bmatrix}\overline{x}\\\mathbf{0}\end{bmatrix}是线性规划的基本可行解，则x=x‾x = \overline{x}是原线性规划的一个基本可行解
  • x‾aT=0\overline{x}^T_a = 0且xax_a中有分量是基变量，可用主元消去法
    • 把原变量中非基变量引进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段

两阶段法·第二阶段

  • 将第一阶段的解，代入回去
  • 对于刚刚引入的人工变量的列，可以直接除去
  • 第一阶段的基变量，对应第二阶段的基变量，其等式的值即为第一阶段解的值

单纯形方法退化情景

在非退化的情形下，单纯形方法经过有限次迭代必然达到最优解。但是对于退化情形（B−1b≥0B^{-1}\mathbf{b} \geq 0且至少有一个分量是00），即使最优解存在，也有可能求不出最优解，出现循环现象

摄动法

考虑以下线性规划问题

mincxs.t.Ax=bx≥0\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad Ax = \mathbf{b} \\ &\qquad x \geq 0 \end{aligned}

让向量b\mathbf{b}向右摄动，即

b(ε)=b+∑j=1nεjpj\mathbf{b}(\varepsilon) = \mathbf{b} + \sum^n_{j=1}\varepsilon^j\mathbf{p}_j

  • ε\varepsilon是充分小的正数
  • εj\varepsilon^j表示ε\varepsilon的jj次方
  • pj\mathbf{p}_j是矩阵AA的第jj列

问题转化为

mincxs.t.Ax=b(ε)x≥0\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} = \mathbf{b}(\varepsilon) \\ &\qquad \mathbf{x} \geq 0 \end{aligned}

定理：对于线性规划问题，存在实数ε1>0\varepsilon_1 > 0，使得当0<ε<ε10 < \varepsilon < \varepsilon_1时，摄动问题是非退化的。

证明：按照之前，AA的秩是mm，因此它能分解为[B,N][B, N]，其中BB可逆，x\mathbf{x}可以分解为x=[xBxN]\mathbf{x}=\begin{bmatrix}\mathbf{x}_B\\\mathbf{x}_N\end{bmatrix}，由Ax=b(ε)A\mathbf{x} = \mathbf{b}(\varepsilon)得到

xB=B−1b(ε)−B−1NxN=B−1(b+∑j=1nεjpj)−B−1NxN=B−1b+∑j=1nεjB−1pj−B−1NxN=b‾+∑j=1nεjyj−B−1NxN\begin{aligned} \mathbf{x}_B &= B^{-1}\mathbf{b}(\varepsilon) - B^{-1}N\mathbf{x}_N \\ &= B^{-1}(\mathbf{b} + \sum^n_{j=1}\varepsilon^j\mathbf{p}_j) - B^{-1}N\mathbf{x}_N \\ &= B^{-1}\mathbf{b} + \sum^n_{j=1}\varepsilon^jB^{-1}\mathbf{p}_j - B^{-1}N\mathbf{x}_N \\ &= \overline{\mathbf{b}} + \sum^n_{j=1}\varepsilon^j\mathbf{y}_j - B^{-1}N\mathbf{x}_N \end{aligned}

把上式按照分量写出

xBi=b‾i+εBi+∑j∈Ryijεj−∑j∈Ryijxj,i=1,⋯ ,mx_{B_i} = \overline{b}_i + \varepsilon^{B_i} + \sum_{j \in R}y_{ij}\varepsilon^j - \sum_{j \in R}y_{ij}x_j, \quad i = 1,\cdots, m

在基BB下，基本解是

xBi=b‾i+εBi+∑j∈Ryijεj,i=1,⋯ ,mxj=0,j∈R\begin{aligned} x_{B_i} &= \overline{b}_i + \varepsilon^{B_i} + \sum_{j \in R}y_{ij}\varepsilon^j, \quad i = 1,\cdots, m \\ x_j &= 0, j \in R \end{aligned}

  • 定理：设对于充分小的ε>0,x^(ε)\varepsilon > 0, \hat{\mathbf{x}}(\varepsilon)是线性规划的基本可行解，则x^(0)\hat{\mathbf{x}}(0)是原来线性规划的基本可行解
  • 推论：设对于充分小的ε>0,x^(ε)\varepsilon > 0, \hat{\mathbf{x}}(\varepsilon)是线性规划的最优解，则x^(0)\hat{\mathbf{x}}(0)是原来的最优解
  • 定理：若线性规划没有可行解，则原来线性规划也没有可行解
  • 定理：若对于充分小的ε>0\varepsilon > 0线性规划是无界问题则原来线性规划也是无界问题
摄动法算法

摄动法与一般单纯形方法的差别主要在于主行的选择，这种方法是按照

b‾r(ε)yrk=min⁡{b‾i(ε)yik∣yik>0}\frac{\overline{b}_r(\varepsilon)}{y_{rk}} = \min \lbrace \frac{\overline{b}_i(\varepsilon)}{y_{ik}} \Big | y_{ik} > 0\rbrace

确定主行，关键是确定最小比值，由于b‾i(ε)/yik\overline{b}_i(\varepsilon)/y_{ik}是ε\varepsilon的多项式，即

b‾i(ε)yik=b‾iyik+∑j=1nyijyikεj\frac{\overline{b}_i(\varepsilon)}{y_{ik}} = \frac{\overline{b}_i}{y_{ik}} + \sum^n_{j=1}\frac{y_{ij}}{y_{ik}}\varepsilon^j

ε\varepsilon是充分小的正数，该多项式值的大小主要决定于低次项，为了确定最小比值，只需要从ε\varepsilon的零次项开始，逐项比较幂的系数

  • 首先比较零次项：b‾i/yik(yik>0)\overline{b}_i/y_{ik}(y_{ik} > 0)
  • 再比较一次项系数，再比较二次项系数

算法：

  • 令

I0={r∣b‾ryrk=min⁡{b‾iyik∣yik>0}}\mathbf{I}_0 = \lbrace r \Big | \frac{\overline{b}_r}{y_{rk}} = \min\lbrace \frac{\overline{b}_i}{y_{ik}} \big | y_{ik} > 0 \rbrace \rbrace

若I0\mathbf{I}_0只有一个元素rr，则xBr\mathbf{x}_{B_r}为离基变量

  • 置j=1j = 1
  • 令

Ij={r∣yrjyrk=min⁡i∈Ij−1{yijyik}}\mathbf{I}_j = \lbrace r \Big | \frac{y_{rj}}{y_{rk}} = \min_{i\in I_{j-1}}\lbrace \frac{y_{ij}}{y_{ik}} \rbrace \rbrace

若Ij\mathbf{I}_j只有一个元素rr，则xBr\mathbf{x}_{B_r}为离基变量

  • 置j:=j+1j := j + 1转上一步骤

Bland规则

  1. 选下标最小的正检验数zj−cjz_j - c_j，所对应的非基变量xNr\mathbf{x}_{N_r}作为进基变量
  2. 离基变量xlx_l的确定：如果同时有几个biyik\frac{b_i}{y_{ik}}达到最小，就选其中下标最小的那个基变量作为离基变量。

r=min⁡{r∣b‾ryrk=min⁡{b‾iyik∣yik>0}}r = \min \lbrace r \Big | \frac{\overline{b}_r}{y_{rk}} = \min\lbrace \frac{\overline{b}_i}{y_{ik}} \big | y_{ik} > 0 \rbrace \rbrace

  • Bland规则的优点是简单易行，但缺点是只考虑最小下标，而不考虑目标函数值下降的快慢。故其效率比字典序或原来单纯形法低
  • 在实际中，退化是常见的，但退化不一定产生循环。事实上，产生循环是较罕见的。

对偶理论

线性规划中普遍存在配对现象，即对每一个线性规划问题，都存在另一个与它有密切关系的线性规划问题。

  • 其中之一称为原问题
  • 另一个称为对偶问题

对称形式的对偶

  • 原问题

mincxs.t.Ax≥bx≥0\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} \geq \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}

  • 对偶问题

maxwbs.t.wA≤cw≥0\begin{aligned} max &\qquad \mathbf{w}\mathbf{b} \\ s.t. &\qquad \mathbf{w}A \leq \mathbf{c} \\ &\qquad \mathbf{w} \geq \mathbf{0} \end{aligned}

原问题 对偶问题
目标函数 c\mathbf{c}与x\mathbf{x}的内积 b\mathbf{b}与w\mathbf{w}的内积
不等式约束 Ax≥bA\mathbf{x} \geq \mathbf{b}，m个不等式 wA≤c\mathbf{w}A \leq \mathbf{c}，n个不等式
分量不等式约束 Aix≥biA_i\mathbf{x} \geq b_i wpj≤cj\mathbf{w}\mathbf{p}_j \leq c_j
变量约束 xj≥0x_j \geq 0 wi≥0w_i \geq 0

原问题有nn个变量、mm个约束，对偶问题有mm个变量、nn个约束

例：

minx1−x2s.t.x1+x2≥5x1−2x2≥1x1,x2≥0⇓max5w1+w2s.t.w1+w2≤1w1−2w2≤−1w1,w2≥0\begin{gathered} \begin{aligned} min &\qquad x_1 - x_2 \\ s.t. &\qquad x_1 + x_2 \geq 5 \\ &\qquad x_1 - 2x_2 \geq 1 \\ &\qquad x_1,x_2 \geq 0 \end{aligned} \\ \Downarrow \\ \begin{aligned} max &\qquad 5w_1 + w_2 \\ s.t. &\qquad w_1 + w_2 \leq 1 \\ &\qquad w_1 - 2w_2 \leq -1 \\ &\qquad w_1,w_2 \geq 0 \end{aligned} \end{gathered}

非对称形式的对偶

mincxs.t.Ax=bx≥0\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}

先将上式写成等价形式

mincxs.t.Ax≥b−Ax≥−bx≥0⇓mincxs.t.[A−A]x≥[b−b]x≥0\begin{gathered} \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} \geq \mathbf{b} \\ &\qquad -A\mathbf{x} \geq -\mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned} \\ \Downarrow \\ \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\begin{bmatrix} A \\ -A \end{bmatrix}\mathbf{x} \geq \begin{bmatrix} \mathbf{b} \\ -\mathbf{b} \end{bmatrix} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned} \end{gathered}

根据对称对偶的定义，对偶问题为

maxub−vbs.t.uA−vA≤cu,v≥0\begin{aligned} max &\qquad \mathbf{u}\mathbf{b} - \mathbf{v}\mathbf{b} \\ s.t. &\qquad \mathbf{u}A - \mathbf{v}A \leq \mathbf{c} \\ &\qquad \mathbf{u},\mathbf{v} \geq \mathbf{0} \end{aligned}

令w=u−v\mathbf{w} = \mathbf{u} - \mathbf{v}，w\mathbf{w}没有非负限制，得到

maxwbs.t.wA≤c\begin{aligned} max &\qquad \mathbf{w}\mathbf{b} \\ s.t. &\qquad \mathbf{w}A \leq \mathbf{c} \end{aligned}

与原问题不同的是，对偶问题没有变量的正负号限制，称为非对称对偶

对偶问题一般情形

实际中线性问题一般含有≥,≤,=\geq, \leq, =等几种约束条件

mincxs.t.A1x≥b1A2x=b2A3x≤b3x≥0\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A_1\mathbf{x} \geq \mathbf{b}_1 \\ &\qquad A_2\mathbf{x} = \mathbf{b}_2 \\ &\qquad A_3\mathbf{x} \leq \mathbf{b}_3 \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}

先引入松弛变量，写为等价形式

mincxs.t.A1x−xs=b1A2x=b2A3x+xt=b3x,xs,xt≥0⇓mincx+0⋅xs+0⋅xts.t.[A1−Im10A200A30Im3][xxsxt]=[b1b2b3]x,xs,xt≥0\begin{gathered} \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A_1\mathbf{x} - \mathbf{x}_s = \mathbf{b}_1 \\ &\qquad A_2\mathbf{x} = \mathbf{b}_2 \\ &\qquad A_3\mathbf{x} + \mathbf{x}_t = \mathbf{b}_3 \\ &\qquad \mathbf{x}, \mathbf{x}_s, \mathbf{x}_t \geq \mathbf{0} \end{aligned} \\ \Downarrow \\ \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} + 0 \cdot \mathbf{x}_s + 0 \cdot \mathbf{x}_t \\ s.t. &\qquad \begin{bmatrix} A_1 & -\mathbf{I}_{m_1} & \mathbf{0} \\ A_2 & \mathbf{0} & \mathbf{0} \\ A_3 & \mathbf{0} & \mathbf{I}_{m_3} \end{bmatrix}\begin{bmatrix} \mathbf{x} \\ \mathbf{x}_s \\ \mathbf{x}_t \end{bmatrix} = \begin{bmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \\ \mathbf{b}_3 \end{bmatrix} \\ &\qquad \mathbf{x}, \mathbf{x}_s, \mathbf{x}_t \geq \mathbf{0} \end{aligned} \end{gathered}

根据对称对偶的定义，对偶问题为

maxw1b1+w2b2+w3b3s.t.w1A1+w2A2+w3A3≤cw1≥0A1x≥b1w3≤0A3x≤b3w2无限制A2x=b2\begin{aligned} max &\qquad \mathbf{w}_1\mathbf{b}_1 + \mathbf{w}_2\mathbf{b}_2 + \mathbf{w}_3\mathbf{b}_3 \\ s.t. &\qquad \mathbf{w}_1A_1 + \mathbf{w}_2A_2 + \mathbf{w}_3A_3 \leq \mathbf{c} \\ &\qquad \mathbf{w}_1 \geq 0 & \color{grey}A_1\mathbf{x} \geq \mathbf{b}_1 \\ &\qquad \mathbf{w}_3 \leq 0 & \color{grey}A_3\mathbf{x} \leq \mathbf{b}_3 \\ &\qquad \mathbf{w}_2 \text{无限制} & \color{grey}A_2\mathbf{x} = \mathbf{b}_2 \end{aligned}

  • 原问题中约束A1x≥b1A_1\mathbf{x} \geq \mathbf{b}_1对应的对偶变量w1\mathbf{w}_1有非负限制
  • 原问题中约束A2x=b2A_2\mathbf{x} = \mathbf{b}_2对应的对偶变量w2\mathbf{w}_2没有限制
  • 原问题中约束A3x≤b3A_3\mathbf{x} \leq \mathbf{b}_3对应的对偶变量w3\mathbf{w}_3有非正限制

上述三种形式的对偶中，原问题和对偶问题是相对的，相互对偶的两个问题中，任何一个问题均可作为原问题，另一个作为对偶问题

对偶问题总结

原问题 对偶问题
问题 极大化：max⁡\max 极小化：min⁡\min
问题 极小化：min⁡\min 极大化：max⁡\max
系数·右端向量 系数：c\mathbf{c}，右端向量：b\mathbf{b} 系数：b\mathbf{b}，右端向量：c\mathbf{c}
约束条件 min⁡Ax≥b\min A\mathbf{x} \geq \mathbf{b}，max⁡Ax≤b\max A\mathbf{x} \leq \mathbf{b} w≥0\mathbf{w} \geq 0
约束条件 min⁡Ax≤b\min A\mathbf{x} \leq \mathbf{b}，max⁡Ax≥b\max A\mathbf{x} \geq \mathbf{b} w≤0\mathbf{w} \leq 0
约束条件 == 无限制
变量约束 min⁡x≥0\min x \geq 0，max⁡x≤0\max x \leq 0 ≤\leq不等式
变量约束 min⁡x≤0\min x \leq 0，max⁡x≥0\max x \geq 0 ≥\geq不等式
变量约束 无限制变量 ==等式

对偶定理

定理：设x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}分别是原问题和对偶问题的可行解，则cx(0)≥w(0)b\mathbf{c}\mathbf{x}^{(0)} \geq \mathbf{w}^{(0)}\mathbf{b}

∑j=1ncjxj≥∑i=1mbiwi原问题函数值≥对偶问题函数值\begin{aligned} \sum^n_{j=1}c_jx_j &\geq \sum^m_{i= 1}b_iw_i \\ \text{原问题函数值} &\geq \text{对偶问题函数值} \end{aligned}

也就是原问题的目标函数值大于等于对偶函数值，就原问题和对偶问题的可行解而言，对于对偶问题中的两个问题，每一个问题的任何一个可行解处的目标函数值，都给出另一个问题的目标函数值的界

  • 极小化问题给出极大化的目标函数值的上界
  • 极大化问题给出极小化的目标函数值的下界

推论：若x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}分别是原问题和对偶问题的可行解，且cx(0)=w(0)b\mathbf{c}\mathbf{x}^{(0)} = \mathbf{w}^{(0)}\mathbf{b}，则x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}分别是原问题和对偶问题的最优解
推论：原问题和对偶问题有最优解的充要条件是它们同时具有可行解
推论：若线性规划（对称对偶）存在一个对应基BB的最优基本可行解，则单纯形乘子w=cBB−1\mathbf{w} = \mathbf{c}_BB^{-1}是对偶问题的一个最优解
推论：

原问题的目标函数在可行域上无下界，则对偶问题无可行解对偶问题的目标函数在可行域上无上界，则原问题无可行解\begin{aligned} \text{原问题的目标函数在可行域上无下界，则对偶问题无可行解} \\ \text{对偶问题的目标函数在可行域上无上界，则原问题无可行解} \end{aligned}

定理：设原问题和对偶问题中有一个存在最优解，则另一个问题也存在最优解，且两个问题的目标函数的最优值相等

互补松弛性质

定理：设x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}分别是原问题和对偶问题的可行解（对称对偶），那么x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}都是最优解的充要条件是，对所有ii和jj，下列关系成立

xj(0)>0⇒w(0)pj=cjw(0)pj<cj⇒xj(0)=0wi(0)>0⇒Aix(0)=biAix(0)>bi⇒wi(0)=0\begin{aligned} \mathbf{x}^{(0)}_j > 0 &\Rightarrow \mathbf{w}^{(0)}\mathbf{p}_j = c_j \\ \mathbf{w}^{(0)}\mathbf{p}_j < c_j &\Rightarrow \mathbf{x}^{(0)}_j = 0 \\ \\ w^{(0)}_i > 0 &\Rightarrow A_i\mathbf{x}^{(0)} = b_i \\ A_i\mathbf{x}^{(0)} > b_i &\Rightarrow w^{(0)}_i = 0 \end{aligned}

定理：设x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}分别是原问题和对偶问题的可行解（非对称对偶），那么x(0)\mathbf{x}^{(0)}和w(0)\mathbf{w}^{(0)}都是最优解的充要条件是，对所有jj，下列关系成立

xj(0)>0⇒w(0)pj=cjw(0)pj<cj⇒xj(0)=0\begin{aligned} \mathbf{x}^{(0)}_j > 0 &\Rightarrow \mathbf{w}^{(0)}\mathbf{p}_j = c_j \\ \mathbf{w}^{(0)}\mathbf{p}_j < c_j &\Rightarrow \mathbf{x}^{(0)}_j = 0 \end{aligned}

强互补松弛定理

若对称对偶问题存在最优解，则必存在满足强互补松弛条件的最优解，即存在最优解(x‾,x‾s)(\overline{\mathbf{x}}, \overline{\mathbf{x}}_s)和(w‾,w‾s)(\overline{\mathbf{w}}, \overline{\mathbf{w}}_s)，使得由对应分量构成的所有二元数组{(x‾j,w‾m+j),(x‾n+i,w‾i) ∣ j=1,2,⋯ ,n;i=1,2,⋯ ,m}\lbrace (\overline{x}_j, \overline{w}_{m + j}), (\overline{x}_{n+i}, \overline{w}_{i}) \ |\ j =1,2,\cdots,n; i =1, 2, \cdots, m\rbrace中，每个二元数组均包含一个正数，其中w‾m+j\overline{w}_{m+j}和x‾n+i\overline{x}_{n+i}分别是松弛变量w‾s\overline{\mathbf{w}}_s和x‾s\overline{\mathbf{x}}_s的第jj个和第ii个分量

参考文献

  • 最优化 - 理论与算法丨陈宝林丨第二版丨7-302-11376-9