Название: Linear and Convex Optimization
Автор: Michael H. Veatch
Издательство: John Wiley & Sons Limited
Жанр: Математика
isbn: 9781119664055
isbn:
The first idea one might have is to load six pallets of tents, the item with the largest expected benefit. However, this load is not allowed because it exceeds the weight limit. Further, since the number of pallets does not have to be an integer, trying other loads may not find the best one. Instead, we formulate the problem mathematically. Let
Then the expected value of aid loaded is
and we want to maximize
In this expression, 7.5 is the weight per pallet of tents, so
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
These inequalities define the domain of
We have abbreviated “subject to” as “s.t.”
Constrained optimization problems have three components:
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.
The formulation of this problem consists of the Eqs. (1.1) and the definitions of the variables. It is essential to define the variables and also good practice to label or describe the objective function and each constraint. This problem is an example of a linear program because the variables are continuous and the objective function and all constraints are linear.
Now that we have formulated the loading decisions as a linear program, how do we solve it? For
Figure 1.1 Region satisfying constraints for sending aid.
are graphed as dashed lines. They both intersect the shaded region, so there are points satisfying the constraints with objective function values of 24 and 36. Since all contour lines are parallel, we can visualize sweeping the line up and to the right without rotating it to find larger objective function values. The farthest contour line that touches the shaded region is shown in Figure 1.2. The point where it touches the region has the largest objective function value. This point lies on the constraint lines for weight and pallets, so we can find it by solving these two constraints with equality in place of inequality:
with solution