Bahçeşehir Cyprus University
DEPARTMENT OF INDUSTRIAL ENGINEERING
OPERATIONS RESEARCH II
INE 3201
Lecturer: Dr. Faramarz Khosravi
AN ALGEBRAIC OVERVIEW OF THE SIMPLEX METHOD
✓ m= number of constraints ; n= number of variables : infinite number of
solutions
✓ A basic solution is obtained by setting m of the n variables equal to zero and
solving the equations simultaneously for the values of the other three
variables.
✓ Mathematically, we are guaranteed a solution only if the resulting three
equations are linearly independent.
✓ The simplex method is designed to guarantee that a solution exists for the
basic variables at each iteration.
AN ALGEBRAIC OVERVIEW OF THE SIMPLEX METHOD
Cont 1
Cont 2
Number of variables in the standard form is n=4
Number of constraints is m =2
Basic Feasible Solution will have :
m Variables non negative : Basic Variables
(n-m) equal to zero : Non- Basic Variables
AN ALGEBRAIC OVERVIEW OF THE SIMPLEX METHOD
n=4
m =2
AN ALGEBRAIC OVERVIEW OF THE SIMPLEX METHOD
n=4
m =2
How can we search the basic feasible solutions of a
standard model?
GAUSS-JORDAN ELIMINATION (ROW)
OPERATIONS
• X1+X2-X3=7
• X1-X2+2X3=3 1 1 -1 1 0 0
• 2X1+X2+X3=9
1 -1 2 0 1 0
• X1,X2,X3=?
2 1 1 0 0 1
• A.x=b
SUMMARY OF THE SIMPLEX ALGORITHM
❑Optimality condition: The entering variable in a maximization (minimization) problem is the non-basic
variable with the most negative (positive) coefficient in the z-row. Ties are broken arbitrarily. The optimum
is reached at the iteration where all the z-row coefficients are nonnegative (non-positive).
❑Feasibility condition: For both the maximization and the minimization problems, the leaving variable is the
basic variable associated with the smallest nonnegative ratio with strictly positive denominator. Ties are
broken arbitrarily.
❑Gauss-Jordan row operations:
1. Pivot row
a. Replace the leaving variable in the basic column with the entering variable.
b. New pivot row = Current pivot row / Pivot element
2. All other rows, including z
New row = (Current row) – (Its pivot column coefficient) x (New pivot row)
AN ALGEBRAIC OVERVIEW OF THE SIMPLEX METHOD
Maximum number
of corner points
SIMPLEX ALGORITHM
❑The simplex method always starts at the origin where all the
decision variables, xj , j = 1, 2,.., n are zero.
❑The design of the simplex method does not allow simultaneous
increases in variables. Instead, it targets the variables one at a
time.
❑ The variable slated for increase is the one with the largest rate of
improvement in z.
❑The path of the simplex algorithm always connects corner points.
In the present example the path to the optimum is A→B→C.
❑Each corner point along the path is associated with an iteration.
❑It is important to note that the simplex method always moves
alongside the edges of the solution space, which means that the
method does not cut across the solution space. For example, the
simplex algorithm cannot go from A to C directly.
SIMPLEX ALGORITHM – Example 1
• Reddy Mikks produces both interior and exterior paints from two raw materials, M1 and M2. The
following table provides the basic data of the problem:
The daily demand for interior paint cannot exceed that for exterior paint by more than 1 ton. Also, the
maximum daily demand for interior paint is 2 tons. Reddy Mikks wants to determine the optimum (best)
product mix of interior and exterior paints that maximizes the total daily profit.
Z - (5x1 + 4x2) = 0
Z – 5x1-4x2 +0s1 + 0s2 +0s3 + 0s4 =0
6x1+4x2+s1 = 24 • Optimality condition
• Entering variable
• Feasibility condition
Basis x1 x2 s1 s2 s3 s4 RHS (b)
Z -5 -4 0 0 0 0 • Leaving variable
0
S1 6 4 1 0 0 0 24
S2 1 2 0 1 0 0 6
S3 -1 1 0 0 1 0 1
S4 0 1 0 0 0 1 2
X1 = 1
X2= 5
Z - 5*1 - 4*5 = 25-25=0
SIMPLEX ALGORITHM
• Starting simplex tableau:
• Optimality condition
• Entering variable
• Feasibility condition
• Leaving variable
SIMPLEX ALGORITHM
The Graphical Method and THE SIMPLEX METHOD – Example 2
❑HighTech Industries imports electronic components that are used to assemble
two different models of personal computers. One model is called the Deskpro,
and the other model is called the Portable.
❑HighTech’s management is currently interested in developing a weekly
production schedule for both products. The Deskpro generates a profit
contribution of $50 per unit, and the Portable generates a profit contribution of
$40 per unit.
❑For next week’s production, a maximum of 150 hours of assembly time can be
made available. Each unit of the Deskpro requires 3 hours of assembly time, and
each unit of the Portable requires 5 hours of assembly time.
❑In addition, HighTech currently has only 20 Portable display components in
inventory; thus, no more than 20 units of the Portable may be assembled.
❑Finally, only 300 square feet of warehouse space can be made available for new
production. Assembly of each Deskpro requires 8 square feet of warehouse
space; similarly, each Portable requires 5 square feet.
x1 = number of units of the Deskpro
x2 = number of units of the Portable
The development of the simplex method computations is facilitated by
imposing three requirements on the LP model:
1. All the constraints must have nonnegative right-hand sides.
2. All the constraints must be written as equations
3. All the variables are nonnegative
HOMEWORK
SPECIAL CASES IN SIMPLEX METHOD
1. Degeneracy
2. Alternative optima
3. Unbounded solutions
4. Non-existing (or infeasible) solutions
SPECIAL CASES IN SIMPLEX METHOD
DEGENERACY
❑In the application of the feasibility condition of the simplex method,
a tie for the minimum ratio may occur and can be broken arbitrarily.
❑When this happens, at least one basic variable will be zero in the
next iteration, and the new solution is said to be degenerate.
❑Degeneracy can cause the simplex iterations to cycle indefinitely,
thus never terminating the algorithm.
❑The condition also reveals the possibility of at least one redundant
constraint.
SPECIAL CASES IN SIMPLEX METHOD
DEGENERACY
s1 s2
s1
s2
s2
SPECIAL CASES IN SIMPLEX METHOD
ALTERNATIVE OPTIMA
An LP problem may have an infinite number of alternative optima when the objective
function is parallel to a non-redundant binding constraint (i.e., a constraint that is
satisfied as an equation at the optimal solution).
s1 s2
s1
s2
s2
SPECIAL CASES IN SIMPLEX METHOD
UNBOUNDED SOLUTION
❑ In some LP models, the solution space is unbounded in at least one
variable—meaning that variables may be increased indefinitely without
violating any of the constraints. The associated objective value may also
be unbounded in this case.
❑ An unbounded solution space may signal that the model is poorly
constructed. The most likely irregularity in such models is that some key
constraints have not been accounted for.
❑ Another possibility is that estimates of the constraint coefficients may
not be accurate.
SPECIAL CASES IN SIMPLEX METHOD
UNBOUNDED SOLUTION
s1 s2
s1
s2
SPECIAL CASES IN SIMPLEX METHOD
INFEASIBLE SOLUTION
❑ LP models with inconsistent constraints have no feasible solution.
❑ This situation does not occur if all the constraints are of the type ≤ with
nonnegative right-hand sides because the slacks provide an obvious
feasible solution.
❑ For other types of constraints, penalized artificial variables are used to
start the solution.
❑ If at least one artificial variable is positive in the optimum iteration, then
the LP has no feasible solution. From the practical standpoint, an
infeasible space points to the possibility that the model is not formulated
correctly.
SPECIAL CASES IN SIMPLEX METHOD
INFEASIBLE SOLUTION
e3 s1 a3