Linear program
==============
A linear program is an optimization problem with a linear objective and
affine inequality constraints. A common standard form is the following:
.. math::
\begin{array}{ll}
\mbox{minimize} & c^Tx \\
\mbox{subject to} & Ax \leq b.
\end{array}
Here :math:`A \in \mathcal{R}^{m \times n}`,
:math:`b \in \mathcal{R}^m`, and :math:`c \in \mathcal{R}^n` are problem
data and :math:`x \in \mathcal{R}^{n}` is the optimization variable. The
inequality constraint :math:`Ax \leq b` is elementwise.
For example, we might have :math:`n` different products, each
constructed out of :math:`m` components. Each entry :math:`A_{ij}` is
the amount of component :math:`i` required to build one unit of product
:math:`j`. Each entry :math:`b_i` is the total amount of component
:math:`i` available. We lose :math:`c_j` for each unit of product
:math:`j` (:math:`c_j < 0` indicates profit). Our goal then is to choose
how many units of each product :math:`j` to make, :math:`x_j`, in order
to minimize loss without exceeding our budget for any component.
In addition to a solution :math:`x^\star`, we obtain a dual solution
:math:`\lambda^\star`. A positive entry :math:`\lambda^\star_i`
indicates that the constraint :math:`a_i^Tx \leq b_i` holds with
equality for :math:`x^\star` and suggests that changing :math:`b_i`
would change the optimal value.
Example
-------
In the following code, we solve a linear program with CVXPY.
.. code:: python
# Import packages.
import cvxpy as cp
import numpy as np
# Generate a random non-trivial linear program.
m = 15
n = 10
np.random.seed(1)
s0 = np.random.randn(m)
lamb0 = np.maximum(-s0, 0)
s0 = np.maximum(s0, 0)
x0 = np.random.randn(n)
A = np.random.randn(m, n)
b = A @ x0 + s0
c = -A.T @ lamb0
# Define and solve the CVXPY problem.
x = cp.Variable(n)
prob = cp.Problem(cp.Minimize(c.T@x),
[A @ x <= b])
prob.solve()
# Print result.
print("\nThe optimal value is", prob.value)
print("A solution x is")
print(x.value)
print("A dual solution is")
print(prob.constraints[0].dual_value)
.. parsed-literal::
The optimal value is -15.220912604467838
A solution x is
[-1.10131657 -0.16370661 -0.89711643 0.03228613 0.60662428 -1.12655967
1.12985839 0.88200333 0.49089264 0.89851057]
A dual solution is
[0. 0.61175641 0.52817175 1.07296862 0. 2.3015387
0. 0.7612069 0. 0.24937038 0. 2.06014071
0.3224172 0.38405435 0. ]