PSLP

4rd SEMESTER
BS-202

Department of Applied Science, BVCOE New Delhi Subject: PSLP

1
 UNIT-4

Department of Applied Science, BVCOE New Delhi Subject: PSLP

2
 Simplex Method

• Simplex: a linear-programming algorithm that can solve

problems having more than two decision variables.
• The simplex technique involves generating a series of
solutions in tabular form, called tableaus. By inspecting
the bottom row of each tableau, one can immediately
tell if it represents the optimal solution. Each tableau
corresponds to a corner point of the feasible solution
space. The first tableau corresponds to the origin.
Subsequent tableaus are developed by shifting to an
adjacent corner point in the direction that yields the
highest (smallest) rate of profit (cost). This process
continues as long as a positive (negative) rate of profit
(cost) exists.
Simplex Algorithm

The key solution concepts

• Solution Concept 1: the simplex method focuses on CPF solutions.
• Solution concept 2: the simplex method is an iterative algorithm (a
systematic solution procedure that keeps repeating a fixed series of
steps, called, an iteration, until a desired result has been obtained)
with the following structure:
 Simplex algorithm
Initialization: setup to start iterations, including finding an initial CPF
solution

Optimality test: is the current CPF solution optimal?

if no if yes stop

Iteration: Perform an iteration to find a better CFP solution

Simplex algorithm

•Solution concept 3: whenever possible, the initialization

of the simplex method chooses the origin point (all
decision variables equal zero) to be the initial CPF
solution.

•Solution concept 4: given a CPF solution, it is much

quicker computationally to gather information about its
adjacent CPF solutions than about other CPF solutions.
Therefore, each time the simplex method performs an
iteration to move from the current CPF solution to a
better one, it always chooses a CPF solution that is
adjacent to the current one.
 Simplex algorithm
• Solution concept 5: After the current CPF solution is identified, the simplex
method examines each of the edges of the feasible region that emanate from
this CPF solution. Each of these edges leads to an adjacent CPF solution at the
other end, but the simplex method doesn’t even take the time to solve for the
adjacent CPF solution. Instead it simply identifies the rate of improvement in Z
that would be obtained by moving along the edge. And then chooses to move
along the one with largest positive rate of improvement.
 Simplex algorithm
•Solution concept 6: A positive rate of
improvement in Z implies that the adjacent
CPF solution is better than the current one,
whereas a negative rate of improvement in Z
implies that the adjacent CPF solution is
worse. Therefore, the optimality test consists
simply of checking whether any of the edges
give a positive rate of improvement in Z. if
none do, then the current CPF solution is
optimal.
The simplex method in tabular form
• Steps:
1. Initialization:
a. transform all the constraints to equality by
introducing slack, surplus, and artificial variables as
follows:

Constraint type Variable to be added

≥ + slack (s)

≤ - Surplus (s) + artificial (A)

= + Artificial (A)
Simplex method in tabular form
b. Construct the initial simplex tableau

Basic X1 …
Xn S1 …... Sn A1 …. An RHS
variable
S b1
Coefficient of the constraints

A bm
Z Objective function coefficient Z
In different signs value
 Simplex method
2. Test for optimality:
in tabular form
Case 1: Maximization problem
the current BF solution is optimal if every coefficient in the objective
function row is nonnegative
Case 2: Minimization problem
the current BF solution is optimal if every coefficient in the objective
function row is nonpositive
 Simplex
3. Iteration
method in tabular form
Step 1: determine the entering basic variable by selecting the variable
(automatically a nonbasic variable) with the most negative value (in case of
maximization) or with the most positive (in case of minimization) in the
last row (Z-row). Put a box around the column below this variable, and call
it the “pivot column”
Simplex method in tabular form

•Step 2: Determine the leaving basic variable by

applying the minimum ratio test as following:
1. Pick out each coefficient in the pivot column that is
strictly positive (>0)
2. Divide each of these coefficients into the right hand
side entry for the same row
3. Identify the row that has the smallest of these ratios
4. The basic variable for that row is the leaving variable,
so replace that variable by the entering variable in the
basic variable column of the next simplex tableau. Put a
box around this row and call it the “pivot row”
 Simplex method in tabular form
