Convert LP to a Standard Form
\[\min{}c^\top{}x,\text{subject to }Ax=b\land{}x\geq0\]
For Inequality
- \(x+y\geq{}a\rightarrow{}x+y-z=a,z\geq0\)
- \(x+y\leq{}a\rightarrow{}x+y+s=a,s\geq0\)
- Unrestricted \(\rightarrow{}x=y-z,y\geq0,z\geq0\)
Preview of Simplex Algorithm
Basic solutions
\[Ax=b,A\in{}R^{m\times{}n},x\in{}R^n,n\geq{}m\] Set \(n-m\) variables to \(0\) and solving for the remaining \(m\) variables. The columns for the remaining \(m\) variables are linear independent. \[\text{Total number: }C_n^m\]
Basic feasible solutions
- Feasible region for any LP problem is a convex set
- If a LP has an optimal solution, there must be an extreme point of the feasible region that is optimal
Proof
\[\text{Suppose }x^\star=\sum_{i=1}^n\alpha_ix_i\text{ is an optimal solution}\] \[c^\top{}x^\star=c^\top{}\sum_{i=1}^n\alpha_ix_i>\sum_{i=1}^n\alpha_ic^\top{}x^\star=c^\top{}x^\star\]
Adjacent Basic Feasible Solutions
Two basic feasible solutions are said to be adjacent if their sets of basic variables have \(m-1\) basic variables in common
General Description of the Simplex Algorithm
- Find an initial bfs of LP
- Change bfs to its adjacent bfs
- Recalculate by Gaussian elimination
- For maximum, until the first row is all nonnegative; For minimum, until the first row is all nonpositive
Example
Standard form: \[\max{}z=3x_1+5x_2\] \[\begin{split} \text{subject to }\quad{}x_1+s_1&=8\\ 2x_2+s_2&=12\\ 3x_1+4x_2+s_3&=36\\ x_1,x_2,s_1,s_2,s_3&\geq0 \end{split} \label{p1s}\]
Choose \((s_1,s_2,s_3)\) as BFS, we have table:
| \(z\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | rhs | Basic Variable |
|---|---|---|---|---|---|---|---|
| 1 | -3 | -5 | 0 | 0 | 0 | 0 | \(z=0\) |
| 0 | 1 | 0 | 1 | 0 | 0 | 8 | \(s_1=8\) |
| 0 | 0 | 2 | 0 | 1 | 0 | 12 | \(s_2=12\) |
| 0 | 3 | 4 | 0 | 0 | 1 | 36 | \(s_3=36\) |
Choose \((s_1,x_2,s_3)\) as BFS, we have table:
| \(z\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | rhs | Basic Variable |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 2.5 | 0 | 30 | \(z=30\) |
| 0 | 1 | 0 | 1 | 0 | 0 | 8 | \(s_1=8\) |
| 0 | 0 | 1 | 0 | 0.5 | 0 | 6 | \(x_2=6\) |
| 0 | 3 | 0 | 0 | -2 | 1 | 12 | \(s_3=12\) |
Choose \((s_1,x_2,x_1)\) as BFS, we have table:
| \(z\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | rhs | Basic Variable |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0.5 | 0 | 42 | \(z=42\) |
| - | - | - | - | - | - | - | - |
| 0 | 0 | 1 | 0 | 0.5 | 0 | 12 | \(x_2=6\) |
| 0 | 1 | 0 | 0 | -2/3 | 1/3 | 4 | \(x_1=4\) |
So the final result is \[x_1=4,x_2=6,z_{max}=42\]
Degeneracy
An LP is degenerate if it has at least one basic feasible solution in which a basic feasible variable is equal to \(0\)
- pivoting may not improve the objective value
- simplex method may end up in cycles
Two BFS Methods
Big M Method
\[\min{}f(x),\text{ subject to }Ax=b(b\succeq0)\] \[\Rightarrow\min{}f(x)+M^\top{}a,\text{ subject to }Ax+Ia=b\]
Introduce \(a_i\) to every row which has a negative coefficient (on \(s\) or \(z\)), then we can get bfs easily
\[(x=0,a=b)\]
If we can't reduce all parameters of \(a\) to 0, then the original problem is infeasible
Two-Phase Method
\[\min{}f(x),\text{ subject to }Ax=b(b\succeq0)\] \[\Rightarrow\min{}I^\top{}a,\text{ subject to }Ax+Ia=b,a\succeq0\] If \(a^\star\neq0\), then the original problem is infeasible
