LP extensions

Question 1

What are the simplest constraints for LP problems?

Answer 1

Upper and lower bounds for variables.

For instance:

xj >= 6
xj <= 10

Question 2

Should we include all types of constraints on simplex?

Answer 2

we can, but if the constraint is just an upper or lower limit, it is basically just adding a lot of extra work that we can actually solve in some other way.

Question 3

What is the general idea we use to treat upper and lower bounded variables without adding completely new rows/constraints?

Answer 3

We modify the feasibility condition. Before, we only used non negativity as a condition. However, now we want to also make sure that the upper or lower limit is also considered as illegal.

Recall that regular simplex figure out a step length based on whenever a constraint becomes active, and going further makes it invalid.

Question 4

How do we treat a variable that has a lower bound?

Answer 4

Perform subtitution: x’ = x - L

Then, for every place in the problem where x was, we add (x’+L) instead of x.

Question 5

is there a trick to incoirporate uppwer bounded variables?

Answer 5

Not like a simple substitution. We need to modify the solution procedure

Question 6

Elaborate on simplex for upper bounded variables

Answer 6

The difference between regular simplex and simplex for upper bounded variables, is the way we choose the leaving bsaic variable.

Recall that with regular simplex, the leaving basic variable is the one that first hit the spot of 0.
We still want to include this, because it is general feasibility.
However, we should also look for whether the upper bound of any variable is reached before any variable reach value 0.

So, we end up with the leaving basic variable like this:
The first one that occurs, determines all:
1) One of hte current basic vairables reaches its lower bound. This is the same as with regular simplex.

2) The entering basic variable reaches its upper bound. If this happens, this variable immediately becomes the leaving variable, and its value is changed from 0 to the upper bound uj.

3) One of the current basic variables reaches its upper bound. The one that does this become the leaving variable.

This means that in this LP extension, non basic variables can have value 0 like always, or in the case of upper bound, they can have the upper bound.

if a variable reach upper bound, we perform a substitution:

xj-bar = uj - xj

So, step 4 in the search method is changed.

In addition ot the regular check, we must compare it with:
t2 = up

and

t3 =. min j {(uj - xj^(k)) / dj^(k) | dj^(k) > 0}

There is also some bullshit on replacement and substitutions

Question 7

Recall the difference between primal methods and dual methods

Answer 7

Primal methods iterate between feasible solutions.

Dual methods iterate between infeasible solutions.

Question 8

elaborate on dual simplex

Answer 8

Dual simplex start from a point that is dual feasible. This means that the point is either the optimal solution, or it si primal infeasible.

we typically run dual simplex after adding a variable or something like that.

Step 1)
we check the convergence criterion. the poiont x^(k) is optimal if >= 0 for all its values.

Step 2)
Determien the leaving basic variable according to the criterion:

xr^(k) = min j {xj^k | xj^k < 0}

Now we have selected the variable to be leaving basic that is the variable with the smallest (most infeasible) value.

Step 3)
Determine the entering basic variable according to:

|c-bar_p / a-bar_sp| = min j {|c-bar_j / a-bar_sj| a-bar_sj < 0}

This gives that xp becomes the basic entering variable.
if there is no valid entering basic variable, the problem has no feasible solution.

Step 4)
Rewrite the system of equations as before and compute next iteration