1
$\begingroup$

Given LPP: $\min c^tx $ subject to $Ax\leq b$, $x\geq 0$, where $rank$ $A_{m\times n}=m$, the SLPP is $\min [c^t$ $ 0]$$\begin{bmatrix} x \\y \end{bmatrix}$ subject to $[A$ $I_m]$$\begin{bmatrix} x \\y \end{bmatrix}=b$, where $b,x\geq 0, y\geq 0$. Show that $v$ is a BFS of $S$ if and only if $\begin{bmatrix} v \\b-Av \end{bmatrix}$ is a BFS of $S'$, where $S$ and $S'$ are the feasible sets for the LPP and the SLPP.

I have been able to show that BFS of $S$ implies BFS of $S'$, but I am having problem proving the converse. If we consider $w=$$\begin{bmatrix} v \\b-Av \end{bmatrix}_{(n+m)\times 1}$ to be a BFS of $S'$, then writing $w=$$\begin{bmatrix} w_B \\w_C \end{bmatrix}_{(n+m) \times 1}$, where $w_B=B^{-1}b$ and $w_C=0$, we observe that $Cw_C=0$, where $C$ has $n(\geq m)$ columns. Here $[A|I_m]_{m \times (m+n)}$=$[B|C]_{m \times (m+n)}$ and $B$ is the basis matrix of $w_B$. For $v$ to be a BFS of $S$, I think that $b-Av$ should be a component of $w_C$. But I can not come to see how, if at all I am right in being apprehensive here?

$\endgroup$
1
$\begingroup$

$\require{extpfeil} \Newextarrow{\xlf}{5,10}{0x2194}$ $$ \cssId{lpS}{(S)} \quad \begin{array}{cc} Ax &\le b \\ x &\ge 0 \end{array} \xlf[\text{add slack variable } y]{} \begin{array}{cc} Ax + Iy &= b \\ x,y &\ge 0 \end{array} \quad \cssId{lpSp}{(S')} $$

Let's see a simpler version first: if $(S')$ has a solution $(x,y)$, you can simply discard $y$ so that $x$ satisfy $(S)$.

Apply this with $x = v$ and $y = b - Av$ to finish the problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.