Different Types of Linear Programming Problems: Introduction, Types, Limitations, Examples

Different types of linear programming problems: Linear programming, often known as linear optimisation, is a technique for finding the best solution to a mathematical problem by considering certain linear relationships. It entails, among other things, maximising revenues, reducing expenditures, and making the most efficient use of resources.

These are known as linear programming problems (LPP). Commerce, industry, marketing, distribution, military, economics, and business are just a few domains where the LPP can be used. In this article, we will go over the many different types of linear programming issues.

Introduction to Different Types of Linear Programming Problems

Linear programming aims to discover the optimal value of a linear function of many variables (say \(x\) and \(y\)) under the criteria that the variables are non-negative and that a set of linear inequalities are satisfied, called linear constraints. The term programming refers to determining a specific programme or plan of action, whereas linear refers to the method of finding all mathematical relations employed in the problem.

\(x \ge 0,\,y \ge 0\)

Linear programming is a popular technique for discovering the most effective resource allocation. The term ‘linear’ refers to a one-dimensional relationship between many variables. Picking the optimal answer from a group of choices is called ‘programming’.

Learn Exam Concepts on Embibe

Types of Linear Programming Problems

The following are the types of linear programming problems:

• Manufacturing problems
• Diet problems
• Transport problems
• Optimal alignment problem

Manufacturing Problems

In these problems, we evaluate the number of units of various items that should be produced and sold by a company when each product requires a given number of workforce, machine hours, labour hours per unit of product, warehouse space per unit of output, and so on, to maximise profit.

Manufacturing problems involve maximising the production rate or net profits of manufactured products, which might measure the available workspace, the number of workers, machine hours, packing materials used, raw materials required, the product’s market value, and other factors. These are commonly used in the industrial sector to anticipate a company’s future capital increase over time.

Diet Problems

In these problems, we evaluate the number of constituents/nutrients that should be included in a diet to reduce the desired diet’s expense while ensuring that each nutrient is present at a minimum level.

As the name implies, diet issues involve increasing the intake of specific foods that are high in the key nutrients and can help adopt a specific diet plan. The goal of a diet problem is to identify a set of meals that will meet a set of daily nutritional needs for the least amount of money.

Transportation Problems

In these problems, we create a transportation schedule to discover the most cost-effective method of carrying a product from various plants/factories to various markets.

The study of transportation routes or how items from diverse production sources are transported to various markets to minimise the total transportation cost is linked to transportation difficulties. Analysing such challenges is crucial for large firms with several production units and a broad customer base.

Optimal Alignment Problem

This problem addresses a company’s completion of a given task/assignment by selecting a specific number of employees to complete the assignment within the required timeframe, assuming that each person works on only one job. Event planning and management in major organisations, for example, are examples of such problems.

Constraints and Objective Functions

Optimal and Feasible Solutions

The problem of optimisation is an issue in which the goal is to maximise or minimise a linear function (say, of two variables \(x\) and \(y\)) while adhering to specific constraints given by a set of linear inequalities.

The viable zone (or solution region) of a linear programming problem is the common region given by all the constraints, including non-negative constraints \(x,\,y \ge 0\). The task is achievable in the region \(ABCDEF\) (shaded) in the figure below. A region that is not feasible is referred to as an infeasible region. Feasible solutions to the constraints are represented as points within and on the boundary of the feasible region.

Formulation of Different Types of LPP

The steps involved in mathematical modelling or formulation of different types of linear programming problems are given below:

• Step 1: Identify the decision variables: The first step is to identify the decision variables that govern how the objective function behaves. An objective function is one that must be optimised. Recognise decision variables and give them symbols such as \(X,\,Y\) and \(Z\).
• Step 2: Form an objective function: Using the decision variables, write out an algebraic expression that displays the quantity we aim to maximise.
• Step 3: Identify the constraints: Choose and write the given linear inequalities from the data.
• Step 4: Draw the graph for the given data: Construct the graph by using constraints for solving the linear programming problem.
• Step 5: Draw the feasible region: This section of the graph satisfies all of the problem’s constraints. A valid solution for the objective function can be found at any point in the feasible zone.
• Step 6: Choosing the optimal point: Choose the point for which the given function has maximum or minimum values.

Practice Exam Questions

Solved Examples of Different Types of Linear Programming  Problems

