Sometimes when an optimization model is formulated, the model produces many alternative optimal solutions, which means that for the same value of the objective function, the model produces multiple values of non-basic variables or decision variables.

The surrogate optimal solution arises mainly because some parts of the polyhedron are parallel to the objective function. In this case, all points along the segment of the line parallel to the obj function will be affine transformed and will yield the same value as the obj function.

In practical terms, this means when one is trying to solve a problem, say trying to calculate the maximum profit under the constraints of the effort to produce 10 different products and the total labor available in the factory. Suppose the problem has 10 decision variables and two constraints. Because of the degeneracy explained above, for multiple combinations of product portfolios that need to be manufactured in a factory, it may yield the best solution with a maximum profit of $10,000.

In this case, it is difficult to decide which production mix to choose as the best criterion, since there are actually multiple values. Parallel parts of a polyhedron edge or a hyperplane connecting two planes of an n-dimensional polyhedron can be slightly perturbed by adjusting the constraints slightly.

Constraints in a linear programming model form the boundaries of a polyhedron or a hyperplane of a polyhedron. However, just modifying the constraints from 4*X + 5 * Y < 5 to 4*X + 5 * Y < 5.1 will cause the feasible region to change slightly, but will no longer yield an alternative optimal solution.

In the same context, we can also discuss what makes a feasible convex set and why linear programming problems require the constraint set to be convex. The optimal solution to a linear programming formula is found by traversing a set of constraints from one vertex to another. So why doesn’t the optimal solution fall on the edge connecting the two vertices, but only on the vertices? This is because feasible sets can be visualized as bounds enforced by constraints. Constraints in a linear programming model will result in a polyhedron/polyhedron. When it is convex, it means that any point connecting the two vertices is not inside, so the extremal solution of the objective function must be found on the vertex.