Documentation

The geometry of linear optimization problems

Before showing optimization models that exhibit bad behavior, we first need to understand the geometry behind them. Consider a problem of the form

For example: Note that if we denote , then the problem can be stated as The feasible region, direction of improvement , and optimal solution can be depicted as Note that whenever we move in the direction of , the value increases. Furthermore, since we can not move from to another feasible point with better objective value, we can conclude that is indeed the optimal solution for the problem. Note that is a corner point of the feasible region. This is not a coincidence; you will always find an optimal solution at a corner point if the feasible region is bounded and is not zero. If the objective is zero then all feasible solutions are optimal; we will talk more about zero objectives and their implications later.

To understand how changes in the input data affect the feasible region and the optimal solution, consider a small modification: , , and . Then our optimization problem would look like

Note that although we changed the right-hand side, this change had no effect in the optimal solution to the problem, but it did change the feasible region by enlarging the bottom part of the feasible area.

Changing the objective vector tilts the corresponding vector in the graphical representation. This of course also changes the optimal objective value. Perturbing a constraint tilts the graphical representation of the constraint. The change in changes the primal solution itself. The amount of tilting constraint undergoes depends on the relative value of the perturbation. For example, although the constraint and the constraint induce the same feasible region, the perturbation will induce more tilting that the perturbation .