Modifying primal constraint in a LP problem

Question

Suppose we have a primal-dual pair in standard form, Add a scalar multiple of one primal constraint to another primal constraint. Does this change the dual solution?

Try

Supose we have primal $ \max cx $ subjeect to $Ax = b $, $x \geq 0$ and the ${\bf dual}$ then is given by $\min yb $ subject to $yA \geq c $ and $y \; free$. Consider rows $i$ and $j$ of $A$ :

$$ a^i x_k = b_i \; \; \; \; and \; \; \; \; \; a^j x_k = b_j $$

$k=1,...,n$. Let's perform what we are asked: Let $\alpha$ be scalar so that

$$ (a^i + \alpha a^j) x_k = b_i+\alpha b_j $$

So the ith dual variable coefficient changes. But, is it a multiple of $\alpha$ or not?

Answer 1

Let $E$ be the corresponding elementary matrix corresponding to adding $\alpha$ times the $j$-th row to the $i$-th row.

Let $w$ be the original dual variable, then we have

$$y=E^{-T}w$$

from the working here.

$E^T$ be the corresponding elementary matrix corresponding to adding $\alpha$ times the $i$-th row to the $j$-th row.

$E^{-T}$ be the corresponding elementary matrix corresponding to adding $-\alpha$ times the $i$-th row to the $j$-th row.

Hence the $j$-th entry of the dual would change, $$y_j = w_j-\alpha w_i.$$