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 = 40x1

+ 30x2

needs to be maximized and the constraints are given as follows:

x1

+ x2
≤ 12

2x1

+ x2

≤ 16

x1

≥ 0, x2

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

- 40x1

- 30x2

+Z=0

x1

+ x2 + y1

=12

2x1

+ x2 + y2

=16

y1

and y2

are the slack variables.

Step 2: Construct the initial simplex matrix as follows:

⎡⎢ ⎢ ⎢⎣x1x2y1y2Z11100122101016−40−300010⎤⎥ ⎥ ⎥⎦
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

16 / 2 = 8

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 (R2

/ 2)

⎡⎢ ⎢ ⎢ ⎢⎣x1x2y1y2Z111001211/201/208−40−300010⎤⎥ ⎥ ⎥ ⎥⎦

Now apply R1

= R1 - R2

⎡⎢ ⎢ ⎢ ⎢⎣x1x2y1y2Z01/21−1/20411/201/208−40−300010⎤⎥ ⎥ ⎥ ⎥⎦

Finally R3

= R3 + 40R2

to get the required matrix.

⎡⎢ ⎢ ⎢ ⎢⎣x1x2y1y2Z01/21−1/20411/201/2080−100201320⎤⎥ ⎥ ⎥ ⎥⎦

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.

⎡⎢ ⎢ ⎢⎣x1x2y1y2Z012−10810−11040020101400⎤⎥ ⎥ ⎥⎦
Writing the bottom row in the form of an equation we get Z = 400 - 20y1

- 10y2. Thus, 400 is the highest value that Z can achieve when both y1 and y2

are 0.

Also, when x1

= 4 and x2

= 8 then value of Z = 400

Thus, x1

= 4 and x2

= 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

x+y=9

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.

O = (0, 0)

A = (7, 0)

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

D = (0, 6)

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.

Corner Points Z = 2x + 5y
O = (0, 0) 0
A = (7, 0) 14
B = (6, 3) 27
C = (4, 5) 33
D = (0, 6) 30

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.

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.