Difference between revisions of "Linear programming"

From Karnataka Open Educational Resources
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{Geogebra|qvjg3ntd}}
 
 
 
== Concept 1 : Mathematical modelling ==
 
== 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?   
 
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?   
Line 39: Line 37:
 
<math>25x + 50y \leq 1000</math>
 
<math>25x + 50y \leq 1000</math>
  
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.  
+
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 ====
 
==== Activity ====
Line 52: Line 50:
 
<math>25x + 50y \leq 1000</math>
 
<math>25x + 50y \leq 1000</math>
  
Geogebra file : https://www.geogebra.org/calculator/qvjg3ntd
+
{{Geogebra|shvcc7wh}}
  
 
The area in which all the colors are overlapping represents the region where all these inequalities are satisfied.  
 
The area in which all the colors are overlapping represents the region where all these inequalities are satisfied.  
[[File:Linear programming question 1.png|Geogebra plot|center|frameless|777x777px]]
 
 
 
==== Activity ====
 
==== Activity ====
 
Plot the area in which all the four inequalities overlap and plot all the vertices of the resulting polygon.  
 
Plot the area in which all the four inequalities overlap and plot all the vertices of the resulting polygon.  
  
Geogebra file : https://www.geogebra.org/calculator/qvjg3ntd
+
{{Geogebra|qvjg3ntd}}
 +
 
 +
==== 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 <math>x+y</math>is maximised. 
 +
 
 +
Simply looking at the the second plot, we can see that at A , <math>x+y</math>= 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''''' .  
  
[[File:Linear Programming plot 2 .png|center|frameless|700x700px]]
+
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.  
  
==== Observation ====
+
== Recap ==
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 <math>x+y</math>is maximised.
+
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 <math>x+y</math>
 +
* And you are done!
  
Simply looking at the
+
== Additional Material ==
 +
{{Youtube
 +
| 1 = K7TL5NMlKIk
 +
}}{{Youtube|Bzzqx1F23a8
 +
}}

Latest revision as of 10:52, 17 June 2022

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 are allowed where are constants and 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 be the number of cake A and be the number of cake B.

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

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

Hence

For flour :

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

Similarly for fat :

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.


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 is maximised.

Simply looking at the the second plot, we can see that at A , = 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
  • And you are done!

Additional Material