example of assignment problem in linear programming

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

Machine Learning Geek

Boost Your Machine Learning Knowledge

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

Solving Staff Scheduling Problem using Linear Programming

Keras Tutorial for Beginners

apply() in Pandas

• Number System and Arithmetic
• Trigonometry
• Probability
• Mensuration
• Linear Algebra
• CBSE Class 8 Maths Formulas
• CBSE Class 9 Maths Formulas
• CBSE Class 10 Maths Formulas
• CBSE Class 11 Maths Formulas

• Explore Our Geeks Community
• CBSE Class 12 Maths Notes

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
• 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
• 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
• 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

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
• 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 Solutions for Class 12 Maths
• 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. The 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 others in detail.

What is Linear Programming? 

Linear programming 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 given limited resources you need to do the optimum utilization of resources to achieve the best possible result in a particular objective. such as least cost, highest margin, or least time. 

The situation which 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.

Components of Linear Programming

A linear programming problem has two basic parts:

• First Part: It is the objective function that describes the primary purpose of the formation to maximize some return or to minimize some.
• Second Part: It is a constant set, It is the system of equalities or inequalities that describe the condition or constraints of the restriction under which Optimisation is to be accomplished.

Linear Programming Examples

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.

Types of Linear Programming Problems

Basically, there are many different linear programming problems 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 in order 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 in order 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.

Linear Programming Formula

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.

How to Solve Linear Programming Problems?

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.

Linear Programming Methods

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

• Simplex Method
• Graphical Method

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

Linear Programming Simplex Method

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’ 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.

Linear Programming Graphical Method

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 Applications

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.

Importance of Linear Programming

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

Linear Programming Problems

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 b 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 in order 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 ∴ The 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.

Solution: 

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.

FAQs on Linear Programming

Q1: 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

Q2: What are Linear Programming Problems?

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

Q3: 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

Q4: 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

Q5: What are requirements of Linear Programming?

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

Q6: 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...

• satyam_sharma
• vedantkingh
• Maths-Class-12
• Technical Scripter 2020
• School Learning
• School Mathematics
• Technical Scripter

Please write us at contrib[email protected] to report any issue with the above content

Improve your Coding Skills with Practice

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

Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey

Get full access to Quantitative Techniques: Theory and Problems and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

WHAT IS ASSIGNMENT PROBLEM

Assignment Problem is a special type of linear programming problem where the objective is to minimise the cost or time of completing a number of jobs by a number of persons.

The assignment problem in the general form can be stated as follows:

“Given n facilities, n jobs and the effectiveness of each facility for each job, the problem is to assign each facility to one and only one job in such a way that the measure of effectiveness is optimised (Maximised or Minimised).”

Several problems of management has a structure identical with the assignment problem.

Example I A manager has four persons (i.e. facilities) available for four separate jobs (i.e. jobs) and the cost of assigning (i.e. effectiveness) each job to each ...

Get Quantitative Techniques: Theory and Problems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Linear Programming Problems, Solutions & Applications [With Example]

Data science has many applications, one of the most prominent among them is optimization. We all tend to focus on optimizing stuff. Optimization focuses on getting the most desired results with the limited resources you have.

There are all sorts of optimization problems available, some are small, some are highly complicated. While going through them, you’ll find a specific category called linear programming problems. In this article, we’ve discussed what they are and how you can work on them. 

Suppose you’re a fruit seller who can either buy oranges or apples or a certain combination of them both. However you only have a budget of INR 5,000 and you can only store 30 bags of them. Now, you have to buy them in the way that yields you the highest profit.

Now one bag of oranges costs you INR 500 while a bag of apples costs you INR 750. You can make INR 100 from the sale of one bag of oranges and INR 200 from the sale of one bag of apples. 

This problem has various possibilities. You might choose to only buy oranges but then, you’d only have 10 bags in your storage and your profit would be INR 1000. Similarly, you might choose to only buy apples and make INR 1500 as profit. You can also buy a combination of the two. 

Such problems are called linear programming problems and we’ll discuss them in detail. Let’s get started:

What is Linear Programming?

Linear programming is a method of depicting complex relationships by using linear functions. Our aim with linear programming is to find the most suitable solutions for those functions. The real relationship between two points can be highly complex, but we can use linear programming to depict them with simplicity. Linear programming finds applications in many industries. 

Check out our data science online courses to upskill yourself

Basics of Linear Programming

Here are some fundamental terms of linear programming:

The limitations (or restrictions) of your decision variables are called constraints. Most of the time constraints are the limitations you have on your resources for solving a problem. 

Decision Variable

These variables define your output. Your result depends on these variables, that’s why we call them ‘decision variables’. 

Non-negativity Restriction

The decision variables of a linear programming problem can only have non-negative value. It means the values for your decision variables can be equal to or greater than zero only. 

Objective Function

The objective function is the objective of making your decision. In simple terms it is the final result of your linear programming problem. For example, when you’re finding the maximum profit you can make with a given set of resources, the maximum profit is the objective function.

Formulating Linear Programming Problems

You should know how to formulate a linear programming to apply it in real-life. Suppose you are a manufacturer of toys and you only produce two toys: A and B. Roughly speaking, your toys require two resources X and Y to manufacture. Here are the requirements of your toys:

• One unit of toy A requires you one unit of resource X and three units of resource Y
• One unit of toy B requires one unit of resource X and two units of resource Y

You have five units of resource X and 12 units of resource Y. Your profit margins on the sale of these toys are:

• INR 6 on each sold unit of toy A
• INR 5 on each sold unit of toy B

How many units of each toy would you produce to get the maximum profit?