• Step 3: Solve for the new BF solution by using
elementary row operations (multiply or divide a row by a
nonzero constant; add or subtract a multiple of one row
to another row) to construct a new simplex tableau, and
then return to the optimality test. The specific
elementary row operations are:
1. Divide the pivot row by the “pivot number” (the number
in the intersection of the pivot row and pivot column)
2. For each other row that has a negative coefficient in the
pivot column, add to this row the product of the
absolute value of this coefficient and the new pivot row.
3. For each other row that has a positive coefficient in the
pivot column, subtract from this row the product of the
absolute value of this coefficient and the new pivot row.
 Simplex method
•Example (All constraints are ≤)
Solve the following problem using the simplex method
•Maximize
Z = 3X1+ 5X2
Subject to
X1 ≤ 4
2 X2 ≤ 12
3X1 +2X2 ≤ 18
X1 , X2 ≥ 0
 Simplex method
• Solution
• Initialization
1. Standard form
Maximize Z,
Subject to Sometimes it is called
Z - 3X1- 5X2 =0 the augmented form of
the problem because
X1 + S1 = 4 the original form has
2 X2 + S2 = 12 been augmented by
3X1 +2X2 + S3 = 18 some supplementary
X1 , X2, S1, S2, S3 ≥ 0 variables needed to
apply the simplex
method
Definitions

• A basic solution is an augmented corner point solution.

• A basic solution has the following properties:
1. Each variable is designated as either a nonbasic variable or a
basic variable.
2. The number of basic variables equals the number of functional
constraints. Therefore, the number of nonbasic variables
equals the total number of variables minus the number of
functional constraints.
3. The nonbasic variables are set equal to zero.
4. The values of the basic variables are obtained as simultaneous
solution of the system of equations (functional constraints in
augmented form). The set of basic variables are called “basis”
5. If the basic variables satisfy the nonnegativity constraints, the
basic solution is a Basic Feasible (BF) solution.
Initial tableau
Entering
2. Initial tableau variable

RHS Min
Cj 3 5 0 0 0 ratio

B. Cb X1 X2 S1 S2 S3
V
S1 0 1 0 1 0 0 4 4/0

S2 0 2 0 1 0 12 12/2
0

S3 3 2 0 0 1 18 18/2
0
Z -3 -5 0 0 0 0
Leaving Pivot row
Pivot column
variable Pivot
Z=∑CbXi-Cj
number
 Simplex
Notes:
tableau
• The basic feasible solution at the initial tableau is (0, 0, 4, 12, 18) where:
X1 = 0, X2 = 0, S1 = 4, S2 = 12, S3 = 18, and Z = 0
Where S1, S2, and S3 are basic variables
X1 and X2 are nonbasic variables
• The solution at the initial tableau is associated to the origin point at which
all the decision variables are zero.
Optimality test

• By investigating the last row of the initial tableau, we find that there
are some negative numbers. Therefore, the current solution is not
optimal
Iteration

• Step 1: Determine the entering variable by selecting the variable with

the most negative in the last row.
• From the initial tableau, in the last row (Z row), the coefficient of X1 is
-3 and the coefficient of X2 is -5; therefore, the most negative is -5.
consequently, X2 is the entering variable.
• X2 is surrounded by a box and it is called the pivot column
Iteration
•Step 2: Determining the leaving variable by using the
minimum ratio test as following:

Basic Entering RHS Ratio

variable variable X2
(1) (2) (2)÷(1)
S1 0 4 None
S2 2 12 6
Leaving Smallest ratio
S3 2 18 9
Iteration
• Step 3: solving for the new BF solution by using the
eliminatory row operations as following:
1. New pivot row = old pivot row ÷ pivot number

