Linear Programming

General Form of Linear Programming

We can usually express the problem as

$$\begin{array}{rlllll} \min & f(\bold{x})=\bold{c}^T\bold{x} \\ \text{s.t.} & \bold{Ax=b} \\ & \bold{x}\ge 0\\ \text{where} & \bold{x}=\begin{bmatrix} x_1\\x_2\\\vdots\\x_n \end{bmatrix}, \bold{b}=\begin{bmatrix} b_1\\b_2\\\vdots\\ b_m \end{bmatrix}\ge 0, \bold{c}=\begin{bmatrix} c_1\\c_2\\\vdots\\c_n \end{bmatrix}\\ \text{and} & \bold{A}=\begin{bmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,n}\\ a_{2,1} & a_{2,2} & \dots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n} \end{bmatrix} \end{array}$$

• If we have some inequality constraints, we can transform it into an equality constraint by adding slack variables.
• Also note that, here we require $x_i\ge 0$. If some constraints have the form $l\le x_i\le r$, we can transform it into two constraints $x_i'=x_i-l\ge 0, x_i''=r-x_i\ge 0'$.
  • In addition, if $x_i$ is unbounded, we can set $x_i=x_a-x_b$ where $x_a\ge 0, x_b\ge 0$ as a transformation.