Linear and Convex Optimization. Michael H. Veatch

Linear and Convex Optimization - Michael H. Veatch


Скачать книгу

      In this expression, 7.5 is the weight per pallet of tents, so images is the weight of tents. Similarly, images is the weight of food. The left‐hand side, then, is the total weight of the load, which must be less than or equal to the payload capacity of 40 (these quantities are in 1000s of lbs). The space limit requires that

equation

      The left‐hand side is the total number of pallets. This total does not have to be an integer; a total of 5.4 pallets would mean that one pallet is only loaded 40% full. Finally, only five pallets of food are ready, so

equation

      These inequalities define the domain of images. We will call them constraints and the function images to be maximized the objective function. Optimizing a function whose domain is defined by constraints is a constrained optimization problem. The complete problem is

      We have abbreviated “subject to” as “s.t.”

      Components of an Optimization Problem

      1 1. The decision variables.

      2 2. The objective function to be maximized or minimized, as a function of the decision variables.

      3 3. The constraints that the decision variables are subject to.

Graph depicts the region satisfying constraints for sending aid. equation equation

      with solution images and objective function value 44. This agrees with Figure 1.2, where the contour line drawn is images. Thus, the optimal load is four pallets of tents and two pallets of food, with an expected value of 44.

Graph depicts the optimal point and contour for sending aid.

      Solving a Linear Program Graphically

      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


Скачать книгу