7.11 线性方案拟订
Section outline
-
Linear Programming
::线线性规划A lot of interesting real-world problems can be solved with systems of linear inequalities.
::许多有趣的现实世界问题可以通过线性不平等制度来解决。For example, you go to your favorite restaurant and you want to be served by your best friend who happens to work there. However, your friend only waits tables in a certain region of the restaurant. The restaurant is also known for its great views, so you want to sit in a certain area of the restaurant that offers a good view. Solving a system of linear inequalities will allow you to find the area in the restaurant where you can sit to get the best view and be served by your friend.
::例如,去你最喜欢的餐厅,然后想得到碰巧在那里工作的你最好的朋友的服务。然而,你的朋友只在餐厅的某个地区等候餐桌。餐厅也以其美观著称,所以你想坐在餐厅的某个地区,提供良好的视野。解决线性不平等制度可以让您在餐厅找到一个地区,在那里您可以坐下来得到最好的视野并得到朋友的服务。Often, systems of linear inequalities deal with problems where you are trying to find the best possible situation given a set of constraints. Most of these application problems fall in a category called linear programming problems.
::线性不平等制度往往涉及一些问题,在遇到一系列限制的情况下,你试图找到最佳可能的情况,而其中大多数应用问题属于称为线性编程问题一类。Linear programming is the process of taking various linear inequalities relating to some situation, and finding the best possible value under those conditions. A typical example would be taking the limitations of materials and labor at a factory, then determining the best production levels for maximal profits under those conditions. These kinds of problems are used every day in the organization and allocation of resources. These real-life systems can have dozens or hundreds of variables, or more. In this section, we’ll only work with the simple two- variable linear case.
::线性编程过程是针对某些情况采取各种线性不平等,并在这些条件下找到可能的最佳价值。 一个典型的例子就是对工厂材料和劳动力的限制,然后确定这些条件下最大利润的最佳生产水平。 这些问题每天都在组织与分配资源中被使用。 这些现实生活系统可以有几十个或数百个变量,或者更多。 在这一部分,我们只能处理简单的两个可变线性案例。The general process is to:
::一般程序是:-
Graph the inequalities (called
constraints
) to form a bounded area on the
coordinate plane
(called
the feasibility region
).
::将不平等(所谓的限制)图解成坐标平面(称为可行性区域)上的封闭区。 -
Figure out the
coordinates
of the corners (or vertices) of this feasibility region by solving the
system of equations
that applies to each of the
intersection
points.
::通过解决适用于每个交叉点的方程系统,找出这一可行性区域的角(或顶点)坐标。 -
Test these corner points in the
formula
(called the
optimization
equation
) for which you're trying to find the
maximum
or
minimum
value.
::在公式中测试这些角点(称为优化方程),您正在为此尝试找到最大值或最小值。
Finding Maximum and Minimum Values
::查找最大值和最低值If , find the maximum and minimum values of given these constraints:
::如果z=2x+5y,根据这些限制,发现最大值和最小值为z:
::2 - y124x+3y0x- y6First, we need to find the solution to this system of linear inequalities by graphing and shading appropriately. To graph the inequalities, we rewrite them in slope-intercept form :
::首先,我们需要找到解决这一线性不平等系统的办法,通过绘制图表和适当遮盖阴影。为了绘制不平等图,我们用斜坡界面重写:
::y2x- 12y 43xyxxx-6These three linear inequalities are called the constraints , and here is their graph:
::这三种线性不平等被称为制约,The shaded region in the graph is called the feasibility region . All possible solutions to the system occur in that region; now we must try to find the maximum and minimum values of the variable within that region. In other words, which values of and within the feasibility region will give us the greatest and smallest overall values for the expression ?
::图形中的阴暗区域被称为“可行性区域 ” 。 该系统的所有可能解决方案都发生在该地区; 现在我们必须尝试找到该区域内变量z的最大值和最小值。 换句话说, 可行性区域内的 x 值和 y 值将为表达 2x+5 提供最大和最小的总值 ?Fortunately, we don’t have to test every point in the region to find that out. It just so happens that the minimum or maximum value of the optimization equation in a linear system like this will always be found at one of the vertices (the corners) of the feasibility region; we just have to figure out which vertices. So for each vertex—each point where two of the lines on the graph cross—we need to solve the system of just those two equations, and then find the value of at that point.
::幸运的是,我们不必测试这个区域的每一点才能发现这一点。 类似这样的线性系统中优化方程式的最小值或最大值总是在可行性区域的一个顶端(角)发现;我们只需要弄清楚哪个顶端。 因此,对于每个顶端点 — — 图形十字路口上两条线的每个点 — — 我们需要解决这两个方程式的系统,然后在那个点找到z值。The first system consists of the equations and . We can solve this system by substitution:
::第一个系统由 y=2x-12 和 y43x 等式组成。 我们可以通过替换解决这个系统 :
::-43x=2x-124x=6x-3610x36xx=3.6y=2x-12y=2(3.6)-12y4.8The lines intersect at the point (3.6, -4.8).
::点( 3.6, - 4.8) 上的线交叉。The second system consists of the equations and . Solving this system by substitution:
::第二个系统由y=2x-12和y=x-6等方程式组成。
::x-6=2x- 126=xx=6y=x-6y=6- 6_ 6_ y=0The lines intersect at the point (6, 0).
::点的线条交叉( 6, 0) 。The third system consists of the equations and . Solving this system by substitution:
::第三个系统由y43x和y=x-6等方程组成。
::x-64x33x-184x7x=184x7x18}x=2.57y=x-664y=2.57-663.43The lines intersect at the point (2.57, -3.43).
::点的线条交叉(2.57,-3.43)。So now we have three different points that might give us the maximum and minimum values for . To find out which ones actually do give the maximum and minimum values, we can plug the points into the optimization equation .
::所以现在我们有三个不同的点, 可能给我们 z 的最大值和最小值。 要找出哪些真正给出最大值和最小值, 我们可以将这些点插入到 z=2x+5y 的优化方程式中。When we plug in (3.6, -4.8), we get .
::当我们插入( 3.6, -4.8) 我们得到z=2( 3.6)+5( - 4.8)\\\16.8。When we plug in (6, 0), we get .
::当我们插入(6,0)时,我们得到z=2(6)+5(0)=12。When we plug in (2.57, -3.43), we get .
::当我们插入时 (2.57, - 3.43) 我们得到z=2(2.57)+5(- 3.43)\\\\12.01。So we can see that the point (6, 0) gives us the maximum possible value for and the point (3.6, –4.8) gives us the minimum value.
::因此,我们可以看到,点(6,0)给了我们z的最大可能值,点(3.6,-4.8)给了我们最小值。In the previous example, we learned how to apply the method of linear programming in the abstract. In the next example, we’ll look at a real-life application.
::在上一个例子中,我们学会了如何抽象地应用线性编程方法。 在下一个例子中,我们将审视现实生活中的应用。Real-World Application: Stock Market
::现实世界应用:股票市场You have $10,000 to invest, and three different funds to choose from. The municipal bond fund has a 5% return, the local bank's CDs have a 7% return, and a high-risk account has an expected 10% return. To minimize risk, you decide not to invest any more than $1,000 in the high-risk account. For tax reasons, you need to invest at least three times as much in the municipal bonds as in the bank CDs. What’s the best way to distribute your money given these constraints?
::您有1万美元的投资,三个不同的基金可以选择。 市政债券基金回报率为5%,当地银行的CD回报率为7%,高风险账户回报率预计为10 % 。 为了降低风险,您决定不在高风险账户投资超过1 000美元。 出于税收原因,您需要在市债券上投资至少是银行CD的三倍。 面对这些限制,分配您资金的最佳方式是什么?Let’s define our variables:
::让我们定义我们的变数:is the amount of money invested in the municipal bond at 5% return
::x 是收益5%的市政债券投资金额。is the amount of money invested in the bank’s CD at 7% return
::y 是以7%的回报率投入银行CD的金额。is the amount of money invested in the high-risk account at 10% return
::10000-x-y 投资到高风险账户的资金数额,回报率为10%is the total interest returned from all the investments, so or . This is the amount that we are trying to maximize. Our goal is to find the values of and that maximizes the value of .
::z 是所有投资的回报总利息, 所以 z=. 05x+. 07y+1( 10000- x-y) 或 z= 1000- 0.05x- 0.03y。 这就是我们试图最大化的金额。 我们的目标是找到 x 和 y 的值, 使 z 的值最大化 。Now, let’s write inequalities for the constraints :
::现在,让我们来写一下这些限制的不平等:You decide not to invest more than $1000 in the high-risk account—that means:
::你决定不在高风险账户投资超过1000美元, 这意味着:
::10000-x-y1000You need to invest at least three times as much in the municipal bonds as in the bank CDs—that means:
::您需要至少将市级债券投资三倍于银行CD,这意味着:
::3yxAlso, you can’t invest less than zero dollars in each account, so:
::而且,你不能在每个账户投资不到零美元,所以:
::x0y010000-x-y_0To summarize, we must maximize the expression using the constraints:
::简言之,我们必须使用下列限制,尽量扩大z=1000-.05x-.03y的表达方式:
::10000-x-y10000-y10000-9900-x3yxxx3x3x}Or 斜坡截取形式:x0-0y0-0y0N010000-x-y0-0y1000-x-y1000-xxStep 1: Find the solution region to the set of inequalities by graphing each line and shading appropriately. The following figure shows the overlapping region:
::第1步:通过绘制每一行的图表并适当遮盖阴影,找到一套不平等的解决办法区域。The purple region is the feasibility region where all the possible solutions can occur.
::紫色区域是所有可能的解决办法都能出现的可行性区域。Step 2: Next we need to find the corner points of the feasibility region. Notice that there are four corners. To find their coordinates, we must pair up the relevant equations and solve each resulting system.
::步骤2: 下一步我们需要找到可行性区域的角点。 注意有四个角。 要找到它们的坐标, 我们必须对齐相关的方程式, 并解决每个结果系统 。System 1:
::系统1:
::y=x3y=1000-xSubstitute the first equation into the second equation:
::将第一个方程替换为第二个方程:
::x3=1000- xx=30000- 3x4x=30000_x@x=7500y=x3_ y=750000_y=2500The intersection point is (7500, 2500).
::交叉点是(7500,2500)System 2:
::系统2:
::y=x3y=900-xSubstitute the first equation into the second equation:
::将第一个方程替换为第二个方程:
::x3=9000 -xx=27000-3x4x=27000}*x=6750y=x3}*y=67503}*y=67503}*y=2250The intersection point is (6750, 2250).
::交叉点是(6750,2250)。System 3:
::系统3:
::y=0y=1000-xThe intersection point is (10000, 0).
::交叉点是 (10,000,0) 。System 4:
::系统4:
::y=0y=900-xThe intersection point is (9000, 0).
::交叉点是 (9000,0) 。Step 3: In order to find the maximum value for , we need to plug all the intersection points into the equation for and find which one yields the largest number.
::第3步:为了找到z的最大值,我们需要将所有交叉点插入z方程式中,并找出一个产生最大值。(7500, 2500):
:7500, 2500: z=1000-0.05( 7500)- 0.03( 2500)=550)
(6750, 2250):
:6750,2250):z=1000-0.05(6750)-0.03(2250)=595
(10000, 0):
:10000,0):z=1000-0.05(1000-0.03(0)=500)
(9000, 0):
:9000,0):z=1000-0.05(900-0.003(0)=550)
The maximum return on the investment of $595 occurs at the point (6750, 2250). This means that:
::投资的最大收益为595美元(6750美元、2250美元)。$6,750 is invested in the municipal bonds.
::市政债券投资6 750美元。$2,250 is invested in the bank CDs.
::2 250美元投资在银行光盘上。$1,000 is invested in the high-risk account.
::1 000美元投资于高风险账户。Real-World Application: Revenue
::实际世界应用:收入James is trying to expand his pastry business to include cupcakes and personal cakes. He has 40 hours available to decorate the new items and can use no more than 22 pounds of cake mix. Each personal cake requires 2 pounds of cake mix and 2 hours to decorate. Each cupcake order requires one pound of cake mix and 4 hours to decorate. If he can sell each personal cake for $14.99 and each cupcake order for $16.99, how many personal cakes and cupcake orders should James make to make the most revenue ?
::James试图扩大他的糕点业务,以包括蛋糕和个人蛋糕。他有40个小时可以装饰新的物品,并且不能使用超过22磅的蛋糕混合。每个个人蛋糕需要2磅的蛋糕混合和2小时的装饰。每个蛋糕订单需要1磅的蛋糕混合和4小时的装饰。如果他能卖出每个个人蛋糕14.99美元,每个蛋糕订单16.99美元,詹姆斯应该做多少个人蛋糕和蛋糕订单来赚取最大的收入?There are four inequalities in this situation. First, state the variables. Let the number of personal cakes and the number of cupcake orders .
::在此情况下,存在四种不平等。 首先, 说明变量。 让我们来说明个人蛋糕的数量和 c = 纸杯蛋糕订单的数量 。Translate this into a system of inequalities.
::将这一点转化为不平等制度。– This is the amount of available cake mix.
::2p+1c22 - 这是可用蛋糕组合的数量 。– This is the available time to decorate.
::2p+4c40—这是装饰的可用时间。– You cannot make negative personal cakes.
:掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声) (掌声(掌声) (掌声) (掌声) (掌声)
– You cannot make negative cupcake orders.
::- 你不能做负纸杯蛋糕订单。Now graph each inequality and determine the feasible region .
::现在绘制每一种不平等的图表,并确定可行的区域。The feasible region has four vertices: {(0, 0),(0, 10),(11, 0),(8, 6)}. According to our theorem , the optimization answer will only occur at one of these vertices.
::可行的区域有四个顶点:{( 0, 0, 10, 10, (11, 0, 8, 6 )}。 根据我们的理论, 优化答案只出现在其中的一个顶点上 。Write the optimization equation. How much of each type of order should James make to bring in the most revenue?
::写最优化方程式 詹姆斯应该做多少每类订单 才能带来最大的收入?
::14.99p+16.99c=最大收入Substitute each ordered pair to determine which makes the most money.
::替换每对定购的夫妇,以确定哪对最赚钱。To make the most revenue, James should make 8 personal cakes and 6 cupcake orders.
::为了赚取最大的收入 James应该做8个个人蛋糕 6个蛋糕订单Example
::示例示例示例示例Example 1
::例1Graph the solution to the following system:
::为以下系统绘制解决方案图:
::x- y 62y3x+17Solution:
::解决方案 :First we will rewrite the equations in slope-intercept form in order to graph them:
::首先,我们将重写以斜坡界面形式的方程式,以图示它们:Inequality 1
::不平等 1x- y_ 6Solve y.- yx- 6Subtraction x from each side. y>x+6Bultiply each side by - 1, 翻转不平等。Inequality 2
::不平等 22y3x+17 < solve for y.y3x+8.5 < divide each side by 2 by 2 < y.y3x+17 < solve for y.y32x+8.5 < divide each side.Graph each equation and shade accordingly:
::每个方程式图和阴影图如下:Review
::回顾Solve the following linear programming problems.
::解决以下线性编程问题。-
Given the following constraints, find the maximum and minimum values of
:
::鉴于以下限制,找到最大和最低值为zx+5y: x+3y0x-y03x-7y16。
Santa Claus is assigning elves to work an eight-hour shift making toy trucks. Apprentice elves draw a wage of five candy canes per hour worked, but can only make four trucks an hour. Senior elves can make six trucks an hour and are paid eight candy canes per hour. There’s only room for nine elves in the truck shop, and due to a candy-makers’ strike, Santa Claus can only pay out 480 candy canes for the whole 8-hour shift.
::圣诞老人正在指派精灵从事八小时的轮班工作,制造玩具卡车。 学徒精灵每小时工资为五只糖果杖,但每小时只能造四辆卡车。 高级精灵每小时可以制造六辆卡车,每小时8只糖果杖。 卡车店里只有9只精灵的房间,而且由于糖果制造商罢工,圣诞老人只能支付480只糖果杖的8小时轮班。-
How many senior elves and how many apprentice elves should work this shift to maximize the number of trucks that get made?
::有多少高级精灵和多少学徒精灵应该进行这一转变,以便最大限度地增加卡车数量? -
How many trucks will be made?
::将制造多少卡车? -
Just before the shift begins, the apprentice elves demand a wage increase; they insist on being paid seven candy canes an hour. Now how many apprentice elves and how many senior elves should Santa assign to this shift?
::在轮班开始之前,学徒精灵们要求加薪;他们坚持每小时付七根糖果。 现在,有多少学徒精灵和多少高级精灵应该由圣诞老人派到这一轮班? -
How many trucks will now get made, and how many candy canes will Santa have left over?
::现在有多少卡车能造出来? 圣诞老人还能留下多少只糖果杖?
In Adrian’s Furniture Shop, Adrian assembles both bookcases and TV cabinets. Each type of furniture takes her about the same time to assemble. She figures she has time to make at most 18 pieces of furniture by this Saturday. The materials for each bookcase cost her $20 and the materials for each TV stand costs her $45. She has $600 to spend on materials. Adrian makes a profit of $60 on each bookcase and a profit of $100 on each TV stand.
::在阿德里安的家具商店,阿德里安将书架和电视柜组装在一起,每类家具都与她在同一时间进行组装,她估计到本周六她最多有时间做18件家具,每个书架的材料花费她20美元,每个电视亭的材料花费她45美元。 她有600美元要花在材料上。 阿德里安在每个书架上赚60美元,每个电视亭赚100美元。-
Set up a system of inequalities. What
and
values do you get for the point where Adrian’s profit is maximized? Does this solution make sense in the real world?
::建立不平等体系。 对于Adrian利润最大化,你能得到什么价值? 这个解决方案在现实世界中是否有意义? -
What two possible real-world
values and what two possible real-world
values would be closest to the values in that solution?
::哪些两种可能的现实世界x-价值和哪些两种可能的现实世界y-价值最接近于该解决方案中的价值观? -
With two choices each for
and
, there are four possible combinations of
and
values. Of those four combinations, which ones actually fall within the feasibility region of the problem?
::x和y各有两个选择,有四种可能的x-和y-价值组合。在这四种组合中,哪些实际上属于问题的可行性区域? -
Which one of those feasible combinations seems like it would generate the most profit? Test out each one to confirm your guess. How much profit will Adrian make with that combination?
::这些可行的组合中,哪一种似乎能产生最大的利润?每个测试来证实你的猜测。Adrian用这种组合能赚到多少利润? -
Based on Adrian’s previous sales figures, she doesn’t think she can sell more than 8 TV stands. Now how many of each piece of furniture should she make, and what will her profit be?
::根据Adrian先前的销售数字,她认为她卖不出超过8台电视站。 现在,她应该制造多少家具,她能赚多少利润? -
Suppose Adrian is confident she can sell all the furniture she can make, but she doesn’t have room to display more than 7 bookcases in her shop. Now how many of each piece of furniture should she make, and what will her profit be?
::假设Adrian相信她能卖掉所有家具,但她没有空间在店里展示超过7个书架。 现在,她应该做多少件家具,她的利润会有多大? -
Here’s a “linear programming” problem on a line instead of a plane: Given the constraints
and
, maximize the value of
where
.
::这是一条线上的“线性编程”问题, 而不是平面上的问题:鉴于各种限制 x5 和 x2, y =x+3 的值最大化 y 的值。
Review (Answers)
::回顾(答复)Click to see the answer key or go to the Table of Contents and click on the Answer Key under the 'Other Versions' option.
::单击可查看答题键, 或转到目录中, 单击“ 其他版本” 选项下的答题键 。Texas Instruments Resources
::得克萨斯州工具资源In the CK-12 Texas Instruments Algebra I FlexBook® resource, there are graphing calculator activities designed to supplement the objectives for some of the lessons in this chapter. See .
::在CK-12得克萨斯州仪器代数I FlexBook资源中,有图表计算活动,旨在补充本章某些经验教训的目标。 -
Graph the inequalities (called
constraints
) to form a bounded area on the
coordinate plane
(called
the feasibility region
).