LJR Excelencia logo
LJR Excelencia
Think · Excel · Model

Linear Programming Modelling

Worked example: a firm produces three construction materials — concrete, mortar and grout — each consuming a limited resource of labour, blending time and storage. We compute the optimal production strategy using the Simplex method.

Resource table

ResourceConcreteMortarGroutAvailability
Labour1 hr2 hr2 hr20 hr
Blending time2 hr1 hr2 hr20 hr
Storage2 m³2 m³1 m³20 m³
Sales price$20$30$40—
Manufacturing cost$10$18$28—

Optimisation problem

max⁡x1,x2,x3  10x1+12x2+12x3s.t. x1+2x2+2x3≤20    2x1+x2+2x3≤20    2x1+2x2+x3≤20    x1,x2,x3≥0\begin{aligned} & \max_{x_1,x_2,x_3} \; 10x_1+12x_2+12x_3 \\ & \text{s.t. } x_1+2x_2+2x_3\le 20 \\ & \quad\;\; 2x_1+x_2+2x_3\le 20 \\ & \quad\;\; 2x_1+2x_2+x_3\le 20 \\ & \quad\;\; x_1,x_2,x_3\ge 0 \end{aligned}

After putting the problem in standard form we have:

min⁡x1,…,x6  −10x1−12x2−12x3s.t. x1+2x2+2x3+x4=20    2x1+x2+2x3+x5=20    2x1+2x2+x3+x6=20    x1,x2,x3,x4,x5,x6≥0\begin{aligned} & \min_{x_1,\dots,x_6} \; -10x_1-12x_2-12x_3 \\ & \text{s.t. } x_1+2x_2+2x_3+x_4=20 \\ & \quad\;\; 2x_1+x_2+2x_3+x_5=20 \\ & \quad\;\; 2x_1+2x_2+x_3+x_6=20 \\ & \quad\;\; x_1,x_2,x_3,x_4,x_5,x_6\ge 0 \end{aligned}

Simplex method (outline)

  1. Identify an initial feasible basis {xB1,…,xBm}\{x_{B1},\dots,x_{Bm}\}.
  2. Compute reduced costs cˉk=ck−cBB−1Ak\bar c_k=c_k-c_B B^{-1}A_k for each non-basic variable.
  3. If all reduced costs are non-negative, the current basis is optimal — STOP.
  4. Otherwise, pick a non-basic xkx_k with negative reduced cost to enter the basis.
  5. Set xk=min⁡iΔxix_k=\min_i \Delta x_i.
  6. Return to step 2.

Simplex tableau — outline by inspection

By inspection, a feasible basis is {x4,x5,x6}\{x_4,x_5,x_6\}, which corresponds to the extreme point (0,0,0,20,20,20)(0,0,0,20,20,20). We have

B=[100010001]B=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}

Therefore B−1=BB^{-1}=B and the reduced cost vector is

cˉ=c−cBB−1A=[−10−12−12000]−[000][100010001][122100212010221001]=[−10−12−12000]\bar c = c - c_B B^{-1}A = \begin{bmatrix}-10&-12&-12&0&0&0\end{bmatrix} - \begin{bmatrix}0&0&0\end{bmatrix}\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&2&2&1&0&0\\2&1&2&0&1&0\\2&2&1&0&0&1\end{bmatrix} = \begin{bmatrix}-10&-12&-12&0&0&0\end{bmatrix}

The reduced cost of x1x_1 is negative, so we choose it to enter the basis. We calculate the change in the existing basic variables:

ΔxB=B−1A1=A1=[122]\Delta x^B = B^{-1}A^1 = A^1 = \begin{bmatrix}1\\2\\2\end{bmatrix}

Checking the ratio test, we see that x4/Δx4=20x_4/\Delta x_4=20, x5/Δx5=10x_5/\Delta x_5=10 and x6/Δx6=10x_6/\Delta x_6=10, so one of x5x_5 and x6x_6 must leave the basis; let's assume that x5x_5 leaves, so the new basis is {x4,x1,x6}\{x_4,x_1,x_6\}. Now

B=[110020021]B−1=[1−0.5000.500−11]B=\begin{bmatrix}1&1&0\\0&2&0\\0&2&1\end{bmatrix}\qquad B^{-1}=\begin{bmatrix}1&-0.5&0\\0&0.5&0\\0&-1&1\end{bmatrix}

The current solution is B−1b=[10  0  0  10  0  0]B^{-1}b=[10\;0\;0\;10\;0\;0] and

