问题求解

Linear Programming

2019-02-24 08:00 CST
2019-12-22 15:33 CST
CC BY-NC 4.0

Linear Programming

  • Linear Programming Problem: the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints
    • feasible solution, feasible area, objective function, objective value, optimal solution, optimal objective value
  • unbounded: have a infinite objective value
  • infeasible: no feasible value
  • Equivalent: for each feasible solution $\overline{x}$ to $L$ with objective value $z$, there is a corresponding feasible solution $\overline{x}'$ to $L'$ with objective value $z'$, and for each feasible solution $\overline{x}'$ to $L'$ with objective value $z'$, there is a corresponding feasible solution $\overline{x}$ to $L$ with objective value ́.

Standard Form

  • Maximize $\sum_{j=1}^nc_jx_j$
  • subject to $\sum_{j=1}^na_{ij}x_j\leq b_i, x_{j}\geq 0$
  • Converting to Stand Form
    • Turn Minimize to Maximize
    • $x=x_1-x_2,x_1>0,x_2>0$
    • Turn equation to inequation
    • Turn $\geq$ to $\leq$
  • $(A,b,c)$
    • Maximize $c^Tx$
    • subject to $Ax\leq b,x\geq 0$

Slack Form

  • Maximize $\sum_{j=1}^nc_jx_j$
  • subject to $x_t=\sum_{j=1}^nt_jx_j,x_i>0$
  • basic variable: Left side of equation
  • nonbasic variable: Right side of equation
  • $(N,B,A,b,c,v)$
    • Maximize $v+c*x$
    • subject to $x_i=b_i-\sum_{j\in N}a_{ij}x_j$

Formulating Problems

  • Shortest Path
    • Maximize $d_t$
    • subject to $d_v\leq d_u+w(u,v),d_s=0$
  • Maximum Flow
    • Maximize $\sum_{v\in V}f_{sv}-\sum_{v\in V}f_{vs}$
    • subject to $f_{uv}\leq c(u,v),\sum_{v\in V}f_{vu}=\sum_{v\in V}f_{uv},f_{uv}\geq 0$
  • Minimum-cost Flow
    • Minimize $\sum_{(u,v)\in E}a(u,v)f_{uv}$
    • subject to $f_{uv}\leq c(u,v), \sum_{v\in V}f_{vu}-\sum_{v\in V}f_{uv}=0,f_{uv}\geq 0,\sum_{v \in V}f_{sv}-\sum_{v\in V}f_{vs}=d$
  • Multicommodity Flow
    • Minimize $0$
    • subject to $\sum_{i=1}{k}f_{iuv}\leq c(u,v),\sum_{v\in V}f_{iuv}-\sum_{v\in V}f_{ivu} = 0,\sum_{v\in V}f_{is_iv}-\sum_{v\in V}f_{ivs_i}=d_i,f_{iuv}\geq 0$

Simplex Algorithm

  • basic solution: set N to be 0, calculating B
  • pivot: choose a nonbasic varible(entering variable) and a basic variable(leaving variable) and exchange their roles.
    • $(N,B,A,b,c,v)\rightarrow (\hat{N},\hat{B},\hat{A},\hat{b},\hat{c},\hat{v})$
  • Proof:
    • 若初始解可行,最终返回一个可行解或无解
    • 算法会终止
      • 至多$\binom{n+m}{m}$次迭代
      • Bland 规则必终止
    • 返回解最优
    • 可以找到初始可行值
      • Maximize $-x_0$
      • subject to $A^Ty-c\geq 0$

Duality

  • 标准型转换
    • prime linear program
      • Maximize $c^Tx$
      • subject to $Ax\leq b,x\geq 0$
    • dual linear program
      • Minmize $b^Ty$
      • subject to $A^Ty\geq c,y\geq 0$
  • 一般型转换
prime dual
$\max c_1x_1+\cdots+c_nx_n$ $\min b_1y_1+\cdots+b_my_m$
$a^Tx\geq b$ $y_i\leq 0$
$a^Tx=b$ -
$a^Tx\leq b$ $y_i\geq 0$
- $y_i=0$
$x_i\geq 0$ $a^Ty\geq c$
$x_i\leq 0$ $a^Ty\leq c$
- $a^Ty=c$
$x_i=0$ -
  • Weak Duality Theorem: $\forall$ feasible primal solution $x$ and dual solution $y$, $b^Ty\geq c^Tx$
  • Strong Duality Theorem: Primal LP has finite optimal solution $x^$ iff dual LP has finite optimal solution $y^$, $y^{T}b=c^Tx^$
  • Complementary Slackness Conditions: $\forall$ feasible primal solution $x$ and dual solution $y$, $x$ and $y$ are both optimal iff
    • $\forall i$: either $A_{i\cdot}x=b_i$ or $y_i=0$
    • $\forall j$: either $y^TA_{\cdot j}=c_j$ or $x_j=0$
  • Relaxed Complementary Slackness Conditions: $\forall$ feasible primal solution $x$ and dual solution $y$
    • $\forall i$: either $A_{i\cdot}x\leq \alpha b_i$ or $y_i=0$
    • $\forall j$: either $y^TA_{\cdot j}=c_j/\beta$ or $x_j=0$
    • then $c^Tx\leq \alpha\beta b^Ty\leq\alpha\beta\text{OPT}_\text{LP}$
  • Fundamental theorem of linear programming
    • Any linear program L, given in standard form, either:
      • has an optimal solution with a finite objective value
      • infeasible
      • unbounded

Code

//n: number of variable
//m: number of restriction

void pivot(int l, int e) {
    b[l] /= a[l][e];
    for (int j = 1; j <= n; j++)
        if (j != e) a[l][j] /= a[l][e];
    a[l][e] = 1 / a[l][e];

    for (int i = 1; i <= m; i++)
        if (i != l && fabs(a[i][e]) > 0) {
            b[i] -= a[i][e] * b[l];
            for (int j = 1; j <= n; j++)
                if (j != e) a[i][j] -= a[i][e] * a[l][j];
            a[i][e] = -a[i][e] * a[l][e];
        }

    ans += c[e] * b[l];
    for (int j = 1; j <= n; j++)
        if (j != e) c[j] -= c[e] * a[l][j];
    c[e] = -c[e] * a[l][e];
}

double simplex() {
    while (true) {
        int enter = 0, leave = 0;
        // Select enter variable
        for (enter = 1; enter <= n; ++enter)
            if (c[enter] > eps) break;
        if (enter == n + 1) return ans;
        // Select leave variable
        double mn = INF;
        for (int i = 1; i <= m; ++i)
            if (a[i][enter] > eps && mn > b[i] / a[i][enter]) {
                mn = b[i] / a[i][enter];
                leave = i;
            }
        if (mn == INF) return INF;
        pivot(leave, enter);
    }
}