数学专业英语－Linear Programming

yunjiang · 发表于 2004-5-6 09:36:22

<

>Linear Programming is a relatively new branch of mathematics.The cornerstone of this exciting field was laid independently bu Leonid V. Kantorovich,a Russian mathematician,and by Tjalling C,Koopmans, a Yale economist,and George D. Dantzig,a Stanford mathematician. Kantorovich’s pioneering work was motivated by a production-scheduling problem suggested by the Central Laboratory of the Leningrad Plywood Trust in the late 1930’s. The development in the United States was influenced by the scientific need in World War II to solve logistic military problems, such as deploying aircraft and submarines at strategic positions and airlifting supplies and personnel.
<

>The following is a typical linear programming problem:
<

>A manufacturing company makes two types of television sets: one is black and white and the other is color. The company has resources to make at most 300 sets a week. It takes $180 to make a black and white set and $270 to make a color set. The company does not want to spend more than $64,800 a week to make television sets. If they make a profit of $170 per black and white set and $225 per color set, how many sets of each type should the company make to have a maximum profit?
This problem is discussed in detail in Supplementary Reading Material Lesson 14.
Since mathematical models in linear programming problems consist of linear inequalities, the next section is devoted to such inequalities.
Recall that the linear equation lx+my+n=0 represents a straight line in a plane. Every solution (x,y) of the equation lx+my+n=0 is a point on this line, and vice versa.
An inequality that is obtained from the linear equation lx+my+n=0 by replacing the equality sign “=” by an inequality sign < (less than), ≤ (less than or equal to), > (greater than), or ≥ (greater than or equal to) is called a linear inequality in two variables x and y. Thus lx+my+n≤0, lx+my+n≥0 are all linear liequalities. A solution of a linear inequality is an ordered pair (x,y) of numbers x and y for which the inequality is true.
EXAMPLE 1 Graph the solution set of the pair of inequalities
<v:shapetype><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path connecttype="rect" gradientshapeok="t" extrusionok="f"></v:path><lock aspectratio="t" v:ext="edit"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata></v:shape> <v:shape> <v:imagedata></v:imagedata></v:shape>
<v:shape><v:imagedata></v:imagedata><v:textbox style="mso-next-textbox: #_x0000_s1026"></v:textbox><w:wrap type="tight"></w:wrap></v:shape>SOLUTION Let A be the solution set of the inequality x+y-7≤0 and B be that of the inequality x-3y +6 ≥0 .Then A∩B is the solution set of the given pair of inequalities. Set A is represented by the region shaded with horizontal lines and set B by the region shaded with vertical lines in Fig.1. Therefore the crossed-hatched region represents the solution set of the given pair of inequalities. Observe that the point of intersection (3.4) of the two lines is in the solution set.
Generally speaking, linear programming problems consist of finding the maximum value or minimum value of a linear function, called the objective function, subject to some linear conditions, called constraints. For example, we may want to maximize the production or profit of a company or to maximize the number of airplanes that can land at or take off from an airport during peak hours; or we may want to minimize the cost of production or of transportation or to minimize grocery expenses while still meeting the recommended nutritional requirements, all subject to certain restrictions. Linear programming is a very useful tool that can effectively be applied to solve problems of this kind, as illustrated by the following example.
 EXAMPLE 2 Maximize the function f(x,y)=5x+7y subject to the constraints
x≥0 y≥0
x+y-7≤0
2x-3y+6≥0
 SOLUTION First we find the set of all possible pairs(x,y) of numbers that satisfy all four inequalities. Such a solution is called a feasible sulution of the problem. For example, (0,0) is a feasible solution since (0,0) satisfies the given conditions; so are (1,2) and (4,3).
 Secondly, we want to pick the feasible solution for which the given function f (x,y) is a maximum or minimum (maximum in this case). Such a feasible solution is called an optimal solution.
 Since the constraints x ≥0 and y ≥0 restrict us to the first quadrant, it follows from example 1 that the given constraints define the polygonal region bounded by the lines x=0, y=0,x+y-7=0, and 2x-3y+6=0, as shown in Fig.2.
<v:shape><v:imagedata></v:imagedata></v:shape>
Fig.2.
 Observe that if there are no conditions on the values of x and y, then the function f can take on any desired value. But recall that our goal is to determine the largest value of f (x,y)=5x+7y where the values of x and y are restricted by the given constraints: that is, we must locate that point (x,y) in the polygonal region OABC at which the expression 5x+7y has the maximum possible value.
 With this in mind, let us consider the equation 5x+7y=C, where C is any number. This equation represents a family of parallel lines. Several members of this family, corresponding to different values of C, are exhibited in Fig.3. Notice that as the line 5x+7y=C moves up through the polygonal region OABC, the value of C increases steadily. It follows from the figure that the line 5x+7y=43 has a singular position in the family of lines 5x+7y=C. It is the line farthest from the origin that still passes through the set of feasible solutions. It yields the largest value of C: 43.(Remember, we are not interested in what happens outside the region OABC) Thus the largest value of the function f(x,y)=5x+7y subject to the condition that the point (x,y) must belong to the region OABC is 43; clearly this maximum value occurs at the point B(3,4).
<v:shape><v:imagedata></v:imagedata></v:shape>
Fig.3.
 Consider the polygonal region OABC in Fig.3. This shaded region has the property that the line segment PQ joining any two points P and Q in the region lies entirely within the region. Such a set of points in a plane is called a convex set. An interesting observation about example 2 is that the maximum value of the objective function f occurs at a corner point of the polygonal convex set OABC, the point B(3,4).
 The following celebrated theorem indicates that it was not accidental.
 THEOREM (Fundamental theorem of linear programming) A linear objective function f defined over a polygonal convex set attains a maximum (or minimum) value at a corner point of the set.
 We now summarize the procedure for solving a linear programming problem:
1. Graph the polygonal region determined by the constraints.
2. Find the coordinates of the corner points of the polygon.
3. Evaluate the objective function at the corner points.
4. Identify the corner point at which the function has an optimal value.

yunjiang · 发表于 2004-5-6 09:36:39

<

0cm 0cm 0pt; TEXT-ALIGN: center" align=center>Vocabulary<

0cm 0cm 0pt">linear programming 线形规划 quadrant 象限<

0cm 0cm 0pt">objective function 目标函数 convex 凸的constraints 限制条件，约束条件 convex set 凸集feaseble solution 容许解，可行解 corner point 偶角点optimal solution 最优解 simplex method 单纯形法

yunjiang · 发表于 2004-5-6 09:36:49

<

0cm 0cm 0pt; TEXT-ALIGN: center" align=center>Notes<

0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40">1. A Yale economist, a Stanford mathematician 这里Yale Stanford 是指美国两间著名的私立大学：耶鲁大学和斯坦福大学，这两间大学分别位于康涅狄格州（Connecticut）和加里福尼亚州(California)<

0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40">2. subject to some lincar conditions 解作“在某些线形条件的限制下”。试比较下面各词组在用法上的异同： subject to; under the condition(s) of; satisfying the condition(s).3. celebrated theorem 意思为“著名定理”。4. Since…it follows…与Notice…it follow…都是数学中常用的句型，以表达“根据什么，可得什么”这一意思，请参看附录III。5. 本课多次用到recall, observe, notice, remember等词，用以提醒读者一些已知的事实或定理，读者可从这些例句中体会这些词的用法。请参看附录III。

yunjiang · 发表于 2004-5-6 09:37:00

<

0cm 0cm 0pt; TEXT-ALIGN: center" align=center>Exercise<

0cm 0cm 0pt">I.Translate the following passage into Chinesre:<

0cm 0cm 0pt"> Although satisfactory for two-variable linear programs, the corner-point method is not computationally effective when extended beyond three-variable situations. Its usefulness is restricted to introducing the general idea of linear programming, and the need for more poweful solution techniques is obvious. The simplex method, devised by George Dantzig in the late 1940’s, was, central to the explosion in linear programming applications that occurred in the 1950’s and 1960’s. Although more powerful techniques exist for solving special problems, the simplex method is still the most computationally effective general method available for solving the widest variety of linear programming problems. II.Read the content of this lesson carefully and complete the following sentences:1. Linear programming problems consist of 2. The set of feasible solutions of a linear programming problem is 3. A polygonal region is a region bounded by 4. A convex set in a plane is III.Translate the following sentences into English:1. 点(3,4)是两条直线x+y-7=0和2x-3y+6=0的交点。2. (3,4)是例2的最优解。3. 计算目标函数在偶角点处的值，然后进行比较，求出目标函数的最大值或最小值。

xiaojuan · 发表于 2005-10-26 19:02:16

<

>请问动态规划，目标规划，以及非线性规划是怎么讲得，急需，谢谢！[em06]

xiaojuan · 发表于 2005-10-26 19:06:59

<

>我的qq是24851565，告诉我在哪找这些东西好吗？谢谢

		自动登录	找回密码
密码			注-册-帐-号