Linear Programming Problems (LPP): Formulas and Real-World Examples With Solutions

Linear programming problems (LPP) are mathematical techniques used to optimize outcomes while adhering to constraints. These problems help solve resource allocation, cost reduction, and profit maximization challenges across industries such as logistics, manufacturing, and finance. 

By converting real-world situations into mathematical models, LPP provides precise and effective solutions. This blog explains the key formulas, fundamental concepts, and practical examples of LPP, along with solutions, to demonstrate how it simplifies complex decision-making.

Understanding Linear Programming Problems (LPP): Importance and Key Terminologies

Linear Programming Problems (LPP) are used in various industries, including logistics, manufacturing, and finance, to optimize resource allocation and maximize profit while adhering to constraints like cost, time, and capacity. These problems aim to optimize a particular outcome, such as cost, profit, or resource allocation while considering specific limitations like resources, time, or budget.

This technique is important because it helps businesses solve complex problems by providing optimal solutions that satisfy multiple constraints simultaneously. For example, a company may want to maximize profit while considering constraints like material availability, labor hours, or production capacity.

Based on constraints or objectives, linear programming problems (LPP) can be divided into four types:

• Maximization Problem: The aim is to maximize a linear function, commonly seen in profit optimization scenarios.

  Example: A marketing company can maximize its profits without increasing budgets or changing the maximum working hours.

• Minimization Problem: The objective is to minimize a linear function, often used in cost reduction or loss minimization.

  Example: A logistics company can use linear programming to determine the most efficient routes and minimize transportation costs, reducing its operational expenses.

• Standard Form: This refers to LPPs where all constraints are written as less than or equal to inequalities, and the objective function is to be maximized.

  Example: A restaurant chain can maximize its revenue by offering the most profitable combination of dishes on the menu.

• Canonical Form: In this form, all constraints are equalities, and the decision variables are non-negative.

  Example: Optimizing operations of a resort by reducing costs on cleaning, while meeting exact room booking targets.

By understanding the core principles and types of problems in linear programming, businesses can improve operational efficiency and make data-driven decisions. However, to solve these problems, you need to understand the common terminologies used. Let’s explore them in the following section.

Common Terminologies Used in Linear Programming Problem

Understanding terminologies used in linear programming problems, such as decision variables, the objective function, and constraints, will ensure you solve the problem effectively.

Here are the variables used to solve problems in linear programming.

1. Decision Variables
Decision variables are the variables that represent the choices or quantities that can be controlled and adjusted in order to achieve the desired objective. For example, in a production scenario, decision variables might represent the number of units of different products to produce.

Example: Let x₁ represent the number of units of Product A to produce, and x2represent the number of units of Product B.

2. Objective Function
The objective function describes the goal of the optimization. The objective could represent profit, cost, time, or any other measurable factor. The objective function maximizes profits, such as maximizing revenue from product sales based on decision variables like price or quantity.

Example: A typical objective function might look like:

Here, Z could represent profit, and the goal is to maximize profit by adjusting the number of units x₁ and x₂​ produced.

3. Constraints
Constraints are the limitations or restrictions representing available resources, time, budget, or capacity. In mathematical terms, constraints are usually expressed as inequalities or equations involving decision variables. 

For instance, a factory may have constraints on the amount of raw materials or labor hours available for production.

Example: A constraint could be:

This constraint could represent a limitation on resources (e.g., material availability), indicating that the combined use of resources for both products must not exceed 100 units.

4. Non-Negativity Restrictions
The values of decision variables in linear programming problems cannot be less than zero because negative quantities of products, resources, or time are not feasible in real-world scenarios. 

For instance, a transport company allocating a number of trucks to deliver goods cannot give a negative number of trucks.

Example:

These restrictions ensure that the decision variables give feasible and realistic solutions (e.g., you can’t produce a negative number of units).

5. Additional Characteristics

• Finiteness: A solution is considered feasible if it satisfies all constraints, including non-negativity, and lies within the feasible region. For instance, a food delivery service can minimize delivery time by ensuring that all routes respect time limits and capacity constraints.
• Linearity: The objective function and the constraints can only involve linear terms of the decision variables, and there are no exponents or products of decision variables. For instance, the number of units produced in a factory will directly contribute to an increase in profits.

Example:

The objective function and constraints are linear if they involve only terms such as

but not terms like

Also Read: What is Linear Programming in Data Science: Overview

upGrad’s Exclusive Data Science Webinar for you –

ODE Thought Leadership Presentation

Now that you’ve seen the common terminologies involved in solving a linear programming problem, let’s explore the different methods involved in solving these problems.

Linear Programming Methods: An Overview

The simplex method and graphical method are the two most common methods used for solving linear programming problems. Each method has its own approach and application, depending on the complexity and the number of variables in the problem.