The Solution

Let’s represent our linear programming problem in an equation:

Z = 6a + 5b

Here, z stands for the total profit, a stands for the total number of toy A units and b stands for total number to B units. Our aim is to maximize the value of Z (the profit). 

Now, your company would want to produce as many units of these toys as possible, but you have limited resources. The limitations on our resources are the constraints of this problem. We only have a total of

Now every unit of toy A and B requires 3 and 2 units of resource Y respectively. And we only have a total of 12 units of resource Y so mathematically, it would look like this:

Remember that the values for the units of toy A can be in integers only. This means we also have the constraints of a->0 and b<-0. 

So, now you have a proper linear programming problem. You can formulate other linear programming problems by following this example. While this example was quite simple, LP problems can become highly complicated. 

Read: Linear Programming Project Ideas & Topics

upGrad’s Exclusive Data Science Webinar for you –

ODE Thought Leadership Presentation

Explore our Popular Data Science Online Courses

Steps of formulating linear programming problems.

To formulate a linear programming problem, follow these steps:

• Find the decision variables
• Find the objective function
• Identify the constraints
• Remember the non-negativity restriction

If a problem meets the above criteria, it is a linear programming problem. It’s best practice to keep this criterion in mind when you’re working on identifying the type of the problem. 

Solving Linear Programming Problems with R

If you’re using R, solving linear programming problems becomes much simpler. That’s because R has the lpsolve package which comes with various functions specifically designed for solving such problems. It’s highly probable that you’ll be using R very frequently to solve LP problems as a data scientist. That’s why we’ve shared two distinct examples to help you understand its implementation better:

Let’s start with a basic problem. An organization has two products with selling prices of INR 25 and INR 20 and are called product A and B respectively. Every day, they have 1800 units of resources to produce these products. Product A requires 20 resources units and B requires 12 resources units. The production time for both of these products is four minutes and the organization gets a total of eight working hours every day. The problem is, what should be the production quantity for each of these products to maximize the company’s profits?

We’ll start solving this problem by defining its objective function:

max(Sales) = max( 25 y 1 + 20 y 2 )

Here, 25 and 20 are the prices of product A and B respectively, y1 is the total units of product A produced and y2 is the total units of product B produced. Our decision variables are y1 and y2. 

Top Data Science Skills to Learn to upskill

We’ll now set the constraints for our problem:

Resource constraint:

20 y 1 + 12 y 2 1800

Time constraint:

4 y 1 + 4 y 2 8*60

We aim to find the correct number of products we have to manufacture to get the maximum profit. 

Using R to Solve the Problem:

We’ll use lpsolve to solve this LP problem and start with setting the objective function:

> require(lpSolve)

Loading required package: lpSolve

> objective.in  <- c(25, 20)

> objective.in

Then we’ll build a matrix for the constraints:

> const <- matrix(c(20,  12, 4, 4), nrow=2, byrow=TRUE)

     [,1] [,2]

[1,]   20 12

[2,]    4 4

> time_constraints <- (8*60)

> resource_constraints <- 1800

> time_constraints

> resource_constraints

Let’s now create the already-defined equations:

> rhs <- c(resource_constraints, time_constraints)

[1] 1800  480

> direction  <- c(“<=”, “<=”)

> direction

[1] “<=” “<=”

Once all the necessary information is added, we can start finding the optimal answer. The syntax for our package is:

lp( direction, objective, const.mat, const.dir, const.rhs )

> optimum <-  lp(direction=”max”,  objective.in, const, direction,  rhs)

> optimum

Success: the objective function is 2625

> summary(optimum)

                 Length Class Mode     

direction        1 -none- numeric  

x.count          1 -none- numeric  

objective        2 -none- numeric  

const.count      1 -none- numeric  

constraints      8 -none- numeric  

int.count        1 -none- numeric  

int.vec          1 -none- numeric  

bin.count        1 -none- numeric  

binary.vec       1 -none- numeric  

num.bin.solns    1 -none- numeric  

objval           1 -none- numeric  

solution         2 -none- numeric  

presolve         1 -none- numeric  

compute.sens     1 -none- numeric  

sens.coef.from   1 -none- numeric  

sens.coef.to     1 -none- numeric  

duals            1 -none- numeric  

duals.from       1 -none- numeric  

duals.to         1 -none- numeric  

scale            1 -none- numeric  

use.dense        1 -none- numeric  

dense.col        1 -none- numeric  

dense.val        1 -none- numeric  

dense.const.nrow 1      -none- numeric 

dense.ctr        1 -none- numeric  

use.rw           1 -none- numeric  

tmp              1 -none- character

status           1 -none- numeric

After running the code above, you can get the desired solutions for our problem.

The optimum values for y1 and y2:

Remember that y1 and y2 were the units of product A and product B we had to produce:

> optimum$solution

The optimum sales figure:

The maximum profit we can generate with the obtained values of y1 and y2 is:

> optimum$objval

Also Read:  Linear Algebra For Machine Learning

Read our popular Data Science Articles

Uses of linear programming.

As we mentioned before, linear programming finds applications in many industries. Here are some areas where we use it:

