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 first method we will look at 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.

Observation

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