# Modeling using Linear Programming

#### Optimization using linear models.

By Vamshi Jandhyala in mathematics optimization

September 20, 2021

## Resource Allocation Problem

Consider a factory producing a number $n$ of different goods (say goods $1, . . . , n$). These goods use $m$ different raw resources (say resources $1, . . . , m$). Suppose that the decision maker observes that the amounts of raw resources are $b_1, . . . , b_m$. Each unit of resource $i$ costs $c_i$. Producing each unit of good $j$ requires $r_{1j}$ units of resource $1$, $r_{2j}$ units of resource $2, . . . ,$ and $r_{mj}$ units of resource $m$. Finally, each unit of good $j$ can be sold for $s_j$ dollars. Consequently, the profit for each unit of good $j$ produced is

$$ p_j = s_{j} - \sum_{i=1}^m c_j r_{ij} \text{ for $j = 1, . . . , n$}. $$

As the operator of this factory, the decision maker, one must decide how many units of each good to produce in order to maximize total profit.

## Modeling using Linear Programming

To use linear programming, we first describe our problem with a number of linear functions. We also assume that we can produce fractional units of each product. The inputs are the values $\textbf{r}, \textbf{b}, \textbf{s}$ and $\textbf{c}$, the decisions or outputs are the $n$ quantities $x_1, . . . , x_n$ of each good to produce.

The first linear function describes the objective of the decision maker:

$$ \sum_{j=1}^n p_j x_j, $$

which is the total profit.

Next, we have $m$ linear functions describing the amounts of each of the resources required:

$$ \sum_{j=1}^n r_{ij} x_j \text{ , for $i = 1, . . . , m$}. $$

The standard form of presenting the problem to solve is

$$
\begin{aligned}
\underset{x_1,…,x_n}{\max} &\sum_{j=1}^n p_j x_j \\

\text{subject to} & \sum_{j=1}^n r_{ij} x_j \leq b_i \text{ , for $i = 1, . . . , m$} \\

&x_j ≥ 0 \text{, for $i = 1, . . . , n$}
\end{aligned}
$$

## Example

A factory makes products $A$ and $B$, which makes profit of $£8$ and $£6$ respectively per unit. $2$ units of cement and $7$ units of sand are utilized for producing a unit of type $A$ whereas $2$ units of cement and $5$ units of sand are required to produce a unit of type $B$. The total units of cement used must be less than or equal to $11$ and the the total units of sand used must be less than or equal to $34$. Compute the number of units of each product that must be produced in order to maximize the profit.

### Model

Let $x_A$ and $x_B$ be the number of units of product $A$ and $B$ that are produced.

We need to maximize

$$ 8x_A + 6x_B $$

subject to the constraints

$$
\begin{aligned}
&2x_A + 2x_B \leq 11 \\

&7x_A + 5x_B \leq 34 \\

&x_A, x_B ≥ 0
\end{aligned}
$$

### Solution using Gurobipy

Using the code below we see that $3.25$ units of product $A$ and $2.25$ units of product $B$ need to be produced to obtain a maximum profit of $£39.5$.

```
import gurobipy as gp
from gurobipy import GRB
# Resources
R = ['Sand', 'Cement']
# Products
P = ['A', 'B']
# resource required by product
product_resource = {
('A', 'Cement'): 2,
('B', 'Cement'): 2,
('A', 'Sand'): 7,
('B', 'Sand'): 5
}
# total resources available
resources_avbl = {
'Cement': 11,
'Sand': 34
}
# profit by product
profit = {
'A': 8,
'B': 6
}
# creating the model
m = gp.Model('RAP')
# adding the decision variables for each product
x = m.addVars(P, name="produce")
# declaring resource constraints
m.addConstrs((sum(x[p]*product_resource[(p, r)] for p in P) <= resources_avbl[r] for r in R), name='resource')
# setting the objective
m.setObjective(x.prod(profit), GRB.MAXIMIZE)
# optimizing the model
m.optimize()
# printing the values of each decision variable
for v in m.getVars():
if v.x > 1e-6:
print(v.varName, v.x)
# printing the value of the objective function
print(f'Total Profit: {m.objVal}')
```

Here is the output from Gurobi

```
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0xe9bff615
Coefficient statistics:
Matrix range [2e+00, 7e+00]
Objective range [6e+00, 8e+00]
Bounds range [0e+00, 0e+00]
RHS range [1e+01, 3e+01]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 1.4000000e+31 3.500000e+30 1.400000e+01 0s
2 3.9500000e+01 0.000000e+00 0.000000e+00 0s
Solved in 2 iterations and 0.01 seconds
Optimal objective 3.950000000e+01
produce[A] 3.25
produce[B] 2.25
Total Profit: 39.5
```