Sometimes one seeks to optimize (maximize or minimize) a known function (could be profit/loss or any output), subject to a set of linear constraints on the function. Linear Programming Problems (LPP) provide the method of finding such an optimized function along with/or the values which would optimize the required function accordingly.
Browse more Topics under Linear Programming
- Different Types of Linear Programming Problems
- Graphical Method of Solving Linear Programming Problems
It is one of the most important Operations Research tools. It is widely used as a decision making aid in almost all industries. There can be various fields of application of LPP, in the areas of Economics, Computer Sciences, Mathematics, etc. Since it is a very important topic with numerous practical applications, we will proceed slowly in building up this topic and making it very clear to you. So, let’s begin!
Suggested Videos on Linear Programming
.embed-container { position: relative; padding-bottom: 56.25%; height: 0; overflow: hidden; max-width: 100%; } .embed-container iframe, .embed-container object, .embed-container embed { position: absolute; top: 0; left: 0; width: 100%; height: 100%; }
Mathematical Formulation
Formulation of an LPP refers to translating the real-world problem into the form of mathematical equations which could be solved. It usually requires a thorough understanding of the problem.
Steps towards formulating a Linear Programming problem:
- Step 1: Identify the ‘n’ number of decision variables which govern the behaviour of the objective function (which needs to be optimized).
- Step 2: Identify the set of constraints on the decision variables and express them in the form of linear equations /inequations. This will set up our region in the n-dimensional space within which the objective function needs to be optimized. Don’t forget to impose the condition of non-negativity on the decision variables i.e. all of them must be positive since the problem might represent a physical scenario, and such variables can’t be negative.
- Step 3: Express the objective function in the form of a linear equation in the decision variables.
- Step 4: Optimize the objective function either graphically or mathematically.
Now let us look at an example aimed at enabling you to learn how to formulate a problem in Linear Programming!
Download Linear Programming Problem Cheat Sheet
Solved Examples for You
Question 1: A calculator company produces a handheld calculator and a scientific calculator. Long-term projections indicate an expected demand of at least 150 scientific and 100 handheld calculators each day. Because of limitations on production capacity, no more than 250 scientific and 200 handheld calculators can be made daily.
To satisfy a shipping contract, a minimum of 250 calculators must be shipped each day. If each scientific calculator sold, results in a 20 rupees loss, but each handheld calculator produces a 50 rupees profit; then how many of each type should be manufactured daily to maximize the net profit?
Answer
Such word problems can be very tricky to solve if not formulated properly. Hence, let us approach it in a step by step manner as discussed above.
Step 1: The decision variables: Since the question has asked for an optimum number of calculators, that’s what our decision variables in this problem would be. Let,
x = number of scientific calculators produced
y = number of handheld calculators produced
Therefore, we have 2 decision variables in this problem, namely ‘x’ and ‘y’.
Step 2: The constraints: Since the company can’t produce a negative number of calculators in a day, a natural constraint would be:
x ≥ 0
y ≥ 0
However, a lower bound for the company to sell calculators is already supplied in the problem. We can note it down as:
x ≥ 150
y ≥ 100
We have also been given an upper bound for these variables, owing to the limitations on production by the company. We can write as follows:
x ≤ 250
y ≤ 200
Besides, we also have a joint constraint on the values of ‘x’ and ‘y’ due to the minimum order on a shipping consignment; given as:
x + y ≥ 250
Step 3: Objective Function: Clearly, here we need to optimize the Net Profit function. The Net Profit Function is given as:
P = -20x + 50y
Step 4: Solving the problem: the system here –
Maximization of P = -20x + 50y, subject to:
150 ≤ x ≤ 250
100 ≤ y ≤ 200
x + y ≥ 250
We can solve it graphically or mathematically as per convenience. We will discuss it in later sections. This completes the discussion on the mathematical formulation of a Linear Programming problem!
Question 2: What is meant by LPP?
Answer: The full form of LPP is Linear Programming Problems. This method helps in achieving the best outcome in a mathematical model. The best outcome could be maximum profit or the lowest cost or the best possible price. The representation of this model’s requirements is by linear relationships.
Question 3: Explain how one can calculate LPP?
Answer: In order to calculate LPP, one must follow the following steps:
- Formulate the LP problem.
- Construct a graph and then plot the various constraint lines.
- Ascertain the valid side of all constraint lines.
- Identify the region of feasible solution.
- Plot the objective function.
- Finally, find out the optimum point.
Question 4: What are the various advantages of LPP?
Answer: The various advantages of LPP are as follows:
- Utilized for analyzing numerous military, social, economic social, and industrial problems.
- Linear programming is appropriate for solving complex problems.
- It assists in productive management of an organization for better outcomes.
Question 5: Who is credited with the development of LPP?
Answer: George B Dantzig, a famous mathematician is credited with the development of LPP.
Leave a Reply