• With the rising popularity of delivery services, linear programming has become one of the most favoured methods of finding the optimum routes. When you take an Ola or Uber, the software would use linear programming to find the best route. Delivery companies like Amazon and FedEx also use it to determine the best routes for their delivery men. They focus on reducing the delivery time and cost. 
• Machine learning’s supervised learning works on the fundamental concepts of linear programming. In supervised learning, you have to find the optimal mathematical model to predict the output according to the provided input data.
• The retail sector uses linear programming for optimizing shelf space. With so many brands and products available, determining where to place them in the store is a very rigorous task. The placement of a product in the store can affect its sales greatly. Major retail chains such as Big Bazaar, Reliance, Walmart, etc. use linear programming for determining product placement. They have to keep the consumers’ interest in mind while ensuring the best product placement to yield maximum profit. 
• Companies use linear programming to improve their supply chains. The efficiency of a supply chain depends on many factors such as the chosen routes, timings, etc. By using linear programming, they can find the best routes, timings, and other allocations of resources to optimize their efficiency. 

Learn More about Linear Programming and Data Science

Linear programming is one of the most vital concepts of data science. It is also a fundamental topic that you should know about to become a proficient data scientist. As we discussed, there are many applications for this concept and you can find its use cases in your daily life. 

You can learn more about data science and its related concepts, by going to our blog. We have many valuable resources to help you learn more. Here are some for your further reading:

• Top Reasons to become a Data Scientist
• The Algorithms Every Data Scientist Should Know
• How to Become a Data Scientist

On the other hand, you can get a data science course to learn from industry experts. You’ll get to learn interactively through videos, quizzes, and projects. Taking a course will help you learn the necessary skills to become a professional data scientist. Check out IIIT-B & upGrad’s  PG Diploma in Data Science  which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.

Rohit Sharma

Something went wrong

Our Popular Data Science Course

Data Science Skills to Master

• Data Analysis Courses
• Inferential Statistics Courses
• Hypothesis Testing Courses
• Logistic Regression Courses
• Linear Regression Courses
• Linear Algebra for Analysis Courses

Our Trending Data Science Courses

• Data Science for Managers from IIM Kozhikode - Duration 8 Months
• Executive PG Program in Data Science from IIIT-B - Duration 12 Months
• Master of Science in Data Science from LJMU - Duration 18 Months
• Executive Post Graduate Program in Data Science and Machine LEarning - Duration 12 Months
• Master of Science in Data Science from University of Arizona - Duration 24 Months

Frequently Asked Questions (FAQs)

Optimization is a way of life for many people. Everything utilizes optimization, from how you spend your time to how you solve supply chain issues for your organization. It's a very fascinating and relevant issue in data science. Linear Programming is one of the most effective methods for doing optimization. It aids in the solution of specific extremely complicated optimization problems by making more easy assumptions. As an analyst, you will undoubtedly come across applications and situations that need Linear Programming. Machine Learning takes advantage of optimizations as well. Supervised learning builds on the foundations of Linear Programming. A system is trained to fit a mathematical model of a function using labeled input data to predict values from unknown test data.

Linear programming is a necessary skill for anyone interested in machine learning/data science. Everything in machine learning and deep learning is about optimization. Convex or nonconvex optimization is used in ML algorithms. The key difference between the two categories is that there can only be one optimal solution in convex optimization, which is globally optimal, or you can prove that there is no feasible solution to the problem. In contrast, in nonconvex optimization, there can be multiple locally optimal points. It can take a long time to determine whether the problem has no solution or if the answer is global.

Professionals can use linear programming in a wide range of disciplines of study. It is often used in mathematics and to a lesser extent in business, economics, and some engineering difficulties. Transportation, energy, telecommunications, and manufacturing are among the industries that employ linear programming methods. It is beneficial in simulating a wide range of problems in planning, routing, scheduling, assignment, and design. Certain specific instances of linear programming, such as network flow issues and multicommodity flow problems, are deemed significant enough to warrant extensive study on specialized methods to solve them. To stabilize YouTube videos, Google employs linear programming.

Explore Free Courses

Learn more about the education system, top universities, entrance tests, course information, and employment opportunities in Canada through this course.

Advance your career in the field of marketing with Industry relevant free courses

Build your foundation in one of the hottest industry of the 21st century

Master industry-relevant skills that are required to become a leader and drive organizational success

Build essential technical skills to move forward in your career in these evolving times

Get insights from industry leaders and career counselors and learn how to stay ahead in your career

Kickstart your career in law by building a solid foundation with these relevant free courses.

Stay ahead of the curve and upskill yourself on Generative AI and ChatGPT

Build your confidence by learning essential soft skills to help you become an Industry ready professional.

Learn more about the education system, top universities, entrance tests, course information, and employment opportunities in USA through this course.

Suggested Blogs

by Rohit Sharma

04 Oct 2023

03 Oct 2023

by Keerthi Shivakumar

26 Sep 2023

20 Sep 2023

19 Sep 2023

17 Sep 2023

15 Sep 2023

14 Sep 2023

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.

Assignment Model | Linear Programming Problem (LPP) | Introduction

What is assignment model.

→ Assignment model is a special application of Linear Programming Problem (LPP) , in which the main objective is to assign the work or task to a group of individuals such that;

i) There is only one assignment.

ii) All the assignments should be done in such a way that the overall cost is minimized (or profit is maximized, incase of maximization).

→ In assignment problem, the cost of performing each task by each individual is known. → It is desired to find out the best assignments, such that overall cost of assigning the work is minimized.

For example:

Suppose there are 'n' tasks, which are required to be performed using 'n' resources.

The cost of performing each task by each resource is also known (shown in cells of matrix)

• In the above asignment problem, we have to provide assignments such that there is one to one assignments and the overall cost is minimized.

How Assignment Problem is related to LPP? OR Write mathematical formulation of Assignment Model.

→ Assignment Model is a special application of Linear Programming (LP).

→ The mathematical formulation for Assignment Model is given below:

