20/11/2024, 11:16 Simplex method Multiple optimal solution example

We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn
more Accept

Support us
Select Language
Powered by Translate

Try our new - Enter problem or search problem

Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra

Home > Operation Research calculators > Simplex method example

2. Simplex method example ( Enter your problem )

Other related methods
1. Structure of Linear programming
problem 0. Formulate linear programming
2. Algorithm model
3. Maximization example-1 1. Graphical method
4. Maximization example-2 2. Simplex method (BigM
5. Maximization example-3 method)
6. BigM method Algorithm 3. Two-Phase method
7. Minimization example-1 4. Primal to dual conversion
8. Minimization example-2 5. Dual simplex method
9. Minimization example-3 6. Integer simplex method
10. Degeneracy example-1 (Tie for 7. Branch and Bound method
leaving basic variable) 8. 0-1 Integer programming problem
11. Degeneracy example-2 (Tie first 9. Revised Simplex method
Artificial variable removed)
12. Unrestricted variable example
13. Multiple optimal solution
example
14. Infeasible solution example
15. Unbounded solution example

12. Unrestricted variable example 14. Infeasible solution example

(Previous example) (Next example)

13. Multiple optimal solution example

Multiple optimal solution

In the final simplex table when all c j - z j imply optimal solution (for
maximization all c j - z j ≤ 0 and for minimization all c j - z j ≥ 0)
but if c j - z j = 0 for some non-basic variable column, then this indicates that
there are more than 1 optimal solution of the problem. Thus by entering this
variable into the basis, we may obtain another alternative optimal solution.

Example
Find solution using Simplex(BigM) method
MAX Z = 6x1 + 4x2
subject to
2x1 + 3x2 <= 30
3x1 + 2x2 <= 24
x1 + x2 >= 3
and x1,x2 >= 0

Solution:
Problem is
Max Z = 6 x 1 + 4 x 2
subject to
2 x 1 + 3 x 2 ≤ 30
3 x 1 + 2 x 2 ≤ 24
x1 + x2 ≥ 3
( Enter your problem )
and x 1, x 2 ≥ 0;

The problem is converted to canonical form by adding slack, surplus and

artificial variables as appropiate

1. As the constraint-1 is of type ' ≤ ' we should add slack variable S 1

[Link] 1/5
20/11/2024, 11:16 Simplex method Multiple optimal solution example

2. As the constraint-2 is of type ' ≤ ' we should add slack variable S 2

3. As the constraint-3 is of type ' ≥ ' we should subtract surplus variable S 3

and add artificial variable A 1

After introducing slack,surplus,artificial variables

Max Z = 6 x 1 + 4 x 2 + 0 S 1 + 0 S 2 + 0 S 3 - M A 1
subject to
2 x1 + 3 x2 + S1 = 30
3 x1 + 2 x2 + S2 = 24
x1 + x2 - S3 + A1 = 3
and x 1, x 2, S 1, S 2, S 3, A 1 ≥ 0

Iteration-1 Cj 6 4 0 0 0 -M

MinRatio
CB XB x1 x2 S1 S2 S3 A1 XB
B
x1

30
S1 0 30 2 3 1 0 0 0 = 15
2
24
S2 0 24 3 2 0 1 0 0 =8
3
3
A1 -M 3 (1) 1 0 0 -1 1 =3→
1

Z=0 Zj -M -M 0 0 M -M

Cj - Zj M+6 ↑ M+4 0 0 -M 0

Positive maximum C j - Z j is M + 6 and its column index is 1. So, the entering

variable is x 1.

Minimum ratio is 3 and its row index is 3. So, the leaving basis variable is A 1.

∴ The pivot element is 1.

Entering = x 1, Departing = A 1, Key Element = 1

R 3(new) = R 3(old)

R 1(new) = R 1(old)- 2R 3(new)

R 2(new) = R 2(old)- 3R 3(new)

Iteration-2 Cj 6 4 0 0 0

MinRatio
CB XB x1 x2 S1 S2 S3 XB
B
S3

24
S1 0 24 0 1 1 0 2 = 12
2

15
S2 0 15 0 -1 0 1 (3) =5→
3

x1 6 3 1 1 0 0 -1 --- ( Enter your problem )

Z = 18 Zj 6 6 0 0 -6

Cj - Zj 0 -2 0 0 6 ↑

[Link] 2/5
20/11/2024, 11:16 Simplex method Multiple optimal solution example
Positive maximum C j - Z j is 6 and its column index is 5. So, the entering
variable is S 3.

Minimum ratio is 5 and its row index is 2. So, the leaving basis variable is S 2.

∴ The pivot element is 3.

Entering = S 3, Departing = S 2, Key Element = 3

R 2(new) = R 2(old) ÷ 3

R 1(new) = R 1(old)- 2R 2(new)

R 3(new) = R 3(old)+ R 2(new)

Iteration-3 Cj 6 4 0 0 0

B CB XB x1 x2 S1 S2 S3 MinRatio

5 2
S1 0 14 0 1 - 0
3 3
1 1
S3 0 5 0 - 0 1
3 3

2 1
x1 6 8 1 0 0
3 3

Z = 48 Zj 6 4 0 2 0

Cj - Zj 0 0 0 -2 0

Since all C j - Z j ≤ 0

Hence, optimal solution is arrived with value of variables as :

x 1 = 8, x 2 = 0

Max Z = 48

Here C 2 - Z 2 = 0 and x 2 is not in the basis (i.e. x 2 = 0).

This indicates that there are more than 1 optimal solution of the problem.
Thus by entering x 2 into the basis, we may obtain another alternative
optimal solution.

Iteration-3 Cj 6 4 0 0 0

MinRatio
CB XB x1 x2 S1 S2 S3 XB
B
x2

14

() 5 2 = 8.4 →
S1 0 14 0 1 - 0 5
3 3
3

1 1
S3 0 5 0 - 0 1 ---
3 3

8
2 1 = 12
x1 6 8 1 0 0 2
3 3
3

Z = 48 Zj 6 4 0 2 0 ( Enter your problem )

Cj - Zj 0 0 ↑ 0 -2 0

So, the entering variable is x 2.

Minimum ratio is 8.4 and its row index is 1. So, the leaving basis variable is

[Link] 3/5
20/11/2024, 11:16 Simplex method Multiple optimal solution example
S 1.

5
∴ The pivot element is .
3

5
Entering = x 2, Departing = S 1, Key Element =
3

3
R 1(new) = R 1(old) ×
5

1
R 2(new) = R 2(old)+ R 1(new)
3

2
R 3(new) = R 3(old)- R 1(new)
3

Iteration-4 Cj 6 4 0 0 0

B CB XB x1 x2 S1 S2 S3 MinRatio

42 3 2
x2 4 0 1 - 0
5 5 5

39 1 1
S3 0 0 0 1
5 5 5

12 2 3
x1 6 1 0 - 0
5 5 5

Z = 48 Zj 6 4 0 2 0

Cj - Zj 0 0 0 -2 0

Since all C j - Z j ≤ 0

Hence, optimal solution is arrived with value of variables as :

12 42
x1 = ,x =
5 2 5

Max Z = 48

This material is intended as a summary. Use your textbook for detail

explanation.
Any bug, improvement, feedback then Submit Here

12. Unrestricted variable example 14. Infeasible solution example

(Previous example) (Next example)

Share this solution or page with your friends.

Home What's new College Algebra Games Feedback About us

Copyright © 2024. All rights reserved. Terms, Privacy

( Enter your problem )

.

[Link] 4/5
20/11/2024, 11:16 Simplex method Multiple optimal solution example

( Enter your problem )

[Link] 5/5