第1页 / 共608页
第2页 / 共608页
第3页 / 共608页
第4页 / 共608页
第5页 / 共608页
第6页 / 共608页
第7页 / 共608页
第8页 / 共608页
Applied Mathematical Programming.pdf
Mathematical Programming:
An Overview
1
Management science is characterized by a scientific approach to managerial decision making. It attempts
to apply mathematical methods and the capabilities of modern computers to the difficult and unstructured
problems confronting modern managers.
It is a young and novel discipline. Although its roots can be
traced back to problems posed by early civilizations, it was not until World War II that it became identified
as a respectable and well defined body of knowledge. Since then, it has grown at an impressive pace,
unprecedented for most scientific accomplishments; it is changing our attitudes toward decision-making, and
infiltrating every conceivable area of application, covering a wide variety of business, industrial, military, and
public-sector problems.
Management science has been known by a variety of other names.
In the United States, operations
research has served as a synonym and it is used widely today, while in Britain operational research seems
to be the more accepted name. Some people tend to identify the scientific approach to managerial problem-
solving under such other names as systems analysis, cost–benefit analysis, and cost-effectiveness analysis.
We will adhere to management science throughout this book.
Mathematical programming, and especially linear programming, is one of the best developed and most
used branches of management science.
It concerns the optimum allocation of limited resources among
competing activities, under a set of constraints imposed by the nature of the problem being studied. These
constraints could reflect financial, technological, marketing, organizational, or many other considerations. In
broad terms, mathematical programming can be defined as a mathematical representation aimed at program-
ming or planning the best possible allocation of scarce resources. When the mathematical representation uses
linear functions exclusively, we have a linear-programming model.
In 1947, George B. Dantzig, then part of a research group of the U.S. Air Force known as Project SCOOP
(Scientific Computation Of Optimum Programs), developed the simplex method for solving the general
linear-programming problem. The extraordinary computational efficiency and robustness of the simplex
method, together with the availability of high-speed digital computers, have made linear programming the
most powerful optimization method ever designed and the most widely applied in the business environment.
Since then, many additional techniques have been developed, which relax the assumptions of the linear-
It is this
programming model and broaden the applications of the mathematical-programming approach.
spectrum of techniques and their effective implementation in practice that are considered in this book.
1.1 AN INTRODUCTION TO MANAGEMENT SCIENCE
Since mathematical programming is only a tool of the broad discipline known as management science,
let us first attempt to understand the management-science approach and identify the role of mathematical
programming within that approach.
1
2
Mathematical Programming: An Overview
1.2
It is hard to give a noncontroversial definition of management science. As we have indicated before,
this is a rather new field that is renewing itself and changing constantly. It has benefited from contributions
originating in the social and natural sciences, econometrics, and mathematics, much of which escape the
rigidity of a definition. Nonetheless it is possible to provide a general statement about the basic elements of
the management-science approach.
Management science is characterized by the use of mathematical models in providing guidelines to
managers for making effective decisions within the state of the current information, or in seeking further
information if current knowledge is insufficient to reach a proper decision.
There are several elements of this statement that are deserving of emphasis. First, the essence of manage-
ment science is the model-building approach—that is, an attempt to capture the most significant features of the
decision under consideration by means of a mathematical abstraction. Models are simplified representations
of the real world. In order for models to be useful in supporting management decisions, they have to be simple
to understand and easy to use. At the same time, they have to provide a complete and realistic representation
of the decision environment by incorporating all the elements required to characterize the essence of the
problem under study. This is not an easy task but, if done properly, it will supply managers with a formidable
tool to be used in complex decision situations.
Second, through this model-design effort, management science tries to provide guidelines to managers or,
in other words, to increase managers’ understanding of the consequences of their actions. There is never an
attempt to replace or substitute for managers, but rather the aim is to support management actions. It is critical,
then, to recognize the strong interaction required between managers and models. Models can expediently
and effectively account for the many interrelationships that might be present among the alternatives being
considered, and can explicitly evaluate the economic consequences of the actions available to managers within
the constraints imposed by the existing resources and the demands placed upon the use of those resources.
Managers, on the other hand, should formulate the basic questions to be addressed by the model, and then
interpret the model’s results in light of their own experience and intuition, recognizing the model’s limitations.
The complementarity between the superior computational capabilities provided by the model and the higher
judgmental capabilities of the human decision-maker is the key to a successful management-science approach.
Finally, it is the complexity of the decision under study, and not the tool being used to investigate the
decision-making process, that should determine the amount of information needed to handle that decision
effectively. Models have been criticized for creating unreasonable requirements for information. In fact,
this is not necessary. Quite to the contrary, models can be constructed within the current state of available
information and they can be used to evaluate whether or not it is economically desirable to gather additional
information.
The subject of proper model design and implementation will be covered in detail in Chapter 5.
1.2 MODEL CLASSIFICATION
The management-science literature includes several approaches to classifying models. We will begin with a
categorization that identifies broad types of models according to the degree of realism that they achieve in
representing a given problem. The model categories can be illustrated as shown in Fig. 1.1.
Operational Exercise
The first model type is an operational exercise. This modeling approach operates directly with the real
environment in which the decision under study is going to take place. The modeling effort merely involves
designing a set of experiments to be conducted in that environment, and measuring and interpreting the results
of those experiments. Suppose, for instance, that we would like to determine what mix of several crude oils
should be blended in a given oil refinery to satisfy, in the most effective way, the market requirements for
final products to be delivered from that refinery. If we were to conduct an operational exercise to support that
decision, we would try different quantities of several combinations of crude oil types directly in the actual
1.2
Model Classification
3
refinery process, and observe the resulting revenues and costs associated with each alternative mix. After
performing quite a few trials, we would begin to develop an understanding of the relationship between the
Fig. 1.1 Types of model representation.
crude oil input and the net revenue obtained from the refinery process, which would guide us in identifying
an appropriate mix.
In order for this approach to operate successfully, it is mandatory to design experiments to be conducted
carefully, to evaluate the experimental results in light of errors that can be introduced by measurement inac-
curacies, and to draw inferences about the decisions reached, based upon the limited number of observations
performed. Many statistical and optimization methods can be used to accomplish these tasks properly. The
essence of the operational exercise is an inductive learning process, characteristic of empirical research in the
natural sciences, in which generalizations are drawn from particular observations of a given phenomenon.
Operational exercises contain the highest degree of realism of any form of modeling approach, since
hardly any external abstractions or oversimplifications are introduced other than those connected with the
interpretation of the observed results and the generalizations to be drawn from them. However, the method
is exceedingly, usually prohibitively, expensive to implement. Moreover, in most cases it is impossible to
exhaustively analyze the alternatives available to the decision-maker. This can lead to severe suboptimization
in the final conclusions. For these reasons, operational exercises seldom are used as a pure form of modeling
practice. It is important to recognize, however, that direct observation of the actual environment underlies
most model conceptualizations and also constitutes one of the most important sources of data. Consequently,
even though they may not be used exclusively, operational exercises produce significant contributions to the
improvement of managerial decision-making.
Gaming
The second type of model in this classification is gaming. In this case, a model is constructed that is an
abstract and simplified representation of the real environment. This model provides a responsive mechanism
to evaluate the effectiveness of proposed alternatives, which the decision-maker must supply in an organized
and sequential fashion. The model is simply a device that allows the decision-maker to test the performance
of the various alternatives that seem worthwhile to pursue. In addition, in a gaming situation, all the human
interactions that affect the decision environment are allowed to participate actively by providing the inputs
they usually are responsible for in the actual realization of their activities. If a gaming approach is used in our
previous example, the refinery process would be represented by a computer or mathematical model, which
could assume any kind of structure.
The model should reflect, with an acceptable degree of accuracy, the relationships between the inputs and
outputs of the refinery process. Subsequently, all the personnel who participate in structuring the decision
process in the management of the refinery would be allowed to interact with the model. The production man-
ager would establish production plans, the marketing manager would secure contracts and develop marketing
4
Mathematical Programming: An Overview
1.2
strategies, the purchasing manager would identify prices and sources of crude oil and develop acquisition
programs, and so forth. As before, several combinations of quantities and types of crude oil would be tried,
and the resulting revenues and cost figures derived from the model would be obtained, to guide us in for-
mulating an optimal policy. Certainly, we have lost some degree of realism in our modeling approach with
respect to the operational exercise, since we are operating with an abstract environment, but we have retained
some of the human interactions of the real process. However, the cost of processing each alternative has been
reduced, and the speed of measuring the performance of each alternative has been increased.
Gaming is used mostly as a learning device for developing some appreciation for those complexities
inherent in a decision-making process. Several management games have been designed to illustrate how
marketing, production, and financial decisions interact in a competitive economy.
Simulation
Simulation models are similar to gaming models except that all human decision-makers are removed from
the modeling process. The model provides the means to evaluate the performance of a number of alterna-
tives, supplied externally to the model by the decision-maker, without allowing for human interactions at
intermediate stages of the model computation.
Like operational exercises and gaming, simulation models neither generate alternatives nor produce an
optimum answer to the decision under study. These types of models are inductive and empirical in nature;
they are useful only to assess the performance of alternatives identified previously by the decision-maker.
If we were to conduct a simulation model in our refinery example, we would program in advance a large
number of combinations of quantities and types of crude oil to be used, and we would obtain the net revenues
associated with each alternative without any external inputs of the decision-makers. Once the model results
were produced, new runs could be conducted until we felt that we had reached a proper understanding of the
problem on hand.
Many simulation models take the form of computer programs, where logical arithmetic operations are
performed in a prearranged sequence. It is not necessary, therefore, to define the problem exclusively in
analytic terms. This provides an added flexibility in model formulation and permits a high degree of realism
to be achieved, which is particularly useful when uncertainties are an important aspect of the decision.
Analytical Model
Finally, the fourth model category proposed in this framework is the analytical model. In this type of model,
the problem is represented completely in mathematical terms, normally by means of a criterion or objective,
which we seek to maximize or minimize, subject to a set of mathematical constraints that portray the conditions
under which the decisions have to be made. The model computes an optimal solution, that is, one that satisfies
all the constraints and gives the best possible value of the objective function.
In the refinery example, the use of an analytical model implies setting up as an objective the maximization
of the net revenues obtained from the refinery operation as a function of the types and quantities of the crude
oil used. In addition, the technology of the refinery process, the final product requirements, and the crude
oil availabilities must be represented in mathematical terms to define the constraints of our problem. The
solution to the model will be the exact amount of each available crude-oil type to be processed that will
maximize the net revenues within the proposed constraint set. Linear programming has been, in the last two
decades, the indisputable analytical model to use for this kind of problem.
Analytical models are normally the least expensive and easiest models to develop. However, they intro-
duce the highest degree of simplification in the model representation. As a rule of thumb, it is better to be
as much to the right as possible in the model spectrum (no political implication intended!), provided that the
resulting degree of realism is appropriate to characterize the decision under study.
Most of the work undertaken by management scientists has been oriented toward the development and
implementation of analytical models. As a result of this effort, many different techniques and methodologies
have been proposed to address specific kinds of problems. Table 1.1 presents a classification of the most
important types of analytical and simulation models that have been developed.
1.3
Formulation of Some Examples
5
Table 1.1 Classification of Analytical and Simulation Models
Strategy evaluation
Strategy generation
Certainty
Uncertainty
Deterministic simulation
Econometric models
Systems of simultaneous
equations
Input-output models
Linear programming
Network models
Integer and mixed-integer
programming
Nonlinear programming
Control theory
Monte Carlo simulation
Econometric models
Stochastic processes
Queueing theory
Reliability theory
Decision theory
Dynamic programming
Inventory theory
Stochastic programming
Stochastic control theory
Statistics and subjective assessment are used in all models to determine values for
parameters of the models and limits on the alternatives.
The classification presented in Table 1.1 is not rigid, since strategy evaluation models are used for
improving decisions by trying different alternatives until one is determined that appears ‘‘best.’’ The important
distinction of the proposed classification is that, for strategy evaluation models, the user must first choose
and construct the alternative and then evaluate it with the aid of the model. For strategy generation models,
the alternative is not completely determined by the user; rather, the class of alternatives is determined by
establishing constraints on the decisions, and then an algorithmic procedure is used to automatically generate
the ‘‘best’’ alternative within that class. The horizontal classification should be clear, and is introduced because
the inclusion of uncertainty (or not) generally makes a substantial difference in the type and complexity of
the techniques that are employed. Problems involving uncertainty are inherently more difficult to formulate
well and to solve efficiently.
This book is devoted to mathematical programming—a part of management science that has a common
base of theory and a large range of applications. Generally, mathematical programming includes all of
the topics under the heading of strategy generation except for decision theory and control theory. These
two topics are entire disciplines in themselves, depending essentially on different underlying theories and
techniques. Recently, though, the similarities between mathematical programming and control theory are
becoming better understood, and these disciplines are beginning to merge. In mathematical programming,
the main body of material that has been developed, and more especially applied, is under the assumption of
certainty. Therefore, we concentrate the bulk of our presentation on the topics in the upper righthand corner
of Table 1.1. The critical emphasis in the book is on developing those principles and techniques that lead
to good formulations of actual decision problems and solution procedures that are efficient for solving these
formulations.
1.3 FORMULATION OF SOME EXAMPLES
In order to provide a preliminary understanding of the types of problems to which mathematical programming
can be applied, and to illustrate the kind of rationale that should be used in formulating linear-programming
problems, we will present in this section three highly simplified examples and their corresponding linear-
programming formulations.
Charging a Blast Furnace∗ An iron foundry has a firm order to produce 1000 pounds of castings containing
at least 0.45 percent manganese and between 3.25 percent and 5.50 percent silicon. As these particular castings
are a special order, there are no suitable castings on hand. The castings sell for $0.45 per pound. The foundry
has three types of pig iron available in essentially unlimited amounts, with the following properties:
∗ Excel spreadsheet available at http://web.mit.edu/15.053/www/Sect1.3_Blast_Furnace.xls
6
Mathematical Programming: An Overview
1.3
Type of pig iron
Silicon
Manganese
A
4 %
0.45%
B
1 %
0.5%
C
0.6%
0.4%
Further, the production process is such that pure manganese can also be added directly to the melt. The costs
of the various possible inputs are:
Pig A
Pig B
Pig C
Manganese
$21/thousand pounds
$25/thousand pounds
$15/thousand pounds
$ 8/pound.
It costs 0.5 cents to melt down a pound of pig iron. Out of what inputs should the foundry produce the castings
in order to maximize profits?
The first step in formulating a linear program is to define the decision variables of the problem. These are
the elements under the control of the decision-maker, and their values determine the solution of the model.
In the present example, these variables are simple to identify, and correspond to the number of pounds of pig
A, pig B, pig C, and pure manganeseto be used in the production of castings. Specifically, let us denote the
decision variables as follows:
x1 = Thousands of pounds of pig iron A,
x2 = Thousands of pounds of pig iron B,
x3 = Thousands of pounds of pig iron C,
x4 = Pounds of pure manganese.
The next step to be carried out in the formulation of the problem is to determine the criterion the decision-
maker will use to evaluate alternative solutions to the problem. In mathematical-programming terminology,
this is known as the objective function. In our case, we want to maximize the total profit resulting from the
production of 1000 pounds of castings. Since we are producing exactly 1000 pounds of castings, the total
income will be the selling price per pound times 1000 pounds. That is:
Total income = 0.45 × 1000 = 450.
To determine the total cost incurred in the production of the alloy, we should add the melting cost of
$0.005/pound to the corresponding cost of each type of pig iron used. Thus, the relevant unit cost of the pig
iron, in dollars per thousand pounds, is:
Pig iron A
Pig iron B
Pig iron C
21 + 5 = 26,
25 + 5 = 30,
15 + 5 = 20.
Therefore, the total cost becomes:
Total cost = 26x1 + 30x2 + 20x3 + 8x4,
and the total profit we want to maximize is determined by the expression:
Total profit = Total income − Total cost.
Thus,
Total profit = 450 − 26x1 − 30x2 − 20x3 − 8x4.
(1)
(2)
1.3
Formulation of Some Examples
7
It is worthwhile noticing in this example that, since the amount of castings to be produced was fixed in
advance, equal to 1000 pounds, the maximization of the total profit, given by Eq. (2), becomes completely
equivalent to the minimization of the total cost, given by Eq. (1).
We should now define the constraints of the problem, which are the restrictions imposed upon the values
of the decision variables by the characteristics of the problem under study. First, since the producer does not
want to keep any supply of the castings on hand, we should make the total amount to be produced exactly
equal to 1000 pounds; that is,
1000x1 + 1000x2 + 1000x3 + x4 = 1000.
Next, the castings should contain at least 0.45 percent manganese, or 4.5 pounds in the 1000 pounds of
castings to be produced. This restriction can be expressed as follows:
4.5x1 + 5.0x2 + 4.0x3 + x4 ≥ 4.5.
(4)
The term 4.5x1 is the pounds of manganese contributed by pig iron A since each 1000 pounds of this pig iron
contains 4.5 pounds of manganese. The x2, x3, and x4 terms account for the manganese contributed by pig
iron B, by pig iron C, and by the addition of pure manganese.
Similarly, the restriction regarding the silicon content can be represented by the following inequalities:
40x1 + 10x2 + 6x3 ≥ 32.5,
40x1 + 10x2 + 6x3 ≤ 55.0.
(3)
(5)
(6)
Constraint (5) establishes that the minimum silicon content in the castings is 3.25 percent, while constraint
Finally, we have the obvious nonnegativity constraints:
(6) indicates that the maximum silicon allowed is 5.5 percent.
x3 ≥ 0,
x2 ≥ 0,
x1 ≥ 0,
x4 ≥ 0.
If we choose to minimize the total cost given by Eq. (1), the resulting linear programming problem can
be expressed as follows:
Minimize z =
subject to:
26x1 + 30x2 + 20x3 +
1000x1 + 1000x2 + 1000x3 +
4.5x1 + 5.0x2 + 4.0x3 +
40x1 + 10x2 +
40x1 + 10x2 +
x1 ≥ 0,
6x3
6x3
x3 ≥ 0,
8x4,
x4 = 1000,
x4 ≥ 4.5,
≥ 32.5,
≤ 55.0,
x4 ≥ 0.
Often, this algebraic formulation is represented in tableau form as follows:
x2 ≥ 0,
Total lbs.
Manganese
Silicon lower
Silicon upper
Objective
(Optimal solution)
x1
1000
4.5
40
40
26
0.779
Decision variables
x2
1000
x3
1000
x4
1
1
0
0
8
Relation Requirements
=
≥
≥
≤
=
1000
4.5
32.5
55.0
z (min)
25.54
4
6
6
20
5
10
10
30
0
0.220
0.111
The bottom line of the tableau specifies the optimal solution to this problem. The solution includes
the values of the decision variables as well as the minimum cost attained, $25.54 per thousand pounds; this
solution was generated using a commercially available linear-programming computer system. The underlying
solution procedure, known as the simplex method, will be explained in Chapter 2.
8
Mathematical Programming: An Overview
1.3
Fig. 1.2 Optimal cost of castings as a function of the cost of pure manganese.
It might be interesting to see how the solution and the optimal value of the objective function is affected
by changes in the cost of manganese. In Fig. 1.2 we give the optimal value of the objective function as this
cost is varied. Note that if the cost of manganese rises above $9.86/lb., then no pure manganese is used. In the
range from $0.019/lb. to $9.86 lb., the values of the decision variables remain unchanged. When manganese
becomes extremely inexpensive, less than $0.019/lb., a great deal of manganese is used, in conjuction with
only one type of pig iron.
Similar analyses can be performed to investigate the behavior of the solution as other parameters of the
problem (for example, minimum allowed silicon content) are varied. These results, known as parametric
analysis, are reported routinely by commercial linear-programming computer systems. In Chapter 3 we will
show how to conduct such analyses in a comprehensive way.
Portfolio Selection∗ A portfolio manager in charge of a bank portfolio has $10 million to invest. The
securities available for purchase, as well as their respective quality ratings, maturities, and yields, are shown
in Table 1.2.
Table 1.2
Bond
name
Bond
type
Quality scales
Moody’s
Bank’s
Years to
maturity
Yield to
maturity
After-tax
yield
A
B
C
D
E
Municipal
Agency
Government
Government
Municipal
Aa
Aa
Aaa
Aaa
Ba
2
2
1
1
5
9
15
4
3
2
4.3%
5.4
5.0
4.4
4.5
4.3%
2.7
2.5
2.2
4.5
The bank places the following policy limitations on the portfolio manager’s actions:
1. Government and agency bonds must total at least $4 million.
2. The average quality of the portfolio cannot exceed 1.4 on the bank’s quality scale. (Note that a low
number on this scale means a high-quality bond.)
3. The average years to maturity of the portfolio must not exceed 5 years.
Assuming that the objective of the portfolio manager is to maximize after-tax earnings and that the tax rate is
50 percent, what bonds should he purchase? If it became possible to borrow up to $1 million at 5.5 percent
∗ Excel spreadsheet available at http://web.mit.edu/15.053/www/Sect1.3_Portfolio_Selection.xls
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
