What is Linear Programming?
Linear programming (LP) or Linear Optimization 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 optimization problems involve the
calculation of profit and loss. Linear programming problems (LPP) are an important class
of optimization problems, that helps to find the feasible region and optimize 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 optimized
Components of Linear Programming
The basic components of the LP are as follows:
• Decision Variables
• Constraints
• Data
• 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
A. 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.
B. Graphical Method
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.