Exercise 3.33

Question

Consider a polyhedron in standard form, and let $x$, $y$ be two different basic feasible solutions. If we are allowed to move from any basic feasible solution to an adjacent one in a single step, show that we can go from $x$ to $y$ in a finite number of steps.

Subham Saha · Accepted Answer

Since $y$ is a basic feasible solution, $y$ is also a vertex. Therefore, there exists a $c$ such that $c^{T} y < c^{T} z$ for all $z$ in the polyhedron $P$. We denote this unique cost as $c_{y}$.

Next, we define a linear programming problem as following:

\begin{align}
\min & c_{y}^{T} z \
	ext{subject to, } Az &= b \
z &\geq b.
\end{align}

By definition, $y$ is the unique minimizer of the linear programming problem. Therefore, if we start at $x$ and use simplex method with any anticycling rule, we will reach to $y$ in finite steps. Since, the simplex method moves along the adjacent basic feasible solutions, we are done.

Exercise 3.33

Answers

Comments

Exercise 3.33

Answers

Comments

Add answer