define linear programming problem in operation research

• School Guide
• Mathematics
• Number System and Arithmetic
• Trigonometry
• Probability
• Mensuration
• Maths Formulas
• Integration Formulas
• Differentiation Formulas
• Trigonometry Formulas
• Algebra Formulas
• Mensuration Formula
• Statistics Formulas
• Trigonometric Table

Linear Programming

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.

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

Practice Problems on Linear Programming

Problem 1: Maximize Z=3x+4y subject to the constraints:

• [Tex]x+2\leq 8[/Tex]
• [Tex]3x+y\leq 9[/Tex]
• [Tex]x \geq 0[/Tex]
• [Tex]y \geq 0[/Tex]

Problem 2: Minimize Z=5x+2y subject to the constraints:

• [Tex]2x + y \geq 10[/Tex]
• [Tex]x + 3y \geq 15[/Tex]

Problem 3: A factory produces two products, P1 and P2. The profit for P1 is $40 and for P2 is $30. Each product requires processing in two departments. The processing times in hours per unit for each department are given below:

The available hours for Department A are 100 and for Department B are 80. Formulate the linear programming problem to maximize the profit.

Problem 4: Minimize the cost of a diet containing at least 60 units of protein and 70 units of carbohydrates. Two food items, A and B, provide the following nutrients per unit:

The cost per unit of food A is $2 and food B is $3. Formulate the linear programming problem to minimize the cost.

Problem 5: A company needs to transport goods from two warehouses to three retail stores. The supply at Warehouse 1 is 70 units, and at Warehouse 2 is 80 units. The demand at Store 1 is 40 units, at Store 2 is 50 units, and at Store 3 is 60 units. The transportation costs per unit are given below:

Formulate the linear programming problem to minimize the transportation cost.

Problem 6: Maximize the return on an investment portfolio consisting of two investments, A and B. Investment A has a return of 5% and investment B has a return of 7%. The total investment is $100,000, with at least $30,000 in investment A and no more than $60,000 in investment B. Formulate the linear programming problem.

Problem 7: A company needs to schedule workers for a week with the following constraints: At least 3 workers on Monday, 2 on Tuesday, 4 on Wednesday, 3 on Thursday, and 5 on Friday. Each worker can work at most 3 days a week. Formulate the linear programming problem to minimize the number of workers needed.

Problem 8: A company produces a blend of two chemicals, A and B. The blend must contain at least 30% of A and at least 40% of B. Chemical A costs $10 per unit and chemical B costs $15 per unit. The company needs to produce 100 units of the blend. Formulate the linear programming problem to minimize the cost.

Problem 9: Assign 4 workers to 4 jobs with the following costs:

Formulate the linear programming problem to minimize the total cost.

Problem 10: An investor wants to maximize the return from a portfolio consisting of three investments: X, Y, and Z. The returns are 6%, 8%, and 10%, respectively. The total investment is $200,000, with at least $50,000 in each investment and at least as much in X as in Y. Formulate the linear programming problem.

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.

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

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

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

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

Operations Research by P. Mariappan

Get full access to Operations Research 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.

Linear Programming Problem (LPP)

2.1  introduction.

Linear Programming constitutes a set of Mathematical Methods specially designed for the Modelling and solution of certain kinds of constrained optimization problems.

The Mathematical presentation of a Linear Programming Problem in the form of a linear objective function and one or more linear constraints with equations or inequations constitutes a Linear Programming Problem. The process leading to the construction of this model is referred to as the Model Building or Mathematical formulation of Business problem given. In this model, a linear objective function of the decision variables are maximized/minimized subject to a set of linear constraints with equations/inequations. This technique ...

Get Operations Research 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.

What is Linear Programming? Assumptions, Properties, Advantages, Disadvantages

• Post last modified: 22 July 2022
• Reading time: 24 mins read
• Post category: Operations Research

What is Linear Programming?

Linear programming is also a form of constrained optimisation, and quite possibly, the most commonly used. To understand the meaning of linear programming, we need to first understand what is meant by constrained optimisation.

In constrained optimisation, we have to optimise the objective function (or find the best value of the function), keeping in mind the various constraints. Therefore, the optimum feasible solution may be somewhat lower than the maximum because of the constraints.

