represent assignment problem in lpp form

Your Article Library

Assignment problem in linear programming : introduction and assignment model.

ADVERTISEMENTS:

Assignment problem is a special type of linear programming problem which deals with the allocation of the various resources to the various activities on one to one basis. It does it in such a way that the cost or time involved in the process is minimum and profit or sale is maximum. Though there problems can be solved by simplex method or by transportation method but assignment model gives a simpler approach for these problems.

In a factory, a supervisor may have six workers available and six jobs to fire. He will have to take decision regarding which job should be given to which worker. Problem forms one to one basis. This is an assignment problem.

1. Assignment Model :

Suppose there are n facilitates and n jobs it is clear that in this case, there will be n assignments. Each facility or say worker can perform each job, one at a time. But there should be certain procedure by which assignment should be made so that the profit is maximized or the cost or time is minimized.

In the table, Co ij is defined as the cost when j th job is assigned to i th worker. It maybe noted here that this is a special case of transportation problem when the number of rows is equal to number of columns.

Mathematical Formulation:

Any basic feasible solution of an Assignment problem consists (2n – 1) variables of which the (n – 1) variables are zero, n is number of jobs or number of facilities. Due to this high degeneracy, if we solve the problem by usual transportation method, it will be a complex and time consuming work. Thus a separate technique is derived for it. Before going to the absolute method it is very important to formulate the problem.

Suppose x jj is a variable which is defined as

1 if the i th job is assigned to j th machine or facility

0 if the i th job is not assigned to j th machine or facility.

Now as the problem forms one to one basis or one job is to be assigned to one facility or machine.

The total assignment cost will be given by

The above definition can be developed into mathematical model as follows:

Determine x ij > 0 (i, j = 1,2, 3…n) in order to

Subjected to constraints

and x ij is either zero or one.

Method to solve Problem (Hungarian Technique):

Consider the objective function of minimization type. Following steps are involved in solving this Assignment problem,

1. Locate the smallest cost element in each row of the given cost table starting with the first row. Now, this smallest element is subtracted form each element of that row. So, we will be getting at least one zero in each row of this new table.

2. Having constructed the table (as by step-1) take the columns of the table. Starting from first column locate the smallest cost element in each column. Now subtract this smallest element from each element of that column. Having performed the step 1 and step 2, we will be getting at least one zero in each column in the reduced cost table.

3. Now, the assignments are made for the reduced table in following manner.

(i) Rows are examined successively, until the row with exactly single (one) zero is found. Assignment is made to this single zero by putting square □ around it and in the corresponding column, all other zeros are crossed out (x) because these will not be used to make any other assignment in this column. Step is conducted for each row.

(ii) Step 3 (i) in now performed on the columns as follow:- columns are examined successively till a column with exactly one zero is found. Now , assignment is made to this single zero by putting the square around it and at the same time, all other zeros in the corresponding rows are crossed out (x) step is conducted for each column.

(iii) Step 3, (i) and 3 (ii) are repeated till all the zeros are either marked or crossed out. Now, if the number of marked zeros or the assignments made are equal to number of rows or columns, optimum solution has been achieved. There will be exactly single assignment in each or columns without any assignment. In this case, we will go to step 4.

4. At this stage, draw the minimum number of lines (horizontal and vertical) necessary to cover all zeros in the matrix obtained in step 3, Following procedure is adopted:

(iii) Now tick mark all the rows that are not already marked and that have assignment in the marked columns.

