Lecture 2

Chapter 3, ND Vohra Book

Linear Programming II:
Simplex Method
Steps in Simplex Method
1. Write down the problem preferably
in a tabular form.
2. Formulate the objective and
constraint functions.
3. For maximization problem all
constraints should be ≤
4. For minimization problem, all
constraints should be ≥
5. If required, multiply the constraint
equation with -1
6. Standardize the problem
Introduce slack variables to convert
each constraint to an equality.
Add artificial variables to constraints to
have a starting solution. Normally
required for constraints with ≥ sign
Steps in Simplex Method..contd.
7. Set up the first tableau using slack
variables and artificial variables
as necessary.
8. Obtain initial solution also
known as Basic Solution.
9. Identify Key Column
corresponding to with highest
positive value of ∆ij for
maximization objective and
highest negative value of ∆ij for
minimization objective
10.Calculate Replacement Ratio by
dividing solution value with
corresponding element in the key
column. The row with minimum
positive ratio is called as Key Row
Steps in Simplex Method..contd.

11.Identify the key element – one

common to both key column and
key row. Non-basic variable
corresponding to Key column will
replace the Basic variable
corresponding to the Key Row
and prepare a Revised tableu
12.Perform row operations to
complete the new solution:
Write down Replacement Row by
dividing each element of the Key Row
with Key Element
For each row other than the Key Row,
find the values using the formula:
New Row Element = Old Row Element
less Replacement Row value x Row
Element in Key Column.
Steps in Simplex Method..contd.

13.Check solution for optimality.

To be optimal, ∆ij ≤ 0 for all
variables for maximization
problem.
and ∆ij ≥ 0 for minimization
problem.
14. If optimal, stop. If not go to
step 9 to prepare a new table
for improved solution
How to Interpret a Solution
Obtained by Simplex Method
No artificial variable present in the
basis
It is a feasible solution

It is a feasible solution and the ∆ij

values of all non-basic variables are
≤ 0 for a max problem (or ≥ 0 for a
min problem)
The solution is optimal

It is an optimal solution and the ∆ij

values of all non-basic variables are
< 0 for a max problem (or > 0 for a
min problem)
The solution is optimal and unique
How to Interpret a Solution
Obtained by Simplex Method
It is an optimal solution and the ∆ij
value of one or more non-basic
variables is equal to zero
The solution is not unique: the
problem has multiple optimal
solutions

It is final in terms of the ∆ij values

and has an artificial variable in the
basis
It indicates infeasibility

It is non-optimal and the elements of

the key column are all zero/negative
The problem has unbounded
solution
Conditions for using
Simplex Method

1. Non-negative bi values
Multiply a constraint on both sides
by -1 if it involves a negative bi
value

2. Non-negative variables
Replace every unrestricted
variable by difference of two non-
negative variables
Conditions for using
Simplex Method (…continued)
Maximize Z = 8x1 + 5x2 +12x3
Subject to 2x1 + 5x2 + 4x3 ≤ 44
3x1 – 7x2 – 6x3 ≥ –10
7x1 + 2x2 +4x3 = 54
x1, x2 ≥ 0 x3: unrestricted in
sign
Should change as follows:
(i) Let x3 = x4 – x5, where x4, x5 ≥ 0
(ii) 3x1 – 7x2 – 6x3 ≥ –10 be replaced as
– 3x1 + 7x2 + 6x3 ≤ 10
Revised LPP:
Maximize Z = 8x1 + 5x2 +12x4 – 12x5
Subject to 2x1 + 5x2 + 4x4 – 4x5 ≤ 44
– 3x1 + 7x2 + 6x4 – 6x5 ≤ 10
7x1 + 2x2 + 4x4 – 4x5 = 54
Simplex Method for a Max
Problem (all constraints of ≤ type)

1. Standardise the problem

Introduce slack variables
2. Obtain initial solution (with slack
variables)
3. Test if solution is optimal
To be optimal, ∆ij ≤ 0 for all
variables
4. If optimal, stop and exit; else go to
step 5
5. Obtain a revised solution (refer
next slide) and go back to step 3
 Obtain a revised solution
(steps)

1. Select a variable to enter to