Table of Content

• 1 What is Linear Programming?
• 2 Introduction to Linear Programming
• 3.1 Proportionality / Linearity
• 3.2 Certainty
• 3.3 Presence of different alternatives
• 3.4 Additivity
• 3.5 Non-negative variable
• 3.6 Finiteness
• 3.7 Divisibility
• 3.8 Continuity
• 4.1 Objective Function
• 4.2 Decision Variables
• 4.3 Constraint Equation
• 4.4 Structural Constraints
• 4.5 Non-negativity Constraint
• 5.1 Scientific approach to problem-solving
• 5.2 Evaluation of all possible alternatives
• 5.3 Optimal utilisation
• 5.4 Helps in re-evaluation
• 5.5 Improves the quality of the decision
• 5.6 Addresses bottlenecks
• 5.7 Applicable to diverse problems
• 5.8 Formation of information base
• 6.1 Assumption of linear relationship
• 6.2 Constant value of objective and constraint equations
• 6.3 No scope for fractional value solutions
• 6.4 Degree of complexity
• 6.5 Unsuitability for multiple goals
• 6.6 Lack of flexibility
• 7.1 Identification of the decision variables
• 7.2 Identification of the constraints
• 7.3 Identification of the objective

As with any constrained optimisation, the main elements of LP are:

• Objective function
• Constraints

In the context of operations research, LP can be defined as a mathematical tool that enables decision makers to allocate limited resources amongst competing activities in an optimal manner in situations where the problem can be expressed using a linear objective function and linear inequality constraints. It concerns the optimisation of a function of variables (i.e. the objective function), subject to a set of linear equations and/or inequalities (i.e. constraints).

The objective function could be any measure of effectiveness such as cost, time, profit, capacity, etc., that has to be achieved in the best possible way.

Let us now find out what makes a linear function. Linearity is the property of a mathematical equation in which the expressions among the variables are linear i.e. higher power of the variables and their products are not allowed. Thus, the function f of n variables x = (x1, . . . ,xn) is linear if there are constants a1, . . . , an such that:

f (x) = a1 x1 + a2 x2 . . . + an xn

Introduction to Linear Programming

Linear Programming (LP) is one of the most widely used techniques for effective decision-making. It is an optimisation technique that focuses on providing the optimal solution for allocating available resources amongst different competing and conflicting requirements.

The first serious attempt at the linear programming formulation and solution of a problem was done by Soviet mathematician and economist Leonid Kantorovich in 1939 during World War II, for planning the transport, scheduling, and allocation of resources within the given constraints of costs and availability.

In 1941, American mathematician Frank Lauren Hitchcock also formulated transportation problems as linear programs and developed a solution quite like the simplex method which was invented by American mathematician George B. Dantzig in 1947.

In 1979, Russian mathematician Leonid Khachi- yan first solved a linear programming problem in polynomial time. In a major breakthrough in 1984, Indian mathematician Narendra Karmarkar discovered a new interior-point method for solving linear programming problems.

The scope for application of LP is wide-range as it can be adapted to analyse diverse multi-dimensional decision-making problems. To be able to use and apply LP successfully, the formulation of a realistic model which accurately states the objectives of the decision-making is needed, subject to the restrictions in which the decision-making has to be made.

This article will allow readers to understand the meaning of linear programming and its various elements, gain an insight into how a lin- ear programming model is formulated, and how linear programming is expressed in its general, canonical and standard forms.

Assumptions of Linear Programming

The first and foremost assumption when using linear programming to model the real world is that a linear model is suitable. This is an important point to consider, given the fact that the real world will have plenty of non-linear relationships. Let us look at the other assumptions of linear programming:

Proportionality / Linearity

Presence of different alternatives, non-negative variable, divisibility.

Linear programming assumes that any modification in the constraint inequalities will result in a proportional change in the objective function. This means that if it takes 10 hours to produce 1 unit of a product, then it would take 50 hours to produce 5 such products.

Certainty in linear programming refers to the assumption that the parameters of the objective function coefficients and the coefficients of constraints are known with certainty. For example, profit per unit of product, resource availability per unit, etc. are known with certainty.

