MATH06, Linear programming
Back to the previous page｜Optimization
List of posts to read before reading this article
Contents
Linear programming
The solution to a linear optimization problem must necessarily lie on a constraint boundary, so it is sufficient to search the vertices of the intersections of the linear constraint functions.
- Simplex algorithm
$$the\ objective\ function\ :\ f(x) = -x_{0}+2x_{1}-3x_{2}$$
$$s.t. \qquad x_{0}+x_{1} \le 1,\ -x_{0}+3x_{1} \le 2,\ -x_{1}+x_{2} \le 3$$
$$\ $$
$$standard\ form\ for\ linear\ programming$$
$$min_{x}c^{T}x \qquad where\ Ax\ ≤\ b\ and\ x\ ≥\ 0$$
$$A = \begin{pmatrix}
1 & 1 & 0 \\
-1 & 3 & 0 \\
0 & -1 & 1
\end{pmatrix},\
b = \begin{pmatrix}
1 \\
2 \\
3
\end{pmatrix},\
c = \begin{pmatrix}
-1 \\
-2 \\
-3
\end{pmatrix}$$
import numpy as np
import cvxopt
c = np.array([-1.0, 2.0, -3.0])
A = np.array([[ 1.0, 1.0, 0.0],
[-1.0, 3.0, 0.0],
[ 0.0, -1.0, 1.0]])
b = np.array([1.0, 2.0, 3.0])
A_ = cvxopt.matrix(A)
b_ = cvxopt.matrix(b)
c_ = cvxopt.matrix(c)
cvxopt.solvers.lp(c_, A_, b_)
OUTPUT
Optimal solution found.
{'dual infeasibility': 1.4835979218054372e-16,
'dual objective': -10.0,
'dual slack': 0.0,
'gap': 0.0,
'iterations': 0,
'primal infeasibility': 0.0,
'primal objective': -10.0,
'primal slack': -0.0,
'relative gap': 0.0,
'residual as dual infeasibility certificate': None,
'residual as primal infeasibility certificate': None,
's': <3x1 matrix, tc='d'>,
'status': 'optimal',
'x': <3x1 matrix, tc='d'>,
'y': <0x1 matrix, tc='d'>,
'z': <3x1 matrix, tc='d'>}
SUPPLEMENT
INPUT
x = np.array(sol['x'])
x
OUTPUT
array([[ 0.25],
[ 0.75],
[ 3.75]])
INPUT
sol['primal objective']
OUTPUT
-10.0
List of posts followed by this article
Reference