Basic X1 X2 S1 S2 S3 RHS
variable
S1
X2 0 1 0 1/2 0 6
S3
Z
Note that X2 becomes in the basic
variables list instead of S2
 iteration
2. For the other row apply this rule:
New row = old row – the coefficient of this row in the pivot column (new pivot row).
For S1

1 0 1 0 0 4
-
0 (0 1 0 1/2 0 6)
1 0 1 0 0 4
For S3

3 2 0 0 1 18
-
2 (0 1 0 1/2 0 6)
3 0 0 -1 1 6
for Z
-3 -5 0 0 0 0
-
-5(0
-3
1
0
0
0
1/2
5/2
0
0
6)
30
Substitute this
values in the table
Iteration
This solution is not optimal, since there is a negative numbers in the last row

B. Cj 3 5 0 0 0
RHS
V Cb X1 X2 S1 S2 S3
S1 0 1 0 1 0 0 4
X2 5 0 1 0 1/2 0 6
S3 0 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30

The smallest ratio

The most negative
is 6/3 =2; therefore,
value; therefore, X1
S3 is the leaving
is the entering
variable
variable
Iteration
•Apply the same rules we will obtain this solution:
B. Cj 3 5 0 0 0
RHS
V Cb
X1 X2 S1 S2 S3
S1 0
0 0 1 1/3 -1/3 2
X2 5
0 1 0 1/2 0 6
X1 3 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
This solution is optimal; since there is no negative solution in
the last row: basic variables are X1 = 2, X2 = 6 and S1 = 2; the
nonbasic variables are S2 = S3 = 0
Z = 36
Special cases of linear programming

• Infeasible solution
• Multiple solution (infinitely many solution)
• Unbounded solution
• Degenerated solution
 Notes on the Simplex tableau
1. In any Simplex tableau, the intersection of any basic variable with itself is always
one and the rest of the column is zeroes.
2. In any simplex tableau, the objective function row (Z row) is always in terms of the
nonbasic variables. This means that under any basic variable (in any tableau) there
is a zero in the Z row. For the non basic there is no condition ( it can take any value
in this row).
3. If there is a zero under one or more nonbasic variables in the last tableau (optimal
solution tableau), then there is a multiple optimal solution.
4. When determining the leaving variable of any tableau, if there is no positive ratio
(all the entries in the pivot column are negative and zeroes), then the solution is
unbounded.
5. If there is a tie (more than one variables have the same most negative or positive)
in determining the entering variable, choose any variable to be the entering one.
6. If there is a tie in determining the leaving variable, choose any one to be the
leaving variable. In this case a zero will appear in RHS column; therefore, a “cycle”
will occur, this means that the value of the objective function will be the same for
several iterations.
7. A Solution that has a basic variable with zero value is called a “degenerate
solution”.
8. If there is no Artificial variables in the problem, there is no room for “infeasible
solution”
 Simplex method incase of Artificial variables
“BigtheMfollowing
• Solve method” linear programming problem by using the simplex
method:
• Min Z =2 X1 + 3 X2
S.t.
½ X1 + ¼ X2 ≤ 4
X1 + 3X2 ≥ 20
X1 + X2 = 10
X1 , X 2 ≥ 0
 Big M
• Solution
method
Step 1: standard form
Min Z,
s.t.
Z – 2 X1 – 3 X2 - M A1 -M A2 =0
½ X 1 + ¼ X2 + S1 =4
X1 + 3X2 - S 2 + A1 = 20
X 1 + X2 + A2 = 10
X1, X2 ,S1, S2, A1, A2 ≥ 0
Where: M is a very large number
• Big M method
Notes
M, a very large number, is used to ensure that the values of A1, A2, …, and An will be
zero in the final (optimal) tableau as follows:
1. If the objective function is Minimization, then A1, A2, …, and An must be added to
the RHS of the objective function multiplied by a very large number (M).
Example: if the objective function is Min Z = X1+2X2, then the obj. function should be
Min Z = X1 + X2+ MA1 + MA2+ …+ MAn
OR
Z – X1 - X2- MA1 - MA2- …- MAn = 0