(iv) All the steps i.e. (4(i), 4(ii), 4(iii) are repeated until no more rows or columns can be marked.

(v) Now draw straight lines which pass through all the un marked rows and marked columns. It can also be noticed that in an n x n matrix, always less than ‘n’ lines will cover all the zeros if there is no solution among them.

5. In step 4, if the number of lines drawn are equal to n or the number of rows, then it is the optimum solution if not, then go to step 6.

6. Select the smallest element among all the uncovered elements. Now, this element is subtracted from all the uncovered elements and added to the element which lies at the intersection of two lines. This is the matrix for fresh assignments.

7. Repeat the procedure from step (3) until the number of assignments becomes equal to the number of rows or number of columns.

Related Articles:

• Two Phase Methods of Problem Solving in Linear Programming: First and Second Phase
• Linear Programming: Applications, Definitions and Problems

No comments yet.

Leave a reply click here to cancel reply..

You must be logged in to post a comment.

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

Data Visualization using Seaborn

Merging and Joining in Pandas

Python Generators

Assignment Problem: Linear Programming

The assignment problem is a special type of transportation problem , where the objective is to minimize the cost or time of completing a number of jobs by a number of persons.

In other words, when the problem involves the allocation of n different facilities to n different tasks, it is often termed as an assignment problem.

The model's primary usefulness is for planning. The assignment problem also encompasses an important sub-class of so-called shortest- (or longest-) route models. The assignment model is useful in solving problems such as, assignment of machines to jobs, assignment of salesmen to sales territories, travelling salesman problem, etc.

It may be noted that with n facilities and n jobs, there are n! possible assignments. One way of finding an optimal assignment is to write all the n! possible arrangements, evaluate their total cost, and select the assignment with minimum cost. But, due to heavy computational burden this method is not suitable. This chapter concentrates on an efficient method for solving assignment problems that was developed by a Hungarian mathematician D.Konig.

"A mathematician is a device for turning coffee into theorems." -Paul Erdos

Formulation of an assignment problem

Suppose a company has n persons of different capacities available for performing each different job in the concern, and there are the same number of jobs of different types. One person can be given one and only one job. The objective of this assignment problem is to assign n persons to n jobs, so as to minimize the total assignment cost. The cost matrix for this problem is given below:

The structure of an assignment problem is identical to that of a transportation problem.

To formulate the assignment problem in mathematical programming terms , we define the activity variables as

for i = 1, 2, ..., n and j = 1, 2, ..., n

In the above table, c ij is the cost of performing jth job by ith worker.

Generalized Form of an Assignment Problem

The optimization model is

Minimize c 11 x 11 + c 12 x 12 + ------- + c nn x nn

subject to x i1 + x i2 +..........+ x in = 1          i = 1, 2,......., n x 1j + x 2j +..........+ x nj = 1          j = 1, 2,......., n

x ij = 0 or 1

In Σ Sigma notation

x ij = 0 or 1 for all i and j

An assignment problem can be solved by transportation methods, but due to high degree of degeneracy the usual computational techniques of a transportation problem become very inefficient. Therefore, a special method is available for solving such type of problems in a more efficient way.

Assumptions in Assignment Problem

• Number of jobs is equal to the number of machines or persons.
• Each man or machine is assigned only one job.
• Each man or machine is independently capable of handling any job to be done.
• Assigning criteria is clearly specified (minimizing cost or maximizing profit).

Share this article with your friends

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

4.3: Linear Programming - Maximization Applications

• Last updated
• Save as PDF
• Page ID 40134

• Rupinder Sekhon and Roberta Bloom
• De Anza College

Learning Objectives

In this section, you will learn to:

• Recognize the typical form of a linear programming problem.
• Formulate maximization linear programming problems.
• Graph feasible regions for maximization linear programming problems.
• Determine optimal solutions for maximization linear programming problems.

Prerequisite Skills

Before you get started, take this prerequisite quiz.

1. Graph this system of inequalities:

\(\left\{\begin{array} {l} 2x+4y\leq 10\\3x−5y<15\end{array}\right.\)

If you missed this problem, review Section 4.2 . (Note that this will open in a new window.)

2. Graph this system of inequalities:

\(\left\{\begin{array} {l} y\leq 2x+1\\y\leq-3x+6\\x\geq0\\y\geq0\end{array}\right.\)

(The solution is in the center region.)

Application problems in business, economics, and social and life sciences often ask us to make decisions on the basis of certain conditions. The conditions or constraints often take the form of inequalities. In this section, we will begin to formulate, analyze, and solve such problems, at a simple level, to understand the many components of such a problem.

A typical linear programming problem consists of finding an extreme value of a linear function subject to certain constraints. We are either trying to maximize or minimize the value of this linear function, such as to maximize profit or revenue, or to minimize cost. That is why these linear programming problems are classified as maximization or minimization problems , or just optimization problems . The function we are trying to optimize is called an objective function , and the conditions that must be satisfied are called constraints .

When we graph all constraints, the area of the graph that satisfies all constraints is called the feasible region . The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasible region.  We call these vertices critical points.   These are found using any methods from Chapter 3 as we are looking for the points where any two of the boundary lines intersect. 

A typical example is to maximize profit from producing several products, subject to limitations on materials or resources needed for producing these items; the problem requires us to determine the amount of each item produced. Another type of problem involves scheduling; we need to determine how much time to devote to each of several activities in order to maximize income from (or minimize cost of) these activities, subject to limitations on time and other resources available for each activity.

In this chapter, we will work with problems that involve only two variables, and therefore, can be solved by graphing. Here are the steps we'll follow:

The Maximization Linear Programming Problems

• Define the unknowns.
• Write the objective function that needs to be maximized.
• For the standard maximization linear programming problems, constraints are of the form: \(ax + by ≤ c\)
• Since the variables are non-negative, we include the constraints: \(x ≥ 0\); \(y ≥ 0\).
• Graph the constraints.
• Shade the feasible region.
• Find the corner points.
• Find the value of the objective function at each corner point to determine the corner point that gives the maximum value.

Example \(\PageIndex{1}\)

Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation.

If Niki makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income?

We start by defining our unknowns.

• Let the number of hours per week Niki will work at Job I = \(x\).
• Let the number of hours per week Niki will work at Job II = \(y\).

Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an hour at Job II, her total income I is given by the following equation.

\[I = 40x + 30y \nonumber\]

Our next task is to find the constraints. The second sentence in the problem states, "She never wants to work more than a total of 12 hours a week." This translates into the following constraint:

\[x + y \leq 12 \nonumber \]

The third sentence states, "For every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation." The translation follows.

\[2x + y \leq 16 \nonumber\]

The fact that \(x\) and \(y\) can never be negative is represented by the following two constraints:

\[x \geq 0 \text{, and } y \geq 0 \nonumber.\]

Well, good news! We have formulated the problem. We restate it as

\[\begin{array}{ll} \textbf { Maximize } & \mathrm{I}=40 \mathrm{x}+30 \mathrm{y} \\ \textbf { Subject to: } & \mathrm{x}+\mathrm{y} \leq 12 \\ & 2 \mathrm{x}+\mathrm{y} \leq 16 \\ & \mathrm{x} \geq 0 ; \mathrm{y} \geq 0 \end{array}\nonumber\]

In order to solve the problem, we graph the constraints and shade the region that satisfies all the inequality constraints.

Any appropriate method can be used to graph the lines for the constraints. However often the easiest method is to graph the line by plotting the x-intercept and y-intercept.

The line for a constraint will divide the plane into two region, one of which satisfies the inequality part of the constraint. A test point is used to determine which portion of the plane to shade to satisfy the inequality. Any point on the plane that is not on the line can be used as a test point.

• If the test point satisfies the inequality, then the region of the plane that satisfies the inequality is the region that contains the test point.
• If the test point does not satisfy the inequality, then the region that satisfies the inequality lies on the opposite side of the line from the test point.

In the graph below, after the lines representing the constraints were graphed, the point (0,0) was used as a test point to determine that

• (0,0) satisfies the constraint \(x + y \leq 12\) because \(0 + 0 < 12\)
• (0,0) satisfies the constraint \(2x + y \leq 16\) because \(2(0) + 0 < 16\)

Therefore, in this example, we shade the region that is below and to the left of both constraint lines, but also above the x axis and to the right of the y axis, in order to further satisfy the constraints \(x \geq 0\) and \(y \geq 0\).

The shaded region where all conditions are satisfied is the feasible region or the feasible polygon.

The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasible region.

Therefore, we will identify all the vertices (corner points) of the feasible region. These are found using any methods from Chapter 3 as we are looking for the points where any two of the boundary lines intersect. They are listed as (0, 0), (0, 12), (4, 8), (8, 0). To maximize Niki's income, we will substitute these points in the objective function to see which point gives us the highest income per week. We list the results below.

Clearly, the point (4, 8) gives the most profit: $400.

Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II.

Example \(\PageIndex{2}\)

A factory manufactures two types of gadgets, regular and premium. Each gadget requires the use of two operations, assembly and finishing, and there are at most 12 hours available for each operation. A regular gadget requires 1 hour of assembly and 2 hours of finishing, while a premium gadget needs 2 hours of assembly and 1 hour of finishing. Due to other restrictions, the company can make at most 7 gadgets a day. If a profit of $20 is realized for each regular gadget and $30 for a premium gadget, how many of each should be manufactured to maximize profit?

We define our unknowns:

• Let the number of regular gadgets manufactured each day = \(x\).
• and the number of premium gadgets manufactured each day = \(y\).

The objective function is

\[P = 20x + 30y \nonumber\]

We now write the constraints. The fourth sentence states that the company can make at most 7 gadgets a day. This translates as

\[x + y \leq 7 \nonumber\]

Since the regular gadget requires one hour of assembly and the premium gadget requires two hours of assembly, and there are at most 12 hours available for this operation, we get

\[x + 2y \leq 12 \nonumber\]

Similarly, the regular gadget requires two hours of finishing and the premium gadget one hour. Again, there are at most 12 hours available for finishing. This gives us the following constraint.

\[2x + y \leq 12 \nonumber \]

We have formulated the problem as follows:

\[\begin{array}{ll} \textbf { Maximize } & \mathrm{P}=20 \mathrm{x}+30 \mathrm{y} \\ \textbf { Subject to: } & \mathrm{x}+\mathrm{y} \leq 7 \\ & \mathrm{x}+2\mathrm{y} \leq 12 \\ & 2\mathrm{x} +\mathrm{y} \leq 12 \\ & \mathrm{x} \geq 0 ; \mathrm{y} \geq 0 \end{array} \nonumber\]

In order to solve the problem, we next graph the constraints and feasible region.

Again, we have shaded the feasible region, where all constraints are satisfied.

Since the extreme value of the objective function always takes place at the vertices of the feasible region, we identify all the critical points. They are listed as (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0). To maximize profit, we will substitute these points in the objective function to see which point gives us the maximum profit each day. The results are listed below.

The point (2, 5) gives the most profit, and that profit is $190. Therefore, we conclude that we should manufacture 2 regular gadgets and 5 premium gadgets daily to obtain the maximum profit of $190.

So far we have focused on “ standard maximization problems ” in which

• The objective function is to be maximized
• All constraints are of the form \(ax + by \leq c\)
• All variables are constrained to by non-negative (\(x ≥ 0\), \(y ≥ 0\))

We will next consider an example where that is not the case. Our next problem is said to have “ mixed constraints ”, since some of the inequality constraints are of the form \(ax + by ≤ c\) and some are of the form \(ax + by ≥ c\). The non-negativity constraints are still an important requirement in any linear program.

Example \(\PageIndex{3}\)

Solve the following maximization problem graphically.

\[\begin{array}{ll} \textbf { Maximize } & \mathrm{P}=10 \mathrm{x}+15 \mathrm{y} \\ \textbf { Subject to: } & \mathrm{x}+\mathrm{y} \geq 1 \\ & \mathrm{x}+2\mathrm{y} \leq 6 \\ & 2\mathrm{x} +\mathrm{y} \leq 6 \\ & \mathrm{x} \geq 0 ; \mathrm{y} \geq 0 \end{array} \nonumber\]

The graph is shown below.

The five critical points are listed in the above figure. The reader should observe that the first constraint \(x + y ≥ 1\) requires that the feasible region must be bounded below by the line \(x + y =1\); the test point (0,0) does not satisfy \(x + y ≥ 1\), so we shade the region on the opposite side of the line from test point (0,0).

Clearly, the point (2, 2) maximizes the objective function to a maximum value of 50.

It is important to observe that that if the point (0,0) lies on the line for a constraint, then (0,0) could not be used as a test point. We would need to select any other point we want that does not lie on the line to use as a test point in that situation.

Finally, we address an important question. Is it possible to determine the point that gives the maximum value without calculating the value at each critical point?

The answer is yes.

We summarize:

Linear Programming Problem (LPP) Formulation with Numericals

To formulate Linear Programming Problem (LPP) for given statement type problems(numerical) is easy if we go through its Mathematical Model.

General Mathematical Modelling of LP

As explained in the video, mathematical model of LP consists of the following:

i) Objective Function (denote with “Z”) ii) Decision variables (represented in terms of “x”) iii) Constraints

