Home | ARTS | Operations Management
|
Introduction and Definition of Linear Programming – Problem Solving [SIMPLEX METHOD]
Operations Management - Introduction to Operations Research
Introduction and Definition of Linear Programming – Problem Solving [SIMPLEX METHOD]
Posted On :
The Simplex Method also called the ‘Simplex Technique’ or the Simplex Algorithm is an iterative procedure for solving a linear programming problem in a finite number of steps.
Linear Programming – Problem Solving [SIMPLEX METHOD]
The Simplex Method also called the ‘Simplex Technique’ or the Simplex Algorithm is an iterative procedure for solving a linear programming problem in a finite number of steps. The method provides an algorithm which consists in moving from one vertex / corner point of the region of feasible solutions to another vertex in such a manner that the value of the objective function at the succeeding vertex is improved [lesser in case of minimization and more in case of maximization] than at the preceding vertex. This procedure of jumping from one vertex to another is then repeated. Since the number of vertices is finite, the method leads to an optimal vertex in a finite number of steps or indicates the existence of an unbounded solution.
We will introduce various concepts / definitions that are related to simplex method in the following paragraphs.
The function that is to be either minimized or maximized is called as objective function. For example, it may represent the cost that you are trying to minimize or total revenue that is to be maximized and so on.
A set of equalities and inequalities that the feasible solution must satisfy is called as constraints of the problem.
A vector X, which is both feasible (satisfying all the constraints in the given problem) and optimal (obtaining the largest or smallest value for the objective function, depends upon the case) is known as optimal solution.
A solution vector, X, which satisfies all the constraints of the given problem is called feasible solution to the given LPP.
X of (AX=b) is a basic solution if the n components of X can be partitioned into m “basic” and n-m “non-basic” variables in such a way that: the m columns of A corresponding to the basic variables form a nonsingular basis and the value of each “non-basic” variable is 0. The constraint matrix A has m rows (constraints) and n columns (variables).
The set of basic variables is called the basis for the given problem.
Basic variables are set of variables, which are obtained by setting n-m variables values to zero, and are solving the resulting system.
A variable not in the basic solution, not part of the solution is called non-basic variable.
If we have a ‘less or equal’ to constraint, to convert that as an equation, a variable is added to the left hand side of the constraint; the new variable, which is added to the left hand side of the constraint is called as slack variable.
Ex: 2X1 + 5X2 ≤10
2X1 + 5X2 + SX3 = 10
The variable, SX3, is called as slack variable for the given constraint.
If we have a ‘greater or equal’ to constraint, to convert that as an equation, a variable is subtracted from the left hand side of the constraint; the new variable, which is subtracted, to the left hand side of the constraint is called as surplus variable.
Ex: 2X1 + 5X2 ≥10
2X1 + 5X2 – SX4 = 10
The variable, SX4, is called as surplus variable for the given constraint. Therefore, it is a variable added to the problem to eliminate greater-than constraints.
To get the initial basis in a ‘greater than or’ equal to constraint, additional variable is added in addition to the surplus variable. The
For some linear programs it is possible for the objective function to achieve infinitely high / low values, depends upon the objective. Such an LP is said to have an unbounded solution.
Let the objective function be
Max Z = CX
And the set of constraints are represented as
Introduction
The Simplex Method also called the ‘Simplex Technique’ or the Simplex Algorithm is an iterative procedure for solving a linear programming problem in a finite number of steps. The method provides an algorithm which consists in moving from one vertex / corner point of the region of feasible solutions to another vertex in such a manner that the value of the objective function at the succeeding vertex is improved [lesser in case of minimization and more in case of maximization] than at the preceding vertex. This procedure of jumping from one vertex to another is then repeated. Since the number of vertices is finite, the method leads to an optimal vertex in a finite number of steps or indicates the existence of an unbounded solution.
We will introduce various concepts / definitions that are related to simplex method in the following paragraphs.
Definations
1. Objective Function
The function that is to be either minimized or maximized is called as objective function. For example, it may represent the cost that you are trying to minimize or total revenue that is to be maximized and so on.
2. Constraints
A set of equalities and inequalities that the feasible solution must satisfy is called as constraints of the problem.
3. Optimal Solution
A vector X, which is both feasible (satisfying all the constraints in the given problem) and optimal (obtaining the largest or smallest value for the objective function, depends upon the case) is known as optimal solution.
4. Feasible Solution
A solution vector, X, which satisfies all the constraints of the given problem is called feasible solution to the given LPP.
5. Basic Solution
X of (AX=b) is a basic solution if the n components of X can be partitioned into m “basic” and n-m “non-basic” variables in such a way that: the m columns of A corresponding to the basic variables form a nonsingular basis and the value of each “non-basic” variable is 0. The constraint matrix A has m rows (constraints) and n columns (variables).
6. Basis
The set of basic variables is called the basis for the given problem.
7. Basic Variables
Basic variables are set of variables, which are obtained by setting n-m variables values to zero, and are solving the resulting system.
8. Non-basic Variables
A variable not in the basic solution, not part of the solution is called non-basic variable.
9. Slack Variable
If we have a ‘less or equal’ to constraint, to convert that as an equation, a variable is added to the left hand side of the constraint; the new variable, which is added to the left hand side of the constraint is called as slack variable.
Ex: 2X1 + 5X2 ≤10
2X1 + 5X2 + SX3 = 10
The variable, SX3, is called as slack variable for the given constraint.
10. Surplus Variable
If we have a ‘greater or equal’ to constraint, to convert that as an equation, a variable is subtracted from the left hand side of the constraint; the new variable, which is subtracted, to the left hand side of the constraint is called as surplus variable.
Ex: 2X1 + 5X2 ≥10
2X1 + 5X2 – SX4 = 10
The variable, SX4, is called as surplus variable for the given constraint. Therefore, it is a variable added to the problem to eliminate greater-than constraints.
11. Artificial Variable
To get the initial basis in a ‘greater than or’ equal to constraint, additional variable is added in addition to the surplus variable. The
12. Unbounded Solution
For some linear programs it is possible for the objective function to achieve infinitely high / low values, depends upon the objective. Such an LP is said to have an unbounded solution.
13. Standard form of LPP
Let the objective function be
Max Z = CX
And the set of constraints are represented as
AX<=b
Where, b-
the vector obtained by collecting all the right hand side of the constraints.
If we add set of slack variables to all the constraints
and if the constraints are equation, then that particular form is called as
standard form of linear programming problem.
Therefore,
Max Z = CX And the set of constraints are represented as
AX=b
Example
Consider the following LPP
Maximize Z = 15X1 + 10X2
Subject to constraints
4X1+6X2 <=360
3X1+0X2<=180
0X1+5X2 <=200
X1, X2>=0
The standard form of the given problem is obtained by adding slack variable X3 to the first constraint, X4 to the second and X5 to the third constraint.
4X1+6X2 +
X3=360
3X1+0X2 +X4=180
0X1+5X2 +X5=200
X1, X2, X3, X4 & X5>=0
The modified objective function is
Maximize Z = 15X1 + 10X2 + 0X3 + 0X4 +OX5
Let the objective function be
Max Z = CX
And the set of constraints are represented as
Where, b-
the vector obtained by collecting all the right hand side of the constraints.
This form, where all the constraints are ‘<=’ type for a maximization problem and ‘>=’ type for a minimization problem is known as canonical form of LPP.
AX=b
Example
Consider the following LPP
Maximize Z = 15X1 + 10X2
Subject to constraints
4X1+6X2 <=360
3X1+0X2<=180
0X1+5X2 <=200
X1, X2>=0
The standard form of the given problem is obtained by adding slack variable X3 to the first constraint, X4 to the second and X5 to the third constraint.
3X1+0X2 +X4=180
0X1+5X2 +X5=200
X1, X2, X3, X4 & X5>=0
The modified objective function is
Maximize Z = 15X1 + 10X2 + 0X3 + 0X4 +OX5
14. Canonical form of LPP
Let the objective function be
Max Z = CX
And the set of constraints are represented as
AX<=b
This form, where all the constraints are ‘<=’ type for a maximization problem and ‘>=’ type for a minimization problem is known as canonical form of LPP.
Tags : Operations Management - Introduction to Operations Research
Last 30 days 1356 views
