数模论坛

 找回密码
 注-册-帐-号
搜索
热搜: 活动 交友 discuz
查看: 11453|回复: 5

数学专业英语-Linear Programming

[复制链接]
发表于 2004-5-6 09:36:22 | 显示全部楼层 |阅读模式
< ><FONT face="Times New Roman"><FONT size=3>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.</FONT></FONT></P>
< ><FONT face="Times New Roman" size=3>The following is a typical linear programming problem:</FONT></P>
< ><FONT face="Times New Roman" size=3>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?</FONT></P>
<P ><FONT face="Times New Roman" size=3>This problem is discussed in detail in Supplementary Reading Material Lesson 14.</FONT></P>
<P ><FONT face="Times New Roman" size=3>Since mathematical models in linear programming problems consist of linear inequalities, the next section is devoted to such inequalities.</FONT></P>
<P ><FONT face="Times New Roman" size=3>Recall that the linear equation <I >lx+my+n=0</I> represents a straight line in a plane. Every solution (<I >x,y</I>) of the equation <I >lx+my+n=0</I> is a point on this line, and vice versa.</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">An inequality that is obtained from the linear equation <I >lx+my+n=0</I> by replacing the equality sign “=” by an inequality sign &lt; (less than), </FONT>≤ <FONT face="Times New Roman">(less than or equal to), &gt; (greater than), or </FONT>≥<FONT face="Times New Roman"> (greater than or equal to) is called a linear inequality in two variables <I >x</I> and <I >y</I>. Thus <I >lx+my+n</I></FONT><I >≤<FONT face="Times New Roman">0, lx+my+n</FONT></I><I >≥<FONT face="Times New Roman">0</FONT></I><FONT face="Times New Roman"> are all linear liequalities. A solution of a linear inequality is an ordered pair (<I >x,y</I>) of numbers <I >x</I> and <I >y</I> for which the inequality is true.</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>EXAMPLE 1 Graph the solution set of the pair of inequalities</FONT></P>
<P  align=center><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><FONT face="Times New Roman" size=3></FONT></v:imagedata></v:shape><FONT face="Times New Roman" size=3> </FONT><v:shape><FONT face="Times New Roman"><FONT size=3> <v:imagedata></v:imagedata></FONT></FONT></v:shape></P>
<P ><v:shape><FONT face="Times New Roman"><FONT size=3><v:imagedata></v:imagedata><v:textbox style="mso-next-textbox: #_x0000_s1026"></v:textbox><w:wrap type="tight"></w:wrap></FONT></FONT></v:shape><FONT size=3><FONT face="Times New Roman">SOLUTION Let A be the solution set of the inequality x+y-7</FONT>≤<FONT face="Times New Roman">0 and B be that of the inequality x-3y +6 </FONT>≥<FONT face="Times New Roman">0 .Then A</FONT>∩<FONT face="Times New Roman">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.</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>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.</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>    EXAMPLE 2 Maximize the function f(x,y)=5x+7y subject to the constraints</FONT></FONT></P>
<P  align=center><FONT size=3><FONT face="Times New Roman">x</FONT>≥<FONT face="Times New Roman">0 y</FONT>≥<FONT face="Times New Roman">0</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">x+y-7</FONT>≤<FONT face="Times New Roman">0</FONT></FONT></P>
<P  align=center><FONT size=3><FONT face="Times New Roman">2x-3y+6</FONT>≥<FONT face="Times New Roman">0</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    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) satisf</FONT>ies the given conditions; so are (1,2) and (4,3).<p></p></FONT></P>
<P ><FONT size=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.<p></p></FONT></P>
<P ><FONT size=3>    Since the constraints x ≥<FONT face="Times New Roman">0 and y </FONT>≥<FONT face="Times New Roman">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.</FONT></FONT></P>
<P  align=center><v:shape><v:imagedata><FONT face="Times New Roman" size=3></FONT></v:imagedata></v:shape></P>
<P  align=center><FONT face="Times New Roman" size=3>Fig.2.</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    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.</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    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).</FONT></FONT></P>
<P  align=center><v:shape><v:imagedata><FONT face="Times New Roman" size=3></FONT></v:imagedata></v:shape></P>
<P  align=center><FONT face="Times New Roman" size=3>Fig.3.</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    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).</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    The following celebrated theorem indicates that it was not accidental.</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    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.</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    We now summarize the procedure for solving a linear programming problem:</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>1.</FONT>       <FONT size=3>Graph the polygonal region determined by the constraints.</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>2.</FONT>       <FONT size=3>Find the coordinates of the corner points of the polygon.</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>3.</FONT>       <FONT size=3>Evaluate the objective function at the corner points.</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>4.</FONT>       <FONT size=3>Identify the corner point at which the function has an optimal value.</FONT></FONT></P>
 楼主| 发表于 2004-5-6 09:36:39 | 显示全部楼层
< 0cm 0cm 0pt; TEXT-ALIGN: center" align=center><B><FONT face="Times New Roman">Vocabulary</FONT></B></P>< 0cm 0cm 0pt"><FONT face="Times New Roman">linear programming   </FONT>线形规划<FONT face="Times New Roman">                        quadrant   </FONT>象限</P>< 0cm 0cm 0pt"><FONT face="Times New Roman">objective function   </FONT>目标函数<FONT face="Times New Roman">                          convex   </FONT>凸的</P><P 0cm 0cm 0pt"><FONT face="Times New Roman">constraints   </FONT>限制条件,约束条件<FONT face="Times New Roman">                      convex set   </FONT>凸集</P><P 0cm 0cm 0pt"><FONT face="Times New Roman">feaseble solution   </FONT>容许解,可行解<FONT face="Times New Roman">                     corner point   </FONT>偶角点</P><P 0cm 0cm 0pt"><FONT face="Times New Roman">optimal solution   </FONT>最优解<FONT face="Times New Roman">                             simplex method   </FONT>单纯形法</P>
 楼主| 发表于 2004-5-6 09:36:49 | 显示全部楼层
< 0cm 0cm 0pt; TEXT-ALIGN: center" align=center><B><FONT face="Times New Roman">Notes</FONT></B></P>< 0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40"><FONT face="Times New Roman">1.       A Yale economist, a Stanford mathematician </FONT>这里<FONT face="Times New Roman">Yale Stanford </FONT>是指美国两间著名的私立大学:耶鲁大学和斯坦福大学,这两间大学分别位于康涅狄格州(<FONT face="Times New Roman">Connecticut</FONT>)和加里福尼亚州<FONT face="Times New Roman">(California)</FONT></P>< 0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40"><FONT face="Times New Roman">2.       subject to some lincar conditions </FONT>解作“在某些线形条件的限制下”。试比较下面各词组在用法上的异同:<FONT face="Times New Roman"> subject to; under the condition(s) of; satisfying the condition(s).</FONT></P><P 0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40"><FONT face="Times New Roman">3.       celebrated theorem </FONT>意思为“著名定理”。</P><P 0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40"><FONT face="Times New Roman">4.       Since…it follows…</FONT>与<FONT face="Times New Roman">Notice…it follow…</FONT>都是数学中常用的句型,以表达“根据什么,可得什么”这一意思,请参看附录<FONT face="Times New Roman">III</FONT>。</P><P 0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l11 level1 lfo40"><FONT face="Times New Roman">5.       </FONT>本课多次用到<FONT face="Times New Roman">recall, observe, notice, remember</FONT>等词,用以提醒读者一些已知的事实或定理,读者可从这些例句中体会这些词的用法。请参看附录<FONT face="Times New Roman">III</FONT>。</P>
 楼主| 发表于 2004-5-6 09:37:00 | 显示全部楼层
< 0cm 0cm 0pt; TEXT-ALIGN: center" align=center><B><FONT face="Times New Roman">Exercise</FONT></B></P>< 0cm 0cm 0pt"><FONT face="Times New Roman">I.Translate the following passage into Chinesre:</FONT></P>< 0cm 0cm 0pt"><FONT face="Times New Roman">    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.</FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> <p></p></FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman">II.Read the content of this lesson carefully and complete the following sentences:</FONT></P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l44 level1 lfo42"><FONT face="Times New Roman">1.       Linear programming problems consist of<U>                                                    <p></p></U></FONT></P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l44 level1 lfo42"><FONT face="Times New Roman">2.       The set of feasible solutions of a linear programming problem is<U>                                 </U>                </FONT></P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l44 level1 lfo42"><FONT face="Times New Roman">3.       A polygonal region is a region bounded by<U>                                                   </U> </FONT></P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l44 level1 lfo42"><FONT face="Times New Roman">4.       A convex set in a plane is<U>                                                                <p></p></U></FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> <p></p></FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman">III.Translate the following sentences into English:</FONT></P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l30 level1 lfo43"><FONT face="Times New Roman">1.       </FONT>点<FONT face="Times New Roman">(3,4)</FONT>是两条直线<FONT face="Times New Roman">x+y-7=0</FONT>和<FONT face="Times New Roman">2x-3y+6=0</FONT>的交点。</P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l30 level1 lfo43"><FONT face="Times New Roman">2.       (3,4)</FONT>是例<FONT face="Times New Roman">2</FONT>的最优解。</P><P 0cm 0cm 0pt 39.75pt; TEXT-INDENT: -18pt; tab-stops: list 39.75pt; mso-list: l30 level1 lfo43"><FONT face="Times New Roman">3.       </FONT>计算目标函数在偶角点处的值,然后进行比较,求出目标函数的最大值或最小值。<FONT face="Times New Roman"> </FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> <p></p></FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> <p></p></FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> <p></p></FONT></P>
发表于 2005-10-26 19:02:16 | 显示全部楼层
<>请问动态规划,目标规划,以及非线性规划是怎么讲得,急需,谢谢!</P>[em06]
发表于 2005-10-26 19:06:59 | 显示全部楼层
<>我的qq是24851565,告诉我在哪找这些东西好吗?谢谢</P>
您需要登录后才可以回帖 登录 | 注-册-帐-号

本版积分规则

小黑屋|手机版|Archiver|数学建模网 ( 湘ICP备11011602号 )

GMT+8, 2024-3-28 21:28 , Processed in 0.054044 second(s), 19 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表