Note: To know more about above terms you can go through the notes of the Basics of Linear programming, link to the notes- click here

Now, let us generate the mathematical model of the LPP:

Let, Decision variables be x 1 , x 2 , x 3 , x 4 , … , x n x_1, x_2, x_3, x_4,…, x_n x 1 ​ , x 2 ​ , x 3 ​ , x 4 ​ , … , x n ​ with total ‘m’ constraints. Now, LP can be formulate as:

Thus, we will have any of the three conditions applied on constraints as per the provided problem ( ≤ , = , ≥ ) (≤ , = , ≥) ( ≤ , = , ≥ ) .

Steps for LPP Formulation

Identify the decision variables: It is the most important step on LPP Formulation, because based on the decision variables only, the whole problem governs. We will learn about, how to identify decision variables from given numerical/problem in this note only. (Also you can go through video for the same. Link provided in cover page)

Identify Objective Function (Z) and express it as a linear function of decision variables: As we have seen above in mathematical model, objective of any problem can be maximize or minimize. Based on that, we will have to define the objective function in terms of decision variables. (For eg: Maximize Z = 2 x 1 + 5 x 2 + 9 x 3 Z= 2x_1 + 5x_2 + 9x_3 Z = 2 x 1 ​ + 5 x 2 ​ + 9 x 3 ​ )