Q.1. An IT company that wants to outfit your office with some new cabinets. Cabinet \(X\) costs \({\rm{Rs}}{\rm{.}}\,{\rm{10}}\) per unit, takes up \(6\) square feet of floor space, and holds eight cubic feet of files, according to a furniture business. Cabinet \(Y\) costs \({\rm{Rs}}{\rm{.}}\,{\rm{20}}\) per unit, takes up eight square feet of floor space, and has a capacity of twelve cubic feet of files. The company only have \(72\) square feet of cabinet space and \({\rm{Rs}}{\rm{.}}\,{\rm{140}}\) to spend on this transaction. How many of each type should you purchase to maximise the storage capacity?
Ans:

Step 1: Determine how many decision variables there are.

The number of cabinets \(A\) and \(B\) are the choice variables in this problem because we need to figure out how many of each model, we should buy to maximise storage volume.

\(A\) is the number of models \(A\) cabinets that were purchased.
\(B\) is the number of models \(B\) cabinets that were purchased.

As a result, this problem has two decision variables.

Step 2: Determine the constraints of the decision variables. The two constraints in this problem are cost and space.

Cost \( = 10A + 20B < 140\) or \(B < – \frac{1}{2}A + 7\)

Space \( = 6A + 8B < 72\), or \(B < – \frac{3}{4}A + 9\)

Step 3: Create a linear equation for the objective function. It is expressed in this problem that we must optimise the volume, which may be represented as

Volume \((V) = 8A + 12B\)

Step 4: State the non-negativity constraint clearly. Naturally, \(A \ge 0,\,B \ge 0\)

Convert the problem into a mathematical form and solve it further now that we have formulated it.

Step 5: On the graph, highlight the feasible zone. Shade the area outside the constraint boundaries after plotting the coordinates on the graph (which is not feasible). This is how the indicated feasible area will look:

Step 6: Determine the optimum point’s coordinates. We’ll use some random numbers to solve the simultaneous pair of linear equations to discover the coordinates of the optimum point.

\(V = 8X + 12Y\)

For corner points:

\(A(8,\,3),\, \Rightarrow P = 100\)

\(B(0,\,7),\, \Rightarrow P = 84\)

\(C(12,\,0),\, \Rightarrow P = 96\)

Drawing two perpendicular lines from the point onto the coordinate axes gives these corner point coordinates.

Step 7: Find the optimum point.

The maximum value of \(V\) is \(100\), as shown in the figure above, which is attained when \((X,\,Y) = A(8,\,3)\)

Q.2. Find the maximum and minimum values of the function \(f(x,\,y) = 4x + 5y\) for the constraints \(x \ge 0,\,y \ge 0,\,x + y \le 6\).
Ans:

The graph for the given constraints \(x \ge 0,\,y \ge 0,\,x + y \le 6\) is given below.

The coordinates of the region formed are \((0,\,0),\,(6,\,0),(0,\,6)\)

• At \((0,\,0)\) the value of the function \(f(x,\,y) = 4(0) + 5(0) = 0\), which is the minimum value.
• At \((6,\,0)\), the value of the function \(f(x,\,y) = 4(6) + 5(0) = 24\)
• At \((0,\,6)\), the value of the function \(f(x,\,y) = 4(0) + 5(6) = 30\), which is the maximum value.

Hence, the maximum value of the given function is \(30\), and the minimum value is \(0\)

Q.3. During the festival season, the \(XYZ\) company mixes two variables \(A\) and \(B\) to create a gift pack that must weigh \(5\,\;{\rm{kg}}\). A minimum of \(2\,\;{\rm{kg}}\) of \(A\) and a maximum of \(4\,\;{\rm{kg}}\) of \(B\) should be used. \(A\) contributes \({\rm{Rs}}.\,5\) per \({\rm{kg}}\) to the company’s net profit, while \(B\) contributes \({\rm{Rs}}.\,6\) per \({\rm{kg}}\). Create an LPP Model to identify the optimal factor mix.
Ans:

Step 1: Objective function

The company’s goal in the challenge is to maximise profit. The net profit contribution for factors \(A\) and \(B\) is supplied to us.

• Let \(x\,\;{\rm{kg}}\) of factor \(A\) be used
• Let \(y\,\;{\rm{kg}}\) of factor \(B\) be used

Objective function is to maximise the \(z = 5x + 6y\)

Step 2: Constraint variables

The gift pack must weigh at least \(5\,\;{\rm{kg}}\).

