Alternative optimal solutions

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 slice that is parallel to the obj function will be affine transforms and will produce the same value of the obj function.

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

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

The constraints in the linear programming model form the boundaries of the polyhedron or the hyperplane of the polyhedron. But simply modifying the constraint, say from 4 * X + 5 * Y <5 to 4 * X + 5 * Y <5.1, would result in altering the feasible region just a little bit, but would fail to produce alternative optimal solutions.

In the same context, we can also discuss what forms a feasible convex set and why linear programming problems require the set of constraints to be convex. The optimal solution for 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 at the vertex? This is because the feasible set can be viewed as the limit imposed by constraints. Constraints in a linear programming model would result in a polyhedron / polytope. When this is convex it means that any point connecting the two vertices does not lie inside, and therefore the extreme solution of the objective function will necessarily lie at the vertex.