Identify all constraints and express it as linear inequalities or equalities in terms of decision variables: As we know that, in the real world all the resources are limited and so in each particular problem you will find some limitation/constraint on the use of available resources.

Express decision variables as Feasible variables: It means that, we have lastly define all the decision variables are greater than or equal to zero (For eg:   x 1 , x 2 , x 3 ≥ 0 \ x_1, x_2, x_3 ≥ 0   x 1 ​ , x 2 ​ , x 3 ​ ≥ 0 )

Let’s move to numerical now,

Numerical 1: Two products ‘A’ and ‘B’ are to be manufactured. Single unit of ‘A’ requires 2.4 minutes of punch press time and 5 minutes of assembly time, while single unit of ‘B’ requires 3 minutes of punch press time and 2.5 minutes of welding time. The capacity of punch press department, assembly department and welding department are 1200 min/week, 800 min/week and 600 min/week respectively. The profit from ‘A’ is ₹60 and from ‘B’ is ₹70 per unit. Formulate LPP such that, profit is maximized.

Tip: Always relate/treat LPP with real life problems for better understanding and ease of solution

Step 1: Identify the decision variables

Here, the decision has to be taken for how much quantities of product ‘A’ and ‘B’ to be manufactured in order to maximize the profit. (Quantities of product is governing this problem)

Let, Quantity of product ‘A’ manufactured = x 1 x_1 x 1 ​ Quantity of product ‘B’ manufactured = x 2 x_2 x 2 ​

Step 2: Identify Objective Function (Z)

Here, the objective is to maximize the profit from product ‘A’ and ‘B’. Each unit produced product ‘A’ gives profit of ₹60, while ‘B’ gives ₹70. So, the objective function can be defined in terms of decision variables as:

Step 3: Identify all the constraints

Product ‘A’ manufactured by: Punch press and Assembly Product ‘B’ manufactured by: Punch press and Welding

So, we have a total of three processes for the manufacturing of two products A and B. Thus, there are total three constraints.

Now, we will bifurcate this problem based on processes to get a clear idea of constraints on resources, as follows:

Product ‘A’ requires 2.4 min and product ‘B’ requires 3 min of Punch press time . Also, punch press time is limited to 1200 min/week .

Product ‘A’ requires 5 min of Assembly time . Also, assembly time is limited to 800 min/week .

Product ‘B’ requires 2.5 min of Welding time . Also, welding time is limited to 600 min/week .

Step 4: Express decision variables as feasible variables

We assume that the decision variables has feasible solution, that implies - decision variables are greater than or equal to zero.

So, complete LP can be written as,

Note that, here the solution provided (in above numerical) to you with steps is just for explanation. You can always skip this step wise solution to LP problems and can use direct method as provided in video of this topic (click here to watch video) .

Numerical 2: A tailor prepares two kinds of dresses. First kind of dress is having raw material cost of ₹150 and labour cost of ₹80, while the second kind of dress is raw material cost of ₹250 and labour cost of ₹100. He can sell the dresses of first and second kind at the rate of ₹300 and ₹500 respectively. First kind of dress takes 2 hours and second kind takes 2.5 hours of cutting. The total labour hours are restricted to 84 hours/week. Also, first kind of dress takes 1.5 hours of stitching and second requires 2 hours of stitching. The stitching hours are restricted to 60 hours/week. Formulate LPP, such that maximum profit can be earned by tailor.

The solution of this numerical will be such that, you can present this in your examination. This will save your time and gives complete idea of your explanation too in examination. All the explanation stuff will be provided in {"Explanation"} brackets for your understanding only, in the solution of this problem.

Let, Number of first kind of dress = x 1 x_1 x 1 ​ units Number of first kind of dress = x 2 x_2 x 2 ​ units

{The decision variables selected here are the units of dresses of both kind so produced, as we are going to maximize the profit of tailor. Also, by understanding the whole problem you can easily make out that, to increase the profit, tailor needs to produce more goods.}

Now, Net Profit earned by selling a unit of first kind of dress = ₹ ( 300 − 150 − 80 ) = ₹ 70 = ₹(300-150-80) = ₹70 = ₹ ( 300 − 150 − 80 ) = ₹70

Net Profit earned by selling a unit of first kind of dress = ₹ ( 500 − 250 − 100 ) = ₹ 150 = ₹(500-250-100) = ₹150 = ₹ ( 500 − 250 − 100 ) = ₹150

{As you can understand that the problem provided here is based on revenue so generated by selling different kinds of dresses. Now, revenue will be the profit generated after excluding the raw material and manufacturing cost on each of these dresses. So, for example you can see above we have excluded raw material cost of first kind of dress ₹150 and labour cost ₹80 from total selling cost of ₹300 . Thus revenue/net profit generated by selling each unit of first kind of dress is ₹ (300-150-80) = ₹70 and the same for the second kind of dress.}

∴ The objective function can be defined as;

Now, constraints are provided on labour hours for cutting and stitching. Thus, LP is subject to the following constraints;

{As we can find from problem provided, the cutting and stitching hour requirements for both kinds of dresses. Also total hours are restricted on cutting and stitching is 84 hours/week and 60 hours/week respectively.}

Suggested Notes:

Modified Distribution Method (MODI) | Transportation Problem | Transportation Model

Stepping Stone | Transportation Problem | Transportation Model

