• 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
  • CBSE Class 12 Maths Notes: Chapter Wise Notes PDF 2024

Chapter 1: Relations and Functions

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

Chapter 2: Inverse Trigonometric Functions

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

Chapter 3: Matrices

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

Chapter 4: Determinants

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

Chapter 5: Continuity and Differentiability

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

Chapter 6: Applications of Derivatives

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

Chapter 7: Integrals

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

Chapter 8: Applications of Integrals

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

Chapter 9: Differential Equations

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

Chapter 10: Vector Algebra

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

Chapter 11: Three-dimensional Geometry

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

Chapter 12: Linear Programming

Linear programming.

  • Graphical Solution of Linear Programming Problems

Chapter 13: Probability

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

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

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

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

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

Table of Content

What is Linear Programming? 

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

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

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

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

Linear Programming Definition

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

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

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

Additional Characteristics of Linear Programming

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

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

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

Linear Programming Examples

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.

LPP Graph for Z = 3x + 4y

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

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

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

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

Linear Programming – FAQs

What is linear programming.

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

What are Linear Programming Problems?

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

What is Linear Programming Formula?

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

What are the different types of Linear Programming?

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

What are requirements of Linear Programming?

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

What are the advantages of Linear Programming?

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

Please Login to comment...

Similar reads.

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

Improve your Coding Skills with Practice

 alt=

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.

Linear Programming - Graph

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.

define linear programming problem in operation research

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

define linear programming problem in operation research

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

Thank you very much for this material.

define linear programming problem in operation research

  • Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

close

Operations Research by

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.

Cover of Software Architecture Patterns

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.

define linear programming problem in operation research

Geektonight

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

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

Coursera 7-Day Trail offer

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

Project network analysis with critical path method, transportation problem: finding an optimal solution, linear programming: artificial variable technique, what is operations research (or) definition, concept, characteristics, tools, advantages, limitations, applications and uses, linear programming: simplex method, operation research models and modelling, transportation problem: initial basic feasible solution, linear programming: graphic solution, 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.

define linear programming problem in operation research

Development

define linear programming problem in operation research

Algorithmic Optimization Techniques for Operations Research Problems

  • Conference paper
  • First Online: 24 February 2024
  • Cite this conference paper

define linear programming problem in operation research

  • Carla Silva 11 ,
  • Ricardo Ribeiro   ORCID: orcid.org/0000-0003-2983-9080 12 &
  • Pedro Gomes 13  

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 935))

Included in the following conference series:

  • Proceedings of the Computational Methods in Systems and Software

101 Accesses

This paper provides an overview of the key concepts and approaches discussed in the field of Algorithmic Optimization Techniques. Operation re-search plays a role in addressing complex decision-making challenges across industries. This paper explores a range of algorithmic methods and optimization strategies employed to solve real-world problems efficiently and effectively.

This paper outlines the core themes covered in our research, including the classification of optimization problems, the utilization of mathematical models, and the development of algorithmic solutions. It highlights the importance of algorithm selection and design in achieving optimal solutions for diverse operations research problems.

Furthermore, this underscores the relevance of this research area enhancing decision-making processes, resource allocation, and overall efficiency in industries such as transportation, supply chain management, finance, and healthcare. The paper aims to provide readers with insights into cutting-edge algorithmic techniques, their applications, and their potential impact on addressing complex optimization challenges in operations research.

Algorithmic Optimization Techniques for Operations Research Problems serves as theoretical board for researchers, practitioners, and students seeking to understand and apply algorithmic optimization methods to tackle a wide range of operations research problems and make informed decisions in various domains.

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

Access this chapter

  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
  • Available as EPUB and PDF
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)

Google Scholar  

Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34 (3), 209–219 (2006)

Article   Google Scholar  

Brandeau, M.L., Sainfort, F., Pierskalla, W.P.: Operations Research and Health Care: A Handbook of Methods and Applications. Kluwer Academic Publishers, Dordrecht (2004)

Book   Google Scholar  

Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)

Hillier, F.S., Lieberman, G.J.: Introduction to Operations Research. McGraw-Hill, New York (2014)

Jain, A., Meeran, S.: Multi-objective optimization of supply chain networks. Comput. Chem. Eng. 27 (8–9), 1155–1174 (2003)

Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Cham (2006)

Ozcan-Top, O., McCarthy, T.: A review of optimization models for patient admission scheduling in hospitals. Health Care Manag. Sci. 20 (2), 139–162 (2017)

Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, New York (1998)

Salhi, S.: Heuristic Algorithms for the Vehicle Routing Problem. Wiley, Hoboken (2000)

Simchi-Levi, D., Kaminsky, P., Simchi-Levi, E.: Designing and Managing the Supply Chain: Concepts, Strategies, and Case Studies. McGraw-Hill, New York (2019)

Toth, P., Vigo, D.: The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia (2002)

Acknoff, R.L.: The future of operational research is past. J. Oper. Res. Soc. 30 (2), 93–104 (1979)

Bakker, H., Fabian, D., Stefan, N.: A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice. Omega 96 , 102080 (2020)

Bertsimas, D., Dunn, J.: Optimal classification trees. Mach. Learn. 106 , 1039–1082 (2017)

Article   MathSciNet   Google Scholar  

Carrizosa, E.: Enhancing interpretability in factor analysis by means of mathematical optimization. Multivar. Behav. Res. 55 (5), 748–762 (2020)

Cazals, C., Florens, J., Simar, L.: Nonparametric frontier estimation: a robust approach. J. Econometr. 106 (1), 1–25 (2002)

Jordan, M.I., Mitchell, T.M.: Machine learning: trends, perspectives, and prospects. Science 349 (6245), 255–260 (2015)

Kumar, A.M., Satyanarayana, S., Wilson, N., Zachariah, R., Harries, A.D.: Operational research capacity building in Asia: innovations, successes and challenges of a training course. Publ. Health Action 3 (2), 186-8 (2013). https://doi.org/10.5588/pha.13.0008 . PMID: 26393025; PMCID: PMC4463115

Pu, G., Wang, Y.: Survey of undergraduate or courses from IE programme: content, coverage, and gaps. J. Oper. Res. Soc., 1–20 (2023)

Vilalta-Perdomo, E., Hingley, M.: Beyond links and chains in food supply: a community OR perspective. J. Oper. Res. Soc. 69 (4), 580–588 (2018)

Koskela, L.: Why is management research irrelevant? Constr. Manag. Econ. 35 (1–2), 4–23 (2017)

O’Brien, F.A.: On the roles of OR/MS practitioners in supporting strategy. J. Oper. Res. Soc. 66 (2), 202–218 (2015)

Ackoff, R.L.: Resurrecting the future of operational research. J. Oper. Res. Soc. 30 , 189–199 (1979)

EPSRC. Review of the Research Status of Operational Research in the UK. Engineering and Physical Sciences Research Council, Swindon (2004)

Rosenhead, J.: Reflections on fifty years of operational research. J. Oper. Res. Soc. 60 (sup1), S5–S15 (2009). https://doi.org/10.1057/jors.2009.13

Kunc, M.: System Dynamics: Soft and Hard Operational Research. Springer, Cham (2017)

Download references

Author information

Authors and affiliations.

Atlântica University, UNINOVA, Lisbon, Portugal

Carla Silva

Atlântica University, CESNOVA, Minho, Portugal

Ricardo Ribeiro

Atlântica University, Barcarena, Portugal

Pedro Gomes

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Carla Silva .

Editor information

Editors and affiliations.

Faculty of Applied Informatics, Tomas Bata University in Zlin, Zlin, Czech Republic

Radek Silhavy

Petr Silhavy

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Silva, C., Ribeiro, R., Gomes, P. (2024). Algorithmic Optimization Techniques for Operations Research Problems. In: Silhavy, R., Silhavy, P. (eds) Data Analytics in System Engineering. CoMeSySo 2023. Lecture Notes in Networks and Systems, vol 935. Springer, Cham. https://doi.org/10.1007/978-3-031-54820-8_26

Download citation

DOI : https://doi.org/10.1007/978-3-031-54820-8_26

Published : 24 February 2024

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-54819-2

Online ISBN : 978-3-031-54820-8

