# Linear Programming

Linear programming is the minimization (or maximization) of a linear objective subject to linear constraints. There are several widely adopted schemes for representing linear programming problems. Here we adopt a scheme corresponding where the linear objective is written in terms of decision variables $x_1, x_2, \ldots, x_N$ as

\begin{align}
\min_{x_1, x_1, \ldots, x_N} c_1x_1 + c_2x_2 + \cdots + c_Nx_N
\end{align}

subject to

\begin{align}
x_i  \geq 0 & \qquad i=1,\ldots,N\quad\mbox{lower bounds on decision variables}\\
\sum_{j=1}^N a^{ub}_{ij}x_j \leq b^{ub}_i & \qquad i=1,\ldots,M_{ub}\quad\mbox{upper bound constraints} \\
\sum_{j=1}^N a^{eq}_{ij}x_j = b^{eq}_i & \qquad i=1,\ldots,M_{eq}\quad\mbox{equality constraints}\\
\end{align}

## Matrix/Vector format

The notation can be simplified by adopting a matrix/vector formulation where

\begin{align}
\min_{x\geq 0} c^T x
\end{align}

subject to

\begin{align}
A_{ub} x \leq b_{ub} \\
A_{eq} x = b_{eq}
\end{align}

where $c$, $A_{ub}, b_{ub}$, and $A_{eq}, b_{eq}$, are vectors and matrices of coefficients constructed from the linear expressions given above.

## Example 19.3: Refinery Blending Problem

The decision variables are


| Variable | Description | Units |
| ---------|-------------| ------|
| $x_1$ | crude #1 | bbl/day |
| $x_2$ | crude #2 | bbl/day |
| $x_3$ | gasoline | bbl/day |
| $x_4$ | kerosine | bbl/day |
| $x_5$ | fuel oil | bbl/day |
| $x_6$ | residual | bbl/day |


The overall objective is to maximize profit

\begin{align}
\mbox{profit} & = \mbox{income} - \mbox{raw_material_cost} - \mbox{processing_cost}
\end{align}

where the financial components are given by

\begin{align}
\mbox{income} & = 72x_3 + 48x_4 + 42x_5 + 20x_6 \\
\mbox{raw_material_cost} & = 48x_1 + 30x_2 \\
\mbox{processing_cost} & = 1 x_1 + 2x_2
\end{align}

Combining these terms, the objective is to maximize

\begin{align}
f & = c^T x = - 49 x_1 - 32 x_2 + 72 x_3 + 48x_4 + 42x_5 + 20x_6 
\end{align}

The material balance equations are

\begin{align}
\mbox{gasoline: } x_3 & = 0.80 x_1 + 0.44 x_2 \\
\mbox{kerosine: } x_4 & = 0.05 x_1 + 0.10 x_2 \\
\mbox{fuel oil: } x_5 & = 0.10 x_1 + 0.36 x_2 \\
\mbox{residual: } x_6 & = 0.05 x_1 + 0.10 x_2
\end{align}

Production limits

\begin{align}
\mbox{gasoline: } x_3 & \leq 24,000 \\
\mbox{kerosine: } x_4 & \leq 2,000 \\
\mbox{fuel oil: } x_5 & \leq 6,000
\end{align}

\begin{align}
\underbrace{\left[\begin{array}{cccccc}
0.80 & 0.44 & -1 & 0 & 0 & 0 \\
0.05 & 0.10 & 0 & -1 & 0 & 0 \\
0.10 & 0.36 & 0 & 0 & -1 & 0 \\
0.05 & 0.10 & 0 & 0 & 0 & -1
\end{array}\right]}_{A_{eq}}
\left[\begin{array}{c}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 
\end{array}\right]
& = 
\underbrace{\left[\begin{array}{c}
0 \\ 0 \\ 0 \\ 0
\end{array}\right]}_{b_{eq}}
\end{align}


```python
from scipy.optimize import linprog

c = [49, 32, -72, -48, -42, -20]

A_ub = [[0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0]]

b_ub = [24000, 2001, 6000]

A_eq = [[0.80, 0.44, -1,  0,  0,  0],
        [0.05, 0.10,  0, -1,  0,  0],
        [0.10, 0.36,  0,  0, -1,  0],
        [0.05, 0.10,  0,  0,  0, -1]]

b_eq = [0, 0, 0, 0]

results = linprog(c, A_ub, b_ub, A_eq, b_eq)
results
p0 = 573517.24
print('additional profit', -results.fun - p0)
```

    additional profit 175.0356333295349



```python
print(results.message)
if results.success:
    for k in range(len(results.x)):
        print('x[{0:2d}] = {1:7.1f} bbl/day'.format(k+1, results.x[k]))
```

    Optimization terminated successfully.
    x[ 1] = 26199.3 bbl/day
    x[ 2] =  6910.3 bbl/day
    x[ 3] = 24000.0 bbl/day
    x[ 4] =  2001.0 bbl/day
    x[ 5] =  5107.7 bbl/day
    x[ 6] =  2001.0 bbl/day



```python

```


```python

```

9aebee9bfcd309ba11a7999a482518e113b3f0e5
ipynb
Jupyter Notebook
Mathematics/Mathematical Modeling/06.03-Linear-Programming.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
Mathematics/Mathematical Modeling/06.03-Linear-Programming.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
Mathematics/Mathematical Modeling/06.03-Linear-Programming.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
2022-02-09T15:41:33.000Z
2022-02-11T07:47:40.000Z
Qwen/Qwen-72B
1. YES
2. YES