Here’s how problems in linear programming are solved using these two methods.

Simplex Method:

This method is used when there are multiple decision variables and constraints. It traverses from one feasible solution to another, always improving the objective function until it reaches the optimal solution.

For instance, an NGO might use the Simplex Method to optimize the distribution of its limited funds across various community programs.

To understand the steps in detail, consider the following example.

Steps Involved:

1. Creating the Simplex Table:

Convert the inequalities into equalities by introducing slack variables. The constraints become:

where s₁ and s₂ are the slack variables.

Here, -3 and -2 are negative of the original coefficients of the objective function.

2. Pivot Element Calculation:

To start the iteration, identify the pivot column, which is the column with the most negative value in the objective row (for maximization problems). In this case, x1x_1x1​ has the most negative coefficient (-3), so it enters the basis.

Now, calculate the ratios for each row to determine the pivot row:

• Row 1: 10/2 = 5
• Row 2: 8/1 = 8

The smallest ratio is 5, which corresponds to Row 1. Thus, x₁ will replace s_1​ in the basis.

3. Iterative Optimization Process:

Perform row operations to make the pivot element equal to 1 and adjust the rest of the table accordingly.

Repeat the process until there are no negative values left in the objective row, which indicates that the optimal solution has been reached.

After the next iteration, the Simplex method gives the optimal solution:

x₁= 5 and x₂= 0, and the maximum value of Z = 15.

Graphical Method:

The Graphical Method is a visual approach to solving linear programming problems, useful when the problem has only two decision variables. It plots the constraints and identifies the feasible region, then finds the optimal solution at one of the corner points.

For instance, a marketing company might use the Graphical Method to optimize ad budgets based on constraints.

Here’s an example to understand the workings of the graphical method.

Example:

Steps Involved:

1. Graphical Representation:

Plot the constraint lines on a graph by converting inequalities into equalities:

These lines will intersect the axes, and the feasible region is the overlapping area that satisfies all constraints.

2. Finding Feasible Regions and Corner Points:

Identify the feasible region that satisfies all the constraints. It is formed by the intersection of the constraint lines and the axes.

The corner points (vertices) of the feasible region are the key points where the optimal solution could lie.

When you plot this on the graph, you get the following corner points: (0,6), (2,4), (4, 0).

3. Calculating Maxima/Minima for the Objective Function:

Calculate the value of the objective function at each corner point:

• At (0,6), Z = 4(0)+3(6) = 18
• At (2,4), Z = 4(2)+3(4) = 14
• At (4,0), Z = 4(4)+3(0) = 16

The maximum value of Z occurs at the corner point (0,6) with Z = 18.

Also Read: Linear Programming Projects Ideas & Topics For Beginners 2025

Now that you’ve seen how to solve a linear programming problem using simplex and graphical methods, let’s explore the formulas and techniques involved in solving such problems.

Essential Formulas and Components To Solve Linear Programming Problems

Knowledge of formulas and techniques is essential for solving real-world linear programming problems in fields such as operations research, economics, and logistics. 

Here are the main components involved in solving problems in linear programming.

1. General Formula

The general formula of linear programming can be represented as:

Maximize (or Minimize)

Where:

• Z is the objective function value (profit, cost, etc.).
• $c_1,c_2,c_3,c_4,...,c_n$ are the coefficients that represent the contribution of each decision variable to the objective function.
• x₁,x₂,. . .x_n​ are the decision variables

2. Objective Function

This is the equation that represents the goal of the optimization problem, whether it's maximizing profit or minimizing cost. It is represented using the following formula:

Z=ax+by

Where,  

a and b and coefficients

x and y are decision variables

3. Constraints

Constraints limit the values the decision variables can take. These are linear equations or inequalities that represent limitations like resource availability, budget, or time. They can be represented in the form of:

4. Non-Negativity Restrictions

Since decision variables in real-world problems (like quantities) can't be negative, LP problems have non-negativity constraints. This ensures that the variables are greater than or equal to zero.

5. Decision Variables

The variables represent the unknown quantities that need to be optimized. The coefficients in the objective function and constraints reflect the relationships between the variables and the quantities being optimized or restricted.

In this objective function

x and y are decision variables
Now that you’ve identified all the components that influence the outcome of linear programming problems, let’s take a detailed look at the steps involved in solving these problems.

Step-by-Step Guide to Solving Linear Programming Problems

Solving a linear programming problem (LPP) involves defining the variables, constraints, and objective functions. These steps will help you systematically optimize an objective function subject to certain constraints.

Here are the steps to solve linear programming problems.

1. Identify decision variables

The decision variables represent real-world quantities like the number of units of a product or time to be invested in a task. 

By clearly defining the decision variables, you can represent the quantities that you need to determine in order to achieve the objective.

2. Define the objective function