2. If the objective function is Maximization, then A1, A2, …, and An must be

subtracted from the RHS of the objective function multiplied by a very large
number (M).
Example: if the objective function is Max Z = X1+2X2, then the obj. function should be
Max Z = X1 + X2- MA1 - MA2- …- MAn
OR
Z - X1 - X2+ MA1 + MA2+ …+ MAn = 0

N.B.: When the Z is transformed to a zero equation, the signs are changed
Big M method
•Step 2: Initial tableau

B.V Cj 2 3 0 0 M M RHS
Cb X1 X2 S1 S2 A1 A2

S1 0
½ ¼ 1 0 0 0 4
A1 M
1 3 0 -1 1 0 20
A2 M
1 1 0 0 0 1 10
Z 2M-2 4M-3 0 -M 0 0 0

Note that one of the simplex rules is violated, which is the basic variables A1,
and A2 have a non zero value in the z row; therefore, this violation must be
corrected before proceeding in the simplex algorithm as follows. (4M-3 will
enter, most positive)
 Big M method
• To correct this violation before starting the simplex algorithm, the elementary
row operations are used as follows:
New (Z row) = old (z row) ± M (A1 row) ± M (A2 row)
In our case, it will be positive since M is negative in the Z row,
as following:
Old (Z row): -2 -3 0 0 -M -M 0
M (A1 row): M 3M 0 -M M o 20M
M (A2 row): M M 0 0 0 M 10M
New (Z row):2M-2 4M-3 0 -M 0 0 30M

It becomes zero
Big M method
•The initial tableau will be:
B.v Cb X1 X2 S1 S2 A1 A2 RHS
2 3 0 0 M M
S1 0
1/2 1/4 1 0 0 0 4
A1 M
1 3 0 -1 1 0 20
A2 M
1 1 0 0 0 1 10
Z 2M-2 4M-3 0 -M 0 0 30M

• Since there is a positive value in the last row, this solution is not optimal
• The entering variable is X2 (it has the most positive value in the last row)
• The leaving variable is A1 (it has the smallest ratio)
Big M method
•First iteration

Bv Cb X1 X2 S1 S2 A1 A2 RHS
Cj
2 3 0 0 M M
S1 5/12 0 1 1/12 -1/12 0 7/3
0
X2 1/3 1 0 -1/3 1/3 0 20/3
3
A2 2/3 0 0 1/3 -1/3 1 10/3
M

Z 2/3M-1 0 0 1/3M-1 1-4/3M 0 20+10/3M

• Since there is a positive value in the last row, this solution is not optimal
• The entering variable is X1 (it has the most positive value in the last row)
• The leaving variable is A2 (it has the smallest ratio)
Big M method
•Second iteration
Bv Cj 2 3 0 0 M M
RHS
Cb X1 X2 S1 S2 A1 A2
S1 0 0 1 -1/8 1/8 -5/8 1/4
0
X2 0 1 0 -1/2 1/2 -1/2 5
3
X1 1 0 0 1/2 -1/2 3/2 5
2

Z 0 0 0 -1/2 ½-M 3/2-M 25

This solution is optimal, since there is no positive value in the last row. The
optimal solution is: (here,we are looking for positive Z value.)
X1 = 5, X2 = 5, S1 = ¼
A1 = A2 = 0 and Z = 25
Note for the Big M method

• In the final tableau, if one or more artificial variables (A1, A2, …) still
basic and has a nonzero value, then the problem has an infeasible
solution.
• All other notes are still valid in the Big M method.
 Special cases
• In the final tableau, if one or more artificial variables (A , A , …) still basic
1 2
and has a nonzero value, then the problem has an infeasible solution
• If there is a zero (zj-cj) under one or more nonbasic variables in the last
tableau (optimal solution tableau), then there is a multiple optimal solution.
• When determining the leaving variable of any tableau, if there is no positive
ratio (all the entries in the pivot column are negative and zeroes), then the
solution is unbounded.