solving linear programming problems using matrices

Linear Programming

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

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

What is Linear Programming?

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

Linear Programming Definition

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

Linear Programming Examples

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

Linear Programming Formula

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

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

How to Solve Linear Programming Problems?

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

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

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

Linear Programming Methods

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

Linear Programming by Simplex Method

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

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

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

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

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

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

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

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

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

Step 2: Construct the initial simplex matrix as follows:

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

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

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

12 / 1 = 12

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

Thus, pivot element = 2.

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

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

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

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

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

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

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

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

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

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

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

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

Linear Programming by Graphical Method

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

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

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

where, x ≥ 0 and y ≥ 0.

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

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

x + 4y = 24

3x + y = 21

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Applications of Linear Programming

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

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

Related Articles:

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

Important Notes on Linear Programming

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

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

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

go to slide go to slide go to slide

Book a Free Trial Class

Practice Questions on Linear Programming

go to slide go to slide

FAQs on Linear Programming

What is meant by linear programming.

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

What is Linear Programming Formula?

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

What is the Objective Function in Linear Programming Problems?

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

How to Formulate a Linear Programming Model?

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

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

How to Find Optimal Solution in Linear Programming?

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

How to Find Feasible Region in Linear Programming?

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

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

What are Linear Programming Uses?

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

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

• Explore Our Geeks Community
• CBSE Class 12 Maths Notes

Chapter 1: Relations and Functions

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

Chapter 2: Inverse Trigonometric Functions

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

Chapter 3: Matrices

• Types of Matrices
• Matrix Operations
• Matrix Addition
• Matrix Multiplication
• Transpose of a Matrix
• Symmetric and Skew Symmetric Matrices
• Elementary Operations on Matrices
• Inverse of a Matrix by Elementary Operations - Matrices | Class 12 Maths
• Invertible Matrix

Chapter 4: Determinants

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

Chapter 5: Continuity and Differentiability

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

Chapter 6: Applications of Derivatives

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

Chapter 7: Integrals

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

Chapter 8: Applications of Integrals

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

Chapter 9: Differential Equations

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

Chapter 10: Vector Algebra

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

Chapter 11: Three-dimensional Geometry

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

Chapter 12: Linear Programming

Linear programming.

• Graphical Solution of Linear Programming Problems

Chapter 13: Probability

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

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

Linear programming is used in various industries such as shipping industries, manufacturing industries, transportation industries, telecommunications, and others. The term “linear programming” consists of two words linear and programming, the word linear tells the relation between various types of variables of degree one used in a problem and the word programming tells us the step-by-step procedure to solve these problems.

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

What is Linear Programming? 

Linear programming is a technique that helps us to find the optimum solution for a given problem, an optimum solution is a solution that is the best possible outcome of a given particular problem. In simple terms, it is the method to find out how to do something in the best possible way with given limited resources you need to do the optimum utilization of resources to achieve the best possible result in a particular objective. such as least cost, highest margin, or least time. 

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

Linear Programming Definition

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

Components of Linear Programming

A linear programming problem has two basic parts:

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

Linear Programming Examples

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

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

Types of Linear Programming Problems

Basically, there are many different linear programming problems but we will deal with three major linear programming problems in this article.

Manufacturing Problems

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

Diet Problems

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

Transportation Problems

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

Linear Programming Formula

A linear programming problem consists of,

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

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

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

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

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

Objective Function : Z = ax + by

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

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

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

How to Solve Linear Programming Problems?

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

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

Linear Programming Methods

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

• Simplex Method
• Graphical Method

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

Linear Programming Simplex Method

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

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

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

Linear Programming Graphical Method

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

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

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

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

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

Linear Programming Applications

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

Engineering Industries

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

Manufacturing Industries

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

Energy Industries

Energy companies use linear programming to optimize their production output.

Transportation Industries

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

Importance of Linear Programming

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

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

Linear Inequalities Algebraic Solution of Linear Inequalities

Linear Programming Problems

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

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

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

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

Solution: 

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

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

FAQs on Linear Programming

Q1: what is linear programming.

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

Q2: What are Linear Programming Problems?

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

Q3: What is Linear Programming Formula?

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

Q4: What are the different types of Linear Programming?

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

Q5: What are requirements of Linear Programming?

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

Q6: What are the advantages of Linear Programming?

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

Please Login to comment...

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

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

Improve your Coding Skills with Practice

Help Center Help Center

• Help Center
• Trial Software
• Product Updates
• Documentation

Solve linear programming problems

Description

Linear programming solver

Finds the minimum of a problem specified by