The objective function reflects the goal of the problem, such as maximizing profit or minimizing cost. Represent the objective function in terms of the decision variables. For example, in a maximization problem, it could be in the form of  Z=ax+by.

Here, Z is the total profit or cost, and a and b are coefficients representing the profit or cost contribution. 

3. Specify constraints

Constraints are limitations or restrictions on the decision variables, representing limitations on available resources, budget, time, etc. You will have to formulate each constraint as a linear inequality or equation involving the decision variables.

For example, a constraint could be in the form of:

The left-hand side represents the relationship between the variables, and the right-hand side represents the available resource or limit.

4. Ensure non-negativity restrictions are applied

Non-negativity restrictions prevent decision variables from taking negative values, as negative quantities might not make sense in many real-world scenarios (like the number of items produced).

Negative restrictions are expressed as  x>=0    y>=0 to ensure decision variables are non-negative.

5. Solve the Problem

Once you’ve defined the decision variables, objective function, and constraints, you can proceed to solve the problem using appropriate methods, such as graphical methods for simple two-variable problems or the Simplex method for larger, more complex problems.

After being introduced to the steps for solving linear programming problems, you can now apply these techniques to real-world examples and gain a better understanding of how to use them effectively.

Real-World Examples of Linear Programming Problems with Solutions

Linear programming can be applied to solve problems arising in industries like manufacturing, finance, logistics, and marketing, which require decision-making with limited resources.

Here are three real-world linear programming problems, followed by step-by-step solutions to solve them.

1. Example: A company manufactures two types of products: Product A and Product B. The company wants to maximize its profit, given the following information:

• Each unit of Product A yields a profit of INR 5.
• Each unit of Product B yields a profit of INR 8.
• Product A requires 1 hour of labor to produce, while Product B requires 2 hours of labor.
• The company has a total of 100 labor hours available.
• The company is limited to producing 50 units of Product A and 40 units of Product B.

Develop a linear programming model to maximize the total profit and determine how many units of each product should be produced.

Solution: This problem focuses on the manufacturing industry, looking to maximize its profits. 

Objective Function in this problem:

Z = 5x + 8y

Constraints:

Productivity constraint: x + 2y ≤ 100

Product A constraint: x ≤ 50

Product B constraint: y ≤ 40

Non-negative constraints: x ≥ 0 and y ≥ 0

Step 1: Introduce slack variables

x+2y+s₁=100

x+s₂=50

y+s₃=40

Step 2: Set up the table:

Step 3: Perform the Simplex method

• Identify the pivot column (most negative value in the last row, excluding the RHS).
• Identify the pivot row by dividing the RHS values by the corresponding values in the pivot column (only positive values).
• Perform pivoting to update the tableau.

To identify the pivot row, divide the RHS values by the respective coefficients in the y column:

• Row 1: 100 ÷ 2 = 50
• Row 2: 50 ÷ 0= ∞  (ignore)
• Row 3: 40 ÷ 1 = 40

The smallest positive value is 40, so the pivot element is in the y-column and the s3 row.

Step 4: Perform pivoting and update the tableau

After pivoting, the updated table will look like this:

Step 5: Check for optimality

Since there are no negative values in the bottom row (other than the RHS), the optimal solution has been found.

X = 50 and y = 40

Thus, maximum profit, Z = 5(50) + 8(40) = 590

2. Example: A nutritionist is trying to create a diet plan that satisfies the nutritional needs of a patient at the minimum cost. The patient requires at least 50 grams of protein and 40 grams of carbohydrates. The following food options are available:

• Food X: Costs ₹10 per serving, provides 10 grams of protein and 5 grams of carbohydrates.
• Food Y: Costs ₹12 per serving, provides 15 grams of protein and 10 grams of carbohydrates.

Determine a linear programming model to minimize the cost of the diet, while meeting the required nutritional values.

Solution: This type of problem is usually encountered in the health and wellness industries.

The objective function can be written as:

Step 1: Set up the Simplex method

Introduce slack variables and write the constraints:

Step 2: Set up the Table

Step 3: Perform Pivoting

Look for the most negative value in the objective function row (Z row). In this case, -12 in column y. This means we will pivot around the y column. Divide the RHS values by the corresponding values in the y column to determine which row is the pivot row.

Since the smallest ratio is 3.33 (Row 1), Row 1 is the pivot row.

After performing the row operations to eliminate values in the pivot column, you get the following table:

From the table, we get x = 10 and y = 4. Inserting this into the objective function, you get:

Z=10(10)+12(4)=148 

Thus, the minimum cost of the diet is INR 148.

3. Example: A company produces two products, A and B, using limited resources. The company wants to maximize its profit. The resources and profit data are as follows:

• Product A:
  • Profit = ₹20 per unit
  • Requires 3 units of Resource 1 and 2 units of Resource 2 per unit