improve the solution.
2. Select a variable to leave the
solution.
3. Perform row operations to
complete the new solution.
4. Repeat above steps until
optimality is achieved
An Example
Example 3.2 data
Max Z = 5x1 + 10x2 + 8x3 Contribution
St 3x1 + 10x2 + 2x3 ≤ 60 Fabrication Hrs
4x1 + 4x2 + 4x3 ≤ 72 Finishing Hrs
2x1 + 4x2 + 4x3 ≤ 100 Packaging Hrs
x1, x2, x3 ≥ 0
Conditions for application of simplex
method are both satisfied here
We need 3 slack variables to convert
the inequalities in to equations
The problem becomes:
Max Z = 5x1 + 10x2 + 8x3 + 0S1 + 0S2 + 0S3
St 3x1 + 10x2 + 2x3 + S1 = 60
4x1 + 4x2 + 4x3 + S2 = 72
2x1 + 4x2 + 4x3 + S3 = 100
x1, x2, x3, S1, S2, S3 ≥ 0
 Simplex Solution

Simplex Tableau 1
Basis x1 x2 x3 S1 S2 S3 bi bi/aij
S1 0 3 5* 2 1 0 0 60 12
S2 0 4 4 4 0 1 0 72 18
S3 0 2 4 5 0 0 1 100 25
Cj 5 10 8 0 0 0

Sol 0 0 0 60 72 100 Z=0

Δj 5 10 8 0 0 0

Key row
Key column
Key element
Includes variables that
yield identity matrix
Simplex Solution
To derive values in the next tableau,
Divide each element of key row by
key element: 3/5, 5/5, 2/5, 1/5 etc.
For other rows (for example row 2): 4–
4 × 3/5 = 8/5
4–4×1=0
4 – 4 × 2/5 = 12/5
0 – 4 × 1/5 = -4/5 etc.

Simplex Tableau 2
Basis x1 x2 x3 S1 S2 S3 bi bi/aij
x2 10 3/5 1 2/5 1/5 0 0 12 30
S2 0 8/5 0 12/5 -4/5 1 0 24 10
S3 0 -2/5 0 17/5 -4/5 0 1 52 260/17

Cj 5 10 8 0 0 0
Sol 0 12 0 0 24 52 120

Δj -1 0 4 -2 0 0
Simplex Solution
Simplex Tableau 3: Optimal Solution
Basis x1 x2 x3 S1 S2 S3 bi
x2 10 1/3 1 0 1/3 -1/6 0 8
x3 8 2/3 0 1 -1/3 5/12 0 10
S3 0 -8/3 0 0 1/3 -17/12 1 18
Cj 5 10 8 0 0 0
Sol 0 8 10 0 0 18 160
Δj -11/3 0 4 -2/3 -5/3 0

Solution optimal as all Δj ≤ 0

Optimal Product mix: x1 = 0, x2 = 8 and x3 = 10
Maximum contribution = Rs 160
Capacity utilization: Fabrication and Finishing –
Full; Packaging – 18 hours unutilized
No production of x1 since every unit of it produced
would result in a loss of Rs 11/3
Production of a unit of x1 will result in losing 1/3
unit of x2 and 2/3 unit of x3 together with a release
of 8/3 hours of Packaging time
Solution to LPPs when some/all
Constraints are not ≤ type: Big M

1. Standardise the problem

Introduce surplus and artificial variables
for all “≥” constraints
Introduce artificial variables for all “=“
constraints
In the objective function assign co-
efficients to each of the artificial
variables [For max problems: assign –M
and for min problems: assign M]
2. Obtain initial solution (with
slack/artificial variables)
3. Test if solution is optimal (to be optimal,
∆ij ≥ 0 for all variables)
4. If optimal, stop and exit; else go to step
5
5. If not, obtain a revised solution and go
back to step 3
Artificial Variables

Needed to be used to obtain initial

solution
Introduced where a constraint is of “ ≥ ”
or “ = ” type
May also be required in maximisation
problems
Expected to leave the basis one-by-one
in successive simplex iterations
Solution infeasible as long as one or
more artificial variables present in the
basis
Not expected to be present in the basis
of the final solution
In case artificial variable present in basis
of final solution, there is infeasibility
Solution to LPPs when some/all
Constraints are not
≤ type: 2-Phase

