Why are linear models so ubiquitous? Firstly they are relatively easy to understand and implement. They are based on a well founded mathematical theory, developed around the mid 1700's and later played a pivotal role in the development of the digital computer. Computers are uniquely tasked implement linear programs because computers were conceptualised largely on basis of the theory of linear programming. Linear functions are always convex meaning it has only one minima. Linear programming (LP) problems are usually solved using the *simplex * method. Suppose we want to solve the optimisation problem:

*max* *x _{1} + x_{2 }*with constraints: 2

*x*x

_{1}+_{2}

*≤*4

*and:*

*x*2

_{1}+*x*3

_{2 }≤We assume *x _{1} *and

*x*are greater than or equal to 0. The first thing we need to do is convert it to the

_{2}*standard form*. This is done by ensuring the problem is a maximisation problem, that is convert min z to max - z. We also need to convert the inequalities to equalities by adding non negative

*slack*variables. The example here already a maximisation problem so we can leave our objective function as it is. We do need to change the inequalities in the constraints to equalities:

2*x _{1} *+

*x*

_{2}_{ }+

*x*= 4 and :

_{3}*x*+ 2

_{1}*x*+

_{2}*x*= 3

_{4}If we let * z *denote the value of the objective function we can then write:

*z* – *x _{1}* –

*x*= 0

_{2}We now have the following system of linear equations.

Objective: z – *x _{1}* –

*x*+ 0 + 0 = 0

_{2 } Constraint 1: 2*x _{1}* +

*x*+

_{2}*x*+ 0 = 4

_{3}* * Constraint 2:* x _{1}+ *2

*x*0

_{2}+*+ x*3

_{4 }=Our objective is to maximise *z* remembering that all variables are non negative. We can see that *x _{1}* and

*x*appear in all the equations and are called

_{2 }*non basic*.

*x*and

_{3}*x*only appear in one equation each. They are called basic variables. We can find a basic solution by assigning all non basic variables to 0. Here this gives us:

_{4}*x _{1 }* =

*x*0 ;

_{2}=*x*= 4 ;

_{3}*x*= 3 ; z = 0.

_{4 }Is this an optimum solution remembering that our goal is to maximise *z? *We can see that since *z *subtracts *x _{1}* and

*x*in the first equation in our linear system we are able to increase these variables. If the coefficients in this equation were all non negative then there would be no way to increase

_{2}*z*. Remember

*x*So we will know that we have found an optimum solution when all coefficients in the objective equation are positive.

_{1 }≥ 0,_{ }x_{2 }≥ 0,_{ }x_{3 }≥ 0_{ , }x_{4 }≥ 0.This is not the case here. So we take one of the non basic variables with a negative coefficient in the objective equation, say, *x _{1}*, called the

*entering*variable, and use a technique called

*pivoting*to turn it from a non basic to a basic variable. At the same time we will change a basic variable, called the

*leaving*variable, into a non basic. We can see that

*x*appears in both the constraint equations so which one do we choose to pivot? Remembering we need to keep the coefficients positive. We find that by using the pivot element that yield the lowest ratio of right hand side of the equations to their respective entering coefficients then we can find another basic solution. For

_{1}*x*in this example this gives us 4/2 for the first constraint and 3/1 for the second. So we will pivot using

_{1}*x*in constraint 1.

_{1}We divide constraint one by 2 and this gives:

*x _{1 }+ *½

*x*½

_{2 }+*x*2

_{3 }=We can now write this in terms of *x _{1 }* and substitute it into the other equations to eliminate

*x*from these equations. Once we have performed a bit of algebra we end up with the following linear system.

_{1 }*z –* 1/2*x _{2}* + 1/3

*x*= 2

_{3}*x _{1 }+ *1/2

*x*1/2

_{2 }+*x*2

_{3 }=3/2*x _{2}* – 1/2

*x*+

_{3}*x*= 1

_{4 }We have another basic solution. Is this the optimal solution? Since we still have a minus coefficient in the first equation, the answer is no. We can now go through the same pivot process with *x _{2}* and using the ratio rule we find we can pivot on 3/2

*x*in the third equation. This gives us:

_{2 }*z *+ 1/3*x _{3}* + 1/3

*x*

_{4 }_{ }= 7/3

*x _{1}* + 2/3

*x*– 1/3

_{3 }*x*= 5/3

_{4}x_{2 }– 1/3*x _{3 }*

_{ }+ 2/3

*x*= 2/3

_{4}This gives us the solution of *x _{3 }*=

*x*= 0 ;

_{4 }*x*= 5/3 ; x

_{1 }_{2 }

*=*2/3

*; and*

*z*= 7/3. This is the optimal solution because there are no more negatives in the first equation.

We can visualise this with a graph. The shaded area is the region where we will find a feasible solution.