• Product B:
  • Profit = ₹15 per unit
  • Requires 2 units of Resource 1 and 4 units of Resource 2 per unit

The company has a total of 18 units of Resource 1 and 16 units of Resource 2 available.

Solution: This problem is also an example of the manufacturing industry, looking to increase profits while keeping production limits in mind.

The objective function can be written as:

Z=20x+15y 

Constraints: 

Non-negativity constraints: x ≥ 0 y ≥ 0

Step 1: Set up the Simplex method

Write constraints using the slack variables.

Step 2: Set up the table

Step 4: Perform the Simplex Method

Look at the Z row. The most negative value is -20 in the x column, so the pivot column is x. Divide the values in the RHS column by the corresponding values in the x column (for positive values)

The smallest ratio is 6, so Row 1 is the pivot row. The pivot element is 3 (in Row 1, Column x). Divide the Row 1 by 3 to make the pivot element 1. You get the following table.

The most negative value is -5 in the y column, so the pivot column is y. Divide the values in the RHS column by the corresponding values in the y column (for positive values only).

The smallest ratio is 1.5, so Row 2 is the pivot row. Perform row operations again to update the table.

Since no further pivoting is possible, you obtain x = 7.5 and y = 3

To calculate the maximum profit, insert these values in the objective function:

Z=20(7.5)+15(3)=195

Thus, the company should produce 7.5 units of Product A and 3 units of Product B. The maximum profit the company can achieve is INR 195.

To master linear programming, applying what you've learned through practice is key. This will help you solidify your understanding of the topic by tackling a variety of problems Let’s check out some sample problems in the next section.

10 Practice Problems on Linear Programming (LPP)  for Skill Development

The following practice problems will cover important concepts like optimization of resources and production planning. By solving these problems, you will gain a deeper understanding of key concepts like decision variables, constraints, objective functions, and the Simplex Method.

Here are some linear programming problems for you to practice.

1. A delivery company needs to determine the most cost-effective route to deliver goods to 5 different cities. Formulate a linear programming problem to minimize transportation costs.
2. A company wants to allocate its production capacity between two products, A and B, to maximize total revenue, given limited raw materials and production time.
3. A restaurant wants to decide how many meals of different types to prepare daily in order to maximize profit, given limited ingredients and labor.
4. A company is deciding how many units of two products to produce, each requiring different raw materials and labor hours.
5. A farmer wants to determine how much of two crops to plant on his land in order to maximize profit, given limitations on water and land space.
6. A telecommunications company wants to determine how to allocate resources between different regions to maximize market coverage while staying within a budget.
7. A company needs to decide how much to invest in advertising on TV and social media to maximize the number of responses within a budget constraint.
8. A transportation company needs to decide how many vehicles to send to each destination to minimize transportation costs while meeting delivery requirements.
9. A manufacturer wants to determine the most efficient use of raw materials to produce two types of products that require different combinations of materials.
10. A construction company wants to allocate its workers to different tasks on a project in order to minimize labor costs while meeting project deadlines.

You may have encountered challenges while solving these problems, such as formulating the equations or finding solutions. In the next section, you can explore the common difficulties you may face and provide strategies to overcome them.

Challenges in Linear Programming and How to Overcome Them

Challenges like formulating the objective function, handling constraints, or applying the Simplex Method can sometimes impact progress. By understanding these challenges and learning practical tips to address them, you’ll be better equipped to solve LPPs effectively.

Here are some common challenges in linear programming problems and practical solutions to address them.

Learn how advanced knowledge in data science can help you overcome challenges like handling constraints while implementing linear programming. Join Executive Diploma in Data Science & AI course now!

Linear programming is a powerful technique for solving practical problems, such as maximizing profits or minimizing costs. Its wide-ranging applications in industries like logistics management and manufacturing make it an essential tool. To deepen your understanding and expand your knowledge in this field, explore the following section.

How upGrad Can Help You Excel Linear Programming and Data Science

Applications of linear programming are spreading across emerging fields like machine learning and data analytics, helping them in optimal decision-making and resource allocation. 

To master this concept, upGrad’s courses will provide a comprehensive foundation. These courses will introduce you to the basics of LP while preparing you for advanced learning.

Here are some courses offered by upGrad to help you understand linear programming.

• Unsupervised Learning: Clustering 
• Executive Diploma in Machine Learning and AI
• Post Graduate Certificate in Machine Learning & NLP (Executive)
• Fundamentals of Deep Learning and Neural Networks

Do you need help deciding which courses can help you in linear programming? Contact upGrad for personalized counseling and valuable insights. For more details, you can also visit your nearest upGrad offline center.

Similar Read:

• Linear Algebra for Machine Learning: Critical Concepts, Why Learn Before ML
• Generalized Linear Models (GLM): Applications, Interpretation, and Challenges

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired  with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles