0

Let an LP of the form:

$\max \ cx$

$s.t. \ Ax= b,$

$\ \ \ \ \ \ \ \ x\geq0$

Let the optimal solution of the dual LP problem be $w^*$.

If the $k^{th}$ equation of the original primal problem is multiplied by a constant $a>0$, what is the new optimal solution of the dual problem?

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149

1 Answers1

2

The dual for the original problem is :

$$\min p'b$$

$$p'A \geq c'$$

Let $a_i'$ denotes the $i^{th}$ row of $A$, where $i$ takes value from $1$ to $m$.

Let's rewrite the dual again:

$$\min \sum_{i \neq k}p_ib_i+p_kb_k$$

$$\sum_{i \neq k} p_ia_i'+p_ka_k' \geq c'$$

Now let's write down the dual upon multiplying the $k^{th}$ row by $a>0.$

Let $q$ denotes the new dual variable.

$$\min \sum_{i \neq k}q_ib_i+q_k(ab_k)$$

$$\sum_{i \neq k} q_ia_i'+q_k(aa_k') \geq c'$$

We know that multiplying a row by a non-zero constant doesn't change the objective value.

Hence given $w^*$, we should find a $q$ that satisfies the new dual. A natural choice is

$$q_i=\begin{cases} w_i^* & , i\neq k\\ \frac{w_i^*}{a} & ,i=k\end{cases}$$

Check that the proposed solution shares the same objective value and it is feasible.

Remark: We just require $a$ to be non-zero.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • hello, can you help again ? http://math.stackexchange.com/questions/1960213/sensitivity-analysis-removing-one-decision-variable-or-constraint-from-the-prev – user312479 Oct 09 '16 at 03:36