2
$\begingroup$

In Linear programming a degenerate basic feasible solution leads to no increment of the objective function.

How , intuitively, the fact that a degenerate solution has at least one variable = 0, it's connected with the fact that it leads to no increment of the objective function ?

$\endgroup$
0
$\begingroup$

The simplex algorithm iteratively moves from a solution to another as follows: given a feasible solution with value $z_n$, a variable with positive (if we are maximizing) reduced cost $\hat{c}$ is chosen to enter the basis. The maximum value it can take for the problem to remain feasible is denoted by $v$, such that $$ z_{n+1} = z_n + \hat{c}\cdot v $$

But in case of a degenerate solution, the entering variable verifies $v=0$, hence $$ z_{n+1} = z_n + 0, $$ i.e., there is no increment of the objective function as you stated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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