"For any linear programming problem with n decision variables, each CPF solution lies at the intersection of n constraint boundaries; i.e., it is the simultaneous solution of a system of n constraint boundary equations. However, this is not to say that every set of n constraint boundary equations chosen from the n + m constraints (n nonnegativity and m functional constraints) yields a CPF solution. In particular, the simultaneous solution of such a system of equations might violate one or more of the other m constraints not chosen, in which case it is a corner-point infeasible solution" Please, why is this so? Why is the intersection of "n" out of the "n+m" constraint boundaries a corner-point solution at all?
Asked
Active
Viewed 30 times
1 Answers
0
The location of an optima is one of the following:
- A stationary point
- A point where the objective function is discontinuous
- The boundary of the feasible region
Linear programming deals with linear functions. Consequently, there is no stationary point or discontinuity. Thus, the optima is on the boundary.
When you are in $n$ dimensional space, the boundary is defined by $n$ constraint equations. For example, in 2D space, a corner point is the intersection of two lines.
The popular simplex method takes advantage of this, the method “walks” along the boundary to find the optima.
acat3
- 11,897