Log In Start studying!

Select your language

Suggested languages for you:
StudySmarter - The all-in-one study app.
4.8 • +11k Ratings
More than 3 Million Downloads
Free
|
|

Formulating Linear Programming Problems

Formulating Linear Programming Problems

Suppose you decide to create a diet chart. You would wish it to contain all the nutrients that are needed for a healthy body, and also would like to minimise the costs involved in the purchase of the food types included. The allocation of nutritional food for each day can be done by formulating it into a linear programming problem (LPP).

What is Linear Programming?

Linear programming problems deal with determining the optimal allocations of limited resources to attain the objectives. Some classical linear programming problems are encountered in manufacturing, diet, and transportation planning.

The resources can be in the form of men, raw materials, money, demand, machines, etc. The objective of the linear programming problem could be maximising profit and utility, minimising the total cost and capital expenditure, etc. There will be certain restrictions on the total amount of available resources and on the quantity or quality of each product made.

A linear programming problem deals with optimising (maximising or minimising) a function. It constitutes three parts: objective function, decision variable and constraints.

The functions which need to be optimised are known as the objective function.

The variables whose values determine the solution of the given problem are called decision variables of the problem.

The set of simultaneous linear equations or inequalities that the problem is subject to are known as constraints.

In Linear programming problems, the term 'linear' refers to the fact that all the variables involved in the objective function and the constraints are linear, that is of degree \(1\) in the problems under consideration. The term 'programming' refers to the process of determining a particular course of action.

Rules in Formulating Linear Programming Problems

The following rules must be applied while formulating a linear programming problem.

  1. There must be a well-defined objective to achieve (maximise or minimise).

  2. There is only a finite number of decision variables.

  3. At least a few of the resources must be in limited supply, which gives rise to constraints.

  4. All the elements should be quantifiable. All the decision variables should assume only non-negative values.

  5. Both the given objective function and constraints must be linear equations or inequalities.

  6. There must be alternative courses of the line of action to choose from.

Mathematical Formulation of Linear Programming Problems

If \(x_i (i=1,2,...,n)\) are the \(n\) decision variables of the problem and if the given system is subject to \(k\) constraints, then the general mathematical model can be written in the form

Optimise \(Z = f(x_1,x_2,...,x_n)\) subject to \(g_i(x_1,x_2,...,x_n) \leq ,=,\geq b_j,(i=1,2,...,k)\)

and \(x_1,x_2,....,x_n \geq 0\)

Let's look at the steps involved in the mathematical formulation of Linear programming problems.

  1. We have to identify the unknown decision variables to be determined and assign symbols to them.

  2. After that identify the objective or aim and represent it also as a linear function of the decision variables.

  3. Next, you need to identify all the restrictions or constraints in the given problem and express those restrictions or constraints as linear equations or inequalities of decision variables.

  4. Express the complete formulation of the Linear Programming Problem as a mathematical model consisting of the objective and constraints.

Steps in Formulating Linear Programming Problems

The below steps are used in formulating the Linear Programming Problems mathematically.

Step 1: Firstly, for the optimisation of the function, identify all the number of decision variables that govern the behaviour of the objective function. Let's represent it by '\(n\)'.

Step 2: Secondly, you need to identify the set of constraints on the decision variables. You will need to express them through linear equations or inequation form. This will help you to set up your region in the \(n\)-dimensional space in which your objective function needs to be optimised. Please note the condition of non-negativity on the decision variables, that is, all of them should be positive as the problem might represent a real-world scenario, and such variables can’t be negative.

Step 3: Now express the objective function in the form of a linear equation or inequations in the decision variables.

Step 4: Finally, optimise the objective function mathematically.

Linear Programming Problem Formulation Examples

A factory manufactures two types of products \(S\) and \(T\) and sells them at a profit of \($2\) on type \(S\) and \($3\) on type \(T\). Each product is processed on two machines \(M_1\) and \(M_2\). Type \(S\) requires \(1\) minute of processing time on \(M_1\) and \(2\) minutes on \(M_2\). Type \(T\) requires \(1\) minute on \(M_1\) and 1 minute on \(M_2\). Machine \(M_1\) is available for not more than \(6\) hours \(40\) minutes while machine \(M_2\) is available for \(10\) hours during any working day. Formulate the problem as an LPP so as to maximise the profit.

Solution:

Let the factory decide to produce \(x_1\) units of product \(S\) and \(x_2\) units of product \(T\) to maximise its profit.

To produce these units of type \(S\) and type \(T\) products it requires \(x_1+x_2\) processing minutes on \(M_1\) and \(2x_1+x_2\) processing minutes on \(M_2\). Since machine \(M_1\) is available for maximum \(6\) hours \(40\) minutes and \(M_2\) is available for maximum \(10\) hours doing any working day, the constraints are