Vogel’s Approximation Method (VAM) | Method to Solve Transportation Problem | Transportation Model

Transportation Model - Introduction

North West Corner Method | Method to Solve Transportation Problem | Transportation Model

Least Cost Method | Method to Solve Transportation Problem | Transportation Model

Tie in selecting row and column (Vogel's Approximation Method - VAM) | Numerical | Solving Transportation Problem | Transportation Model

Assignment Model | Linear Programming Problem (LPP) | Introduction

Crashing Special Case - Multiple (Parallel) Critical Paths

Crashing Special Case - Indirect cost less than Crash Cost

Basics of Program Evaluation and Review Technique (PERT)

Numerical on PERT (Program Evaluation and Review Technique)

Network Analysis - Dealing with Network Construction Basics

Construct a project network with predecessor relationship | Operation Research | Numerical

Graphical Method | Methods to solve LPP | Linear Programming

Basics of Linear Programming

All comments that you add will await moderation. We'll publish all comments that are topic related, and adhere to our Code of Conduct .

Want to tell us something privately? Contact Us

Post comment

Education Lessons

Stay in touch, [notes] operation research, [notes] dynamics of machinery, [notes] maths, [notes] science, [notes] computer aided design.

• Trending Now
• Foundational Courses
• Data Science
• Practice Problem
• Machine Learning
• System Design
• DevOps Tutorial
• CBSE Class 12 Maths Notes: Chapter Wise Notes PDF 2024

Chapter 1: Relations and Functions

• Types of Functions
• Composite functions - Relations and functions
• Invertible Functions
• Composition of Functions
• Inverse Functions
• Verifying Inverse Functions by Composition

Chapter 2: Inverse Trigonometric Functions

• Inverse Trigonometric Functions
• Graphs of Inverse Trigonometric Functions - Trigonometry | Class 12 Maths
• Properties of Inverse Trigonometric Functions
• Inverse Trigonometric Identities

Chapter 3: Matrices

• Types of Matrices
• Matrix Operations
• Matrix Addition
• Matrix Multiplication: How to Multiply Matrices, Methods, Examples
• Transpose of a Matrix
• Symmetric and Skew Symmetric Matrices
• Elementary Operations on Matrices
• Inverse of a Matrix by Elementary Operations - Matrices | Class 12 Maths
• Invertible Matrix

Chapter 4: Determinants

• Determinant of a Matrix with Solved Examples
• Properties of Determinants
• Area of a Triangle using Determinants
• Minors and Cofactors
• Adjoint of a Matrix
• Applications of Matrices and Determinants

Chapter 5: Continuity and Differentiability

• Continuity and Discontinuity in Calculus - Class 12 CBSE
• Differentiability of a Function | Class 12 Maths
• Derivatives of Inverse Functions
• Derivatives of Implicit Functions - Continuity and Differentiability | Class 12 Maths
• Derivatives of Composite Functions
• Derivatives of Inverse Trigonometric Functions | Class 12 Maths
• Derivative of Exponential Functions
• Logarithmic Differentiation - Continuity and Differentiability
• Proofs for the derivatives of eˣ and ln(x) - Advanced differentiation
• Rolle's Theorem and Lagrange's Mean Value Theorem
• Derivative of Functions in Parametric Forms
• Second Order Derivatives in Continuity and Differentiability | Class 12 Maths
• Mean Value Theorem
• Algebra of Continuous Functions - Continuity and Differentiability | Class 12 Maths

Chapter 6: Applications of Derivatives

• Critical Points
• Derivatives as Rate of Change
• Increasing and Decreasing Functions
• Increasing and Decreasing Intervals
• Tangents and Normals
• Equation of Tangents and Normals
• Relative Minima and Maxima
• Absolute Minima and Maxima
• Concave Function
• Inflection Point
• Curve Sketching
• Approximations & Maxima and Minima - Application of Derivatives | Class 12 Maths
• Higher Order Derivatives

Chapter 7: Integrals

• Integration by Substitution Method
• Integration by Partial Fractions
• Integration by Parts
• Integration of Trigonometric Functions
• Functions Defined by Integrals
• Definite Integral
• Computing Definite Integrals
• Fundamental Theorem of Calculus
• Finding Derivative with Fundamental Theorem of Calculus
• Evaluating Definite Integrals
• Properties of Definite Integrals
• Definite Integrals of Piecewise Functions
• Improper Integrals
• Riemann Sum
• Riemann Sums in Summation Notation
• Trapezoidal Rule
• Definite Integral as the Limit of a Riemann Sum
• Antiderivatives
• Indefinite Integrals
• Particular Solutions to Differential Equations
• Integration by U-substitution
• Reverse Chain Rule
• Partial Fraction Expansion
• Trigonometric Substitution: Method, Formula and Solved Examples

Chapter 8: Applications of Integrals

• Area under Simple Curves
• Area Between Two Curves - Calculus
• Area between Polar Curves
• Area as Definite Integral

Chapter 9: Differential Equations

• Differential Equations
• Homogeneous Differential Equations
• Separable Differential Equations
• Exact Equations and Integrating Factors
• Implicit Differentiation
• Implicit differentiation - Advanced Examples
• Advanced Differentiation
• Disguised Derivatives - Advanced differentiation | Class 12 Maths
• Derivative of Inverse Trig Functions
• Logarithmic Differentiation

Chapter 10: Vector Algebra

• Vector Algebra
• Dot and Cross Products on Vectors
• How to Find the Angle Between Two Vectors?
• Section Formula - Vector Algebra

Chapter 11: Three-dimensional Geometry

• Direction Cosines and Direction Ratios
• Equation of a Line in 3D
• Angles Between two Lines in 3D Space: Solved Examples
• Shortest Distance Between Two Lines in 3D Space | Class 12 Maths
• Points, Lines and Planes

Chapter 12: Linear Programming

Linear programming.

• Graphical Solution of Linear Programming Problems

Chapter 13: Probability

• Conditional Probability and Independence - Probability | Class 12 Maths
• Multiplication Theorem
• Dependent and Independent Events
• Bayes' Theorem
• Probability Distribution
• Binomial Distribution in Probability
• Binomial Mean and Standard Deviation - Probability | Class 12 Maths
• Bernoulli Trials and Binomial Distribution
• Discrete Random Variable
• Expected Value
• NCERT Solution for Class 12 Math PDF 2024-25
• RD Sharma Class 12 Solutions for Maths

Linear programming is a mathematical concept that is used to find the optimal solution of the linear function. This method uses simple assumptions for optimizing the given function. Linear Programming has a huge real-world application and it is used to solve various types of problems.

Linear programming is used in various industries such as shipping industries, manufacturing industries, transportation industries, telecommunications, and others.

Term “linear programming” consists of two words linear and programming, the word linear tells the relation between various types of variables of degree one used in a problem and the word programming tells us the step-by-step procedure to solve these problems.

In this article, we will learn about linear programming, its examples, formulas, and other concepts in detail.

Table of Content

What is Linear Programming? 

Components of linear programming, linear programming examples, linear programming problems, types of linear programming problems, linear programming formula, how to solve linear programming problems, linear programming methods, linear programming simplex method, linear programming graphical method, linear programming applications, importance of linear programming, up-to-date applications of linear programming, linear programming in operations research, simplex method.

Linear programming or Linear optimization is a technique that helps us to find the optimum solution for a given problem, an optimum solution is a solution that is the best possible outcome of a given particular problem.

In simple terms, it is the method to find out how to do something in the best possible way. With limited resources, you need to do the optimum utilization of resources and achieve the best possible result in a particular objective such as least cost, highest margin, or least time. 

The situation that requires a search for the best values of the variables subject to certain constraints is where we use linear programming problems. These situations cannot be handled by the usual calculus and numerical techniques.

Linear Programming Definition

Linear programming is the technique used for optimizing a particular scenario. Using linear programming provides us with the best possible outcome in a given situation. It uses all the available resources in a manner such that they produce the optimum result.

The basic components of a linear programming(LP) problem are:

• Decision Variables: Variables you want to determine to achieve the optimal solution.
• Objective Function: M athematical equation that represents the goal you want to achieve
• Constraints: Limitations or restrictions that your decision variables must follow.
• Non-Negativity Restrictions: In some real-world scenarios, decision variables cannot be negative

Additional Characteristics of Linear Programming

• Finiteness: The number of decision variables and constraints in an LP problem are finite.
• Linearity: The objective function and all constraints must be linear functions of the decision variables . It means the degree of variables should be one.

We can understand the situations in which Linear programming is applied with the help of the example discussed below,

Suppose a delivery man has to deliver 8 packets in a day to the different locations of a city. He has to pick all the packets from A and has to deliver them to points P, Q, R, S, T, U, V, and W. The distance between them is indicated using the lines as shown in the image below. The shortest path followed by the delivery man is calculated using the concept of Linear Programming.

Linear Programming Problems (LPP) involve optimizing a linear function to find the optimal value solution for the function. The optimal value can be either the maximum value or the minimum value.

In LPP, the linear functions are called objective functions. An objective function can have multiple variables, which are subjected to conditions and have to satisfy the linear constraints .

There are many different linear programming problems(LPP) but we will deal with three major linear programming problems in this article.

Manufacturing Problems

Manufacturing problems are a problem that deals with the number of units that should be produced or sold to maximize profits when each product requires fixed manpower, machine hours, and raw materials.

Diet Problems

It is used to calculate the number of different kinds of constituents to be included in the diet to get the minimum cost, subject to the availability of food and their prices.

Transportation Problems

It is used to determine the transportation schedule to find the cheapest way of transporting a product from plants /factories situated at different locations to different markets.

A linear programming problem consists of,

• Decision variables
• Objective function
• Constraints
• Non-Negative restrictions

Decision variables are the variables x, and y, which decide the output of the linear programming problem and represent the final solution. 

The objective function , generally represented by Z, is the linear function that needs to be optimized according to the given condition to get the final solution. 

The restrictions imposed on decision variables that limit their values are called constraints.

Now, the general formula of a linear programming problem is,

Objective Function : Z = ax + by

Constraints: cx + dy ≥ e, px + qy ≤ r

Non-Negative restrictions: x ≥ 0, y ≥ 0

In the above condition x, and y are the decision variables.

Before solving the linear programming problems first we have to formulate the problems according to the standard parameters. The steps for solving linear programming problems are,

Step 1: Mark the decision variables in the problem. Step 2: Build the objective function of the problem and check if the function needs to be minimized or maximized. Step 3: Write down all the constraints of the linear problems. Step 4: Ensure non-negative restrictions of the decision variables. Step 5: Now solve the linear programming problem using any method generally we use either the simplex or graphical method.

We use various methods for solving linear programming problems. The two most common methods used are,

• Graphical Method

Let’s learn about these two methods in detail in this article,

One of the most common methods to solve the linear programming problem is the simplex method. In this method, we repeat a specific condition ‘n’ a number of times until an optimum solution is achieved.

The steps required to solve linear programming problems using the simplex method are,

Step 1: Formulate the linear programming problems based on the given constraints. Step 2: Convert all the given inequalities to equations or equalities of the linear programming problems by adding the slack variable to each inequality where ever required. Step 3: Construct the initial simplex table. By representing each constraint equation in a row and writing the objective function at the bottom row. The table so obtained is called the Simplex table. Step 4: Identify the greatest negative entry in the bottom row the column of the element with the highest negative entry is called the pivot column Step 5: Divide the entries of the right-most column with the entries of the respective pivot column, excluding the entries of the bottommost row. Now the row containing the least entry is called the pivot row. The pivot element is obtained by the intersection of the pivot row and the pivot column. Step 6: Using matrix operation and with the help of the pivot element make all the entries in the pivot column to be zero. Step 7: Check for the non-negative entries in the bottommost row if there are no negative entries in the bottom row, end the process else start the process again from step 4. Step 8: The final simplex table so obtained gives the solution to our problem.

Graphical Method is another method than the Simplex method which is used to solve linear programming problems. As the name suggests this method uses graphs to solve the given linear programming problems. This is the best method to solve linear programming problems and requires less effort than the simplex method. 

While using this method we plot all the inequalities that are subjected to constraints in the given linear programming problems. As soon as all the inequalities of the given LPP are plotted in the XY graph the common region of all the inequalities gives the optimum solution. All the corner points of the feasible region are calculated and the value of the objective function at all those points is calculated then comparing these values we get the optimum solution of the LPP.

Example: Find the maximal and minimal value of z = 6x + 9y when the constraint conditions are,

• 2x + 3y ≤ 12
• x and y ≥ 0

Step 1 : First convert the inequations into normal equations. Hence the equations will be 2x+3y = 0, x = 0, y = 0 and x + y = 5. Step 2 : Find the points at which 2x + 3y and x + y = 5 cut the x-axis and y-axis. To find the point of intersection of the x-axis put y = 0 in the respective equation and find the point. Similarly for y-axis intersection points put x = 0 in the respective equation. Step 3 : Draw the two lines cutting the x-axis and y-axis. We find that the two axes cut each other at (3,2). Step 4 : For x ≥ 0 and y ≥ 0, we find that both inequations are followed. Hence the region will include an area region enclosed by two axes and both lines including the origin. The plotted region is shown below in the figure. Step 5 : Find Z for each point and maxima and minima. Coordinates Z = 6x + 9y (0,5) Z = 45 (0,4) Z = 36 (5,0) Z = 30 (6,0) Z = 36 (3,2) Z = 36 Hence, we find that Z = 6x + 9y is maximum at (0,5) and minimum at (5,0).

Linear Programming has applications in various fields. It is used to find the minimum cost of a process when all the constraints of the problems are given. It is used to optimize the transportation cost of the vehicle, etc. Various applications of Linear Programming are

Engineering Industries

Engineering Industries use linear programming to solve design and manufacturing problems and to get the maximum output from a given condition.

Manufacturing Industries

Manufacturing Industries use linear programming to maximize the profit of the companies and to reduce the manufacturing cost.

Energy Industries

Energy companies use linear programming to optimize their production output.

Transportation Industries

Linear programming is also used in transportation industries to find the path to minimize the cost of transportation.

Linear Programming has huge importance in various industries it maximizes the output value while minimizing the input values according to various constraints.

LP is highly applicable when we have multiple conditions while solving a problem and we have to optimize the output of the problem i.e. either we have to find the minimum or the maximum value according to a given condition.

Linear Inequalities Algebraic Solution of Linear Inequalities

Problem 1: A company manufactures and sells two types of products and the cost of production of each unit a and b is rupees 200 and 150 respectively each unit of product yields a profit of 20 rupees and each unit of product b yields a profit of 15 rupees on selling. The company estimates the monthly demand of A and B to be at a maximum of the harvested unit in all the production budget for the month is set at rupees 50000. How many units should the company manufacture to earn maximum profit from its monthly sales from a and b?

Let x = number of units of type A y = Number of units of type B Maximize Z = 40x + 50y Subject to the constraints 3x + y ≤ 9 x + 2y ≤ 8 and x, y ≥ 0 Consider the equation, 3x + y = 9 x = 3 y = 0 and x + 2y = 8 x = 8 y = 0 Now, we can determine the maximum value of Z by evaluating the value of Z at the four points (vertices) is shown below Vertices Z = 40x + 50y (0, 0) Z = 40 × 0 + 50 × 0 = Rs. 0 (3, 0) Z = 40 × 3 + 50 × 0 = Rs. 120 (0, 4)  Z = 40 × 0 + 50 × 4 = Rs. 200 (2, 3) Z = 40 × 2 + 50 × 3 = Rs. 230 Maximum profit, Z = Rs. 230 ∴ Number of units of type A is 2 and the number of units of type B is 3.

Problem 2: Maximize Z = 3x + 4y.

Subject to constraints , x + y ≤ 450, 2x + y ≤ 600 and x, y ≤ 0.

We have from the given Constraints (1) X + Y = 450 Putting x = 0, ⇒ 0 + y = 450 ⇒ y = 450 Putting y = 0, ⇒ x + 0 = 450 ⇒ x = 450 From, Constraints (2) 2x + y = 600 Putting x = 0, ⇒ 0 + y = 600 ⇒ y = 600 Putting  y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300 Now, we have the points co-ordinate Z = 3x + 4y

Therefore, the optimal solution maximum Z = 1800 at co-ordinate x = 0 and y = 450. The graph is given below.

Linear programming, a powerful mathematical technique, is used to solve optimization problems in various industries. Here are some modern applications:

• Supply Chain Optimization : Linear programming helps companies minimize costs and maximize efficiency in their supply chains. It’s used for determining the most cost-effective transportation routes, warehouse operations, and inventory management strategies.
• Energy Management : In the energy sector, linear programming is utilized to optimize the mix of energy production methods. This includes balancing traditional energy sources with renewable ones to reduce costs and environmental impact while meeting demand.
• Telecommunications Network Design : Linear programming aids in designing efficient telecommunications networks. It helps in allocating bandwidth, designing network layouts, and optimizing the flow of data to ensure high-speed communication at lower costs.
• Financial Planning : Businesses and financial analysts use linear programming for portfolio optimization, risk management, and capital budgeting. It helps in making investment decisions that maximize returns while minimizing risk.
• Healthcare Logistics : In healthcare, linear programming is applied to optimize the allocation of resources, such as hospital beds, medical staff, and equipment. It’s crucial for improving patient care, reducing wait times, and managing costs effectively.
• Manufacturing Process Optimization : Linear programming is used to determine the optimal production levels for multiple products within a manufacturing facility, considering constraints like labor, materials, and machine availability.
• Agricultural Planning : Farmers and agricultural planners use linear programming to decide on crop selection, land use, and resource allocation to maximize yields and profits while conserving resources.
• Airline Crew Scheduling : Airlines employ linear programming to schedule crews efficiently, ensuring that flights are staffed in compliance with regulations and minimizing operational costs.

These applications demonstrate the versatility and power of linear programming in solving complex optimization problems across various sectors, showcasing its relevance in today’s data-driven world.

• Core Tool : Linear programming is a foundational tool in operations research for optimizing resources.
• Decision Making : Helps in making the best decisions regarding resource allocation, maximizing profits, or minimizing costs.
• Wide Applications : Used in various fields such as logistics, manufacturing, finance, and healthcare for solving complex problems.
• Modeling Real-World Problems : Transforms real-world problems into mathematical models to find the most efficient solutions.
• Optimization Algorithm : The Simplex Method is a powerful algorithm used in linear programming to find the optimal solution to linear inequalities.
• Step-by-Step Approach : It iteratively moves towards the best solution by navigating the edges of the feasible region defined by constraints.
• Efficiency : Known for its efficiency in solving large-scale linear programming problems.
• Versatility : Applicable in various domains like diet planning, network flows, production scheduling, and more, showcasing its versatility.

Linear Programming – FAQs

What is linear programming.

Linear programming is a mathematical concept which is used to optimize a given linear problem which has a variety of constraints. Using linear programming we the optimum output of the given problem

What are Linear Programming Problems?

Linear Programming Problems (LPP) are the problems which give the optimum solution to the given conditions.

What is Linear Programming Formula?

General Linear Programming Formulas are, Objective Function: Z = ax + by Constraints: px + qy ≤ r, sx + ty ≤ u Non-Negative Restrictions: x ≥ 0, y ≥ 0

What are the different types of Linear Programming?

Different types of linear programming methods are, Linear Programming by Simplex Method Linear Programming by R Method Linear Programming by Graphical Method

What are requirements of Linear Programming?

Various requirements of linear programming problems are, Linearity Objective Function Constraints Non-negativity

What are the advantages of Linear Programming?

Various advantages of linear programming are, It provides the optimal solution to any given linear problem. It is easy to use and always gives consistent results It helps to maximize profits and to reduce the input cost.

Please Login to comment...

Similar reads.

• Math-Concepts
• Maths-Class-12
• Technical Scripter 2020
• Mathematics
• School Learning
• Technical Scripter

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• Math Article
• Linear Programming Problem Lpp

Linear programming problem (LPP)

Linear Programming Problems (LPP): Linear programming or linear optimization is a process which takes into consideration certain linear relationships to obtain the best possible solution to a mathematical model. It is also denoted as LPP. It includes problems dealing with maximizing profits, minimizing costs, minimal usage of resources, etc. These problems can be solved through the simplex method or graphical method.

The Linear programming applications are present in broad disciplines such as commerce, industry, etc. In this section, we will discuss, how to do the mathematical formulation of the LPP.

Mathematical Formulation of Problem

Let x and y be the number of cabinets of types 1 and 2 respectively that he must manufacture. They are non-negative and known as non-negative constraints.

The company can invest a total of 540 hours of the labour force and is required to create up to 50 cabinets. Hence,

15x + 9y <= 540

x + y <= 50

The above two equations are known as linear constraints.

Let Z be the profit he earns from manufacturing x and y pieces of the cabinets of types 1 and 2. Thus,

Z = 5000x + 3000y

Our objective here is to maximize Z. Hence Z is known as the objective function. To find the answer to this question, we use graphs, which is known as the graphical method of solving LPP. We will cover this in the subsequent sections.

Graphical Method

The solution for problems based on linear programming is determined with the help of the feasible region, in case of graphical method. The feasible region is basically the common region determined by all constraints including non-negative constraints, say, x,y≥0, of an LPP. Each point in this feasible region represents the feasible solution of the constraints and therefore, is called the solution/feasible region for the problem. The region apart from (outside) the feasible region is called as the infeasible region .

The optimal value (maximum and minimum) obtained of an objective function in the feasible region at any point is called an optimal solution. To learn the graphical method to solve linear programming completely reach us.

Linear Programming Applications

Let us take a real-life problem to understand linear programming. A home décor company received an order to manufacture cabinets. The first consignment requires up to 50 cabinets. There are two types of cabinets. The first type requires 15 hours of the labour force (per piece) to be constructed and gives a profit of Rs 5000 per piece to the company. Whereas, the second type requires 9 hours of the labour force and makes a profit of Rs 3000 per piece. However, the company has only 540 hours of workforce available for the manufacture of the cabinets. With this information given, you are required to find a deal which gives the maximum profit to the décor company.

Given the situation, let us take up different scenarios to analyse how the profit can be maximized.

• He decides to construct all the cabinets of the first type. In this case, he can create 540/15 = 36 cabinets. This would give him a profit of Rs 5000 × 36 = Rs 180,000.
• He decides to construct all the cabinets of the second type. In this case, he can create 540/9 = 60 cabinets. But the first consignment requires only up to 50 cabinets. Hence, he can make profit of Rs 3000 × 50 = Rs 150,000.
• He decides to make 15 cabinets of type 1 and 35 of type 2. In this case, his profit is (5000 × 15 + 3000 × 35) Rs 180,000.

Similarly, there can be many strategies which he can devise to maximize his profit by allocating the different amount of labour force to the two types of cabinets. We do a mathematical formulation of the discussed LPP to find out the strategy which would lead to maximum profit.

Related Links

To learn more about solving LPP, download BYJU’S The Learning App.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

• Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.