→ Let, C i j \text {C}_{ij} C ij ​ denotes the cost of resources 'i' to the task 'j' ; such that

→ Now assignment problems are of the Minimization type. So, our objective function is to minimize the overall cost.

→ Subjected to constraint;

(i) For all j t h j^{th} j t h task, only one i t h i^{th} i t h resource is possible:

(ii) For all i t h i^{th} i t h resource, there is only one j t h j^{th} j t h task possible;

(iii) x i j x_{ij} x ij ​ is '0' or '1'.

Types of Assignment Problem:

(i) balanced assignment problem.

• It consist of a suqare matrix (n x n).
• Number of rows = Number of columns

(ii) Unbalanced Assignment Problem

• It consist of a Non-square matrix.
• Number of rows ≠ \not=  = Number of columns

Methods to solve Assignment Model:

(i) integer programming method:.

In assignment problem, either allocation is done to the cell or not.

So this can be formulated using 0 or 1 integer.

While using this method, we will have n x n decision varables, and n+n equalities.

So even for 4 x 4 matrix problem, it will have 16 decision variables and 8 equalities.

So this method becomes very lengthy and difficult to solve.

(ii) Transportation Methods:

As assignment problem is a special case of transportation problem, it can also be solved using transportation methods.

In transportation methods ( NWCM , LCM & VAM), the total number of allocations will be (m+n-1) and the solution is known as non-degenerated. (For eg: for 3 x 3 matrix, there will be 3+3-1 = 5 allocations)

But, here in assignment problems, the matrix is a square matrix (m=n).

So total allocations should be (n+n-1), i.e. for 3 x 3 matrix, it should be (3+3-1) = 5

But, we know that in 3 x 3 assignment problem, maximum possible possible assignments are 3 only.

So, if are we will use transportation methods, then the solution will be degenerated as it does not satisfy the condition of (m+n-1) allocations.

So, the method becomes lengthy and time consuming.

(iii) Enumeration Method:

It is a simple trail and error type method.

Consider a 3 x 3 assignment problem. Here the assignments are done randomly and the total cost is found out.

For 3 x 3 matrix, the total possible trails are 3! So total 3! = 3 x 2 x 1 = 6 trails are possible.

The assignments which gives minimum cost is selected as optimal solution.

But, such trail and error becomes very difficult and lengthy.

If there are more number of rows and columns, ( For eg: For 6 x 6 matrix, there will be 6! trails. So 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720 trails possible) then such methods can't be applied for solving assignments problems.

(iv) Hungarian Method:

It was developed by two mathematicians of Hungary. So, it is known as Hungarian Method.

It is also know as Reduced matrix method or Flood's technique.

There are two main conditions for applying Hungarian Method:

(1) Square Matrix (n x n). (2) Problem should be of minimization type.

Suggested Notes:

Unbalanced Transportation Problem Numerical

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

Critical Path Method [CPM] - Steps and Introduction | Network Analysis | Operation Research

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

Linear Programming Problem (LPP) Formulation with Numericals

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.

Linear Programming

Linear programming is a process that is used to determine the best outcome of a linear function. It is the best method to perform linear optimization by making a few simple assumptions. The linear function is known as the objective function. Real-world relationships can be extremely complicated. However, linear programming can be used to depict such relationships, thus, making it easier to analyze them.

Linear programming is used in many industries such as energy, telecommunication, transportation, and manufacturing. This article sheds light on the various aspects of linear programming such as the definition, formula, methods to solve problems using this technique, and associated linear programming examples.

What is Linear Programming?

Linear programming, also abbreviated as LP, is a simple method that is used to depict complicated real-world relationships by using a linear function . The elements in the mathematical model so obtained have a linear relationship with each other. Linear programming is used to perform linear optimization so as to achieve the best outcome.

Linear Programming Definition

Linear programming can be defined as a technique that is used for optimizing a linear function in order to reach the best outcome. This linear function or objective function consists of linear equality and inequality constraints. We obtain the best outcome by minimizing or maximizing the objective function .

Linear Programming Examples

Suppose a postman has to deliver 6 letters in a day from the post office (located at A) to different houses (U, V, W, Y, Z). The distance between the houses is indicated on the lines as given in the image. If the postman wants to find the shortest route that will enable him to deliver the letters as well as save on fuel then it becomes a linear programming problem. Thus, LP will be used to get the optimal solution which will be the shortest route in this example.

Linear Programming Formula

A linear programming problem will consist of decision variables , an objective function, constraints, and non-negative restrictions. The decision variables, x, and y, decide the output of the LP problem and represent the final solution. The objective function, Z, is the linear function that needs to be optimized (maximized or minimized) to get the solution. The constraints are the restrictions that are imposed on the decision variables to limit their value. The decision variables must always have a non-negative value which is given by the non-negative restrictions. The general formula of a linear programming problem is given below:

• Objective Function: Z = ax + by
• Constraints: cx + dy ≤ e, fx + gy ≤ h. The inequalities can also be "≥"
• Non-negative restrictions: x ≥ 0, y ≥ 0

How to Solve Linear Programming Problems?

The most important part of solving linear programming problem is to first formulate the problem using the given data. The steps to solve linear programming problems are given below:

• Step 1: Identify the decision variables.
• Step 2: Formulate the objective function. Check whether the function needs to be minimized or maximized.
• Step 3: Write down the constraints.
• Step 4: Ensure that the decision variables are greater than or equal to 0. (Non-negative restraint)
• Step 5: Solve the linear programming problem using either the simplex or graphical method.

Let us study about these methods in detail in the following sections.

Linear Programming Methods