Phase I
1. Standardise the problem
For each artificial variable, assign
co-efficients in the objective
function
For max problem: assign –1
For min problem: assign 1
For every other variable, assign co-
efficient of zero

2. Solve by Simplex Method. If the

objective function value for
optimal solution is zero, move to
Phase II
Solution to LPPs when some/all
Constraints are not
≤ type: 2-Phase

Phase II

1. Begin with Simplex Tableau of

Phase I final solution, eliminate all
entries for artificial variables and
replace the zero co-efficients of
decision variables by original co-
efficient values

2. Solve the modified problem by

Simplex Method
Degeneracy

A solution in which a basic variable has

solution value equal to zero is
degenerate solution
The basic variable which has solution
value of zero is called degenerate
variable
Whenever there is a tie in the
replacement ratios (bi/aij) to be
selected, the next solution will be a
degenerate solution
A degenerate solution may or may not
be optimal
Revision of a non-optimal solution leads
to no improvement (in terms of the Z-
value) if the degenerate variable is the
outgoing variable
Degeneracy: An Example
Max Z = 28x1 + 30x2
Stt 6x1 + 3x2 ≤ 18
3x1 + x2 ≤ 8
4x1 + 5x2 ≤ 30
x 1 , x2 ≥ 0
With slack variables S1,S2 and S3, solution follows:
Tie
Simplex Tableau 1
Basis x1 x2 S1 S2 S3 bi bi/aij
S1 0 6 3 1 0 0 18 6
S2 0 3 1 0 1 0 8 8
S3 0 4 5 0 0 1 30 6
Cj 28 30 0 0 0

Sol 0 0 18 8 30
Δj 28 30 0 0 0

Key column Next solution would be degenerate

Degeneracy: An Example
(…continued)
Simplex Tableau 2: Non-optimal Solution
Basis x1 x2 S1 S2 S3 bi bi/aij
S1 0 18/5 0 1 0 -3/5 0 0
S2 0 11/5 0 0 1 -1/5 2 10/11

X2 30 4/5 1 0 0 1/5 6 15/2

Cj 28 30 0 0 0

Sol 0 6 0 2 0 180
Δj 4 0 0 0 -6
Degenerate outgoing variable
Simplex Tableau 3: Optimal Solution
Basis x1 x2 S1 S2 S3 bi
x1 28 1 0 5/18 0 -1/6 0
S2 0 0 0 -11/18 1 1/6 2
x2 30 0 1 -2/9 0 1/3 6
Cj 28 30 0 0 0
Sol 0 6 0 2 180
Δj 0 0 -10/9 0 -16/3
Degeneracy: An Example
(…continued)

A tie in the minimum replacement

ratios in Tableau 1 results in the solution
in next tableau to be degenerate (even
if the outgoing variable was chosen to
be S1 instead of S3)
Since all values in the key column are
positive, the least ratio to be considered
is 0 and the outgoing variable (S1) is
degenerate
As a result, there is no change in the
objective function value: it remains at
180
The solution in Tableau 3 is also
degenerate
While the solution in Tableau 2 is non-
optimal, the solution in Tableau 3 is
optimal
Multiple Choice Questions

Mark the wrong statement:

1. An LPP with n variables and m
constraints gives nCm basic solutions.

2. A basic solution with all non-

negative variables is called basic
feasible solution.

3. For any LPP, there is a unique

extreme point of the feasible region
corresponding to every basic
solution.

4. The basic feasible solution that

maximises or minimises, as the case
may be, is called optimal solution.
Multiple Choice Questions

Mark the correct alternative.

A feasible solution is the one which

1. satisfies all constraints of the

problem.

2. is necessarily an optimal solution.

3. makes use of all available resources.

4. yields more than one way to achieve

the objective.
Multiple Choice Questions

Which of the following statements

is not true about application of
simplex method?
1. The RHS of each constraint should
be greater-than-or-equal-to zero.

2. All decision variables of the problem

should be non-negative.

3. All constraints of the given problem

should be either  or  type.

4. All constraints should be converted

into “=” type, with slack/surplus
variables which, like decision
variables, are also non-negative.
Multiple Choice Questions

