LPP-Simplex Method – Big-M method – Unique and Unbounded Cases

Example 4 (Minimization Problem)

Unique and Optimum solution
Refer – OR by J K Sharma Page 123 Ex 4.9

• ABC Printing Company is facing a tight financial squeeze and is attempting to cut costs
wherever possible. At present it has only one printing contact and, luckily, the book is selling
well in both the hardcover and the paperback editions. It has just received a request to print
more copies of this book in either the hardcover or the paperback form. The printing cost for
the hardcover books is Rs. 600 per 100 books while that for paperback is only Rs. 500 per
100.

• Although the company is attempting to economize, it does not wish to lay off any employee.
Therefore, it feels obliged to run its two printing presses – I and II, at least 80 and 60 hours
per week, respectively. Press I can produce 100 hardcover books in 2 hours or 100
paperback books in 1 hour. Press II can produce 100 hardcover books in 1 hour or 100
paperbacks books in 2 hours. Determine how many books of each type should be printed in
order to minimize costs. (Use Big-M Method)

• Ans. X = 100/3 batches of hardcover books and y = 40/3 batches of paperback books at a
total minimum cost, Z = Rs.80, 000/3 (Unique and Optimum solution)

Solution:

Formulation of the LPP

Let x and y be the books (100 nos.) of each type to be printed

The given information is written in tabular form as follows:

Particulars Hardcover Book Paperback Book printing press

(x) (y) runs at least for
given hrs. per
week
Press I 2 hrs 1 hrs 80 hrs
Press II 1 hrs 2 hrs 60 hrs
Cost per 100 Rs. 600 Rs. 500
book
The formulated LPP is given as follows

Minimize Z = 600 x + 500 y

Subject to

2x + y ≥ 80 (Press I )

x + 2y ≥ 60 (Press II)

x, y ≥ 0

Solve it further using simplex method (Big-M method/Penalty Method))

Step 1: RHS of the constraints should be positive, in our case they are positive so we can proceed

Step 2: Write down the standard form of LPP

Minimize Z = 600 x + 500 y + 0S1 + 0S2 + MA1 + MA2

2x + y - S1 + A1 = 80 S1 – Surplus variable, A1=Artificial variable (help the non-basic solution to

be basic and a big penalty is associated with it in the objective function so
that it helps the artificial variable to drag out of the solution

X + 2y - S2 + A2 = 60

X, y, S1, S2, A1, A2 ≥ 0

Where

S1 and S2 are surplus variables

A1 and A2 are artificial variables which are introduced to make our solution non-negative and the
coefficient in the objective function is M, which called as a penalty with a very high value associated
with it so that it helps in dragging out the artificial variable out of the solution.

Step 3: Get IBFS, put values of x and y = 0, S1 = 0 and S2 = 0

A1 = 80

A2 = 60

Z = 140M

Step 4: Construct initial simplex table

Cj 600 500 0 0 M M Ө
Basis x y S1 S2 A1 A2 bj Min Ratio
A1 M 2 1 -1 0 1 0 80
A2 M 1 2 0 -1 0 1 60
Zj 3M 3M -M -M M M Z = 140M
Net Evaluation Δj=cj- Zj 600-3M 500-3M M M 0 0
Row
y- IV A2-OV, skip this column in further calculations

Here M is a very big quantity (1000)

600-3*1000 = -2400

500-3*1000 = -2500

Step 5: Perform optimality test

Calculate zjs = ƩCBX

Z1 = 0*2 + 0*4 = 0

Calculate the net evaluation row Δj = cj-Zj

For a minimization problem

a) If any of Δj≥0 then the solution is non-optimum, move to step 6 for the improvement
b) If all Δj<0 then we have reached the optimum condition hence stop iterating and write
down the optimum solution
 In our case since two Δj<0 hence the solution is non-optimum, move to step 6 for the
improvement in the solution.

Step 6: Improvement in the solution

a) Identify the most negative Δj, the corresponding variable heading the row is called as
incoming variable (IV)
b) Calculate minimum positive ratio column denoted by Ө, and choose minimum positive ratio
as outgoing variable
c) Convert key element unity (1) and other elements of the key column zero

Now Convert the key element to unity (1) and other elements of the key column zero (0) using
row transformation