Linear programming assumes that different courses of action are available to the decision-maker/s and they need to decide which is the most optimal.

Additivity means that each function in a linear programming model is the sum of the individual contributions of the respective activities. For example, the total profit is determined by the sum of profit contributed by each activity separately.

Likewise, the total amount of resources used is also determined by the sum of resources used by each activity separately. This assumption thus implies that there is no interaction among the decision variables.

Linear programming assumes that all answers or variables are non-negative. This assumption is true in the sense that negative values of physical quantities are not possible. It is not possible for the output in the production problem (such as bicycles, cars, computers, etc.) to be negative.

Linear programming assumes about the presence of a finite number of activities. An optimal solution is not possible in a situation where there is an infinite number of alternative activities and resource constraints.

Linear programming makes the divisibility assumption that the solution has to be in whole numbers i.e. integers. This assumption means that decision variable may take any value, including non-integer values, as long as functional and non-negativity constraints are satisfied.

Linear programming assumes the continuity of decision variables. This means that a combination of outputs with fractional values plus integer values can be used.

Properties of Linear Programming Model

As you know by now, a linear programming model has the following conditions:

• The decision variables must have a linear relationship.
• It must have an objective function.
• Resource constraints are required.
• It must have a non-negative constraint.

A linear programming model involves an objective function, well-defined decision variables, and a set of non-negative structural constraints.

Let us try to understand these terms in the following section:

Objective Function

Decision variables, constraint equation, structural constraints, non-negativity constraint.

The goal of an LP model is to optimise (maximise or minimise) the objective function; thus, the objective function can be defined as the mathematical equation that is a linear function of a set of variables that needs to be optimised. It is the mathematical expression that represents the aim of the system. In most cases, the objective is to maximise resources or profits and minimise the time or cost.

The decision variables in a linear program are a set of variables that need to be determined to solve the problem. The aim is to determine the values of variables that yield the best value of objective function.

Decision-making problems arise mostly because the availability of resources in organisations is limited and tasks need to be performed in the most effective manner within this limit. Therefore, problems occur within these constraints in which the optimal solution to the problem needs to be identified.

An LP model thus has different linear constraints equations that are basically a mathematical statement of the limits on the resources or inputs at hand.

Structural constraints will always be present in linear programming problems. For example, the inequalities in the problem

x + y ≤ 100 20 x + 10y ≤ 1200

are the structural constraints of the linear programming problem. A constraint in an LP model restricts the value of the objective function, the value of decision variables and the use of resources at hand.

As we read earlier, physical quantities cannot have negative values. Non-negativity constraint refers to a restriction added to a linear programming problem which highlights the negative values for physical quantities that cannot be shown in a solution.

It is essential to include the element of non-negativity as a constraint in a linear programming problem. In the above problem, the inequalities x ≥ 0, y ≥ 0 are the non-negative constraints.

Advantages of Linear Programming

There are several advantages of linear programming as mentioned below:

Scientific approach to problem-solving

Evaluation of all possible alternatives, optimal utilisation, helps in re-evaluation, improves the quality of the decision, addresses bottlenecks, applicable to diverse problems, formation of information base.

LP employs a scientific approach to problem-solving. It helps to determine the best possible outcome by representing complex relationships through linear functions. Thus, it presents a clear picture of problems which helps in better analysis.

Today’s environment presents highly complex decision-making problems to organisations which are difficult to solve by the traditional approach.

LP enables optimal utilisation of various prevailing factors of production such as labour, raw materials, equipment, cost, etc.

LP helps to re-assess a basic plan in case of changing conditions. If, the conditions change while the plan has been only executed in part, LP can be used to determine these conditions accurately to adapt the rest of the plan for the best outcome.

LP helps to improve quality of decisions by incorporating the limitations of the system (which are the various restrictions which the system must conform to for the solution to be optimal). If deviating from the optimal path becomes inevitable, LP can also allow an easy estimation of the costs or penalty associated with this.

Bottlenecks can cause imbalances in the production process as some machines will not be able to face the demand even at their peak performance while others may remain idle for long periods of time. LP highlights and addresses the problem of bottlenecks in the production process through optimisation.