\(x + y = 5\)

A minimum of \(2\,\;{\rm{kg}}\) of \(A\) and a maximum of \(4\,\;{\rm{kg}}\) of \(B\) must be used.

\(x \ge 2,\,y \le 4\)

Step 3: Non-negative constraints

\(x \ge 0,\,y \ge 0\)

Step 4: Summarise the linear programming problem for maximising.

• \(x \ge 2,\,y \le 4\) 
• \(x \ge 0,\,y \ge 0\)
• \(x + y = 5\)

Q.4. Calculate the maximum and minimum value of the function \(z = 5x + 4y\) for the following constraints
\(x + 2y \le 14,\,3x – y \ge 0,\,x – y \le 2\)
Ans:

The three inequalities show the constraints. The feasible region is the area of the plane that will be marked.

\((z) = 5x + 3y\) is the optimisation equation. You must locate the \((x,\,y)\) corner points that correspond to the highest and smallest \(z\) values.

To begin, solve each inequality separately.

\(x + 2y \le 14,\, \Rightarrow y = – \frac{1}{2}x + 7\)
\(3x – y \ge 0,\, \Rightarrow y \le 3x\)
\(x – y \le 2,\, \Rightarrow y \ge x – 2\)

The graph for the above constraints is given below.

Q.5. Solve the following linear equation graphically for the given constraints Minimise \(Z = 200x + 500y \cdot x + 2y \ge 10\) and \(3x + 4y \le 24\)
Ans:

Given linear objective function is \(Z = 200x + 500y\)

The constraints are given

\(x + 2y \ge 10,\,3x + 4y \le 24\) and non-negative constraints \(x \ge 0,\,y \ge 0\)

The graph of the above inequalities is given below.

Corner points of this (feasible or shaded) region, say \(A,\,B\) and \(C\), have coordinates of \((0,\,5),\,(4,\,3)\)and \((0,\,6)\) accordingly.

• At point \((0,\,5)\), the value of \(Z = 200 \times 0 + 500 \times 5 = 2500\)
• At point \((4,\,3)\), the value of \(Z = 200 \times 4 + 500 \times 3 = 2300\)
• At point \((0,\,6)\), the value of \(Z = 200 \times 0 + 500 \times 6 = 3000\)

Hence, the minimum value of the function \(Z = 200x + 500y\) is \(3000\)

Summary of Different Types of Linear Programming Problems

Linear programming aims to discover the optimal value of a linear function of many variables (say \(x\) and \(y\)) under the criteria that the variables are non-negative and that a set of linear inequalities are satisfied, called linear constraints. There different components and characteristics of linear programming problems are objective functions, constraints, linearity, finiteness, and decision variables.

The different types of linear programming problems as mentioned before are manufacturing problems, diet problems, transport problems and optimal allocation problems. These have been discussed with examples. And the fact that Linear programming problems are generally solved by simple and graphical methods is also clear.

Attempt Mock Tests

FAQ’s on Different Types of Linear Programming Problems

Following are a few FAQ’s which usually pop up on the different types of Linear Programming Problems:

Q.1. What is linear programming?
Ans: Linear programming is a technique for solving constrained problems in some way. It is the process of maximum or minimising linear functions under restrictions of a linear inequality. The challenge of solving linear programming is thought to be the most straightforward.

Q.2. What are the two forms of LPP?
Ans: The two forms of LPP are
(i) Standard form of linear programming problem
(ii) Canonical form of linear programming problem

Q.3. What is the difference between standard LPP and canonical LPP?
Ans: The basic difference between canonical and standard form is that the canonical form uses Boolean Algebra to represent Boolean outputs of digital circuits, whereas the standard form is a simplified version of the canonical form that uses Boolean Algebra to represent Boolean outputs of digital circuits.

Q.4. What are the two limitations of LPP?
Ans: The limitations of linear programming problems are:
(i) They can be used only when the objective function and all constraints represented in linear inequalities are used.
(ii) They are used only when all aspects of a problem can be quantified.

Q.5. What are the types of Linear programming problems?
Ans: The different types of linear programming problems are
(i) Manufacturing problems
(ii) Diet problems
(iii)Transport problems
(iv) Optimal allocation problem

We hope this detailed article on Different Types of Linear Programming Problems helps you. If you have any questions pertaining to the same, feel to ask in the comment section below. We will get back to you as soon as possible.