I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem:

Consider the simplex method applied to a standard form problem and assume that the rows of the matrix $A$ are linearly independent . For each of the statements that follow, give either a proof or a counterexample. Take $n\geq m$, where $A$ is $m*n$ and $b$ is $m*1$ matrix.

(a) An iteration of the simplex method may move the feasible solution by a positive distance while leaving the cost unchanged.

(b) If there is a nondegenerate optimal basis , then there exists a unique optimal basis.

(c) If $x$ is an optimal solution, no more than $m$ of its components can be positive.

I tried this question, and was able to solve some of them. But, I'm not sure if my solutions are correct. It'd be really helpful if someone could tell if I solved these correctly and tell the solutions/hints for the unsolved ones.

My try:

I considered a tableau while solving all of these problems.

a) False. Let $c$ and $\bar{c}$ be the initial and final costs. When we update the tableau, we'll apply row transformation to go from $c$ to $\bar{c}$. But since $c=\bar{c}$, for the cost to remain the same after an iteration, the basic variable that is exiting the basis has to be zero. Let $k$ be the index of the variable entering the basis and $B(l)$ be that of leaving the basis. When we move from $x_{B(l)}$ to $x_k$, whatever we multiply by, $x_{B(l)} (=x_k)$ will remain the same ($0$). So, we are still at the same point.

b) I was unable to understand it clearly. What does "basis" mean? The basis matrix $B$ or the vector of basic variables $x_B$? I've no idea on how to proceed in any of those two way either.

c) This is true since $x$ being an optimal solution is a bfs.

Please note that I don't even need full solutions, even hints will do. Thanks!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.