LP is quite an accommodating mathematical technique and can be adapted to analyse diverse multi-dimensional decision-making problems quite effectively.

LP models can help managers obtain a highly useful information database by the analysis of the many possible alternatives taking into account the existing constraints. This database can be used to make rational decisions regarding the allocation of valuable resources.

Disadvantages of Linear Programming

While LP is a highly effective OR technique and has a wide range of applications in organisations, it still has certain limitations, of which we will learn about in this section.

Assumption of linear relationship

Constant value of objective and constraint equations, no scope for fractional value solutions, degree of complexity, unsuitability for multiple goals, lack of flexibility.

We earlier discussed that LP assumes that the objective, variables as well as all the constraints can be stated in term of linear expressions which may not hold true for a lot of real-life situations.

Therefore, for LP models to be successfully applied, a given problem has be to clearly stated in the form of a linear relationship between different decision variables, whereas many reality-based organisational problems can be expressed quite easily in terms of a quadratic equation instead of a linear equation. LP fails to work and provide optimal solutions in these situations.

For example, LP techniques are unable to solve a problem that is expressed in the form of ax2 + bx + C = 0 where a ≠ 0.

LP technique can only be applied to a given problem once the values or the coefficients of the objective function as well as the constraint equations are all known with absolute certainty. In practical scenarios, however, it is not always possible to know with certainty the coefficients of objective function and the constraints equations.

In real-life scenarios, these variables may lie on a probability distribution curve and only the possibility of their occurrence can be predicted at best. LP also assumes that these values do not change over a while.

LP would lose it efficacy and might be unsuccessful in providing an optimal solution to the problem if these values were to change during the period of study. In practical situations, however, the values may change due to both external and internal factors during the course of the OR study. These assumptions limit the actual applicability of LP tools.

The solution to an LP problem may not always be quantified as an integer. A lot of times an LP offers a variety of fractional value solutions which needs to be rounded off to the next integer. In such cases, the solution would not be optimal.

A lot of real-life projects are large-scale. LP models are less useful in such cases because of the difficulty in performing the highly complex and lengthy calculations.

In such cases, various assumptions and approximations need to be made so that the given problem can be decomposed into several smaller problems and then solved individually. The validity of the final result may be unreliable in these situations.

Most organisations’ long-term objectives are not limited to a single goal. An organisation might need to achieve multiple goals such as profit maximisation or cost minimisation, expanding market share, improving customer relationships, etc. on a priority basis to attain its long-term growth objectives.

Sometimes, there might be a conflict between the different goals and LP will fail in such cases. This is because only one goal can be expressed in the objective function in LP.

If there are changes in decision variables in the system, it is very hard to incorporate these changes after a problem has been properly quantified in terms of objective function and the constraint equations and LP tools have been applied. Thus, LP does not have the desired operational flexibility.

Formulation of Linear Programming Model

The representation of an optimisation problem in a linear programming mathematical form is referred to as the formulation of an LP model.

The basic steps in the formulation of an LP model are:

Identification of the decision variables

Identification of the constraints, identification of the objective.

The aim of an LP problem is to identify ways to optimise an objective and the answer to this problem is influenced by value of the selected decision variables. Therefore, the first step is to define the decision variables (parameters) that govern the behaviour of the objective function.

These decision variables are then stated in the form of linear algebraic functions or equations. The value of decision variables will be limited by the constraints stated in the problem which is the next step in the process.

Once the decision variables have been determined, the next step is to identify all the constraints which limit the operations of an organisation at a given point of time.

These constraints need to be stated as linear functions in terms of the decision variables. The non-negativity constraints should also be included at this stage as decision variables cannot be negative in a physical scenario.

The next step is to identify the objective that needs to be optimised and express it in terms of the pre-defined decision variables and constraints.

Business Ethics

( Click on Topic to Read )

