Register to reply 
Simplex method  algebraic vs tabular form 
Share this thread: 
#1
Mar812, 12:44 PM

P: 13

1. The problem statement, all variables and given/known data
I donīt know when to use the algebraic form and when the tabular form. Or does it not matter? 1. The problem statement, all variables and given/known data 2. Relevant equations 3. The attempt at a solution 


#2
Mar812, 02:43 PM

Sci Advisor
HW Helper
Thanks
P: 5,203

It does not matter very much. If all you want is to understand the simplex method and, perhaps, solve a handful of small problems by hand, the algebraic method is good enough and does not require memorization of any special rules. If you intend to solve many larger examples by hand, the tabular method would be worth knowing. Chvatal's book "Linear Programming", Freeman (1983) discusses this issue right from the start. Of course, if you are trying to read a published paper which uses tableaux, you would need to understand them. RGV 


#3
Mar812, 05:40 PM

P: 13

1) are you sure itīs easier to use the algebraic form? I feel like the tabular is easier as you donīt have to do the minimum ratio test when doing the tabular form.
2) do you get the same solution from both tests? tabular and algebraic? 


#4
Mar812, 08:32 PM

Sci Advisor
HW Helper
Thanks
P: 5,203

Simplex method  algebraic vs tabular form
1) I never said anything about one form or another being "easier": those are your words, not mine. 2) The algebraic and tabular forms use *exactly* the same computations throughout, so of course arrive at the same solutions. They certainly *both* use the minimum ratio test. Basically, the only difference is in how the relations are written: in the tabular form we would write the equations with all variables on the left: 2x1 + 3 x2 + x3 = 5 x1 + x2 + + x4 = 6 or, in shorthand form as 2 3 1 0  5 1 1 0 1  6 In the algebraic form we would essentially write the basic vars on the left and the nonbasics on the right: x3 = 5  2x1  3x2 x4 = 6  x1  x2 Aside from that there is no distinction. RGV 


#5
Mar912, 11:52 AM

P: 13

Thank you very much for your help!
Iīm now learning the big M method and learning about the radiation therapy problem where the ≤ isnīt always that way but itīs also ≥. See picture I was wondering if the big M method was the only way to solve it when it looks like this or could i solve it by using the tabular form? And if I use the tabular form, would I also put x5 +x6 in the bottom line where it looks like this: ≥ ? 


#6
Mar912, 02:02 PM

Sci Advisor
HW Helper
Thanks
P: 5,203

(I) max x1 + x2 + x3 st 2*x1 + 4*x2 + x3 <= 8 2*x1 + x2 + 2*x3 >= 8 2*x1 + 3*x2 + 4*x3 >= 30 x1,x2,x3 >= 0 (II) Same as (I), except change 30 on RHS of third constraint to 34. Question: is (I) a feasible problem? One way is to solve a Phase I problem: min a2 + a3 <Phase I objective. st 2*x1 + 4*x2 + x3 + s1 = 8 2*x1 + x2 + 2*x3 s2 + a2 = 8 2*x1 + 3*x2 + 4*x3  s3 + a3 = 30 x1,x2,x3,s1,s2,s3,a2,a3,>=0. Here, s1 is a slack variable, s2 and s3 are surplus variables and a2, a3 are artificial variables. If the optimal phase I objective is > 0 that means that it is impossible to have both artificial variables = 0, so it is impossible to satisfy all of the original constraints; that is, the original problem is infeasible. However, if the optimal Phase I objective = 0, it is possible to have all artificial vars = 0, so the original problem is feasible; furthermore, the output solution to Phase I is a basic feasible solution to the original problem, which can the be used to start Phase II (the optimization phase). Phase I just forgets about the original objective until it has been determined whether or not the problem is even feasible; after all, if it is infeasible, the objective does not matter. The Phase I problem for (II) is similar, except it has 34 on the right of the 3rd equation. If we solve both problems, we find: (I) is feasible, but (II) is infeasible. Neither statement is "obvious" when you first look at these problems. The bigM method tries to combine Phases I and II in a single problem. Realworld, commercialscale LP codes do not actually use either of these methods; some of them start with infeasible solutions (having one or more negative vars which are supposed to be >= 0) and use modified simplex steps to try to reduce the amount of infeasiblilty. But, those are details best left to more advanced treatments. RGV 


#7
Mar1212, 12:57 PM

P: 13

Thanks so much



Register to reply 
Related Discussions  
When exactly does the tabular method for integration by parts fail?  Calculus  4  
Simplex method stuff  Calculus & Beyond Homework  12  
Simplex method  Calculus & Beyond Homework  0  
Stupid Tabular Method for Integration by parts  Calculus & Beyond Homework  3  
Revised Simplex Method  Calculus & Beyond Homework  0 