# Modeling using Linear Programming

Optimization using linear models.
linear programming
mathematical programming
Published

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

# 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