Question about sensitivity analysis of an LP problem

122 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.