Читать книгу Linear and Convex Optimization - Michael H. Veatch - Страница 15

1 Graph the region that satisfies all of the constraints.

2 Draw a contour line of the objective function and determine which direction improves the objective function. A second contour line can be used to determine which direction is improving.

3 Sweep the contour line in the improving direction, generating parallel lines, until it is about to leave the region. The last line intersecting the region has the optimal objective function value. The point(s) where this line intersects the region is optimal.

4 Find the coordinates of an optimal point by solving a system of two linear equations from the constraints whose lines pass through this point.

If the set of points satisfying the constraints is nonempty and bounded, then an optimal solution exists and the method earlier will find it. The other cases are discussed in Section 1.3.

Viewing the problem graphically brings up several questions about linear programs that will be answered in later chapters. First, the optimal value occurred at a corner point of the region, where two (or more) constraint lines intersect. Will this always be the case? Second, the idea of sweeping the contour line until it leaves the region assumes that contour lines intersect points satisfying the constraints for in a single interval. Thus, an optimal objective function value is one where lines with slightly larger do not touch the region. Is it possible for the contour line to leave the region and reenter it? That is, for if the line for touches the region and the line for does not, it possible for the line for to touch the region? If so, we would have to do more checking to find the optimal . Related to this is the question of local maxima. The point is called a local maximum as it has the largest objective function value of all points in a small circle around . It is easier to check that it is a local maximum than examining all points that satisfy the constraints to check that it is a global maximum. Is it always true that a local maximum is also a global maximum? Finally, the region in Figure 1.2 is defined by the constraints, but the optimal point depends on the objective function. For example, if instead we wish to maximize

(1.2)

the optimal load is pallets of tents and pallets of food, with a cost of $58 667. However, for small changes in the coefficients of , the point is still optimal. How much can an objective function coefficient be changed without changing the optimal point?

The fractional solution makes sense in this problem: one pallet is re‐packed with as much food. In other problems, fractional solutions may not make sense. They can either be interpreted as approximate solutions that must be converted to integers to be implemented, or a different optimization problem can be studied, where the variables are discrete, only taking on integer values.