LP exentsions

Question 1

elaborate on the simplest types of constraints

Answer 1

Upper and lower bounded variable

Question 2

what do we do with upper and lower bounded variables?

Answer 2

we could treat it like regular constraints, but this is not very good approahc because of how much additional work this adds. The point is that we can extedn regular simplex to account for upper and lower bounds without that much additional work.

Question 3

elaborate on how we deal with lower bounded variables

Answer 3

We simply reformulate the problem before the solution procedure is started. Given the condition that xj >= l_i, we perform a substitution:

x_j^(new) = x_j - l_j

Notice how now, since x_j is bounded at l_j, the new variable has a lower bound of 0, like we want it to.

So, at each place where we had x_j previously, we know enter x_j^(new) + l_j.

Question 4

in one sentence, what is required from upper bounded variables?

Answer 4

We need to change our entire solution procedure: Specifically, change the way we find leaving basic variable.

Question 5

consider the regular simplex. How do we pick leaving basic variable?

Answer 5

We have found some non-basic variable that is our enteirng basic variable. We then look at how increasing this variable affect the basic variables. we know that one of them will be “removed” from basis because of how vertices work and all that. The question is therefore: which variable will we remove.

We pick as leaving basic variable the variable that first reach one of its boundaries. The way this is done is by choosing the variable that become 0 first. whether it is regular decisions variable or slack or surplus doesnt matter. All that matter is that it reach 0 first. When it reach 0, it means that (since it cannot go from infeasible to 0) increasing it further than this will make it infeasible.

So, the question is really, which variable reach 0 first. To figure this out, we consider the current basic solution. We want the “real” effect of increasing the entering basic variable to be that the basic variables should decrease. Therefore, we take the ones in the simplex tableau that has the correct sign, and divide the current value on the slope. This gives us a number of “steps” before it reach 0. Then we pick the basic variable that reach 0 first to be leaving basic variable.

Question 6

When we account for upper bounded variables, how do we select leaving basic variable?

Answer 6

Now there are more tests we need to check.

in addition to the regular one, we need:
If the entering basic variable reach its upper bound first. In such a case, the entering basic variable should immediately become the leaving basic variable, and its value should be changed from 0 to the upper bound uj.

Also, if one of the other current basic variables reaches its upper bound, this basic variable become the leaving basic variabl.

Question 7

In the upper bounded simplex extensions, what values can a non basic variable have?

Answer 7

Either 0 or the upper bound value. Of course, this only applies for upper bounded variables.

Question 8

if a variable xj has an upper bound, reach this upper bound, what do we do?

Answer 8

We perform the substitution: xj^(bar) = uj - xj. The new variable of course becomes a non-basic variable as it has the value 0.

Question 9

Specifically (mathematically), what are the leaving basic variable critereons for the upepr bounded simplex+

Answer 9

The normal one.

t2 = u_p (upper bound for the specific entering variable)

t3 = the basic variable that first reach its upper bound

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

So, whats going on here?
In the third case, we take the upper bound of the basic variable, less its current value, and divide on the search direction component that correspond to it.

then we pick the varible with the smallest case to be the leavign basic variable.

Question 10

After finding the leaving basic variable from the conditions, then what

Answer 10

Depending on what case we found to give the smallest, we do differnet things:

As always, a new point is computed by the regualr search direction function.

In the new basic solution, “xr” which is the leaving basic variable, is replaced by x_p (entering basic variable) except when t2 defines the step length and the set of basic variables is unchanged.

If t2 or t3 defines the step length, the substitution must be carried out. xr^(bar) = ur - xr

Question 11

explain t3 better

Answer 11

t3 is about this: We figure out how much “room” there is between the upepr bound of the variable and the current value that this basic variable has. This room/space/gap is defined as the differnece: uj - xj.
This gap is nice, but its doesnt tell us anything about the step length before it becomes iunfeasible. to do this, we need the specific d-component that is specific to the entering basicvariable. But, since we are now reversing the direction, we take the opposite sign as the regualr step length check.

Question 12

elaborate on what we do in dual methods

Answer 12

We iterate between solutions that are dual feasible AND satisfy the complementarity conditions.

We search until we find a solution that is primal feasible, and once found we reach that point where we have the optimal solution.

Question 13

when is the dual simplkex most powerful

Answer 13

when we have solved an LP problem using regular simplex, and we want to re-solve with some changed data

Question 14

what is the convergence criterion in dual simplex?

Answer 14

If all basic variables are equal to 0 or larger, xb>=0, then we have optimal solution.

Question 15

what is the leaving basic variable criterion for dual simplex?

Answer 15

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

so, we pick the variable (basic variable) whose value is most negative to be the leaving basic variable.

Question 16

how do we determine the entering basic variable in dual simplex?

Answer 16

|cp^(bar) / asp^(bar)| = min j {|cj^(bar) / asj^(bar)| | asj^(bar) < 0}

this gives that xp is the entering basic variable.