Simplex:
Introduction:
Let us understand the meaning of Simplex Method.
The Simplex method is a method which goes from one BFS or extreme point of the feasible region of an Linear programming problem expressed in tableau form to another BFS, in such a way as to continually increase or decrease the value of the objective function until optimality is reached.The simplex method moves from one extreme point to one of its neighboring extreme point.
In geometry,a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope with n + 1 vertices, of which the simplex is the convex hull. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a pentachoron. A single point may be considered a 0-simplex, and a line segment may be viewed as a 1-simplex.
Definition of a Simplex is given below:
A simplex may be defined as the smallest convex set which contains the given vertices.A regular simplex is a simplex that is also a regular polytope. A regular n-simplex may be constructed from a regular (n − 1)-simplex by connecting a new vertex to all original vertices by the common edge length.
Simplex method Problem 1:
Consider
x1 + x2 - x3 + x4 = 5
2x1 – 3x2 + x3 + x5 = 3
-x1 + 2x2 - x3 + x6 = 1
Solution:
The initial tableau is given by
Tableau 1:
x1 x2 x3 x4 x5 x6 b B1
x4 1 1 -1 1 0 0 5 1 0 0
x5 2 -3 1 0 1 0 3 0 1 0
x6 -1 2 -1 0 0 1 1 0 0 1
The current basic solution is [ 0, 0 , 0, 5, 3, 1]T which is feasible. Suppose we choose a1,1 as our pivot element. Then after one pivot operation, we have
Tableau 2:
x1 x2 x3 x4 x5 x6 b B1
x1 1 1 -1 1 0 0 5 1 0 0
x5 0 -5 3 -2 1 0 -7 2 1 0
x6 0 3 -2 1 0 1 6 -1 0 1
We note that the current basic solution is [ 5, 0, 0, 0, -7, 6]T which is infeasible. Using the new (2, 2) entry as pivot, we have
Tableau 3:
x1 x2 x3 x4 x5 x6 b B1
x1 1 0 -2/5 3/5 1/5 0 18/5 1 0 0
x2 0 1 -3/5 2/5 -1/5 0 7/5 2 -3 0
x6 0 0 -1/5 -1/5 -3/5 1 9/5 -1 2 1
The current basic solution is [ 18/5 , 7/5, 0, 0, 0, 9/5]T and is feasible. Finally, let us eliminate the last slack variable x6 by replacing it by x3.
Tableau 4:
x1 x2 x3 x4 x5 x6 b B1
x1 1 0 0 1 -1 -2 0 1 1 -1
x2 0 1 0 1 -2 -3 -4 2 -3 1
x3 0 0 1 1 -2 -5 -9 -1 2 -1
The current basic solution is [ 0, -4, -9, 0, 0, 0]T which is infeasible and degenerate.
Hope you like the above example of Simplex.Please leave your comments, if you have any doubts.
Introduction:
Let us understand the meaning of Simplex Method.
The Simplex method is a method which goes from one BFS or extreme point of the feasible region of an Linear programming problem expressed in tableau form to another BFS, in such a way as to continually increase or decrease the value of the objective function until optimality is reached.The simplex method moves from one extreme point to one of its neighboring extreme point.
In geometry,a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope with n + 1 vertices, of which the simplex is the convex hull. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a pentachoron. A single point may be considered a 0-simplex, and a line segment may be viewed as a 1-simplex.
Definition of a Simplex is given below:
A simplex may be defined as the smallest convex set which contains the given vertices.A regular simplex is a simplex that is also a regular polytope. A regular n-simplex may be constructed from a regular (n − 1)-simplex by connecting a new vertex to all original vertices by the common edge length.
Simplex method Problem 1:
Consider
x1 + x2 - x3 + x4 = 5
2x1 – 3x2 + x3 + x5 = 3
-x1 + 2x2 - x3 + x6 = 1
Solution:
The initial tableau is given by
Tableau 1:
x1 x2 x3 x4 x5 x6 b B1
x4 1 1 -1 1 0 0 5 1 0 0
x5 2 -3 1 0 1 0 3 0 1 0
x6 -1 2 -1 0 0 1 1 0 0 1
The current basic solution is [ 0, 0 , 0, 5, 3, 1]T which is feasible. Suppose we choose a1,1 as our pivot element. Then after one pivot operation, we have
Tableau 2:
x1 x2 x3 x4 x5 x6 b B1
x1 1 1 -1 1 0 0 5 1 0 0
x5 0 -5 3 -2 1 0 -7 2 1 0
x6 0 3 -2 1 0 1 6 -1 0 1
We note that the current basic solution is [ 5, 0, 0, 0, -7, 6]T which is infeasible. Using the new (2, 2) entry as pivot, we have
Tableau 3:
x1 x2 x3 x4 x5 x6 b B1
x1 1 0 -2/5 3/5 1/5 0 18/5 1 0 0
x2 0 1 -3/5 2/5 -1/5 0 7/5 2 -3 0
x6 0 0 -1/5 -1/5 -3/5 1 9/5 -1 2 1
The current basic solution is [ 18/5 , 7/5, 0, 0, 0, 9/5]T and is feasible. Finally, let us eliminate the last slack variable x6 by replacing it by x3.
Tableau 4:
x1 x2 x3 x4 x5 x6 b B1
x1 1 0 0 1 -1 -2 0 1 1 -1
x2 0 1 0 1 -2 -3 -4 2 -3 1
x3 0 0 1 1 -2 -5 -9 -1 2 -1
The current basic solution is [ 0, -4, -9, 0, 0, 0]T which is infeasible and degenerate.
Hope you like the above example of Simplex.Please leave your comments, if you have any doubts.
No comments:
Post a Comment