2

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 ?

Qwerto
  • 969
  • 6
  • 20

1 Answers1

0

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.

Kuifje
  • 9,584