x y S1 S2 A1 A2 bj
2 1 -1 0 1 0 80
1 2 0 -1 0 1 60
R2 - > R2/2

x y S1 S2 A1 A2 bj
2 1 -1 0 1 0 80
½ 1 0 -1/2 0 ½ 30
R1 - > R1 – R2

x y S1 S2 A1 A2 bj
3/2 0 -1 ½ 1 -1/2 50
½ 1 0 -1/2 0 ½ 30
Step 7: Construct Second Simplex Table (A2 was outgoing, it is skipped in this table)

Cj 600 500 0 0 M Ө
CSV CB x y S1 S2 A1 bj Min Ratio
A1 M 3/2 0 -1 ½ 1 50 50/ (3/2) =
100/3=33.33
y 500 ½ 1 0 -1/2 0 30 30/(1/2) = 60
Zj (3/2) M + 250 500 -M M/2 - 250 M Z = 50 M +
15000
Net Δj=cj- Zj 600-250-3/2M = 0 M 250-M/2 0
Evaluati 350-3/2M
on Row
M = 1000 350 – 3/2(1000) = 350-1500 = -1150 250-1000/2 = 250-500 = 250

Cj 600 500 0 0 M Ө
CSV CB x y S1 S2 A1 bj Min Ratio
A1 M 3/2 0 -1 ½ 1 50 100/3 = 33.33
y 500 ½ 1 0 -1/2 0 30 60
Zj 250+3M/2 500 -M -250 + M/2 M Z = 50M+15000
Δj 350-3M/2 0 M 250-M/2 0

Since one Δj < 0, given solution is non-optimum, improve it further by going to step 6 again

Step 8: Improvement in the solution

 d) Identify the most negative Δj, the corresponding variable heading the row is called as
incoming variable (IV)
e) Calculate minimum positive ratio column denoted by Ө, and choose minimum positive ratio
as outgoing variable

Now Convert the key element to unity (1) and other elements of the key column zero (0) using row
transformation

x y S1 S2 A1 bj
3/2 0 -1 ½ 1 50
½ 1 0 -1/2 0 30
To make key element unity the row transformation is R1-> (2 /3)*R1

x y S1 S2 A1 bj
1 0 -2/3 1/3 2/3 100/3
½ 1 0 -1/2 0 30
To make other element if the key column zero the row transformation is R2 - > R2 – (1/2)*R1

x y S1 S2 A1 bj
1 0 -2/3 1/3 2/3 100/3
0 1 1/3 -2/3 -1/3 40/3
Third Simplex table (A1 was outgoing var. skip it in this table)

Cj 600 500 0 0
CSV CB x y S1 S2 bj
x 600 1 0 -2/3 1/3 100/3
y 500 0 1 1/3 -2/3 40/3
Zj 600 500 -700/3 -400/3 Z = 80000/3
Δj 0 0 700/3 400/3 Δj ≥ 0, opt sol.
Since all Δj ≥ 0 we have reached an optimum solution, unique solution

X, y – basic variables non-basic – S1 and S2

Multiple Opt condition – if in Δj row, at least one of the values corresponding to S1 and S2 is zero
then the solution is multiple optimum , else if both are positive then the solution is unique.

Ans.: Optimum product mix is given as follows:

Hardcover books = 100/3 (in 100 books)

Paperback books = 40/3 (in 100 books)

Minimum cost to print is Rs. 80000/3

There is no surplus hour use of press I and II as S1 and S2 = 0

This indicates that Press I and II they utilized for 80 and 60 hrs respectively

Special Cases

Unique

Multiple

Unbounded
Infeasible

LPP-Simplex Method – Big-M method Unbounded case

Example 10 Unbounded Solution using Simplex Method

Refer OR by J K Sharma, Ex4.15, p137

Show that there is an unbounded solution to the following LP problem:

Maximize Z = 3x1 + 5x2 Max Z = 3x1 + 5x2 + 0S1 + 0S2 +0S3 – MA1

Subject to constraints x1 - 2x2 ≤ 6 x1 – 2x2 + S1 = 6

x1 ≤ 10 x1 + S2 = 10

x2 ≥ 1 x2 -S3 + A1 = 1

x1, x2 ≥ 0

Solution:

