Explore BrainMass
Share

# Optimization

Specify whether the following statements are true or false and justify your answer.

a) Suppose we have an optimal basic feasible solution for an LP in standard form. If we increase the cost of a non-basic variable xn, the current solution will always remain optimal.

b) Suppose we have an optimal basic feasible solution for an LP in standard form. If we decrease the cost of a basic variable xb, the current solution will always remain optimal.

c) Suppose we have an optimal basic feasible solution for an LP in standard form. Further, suppose that this solution is both primal and dual non-degenerate. If we change the b vector, the current solution may remain feasible but become sub-optimal.

d) Consider a basic feasible solution to a linear program and suppose that the step size of the next pivot is 0. Does this mean that the current BFS is necessarily degenerate? Why or why not?

e)Consider a basic feasible solution to a linear program and suppose that it is degenerate. Does this mean that the next pivot will have step size of 0? Why or why not?

f)Consider a basic feasible solution to an LP in standard form. Suppose that two or more non-basic variables have negative reduced cost. Does this mean that the current solution is sub-optimal? Why or why not?

g)Suppose that we pivot in the non-basic variable with the most negative reduced cost and move to a new bfs with an improved objective value. Will this lead to the largest improvement in the objective value? Why or why not?

#### Solution Preview

I would like to suggest you to use the book of "Linear programming and network flows" by Mokhtar bazaraa and...

a and b) I wold like to suggest to imaginate the graphical scheme of a Lp. when you move your obj function with the same slope(parallel with itself ) through the feasible region, the last point or points that you wll leave from the feasible area is(are) optimal solution.
Now, if you change the cost of some variables(basic or non- basic), you may ...

#### Solution Summary

This solution is comprised of a detailed explanation to specify whether the following statements are true or false and justify your answer.

\$2.19