## 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