• What is Ethics?
• What is Business Ethics?
• Values, Norms, Beliefs and Standards in Business Ethics
• Indian Ethos in Management
• Ethical Issues in Marketing
• Ethical Issues in HRM
• Ethical Issues in IT
• Ethical Issues in Production and Operations Management
• Ethical Issues in Finance and Accounting
• What is Corporate Governance?
• What is Ownership Concentration?
• What is Ownership Composition?
• Types of Companies in India
• Internal Corporate Governance
• External Corporate Governance
• Corporate Governance in India
• What is Enterprise Risk Management (ERM)?
• What is Assessment of Risk?
• What is Risk Register?
• Risk Management Committee

Corporate social responsibility (CSR)

• Theories of CSR
• Arguments Against CSR
• Business Case for CSR
• Importance of CSR in India
• Drivers of Corporate Social Responsibility
• Developing a CSR Strategy
• Implement CSR Commitments
• CSR Marketplace
• CSR at Workplace
• Environmental CSR
• CSR with Communities and in Supply Chain
• Community Interventions
• CSR Monitoring
• CSR Reporting
• Voluntary Codes in CSR
• What is Corporate Ethics?

Lean Six Sigma

• What is Six Sigma?
• What is Lean Six Sigma?
• Value and Waste in Lean Six Sigma
• Six Sigma Team
• MAIC Six Sigma
• Six Sigma in Supply Chains
• What is Binomial, Poisson, Normal Distribution?
• What is Sigma Level?
• What is DMAIC in Six Sigma?
• What is DMADV in Six Sigma?
• Six Sigma Project Charter
• Project Decomposition in Six Sigma
• Critical to Quality (CTQ) Six Sigma
• Process Mapping Six Sigma
• Flowchart and SIPOC
• Gage Repeatability and Reproducibility
• Statistical Diagram
• Lean Techniques for Optimisation Flow
• Failure Modes and Effects Analysis (FMEA)
• What is Process Audits?
• Six Sigma Implementation at Ford
• IBM Uses Six Sigma to Drive Behaviour Change
• Research Methodology
• What is Research?
• What is Hypothesis?
• Sampling Method
• Research Methods
• Data Collection in Research
• Methods of Collecting Data
• Application of Business Research
• Levels of Measurement
• What is Sampling?
• Hypothesis Testing
• Research Report
• What is Management?
• Planning in Management
• Decision Making in Management
• What is Controlling?
• What is Coordination?
• What is Staffing?
• Organization Structure
• What is Departmentation?
• Span of Control
• What is Authority?
• Centralization vs Decentralization
• Organizing in Management
• Schools of Management Thought
• Classical Management Approach
• Is Management an Art or Science?
• Who is a Manager?

Operations Research

• What is Operations Research?
• Operation Research Models
• Linear Programming
• Linear Programming Graphic Solution
• Linear Programming Simplex Method
• Linear Programming Artificial Variable Technique

Duality in Linear Programming

• Transportation Problem Initial Basic Feasible Solution
• Transportation Problem Finding Optimal Solution
• Project Network Analysis with Critical Path Method

Project Network Analysis Methods

Project evaluation and review technique (pert), simulation in operation research, replacement models in operation research.

Operation Management

• What is Strategy?
• What is Operations Strategy?
• Operations Competitive Dimensions
• Operations Strategy Formulation Process
• What is Strategic Fit?
• Strategic Design Process
• Focused Operations Strategy
• Corporate Level Strategy
• Expansion Strategies
• Stability Strategies
• Retrenchment Strategies
• Competitive Advantage
• Strategic Choice and Strategic Alternatives
• What is Production Process?
• What is Process Technology?
• What is Process Improvement?
• Strategic Capacity Management
• Production and Logistics Strategy
• Taxonomy of Supply Chain Strategies
• Factors Considered in Supply Chain Planning
• Operational and Strategic Issues in Global Logistics
• Logistics Outsourcing Strategy
• What is Supply Chain Mapping?
• Supply Chain Process Restructuring
• Points of Differentiation
• Re-engineering Improvement in SCM
• What is Supply Chain Drivers?
• Supply Chain Operations Reference (SCOR) Model
• Customer Service and Cost Trade Off
• Internal and External Performance Measures
• Linking Supply Chain and Business Performance
• Netflix’s Niche Focused Strategy
• Disney and Pixar Merger
• Process Planning at Mcdonald’s

Service Operations Management

