Название: Linear and Convex Optimization
Автор: Michael H. Veatch
Издательство: John Wiley & Sons Limited
Жанр: Математика
isbn: 9781119664055
isbn:
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?
1.3 Optimization Terminology
Now we introduce more terminology for constrained optimization problems, as well as summarizing the terms introduced in the last section. These problems are called mathematical programs. The variables that we optimize over are the decision variables. They may be continuous variables, meaning that they can take on values in the real numbers, including fractions, or they may discrete variables that can only take on integer values. The function being optimized is the objective function. The domain over which the function is optimized is the set of points that satisfy the constraints, which can be equations or inequalities. We distinguish two kinds of constraints. Functional constraints can have any form, while variable bounds restrict the allowable values of one variable. Many problems have nonnegativity constraints as their variable bounds. In (1.1), the food constraint
Let
A solution to a mathematical program is any value of the variables.
A feasible solution is a solution that satisfies all constraints, i.e. .
The feasible region is the set of feasible solutions, i.e. .
The value of a solution is its objective function value.
An optimal solution is a feasible solution that has a value at least as large (if maximizing) as any other feasible solution.
To solve a mathematical program
Existence of Optimal Solutions When solving a mathematical program:
The problem has one or more optimal solutions (we include in this category having solutions whose value is arbitrarily close to optimal, but this distinction is rarely needed), or
The problem is an unbounded problem, meaning that, for a maximization, there is a feasible solution with value for every , or
The problem is infeasible: there are no feasible solutions, i.e. .
An unbounded problem, then, is one whose objective function is unbounded on
Figure 1.3 Problem has optimal solution for dashed objective but is unbounded for dotted objective.
Example 1.1 (Unbounded region) Consider the linear program
(1.3)
The feasible region is shown in Figure 1.3; the dashed line has an objective function value of 210. Sweeping this line down, the minimum value occurs at the corner point
1.4 Classes of Mathematical Programs
In Section 1.2 we introduced the concept of a linear program. This section introduces algebraic and matrix notation for linear programs. It then defines the three main classes of mathematical programs: linear programs, integer programs, and nonlinear programs. Each СКАЧАТЬ