Step 1: RHS +ve

Step 2: Standard form of LPP

Maximize Z = 3x1 + 5x2 +0S1+ 0S2 + 0S3 – MA1

x1 - 2x2 +S1 = 6 ≤ add S1 slack variable

x1 + S2 = 10

x2 -S3 + A1 = 1 ≥ subtract Surplus -S , Add artificial +A

x1, x2, S1, S2, S3, A1 ≥ 0

Here S1 and S2 are slack variables (whatever unutilized capacity is there will be stored in S1 for
1st constraint and in S2 for the second)

S3 is the surplus variable

A1 is the artificial variable

Note: Since the objective function is maximization, we have taken -M as the coefficient of A1 in
the objective function.

Step 3: Get IBFS solution

Put x1 = 0, x2 = 0, S3 = 0

S1 = 6

S2 = 10

A1 = 1

Z = -M
 Step 4: Construct Initial Simplex Table

Cj 3 5 0 0 0 -M Ө
CSV CB X1 X2 S1 S2 S3 A1 bj Min
Ratio
S1 0 1 -2 1 0 0 0 6 -ve
S2 0 1 0 0 1 0 0 10 ∞
A1 -M 0 1* 0 0 -1 1 1 1
Zj 0 -M 0 0 M -M Z = -M, Z = -1000
Net evaluation row Δj = cj-Zj 3 5+M 0 0 -M 0 Since Δ>0, non-
opt

Step 5: Perform Optimality Test

Calculate Zj = ƩCbXj

Net evaluation row Δj = cj-Zj

For a maximization problem

1. If all Δj ≤ 0 then the optimum condition is reached, and we will stop iterating and write
down the solution
2. If any Δj > 0 then the solution is non-optimum, so move to step 6 for the improvement in
the solution

Step 6: Improvement in the solution

a) Choose the most positive Δj and corresponding variable heading the column would be
incoming variable (IV)
b) Calculate minimum ratio column (Ө) as the ratio of RHS and key column elements and
choose the minimum positive ratio as outgoing variable
c) Now convert the key element unity and rest elements of the key column zero using row
transformation

X1 X2 S1 S2 S3 A1 bj
1 -2 1 0 0 0 6
1 0 0 1 0 0 10
0 1 0 0 -1 1 1
R1-> R1+2R3

X1 X2 S1 S2 S3 A1 bj
1 0 1 0 -2 2 8
1 0 0 1 0 0 10
0 1 0 0 -1 1 1
 Step 7: Construct Second Simplex Table (Since A1 was chosen as outgoing variable it will be
omitted in further simplex tables)

Cj 3 5 0 0 0 Ө
CSV CB X1 X2 S1 S2 S3 bj Min Ratio
S1 0 1 0 1 0 -2 8 8/ (-2) = -4
S2 0 1 0 0 1 0 10 10/0 = ∞
X2 5 0 1 0 0 -1 1 1/ (-1) = -1
Zj 0 5 0 0 -5 Z =5
Net evaluation row Δj = 3 0 0 0 5 Δj>0, Non-opt
cj-Zj
Step 8: Perform optimality test

Calculate Zj and Δj and check the values of Δj row

For a maximization problem

1. If all Δj ≤ 0 then the optimum condition is reached, and we will stop iterating and write
down the solution
2. If any Δj > 0 then the solution is non-optimum, so move to step 6 for the improvement in
the solution

Step 9: Improvement in the solution

a) Choose the most positive Δj and corresponding variable heading the column would be
incoming variable (IV)
b) Calculate minimum ratio column (Ө) as the ratio of RHS and key column elements and
choose the minimum positive ratio as outgoing variable
c) Since in the minimum column ratio there is no positive ratio, the values are either negative
or infinity, we cannot choose any variable as outgoing hence the given solution cannot be
solved further.
In such a case, while choosing outgoing variable, the Ө column consists of negative or
infinity values the solution to such an LPP is called UNBOUNDED.
• Ans.: Since all minimum ratios values are either negative or infinity, s3 value can be
increased indefinitely without violating any of the constraints. Further, since s3 is associated
with x2 in the third constraint, x2 will also be increased infinitely because it can be expressed
as x2 =1+s3 – A1. hence, the solution to the given problem is unbounded.