Linear and Convex Optimization. Michael H. Veatch

Linear and Convex Optimization

Linear and Convex Optimization - Michael H. Veatch

Скачать книгу
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 images intersect points satisfying the constraints for images in a single interval. Thus, an optimal objective function value is one where lines with slightly larger images do not touch the region. Is it possible for the contour line to leave the region and reenter it? That is, for images if the line for images touches the region and the line for images does not, it possible for the line for images to touch the region? If so, we would have to do more checking to find the optimal images. Related to this is the question of local maxima. The point images is called a local maximum as it has the largest objective function value of all points in a small circle around images. 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

      The fractional solution images makes sense in this problem: one pallet is re‐packed with images 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.

      1.2.1 The Modeling Process

      As we move from this small linear program to more general and complex models, some guidelines on modeling will be helpful. When formulating a mathematical program, it is not always obvious what the decision variables should be. There are often multiple approaches to defining the variables and there can be pros and cons to different approaches. The objective is intended to reflect the priorities of the decision‐maker. To pose the situation as a mathematical program, an objective must be chosen. This may be very clear, as when maximizing profit, or much more subtle, as in the example previously. The constraints may include physical, logical, financial, or other limitations. They may also reflect policies that the decision‐maker applies. Finally, a constraint may simply be an equation that defines an auxiliary variable that is used to write the problem more concisely.

      Another theme that will emerge is the difference between specific and general models. We will often use algebraic notation for (some of) the constants in a model, rather than numbers. This allows us to separate the data that goes into a model from its structure. It is this structure that defines the general model. There are multiple levels of generality to a model used in an application. One way to generalize is to allow any size of the problem: instead of two items being loaded, there could be images items. To make a model more specific, we often add constraints with a special structure to describe a specific situation.

      The examples in this book take a verbal description of an optimization problem and translate it into mathematics. There is much more involved in using models to guide decisions. The overall modeling process may involve:

      1 Problem definition. The first step is to identify the problem that the decision‐maker faces. This includes specifying the objective and the system to be studied.

      2 Data collection. The next step is to collect data that is relevant to the model. This may entail observing the system or obtaining data that is already recorded.

      3 Model formulation. In this step the analyst formulates a mathematical model of the decision problem. It involves translation into mathematical language, but also abstraction or simplification of a complex operation into a manageable problem.

      4 Model solution. For optimization problems, this step finds an optimal or near‐optimal solution. Generally this is done numerically using an algorithm, rather than algebraically.

      5 Verification and validation. This step tries to determine if the model is an adequate representation of the decision problem. Verification involves checking for internal consistency in that the mathematical model agrees with its specification or assumptions. Validation seeks to build confidence that the model is sufficiently accurate. For optimization problems, accuracy may be gauged by whether the optimal solution produced by the model is reasonable or whether the objective function is accurate over a variety of feasible solutions. Validation methods that have been developed for statistical or simulation models might also be used.

      6 Implementation. Once an optimal solution is obtained from the model, it may need to be modified. For example, fractional values may need to be converted to integers. The result may be one or more near‐optimal solutions that are presented to the decision‐maker. In other situations, the model may provide insights that help the decision‐maker with their decisions, or a system might be implemented so that the model is run repeatedly with new data to support future decisions.

      These steps are not just done in this order. The verification and validation process, feedback obtained about the model, and changing situations often lead to multiple cycles of revising the model. When applications are presented in this book, we focus on Step 3, model formulation, and mostly on the translation process, not the simplifying assumptions. Whether a model is useful, however, depends on the other steps. It is important to ask “Where does the data come from?” as in Albright and Winston (2005). But it is also necessary to ask “Where does the model come from?,” that is, what are the model assumptions and why were they made?

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