There are two main methods available for solving linear programming problem. These are the simplex method and the graphical method. Given below are the steps to solve a linear programming problem using both methods.

Linear Programming by Simplex Method

The simplex method in lpp can be applied to problems with two or more decision variables. Suppose the objective function Z = 40\(x_{1}\) + 30\(x_{2}\) needs to be maximized and the constraints are given as follows:

\(x_{1}\) + \(x_{2}\) ≤ 12

2\(x_{1}\) + \(x_{2}\) ≤ 16

\(x_{1}\) ≥ 0, \(x_{2}\) ≥ 0

Step 1: Add another variable, known as the slack variable, to convert the inequalities into equations. Also, rewrite the objective function as an equation .

- 40\(x_{1}\) - 30\(x_{2}\) + Z = 0

\(x_{1}\) + \(x_{2}\) + \(y_{1}\) =12

2\(x_{1}\) + \(x_{2}\) + \(y_{2}\) =16

\(y_{1}\) and \(y_{2}\) are the slack variables.

Step 2: Construct the initial simplex matrix as follows:

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 1&1 &1 &0 &0 &12 \\ 2& 1 & 0& 1 & 0 & 16 \\ -40&-30&0&0&1&0 \end{bmatrix}\)

Step 3: Identify the column with the highest negative entry. This is called the pivot column. As -40 is the highest negative entry, thus, column 1 will be the pivot column.

Step 4: Divide the entries in the rightmost column by the entries in the pivot column. We exclude the entries in the bottom-most row.

12 / 1 = 12

The row containing the smallest quotient is identified to get the pivot row. As 8 is the smaller quotient as compared to 12 thus, row 2 becomes the pivot row. The intersection of the pivot row and the pivot column gives the pivot element.

Thus, pivot element = 2.

Step 5: With the help of the pivot element perform pivoting, using matrix properties , to make all other entries in the pivot column 0.

Using the elementary operations divide row 2 by 2 (\(R_{2}\) / 2)

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 1&1 &1 &0 &0 &12 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ -40&-30&0&0&1&0 \end{bmatrix}\)

Now apply \(R_{1}\) = \(R_{1}\) - \(R_{2}\)

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1/2 &1 &-1/2 &0 &4 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ -40&-30&0&0&1&0 \end{bmatrix}\)

Finally \(R_{3}\) = \(R_{3}\) + 40\(R_{2}\) to get the required matrix.

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1/2 &1 &-1/2 &0 &4 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ 0&-10&0&20&1&320 \end{bmatrix}\)

Step 6: Check if the bottom-most row has negative entries. If no, then the optimal solution has been determined. If yes, then go back to step 3 and repeat the process. -10 is a negative entry in the matrix thus, the process needs to be repeated. We get the following matrix.

\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1 &2 &-1 &0 &8 \\ 1& 0 & -1& 1 & 0 & 4 \\ 0&0&20&10&1&400 \end{bmatrix}\)

Writing the bottom row in the form of an equation we get Z = 400 - 20\(y_{1}\) - 10\(y_{2}\). Thus, 400 is the highest value that Z can achieve when both \(y_{1}\) and \(y_{2}\) are 0.

Also, when \(x_{1}\) = 4 and \(x_{2}\) = 8 then value of Z = 400

Thus, \(x_{1}\) = 4 and \(x_{2}\) = 8 are the optimal points and the solution to our linear programming problem.

Linear Programming by Graphical Method

If there are two decision variables in a linear programming problem then the graphical method can be used to solve such a problem easily.

Suppose we have to maximize Z = 2x + 5y.

The constraints are x + 4y ≤ 24, 3x + y ≤ 21 and x + y ≤ 9

where, x ≥ 0 and y ≥ 0.

To solve this problem using the graphical method the steps are as follows.

Step 1: Write all inequality constraints in the form of equations.

x + 4y = 24

3x + y = 21

Step 2: Plot these lines on a graph by identifying test points.

x + 4y = 24 is a line passing through (0, 6) and (24, 0). [By substituting x = 0 the point (0, 6) is obtained. Similarly, when y = 0 the point (24, 0) is determined.]

3x + y = 21 passes through (0, 21) and (7, 0).

x + y = 9 passes through (9, 0) and (0, 9).

Step 3: Identify the feasible region. The feasible region can be defined as the area that is bounded by a set of coordinates that can satisfy some particular system of inequalities.

Any point that lies on or below the line x + 4y = 24 will satisfy the constraint x + 4y ≤ 24.

Similarly, a point that lies on or below 3x + y = 21 satisfies 3x + y ≤ 21.

Also, a point lying on or below the line x + y = 9 satisfies x + y ≤ 9.

The feasible region is represented by OABCD as it satisfies all the above-mentioned three restrictions.

Step 4: Determine the coordinates of the corner points. The corner points are the vertices of the feasible region.

B = (6, 3). B is the intersection of the two lines 3x + y = 21 and x + y = 9. Thus, by substituting y = 9 - x in 3x + y = 21 we can determine the point of intersection.

C = (4, 5) formed by the intersection of x + 4y = 24 and x + y = 9

Step 5: Substitute each corner point in the objective function. The point that gives the greatest (maximizing) or smallest (minimizing) value of the objective function will be the optimal point.

33 is the maximum value of Z and it occurs at C. Thus, the solution is x = 4 and y = 5.

Applications of Linear Programming

Linear programming is used in several real-world applications. It is used as the basis for creating mathematical models to denote real-world relationships. Some applications of LP are listed below:

