The theory of the simplex method

Question 1

Elaborate on how we can find allowable range for a coefficient of the objective function whose variable is nonbasic in the optimal solution

Answer 1

A couple of things is very important here.

First of all, recall the definition of allowable range for such a variable: The range for which the optimal solutions remains the same in terms of values for the variables (obviously not in terms of final z-value).

Second of all, since this is an objective function coefficient, we know which part of the simplex tableau it will reside in. To be specific, we know that the final tableau values for coefficients are given as c{b}B^(-1)A-c, which we abbreviate as z-star - c.

we know that in order to remain at the optimal solution, we cannot move anywhere. This means that we must keep the current objective function coefficients positive in the tableau. Meaning, z-star - c >= 0 for all of its values.

We know that z-star is equal to y-star times A, and we of course know that y-star if the values of the slack-variable coefficeints in row 0 in final tableau.

When we look at a specific coefficeint in the original objective function, say “j”, we must account for this in the expressions.

z-star{j} - c{j} >= 0
which means:

z-star{j} >= c{j}

cj is just a coefficent of the current objective function.

z-star{j} is equal to y-star A{j}

So, the result is that the coefficent must be smaller than or equal to y-star multiplied with A{j}.