• What is Service?
• What is Service Operations Management?
• What is Service Design?
• Service Design Process
• Service Delivery
• What is Service Quality?
• Gap Model of Service Quality
• Juran Trilogy
• Service Performance Measurement
• Service Decoupling
• IT Service Operation
• Service Operations Management in Different Sector

Procurement Management

• What is Procurement Management?
• Procurement Negotiation
• Types of Requisition
• RFX in Procurement
• What is Purchasing Cycle?
• Vendor Managed Inventory
• Internal Conflict During Purchasing Operation
• Spend Analysis in Procurement
• Sourcing in Procurement
• Supplier Evaluation and Selection in Procurement
• Blacklisting of Suppliers in Procurement
• Total Cost of Ownership in Procurement
• Incoterms in Procurement
• Documents Used in International Procurement
• Transportation and Logistics Strategy
• What is Capital Equipment?
• Procurement Process of Capital Equipment
• Acquisition of Technology in Procurement
• What is E-Procurement?
• E-marketplace and Online Catalogues
• Fixed Price and Cost Reimbursement Contracts
• Contract Cancellation in Procurement
• Ethics in Procurement
• Legal Aspects of Procurement
• Global Sourcing in Procurement
• Intermediaries and Countertrade in Procurement

Strategic Management

• What is Strategic Management?
• What is Value Chain Analysis?
• Mission Statement
• Business Level Strategy
• What is SWOT Analysis?
• What is Competitive Advantage?
• What is Vision?
• What is Ansoff Matrix?
• Prahalad and Gary Hammel
• Strategic Management In Global Environment
• Competitor Analysis Framework
• Competitive Rivalry Analysis
• Competitive Dynamics
• What is Competitive Rivalry?
• Five Competitive Forces That Shape Strategy
• What is PESTLE Analysis?
• Fragmentation and Consolidation Of Industries
• What is Technology Life Cycle?
• What is Diversification Strategy?
• What is Corporate Restructuring Strategy?
• Resources and Capabilities of Organization
• Role of Leaders In Functional-Level Strategic Management
• Functional Structure In Functional Level Strategy Formulation
• Information And Control System
• What is Strategy Gap Analysis?
• Issues In Strategy Implementation
• Matrix Organizational Structure
• What is Strategic Management Process?

Supply Chain

• What is Supply Chain Management?
• Supply Chain Planning and Measuring Strategy Performance
• What is Warehousing?
• What is Packaging?
• What is Inventory Management?
• What is Material Handling?
• What is Order Picking?
• Receiving and Dispatch, Processes
• What is Warehouse Design?
• What is Warehousing Costs?

You Might Also Like

Linear programming: graphic solution, linear programming: artificial variable technique, transportation problem: finding an optimal solution, linear programming: simplex method, what is operations research (or) definition, concept, characteristics, tools, advantages, limitations, applications and uses, project network analysis with critical path method, operation research models and modelling, leave a reply cancel reply.

You must be logged in to post a comment.

World's Best Online Courses at One Place

We’ve spent the time in finding, so you can spend your time in learning

Digital Marketing

Personal Growth

Development

• Operations Research Problems

Statements and Solutions

• © 2014
• Raúl Poler 0 ,
• Josefa Mula 1 ,
• Manuel Díaz-Madroñero 2

Research Centre on Production Management and Engineering, Polytechnic University of Valencia, Alcoy, Spain

You can also search for this author in PubMed   Google Scholar

Escuela Politécnica Superior de Alcoy, Universidad Politécnica de Valencia, Alcoy, Spain

Universitat politècnica de valència, alcoy, spain.

• Provides a valuable compendium of problems as a reference for undergraduate and graduate students, faculty, researchers and practitioners of operations research and management science
• Identifies different operations management problems in order to improve the decision making process concerning readers
• Addresses the following topics: Linear programming, integer programming, non-linear programming, network modeling, inventory theory, queue theory, tree decision, game theory, dynamic programming and markov processes

49k Accesses

11 Citations

This is a preview of subscription content, log in via an institution to check access.

Access this book

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as EPUB and PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

Similar content being viewed by others.

Applications and Mathematical Modeling in Operations Research

