Hi guys, I'm working on a homework problem.

It can be viewed at this link:

http://www.math.ubc.ca/~steph/340/2010_340HWK.pdf

In particular it is, question 11.

For those who don't want to click on the link:

----

Given an LP problem with decision variables x1,...,xn and slack variables s1,...,sk we

know from performing the simplex method that if the last line of a feasible dictionary

z = c + summation(i = 1 to n){cixi} + summation(j = 1 to k){djsj}

has all ci <= 0; i = 1,...,n and dj <= 0; j = 1,...,k then z = c is the optimal value.

Question: If not all ci <= 0; i = 1,...,n and dj <= 0; j = 1,...,k it is sometimes possible for z = c to be the optimal value. Under exactly what conditions on the dictionary does this happen? Explain your answer.

----

So my thought process runs as so:

1) The question states there is some ci or dj >= 0.

2) max(c + summation(i = 1 to n){cixi} + summation(j = 1 to k){djsj}) = c implies cixi + djsj = 0 (for all the cis and djs >= 0, all the other terms optimize to 0 because they would be negative so the variables will optimize to 0)

3) cixi + djsj = 0 AND ci > 0 AND dj > 0 implies xi = 0 and sj = 0

4) the only ways to force xi = 0 and sj = 0 is that the constraints are formulated such that simplex (or inspection) will force them to be 0.

The example came up with is:

Objective function:

z = 10 + x1

Constraints:

x1 <= 0

Non-negativity Constraints:

x1 >= 0

So my three concerns are :

1) My explanation doesn't feel mathematically rigorous enough.

2) The question seems to imply that you will have a dictionary with a positive coefficient AFTER the application of Simplex. However, my understanding of Simplex is that the method will not stop until all coefficients in objective function are 0 or negative. Is this right? So any dictionary that can have this result where z = c and there is a positive coefficient, will always result in a infinitely cycling simplex due to degeneracy

3) The correctness of my guess: Constraints that force variables to be 0 can only come from degenracy if the coefficient for the variable is greater than 0 in the final dictionary of Simplex.

Any hints that would be helpful would be greatly appreciated!