2

Suppose we have the problem min $c^Tx$, subject to $Ax = b, x\geq 0$. The dual is then max $b^Ty$, subject to $A^T y \leq c$.

We assume that the linear and dual program are feasible and bounded. Let $y^*$ denote the optimal solution of the dual program. I'm interested in what happens if we multiply the objective function of the linear program with a value $k$ (i.e., the objective function becomes min $(k\cdot c)^Tx$).

The dual then becomes $b^Ty$, subject to $A^T y \leq k \cdot c$. Is the dual solution then simply $k \cdot y^*$? Or is this relation more complicated? .

Ellie
  • 21

1 Answers1

1

Strong Duality requires the optimal objective solutions for both the primal and dual to match. In other words, $(c\cdot k)^Tx^*=b^Ty^*$. When we scale the objective function of the primal problem's objective function by a factor of $k$, the dual problem has to make up for this to achieve a duality gap of zero by allocating $k$ more resources into $y$ to satisfy $A^Ty^*=c\cdot k$. In addition, for the feasible region of the dual model, all $k$ does is expand the bounds of the feasible region by a factor of $k$ for each dual constraint, so all the optimal extreme points are all scaled by $k$.

Thus, you are correct in that the dual solution $y^*$ would scale by $k$ since there was an introduction of $k$ more resources for the dual.

Miss Mae
  • 1,576