1
$\begingroup$

For a constraint as Ax <= b, the dual shows the change in the objective function if the RHS increases by 1 unit. Now my question is that how we can determine how the optimal values will change by 1 unit increase in the RHS. Is there any relation with other duals and/or reduced costs to determine it without actually resolving the LP?

$\endgroup$

3 Answers 3

1
$\begingroup$

Let $\bar{A}$ and $\bar{x}$ be $A$ and $x$ augmented by slack variables, so that the constraints become $\bar{A} \bar{x} = b.$ The LP solution partitions $\bar{A} = [B N]$ (after permuting columns if necessary) where $B$ is the basis matrix and the optimal solution is partitioned into $\bar{x}_B = B^{-1} b$ and $\bar{x}_N = 0.$

If the increase $\Delta b$ in $b$ is small enough that the same basis remains optimal, then the new optimal solution is $\bar{x}_B = B^{-1} (b + \Delta b)$ and $\bar{x}_N = 0,$ which can be computed without any pivoting if you have access to the basis matrix.

If the change is big enough to result in a different basis becoming optimal, then pivoting is required. You can solve a new LP with the changed $b$ vector or you can invoke the dual simplex algorithm starting from the optimal basis to the original problem.

$\endgroup$
0
$\begingroup$

I am unsure if I understand your last sentence as well. B.T.W, To improve the objective function, it is necessary to relax the binding/active constraints. By relaxing, I mean is by having a larger feasible space.

Now, the constraints with the sign of ($\leq$) would be relaxed if the right-hand side is increased. Equivalently, the constraints with the sign of ($\geq$) would be relaxed if the right-hand side is decreased.

From the algebraic point of view, dual is equivalent to $\pi = C_{b}B^{-1}$ and its relation with the associated reduced cost of the variables would also be as $RC = C_{j} - \pi^{T}A_{j}$. These however can be achieved in each iteration of the simplex algorithm.

As a simple example, suppose a transportation problem with an objective function equal to $153.675$. The demand satisfaction constraint has usually been written as a form of ($\geq$). Suppose, its corresponding dual is $0.225$. And it means that increasing the RHS value by one unit can increase the objective function to $153.9$. It obviously shows that by increasing the RHS value the value of the objective function would be worse.

$\endgroup$
0
$\begingroup$

The allowable increase tells you the how much you can change the objective function coefficient without changing the optimal basis of the Simplex. If your objective function coefficients do not change at all, the optimal basis won't change. Then, what happens if you increase the RHS of a constraint that is binding by unit? How much would you increase the basic variable in the constraint by?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.