• Manufacturing companies make widespread use of linear programming to plan and schedule production.
• Delivery services use linear programming to decide the shortest route in order to minimize time and fuel consumption.
• Financial institutions use linear programming to determine the portfolio of financial products that can be offered to clients.

Related Articles:

• Introduction to Graphing
• Linear Equations in Two Variables
• Solutions of a Linear Equation
• Mathematical Induction

Important Notes on Linear Programming

• Linear programming is a technique that is used to determine the optimal solution of a linear objective function.
• The simplex method in lpp and the graphical method can be used to solve a linear programming problem.
• In a linear programming problem, the variables will always be greater than or equal to 0.

As the minimum value of Z is 127, thus, B (3, 28) gives the optimal solution. Answer: The minimum value of Z is 127 and the optimal solution is (3, 28)

• Example 3: Using the simplex method in lpp solve the linear programming problem Minimize Z = \(x_{1}\) + 2\(x_{2}\) + 3\(x_{3}\) \(x_{1}\) + \(x_{2}\) + \(x_{3}\) ≤ 12 2\(x_{1}\) + \(x_{2}\) + 3\(x_{3}\) ≤ 18 \(x_{1}\), \(x_{2}\), \(x_{3}\) ≥ 0 Solution: Convert all inequalities to equations by introducing slack variables. -\(x_{1}\) - 2\(x_{2}\) - 3\(x_{3}\) + Z = 0 \(x_{1}\) + \(x_{2}\) + \(x_{3}\) + \(y_{1}\) = 12 2\(x_{1}\) + \(x_{2}\) + 3\(x_{3}\) + \(y_{2}\) = 18 Expressing this as a matrix we get, \(\begin{bmatrix} x_{1} & x_{2} & x_{3} & y_{1} & y_{2} & Z & \\ 1 & 1 & 1 & 1 & 0 & 0 & 12\\ 2 & 1 & 3 & 0 & 1 & 0 & 18\\ -1 & -2 & -3 & 0 & 0 & 1 & 0 \end{bmatrix}\) As -3 is the greatest negative value thus, column 3 is the pivot column. 12 / 1 = 12 18 / 3 = 6 As 6 is the smaller quotient thus, row 2 is the pivot row and 3 is the pivot element. By applying matrix operations we get, \(\begin{bmatrix} x_{1} & x_{2} & x_{3} & y_{1} & y_{2} & Z & \\ 0.33 & 0.667 & 0 & 1 & -0.33 & 0 & 6\\ 0.667 & 0.33 & 1 & 0 & 0.33 & 0 & 6\\ 1 & -1 & 0 & 0 & 1 & 1 & 18 \end{bmatrix}\) Now -1 needs to be eliminated. Thus, by repreating the steps the matrix so obtained is as follows \(\begin{bmatrix} x_{1} & x_{2} & x_{3} & y_{1} & y_{2} & Z & \\ 0.5 & 1 & 0 & 1.5 & 0.5 & 0 & 9\\ 0.5 & 0 & 1 & -0.5 & 0.5 & 0 & 3\\ 1.5 & 0 & 0 & 1.5 & 0.5 & 1 & 27 \end{bmatrix}\) We get the maximum value of Z = 27 at \(x_{1}\) = 0, \(x_{2}\) = 9 \(x_{3}\) = 3 Answer: Maximum value of Z = 27 and optimal solution (0, 9, 3)

go to slide go to slide go to slide

Book a Free Trial Class

Practice Questions on Linear Programming

go to slide go to slide

FAQs on Linear Programming

What is meant by linear programming.

Linear programming is a technique that is used to identify the optimal solution of a function wherein the elements have a linear relationship.

What is Linear Programming Formula?

The general formula for a linear programming problem is given as follows:

What is the Objective Function in Linear Programming Problems?

The objective function is the linear function that needs to be maximized or minimized and is subject to certain constraints. It is of the form Z = ax + by.

How to Formulate a Linear Programming Model?

The steps to formulate a linear programming model are given as follows:

• Identify the decision variables.
• Formulate the objective function.
• Identify the constraints.
• Solve the obtained model using the simplex or the graphical method.

How to Find Optimal Solution in Linear Programming?

We can find the optimal solution in a linear programming problem by using either the simplex method or the graphical method. The simplex method in lpp can be applied to problems with two or more variables while the graphical method can be applied to problems containing 2 variables only.

How to Find Feasible Region in Linear Programming?

To find the feasible region in a linear programming problem the steps are as follows:

• Draw the straight lines of the linear inequalities of the constraints.
• Use the "≤" and "≥" signs to denote the feasible region of each constraint.
• The region common to all constraints will be the feasible region for the linear programming problem.

What are Linear Programming Uses?

Linear programming is widely used in many industries such as delivery services, transportation industries, manufacturing companies, and financial institutions. The linear program is solved through linear optimization method, and it is used to determine the best outcome in a given scenerio.

• 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: Linear Programming - The Simplex Method

• Last updated
• Save as PDF
• Page ID 37816

• Rupinder Sekhon and Roberta Bloom
• De Anza College

Learning Objectives

In this chapter, you will:

• Investigate real world applications of linear programming and related methods.
• Solve linear programming maximization problems using the simplex method.
• Solve linear programming minimization problems using the simplex method.
• 4.1: Introduction to Linear Programming Applications in Business, Finance, Medicine, and Social Science In this section, you will learn about real world applications of linear programming and related methods.
• 4.2.1: Maximization By The Simplex Method (Exercises)
• 4.3.1: Minimization By The Simplex Method (Exercises)
• 4.4: Chapter Review

Thumbnail: Polyhedron of simplex algorithm in 3D. (CC BY-SA 3.0; Sdo via Wikipedia)

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Linear assignment problem solver for .NET.

