Linear Programming

Linear Programming Problem and Its Mathematical Formulation

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.

Play
Play
Play
Play
Play
Play
previous arrow
next arrow
previous arrownext arrow
Slider

Browse more Topics under Linear Programming

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.

LPP

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

linear programming problem cheat sheetLinear programming 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.

Share with friends

Customize your course in 30 seconds

Which class are you in?
5th
6th
7th
8th
9th
10th
11th
12th
Get ready for all-new Live Classes!
Now learn Live with India's best teachers. Join courses with the best schedule and enjoy fun and interactive classes.
tutor
tutor
Ashhar Firdausi
IIT Roorkee
Biology
tutor
tutor
Dr. Nazma Shaik
VTU
Chemistry
tutor
tutor
Gaurav Tiwari
APJAKTU
Physics
Get Started

Leave a Reply

avatar
  Subscribe  
Notify of

Download the App

Watch lectures, practise questions and take tests on the go.

Customize your course in 30 seconds

Which class are you in?
No thanks.