\[x_1+x_2 \leq 400,\] \[2x_1+x_2 \leq 600,\] and \[x_1,x_2 \geq 0.\]

Since the profit from type \(S\) is \($2\) and the profit from type \(T\) is \($3\), the total profit is \(2x_1+3x_2\). As the objective is to maximise the profit, the objective function is to maximise \(Z=2x_1+3x_2\).

The complete formulation of the LPP is \(\text {Maximise}\, Z=2x_1+3x_2\) subject to the constraints

\[x_1+x_2\leq 400,\]

\[2x_1+x_2\leq 600,\]

and \[x_1,x_2 \geq 0.\]

Let's look into one more problem.

A company produces smartwatches and flagship phones. The company's projections indicate an expected demand for at least \(200\) flagship phones and \(140\) smartwatches each day. Because of a few limitations in the production department, no more than \(300\) flagship phones and \(180\) smartwatches can be made daily.

In order to facilitate the shipping contract, a minimum of \(240\) goods must be shipped each day. If each flagship phone sold, results in a \($10\) loss, but each smartwatch produced a \($20\) profit; then how many of each type of smartwatches and flagship phones should be manufactured daily to maximise the net profit?

Solution:

Let's solve the given linear programming problem as per the steps involved.

Step 1: You have to find the decision variables. You have been asked to optimise the number of smartphones and flagship phones produced by the company. These will be your decision variables in the given problem.

Let \(x=\)Number of flagship phones produced and \(y=\)Number of smartphones produced

Therefore \(x\) and \(y\) are the two decision variables in the given problem.

Step 2: Now you have to take care of constraints. Since the company cannot produce a negative number of flagship phones and smartwatches, the obvious constraints would be \[x \ge 0,\] and \[y \ge 0.\] In the given problem, the lower bound for the company to sell their smartwatches and flagship phones are given. You can write them as \[x \ge 200,\] and \[y \ge 140.\] The upper bounds for these manufacturing considering the limitations from the production department are also given. You can write them as \[x \le 300,\] and \[y \le 180.\] Also, you have the joint constraint for both smartwatches and flagship phones due to the shipping. contract as \[x+y \ge 240.\]

Step 3: Now consider the objective function. You have to optimise the net profit function. It is given as \[P=-10x+20y.\]

Step 4: Final step is to solve the problem.

\[\text {Maximise}\, P=-10x+20y \]

subject to \[200 \le x \le 300,\] \[140 \le y \le 180,\] and \[x+y \ge 240.\]

Let's see one more real-life scenario.

Dave wants to decide the constituents of his diet that fulfill his daily requirements of proteins, fat, and carbohydrates at the minimum cost. He gets these nutrients from four different foods. The yields per unit of his food are given in the following table.


Food typeYield/unitProteinsYields/unitFatsYields/unitCarbohydratesCost/unit$
\[1\]\[3\]\[2\]\[6\]\[2\]
\[2\]\[4\]\[2\]\[4\]\[1\]
\[3\]\[8\]\[7\]\[7\]\[5\]
\[4\]\[6\]\[5\]\[4\]\[3\]
Minimum requirement\[900\]\[200\]\[700\]

Formulate the Linear Pogramming model for the problem.

Solution:

Let \(x_1,x_2,x_3\) and \(x_4\) be the units of food of type \(1\), \(2\), \(3\), and \(4\) used respectively.

From these units of food of types \(1\), \(2\), \(3\) and \(4\) he requires

\[3x_1+4x_2+8x_3+6x_4\, \text{Proteins/day},\]

\[2x_1+2x_2+7x_3+5x_4\, \text{Fats/day and}\]

\[6x_1+4x_2+7x_3+4x_4\, \text{Carbohydrates/day}.\]

Since the minimum requirement of these proteins, fats, and carbohydrates are \(900\), \(200\), and \(700\) respectively, the constraints are

\[3x_1+4x_2+8x_3+6x_4 \geq 900,\] \[2x_1+2x_2+7x_3+5x_4 \geq 200,\] \[6x_1+4x_2+7x_3+4x_4 \geq 700,\]

and \[x_1,x_2,x_3,x_4 \geq 0.\]

Since, the cost of this food of type \(1\), \(2\), \(3\) and \(4\) are \($2\), \($1\), \($5\) and \($3\) per unit, the total cost is \(2x_1+x_2+5x_3+3x_4\, $\). As the objective is to minimise the total cost, the objective function is

\[\text {Minimise}\, Z=2x_1+1x_2+5x_3+3x_4.\]

The complete formulation of the LPP is

\[\text {Minimise}\, Z=2x_1+1x_2+5x_3+3x_4\]

subject to

\[3x_1+4x_2+8x_3+6x_4 \geq 900,\]

\[2x_1+2x_2+7x_3+5x_4 \geq 200,\]

\[6x_1+4x_2+7x_3+4x_4 \geq 700,\] and \[x_1,x_2,x_3,x_4 \geq 0.\]

