Читать книгу Multi-parametric Optimization and Control - Efstratios N. Pistikopoulos - Страница 66

The properties described in the previous section are based on the assumption that the active set of the LP problem solved at is unique. This uniqueness can only be guaranteed if the solution of the LP problem is non‐degenerate. In general, degeneracy refers to the situation where the LP problem under consideration has a specific structure, which does not allow for the unique identification of the active set .3 Commonly, the two types of degeneracy encountered are primal and dual degeneracy (see Figure 2.4):

 Primal degeneracy: In this case, the vertex of the optimal solution of the LP is overdefined, i.e. there exist multiple sets such that(2.11) where, based on Eq. (2.3a):(2.12)

 Dual degeneracy: If there exists more than one point, which attains the optimal objective function value, then the optimal solution is not unique. Thus, there exist multiple sets with such that(2.13) where . Note that as shown in Figure 2.4, the solution of the problem does not necessarily have to be a vertex, and thus, Eq. (2.12) does not have to hold.

Figure 2.4 Primal and dual degeneracy in linear programming. In (a), primal degeneracy occurs since there are three constraints that are active at the solution, while in (b) dual degeneracy occurs since there is more than one point , which features the optimal objective function value.

While any solution is a valid solution of the LP problem at , the key challenge is to identify the effect of primal and dual degeneracy onto the solution of the mp‐LP problem.