# Linear programming with scipy

See https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html


```python
import scipy.optimize
```

Problem examples:
- http://people.brunel.ac.uk/~mastjjb/jeb/or/morelp.html

## Scipy's syntax

Example for a problem of 2 dimensions:

$$
\begin{align}
    \min_{x_1,x_2} & \quad \color{\red}{c_1} x_1 + \color{\red}{c_2} x_2 \\
    \text{s.t.}    & \quad \color{\orange}{A_{1,1}} x_1 + \color{\orange}{A_{1,2}} x_2 \leq \color{\green}{b_1} \\
                   & \quad \color{\orange}{A_{2,1}} x_1 + \color{\orange}{A_{2,2}} x_2 \leq \color{\green}{b_2} \\
                   & \quad \color{\purple}{B_{1,1}} \geq x_1 \geq \color{\purple}{B_{1,2}} \\
                   & \quad \color{\purple}{B_{2,1}} \geq x_2 \geq \color{\purple}{B_{2,2}} \\
\end{align}
$$

 

$$
\color{\red}{
\boldsymbol{c} = \begin{pmatrix}
    c_1 \\
    c_2
\end{pmatrix}
}
\quad
\color{\orange}{
\boldsymbol{A} = \begin{pmatrix}
    A_{1,1} & A_{1,2} \\
    A_{2,1} & A_{2,2}
\end{pmatrix}
}
\quad
\color{\green}{
\boldsymbol{b} = \begin{pmatrix}
    b_1 \\
    b_2
\end{pmatrix}
}
\quad
\color{\purple}{
\boldsymbol{B} = \begin{pmatrix}
    B_{1,1} & B_{1,2} \\
    B_{2,1} & B_{2,2}
\end{pmatrix}
}
$$

 

$$
\text{scipy.optimize.linprog}(\color{\red}{\boldsymbol{c}}, ~ \color{\orange}{\boldsymbol{A}}, ~ \color{\green}{\boldsymbol{b}}, ~ \color{\purple}{\boldsymbol{B}})
$$

## Example 1

$$
\begin{align}
    \min_{x_0,x_1} & \quad -x_0 + 4 x_1 \\
    \text{s.t.}    & \quad -3 x_0 + x_1 \leq 6 \\
                   & \quad -x_0 - 2 x_1 \geq -4 \\
                   & \quad  x_1 \geq -3
\end{align}
$$


```python
# Coefficients of the linear objective function to be minimized
c = [-1, 4]

# 2-D array which, when matrix-multiplied by x, gives the values of the upper-bound inequality constraints at x.
A = [[-3, 1],
     [ 1, 2]]

# 1-D array of values representing the upper-bound of each inequality constraint (row) in A.
b = [6, 4]

# Sequence of (min, max) pairs for each element in x, defining the bounds on that parameter.
# Use None for one of min or max when there is no bound in that direction.
# By default bounds are (0, None) (non-negative).
# If a sequence containing a single tuple is provided, then min and max will be applied to all variables in the problem.
x0_bounds = (None, None)
x1_bounds = (-3, None)
bounds = (x0_bounds,x1_bounds)

scipy.optimize.linprog(c, A_ub=A, b_ub=b, bounds=bounds)
```

## The carpenter problem


```python
# Coefficients of the linear objective function to be minimized
c = np.array([3, 5])

# 2-D array which, when matrix-multiplied by x, gives the values of the upper-bound inequality constraints at x.
A_ub = np.array([[3, 2],
                 [1, 2],
                 [5, 4]])

# 1-D array of values representing the upper-bound of each inequality constraint (row) in A_ub.
b_ub = np.array([700, 500, 1500])

# Sequence of (min, max) pairs for each element in x, defining the bounds on that parameter.
# Use None for one of min or max when there is no bound in that direction.
# By default bounds are (0, None) (non-negative).
# If a sequence containing a single tuple is provided, then min and max will be applied to all variables in the problem.
bounds = ((0, None), (0, None))

scipy.optimize.linprog(-c, A_ub=A_ub, b_ub=b_ub, bounds=bounds)
```

The optimal solution is obtain for $x_1=100$ and $x_2=200$ with a gain of 1300.

e2b4ae6daf557b63ee3754f935363337dfe078c6
ipynb
Jupyter Notebook
nb_dev_python/python_scipy_linear_programming_en.ipynb
jdhp-docs/python-notebooks
91a97ea5cf374337efa7409e4992ea3f26b99179
MIT
2017-05-03T12:23:36.000Z
2020-10-26T17:30:56.000Z
nb_dev_python/python_scipy_linear_programming_en.ipynb
jdhp-docs/python-notebooks
91a97ea5cf374337efa7409e4992ea3f26b99179
MIT
nb_dev_python/python_scipy_linear_programming_en.ipynb
jdhp-docs/python-notebooks
91a97ea5cf374337efa7409e4992ea3f26b99179
MIT
2020-10-26T17:30:57.000Z
2020-10-26T17:30:57.000Z
Qwen/Qwen-72B
1. YES
2. YES