From Operations Research to Dynamic Data Mining and Beyond

Introduction to Stochastic Optimisation and Game Theory

Dynamic programming.

• Game Theory

Integer Programming

Inventory theory.

• Linear and Non-Linear Programming

Markov Processes

• Network Modeling
• Queue Theory

Table of contents (10 chapters)

Front matter, linear programming.

• Raúl Poler, Josefa Mula, Manuel Díaz-Madroñero

Non-Linear Programming

Network modelling, queueing theory, decision theory, games theory, back matter.

From the reviews:

Authors and Affiliations

Josefa Mula

Manuel Díaz-Madroñero

Bibliographic Information

Book Title : Operations Research Problems

Book Subtitle : Statements and Solutions

Authors : Raúl Poler, Josefa Mula, Manuel Díaz-Madroñero

DOI : https://doi.org/10.1007/978-1-4471-5577-5

Publisher : Springer London

eBook Packages : Engineering , Engineering (R0)

Copyright Information : Springer-Verlag London Ltd., part of Springer Nature 2014

Hardcover ISBN : 978-1-4471-5576-8 Published: 22 November 2013

Softcover ISBN : 978-1-4471-7190-4 Published: 23 August 2016

eBook ISBN : 978-1-4471-5577-5 Published: 08 November 2013

Edition Number : 1

Number of Pages : XV, 424

Number of Illustrations : 32 b/w illustrations, 55 illustrations in colour

Topics : Industrial and Production Engineering , Operations Research/Decision Theory , Game Theory, Economics, Social and Behav. Sciences

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Multiple, Unbounded, and Infeasible Problems in Linear Programming

Table of Contents

Linear programming (LP) problems can be challenging to solve, even when there is only one optimal solution. But what happens when there are multiple optimal solutions, no feasible solution exists, or the solution is unbounded? In this blog, we’ll define these three scenarios and discuss how to approach them in your LP models.

Multiple Solutions

A linear programming problem may have multiple optimal solutions when there is more than one set of decision variables that can produce the same objective function value. This situation can occur when the objective function is flat along a line segment in the feasible region. To find all possible solutions, you can use sensitivity analysis to examine the range of values over which the objective function coefficient can change without changing the optimal solution.

Unbounded Solutions

An unbounded solution arises when the objective function value can be made infinitely large without violating any of the problem constraints. This situation can occur when the feasible region is unbounded, or when the objective function coefficient of a decision variable is negative and unbounded in magnitude. To identify an unbounded solution, you can check if the objective function value can be made arbitrarily large by increasing the value of a decision variable without violating any of the constraints.

Infeasible Solutions

An infeasible solution occurs when no feasible solution exists that satisfies all of the problem constraints. This situation can occur when the constraints are mutually contradictory or when the feasible region is empty. To identify an infeasible solution, you can check if the problem constraints are inconsistent or if the feasible region is empty.

How to Identify Multiple, Unbounded, and Infeasible Problems?

Identifying multiple, unbounded, and infeasible problems is crucial because they can affect the decision-making process. Here are some ways to identify them:

Infeasible Problems

• Graphically: An infeasible problem can be identified when the feasible region is empty or when the constraints intersect at a point.
• Algebraically: An infeasible problem can be identified when the constraints are contradictory or when the system of equations has no solution.

Unbounded Problems

• Graphically: An unbounded problem can be identified when the feasible region extends infinitely.
• Algebraically: An unbounded problem can be identified when one or more variables have no upper or lower bounds.

Multiple Optimal Solutions

• Graphically: Multiple optimal solutions can be identified when the objective function is parallel to one of the constraints.
• Algebraically: Multiple optimal solutions can be identified when the optimal value of the objective function is the same for two or more feasible solutions.

What Actions can be Taken to Resolve Multiple, Unbounded, and Infeasible Problems?

Resolving multiple, unbounded, and infeasible problems depends on the nature of the problem. Here are some general guidelines:

• Check for errors in the problem formulation, such as typos in the constraints or objective function.
• Relax some of the constraints to make the problem feasible.
• Check for alternate optimal solutions that may satisfy some of the constraints.
• Add constraints to limit the feasible region.
• Change the objective function to make it bounded.
• Analyze the sensitivity of the problem to changes in the constraints or objective function.
• Choose the optimal solution that best satisfies additional criteria, such as cost, time, or quality.