Formulating Linear Programming Problems - Key takeaways

  • Linear programming problems deal with determining the optimal allocations of limited resources to attain the objectives.
  • Three steps in formulating linear programming problems are finding the decision variables, objective function, and constraints.
  • The variables whose values determine the solution of the given problem are called decision variables of the problem.
  • The functions which need to be optimised are known as the objective function. The set of simultaneous linear equations or inequalities that the problem is subject to are known as constraints.
  • Limitations: It can deal with only single objective problems, all the functions involved can only be linear and decision variables can assume only non-negative values.

Frequently Asked Questions about Formulating Linear Programming Problems

You formulate a linear programming problem by identifying the objective function, decision variables and the constraints.

A linear programming problem deals with optimizing (maximising or minimising) a function. Some classical linear programming problems are encountered in manufacturing, diet planning, and transportation planning.  

The first step in formulating a linear programming problem is identifying the objective function which is to be maximised or minimised.

Without a model formulation, the aim, and constraints in achieving the goal are not obvious. 

Final Formulating Linear Programming Problems Quiz

Question

What is a linear programming problem?

Show answer

Answer

A linear programming problem deals with optimising (maximising or minimising) a function.

Show question

Question

What are the three constituents of a linear programming problem?

Show answer

Answer

Objective function, decision variable and constraints.

Show question

Question

Is happiness a valid quantity for a linear programming problem?

Show answer

Answer

No. Only quantifiable quantities elements can be included in a linear programming problem.

Show question

Question

Can the expression \(x^2\) be an objective function in a linear programming problem? 

Show answer

Answer

No. Objective function and constraints in a linear programming problem must be linear equations or inequalities. 

Show question

Question

A firm manufactures two types of products, A and B and sells them at a profit of $2 on type A and $3 on type B. What would be the objective of a linear programming problem which has to maximise the profit?

Show answer

Answer

Maximise \(2x_1+3x_2\)

Here, \(x_1\) denotes the units of product A and \(x_2\) the units of product B.

Show question

Question

A firm manufactures two types of products, A and B and sells them at a profit of $2 on type A and $3 on type B. What are the decision variables of a linear programming problem which has to maximise the profit?

Show answer

Answer

The firm has to decide how many units of products A and B are to be manufactured to maximise its profit. So, they are the decision variables.

Show question

Question

A person wants to decide the constituents of a diet which will fulfill his daily requirements of proteins, fat, and carbohydrates at the minimum cost. The choice is to be made from four different types of foods. What are the decision variables for this optimisation problem?

Show answer

Answer

The units of food of type 1, 2, 3, and 4 to be consumed to maintain the desired diet are the decision variables.

Show question

Question

What is the function to be optimised in a linear programming problem called?

Show answer

Answer

Objective function

Show question

Question

David wants to optimise his travel route from his house to work. There is only one roadway connecting his house and workplace. Can this be formulated as a linear programming problem?

Show answer

Answer

No. There must be alternative courses of the line of action to choose from. 

Show question

Question

Which of the following inequality or expression cannot be in a linear programming problem?

Show answer

Answer

\(x_1^3+x_2\)

Show question

Question

Which of the following inequality can be in a linear programming problem?

Show answer

Answer

\(x_1+3x_2 \leq 20\)

Show question

Question

True/False: The objective functions and constraints in a linear programming problem must be linear equations or inequalities.

Show answer

Answer

True.

Show question

Question

Which of the following is not a constituent of a linear programming problem?

Show answer

Answer

Cubic term.

Show question

Question

What are the limitations of Linear Programming Problems?

Show answer

Answer

It can deal with only single objective problems, all the functions involved can only be linear and decision variables can assume only non-negative values.

Show question

Question

Can the expression \(x-2\) be an objective function in a linear programming problem? 

Show answer

Answer

Yes.

Show question

More about Formulating Linear Programming Problems
60%

of the users don't pass the Formulating Linear Programming Problems quiz! Will you pass the quiz?

Start Quiz

Discover the right content for your subjects

No need to cheat if you have everything you need to succeed! Packed into one app!

Study Plan

Be perfectly prepared on time with an individual plan.

Quizzes

Test your knowledge with gamified quizzes.

Flashcards

Create and find flashcards in record time.

Notes

Create beautiful notes faster than ever before.

Study Sets

Have all your study materials in one place.

Documents

Upload unlimited documents and save them online.

Study Analytics

Identify your study strength and weaknesses.

Weekly Goals

Set individual study goals and earn points reaching them.

Smart Reminders

Stop procrastinating with our study reminders.

Rewards

Earn points, unlock badges and level up while studying.

Magic Marker

Create flashcards in notes completely automatically.

Smart Formatting

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.

Get FREE ACCESS to all of our study material, tailor-made!

Over 10 million students from across the world are already learning smarter.

Get Started for Free
Illustration