Linear Programming
LINEAR PROGRAMMING
Description also available in video format (attached
below), for better experience use your desktop.
·
In Mathematics, linear programming is a method of
optimizing 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 utilization. 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.
Components
- Decision
Variables
- Constraints
- Data
- Objective
Functions
Characteristics
·
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.
Methods
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.
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.
Linear Programming
Applications
A real-time example would be
considering the limitations of labors 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 optimization techniques. The
applications of LP in some other fields are
- Engineering
– It solves design and manufacturing problems as it is helpful for doing
shape optimization
- Efficient
Manufacturing – To maximize profit, companies use linear expressions
- Energy
Industry – It provides methods to optimize the electric power system.
- Transportation
Optimization – For cost and time efficiency.
Importance
of Linear Programming
·
Linear programming
is broadly applied in the field of optimization 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.
Video
Description
·
Don’t forget to do
these things if you get benefitted from this article
o
Visit our Let’s contribute
page https://keedainformation.blogspot.com/p/lets-contribute.html
o
Follow our page
o
Like & comment
on our post
·
Comments