Multiple, unbounded, and infeasible solutions can pose challenges when solving linear programming problems. However, by understanding the causes of these scenarios and the methods for handling them, you can improve your ability to create effective optimization models. Remember to always check for these scenarios when solving linear programming problems, and be prepared to modify the problem formulation or adopt alternative approaches to arrive at a suitable solution.

How useful was this post?

Click on a star to rate it!

Average rating 2.5 / 5. Vote count: 2

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

Simplex Method for Solution of L.P.P (With Examples) | Operation Research

After reading this article you will learn about:- 1. Introduction to the Simplex Method 2. Principle of Simplex Method 3. Computational Procedure 4. Flow Chart.

Introduction to the Simplex Method :

Simplex method also called simplex technique or simplex algorithm was developed by G.B. Dantzeg, An American mathematician. Simplex method is suitable for solving linear programming problems with a large number of variable. The method through an iterative process progressively approaches and ultimately reaches to the maximum or minimum values of the objective function.

Principle of Simplex Method :

It has not been possible to obtain the graphical solution to the LP problem of more than two variables. For these reasons mathematical iterative procedure known as ‘Simplex Method’ was developed. The simplex method is applicable to any problem that can be formulated in-terms of linear objective function subject to a set of linear constraints.

ADVERTISEMENTS:

The simplex method provides an algorithm which is based on the fundamental theorem of linear programming. This states that “the optimal solution to a linear programming problem if it exists, always occurs at one of the corner points of the feasible solution space.”

The simplex method provides a systematic algorithm which consist of moving from one basic feasible solution to another in a prescribed manner such that the value of the objective function is improved. The procedure of jumping from vertex to the vertex is repeated. The simplex algorithm is an iterative procedure for solving LP problems.

It consists of:

(i) Having a trial basic feasible solution to constraints equation,

(ii) Testing whether it is an optimal solution,

(iii) Improving the first trial solution by repeating the process till an optimal solution is obtained.

Computational Procedure of Simplex Method :

The computational aspect of the simplex procedure is best explained by a simple example.

Consider the linear programming problem:

Maximize z = 3x 1 + 2x 2

Subject to x 1 + x 2 , ≤ 4

x 1 – x 2 , ≤ 2

x 1 , x 2 , ≥ 4

< 2 x v x 2 > 0

The steps in simplex algorithm are as follows:

Formulation of the mathematical model:

(i) Formulate the mathematical model of given LPP.

(ii) If objective function is of minimisation type then convert it into one of maximisation by following relationship

Minimise Z = – Maximise Z*

When Z* = -Z

(iii) Ensure all b i values [all the right side constants of constraints] are positive. If not, it can be changed into positive value on multiplying both side of the constraints by-1.

In this example, all the b i (height side constants) are already positive.

(iv) Next convert the inequality constraints to equation by introducing the non-negative slack or surplus variable. The coefficients of slack or surplus variables are zero in the objective function.

In this example, the inequality constraints being ‘≤’ only slack variables s 1 and s 2 are needed.

Therefore given problem now becomes:

The first row in table indicates the coefficient c j of variables in objective function, which remain same in successive tables. These values represent cost or profit per unit of objective function of each of the variables.

The second row gives major column headings for the simple table. Column C B gives the coefficients of the current basic variables in the objective function. Column x B gives the current values of the corresponding variables in the basic.

Number a ij represent the rate at which resource (i- 1, 2- m) is consumed by each unit of an activity j (j = 1,2 … n).

The values z j represents the amount by which the value of objective function Z would be decreased or increased if one unit of given variable is added to the new solution.

It should be remembered that values of non-basic variables are always zero at each iteration.

So x 1 = x 2 = 0 here, column x B gives the values of basic variables in the first column.

So 5, = 4, s 2 = 2, here; The complete starting feasible solution can be immediately read from table 2 as s 1 = 4, s 2 , x, = 0, x 2 = 0 and the value of the objective function is zero.

Flow Chart of Simplex Method :