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 the nonbasic or decision variables.

Alternative optimal solutions occur mainly because a part of the polyhedron is parallel to the objective function. In such cases, all points along the segment of the portion that is parallel to the function obj will be affine transforms and will produce the same value of the function obj.

In a practical situation, the implications of this would be that when one is trying to solve a problem of trying to calculate the maximum profit given the effort to make 10 different products and the total constraint on available labor in the plant. Assuming that the problem has 10 decision variables and two constraints. Due to the degeneracy explained above, you can generate a $10,000 maximum profit optimal solution for multiple combinations of the product mix that is required to be manufactured in the factory.

In such cases, it is very difficult to determine which output combination to choose as the optimal criteria, since there are actually multiple values. The parallel part of the edge of the polyhedron or hyperplane connecting two planes of an n-dimensional polyhedron can be slightly altered by adjusting the constraints a bit.

The constraints in the linear programming model form the limits of the polyhedron or the hyperplane of the polyhedron. But simply changing the constraint, say from 4*X + 5 * Y < 5 to 4*X + 5 * Y < 5.1, would alter the feasible region a bit, but would no longer produce alternative optimal solutions.

In the same context, we can also discuss what forms a convex feasible set and why linear programming problems require that the constraint set be convex. The optimal solution to a linear programming formulation is found by traversing the set of constraints from vertex to vertex. So why doesn’t an optimal solution fall somewhere on an edge connecting two vertices, but only on the vertex? This is because the feasible set can be viewed as the limit imposed by the constraints. Constraints in a linear programming model would result in a polyhedron/polytope. When this is convex it means that any point that connects the two vertices is not inside and therefore the extreme solution of the objective function will necessarily be found in the vertex.