fuglede/linearassignment

Name already in use.

Use Git or checkout with SVN using the web URL.

Work fast with our official CLI. Learn more about the CLI .

• Open with GitHub Desktop
• Download ZIP

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Linear assignment problem solver in .net.

This repository includes a pure C# solver for the rectangular linear assignment problem , also known as the minimum weight full matching for bipartite graphs .

The problem

Concretely, the problem we solve is the following: Let G = ( V , E ) be a graph and assume that V is the disjoint union of two sets X and Y , with | X | ≤ | Y |, and that for every ( i , j ) ∈ E we have i ∈ X , j ∈ Y . A full matching M ⊆ E is a subset of edges with the property that every vertex in X is incident to exactly one edge in M , and every vertex in Y is incident to at most one edge in M . Let c : E → R be any real function. Our goal is to find a full matching M minimizing Σ e ∈ M c ( e ).

We provide a few different methods for solving the problem. One is based on shortest augmenting paths: At each step of the algorithm, the matching M is expanded by using Dijkstra's algorithm to find the shortest augmenting path from a given non-matched element of X to a non-matched element of Y , and the weights of the graph are updated according to a primal-dual method. We follow the pseudo-code laid out in

which in turn is based closely on Section 4.4 of

Our algorithm for this method is ported from the C++ implementation in scipy.optimize .

For sparse inputs, i.e. inputs for which | E | is less than | X | | Y |, we include an implementation of LAPJVsp, which is also based on shortest augmenting paths. This algorithm is described in

and our implementation is a port of the Pascal code available here .

We also include a different method based on the pseudoflow approach to solving minimum cost flow problems. This is closely based on Section 4.6.4 of Assignment Problems, which in turn is based on the cost-scaling assignment (CSA) approach of

Installation

The package is available from the public NuGet Gallery .

With the notation above, assume that X consists of 3 vertices, and that Y consists of 4 vertices. Then the function c may be described by some double[3, 4] (or int[3, 4] if all weights are integral), each of whose elements is a pair ( i , j ) of elements of X and Y respectively, in which we use double.PositiveInfinity to indicate that a given pair is not connected by an edge. Let us assume that such a c is given, and let us assume that each vertex in X have edges incident with each vertex in Y , except for, say, the last vertex in X not being connected to the last vertex in Y . Then the minimum weight matching may be obtained as follows:

The result is {1, 3, 2} indicating that the three vertices of X are matched with the second, fourth, and third vertex in Y respectively (noting the zero-indexing).

In addition to being able to use double.PositiveInfinity to represent missing edges, it is possible to provide the input cost matrix in compressed sparse row format; depending on the problem structure, this can lead to large performance improvements for the solvers when inputs are sparse.

• Math Article

Linear Programming

In Mathematics, linear programming is a method of optimising operations with some constraints. The main objective of linear programming is to maximize or minimize the numerical value. It consists of linear functions which are subjected to the constraints in the form of linear equations or in the form of inequalities.  Linear programming is considered an important technique that is used to find the optimum resource utilisation. The term “linear programming” consists of two words as linear and programming. The word “linear” defines the relationship between multiple variables with degree one. The word “programming” defines the process of selecting the best solution from various alternatives.

Linear Programming is widely used in Mathematics and some other fields such as economics, business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear programming, its components, and different methods to solve linear programming problems.

Table of Contents:

• Characteristics
• Linear programming Problems
• Simplex Method

Graphical Method

• Applications
• Practice Problems

What is Linear Programming?

Linear programming (LP)   or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints. The constraints may be equalities or inequalities. The optimisation problems involve the calculation of profit and loss.   Linear programming problems  are an important class of optimisation problems, that helps to find the feasible region and optimise the solution in order to have the highest or lowest value of the function.

In other words, linear programming is considered as an optimization method to maximize or minimize the objective function of the given mathematical model with the set of some requirements which are represented in the linear relationship. The main aim of the linear programming problem is to find the optimal solution.

Linear programming is the method of considering different inequalities relevant to a situation and calculating the best value that is required to be obtained in those conditions.  Some of the assumptions taken while working with linear programming are:

• The number of constraints should be expressed in the quantitative terms
• The relationship between the constraints and the objective function should be linear
• The linear function (i.e., objective function) is to be optimised

Components of Linear Programming

The basic components of the LP are as follows:

• Decision Variables
• Constraints
• Objective Functions

Characteristics of Linear Programming

The following are the five characteristics of the linear programming problem:

Constraints – The limitations should be expressed in the mathematical form, regarding the resource.

Objective Function – In a problem, the objective function should be specified in a quantitative way.

Linearity – The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one.

Finiteness –  There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible. 

Non-negativity – The variable value should be positive or zero. It should not be a negative value.

Decision Variables – The decision variable will decide the output. It gives the ultimate solution of the problem. For any problem, the first step is to identify the decision variables.

Linear Programming Problems

The Linear Programming Problems (LPP) is a problem that is concerned with finding the optimal value of the given linear function. The optimal value can be either maximum value or minimum value. Here, the given linear function is considered an objective function. The objective function can contain several variables, which are subjected to the conditions and it has to satisfy the set of linear inequalities called linear constraints. The linear programming problems can be used to get the optimal solution for the following scenarios, such as manufacturing problems, diet problems, transportation problems, allocation problems and so on.

Methods to Solve Linear Programming Problems

The linear programming problem can be solved using different methods, such as the graphical method, simplex method, or by using tools such as R, open solver etc. Here, we will discuss the two most important techniques called the simplex method and graphical method in detail.

