0
$\begingroup$

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!

$\endgroup$

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.