Suppose that we have an LP in the standard form
$$\text{(P) min }c^Tx: Ax=b, x\le 0$$
and it's dual would be
$$\text{(D) max }b^Tx: Ax\le c$$
Let $\overline{x}$ and $\overline{y}$ be the optimal solutions to (P) and (D) respectively.
How do these solutions change if we multiply the constraint $Ax=b$ by a scalar? I think we'd have the following
$$\text{(P$\alpha$) min }c^Tx: \alpha Ax=b, x\le 0$$
and it's dual would be
$$\text{(D$\alpha$) max }b^Tx: \alpha Ax\le c$$
Where $\alpha \in \mathbb{R}-\{0\}$
My initial thoughts are that
1. The optimal value's of (P), (D), (P$\alpha$), and (D$\alpha$) won't change since the feasible region wont' change.
2. The optimal solutions will just be $\overline{x}/\alpha$ and $\overline{y}/\alpha$ for (P$\alpha$) and (D$\alpha$) respectively.
Yet, this seems wrong.
I'm rather new to Linear Programming and duality and would love an explanation of why my intuition is/isn't correct.
Asked
Active
Viewed 172 times
1
1 Answers
2
We would have
$$\text{(P$\alpha$) min }c^Tx: \alpha Ax=\color{blue}\alpha b, x\le 0$$
and it's dual would be
$$\text{(D$\alpha$) max }\color{blue}{\alpha}b^Tx: \alpha Ax\le c$$
Where $\alpha \in \mathbb{R}\setminus \{0\}$
The primal solution would remain the same since the feasible set remains the same. The corresponding dual solution would be $\frac1{\alpha}\bar{y}$.
Siong Thye Goh
- 149,520
- 20
- 88
- 149
-
For (P$\alpha$) why would you multiply b by $\alpha$? Wouldn't that make $\alpha Ax=\alpha b$ equivalent to $Ax=b$? – CandyKing312312 Nov 26 '18 at 12:59
-
That is what the question meant right? Multiplying the constraint $Ax=b$ by a scalar. not just multiplying each row of $A$ by $\alpha$. Yes, they are equivalent. – Siong Thye Goh Nov 26 '18 at 13:05
-
My mistake, I meant $\overline{A}_i=\alpha*A_i$. Where $\overline{A}$ represents the modified primal constraint – CandyKing312312 Nov 26 '18 at 13:07
-
1you probably mean $\alpha \in \mathbb{R}\setminus{0}$ – LinAlg Nov 26 '18 at 17:00