Linear Programming Simplex Method

The simplex method is one of the most popular methods to solve linear programming problems. It is an iterative process to get the feasible optimal solution. In this method, the value of the basic variable keeps transforming to obtain the maximum value for the objective function. The algorithm for linear programming simplex method is provided below:

Step 1 : Establish a given problem. (i.e.,) write the inequality constraints and objective function.

Step 2: Convert the given inequalities to equations by adding the slack variable to each inequality expression.

Step 3 : Create the initial simplex tableau. Write the objective function at the bottom row. Here, each inequality constraint appears in its own row. Now, we can represent the problem in the form of an augmented matrix, which is called the initial simplex tableau.

Step 4 : Identify the greatest negative entry in the bottom row, which helps to identify the pivot column. The greatest negative entry in the bottom row defines the largest coefficient in the objective function, which will help us to increase the value of the objective function as fastest as possible.

Step 5 : Compute the quotients. To calculate the quotient, we need to divide the entries in the far right column by the entries in the first column, excluding the bottom row. The smallest quotient identifies the row. The row identified in this step and the element identified in the step will be taken as the pivot element.

Step 6: Carry out pivoting to make all other entries in column is zero.

Step 7: If there are no negative entries in the bottom row, end the process. Otherwise, start from step 4.

Step 8: Finally, determine the solution associated with the final simplex tableau.

The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method is the best method to find the optimal solution. In this method, the set of inequalities are subjected to constraints. Then the inequalities are plotted in the XY plane. Once, all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region. The feasible region will provide the optimal solution as well as explains what all values our model can take.  Let us see an example here and understand the concept of linear programming in a better way.

Calculate the maximal and minimal value of z = 5x + 3y for the following constraints.

x + 2y ≤ 14

3x – y ≥ 0

x – y ≤ 2

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

The optimisation equation (z) = 5x + 3y. You have to find the (x,y) corner points that give the largest and smallest values of z.

To begin with, first solve each inequality.

x + 2y ≤ 14 ⇒  y ≤ -(1/2)x + 7

3x – y ≥ 0 ⇒  y ≤ 3x

x – y ≤ 2 ⇒ y  ≥ x – 2

Here is the graph for the above equations.

Now pair the lines to form a system of linear equations to find the corner points.

y = -(½) x + 7

Solving the above equations, we get the corner points as (2, 6)

y = -1/2 x + 7

y = x – 2

Solving the above equations, we get the corner points as (6, 4)

Solving the above equations, we get the corner points as (-1, -3)

For linear systems, the maximum and minimum values of the optimisation equation lie on the corners of the feasibility region. Therefore, to find the optimum solution, you only need to plug these three points in z = 3x + 4y

z = 5(2) + 3(6) = 10 + 18 = 28

z = 5(6) + 3(4) = 30 + 12 = 42

z = 5(-1) + 3(-3) = -5 -9 = -14

Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14 lies at (-1, -3)

Linear Programming Applications

A real-time example would be considering the limitations of labours and materials and finding the best production levels for maximum profit in particular circumstances. It is part of a vital area of mathematics known as optimisation techniques. The applications of LP in some other fields are

• Engineering – It solves design and manufacturing problems as it is helpful for doing shape optimisation
• Efficient Manufacturing – To maximise profit, companies use linear expressions
• Energy Industry – It provides methods to optimise the electric power system.
• Transportation Optimisation – For cost and time efficiency.

Importance of Linear Programming

Linear programming is broadly applied in the field of optimisation for many reasons. Many functional problems in operations analysis can be represented as linear programming problems. Some special problems of linear programming are such as network flow queries and multi-commodity flow queries are deemed to be important to have produced much research on functional algorithms for their solution.

Linear Programming Video Lesson

Linear programming problem.

Linear Programming Practice Problems

Solve the following linear programming problems:

• A doctor wishes to mix two types of foods in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 10 units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C. Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs Rs 50 per kg to purchase Food ‘I’ and Rs 70 per kg to purchase Food ‘II’. Formulate this problem as a linear programming problem to minimise the cost of such a mixture
• One kind of cake requires 200g of flour and 25g of fat, and another kind of cake requires 100g of flour and 50g of fat.  Formulate this problem as a linear programming problem to find the maximum number of cakes that can be made from 5kg of flour and 1 kg of fat assuming that there is no shortage of the other ingredients used in making the cakes.

Frequently Asked Questions on Linear Programming

Linear programming is a process of optimising the problems which are subjected to certain constraints. It means that it is the process of maximising or minimizing the linear functions under linear inequality constraints. The problem of solving linear programs is considered as the easiest one.

Mention the different types of linear programming.

The different types of linear programming are: Solving linear programming by Simplex method Solving linear programming using R Solving linear programming by graphical method Solving linear programming with the use of an open solver.

What are the requirements of linear programming?

The five basic requirements of linear programming are: Objective function Constraints Linearity Non-negativity Finiteness

Mention the advantages of Linear programming

The advantages of linear programming are: Linear programming provides insights to the business problems It helps to solve multi-dimensional problems According to the condition change, LP helps in making the adjustments By calculating the cost and profit of various things, LP helps to take the best optimal solution

What is meant by linear programming problems?

The linear programming problems (LPP) helps to find the best optimal solution of a linear function (also, known as the objective function) which are placed under certain constraints (set of linear inequality constraints)

To learn all concepts in Maths in a more engaging way, register at BYJU’S. Also, watch interesting videos on various Maths topics by downloading 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

Thank you so much for clearly explained notes. I benefited a lot from them

Thank you very much for this material.

• Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.