Choose the incorrect statement:

1. Simplex method is an iterative

process wherein variables are
substituted until optimal solution is
reached.
2. Successive simplex tableaus always
yield better solution in terms of the
objective function.
3. For a minimisation problem, the
optimal solution is reached when all
j  0, with no artificial variable in
the basis.
4. The key column indicates the
incoming variable and the key row
represents outgoing variable.
Multiple Choice Questions

If j = cj – zj is equal to 24 – 7M for
x1; 28 – 7M for x2; 45 – 4M for x3
and 28 – 2M in respect of x4 in a
minimisation problem, then the
entering variable would be:

1. x1

2. x2

3. x3

4. x4
Multiple Choice Questions

Mark the wrong statement:

1. First Key element can never be

negative.

2. Key element cannot be zero.

3. Key element has to be positive.

4. Key element can be negative, zero or

positive.
Multiple Choice Questions

The bi values and the elements in

key column are (12, 0, 18, 6)
and (-2, 8, 1, 3) respectively.
Which of the rows will be selected
as the key row?

1. First

2. Second

3. Third

4. Fourth
Multiple Choice Questions

Which of these is not true?

1. All basic variables in an LPP have j =
0.

2. A slack variable cannot be there in

the basis of optimal solution.

3. If a problem has an optimal solution,

the artificial variables, if any,
introduced must be driven out of
the basis one-by-one.

4. An outgoing variable in a simplex

tableau cannot re-enter the basis in
follow-up iterations.
Multiple Choice Questions

Which of the following statements

is not true about artificial
variables?
1. They are introduced when initial
solution to a problem cannot be
obtained for want of identity sub-
matrix in the simplex tableau.
2. Each of such variables has to be
assigned a very large negative co-
efficient in the objective function
when it is of the maximisation type.
3. They help to obtain an initial feasible
solution to the problem.
4. They bear no tangible relationship
with the decision problem.
Multiple Choice Questions

Mark the wrong statement:

1. If a non-basic variable in the optimal

solution to a problem has j = 0, it
indicates multiple optimal solutions.
2. If an artificial variable is found in the
basis of the final solution to an LPP,
it implies feasibility.
3. A constraint with  sign does not
require artificial variable to be
introduced.
4. A slack variable is used to convert ‘’
type and a surplus variable is used
to convert ‘ ‘ type of constraint into
equality.
Multiple Choice Questions

Mark the wrong statement:

1. If there are no non-negative
replacement ratios in a simplex
tableau, then unboundness is
indicated.
2. In a tableau, the key column
elements are –5, 0, 0, 7 while the
corresponding bi values are 20, 6, 8
and 0. This indicates unbounded
solution.
3. A tie in the minimum replacement
ratio implies that the next solution
would be degenerate.
4. It is possible for the initial solution
to an LP to be degenerate.
Multiple Choice Questions

Which of these is not correct?

1. The solution to a maximisation LPP
is unique if j values for all non-
basic variables are less than zero.
2. If infeasibility is present, it is
detected in phase I of the two-phase
method.
3. In two-phase method, the artificial
variables are each assigned a co-
efficient of 1 in case of minimisation,
and –1 in case of maximisation
problems.
4. If the given problem has an optimal
solution, the artificial variables are
all removed one by one in phase I of
the two-phase method.
Multiple Choice Questions

If there is no non-negative
replacement ratio in a solution
which is sought to be improved,
then the solution is indicated to be

1. infeasible

2. unbounded

3. degenerate

4. unique optimal
Multiple Choice Questions

Which of the following is not

correct?
1. As and when a degenerate
variable is outgoing, no change
will take place in the objective
function value.
2. Degeneracy may be a temporary
phenomenon.
3. It is possible for the repetition of
same tableaus in the course of
successive iterations when
degeneracy is encountered.
4. A degenerate solution cannot be
optimal.
Multiple Choice Questions

Degeneracy in LPP (1) renders the

solution infeasible, (2) leads to
multiple optimal solutions, (3)
increases computations without
affecting the solution as long as
the outgoing variable happens to
be degenerate. Which of these
statements is/are correct?

1. 1, 2 and 3
2. 1 and 3
3. 2 and 3
4. 3 only