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