Suppose we have in standard form an LP: $\max cx$ subject to $Ax = b$ and $x \geq 0$. Lets' write its dual as well
\begin{align*}
(P) \max cx &&&&&& (D) \min yb \\
Ax = b &&&&&& A^T y \geq c \\
x \geq 0 &&&&&& y \; \text{free} \\
\end{align*}
suppose we add a scalar multiple of one primal column to another primal column. What happens now to primal and dual solutions?
Attempt
consider the kth column of primal, say $a^{(k)} = (a_{1k}, a_{2k},…, a_{mk} )^T $. Suppose we add $\lambda a^{(k)}$ to another column say $a^{(l)}$. So, the new modified lth column of primal is
$$ a^{(l)'} = (a_{1l}+ \lambda a_{1k},…,a_{ml} + \lambda a_{mk}) ^T$$
Now, suppose we have solutions to the primal and dual, say $x^* = (x_1^*,…,x_n^*)^T$ and $y^*=(y_1^*,…,y_m^*)^T$. we want $x^*$ to remain feasible, notice that once we multiply the new $A$ with $x^*$, the rth component of $Ax^*$ is
$$ a_{r1}x_1 + … + a_{rk}x_k + … + (\lambda a_{rk} + a_{rl})x_l + … + a_{rn}x_n $$
We see that this change in $A$ only affects the lth component of $x^*$. how can we modify it to remain feasible? I dont seem to pinpoint it. I feel that only thing that works is to set $a_{rk}=0$? but then $x_k$ would vanish too. Any help?
Now, as for the dual. Notice that for dual $a^{(l)'}$ is a row. So in this case, the vector $A^T y $ gets affected only on the lth row in which we have
$$( a_{l1} + \lambda a_{k1}) y_1 + … + ( a_{lk} + \lambda a_{kk}) y_k + … + (a_{lm} + \lambda a_{km}) y_m $$
In this case how can we remain feasible?
Im doing this problem correctly?
Best Answer
By revised simplex, you have $x_B = B^{-1}b$, $x_N=0$. Let us assume that the optimal basis stays the same. A change to the nonbasic columns of $A$ does not affect the optimum. A modification to a basic column affects the solution via $x_B^{new} = (B+uv^T)^{-1}b$, with $u=\lambda e_{l'}$ and $v=a_r$, where $e_i$ is the $i$-th unit vector and $l'$ is such that the $l'$-th column of $B$ coincides with the $l$-th column of $A$. By Sherman-Morrison: $$x_B^{new} = B^{-1}b - \frac{B^{-1}uv^TB^{-1}}{1+u^T B^{-1}v}b = x_B^{old}- \frac{B^{-1}uv^T}{1+u^T B^{-1}v}x_B^{old}.$$ Note that $B^{-1}v$ simplifies to a unit vector if $v$ is in the basis.