Simplex 4
Simplex 4
Simplex 4
Simplex method is a linear programming technique in which we start with a certain solution which is
feasible. We improve this solution in a number of consecutive stages until we arrive at an optimal solution.
For arriving at the solution of LPP by this method, the constraints and the objective function are presented in a
table known as simplex table. Then following a set procedure and rules, the optimal solution is obtained making step by
step improvement.
Thus simplex method is an iterative ( step by step ) procedure in which we proceed in systematic steps from an
initial Basic Feasible Solution to another Basic Feasible Solution and finally, in a finite number of steps to an optimal
basic feasible solution, in such a way that the value of the objective function at each step is better than that at the
preceding steps. In other words the simplex algorithm consists of the following main steps.
Given a system of m linear equation with n variables (m < n). The solution obtained by setting ( n-m ) variables
equal to zero and solving for the remaining m variables is called a basic solution
The m variables are called basic variables and they form the basic solution. The (n-m) variables which are put to
zero are called as non-basic variables.
A basic solution is said to be a non-degenerate basic solution if none of the basic variables is zero
A basic solution is said to be a degenerate basic solution if one or more of the basic variables are zero.
Feasible solution
A feasible solution to a Linear Programming Problem is the set of values of the variables which satisfy all the
constraints and non-negative restrictions of the problem
A feasible solution to a LPP is said to be optimum if it optimises the objective function of the problem
A feasible solution to a LPP in which the vectors associated to non zero variables are linearly independent is
called a basic feasible solution
Slack variables
If a constraints has a sign <= (less than or equal to ) then in order to make it an equality (=) add some variables
to the left hand side. The variables which are added to left hand sides of the constraints to convert them into equalities
are called the slack variables. The value of this variable can usually be interpreted as the amount of unused resources.
Surplus variables
If a constraint has sign >= then in order to make it an equality, subtract some variable from its left hand side.
The variables which are subtracted from the left hand sides of the constraints to convert them into equalities are called
surplus variables. The value of this variable can be interpreted as the amount over and above the required minimum
level.
Basis
The variables whose values are not restricted to zero in the current basic solution are listed in one column of the
simplex table known as basis
Basic variables
The variables which are listed in the basis are called basic variables and others are known as non basic variables.
Vector
Unit Vector
A vector with one element 1 and all other elements zero, is a unit vector
Delta j is the net profit or loss if one unit of the variable in the respective column is introduced. The row
containing delta j values is called net evaluation row or index row.
Delta j = Zj – Cj
Where Cj is the coefficient of Xj variables in the objective function and Zj is the sum of the products of coefficients of
basic variables in the objective function and the vector Xj
Minimum Ratio
Minimum ratio is the lowest non negative ratio in the replacing ratio column. The replacing ratio column
contains values obtained by dividing each element in the column showing the values of the basic variable by the
corresponding elements in the incoming vector.
The column which has the highest negative delta j in a maximisation problem or the highest positive delta j in a
minimisation problem, is called incoming vector. The entering variable column is known as the key column or pivot
column which is shown marked with an arrow at the bottom
Key row (outgoing vector)
The row which relates to the minimum ratio, is the outgoing vector. The leaving variable row is called the key
row or pivot row or pivot equation
Key element
Key element is that element of the simplex table which lies both in the key row and key column. The element at
the intersection of the pivot column and pivot row is called the pivot element or key element or leading element.
Iteration
Iteration means step by step process followed in simplex method to move from one basic feasible solution to
another.
Artificial variables are fictitious variables. They are incorporated only for computational purposes. They have
no physical meaning. Artificial variables are introduced when the constraints are of the type >/= or =.
Constraints of some LPPs may have >/= or = signs. In such problems even after introducing surplus variables,
the simplex table may not contain identity matrix. Identity matrix contains columns of the type (1,0,0), (0,1,0), (0,0,1).
They are also known as unit vectors. So to get identity matrix in the simplex table , introduce artificial variables to all or
some of constraints as per requirement. This technique of LPP in which artificial variables are used for solving is known
as artificial variable technique. The problems where artificial variables are introduced can be solved by the method
called Big M Method
BIG M Method or M – technique or Method of penalties
Big M method is a modified simplex method for solving a LPP when a high penalty cost ( or profit ) M
has been assigned to the artificial variable in the objective function. The quantity M is known as penalty. In
maximisation cases –M and in minimisation cases +M are assigned to the artificial variables as their coefficients in
objective functions. Big M method can be applied to minimisation problems as well as maximisation problems.
Big M method
Step 1 : Express the linear programming problem in the standard form by introducing slack or surplus variables , if
necessary.
Step 2 : Introduce the non-negative artificial variables to the left hand side of all the constraints of >/= or = type. The
purpose of introducing artificial variables is just to obtain an initial basic feasible solution
While making iterations, using simplex method, one of the following three cases may arise :
1. If no artificial variable remains in the basis and the optimality condition is satisfied, then the current solution is
an optimal basic feasible solution
2. If atleast one artificial variable appears in the basis at zero level and the optimality condition is satisfied, then
the current solution is an optimal basic feasible solution
3. If atleast one artificial variable appears in the basis at non-zero level and the optimality condition is satisfied,
then the original problem has no feasible solution. The solution satisfies the constraints but does not optimize
the objective function since it contains a very large penalty M and is called pseudo-optimal solution
All problems of minimisation are to be converted to maximisation. In the first phase, -1 is the coefficient of the
artificial variable and zero is of all other variables. Simplex table obtained in phase 1 is used in phase 2. In phase 2 there
is no artificial variable.
Infeasibility
When no solution satisfying all constraints is obtained for a LPP there exists no feasible solution
Unbounded solutions
When a linear programming problem does not have finitely valued solutions, the solution is said to be
unbounded. If the solution of a variable can be made infinitely large without violating constraints, the solution obtained
is unbounded. For such problems feasible region is unbounded.
If there is no non-negative replacement ratio in solving a LPP then the solution is unbounded.
Degeneracy
A basic feasible solution of a linear programming problem is said to be degenerate if at least one of the basic
variables is zero. One of the basic theorems of Linear Programming is that the number of non- zero valued variables in a
LPP should be equal to the number of constraints. Therefore, if one of the basic variables is zero, the number of non-
zero valued variables become one less than the number of constraints ( non-basic variables are always zero). This
situation is called degeneracy because from this simplex table, we cannot continue to reach next simple table as the
variable to be replaced is already zero. The degeneracy occurs in a LPP at the very first iteration or in the subsequent
iteration.
Duality
Every LPP is associated with another LPP called dual. Original problem is called primal. Dual problems may be
defined as mirror image problems of primal problems. The final simplex table which gives the solution of the primal,
also contains the solution of the dual. Similarly the final simplex table which gives the solution of the dual, also contains
the solution of the primal
A shadow price indicates the amount by which the optimal value of the objective function would change if any
constraint is changed marginally. A shadow price therefore indicates marginal change in the value of the objective,
given a unit change in a constraint. The shadow price is also called dual price.
Sensitivity Analysis
After formulating mathematical model to a LPP and then attaining the optimum solution of the problem, it may
be required to study the effect of changes (discrete or continuous), in the different parameters of the problem, on the
optimum solution.
For example : After solving a LPP one may find that certain values of the variables changed and therefore, he would like
to know whether the current optimal solution is still optimal under changed circumstances.
Analysis of such problems arising due to slight change made in the parameters or the structure of a given LPP
after attaining its optimum solution are known as Post Optimality Analysis or Sensitivity Analysis.