# Linear Programming: Constraints

• Feb 21st 2011, 12:18 AM
zigu
Linear Programming: Constraints
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!