Consider a standard form problem, under the usual assumption that the rows of $\textbf{A}$ are linearly independent. Let $\epsilon$ be a scalar and define $$\textbf{b}(\epsilon)=\textbf{b}+\begin{bmatrix} \epsilon \\ \epsilon^{2} \\ \vdots \\ \epsilon^{m} \end{bmatrix}$$ For every $\epsilon>0$, we define the $\epsilon$-perturbed problem to the linear programming obtained by replacing $\textbf{b}$ with $\textbf{b}(\epsilon)$.

(a) Given a basis matrix $\textbf{B}$, show that the corresponding basic solution $x_B(\epsilon)$ in the $\epsilon$-perturbed problem is equal to $$\textbf{B}^{-1}[\textbf{b}|\textbf{I}]\begin{bmatrix} 1 \\ \epsilon \\ \vdots \\ \epsilon^{m} \end{bmatrix}$$

(b) Show that there exists some $\epsilon^*>0$ such that all basic solutions to the $\epsilon$-perturbed problem are nondegenerate, for $0<\epsilon<\epsilon^*$.

This is a question (3.15) from 'Introduction to Linear Optimization' by Dimitris Bertsimas. I am practicing all the problems in this textbook but I'm having hard time even understanding this question and solving it. Could anyone please help me how to approach to this problem or how to solve it? Thank you.


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.