Week 3

Question 1

How to deal with a LP-problem that doesn’t have an equal amount of slack variables and restrictions?

Answer 1

We add artificial variable r1, r2, r3, … for every restriction without a slack variable (thus also restrictions with a surplus variable).

Question 2

What is the big-M method, and how do you use it?

Answer 2

To enforce an artificial variable equals zero we change the function Z to include -Mr1 - Mr2 - … (if max) with M is large. Then we need remove M from r1, r2,… row/column (the one that goes from top to bottom) from the simplex tableau. Then it can be solved with the simplex method.

Question 3

When is an element unbounded?

Answer 3

If in the simplex method at some point there’s no positive number in the column, then it becomes infinitely large/small.

Question 4

When is a problem infeasible using the big-M method?

Answer 4

If it returns a very large negative value.

Question 5

What is degeneration (when using the simplex method)?

Answer 5

If several rows attain a minimum using the minimum ratio test. We can make one non-basic but the rest remains basic. Such a solution is called a degenerate, it might happen that this causes cycling, and thus no optimization can be found.

Question 6

How do you detect that there are multiple solutions (when using the simplex method)?

Answer 6

If one or more variables have a reduced objective coefficient equal to 0 (in the optimal tableau).

Question 7

What is the dual problem?

Answer 7

We can rewrite the problem to get a maximum of a problem. I don’t yet really understand how, but will figure it out.