min x f T x  such that  { A ⋅ x ≤ b , A e q ⋅ x = b e q , l b ≤ x ≤ u b .

f , x , b , beq , lb , and ub are vectors, and A and Aeq are matrices.

linprog applies only to the solver-based approach. For a discussion of the two optimization approaches, see First Choose Problem-Based or Solver-Based Approach .

x = linprog( f , A , b ) solves min f'*x such that A*x  ≤  b .

x = linprog( f , A , b , Aeq , beq ) includes equality constraints Aeq*x = beq . Set A = [] and b = [] if no inequalities exist.

x = linprog( f , A , b , Aeq , beq , lb , ub ) defines a set of lower and upper bounds on the design variables, x , so that the solution is always in the range lb ≤ x ≤ ub . Set Aeq = [] and beq = [] if no equalities exist.

If the specified input bounds for a problem are inconsistent, the output fval is [] .

x = linprog( f , A , b , Aeq , beq , lb , ub , options ) minimizes with the optimization options specified by options . Use optimoptions to set these options.

x = linprog( problem ) finds the minimum for problem , a structure described in problem .

You can import a problem structure from an MPS file using mpsread . You can also create a problem structure from an OptimizationProblem object by using prob2struct .

[ x , fval ] = linprog( ___ ) , for any input arguments, returns the value of the objective function fun at the solution x : fval = f'*x .

[ x , fval , exitflag , output ] = linprog( ___ ) additionally returns a value exitflag that describes the exit condition, and a structure output that contains information about the optimization process.

[ x , fval , exitflag , output , lambda ] = linprog( ___ ) additionally returns a structure lambda whose fields contain the Lagrange multipliers at the solution x .

collapse all

Linear Program, Linear Inequality Constraints

Solve a simple linear program defined by linear inequalities.

For this example, use these linear inequality constraints:

x ( 1 ) + x ( 2 ) ≤ 2

x ( 1 ) + x ( 2 ) / 4 ≤ 1

x ( 1 ) - x ( 2 ) ≤ 2

- x ( 1 ) / 4 - x ( 2 ) ≤ 1

- x ( 1 ) - x ( 2 ) ≤ - 1

- x ( 1 ) + x ( 2 ) ≤ 2 .

Use the objective function - x ( 1 ) - x ( 2 ) / 3 .

Solve the linear program.

Linear Program with Linear Inequalities and Equalities

Solve a simple linear program defined by linear inequalities and linear equalities.

Use the linear equality constraint x ( 1 ) + x ( 2 ) / 4 = 1 / 2 .

Linear Program with All Constraint Types

Solve a simple linear program with linear inequalities, linear equalities, and bounds.

Set these bounds:

- 1 ≤ x ( 1 ) ≤ 1 . 5

- 0 . 5 ≤ x ( 2 ) ≤ 1 . 2 5 .

Linear Program Using the 'interior-point' Algorithm

Solve a linear program using the 'interior-point' algorithm.

Set options to use the 'interior-point' algorithm.

Solve the linear program using the 'interior-point' algorithm.

Solve LP Using Problem-Based Approach for linprog

This example shows how to set up a problem using the problem-based approach and then solve it using the solver-based approach. The problem is

max x ( x + y / 3 ) s u b j e c t t o { x + y ≤ 2 x + y / 4 ≤ 1 x - y ≤ 2 x / 4 + y ≥ - 1 x + y ≥ 1 - x + y ≤ 2 x + y / 4 = 1 / 2 - 1 ≤ x ≤ 1 . 5 - 1 / 2 ≤ y ≤ 1 . 2 5

Create an OptimizationProblem object named prob to represent this problem.

Convert the problem object to a problem structure.

Solve the resulting problem structure.

The returned fval is negative, even though the solution components are positive. Internally, prob2struct turns the maximization problem into a minimization problem of the negative of the objective function. See Maximizing an Objective .

Which component of sol corresponds to which optimization variable? Examine the Variables property of prob .

As you might expect, sol(1) corresponds to x , and sol(2) corresponds to y . See Algorithms .

Return the Objective Function Value

Calculate the solution and objective function value for a simple linear program.

The inequality constraints are

The objective function is - x ( 1 ) - x ( 2 ) / 3 .

Solve the problem and return the objective function value.

Obtain More Output to Examine the Solution Process

Obtain the exit flag and output structure to better understand the solution process and quality.

Set options to use the 'dual-simplex' algorithm.

Solve the linear program and request the function value, exit flag, and output structure.

fval , the objective function value, is larger than Return the Objective Function Value , because there are more constraints.

exitflag = 1 indicates that the solution is reliable.

output.iterations = 0 indicates that linprog found the solution during presolve, and did not have to iterate at all.

Obtain Solution and Lagrange Multipliers

Solve a simple linear program and examine the solution and the Lagrange multipliers.

Use the objective function

f ( x ) = - 5 x 1 - 4 x 2 - 6 x 3 .

Use the linear inequality constraints

x 1 - x 2 + x 3 ≤ 2 0

3 x 1 + 2 x 2 + 4 x 3 ≤ 4 2

3 x 1 + 2 x 2 ≤ 3 0 .

Constrain all variables to be positive:

Set Aeq and beq to [] , indicating that there are no linear equality constraints.

Call linprog , obtaining the Lagrange multipliers.

Examine the solution and Lagrange multipliers.

lambda.ineqlin is nonzero for the second and third components of x . This indicates that the second and third linear inequality constraints are satisfied with equalities:

3 x 1 + 2 x 2 + 4 x 3 = 4 2

3 x 1 + 2 x 2 = 3 0 .

Check that this is true:

lambda.lower is nonzero for the first component of x . This indicates that x(1) is at its lower bound of 0.

Input Arguments

F — coefficient vector real vector | real array.

Coefficient vector, specified as a real vector or real array. The coefficient vector represents the objective function f'*x . The notation assumes that f is a column vector, but you can use a row vector or array. Internally, linprog converts f to the column vector f(:) .

Example: f = [1,3,5,-6]

Data Types: double

A — Linear inequality constraints real matrix

Linear inequality constraints, specified as a real matrix. A is an M -by- N matrix, where M is the number of inequalities, and N is the number of variables (length of f ). For large problems, pass A as a sparse matrix.

A encodes the M linear inequalities

A*x <= b ,

where x is the column vector of N variables x(:) , and b is a column vector with M elements.

For example, consider these inequalities:

x 1 + 2 x 2 ≤ 10 3 x 1 + 4 x 2 ≤ 20 5 x 1 + 6 x 2 ≤ 30.

Specify the inequalities by entering the following constraints.

Example: To specify that the x-components add up to 1 or less, take A = ones(1,N) and b = 1 .

Aeq — Linear equality constraints real matrix

Linear equality constraints, specified as a real matrix. Aeq is an Me -by- N matrix, where Me is the number of equalities, and N is the number of variables (length of f ). For large problems, pass Aeq as a sparse matrix.

Aeq encodes the Me linear equalities

Aeq*x = beq ,

where x is the column vector of N variables x(:) , and beq is a column vector with Me elements.

For example, consider these equalities:

x 1 + 2 x 2 + 3 x 3 = 10 2 x 1 + 4 x 2 + x 3 = 20.

Specify the equalities by entering the following constraints.

Example: To specify that the x-components sum to 1, take Aeq = ones(1,N) and beq = 1 .

b — Linear inequality constraints real vector

Linear inequality constraints, specified as a real vector. b is an M -element vector related to the A matrix. If you pass b as a row vector, solvers internally convert b to the column vector b(:) . For large problems, pass b as a sparse vector.

b encodes the M linear inequalities

where x is the column vector of N variables x(:) , and A is a matrix of size M -by- N .

Example: To specify that the x components sum to 1 or less, use A = ones(1,N) and b = 1 .

beq — Linear equality constraints real vector

Linear equality constraints, specified as a real vector. beq is an Me -element vector related to the Aeq matrix. If you pass beq as a row vector, solvers internally convert beq to the column vector beq(:) . For large problems, pass beq as a sparse vector.

beq encodes the Me linear equalities

where x is the column vector of N variables x(:) , and Aeq is a matrix of size Me -by- N .

Example: To specify that the x components sum to 1, use Aeq = ones(1,N) and beq = 1 .

lb — Lower bounds real vector | real array

Lower bounds, specified as a real vector or real array. If the length of f is equal to the length of lb , then lb specifies that

x(i) >= lb(i) for all i .

If numel(lb) < numel(f) , then lb specifies that

x(i) >= lb(i) for 1 <= i <= numel(lb) .

In this case, solvers issue a warning.

Example: To specify that all x-components are positive, use lb = zeros(size(f)) .

ub — Upper bounds real vector | real array

Upper bounds, specified as a real vector or real array. If the length of f is equal to the length of ub , then ub specifies that

x(i) <= ub(i) for all i .

If numel(ub) < numel(f) , then ub specifies that

x(i) <= ub(i) for 1 <= i <= numel(ub) .

Example: To specify that all x-components are less than 1 , use ub = ones(size(f)) .

options — Optimization options output of optimoptions | structure as optimset returns

Optimization options, specified as the output of optimoptions or a structure as optimset returns.

Some options apply to all algorithms, and others are relevant for particular algorithms. See Optimization Options Reference for detailed information.

Some options are absent from the optimoptions display. These options appear in italics in the following table. For details, see View Optimization Options .

Example: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')

problem — Problem structure structure

Problem structure, specified as a structure with the following fields.

You must supply at least the solver field in the problem structure.

Data Types: struct

Output Arguments

X — solution real vector | real array.

Solution, returned as a real vector or real array. The size of x is the same as the size of f .

fval — Objective function value at the solution real number

Objective function value at the solution, returned as a real number. Generally, fval  =  f'*x .

exitflag — Reason linprog stopped integer

Reason linprog stopped, returned as an integer.

Exitflags 3 and -9 relate to solutions that have large infeasibilities. These usually arise from linear constraint matrices that have large condition number, or problems that have large solution components. To correct these issues, try to scale the coefficient matrices, eliminate redundant linear constraints, or give tighter bounds on the variables.

output — Information about the optimization process structure

Information about the optimization process, returned as a structure with these fields.

lambda — Lagrange multipliers at the solution structure

Lagrange multipliers at the solution, returned as a structure with these fields.

The Lagrange multipliers for linear constraints satisfy this equation with length(f) components:

f + A T λ ineqlin   + Aeq T λ eqlin + λ upper − λ lower = 0 ,

based on the Lagrangian

f T x + λ ineqlin T ( A x − b )   + λ eqlin T ( Aeq   x − beq ) + λ upper T ( x − ub ) + λ lower T ( lb − x ) .

This sign convention matches that of nonlinear solvers (see Constrained Optimality Theory ). However, this sign is the opposite of the sign in much linear programming literature, so a linprog Lagrange multiplier is the negative of the associated "shadow price."

Dual-Simplex Algorithm

For a description, see Dual-Simplex Algorithm .

Interior-Point-Legacy Algorithm

The 'interior-point-legacy' method is based on LIPSOL (Linear Interior Point Solver, [3] ), which is a variant of Mehrotra's predictor-corrector algorithm [2] , a primal-dual interior-point method. A number of preprocessing steps occur before the algorithm begins to iterate. See Interior-Point-Legacy Linear Programming .

The first stage of the algorithm might involve some preprocessing of the constraints (see Interior-Point-Legacy Linear Programming ). Several conditions might cause linprog to exit with an infeasibility message. In each case, linprog returns a negative exitflag , indicating to indicate failure.

If a row of all zeros is detected in Aeq , but the corresponding element of beq is not zero, then the exit message is

If one of the elements of x is found not to be bounded below, then the exit message is

If one of the rows of Aeq has only one nonzero element, then the associated value in x is called a singleton variable. In this case, the value of that component of x can be computed from Aeq and beq . If the value computed violates another constraint, then the exit message is

If the singleton variable can be solved for, but the solution violates the upper or lower bounds, then the exit message is

The preprocessing steps are cumulative. For example, even if your constraint matrix does not have a row of all zeros to begin with, other preprocessing steps can cause such a row to occur.

When the preprocessing finishes, the iterative part of the algorithm begins until the stopping criteria are met. (For more information about residuals, the primal problem, the dual problem, and the related stopping criteria, see Interior-Point-Legacy Linear Programming .) If the residuals are growing instead of getting smaller, or the residuals are neither growing nor shrinking, one of the two following termination messages is displayed, respectively,

After one of these messages is displayed, it is followed by one of the following messages indicating that the dual, the primal, or both appear to be infeasible.

The dual appears to be infeasible (and the primal unbounded). (The primal residual < OptimalityTolerance.)

The primal appears to be infeasible (and the dual unbounded). (The dual residual < OptimalityTolerance.)

The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(OptimalityTolerance). (The primal residual < 10*OptimalityTolerance.)

The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(OptimalityTolerance). (The dual residual < 10*OptimalityTolerance.)

The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.

The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.

Both the primal and the dual appear to be infeasible.

For example, the primal (objective) can be unbounded and the primal residual, which is a measure of primal constraint satisfaction, can be small.

Interior-Point Algorithm

The 'interior-point' algorithm is similar to 'interior-point-legacy' , but with a more efficient factorization routine, and with different preprocessing. See Interior-Point linprog Algorithm .

Alternative Functionality

The Optimize Live Editor task provides a visual interface for linprog .

[1] Dantzig, G.B., A. Orden, and P. Wolfe. “Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints.” Pacific Journal Math., Vol. 5, 1955, pp. 183–195.

[2] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization , Vol. 2, 1992, pp. 575–601.

[3] Zhang, Y., “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment.” Technical Report TR96-01 , Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.

Version History

Introduced before R2006a

intlinprog | mpsread | optimoptions | prob2struct | quadprog | Optimize

• Set Up a Linear Program, Solver-Based
• Typical Linear Programming Problem
• Maximize Long-Term Investments Using Linear Programming: Solver-Based
• Solver-Based Optimization Problem Setup
• Linear Programming Algorithms

Open Example

You have a modified version of this example. Do you want to open this example with your edits?

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office

Linear Programming (LP) – A Primer on the Basics

What is Linear Programming?

Linear programming is a method for solving complex, real-life business problems, using the power of mathematics. Organizations have been applying this method for 50+ years, across nearly all industries, to optimize operational efficiency—to get the most value from their limited resources. For example:

• Transportation providers, such as Air France , Swissport , and Uber , use mathematical programming to create optimal routing, staffing, and maintenance plans.
• Professional sports leagues, including the National Football League and Beko BBL , plan their game schedules using mathematical programming.
• Manufacturers use mathematical programming to plan and manage the procurement, production, and distribution of their products.

How Does Linear Programming Work?

Before you even start programming, you’ll need to collect some important information about your business problem:

• The questions you’re asking (“decision variables”)
• The goals you need to achieve (“linear objectives”)
• The limitations you’re facing (“linear constraints”)

Then, you need someone with mathematical and programming know-how to express this information as a mathematical model—in this case, a linear program. This requires some linear algebra and calculus skills, plus familiarity with mathematical notation and basic Python knowledge.

Not mathematically minded ? Our trusted partners can handle that for you.

As a final step, you will input your linear program into a “solver” (such as the Gurobi Optimizer), and the solver quickly determines how you can best reach your goals, given your limitations, and outputs a recommended action plan that answers your specific questions.

What Is an Example of Linear Programming?

Although there are countless ways to use linear programming, let’s look at a relatively simple one: the Furniture Factory Problem.

Imagine there’s a data scientist who’s in charge of developing a weekly production plan for a factory’s chairs and tables—two key products for this particular furniture factory.

The data scientist, using machine learning, predicts that the selling price of a chair is $45, and the selling price of a table is \$80.

The challenge: To identify how many chairs and tables to make, to maximize total revenue while satisfying the resource constraints.

This is a classic linear programming challenge. Find out how it works through our helpful Linear Programming Tutorial Video Series , which walks you through the entire process.

Where Can I Find More Linear Programming Code Examples?

You’ve come to the right place! We have a robust library of functional code examples and Jupyter Notebook modeling examples . These are a great way to jump in and start digging into the code and trying out your own variations.

What Are Decision Variables, Linear Objectives, and Linear Constraints?

Linear programming (LP) is a powerful framework for describing and solving optimization problems. It allows you to specify a set of decision variables, and a linear objective and a set of linear constraints on these variables.

To give a simple and widely used example, consider the problem of minimizing the cost of a selection of foods that meets all the recommended daily nutrient guidelines. The LP model would have:

• A set of decision variables that capture the amount of each food to buy.
• A linear objective that minimizes the total cost of purchasing the chosen foods.
• A linear constraint for each nutrient, requiring that the chosen foods together contain a sufficient quantity of that nutrient.

Using linear algebra notation, a linear program can be described as follows:

• Objective : minimize c T x
• Constraints : A x = b (linear constraints) l ≤ x ≤ u (bound constraints)

When described in this form, the vector x represents the decision variables, the vector c captures the linear objective function, the matrix equation Ax = b specifies the linear constraints on x , and the vectors l and u give the lower and upper bounds on x .

The set of applications of linear programming is literally too long to list. It includes everything from production scheduling to web advertising optimization to clothing manufacturing. LP touches nearly every commercial industry in some way.

What is the Simplex Method for Solving Linear Programming Models?

Linear programming was first introduced by Leonid Kantorovich in 1939 and then independently reintroduced by George Dantzig in 1947. Dantzig developed the first algorithm for solving linear programming problems, called the “simplex” method. Remarkably, this decades-old algorithm remains one of the most efficient and reliable methods for solving such problems today.

Learn more about the simplex method in practice .

How Does the Simplex Method Differ from the Interior-Point Method?

The primary alternative to the simplex method is the barrier or “interior-point” method. This approach has a long history, but its popularity is due to Karmarkar’s 1984 polynomial-time complexity proof.

Interior-point methods have benefited significantly from advances in computer architecture, including the introduction of multi-core processors and SIMD instruction sets, and they are generally regarded as being faster than simplex for solving LP problems from scratch.

However, the sheer variety of different linear programming models—and the many ways linear programming is used—mean that neither algorithm dominates the other in practice. Both are important in computational linear programming.

What Makes Gurobi a Solver of Choice for Linear Programming?

Given that the simplex and interior-point algorithms have been solving linear programs for decades, you might expect that all solvers (which use those algorithms to solve the linear programming models) would perform the same. But this is far from the case.

Computational benchmarks—across a range of models—show wide performance and robustness variations between solvers. For example, the open-source simplex solvers CLP and GLPK are, on average, a factor of 2.5 and 58 times slower than the Gurobi simplex solver, respectively.

What explains such wide disparities between implementations of such well-established methods? The differences primarily come down to three factors.

1. Sparse Linear Algebra

The constraint matrices that arise in linear programming are typically extremely sparse. Sparse matrices contain very few non-zero entries. It is not unusual to find constraint matrices containing only 3 or 4 non-zero values per columns of A. The steps of both the simplex and interior-point algorithms involve a number of computations with extremely sparse matrices and extremely sparse vectors. Sparse matrices must be factored, systems of sparse linear equations must be solved using the resulting factor matrices, the factor matrices must be modified, etc. It takes years of experience in sparse numerical linear algebra and linear programming to understand the computational issues associated with building efficient sparse matrix algorithms for LP.

2. Numerical Error Handling

The second factor is careful handling of numerical errors. Whenever you solve systems of linear equations in finite-precision arithmetic, you will always get slight numerical errors in the results. A crucial part of building an efficient LP algorithm is to design effective strategies for managing such errors. Failing to do so can mean the difference between a model solving in a fraction of a second and not solving at all.

3. Heuristic Strategies

The third factor is developing effective heuristic strategies for making the variety of choices that arise in the course of the solution process. To give one example, the simplex algorithm must repeatedly pick one variable from among many to enter the basis. The strategy used can have a profound effect on the runtime of the algorithm. Differences between the different strategies are often quite subtle, and in many cases, they are simply based on empirical observations about which schemes are most effective in practice. Again, choosing effective strategies takes years of experience.

Benchmark Results

Public benchmarks of different commercial linear programming solvers demonstrate the effectiveness of the approaches that Gurobi has taken for each of these issues. For both the simplex and barrier methods, the Gurobi solver provides both higher performance and better numerical robustness than competing solvers.

This difference matters when you are solving linear programming models, but more importantly, it also provides a more solid foundation on which to build the many algorithms that rely on linear programming as a subroutine. One very important example is the branch-and-bound algorithm that is used for solving mixed integer programming (MIP) models.

Ready to learn about mixed integer programming—another key type of mathematical programming? Check out our Mixed Integer Programming (MIP) Primer as well as our Recommended Books and Blogs .

Guidance for Your Journey

30 day free trial for commercial users, always free for academics.

GUROBI NEWSLETTER

Latest news and releases

• Welcome: Linear Programming Tutorial
• Mixed-Integer Programming (MIP) – A Primer on…
• Open-Source Mixed-Integer and Linear…

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License

Academic license, cloud trial.

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Looking for documentation?

Jupyter Models

Case studies, privacy overview.

• Mathematicians
• Math Lessons
• Square Roots
• Math Calculators

• Linear Programming – Explanation & Examples

JUMP TO TOPIC

What is Linear Programming?

Identifying variables, identify the objective function, the solution, example 1 solution, example 2 solution, example 3 solution, example 4 solution, example 5 solution, practice questions, linear programming – explanation and examples.

How to Solve Linear Programming Problems

• Identify the variables and the constraints.
• Find the objective function.
• Graph the constraints and identify the vertices of the polygon.
• Test the values of the vertices in the objective function.

• What are the inequalities that define this function?
• If the objective function is 3x+2y=P, what is the maximum value of P?
• If the objective function is 3x+2y=P, what is the minimum value of P

Constraints

The objective function.

Finding the Maximum

The Vertices

Finding the minimum, the feasible region.

Alternative Solution?

Previous Lesson  |  Main Page | Next Lesson

Solving Systems of Linear Equations Using Matrices

Hi there! This page is only going to make sense when you know a little about Systems of Linear Equations and Matrices , so please go and learn about those if you don't know them already.

The Example

One of the last examples on Systems of Linear Equations was this one:

Example: Solve

• x + y + z = 6
• 2y + 5z = −4
• 2x + 5y − z = 27

We went on to solve it using "elimination", but we can also solve it using Matrices!

Using Matrices makes life easier because we can use a computer program (such as the Matrix Calculator ) to do all the "number crunching".

But first we need to write the question in Matrix form.

In Matrix Form?

OK. A Matrix is an array of numbers:

Well, think about the equations:

They could be turned into a table of numbers like this:

We could even separate the numbers before and after the "=" into:

Now it looks like we have 2 Matrices.

In fact we have a third one, which is [x y z] :

Why does [x y z] go there? Because when we Multiply Matrices we use the "Dot Product" like this:

Which is the first of our original equations above (you might like to check that). Here it is for the second line.

 Try the third line for yourself.

The Matrix Solution

We can shorten this:

• A is the 3x3 matrix of x, y and z coefficients
• X is x, y and z , and
• B is 6, −4 and 27

Then (as shown on the Inverse of a Matrix page) the solution is this:

What does that mean?

It means that we can find the X matrix (the values of x, y and z) by multiplying the inverse of the A matrix by the B matrix .

So let's go ahead and do that.

First, we need to find the inverse of the A matrix (assuming it exists!)

Using the Matrix Calculator we get this:

(I left the 1/determinant outside the matrix to make the numbers simpler)

Then multiply A -1 by B (we can use the Matrix Calculator again):

And we are done! The solution is:

x = 5 y = 3 z = −2

Just like on the Systems of Linear Equations page.

Quite neat and elegant, and the human does the thinking while the computer does the calculating.

Just For Fun ... Do It Again!

For fun (and to help you learn), let us do this all again, but put matrix "X" first.

I want to show you this way, because many people think the solution above is so neat it must be the only way.

So we will solve it like this:

And because of the way that matrices are multiplied we need to set up the matrices differently now. The rows and columns have to be switched over ("transposed"):

And XA = B looks like this:

Then (also shown on the Inverse of a Matrix page) the solution is this:

This is what we get for A -1 :

In fact it is just like the Inverse we got before, but Transposed (rows and columns swapped over).

Next we multiply B by A -1 :

And the solution is the same:

x = 5 , y = 3 and z = −2

It didn't look as neat as the previous solution, but it does show us that there is more than one way to set up and solve matrix equations. Just be careful about the rows and columns!

Wolfram|Alpha Widgets Overview Tour Gallery Sign In

Share this page.

• StumbleUpon
• Google Buzz

Output Type

Output width, output height.

To embed this widget in a post, install the Wolfram|Alpha Widget Shortcode Plugin and copy and paste the shortcode above into the HTML source.

To embed a widget in your blog's sidebar, install the Wolfram|Alpha Widget Sidebar Plugin , and copy and paste the Widget ID below into the "id" field:

Save to My Widgets

Build a new widget.

We appreciate your interest in Wolfram|Alpha and will be in touch soon.

• IIT JEE Study Material

Solving Linear Equations Using Matrix

Solving linear equations using matrix is done by two prominent methods, namely the matrix method and row reduction or the Gaussian elimination method. In this article, we will look at solving linear equations with matrix and related examples. With the study notes provided below, students will develop a clear idea about the topic.

Download Complete Chapter Notes of Matrices & Determinants Download Now

How to Solve Linear Equations Using Matrix Method?

Let the equations be:

The first method to find the solution to the system of equations is the matrix method. The steps to be followed are given below:

• All the variables in the equations should be written in the appropriate order.
• The variables, their coefficients and constants are to be written on the respective sides.

Solving a system of linear equations by the method of finding the inverse consists of two new matrices, namely

• Matrix A: which represents the variables
• Matrix B: which represents the constants

A system of equations can be solved using matrix multiplication.

We can write the above equations in the matrix form as follows:

Where, \(\begin{array}{l}A=\left[ \begin{matrix} {{a}_{1}} & {{a}_{2}} & {{a}_{3}} \\ {{b}_{1}} & {{b}_{2}} & {{b}_{3}} \\ {{c}_{1}} & {{c}_{2}} & {{c}_{3}} \\ \end{matrix} \right],\ X=\left[ \begin{matrix} x \\ y \\ z \\ \end{matrix} \right],\ B=\left[ \begin{matrix} {{d}_{1}} \\ {{d}_{2}} \\ {{d}_{3}} \\ \end{matrix} \right]\end{array} \) .

A is the coefficient matrix, X is the variable matrix, and B is the constant matrix.

The second method to find the solution for the system of equations is row reduction or Gaussian elimination.

• The augmented matrix for the linear equations is written.
• Use elementary such that all the elements below the main diagonal are zero. If a zero is obtained on the diagonal, perform the row operation such that a nonzero element is obtained.
• Back substitution is used to find the solution.

Related Topics:

• Introduction to Matrices
• Types of Matrices
• Matrix Operations
• Adjoint and Inverse of a Matrix
• Rank of a Matrix and Special Matrices

Solution to a System of Equations

A set of values of x, y, and z which simultaneously satisfy all the equations, is called a solution to the system of equations.

Consider, x + y + z = 9

2x – y + z = 5

4x + y – z = 7

Here, the set of values – x = 2, y = 3, z = 4, is a solution to the system of linear equations.

Because, 2 + 3 + 4 = 9, 4 – 3 + 4 = 5, 8 + 3 – 4 = 7

Consistent Equations

If the system of equations has one or more solutions, then it is said to be a consistent system of equations; otherwise, it is an inconsistent system of equations. For example, the system of linear equations x + 3y = 5;  x – y = 1 is consistent because x = 2, y = 1 is a solution to it. However, the system of linear equations x + 3y = 5; 2x + 6y = 8 is inconsistent because there is no set of values of x and y, which may satisfy the two equations simultaneously.

Condition for consistency of a system of linear equation AX = B

(b) If |A| = 0, and (Adj A) B ≠ 0, then the system is inconsistent.

(c) If |A| = 0, and (Adj A) B = 0, then the system is consistent and has infinitely many solutions.

Note AX = 0 is known as the homogeneous system of linear equations, and here, B = 0. A system of homogeneous equations is always consistent.

The system has a non-trivial solution (non-zero solution), if | A | = 0

Theorem 1: Let AX = B be a system of linear equations, where A is the coefficient matrix. If A is invertible, then the system has a unique solution, given by X = A -1 B

Uniqueness: If AX = B has two sets of solutions X 1 and X 2 , then AX 1 = B and AX 2 = B (Each equal to B).

⇒  AX 1 = AX 2

By cancellation law, A is invertible.

⇒  X 1 = X 2

Hence, the given system AX = B has a unique solution.

Note: A homogeneous system of equations is always consistent.

Problems on Solving Linear Equations Using Matrix Method

Illustration: Let A = \(\begin{array}{l}\left[ \begin{matrix} x+y & y \\ 2x & x-y \\ \end{matrix} \right],\ B=\left[ \begin{matrix} 2 \\ -1 \\ \end{matrix} \right],\ C = \left[ \begin{matrix} 3 \\ 2 \\ \end{matrix} \right]\end{array} \) . If AB = C, then find the matrix A 2 .

By solving AB = C, we get the values of x and y. Then by substituting these values in A, we obtain A 2

Here \(\begin{array}{l}\left[ \begin{matrix} x+y & y \\ 2x & x-y \\ \end{matrix} \right]\left[ \begin{matrix} 2 \\ -1 \\ \end{matrix} \right]=\left[ \begin{matrix} 3 \\ 2 \\ \end{matrix} \right]\\ \Rightarrow \left[ \begin{matrix} 2\left( x+y \right)-y \\ 2x.2-\left( x-y \right) \\ \end{matrix} \right]=\left[ \begin{matrix} 3 \\ 2 \\ \end{matrix} \right]\\ \Rightarrow 2\left( x+y \right)-y=3 \:\:and \:\:4x-\left( x-y \right)=2\end{array} \) \(\begin{array}{l}\Rightarrow \,\,2x+y=3\;\;\;\;and\;\;\;\;3x+y=2\end{array} \) Subtracting the two equations, we get, x = -1 So, y = 5 .

Illustration: Solve the following equations by matrix inversion

The given equation can be written in a matrix form as AX = D, and then by obtaining A -1 and multiplying it on both sides, we can solve the given problem.

then matrix A equals:

has no solution if a and b are

By applying row operation in the given matrices and comparing them, we can obtain the required result.

\(\begin{array}{l}\Rightarrow \,a=-3 \;\;and \;\;b\ne -1/3 \end{array} \) .

Applying \(\begin{array}{l}{{R}_{3}}\to {{R}_{3}}-2{{R}_{2}}+{{R}_{1}} \;\;and \;\;\;{{R}_{2}} to {{R}_{2}}-2{{R}_{1}}\end{array} \) we get;

Frequently Asked Questions

What do you mean by a linear equation.

A linear equation is an equation that has one or more variables having degree one.

Name two methods to solve linear equations using matrices.

The matrix multiplication method and the Gaussian elimination method are two methods to solve linear equations using matrices.

What do you mean by consistent equations?

A consistent system of equations is an equation having one or more solutions.

Give the formula used in the matrix multiplication method for solving linear equations.

We use the formula AX = B in the matrix multiplication method for solving linear equations. Here, A is the coefficient matrix, X is the variable matrix, and B is the constant matrix.

Put your understanding of this concept to test by answering a few MCQs. Click ‘Start Quiz’ to begin!

Select the correct answer and click on the “Finish” button Check your score and answers at the end of the quiz

Visit BYJU’S for all Maths related queries and study materials

Your result is as below

Request OTP on Voice Call

Leave a Comment Cancel reply

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

Post My Comment

• Share Share

Register with Aakash BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

International Conference on Human Interaction and Emerging Technologies

IHIET 2019: Human Interaction and Emerging Technologies pp 247–252 Cite as

Solving Game Theory Problems Using Linear Programming and Genetic Algorithms

• Marwan Abdul Hameed Ashour 18 , 19 , 20 ,
• Iman A. H. Al-Dahhan 18 , 19 , 20 &
• Sahar M. A. Al-Qabily 18 , 19 , 20  
• Conference paper
• First Online: 25 July 2019

3375 Accesses

4 Citations

Part of the Advances in Intelligent Systems and Computing book series (AISC,volume 1018)

In this paper, we proposed an efficient genetic algorithm that will be applied to linear programming problems in order to find out the Fittest Chromosomes. This paper aim to find the optimal strategy of game theory in basketball by using genetic algorithms and linear programming as well as the comparison between traditional methods and modern methods being represented in artificial intelligence, Genetic algorithms as applied in this paper. A new method was adopted in finding the optimal game strategy for player (A) and player (B) through the application of linear programming and finding solutions by using (GA) in MATLAB. The final results confirmed the equivalent of linear programming and genetic algorithms as the model was in the linear approach, and in the case of nonlinearity, genetic algorithm will be in favor definitely. The Matlab program in the calculation of the results for great possibility optimization should also be adopted.

• Game theory
• Genetic Algorithm
• Linear Programming
• Optimal strategy

This is a preview of subscription content, access via your institution .

Buying options

• 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

Guo, C., Yang, X.: A programming of genetic algorithm in Matlab7.0, China (2011)

Google Scholar  

Lee, C.: Multi-objective game-theory models for conflict analysis in reservoir watershed management. Chemosphere 87 , 608–613 (2012)

CrossRef   Google Scholar  

Sadiq, S., Zhao, J.: Money Basketball: Optimizing Basketball Player Selection Using SAS®, paper China (2014)

Ismail, I.A., El Ramly, N.A., El Kafrawy, M.M., Nasef, M.M.: Game theory using genetic algorithms. Proceedings of the World Congress on Engineering (2007)

Datta, S., Garai, C., Das, C.: Efficient genetic algorithm on linear programming problem for fittest chromosomes. J. Global Res. Comput. Sci. 1 (2012)

Sivaraj, R., Ravichandran, T.: An efficient grouping genetic algorithm. Int. J. Comput. Appl. 21 (7), 0975–8887, May (2011)

Singh, A.P.: Optimal solution strategy for games. Int. J. Comput. Sci. Eng. 2 (9), 2778–2782 (2010)

Linear programming and game theory by Chakravorthy, J.G., University of Calcutta and Ghosh, P.R., University of Calcutta

Goldberg, D.E.: Genetic algorithms. Addison-Wesley (1989)

Gen, M.: Genetic Algorithms and Engineering Optimization. John Wiley and Sons, Inc. (2000)

Peters, H.: Game Theory: A Multi-Leveled Approach, p. 1989. Springer- Verlag, Berlin (2008)

Schecter, S., Gintis, H.: Introduction to Game Theory. North Carolina State University, January 17 (2012)

Shi, Y., Xing, Y., Mou, C., Kuang, Z.: An optimization model based on game theory. J. of Multimedia 9 (4), 583, April 2014, Genetic algorithms. Sci. Am 267, 66e72 (1992)

Download references

Author information

Authors and affiliations.

College of Administration and Economics University of Baghdad, Baghdad, Iraq

Marwan Abdul Hameed Ashour, Iman A. H. Al-Dahhan & Sahar M. A. Al-Qabily

Continuing Education Center/University of Bagdad, Baghdad, Iraq

Business Economics College Al-Nahrain University, Baghdad, Iraq

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Marwan Abdul Hameed Ashour .

Editor information

Editors and affiliations.

Institute for Advanced Systems Engineering, University of Central Florida, Orlando, FL, USA

Prof. Tareq Ahram

Université de Reims Champagne Ardenne, GRESPI, Reims, France

Prof. Redha Taiar

Laboratoire Motricité Humaine, Expertise, Sport, Santé, Université Côte d’Azur, Nice Cedex 3, France

Prof. Serge Colson

IFMK Niçois, Université Côte d’Azur, Nice Cedex 3, France

Prof. Arnaud Choplin

Rights and permissions

Reprints and Permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Cite this paper.

Ashour, M.A.H., Al-Dahhan, I.A.H., Al-Qabily, S.M.A. (2020). Solving Game Theory Problems Using Linear Programming and Genetic Algorithms. In: Ahram, T., Taiar, R., Colson, S., Choplin, A. (eds) Human Interaction and Emerging Technologies. IHIET 2019. Advances in Intelligent Systems and Computing, vol 1018. Springer, Cham. https://doi.org/10.1007/978-3-030-25629-6_39

Download citation

DOI : https://doi.org/10.1007/978-3-030-25629-6_39

Published : 25 July 2019

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-25628-9

Online ISBN : 978-3-030-25629-6

eBook Packages : Engineering Engineering (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

• Find a journal
• Publish with us