« Substitution and Output effects |
Main
| Equation of a learning curve »
Example of using simplex algorithm
Let's consider a simple example of solving linear programming problem by using the simplex method.
Let A company manufactures small and large garden benches in two departments, the Machining Department and the Polishing Department. Small bench requires 2 hours in the Machining Department and 3 hours in the Polishing Department. It takes 4 hours to machine large bench and 3 hours to polish. The available time for processing the two models is 100 hours a week in the Machining Department and 90 hours a week in the Polishing Department. The contribution margin expected is $5 for small bench and $7 for large bench. Let's find the optimal mix of products A company should produce to maximize total contribution margin.
Let X is quantity of small benches and Y is quantity of large benches. Let's find such X, Y that:
5X + 7Y - > max - objective function;
2X + 4Y < = 100 - constraints
3X + 3Y < = 90
X , Y > = 0
Let S1, S2 >= 0 are slack variables and then constraint transforms from inequality expressions to equality form. And linear programming problem may be restated as follows:
5X + 7Y +0S1 + 0S2 - > max
2X + 4Y +1S1 + 0S2 = 100
3X + 3Y +0S1 + 1S2 = 90,
X , Y, S1, S2 > = 0
Now we can construct the initial simplex tableau:
1. The Cj row consists of the coefficients from the objective function. 1 and 2 rows consist of the coefficients from the constraint equalities. The values 100 and 90 in the right-hand side (RHS) column come from the right-hand side of the constraint equations. Those variables that form an identity matrix are basic variables. S1 and S2 are the basic variables in this case.
2. The CB column consists of payoff coefficients of the basic variables in profit-maximization problem (objective function), i.e. 0 for S1 (row 1) and 0 for S2 (row 2).
3. The first element of the Zj row (in X column) is the sum of the products of multiplying each element in the CB column by each element in the X column. 0 (row 1, column CB) * 2 (row 1,column X) + 0 (row 2, column CB) * 3 (row 2,column X) . The subsequent elements of the Zj row (columns Y, S1, S2, RHS) are obtained in a similar way.
4. Row 4 (Cj - Zj) is obtained by subtracting each element in the Zj row from each element in the Cj (top) row.
5. Find in row (Cj-Zj) LARGEST STRICTLY POSITIVE element. Corresponding column is leading column. From row 4 we choose element 7 and the
leading column is Y (rows 1, 2) in our case.
6. Find in the leading column MINIMAL POSITIVE element from the elements are obtained from the formula RHS/leading column. This element gives us leading row. Intersection the leading row and the leading column give us leading element. In our case we choose between 100/4=25 and 90/3=30 and the leading row is row 1. Hence the leading element is 4.
7. The rows 5 is obtained by dividing leading row by leading element and row 6 is obtained by subtracting 3*(row 5) from row 2. Hence we have received an identity leading column. Hence the new basic variables are Y and S2. Go to step 2.
Repeat iterations until there are no strictly positive elements in the (Cj-Zj) row (if the optimal solution exists).
If the optimal solution exist then the element in row Zj (row 11) column RHS is objective function value in the optimal solution point. And (20, 10) from rows 9, 10 column RHS is optimal mix of products.
Hence, maximum profit margin is 190 and A company should produce 10 small benches and 20 large benches.
We have considered the solution of standard maximization problem with non-negative right-hand side of the constraints using the simplex method. The more general case of linear programming (LP) problem with the orbitrary right-hand side of the constraints we consider in the example #2.
Posted by mazoo at February 24, 2005 1:34 PM
Trackback Pings
TrackBack URL for this entry:
http://mazoo.net/mt/mt-tb.cgi/170
Simplex Algorithm. Example #2 Dec 28, 2005
We considered Maximization linear programming problem in this post.
When we want to solve Minimization linear programming problem by simplex method we need to transform objective function.
ax + by - > min transform to
-ax - by - > max
Similarly, when we meet the constrains in the non-standard form:
cx + dy >= A, we can modify it into standard form
-cx - dy <= -A
When we convert minimizing problem into maximizing problem and non-standard constraints into standard we can solve the linear programming problem by the simplex algorithm shown above.
Posted by: Mazoo at March 2, 2005 10:22 AM
can u plz email me the complete solution at hammad.tco@gmail.com
thankz
Hammad
Posted by: Hammad at April 7, 2006 10:31 AM
Hammad, check your email.
Posted by: Mazoo at April 8, 2006 4:40 PM
Thanks, a very useful tip which made my life easier in solving LP by simplex method
Posted by: Saulat at April 10, 2006 2:47 PM
1.can u pls email me the complete solution at the above mentioned email about the above mentioned example.
2. can u pls email me the complete solution at the above mentioned email about transportation problems.
Posted by: lakshmi at July 31, 2006 8:46 PM
aewdsa saf wefrasf adsf sdaf
Posted by: Jessica at January 28, 2008 4:05 PM
aewdsa saf wefrasf adsf sdaf
Posted by: Jessica at January 28, 2008 4:05 PM
Post a comment
