Linear programming

Concept 1 : Mathematical modelling

One of the most important applications of mathematics in life is to find a optimal solution for problems. For example, what goods should a shopkeeper buy to get the most amount of profit or what is the optimal combination of food you should eat to get maximum amount of nutrients?

To solve these questions, we need to mathematize them i.e. make equations out of those which can be solved. For example we need to write down how much profit does the shopkeeper get on each good, how much budget does he have, which goods sell more, which goods might go bad etc and then using this data, devise equations which will help us in finding the optimal combination of goods the shopkeeper should buy.

This process of converting a real life problem in a mathematical fashion is called mathematical modelling.

Concept 2 : Linear Programming

As the name suggests, Linear Programming is a method of optimizing a mathematical model which is represent by linear constraints only i.e. it does not contain any second order terms. Only equations of form $a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}......=a_{0}$are allowed where $a_{n}$are constants and $x_{n}$are variables.

Concept 2 : Finding optimal solutions

Now we will solve a real life optimization problem using linear programming.

Question

One kind of cake (Cake A) requires 200g of flour and 25g of fat, and another kind of cake (Cake B) requires 100g of flour and 50g of fat. Find the maximum number of cakes which can be made from 5kg of flour and 1 kg of fat assuming that there is no shortage of the other ingredients used in making the cakes. (From NCERT)

Let $x$be the number of cake A and $y$be the number of cake B.

According to the question we have to maximize $x+y$in limited number of ingredients (5 kg flour and 1 kg fat)

Before moving ahead we should set a baseline. We know that $x$and $y$cant be less than 0.

Hence $x,y\geq 0$

For flour :

$200x+100y\leq 5000$

What this basically means is that if we make $x$cake A , we will use $200x$grams of flour. Similarly for $y$ cake B, we will use $100y$ grams of flour. The total flour used in all the cakes should be less than 5000g.

Similarly for fat :

$25x+50y\leq 1000$

Now we have four linear inequalities. There are multiple ways to solve these inequalities. The method we will look here is the graphical method which is easier to visualize and understand.

Activity

Plot the following inequalities on geogebra.

$x\geq 0$

$y\geq 0$

$200x+100y\leq 5000$

$25x+50y\leq 1000$

Download this geogebra file from this link.

The area in which all the colors are overlapping represents the region where all these inequalities are satisfied.

Activity

Plot the area in which all the four inequalities overlap and plot all the vertices of the resulting polygon.

Download this geogebra file from this link.

Solution

Now we have four bounds of this polygon inside of which all the four inequalities are satisfied. All we need to do now is find a point in this set, where $x+y$is maximised.

Simply looking at the the second plot, we can see that at A , $x+y$= 0, at C its 20, at D its 25 and finally at B its 30.

This gives us our solution that x = 20 and y = 30 .

What this means in real life is that if the baker bakes 20 of the first type of cakes and 30 of the second type, they will end up with the most possible amount of cakes using 5kg flour and 1kg fat.

Recap

From above we can conclude that solving a optimisation problem using linear programming has following steps:

• Make a system linear inequalities using the constrains of the real life scenario. (For example we only had 5kg flour and 1kg fat and we used it to device the model)
• Plot the system of linear inequalities
• Plot the area which contains all the points that satisfy the inequalities.
• Among those points, find the point which maximizes or minimizes the the variables (depending on your need). This point will always be one of the vertex of the polygon plotted by the linear equations. For example in our question, it was the vertex B(20,10) which maximized $x+y$
• And you are done!