Linear and Convex Optimization. Michael H. Veatch

Linear and Convex Optimization - Michael H. Veatch


Скачать книгу
mathematical model is an optimization problem; the study of them is called optimization.

      Once a system has been modeled, an algorithm is required to find the best, or nearly best, decision. Fortunately, there are general algorithms that can be used to solve broad classes of problems. Algorithms for several classes of problems will be the main topic of this book.

      Optimization is a very broad concept. There are minimization principles in physics, such as Snell's law of diffraction, or surface tension minimizing the area of a surface. In statistics, the least squares principle is an easily‐solved minimization problem while new techniques involve challenging optimization problems to fit models to data. Control engineers use minimization principles to develop feedback controls for systems such as autopilots and robots. Many techniques in machine learning can also be described as optimization problems.

      Operations research is sometimes also called management science or operational research. Similar techniques are used in industrial engineering and operations engineering, with a somewhat narrower view of applications. There is a strong overlap with business analytics, which refers to any use of data to improve business processes, whether statistical methods or optimization.

      While the use of optimization models for decision‐making has become common, most of the decisions to which they are applied are not fully automated; rather, the models provide guidelines or insights to managers for making decisions. For some problems, models can be fairly precise and identify good decisions. For many others, the model is enough of an approximation that the goal of modeling is insights, not numbers. We only briefly cover the modeling process, at the beginning of Chapter 2. However, the examples we present give some appreciation for how models can be useful for decisions.

      A prime example of the use of optimization models is the airline industry (Barnhart et al., 2003). Starting in the late 1960s with American Airlines and United Airlines, flight schedules, routing, and crew assignment in the airline industry were based on large‐scale, discrete optimization models. By about 1990, airlines started using revenue management models to dynamically adjust prices and use overbooking, generating significant additional revenues. Optimization models have also been used more recently for air traffic flow management.

      International responses to rapid‐onset disasters are frequent and expensive. After a major disaster, such as the 2014 earthquake in Nepal, food, shelter, and other items are needed quickly in large quantities. Local supplies may be insufficient, in which case airlift to a nearby airport is an important part of a timely response. The number of flights in the first few days may be limited by cost and other factors, so the aid organizations seek to send priority items first.

Tents Food
Weight (1000 lbs) 7.5 5
Cost ($1000/pallet) 11 4
Criticality 5 8
Expected benefit 8 6

      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

equation

      Then the expected value of aid loaded is

equation

      and we want to maximize images over a domain that contains the possible values of images. First, we have the logical restrictions images. The weight limit requires that

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