原文：
Multivariable Optimization
The practical problems associated with locating the global optimum of a function of several variables are similar in many ways to those discussed in the preceding section. Additional complications arise because of the dimension of the problem. Graphical techniques are not available in dimensions n gt; 3,and solving ▽f= 0 becomes more complicated as the number of independent variables increases. Constrained optimization is also more difficult because the geometry of the feasible region can be more complicated.
Example 3.2. A suburban community intends to replace its old fire station with a new facility. The old station was located at the historical city center.City planners intend to locate the new facility more scientifically. A statistical analysis of response-time data yielded an estimate of 3.2 1.7 minutes required to respond to a call r miles away from the station. (The derivation of this formula is the subject of Exercises 17 and 18 in Chapter 8.) Estimates ofthe frequency of calls from different areas of the city were obtained from the
fire chief. They are presented in Figure 3.7. Each block represents one square
mile,and the numbers inside each block represent the number of emergency calls
per year for that block. Find the best location for the new facility.
We will represent locations on the city map by coordinates (x, y), where x is the
distance in miles to the west side of town, and y is the distance in miles to the south side. For example, (0, 0) represents the lower left-hand corner of the map,
and (0, 6) represents the upper left-hand corner. For simplicity we will divide the
city into nine 2 x 2-mile squares and assume that each emergency is located at thecenter of the square. If (x, y) is the location of the new fire station, the average response time to a call is z= f(x, y), where
The problem is to minimize z= f(x, y) over the feasible region 0 lt; x lt; 6,0lt;ylt; 6.
Figure 3.8 shows a 3-D graph of the objective function f over the feasible region. It appears as though f attains its minimum at the unique interior point at which ▽f = 0. Figure 3.9 shows a contour plot of the level sets of f,indicating that ▽f= 0 near the point x= 2 and y= 3.
Now, it is certainly possible to compute ▽f in this problem, but it is not possible to solve ▽f = 0 algebraically. Further graphical analysis is possible,but this is especially cumbersome for functions of more than one variable. What is needed here is a simple global method for estimating the minimum.
Figure 3.10 presents an algorithm for random search. This optimization method simply picks N feasible points at random and selects the one that yields the smallest value of the objective function. The notation Random {S} denotes a randomly selected point from the set s. A computer implementation of random search was applied to the function in Eq. (3.15) with a=0,b=6,c=0,d=6, and N = 1, 000. The resulting estimate of the minimum occurred at
x min=1.66
y min=2.73
z min=6.46.
Since this algorithm involves random numbers, a repetition
of the same computer implementation with the same inputs
may produce slightly different out-puts. The accuracy of random search is roughly the same as if the N points were to lie on an equally spaced grid over the entire feasible set. Such a grid would contain 32 x 32 points (322 ~ 1, 000), so we would be accurate to within6/32~0.2 in both x and y. Since ▽f= 0 at the
minimum, we obtain much better accuracy in z. An alternative to random search would be a grid search(examine z= F(x,y) at N equally spaced points). The performance of grid search is essentially the same as random search, but random search is more flexible and
easier to implement.
The estimates in Eq. (3.16) of the optimum location (1.7,2.7) and the re
sulting average response time of 6.46 minutes were obtained by evaluating the objective function at N = 1, 000 random points in the feasible region. Better accuracy could be obtained by increasing N. However, the behavior of this simple, global method does not encourage such an approach. Each additional decimal place of accuracy requires increasing N by a factor of one hundred.Hence, this method is only suitable for obtaining a rough approximation of the optimum. For the present problem the answer we found is good enough. The simplifying assumptions we made earlier introduced errors on the order of one mile in
emergency location, so there is no point in demanding more accuracy now. It is enough to state that the facility should be located around (1.7, 2.7)on the map, for an average response time of around 6.5 minutes. The exact location will, in any case, depend on several factors not incorporated into our model, such as the location of roads and the availability of land in the area of the optimal site. It is also reasonable to consider different definitions of an optimal location; see Exercise 3.6.
It is important to provide an estimate of the sensitivity of response time to the eventual facility location. Since ▽f = 0 at the optimal location, we do not expect f to vary much near(1.7, 2.7). To obtain a more concrete understanding of the sensitivity of f to (ж, y) near the optimum, we reran the random search program, replacing f by-f and bounding 1.5lt;xlt;2, 2.5lt;ylt;3. After N = 100 observations we found that the maximum of f over this region was approximately 6. 49 minutes, or about 0.03 minutes longer than the observed optimum. It does not matter in any practical sense where in this half- mile square area we locate the station.
The random search methods employed in the preceding example are simple but slow. For some problems, where greater accuracy is required, such method sare unsuitable. If the functions inv
剩余内容已隐藏，支付完成后下载完整资料
附录A 译文
最优化模型
多变量最优化
关于求一个多元函数的整体最优值点的实际问题与上一节讨论的问题在很多地方都是相似的。由于维数的增加，问题的复杂度也增加了。对维数ngt;3的情况，图像法已不再适用。对方程▽f=0的求解也由于独立变量个数的增加而变得很复杂。有约束的最优化问题由于可行域的几何形状可能很复杂，求解也更为困难。
例3.2 一个城郊的社区计划更新他们的消防站。原来的消防站设置在历史上的市中心，城市规划人员要将新的消防站设置得更科学合理。对响应时间数据的统计分析给出:对离救火站英里处打来求救电话，需要的响应时间估计为3.2 1.7 分钟。(第8章的习题16、17涉及了推导此公式的内容。)图3-7中给出了从消防官员处得到的从城区的不同区域打来的求救电话频率的估计数据。其中每一格代表一平方英里，格内的数字为每年从此区城打来的紧急求教电话的数量。求新的消防站的最佳位置。
|
3 |
0 |
1 |
4 |
2 |
1 |
|
2 |
1 |
1 |
2 |
3 |
2 |
|
5 |
3 |
3 |
0 |
1 |
2 |
|
8 |
5 |
2 |
1 |
0 |
0 |
|
10 |
6 |
3 |
1 |
3 |
1 |
|
0 |
2 |
3 |
1 |
1 |
1 |
图3-7 城区的每一平方英里区域每年发生的紧急呼救次数地图（上北右东）
我们用(x，y)坐标来标记城区的地图上的位置。其中x为按英里到城市西部边界的距离，y为按英里到南部边界的距离。例如，(0, 0)为地图的左下角，(0, 6)为地图的左上角。为简单起见，我们将此城区划分为9个2x2平方英里的正方形子区域，并假设每一次紧急呼救都发生在正方形的中心。如果(x,y)是新的消防站的位置，则对求救电话的平均响应时间为z=f(x，y)，其中
问题是在区域0le;xle;6,0le;yle;6上对z=f(x,y)求最小值
图3-8为目标函数f在可行域上的三维图像。该图显示f在▽f=0的惟一内点达到最小值。图3-9为f的水平集的等值线图，显示了▽f=0发生在点x=2,y=3附近。
对此问题当然可以计算出▽f，但▽f=0无法代数求解。进一步的图像分析是可以的，但对多于一个变量的函数进行图像分析是非常麻烦的。我们这里需要的是用一个简单的全局方法对最小值点给出一个估计。
图3-10为随机搜索算法。这种最优化方法只是随机地在可行域上选取N个点，选择其中使目标函数的值达最小的点。记号随机数{S}表示在集合S中随机选取的一个点。取a=0,b=6,c=0,d=6及N=1000,对(3-15)式中的函数采用随机搜索算法，用计算机实现，得到
最小值点的近似值为:
x min=1.66
y min=2.73
z min=6.46.
图3-10 随机搜索方法的伪代码
由于该算法采用了随机数，所以输人同样数据，再一次执行此程序可能会得到略有不同的解。随机搜索的精确程度与N个点在整个可行域上按均匀网格分布的情况大致相当。这样的网格应该有32 x32个网格点( asymp;1 000)，因此在x和y方向上的精度都约为6/32asymp;0.2。由于在最小点有▽f=0,我们得到的z的精度会高很多。除了随机搜索外，另一种方法是格点搜索(在N个等距节点处检查z=F(x,y))。格点搜索方法的性能基本上与随机搜索相同，但随机搜索方法更灵活，也更容易实现。
(3-16)式中的最小点位置(1.7,2.7)及相应的平均响应时间6.46分钟的估计值是由在可行域中取N=1000个随机点对目标函数求值得到的。增加N会得到更高精度的解。但这简单的全局方法的特性并不适于通过增加N来提高精度。解每多增加一位小数的精确度，就要求N扩大100倍。因此这一方法只适于得到最优解的一个粗略的近似。对我们现在的问题，这样求出的解已经足够好了，由于我们在前面为简化所做的假设，消防站的位置有1英里的误差，因此现在要求更高的精度是没有必要的，可以给出一个足够近似的答案为:消防站的位置应该在地图上的(1.7,2.7)附近，这样平均的响应时间约为6.5分钟。准确的位置要受一些模型中没有体现的因素的影响，如道路的位置、在最佳位置所在区域的可用土地情况等。
对响应时间关于最终给出的消防站位置的灵敏性做出估计是非常重要的。由于在最优点有▽f=0,我们不期望f在(1.7,2.7)附近有太大的变化。为得到f关于最优点附近的(x，y)的灵敏性的一个具体的结果，我们将x，y的范围改为1.5le;xle;2，2.5le;yle;3, f改为一f,再一次运行随机搜索程序。取N=100，得到f在这个区域的最大值约为6.49分钟，或者说大约比观察到的最优时间长0.03分钟。这对在此边长半英里的正方形区域内哪一点设置消防站的实际应用不会有什么影响。
上述例子中采用的随机搜索方法虽然简单，但较慢。对一些要求更高精度的问题，则不适于采用这一方法。如果涉及的函数像例3.2中的目标函数一样复杂，用这种方法很难求得精确的解。更精确、更有效地求解多变量函数的整体最优化问题的方法绝大多数都以梯度为基础。对我们下面讨论的例子，由于梯度很容易计算，用这些方法更容易处理。
例3.3一家草坪家具的生产厂生产两种草坪椅。一种是木架的，一种是铝管架的。木架椅的生产价格为每把18美元，铝管椅为每把10美元。在产品出售的市场上，被售出的数量依赖于价格。据估计，为每天欲售出x把木架椅和y把铝管椅，木架椅的出售价格不能超过10 31 1.3 美元/把，铝管椅的出售价格不能超过5 15 0.8 美元/把。求最优的生产量。
目标是生产水准的可行集合xge;0, yge;0上对利润函数z=f(x, y)(美元/天)求最大值。这里
z = x(10 31 1.3 ) - 18x
（3-17）
y(5 15 0.8 ) - 10y。
下图给出了f的图像。图像显示f有一个唯一的达极大值的内点，此点满足▽f=0。图3-12画出了f的水平集图。由图可见，最大值出现在x=5, y=6附近。我们计算梯度▽f(x, y)=(dz/dx, dz/dy), 得到
在区域0le;xle;10，0le;yle;10，上应用N=1000个点的随机搜索算法，得到生产水准为每天生产x=4.8，y=5.9把椅子时可达每天52.06美元的最大利润。为得到最优值点的一个更精确的数值近似解，我们用多变量函数的牛顿法来求解梯度方程▽f=0。下图给出了两个变量的牛顿法算法。
在问题中，有
F（x,y）=15.5 -8 1.3 -0.064
G（x,y）=9 -5 0.8 -0.26 ，
从而计算出
取x(0)=5,y(0)=5,用两个变量的牛顿法的计算机程序进行N=10次迭代求解，得到
x=4.68959,y=5.85199作为所求根的近似值。为保证解的可靠性，再取N=15计算一次。讲结果带入到（3-17）式中，得到z=52.0727。因此，草坪椅问题的最优解为：每天生产4.69把木架椅、5.85把铝管椅，可得到每天52.07美元的利润。
与单变量情况相同，求方程组的数值近似解也是一个两步过程。首先要用一个全局方法估计出根的位置。如果只有两个变量，可以采用图像法，但对大多数问题则需要采用某个数值方法(如随机搜索法)。也可以采用一些较复杂的全局算法，它们通常都适用于某类特殊的问题，下步我们要用一 个快 速的局部方法来求高精确度的解，所求出的解的可靠性要通过对能够控制精度的参数进行灵敏性分析，或将数值解带回到原始的方程组中来验证。牛顿法是一个需要计算偏导数的非常快的局部方法。还有许名对偏导数做近似的改进牛顿法，可以参见参考文献。大多数电子数据表格软件和计算机代数系统都有多变量方程的求解工具，在大多数数值分析软件的库雨数和工具包中也有相应的求解工具。它们的使用都要从用一个全局方法对根的位置做出初始估计开始，然后用求解工具求出解，并照常对解加以验证。不要仅仅输人方程组，用工具求解后就接受它给出的解，这样可能会导致严重的误差许多电子数据表格软件、计算机代数系统及数值分析软件包都具有多变量数值最优化工具，通常其程序都采用基于对导数进行数值逼近的变形的牛顿法。对这些程序我们也有同样的建议:首先采用一个全局方法估计最优解的近似值，然后用数值最优化工具求解，最后对参数的容许值进行灵敏性分析，以保证结果的正确。
有约束的多变量最优化问题的求解更加困难，在某些情况下，最优解出现在可行集合的内部，从而我们可将问题看作无约束的情况，当最优解出现在边界上时，情况会更为复杂。对这类问题没有简单的、一般有效的计算方法。现有的方法只适用于一些具有特定性质的特殊类型的问题。我们会在下一节中讨论其中最重要的问题。
线性规划
有约束的多变量最优化问题通常总是难以求解的。人们研究了许多计算方法来处理一些特殊类型的多变量最优化问题，但仍缺乏较好的一般性的方法，即使是非常复杂的一般性方法也不存在。讨论这类问题的新的计算方法的研究领域称为非线性规划，这是个非常活跃的领域。
最简单的一类有约束的多变量最优化问题的目标函数和约束函数都是线性的，对这类问题的计算方法的研究称为线性规划。线性规划的软件包非常普及，并且经常被应用于制造业、投资、农业、运输和政府机构。典型的大规模问题包括数千个决策变量和数千个约束。在许多有资料可查的事例中，基于线性规划模型的运筹分析节约了数百万美元的资金。详细的资料可以在运筹学和管理学的文献中找到。
例3.4 一个家庭农场有625英亩的土地可以用来种植农作物。这个家庭考虑种植的农作物有玉米、小麦和燕麦。预计可以有1000英亩-英尺的灌溉用水，农场工人每周可以投入的工作时间为300小时。其他的数据在表3-2中给出。为获得最大收益，每种作物应该各种植多少？
表3-2 例3.4中农场问题的有关数据
我们采用五步方法。第一步的结果显示在图3-14中。第二步为选择建模方法。我们用线性规划模型来处理这个问题。
第三步是将线性规划模型表示为标准形式。在我们的问题中，决策变量为每种作物种植的英亩数为 ， ， 。我们要在集合
及 ge;0， ge;0， ge;0上对总收益y=400 200 250 求最大值。
第四步为求解问题。我们用由Linus Schrage所写的单纯形法计算机执行程序LINDO来求解。第四步的结果表示在图3-15中。最优解为Z=162500， = 187.5，
=437.5， =0。由于第二行与第四行的松驰变量为零，所以第个和第三个约束为关键约束。而第三行的松驰变量等于62.5,因此第二个约束条件不是关键的。
第五步为回答问题。问题为每种作物应该各种植多少。最优的方案为种玉米187.5英亩，种小麦437.5 英亩，不种燕麦。这样可以得到162500美元的收益。我们求出的最优的作物种植方案用光了625英亩的土地和1000英亩-英尺的灌溉用水，但在可用的每周300人-小时的劳力中只用掉了237.5。这样每周有62.5人-小时可以用于其他可获利的工作或空闲下来。
我们的灵敏性分析首先从考虑可用的灌溉用水量开始。这个量会由于降水和温度而改变，这会影响农场的蓄水池的水量。还可能从附近的农场购买额外的灌溉用水。图3-16显示了增加1英亩-英尺的灌溉水量对最优解的影响。现在我们可以多种半英亩的玉米(可获利更多的作物),而且还节约了一点劳力(每周0.3人-小时)。净收益增加了100美元。
这100美元是该资源的影子价格(灌溉用水)。农场会愿意以不超过100美元每英亩-英尺的价格购买额外的灌溉用水。另方面，农场不会愿意以低于100美元每英亩-英尺的价格出让自己拥有的灌溉用水。在图3-15中，三种资源(水、劳力和土地)的影子价格称为对偶价格。它们列在相应的松弛变量旁边。增加1英亩的土地的价值为100美元，额外增加劳力的价值为零，因为劳力已经是过剩的了。种植每种作物能够获得的每英亩的收益会随着气候和市场变化.图3-17显示了玉米收益的少量提高对最优解的影响。这不会影响决策变量x1，x2 和x3(每种作物的种植数量)的最优取值.总的收益当然会增加，增加量为50x1=9375美元.影子价格的改变也是值得注意的，由于玉米的收益提高，水的价值更高了。(虽然水和土地约束都是关键的，但水的约束限制了我们种植更多的玉米来取代小麦。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[426873]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