eBook Packages : Intelligent Technologies and Robotics Intelligent Technologies and Robotics (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

  • Publish with us

Policies and ethics

  • Find a journal
  • Track your research

Operations Research - Linear programming problem | 11th Business Mathematics and Statistics(EMS) : Chapter 10 : Operations Research

Chapter: 11th business mathematics and statistics(ems) : chapter 10 : operations research.

Linear programming problem

The Russian Mathematician L.V. Kantorovich applied mathematical model to solve linear programming problems. He pointed out in 1939 that many classes of problems which arise in production can be defined mathematically and therefore can be solved numerically. This decision making technique was further developed by George B. Dantziz. He formulated the general linear programming problem and developed simplex method (1947) to solve complex real time applications. Linear programming is one of the best optimization technique from theory, application and computation point of view.

Definition:

Linear Programming Problem(LPP) is a mathematical technique which is used to optimize (maximize or minimize) the objective function with the limited resources.

Mathematically, the general linear programming problem (LPP) may be stated as follows.

Maximize or Minimize Z = c 1 x 1 + c 2 x 2 + … + c n x n

Subject to the conditions (constraints)

define linear programming problem in operation research

Short form of LPP

define linear programming problem in operation research

Some useful definitions:

Objective function:.

A function Z = c 1 x 1 + c 2 x 2 + …+ c n x n which is to be optimized (maximized or minimized) is called objective function.

Decision variable:

The decision variables are the variables, which has to be determined x j , j = 1,2,3,…, n , to optimize the objective function.

Constraints:

There are certain limitations on the use of limited resources called constraints.

define linear programming problem in operation research

A set of values of decision variables x j , j =1,2,3,…, n satisfying all the constraints of the problem is called a solution to that problem.

Feasible solution:

A set of values of the decision variables that satisfies all the constraints of the problem and non-negativity restrictions is called a feasible solution of the problem.

Optimal solution:

Any feasible solution which maximizes or minimizes the objective function is called an optimal solution.

Feasible region:

The common region determined by all the constraints including non-negative constraints x j ≥0 of a linear programming problem is called the feasible region (or solution region) for the problem.

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

IMAGES

  1. Operation Research 4: Linear Programming Problem graphical Solution

    define linear programming problem in operation research

  2. Lec-1 Graphical Method

    define linear programming problem in operation research

  3. Operation Research

    define linear programming problem in operation research

  4. Formulation of LPP

    define linear programming problem in operation research

  5. operations research introduction and linear programming problem

    define linear programming problem in operation research

  6. Lec-4 Graphical Method

    define linear programming problem in operation research

VIDEO

  1. Linear Programming Problem

  2. Linear Programming Problem

  3. TYBMS Operational Research Lecture 2

  4. Dynamic linear programming problems in Operational research (Lecture:1)

  5. Operation research

  6. Linear programming, characteristics, Advantages, Assumptions in operation Research Bcom, Mcom, Mba

COMMENTS

  1. Linear Programming: Definition, Formula, Examples, Problems

    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.

  2. Linear Programming (Definition, Methods & Examples)

    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.

  3. PDF IM2010: Operations Research Linear Programming Formulation (Chapter 3)

    Operations Research, Spring 2013 { Linear Programming Formulation 2/52 Introduction I It is important to learn how to model a practical situation as a linear program. I This process is typically called linear programming formulation or modeling. I We will introduce three types of LP problems, demonstrate how to formulate them, and discuss some important issues.

  4. Chapter 2: 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 ...

  5. PDF Linear Programming Notes I: Introduction and Problem Formulation

    Linear Programming Notes I: Introduction and Problem Formulation 1 Introduction to Operations Research Economics 172 is a two quarter sequence in Operations Research. Management Science majors are required to take the course. I do not know what Management Science is. Most of you picked the major. I assume that you either know what it is or do ...

  6. Linear programming

    Linear programming is a special case of mathematical programming (also known as mathematical optimization ). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the ...

  7. Linear Programming

    Introduction. Linear programming is one of the most widely used techniques of operations research and management science. Its name means that planning (programming) is being done with a mathematical model (called a linear-programming model) where all the functions in the model are linear functions.

  8. Tutorial and Practice in Linear Programming

    operations research (OR), management science, or decision science. ... solution and, therefore, becomes an unbounded problem. 1.3 Types of Linear Programming Linear programming can be integer linear programming (ILP), binary integer programming ... The following are steps to formulate the optimization problem: 1) Define a set of decision ...

  9. Using Modern Tools for Operations Research: Concepts & Codes

    Linear Programming. Linear Programming (LP) is both a fundamental and commonplace form of optimization: many, many problems may be expressed as linear programs (see Figure 1). For example, resource allocation problems and many others from business supply-chain applications may be modeled as LPs. We briefly introduce the basics of an LP problem ...

  10. Foundations of operations research: From linear programming to data

    Indeed, the term linear programming is very successful; it is short and informative: "linear" pointing at the mathematical types of equations and "programming" pointing at both the application of LP (originally in military programs - operations) and at the solution procedure that requires computer programming to repeat the solution ...

  11. Operations Research Problems: Statements and Solutions

    The objective of this book is to provide a valuable compendium of problems as a reference for undergraduate and graduate students, faculty, researchers and practitioners of operations research and management science. These problems can serve as a basis for the development or study of assignments and exams. Also, they can be useful as a guide ...

  12. Linear programming

    The a's, b's, and c's are constants determined by the capacities, needs, costs, profits, and other requirements and restrictions of the problem.The basic assumption in the application of this method is that the various relationships between demand and availability are linear; that is, none of the x i is raised to a power other than 1. In order to obtain the solution to this problem, it ...

  13. Linear programming: Theory and applications

    Management sciences and operations research make extensive use of linear models, whereas nonlinear programming problems tend to arise naturally in the physical sciences and engineering (Nocedal & Wright, 2006). ... When formulating an optimization problem, one must define an objective that is a function of a vector decision variables x and ...

  14. Introduction to Operations Research

    The modern field of operations research includes other disciplines such as computer science, industrial engineering, business practices in manufacturing and service companies, supply chain management, and operations management. Linear programming is a mathematical model for determining the best possible outcome such as maximizing profit or ...

  15. Linear Programming

    Foundations of operations research: From linear programming to data envelopment analysis. European Journal of Operational Research, Vol. 306, No. 3. ... New methods for solving imprecisely defined linear programming problem under trapezoidal fuzzy uncertainty. 5 July 2020 | Journal of Information and Optimization Sciences, Vol. 42, No. 3.

  16. PDF Linear Programming

    Example: Dual of the Diet Problem - Feasible Region Figure:The dual feasible region of the diet problem. Each black dot is a basic solution of the dual feasible region and corresponds to a basis of the primal problem in standard form. 2 1 0.5 1 2 (0.4, 0.4) (0.4286, 0.2857) (0, 0.5) 20/24

  17. What Is Linear Programming? Assumptions, Properties, Advantages

    As with any constrained optimisation, the main elements of LP are: Objective function; Constraints; Variables; 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 ...

  18. Algorithmic Optimization Techniques for Operations Research Problems

    Abstract. This paper provides an overview of the key concepts and approaches discussed in the field of Algorithmic Optimization Techniques. Operation re-search plays a role in addressing complex decision-making challenges across industries. This paper explores a range of algorithmic methods and optimization strategies employed to solve real ...

  19. PDF Linear programming

    Duality in linear programming. As we have seen in past lessons, linear programming are either maximization or minimization type, containing m conditions for n variables. As we show, for any such problem can be construct a symmetric problem, we'll call him dual problem. This problem has its own interpretation and also there is a deeper ...

  20. (PDF) Operational Research of Linear Programming

    Abstract. Operational research is a set of quantitative and other. scientific methods used to determine optimal economic and technical. solutions to complex problems. Operations research is ...

  21. Linear programming problem

    Definition: Linear Programming Problem (LPP) is a mathematical technique which is used to optimize (maximize or minimize) the objective function with the limited resources. Mathematically, the general linear programming problem (LPP) may be stated as follows. Maximize or Minimize Z = c1 x1 + c2 x2 + … + cn xn.

  22. PDF Mathematics Honors Theses Mathematics Department 2014 Operations Research

    The development of linear programming (LP) has been ranked among the most important scientific advances of the mid-20th century. Linear programming, the very basic but powerful tool of OR, involves the general problem of allocating limited resources among competing activities in a best possible way; Linear programming helps to select the level ...