- #1

skaterboy1

- 13

- 0

## Homework Statement

I don´t know when to use the algebraic form and when the tabular form.

Or does it not matter?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

In summary: Question: is (II) a feasible problem? The answer is no, because the third constraint is not satisfied. Here is an example:(I) max x1 + x2 + x3st2*x1 + 4*x2 + x3 <= 82*x1 + x2 + 2*x3 >= 82*x1 + 3*x2 + 4*x3 >= 30x1,x2,x3 >= 0(II) Same as (I), except change 30 on RHS of third constraint to 34.Question: is (II) a feasible problem? The answer is no, because the third

- #1

skaterboy1

- 13

- 0

I don´t know when to use the algebraic form and when the tabular form.

Or does it not matter?

Physics news on Phys.org

- New quantum error correction method uses 'many-hypercube codes' while exhibiting beautiful geometry
- Researchers advance new class of quantum critical metal that could advance electronic devices
- Researchers make sound waves travel in one direction only, with implications for electromagnetic wave technology

- #2

Ray Vickson

Science Advisor

Homework Helper

Dearly Missed

- 10,704

- 1,723

skaterboy1 said:## Homework Statement

I don´t know when to use the algebraic form and when the tabular form.

Or does it not matter?

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

skaterboy1

- 13

- 0

2) do you get the same solution from both tests? tabular and algebraic?

- #4

Ray Vickson

Science Advisor

Homework Helper

Dearly Missed

- 10,704

- 1,723

skaterboy1 said:

2) do you get the same solution from both tests? tabular and algebraic?

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 non-basics on the right:

x3 = 5 - 2x1 - 3x2

x4 = 6 - x1 - x2

Aside from that there is no distinction.

RGV

- #5

skaterboy1

- 13

- 0

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: ≥ ?

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

Ray Vickson

Science Advisor

Homework Helper

Dearly Missed

- 10,704

- 1,723

skaterboy1 said: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 pictureI 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: ≥ ?

In introductory textbooks there are two methods discussed: (1) the 2-phase method; and (2) the big-M method. The two-phase method deals with the following two questions: (a) is the problem feasible at all, and if it is, what is a basic feasible solution; then (b) if feasible, go to optimality. (a) is Phase I and (b) [if needed] is Phase II. Here are two little related examples:

(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 big-M method tries to combine Phases I and II in a single problem.

Real-world, commercial-scale 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

Last edited:

- #7

skaterboy1

- 13

- 0

Thanks so much

The simplex method is a mathematical algorithm used to solve linear programming problems. In algebraic form, the problem is represented by a set of equations and inequalities, while in tabular form it is represented by a table. The calculations and steps involved are the same in both forms, but the tabular form is often more organized and easier to understand.

You can use either form in the simplex method, but it is generally recommended to use the tabular form as it is more user-friendly and easier to follow. However, if you are comfortable with working with equations and inequalities, you may use the algebraic form.

To convert a problem from algebraic form to tabular form, you need to first identify the decision variables, constraints, and objective function. Then, you can create a table with columns for the decision variables, slack variables, and the objective function. Populate the table with the coefficients from the equations and inequalities, and then follow the steps of the simplex method as you would with the algebraic form.

Yes, you can switch between the two forms as long as you maintain the same steps and calculations. However, it is recommended to stick to one form throughout the process to avoid confusion and errors.

Yes, there are several advantages of using the tabular form in the simplex method. As mentioned before, it is more organized and easier to understand, which can help in avoiding errors. It also allows for easier identification of the basic feasible solution and the optimal solution. Additionally, it allows for a more efficient method of finding the next pivot element, leading to a faster solution.

- Replies
- 1

- Views
- 1K

- Replies
- 3

- Views
- 3K

- Replies
- 4

- Views
- 1K

- Replies
- 2

- Views
- 2K

- Replies
- 4

- Views
- 1K

- Replies
- 3

- Views
- 11K

- Replies
- 14

- Views
- 2K

- Replies
- 2

- Views
- 1K

- Replies
- 7

- Views
- 2K

- Replies
- 7

- Views
- 862

Share: