0
$\begingroup$

Suppose we have primal and its dual in standard form, that is

\begin{align*} (P) \max z = cx \\ st \; \; Ax = b \\ \; \; \; x \geq 0 \\ \end{align*}

\begin{align*} (D) \min z = by \\ st \; \; yA \geq c \\ \; \; \; y \; \; \; free \\ \end{align*}

Where $A$ is an $m $ by $n$ matrix an $x$ is an n vector and $y$ is an m vector.

Suppose we multiply one of the constraints of the primal by some number $\alpha > 0$. Does this affect the solution of the dual?

Thoughts:

Since a constraint is of the form $a_{ij} \cdot x $, take one of the $i's$, say we multiply

$$ a_{i1}x_1 + a_{i2} x_2 + ... + a_{in} x_n $$

by $\alpha $

Once we set up our tableau, once we divide this row by $\alpha$, then in the LFH, we would have

$$ \frac{ b_i}{\alpha} $$

the ith component of the vector $b$. Doesnt it change the solution in the primal tableau? Since solutions are the same for primal and dual???

$\endgroup$
2
$\begingroup$

Multiplication by a non-zero scalar is equivalent to multiplication of an elementary matrix, $E$.

\begin{align*} (P') \max z = c^Tx \\ st \; \; (EA)x = (Eb) \\ \; \; \; x \geq 0 \\ \end{align*}

The dual is \begin{align*} (D') \min z = (Eb)^Ty \\ st \; \; y^T(EA) \geq c \\ \; \; \; y \; \; \; free \\ \end{align*}

Suppose $w$ is the original dual solution, then $y=E^{-T}w.$

For the operation of multiplication by a scalar, we have $E^T=E$.

Hence $y=E^{-1}w$. That is if we multiply $\alpha$ to the $i$-th constraint, now for the dual solution, we would divide $w_i$ by $\alpha$ and we can keep the rest to be the same.

$\endgroup$
  • $\begingroup$ Can you help me with this related problem: math.stackexchange.com/questions/2989440/… $\endgroup$ – Mikey Spivak Nov 8 '18 at 15:11
  • $\begingroup$ at first glance, it seems that doing that operation might cause the primal problem to become infeasible. $\endgroup$ – Siong Thye Goh Nov 8 '18 at 15:24
  • $\begingroup$ But isnt it doing the same operations as the previous case but this time to the dual? $\endgroup$ – Mikey Spivak Nov 8 '18 at 18:06
  • $\begingroup$ the duality is in inequality form, multiplying an inequality and adding it to another one might change the feasible set. Also, if you multiply by a negative number, the inequality get flipped. $\endgroup$ – Siong Thye Goh Nov 8 '18 at 18:09
  • $\begingroup$ You are right :/ $\endgroup$ – Mikey Spivak Nov 8 '18 at 18:23

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.