cˉ=[−10−12−12000]−[0−100][1−0.5000.500−11][122100212010221001]=[0−7−2050]\bar c = \begin{bmatrix}-10&-12&-12&0&0&0\end{bmatrix} - \begin{bmatrix}0&-10&0\end{bmatrix}\begin{bmatrix}1&-0.5&0\\0&0.5&0\\0&-1&1\end{bmatrix}\begin{bmatrix}1&2&2&1&0&0\\2&1&2&0&1&0\\2&2&1&0&0&1\end{bmatrix} = \begin{bmatrix}0&-7&-2&0&5&0\end{bmatrix}

The reduced cost of x3x_3 is negative, so we choose it to enter the basis. We calculate

ΔxB=B−1A3=[1−0.5000.500−11][211]=[11−1]\Delta x^B = B^{-1}A^3 = \begin{bmatrix}1&-0.5&0\\0&0.5&0\\0&-1&1\end{bmatrix}\begin{bmatrix}2\\1\\1\end{bmatrix} = \begin{bmatrix}1\\1\\-1\end{bmatrix}

Checking the ratio test, we see that x4/Δx4=10x_4/\Delta x_4=10 and x1/Δx1=10x_1/\Delta x_1=10, so one of x4x_4 and x1x_1 must leave the basis; let's assume that x4x_4 leaves, so the new basis is {x3,x1,x6}\{x_3,x_1,x_6\}. Now

B=[210220121]B−1=[1−0.50−1101−1.51]B=\begin{bmatrix}2&1&0\\2&2&0\\1&2&1\end{bmatrix}\quad B^{-1}=\begin{bmatrix}1&-0.5&0\\-1&1&0\\1&-1.5&1\end{bmatrix}

so the current solution is B−1b=[0  0  10  0  0  10]B^{-1}b=[0\;0\;10\;0\;0\;10] and

cˉ=[−10−12−12000]−[−12−100][1−0.50−1101−1.51][122100212010221001]=[0−40240]\bar c = \begin{bmatrix}-10&-12&-12&0&0&0\end{bmatrix} - \begin{bmatrix}-12&-10&0\end{bmatrix}\begin{bmatrix}1&-0.5&0\\-1&1&0\\1&-1.5&1\end{bmatrix}\begin{bmatrix}1&2&2&1&0&0\\2&1&2&0&1&0\\2&2&1&0&0&1\end{bmatrix} = \begin{bmatrix}0&-4&0&2&4&0\end{bmatrix}

The reduced cost of x2x_2 is negative, so we choose it to enter the basis. We calculate

ΔxB=B−1A2=[1−0.50−1101−1.51][212]=[1.5−12.5]\Delta x^B = B^{-1}A^2 = \begin{bmatrix}1&-0.5&0\\-1&1&0\\1&-1.5&1\end{bmatrix}\begin{bmatrix}2\\1\\2\end{bmatrix} = \begin{bmatrix}1.5\\-1\\2.5\end{bmatrix}

Checking the ratio test, we see that x3/Δx3=6.67x_3/\Delta x_3=6.67 and x6/Δx6=4x_6/\Delta x_6=4, so x6x_6 must leave the basis, and the new basis is {x3,x1,x2}\{x_3,x_1,x_2\}. Now

B=[212221122]B−1=[0.40.4−0.6−0.60.40.40.4−0.60.4]B=\begin{bmatrix}2&1&2\\2&2&1\\1&2&2\end{bmatrix}\quad B^{-1}=\begin{bmatrix}0.4&0.4&-0.6\\-0.6&0.4&0.4\\0.4&-0.6&0.4\end{bmatrix}

so the current solution is B−1b=[4  4  4  0  0  0]B^{-1}b=[4\;4\;4\;0\;0\;0] and

cˉ=[−10−12−12000]−[−12−10−12][0.40.4−0.6−0.60.40.40.4−0.60.4][122100212010221001]=[0003.61.61.6]\bar c = \begin{bmatrix}-10&-12&-12&0&0&0\end{bmatrix} - \begin{bmatrix}-12&-10&-12\end{bmatrix}\begin{bmatrix}0.4&0.4&-0.6\\-0.6&0.4&0.4\\0.4&-0.6&0.4\end{bmatrix}\begin{bmatrix}1&2&2&1&0&0\\2&1&2&0&1&0\\2&2&1&0&0&1\end{bmatrix} = \begin{bmatrix}0&0&0&3.6&1.6&1.6\end{bmatrix}

All reduced costs are nonnegative, so the current basis is optimal.

Optimal solution

After iterating the Simplex tableau, the optimal solution is:

x∗=[4    4    4    0    0    0],c⋅x∗=−136x^*=[4\;\;4\;\;4\;\;0\;\;0\;\;0],\qquad c\cdot x^*=-136

i.e. produce 4 tons each of concrete, mortar and grout for maximum profit.

Differential Equation Modelling →Decision Making Tree →