#set document(title: "8.5 Linear Programming", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 8.5#h(0.6em)Linear Programming The term #strong[linear programming] was coined in the late 1940s. It describes a relatively young branch of mathematics, compared to subjects such as Euclidean geometry, where the major ideas were already well understood 23 centuries ago. (The Greek mathematician Euclid wrote what can be considered the first geometry textbook about 300 B.C.) Business managers routinely solve linear programming problems for purchasing and marketing strategy, so it is possible that linear programming affects your daily life as much as any other branch of mathematics. === The Objective Function and Constraints TrailGear would like to maximize its profit from selling hiking boots. The company produces two kinds of hiking boots, a Weekender model, on which it makes \$#math.equation(block: false, alt: "8")[$8$] profit per pair, and a Sierra model, on which it makes \$#math.equation(block: false, alt: "10")[$10$] profit per pair. How many of each model should TrailGear produce each week in order to maximize its profit? If we let #math.equation(block: false, alt: "x")[$x$] represent the number of Weekender boots and #math.equation(block: false, alt: "y")[$y$] the number of Sierra boots TrailGear produces, then the total weekly profit is given by #math.equation(block: true, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] This expression for #math.equation(block: false, alt: "P")[$P$] is called the #strong[objective function]. The goal of a linear programming problem is to maximize or minimize such an objective function, subject to one or more constraints. If TrailGear had infinite resources and an infinite market, there would be no limit to the profit it could earn by producing more and more hiking boots. However, every business has to consider many factors, including its supplies of labor and materials, overhead and shipping costs, and the size of the market for its product. To keep things simple, we will concentrate on just two of these factors. Each pair of Weekender boots requires #math.equation(block: false, alt: "3")[$3$] hours of labor to produce, and each pair of Sierra boots requires #math.equation(block: false, alt: "6")[$6$] hours. TrailGear has available #math.equation(block: false, alt: "2400")[$2400$] hours of labor per week. Thus, #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] must satisfy the inequality #math.equation(block: true, alt: "3 x plus 6 y less than or equal to 2400")[$3 x + 6 y ≤ 2400$] In addition, suppose that TrailGear's suppliers can provide at most #math.equation(block: false, alt: "1000")[$1000$] ounces of silicone gel each week, with each pair of Weekenders using #math.equation(block: false, alt: "2")[$2$] ounces and each Sierra model using #math.equation(block: false, alt: "1")[$1$] ounce. This means that #math.equation(block: true, alt: "2 x plus y less than or equal to 1000")[$2 x + y ≤ 1000$] Of course, we will also require that #math.equation(block: false, alt: "x greater than or equal to 0")[$x ≥ 0$] and #math.equation(block: false, alt: "y greater than or equal to 0")[$y ≥ 0$]. These four inequalities are called the #strong[constraints] of the problem. Which of these could be an objective function? \_\_\_\_\_ #solutionbox[ #math.equation(block: true, alt: "M equals 2 x plus 5 y")[$M = 2 x + 5 y$] ] Which of these could be an objective function? + #math.equation(block: false, alt: "2 x plus 5 y less than or equal to 50")[$2 x + 5 y ≤ 50$] + #math.equation(block: false, alt: "M equals 2 x plus 5 y")[$M = 2 x + 5 y$] + #math.equation(block: false, alt: "y greater than or equal to 2 x plus 50")[$y ≥ 2 x + 50$] + #math.equation(block: false, alt: "2 x plus 5 y equals 50")[$2 x + 5 y = 50$] === Feasible Solutions We have formulated the original problem into an objective function #math.equation(block: true, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] and a system of inequalities called the constraints. #math.equation(block: true, alt: "3 x plus 6 y, less than or equal to 2400; 2 x plus y, less than or equal to 1000; x greater than or equal to 0 ,, y greater than or equal to 0")[$3 x + 6 y & ≤ 2400 \ 2 x + y & ≤ 1000 \ x ≥ 0 , " " " " & y ≥ 0$] Our goal is to find values for #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] that satisfy the constraints and produce the maximum value for #math.equation(block: false, alt: "P")[$P$]. We begin by graphing the solutions to the constraint inequalities. These solutions are shown in the shaded region in at right. The points in this region are called #strong[feasible solutions] because they are the only values we can consider while looking for the maximum value of the objective function #math.equation(block: false, alt: "P")[$P$]. #figure(figph[system of inequalities defining feasible solutions], alt: "system of inequalities defining feasible solutions", caption: none) #examplebox("Example 1")[][ + Verify that the points #math.equation(block: false, alt: "open parenthesis 300 , 100 close parenthesis")[$( 300 , 100 )$] and #math.equation(block: false, alt: "open parenthesis 200 , 300 close parenthesis")[$( 200 , 300 )$] represent feasible solutions for the problem above. Show that #math.equation(block: false, alt: "open parenthesis 300 , 400 close parenthesis")[$( 300 , 400 )$] is not a feasible solution. + Find the values of the objective function #math.equation(block: false, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] at the two feasible solutions in part (a). #solutionbox[ + The two points #math.equation(block: false, alt: "open parenthesis 300 , 100 close parenthesis")[$( 300 , 100 )$] and #math.equation(block: false, alt: "open parenthesis 200 , 300 close parenthesis")[$( 200 , 300 )$] lie within the shaded region above, but #math.equation(block: false, alt: "open parenthesis 300 , 400 close parenthesis")[$( 300 , 400 )$] does not. We can also verify that the coordinates of #math.equation(block: false, alt: "open parenthesis 300 , 100 close parenthesis")[$( 300 , 100 )$] and #math.equation(block: false, alt: "open parenthesis 200 , 300 close parenthesis")[$( 200 , 300 )$] satisfy each of the constraint inequalities. + For #math.equation(block: false, alt: "open parenthesis 300 , 100 close parenthesis")[$( 300 , 100 )$], we have #math.equation(block: true, alt: "P equals 8 open parenthesis 300 close parenthesis plus 10 open parenthesis 100 close parenthesis equals 3400")[$P = 8 ( 300 ) + 10 ( 100 ) = 3400$] For #math.equation(block: false, alt: "open parenthesis 200 , 300 close parenthesis")[$( 200 , 300 )$], we have #math.equation(block: true, alt: "P equals 8 open parenthesis 200 close parenthesis plus 10 open parenthesis 300 close parenthesis equals 4600")[$P = 8 ( 200 ) + 10 ( 300 ) = 4600$] ] ] What is the set of feasible solutions? \_\_\_\_\_ #solutionbox[ The set of points that satisfy the constraints is the set of feasible solutions. ] What is the set of feasible solutions? + The vertices of the solution set + The values of the objective function + The set of points that satisfy the constraints + The boundary lines of the inequalities + Determine which of the points #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis")[$( 0 , 400 )$], #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$], #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis")[$( 500 , 0 )$], and #math.equation(block: false, alt: "open parenthesis 500 , 400 close parenthesis")[$( 500 , 400 )$] represent feasible solutions for the TrailGear problem. #linebreak() \_\_\_\_\_ Separate different ordered pairs with a comma. + Find the values of the objective function #math.equation(block: false, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] at the feasible solutions in part (a). #linebreak() At #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis , P equals")[$( 0 , 400 ) , #h(1em) P =$]\_\_\_\_\_ #linebreak() At #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis , P equals")[$( 400 , 200 ) , #h(1em) P =$]\_\_\_\_\_ #linebreak() At #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis , P equals")[$( 500 , 0 ) , #h(1em) P =$]\_\_\_\_\_ #solutionbox[ + #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis")[$( 0 , 400 )$], #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$], and #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis")[$( 500 , 0 )$] + At #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis")[$( 0 , 400 )$], #math.equation(block: false, alt: "P equals 4000")[$P = 4000$]; at #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$], #math.equation(block: false, alt: "P equals 5200")[$P = 5200$]; at #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis")[$( 500 , 0 )$], #math.equation(block: false, alt: "P equals 4000")[$P = 4000$] ] + Determine which of the points #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis")[$( 0 , 400 )$], #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$], #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis")[$( 500 , 0 )$], and #math.equation(block: false, alt: "open parenthesis 500 , 400 close parenthesis")[$( 500 , 400 )$] represent feasible solutions for the TrailGear problem. + Find the values of the objective function #math.equation(block: false, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] at the feasible solutions in part (a). #solutionbox[ + #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis")[$( 0 , 400 )$], #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$], and #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis")[$( 500 , 0 )$] + At #math.equation(block: false, alt: "open parenthesis 0 , 400 close parenthesis")[$( 0 , 400 )$], #math.equation(block: false, alt: "P equals 4000")[$P = 4000$]; at #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$], #math.equation(block: false, alt: "P equals 5200")[$P = 5200$]; at #math.equation(block: false, alt: "open parenthesis 500 , 0 close parenthesis")[$( 500 , 0 )$], #math.equation(block: false, alt: "P equals 4000")[$P = 4000$] ] Explain how to find the set of feasible solutions. \_\_\_\_\_ Explain how to find the set of feasible solutions. === The Optimum Solutions We cannot check all of the feasible solutions to see which one results in the largest profit. Fortunately, there is a simple way to find the #strong[optimal solution]. Consider the objective function, #math.equation(block: true, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] Suppose TrailGear would like to make #math.equation(block: false, alt: "$ 2000")[$\$ 2000$] on hiking. It could produce #math.equation(block: false, alt: "200")[$200$] pairs of Sierra boots, or #math.equation(block: false, alt: "250")[$250$] pairs of Weekenders. Or it could produce some of each; for example, #math.equation(block: false, alt: "50")[$50$] pairs of Weekenders and #math.equation(block: false, alt: "160")[$160$] pairs of Sierra boots. In fact, every point on the line #math.equation(block: true, alt: "8 x plus 10 y equals 2000")[$8 x + 10 y = 2000$] represents a combination of Weekenders and Sierra boots that will yield a profit of \$#math.equation(block: false, alt: "2000")[$2000$]. This line is labeled #math.equation(block: false, alt: "P equals 2000")[$P = 2000$] in the figure below. #figure(figph[lines of constant objective function drawn over feasible solutions], alt: "lines of constant objective function drawn over feasible solutions", caption: none) If TrailGear would like to make \$#math.equation(block: false, alt: "4000")[$4000$] on boots, it should choose a point on the line labeled #math.equation(block: false, alt: "P equals 4000")[$P = 4000$]. Similarly, all the points on the line labeled #math.equation(block: false, alt: "P equals 6000")[$P = 6000$] will yield a profit of \$#math.equation(block: false, alt: "6000")[$6000$], and so on. Different values of #math.equation(block: false, alt: "P")[$P$] correspond to parallel lines on the graph. Smaller values of #math.equation(block: false, alt: "P")[$P$] correspond to lines near the origin, and larger values of #math.equation(block: false, alt: "P")[$P$] have lines farther from the origin. TrailGear's problem, with the profit line in your hands. The region where all three shadings overlap — above the axis and under both constraint lines — is the feasible region: production plans (x Weekenders, y Sierras) satisfying the labor constraint 3x + 6y ≤ 2400, the silicone constraint 2x + y ≤ 1000, and x, y ≥ 0. The red line is the objective P = 8x + 10y at the profit set by the slider. Slide P and the line moves parallel to itself — same slope −4/5 at every setting, exactly the parallel family this paragraph describes — with larger profits farther from the origin. The dot marks the vertex (400, 200), where the two constraint lines cross. Watch what happens as P climbs: the line leaves the region through that corner, touching it last at exactly P = 5200 — slide to 5200 and the line passes through the dot. For every larger P on the slider the line misses the region entirely: no feasible plan earns it. That is the section's key fact — the maximum of the objective function occurs at a vertex.{"functions":\[{"color":"\#1f4e79","domain":\[0,620\],"expression":"400 - x/2","expression2":"","id":"labor","inequality":"le","lineDash":\[\],"lineWidth":2.5,"mode":"inequality","tMax":0,"tMin":0,"variable":"x","visible":true},{"color":"\#2563eb","domain":\[0,620\],"expression":"1000 - 2\*x","expression2":"","id":"silicone","inequality":"le","lineDash":\[\],"lineWidth":2.5,"mode":"inequality","tMax":0,"tMin":0,"variable":"x","visible":true},{"color":"\#94a3b8","domain":\[0,620\],"expression":"0","expression2":"","id":"floor","inequality":"ge","lineDash":\[\],"lineWidth":2,"mode":"inequality","tMax":0,"tMin":0,"variable":"x","visible":true},{"color":"\#b8442a","domain":\[0,620\],"expression":"(P - 8\*x)/10","expression2":"","id":"objective","inequality":"lt","lineDash":\[\],"lineWidth":2.5,"mode":"cartesian","tMax":10,"tMin":-10,"variable":"x","visible":true},{"color":"\#b8442a","expression":"400 + 12\*cos(t)","expression2":"200 + 12\*sin(t)","id":"vertex","inequality":"lt","lineDash":\[\],"lineWidth":3,"mode":"parametric","tMax":6.2832,"tMin":0,"variable":"t","visible":true}\],"grid":{"majorSpacing":100,"showAxes":true,"showLabels":true},"parameters":\[{"id":"p-P","label":"Weekly profit P (\$)","max":6000,"min":1000,"name":"P","step":200,"value":2000}\],"title":"P = 8x + 10y over the feasible region","version":1,"viewport":{"centerX":260,"centerY":210,"scale":0.72}} What is an optimal solution? \_\_\_\_\_ #solutionbox[ The largest or smallest value of the objective function in the set of feasible solutions ] What is an optimal solution? + The largest or smallest feasible solution + The largest or smallest value of the objective function in the set of feasible solutions + The vertex farthest from the origin + The largest or smallest constrained #math.equation(block: false, alt: "y")[$y$]-value #examplebox("Example 2")[][ The figure below shows the feasible solutions for another linear programming problem. The objective function is #math.equation(block: false, alt: "C equals 3 x plus 5 y")[$C = 3 x + 5 y$]. #figure(figph[system of inequalities defining the feasible solutions], alt: "system of inequalities defining the feasible solutions", caption: none) + Find the value of #math.equation(block: false, alt: "C")[$C$] at the point #math.equation(block: false, alt: "open parenthesis 0 , 3 close parenthesis")[$( 0 , 3 )$]. Are there other feasible solutions that give the same value of #math.equation(block: false, alt: "C")[$C$]? + Find all feasible solutions that result in an objective value of #math.equation(block: false, alt: "30")[$30$]. + How many feasible solutions result in an objective value of #math.equation(block: false, alt: "39")[$39$]? + Is it possible for a feasible solution to result in an objective value of 45? #solutionbox[ + The objective value at the point #math.equation(block: false, alt: "open parenthesis 0 , 3 close parenthesis")[$( 0 , 3 )$] is #math.equation(block: true, alt: "C equals 3 open parenthesis 0 close parenthesis plus 5 open parenthesis 3 close parenthesis equals 15")[$C = 3 ( 0 ) + 5 ( 3 ) = 15$] Another point with the same objective value is #math.equation(block: false, alt: "open parenthesis 5 , 0 close parenthesis")[$( 5 , 0 )$]. In fact, all points on the line #math.equation(block: false, alt: "3 x plus 5 y equals 15")[$3 x + 5 y = 15$] have an objective value of #math.equation(block: false, alt: "15")[$15$]. This line intersects the set of feasible solutions in a line segment, as shown in below. Thus, there are infinitely many feasible solutions with objective value #math.equation(block: false, alt: "15")[$15$].#figure(figph[system of inequalities defining the feasible solutions], alt: "system of inequalities defining the feasible solutions", caption: none) + Points that give an objective value of #math.equation(block: false, alt: "C equals 30")[$C = 30$] lie on the line #math.equation(block: false, alt: "3 x plus 5 y equals 30")[$3 x + 5 y = 30$], as shown in the figure. There are infinitely many feasible solutions that lie on this line; for example, one such point is #math.equation(block: false, alt: "open parenthesis 5 , 3 close parenthesis")[$( 5 , 3 )$]. + The line #math.equation(block: false, alt: "3 x plus 5 y equals 39")[$3 x + 5 y = 39$] intersects the set of feasible solutions in only one point, the point #math.equation(block: false, alt: "open parenthesis 3 , 6 close parenthesis")[$( 3 , 6 )$]. This is the only feasible solution that yields an objective value of #math.equation(block: false, alt: "39")[$39$]. + The line #math.equation(block: false, alt: "3 x plus 5 y equals 45")[$3 x + 5 y = 45$] includes all points for which #math.equation(block: false, alt: "C equals 45")[$C = 45$]. This line does not intersect the set of feasible solutions, as we see in the figure. Thus, there are no feasible solutions that result in an objective value of #math.equation(block: false, alt: "45")[$45$]. ] ] + Returning to this section's opening Example regarding TrailGear profits for selling hiking boots, find all feasible solutions for which the objective function #math.equation(block: false, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] has a value of #math.equation(block: false, alt: "5200")[$5200$]. #linebreak() \_\_\_\_\_ + Find all feasible solutions that result in an objective value of #math.equation(block: false, alt: "6000")[$6000$]. #linebreak() \_\_\_\_\_ #solutionbox[ + #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$] + None ] + Returning to this section's opening Example regarding TrailGear profits for selling hiking boots, find all feasible solutions for which the objective function #math.equation(block: false, alt: "P equals 8 x plus 10 y")[$P = 8 x + 10 y$] has a value of #math.equation(block: false, alt: "5200")[$5200$]. + Find all feasible solutions that result in an objective value of #math.equation(block: false, alt: "6000")[$6000$]. #solutionbox[ + #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$] + None ] We are only allowed to choose points from the set of feasible solutions. Imagine the parallel lines representing different values of the objective function sweeping across the graph of the feasible solutions. The objective values increase as the lines sweep up across the graph. What is the last feasible solution the lines intersect before leaving the shaded region? If you study the preceding examples, perhaps you can see that the largest (and smallest) values of the objective function will occur at corner points of the set of feasible solutions. We have not proved this fact, but it is true. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Linear Programming] The maximum and the minimum values of the objective function always occur at vertices of the graph of feasible solutions. ] Depending on the exact formula for the objective function, the maximum and minimum values may occur at #emph[any] of the vertices of the shaded region. #examplebox("Example 3")[][ Find TrailGear's maximum weekly profit. #solutionbox[ The figure below shows the lines corresponding to the objective values #math.equation(block: false, alt: "P equals 2000")[$P = 2000$], #math.equation(block: false, alt: "P equals 4000")[$P = 4000$], and #math.equation(block: false, alt: "P equals 5200")[$P = 5200$]. #figure(figph[system of inequalities defining the feasible solutions], alt: "system of inequalities defining the feasible solutions", caption: none) The maximum value of the profit, #math.equation(block: false, alt: "P")[$P$], corresponds to the topmost line that intersects the region of feasible solutions. This is the line that passes through the vertex where the lines #math.equation(block: false, alt: "3 x plus 6 y equals 2400")[$" " " " 3 x + 6 y = 2400 " " " "$] and #math.equation(block: false, alt: "2 x plus y equals 1000")[$" " " " 2 x + y = 1000 " " " "$] intersect, namely the vertex at #math.equation(block: false, alt: "open parenthesis 400 , 200 close parenthesis")[$( 400 , 200 )$]. The profit for that point is #math.equation(block: true, alt: "P equals 8 open parenthesis 400 close parenthesis plus 10 open parenthesis 200 close parenthesis equals 5200")[$P = 8 ( 400 ) + 10 ( 200 ) = 5200$] so the maximum weekly profit is #math.equation(block: false, alt: "$ 5200")[$\$ 5200$]. ] ] #figure(figph[system of inequalities defining the feasible solutions], alt: "system of inequalities defining the feasible solutions", caption: none) The figure above shows the feasible solutions for a linear programming problem. The objective function is #math.equation(block: false, alt: "R equals x plus 5 y")[$R = x + 5 y$]. + Sketch lines for objective values of #math.equation(block: false, alt: "R equals 5")[$R = 5$], #math.equation(block: false, alt: "R equals 15")[$R = 15$], #math.equation(block: false, alt: "R equals 25")[$R = 25$], and #math.equation(block: false, alt: "R equals 35")[$R = 35$]. + Evaluate the objective function at each vertex of the shaded region. #linebreak() At #math.equation(block: false, alt: "open parenthesis 2 , 1 close parenthesis , P equals")[$( 2 , 1 ) , #h(1em) P =$]\_\_\_\_\_ #linebreak() At #math.equation(block: false, alt: "open parenthesis 0 , 5 close parenthesis , P equals")[$( 0 , 5 ) , #h(1em) P =$]\_\_\_\_\_ #linebreak() At #math.equation(block: false, alt: "open parenthesis 7 , 2 close parenthesis , P equals")[$( 7 , 2 ) , #h(1em) P =$]\_\_\_\_\_ + Which vertex corresponds to the maximum value of the objective function? \_\_\_\_\_ #linebreak() What is the maximum value? \_\_\_\_\_ + Which vertex corresponds to the minimum value of the objective function? \_\_\_\_\_ #linebreak() What is the minimum value? \_\_\_\_\_ #solutionbox[ + A graph is below. + At #math.equation(block: false, alt: "open parenthesis 2 , 1 close parenthesis")[$( 2 , 1 )$], #math.equation(block: false, alt: "R equals 7")[$R = 7$]; at #math.equation(block: false, alt: "open parenthesis 0 , 5 close parenthesis")[$( 0 , 5 )$], #math.equation(block: false, alt: "R equals 25")[$R = 25$]; at #math.equation(block: false, alt: "open parenthesis 7 , 2 close parenthesis")[$( 7 , 2 )$], #math.equation(block: false, alt: "R equals 17")[$R = 17$] + The maximum value of #math.equation(block: false, alt: "R")[$R$] occurs at #math.equation(block: false, alt: "open parenthesis 0 , 5 close parenthesis")[$( 0 , 5 )$]. The maximum value is #math.equation(block: false, alt: "25")[$25$]. + The minimum value of #math.equation(block: false, alt: "R")[$R$] occurs at #math.equation(block: false, alt: "open parenthesis 2 , 1 close parenthesis")[$( 2 , 1 )$]. The minimum value is #math.equation(block: false, alt: "7")[$7$]. ] Graph for part (a): #figure(figph[feasible solutions and objective function lines], alt: "feasible solutions and objective function lines", caption: none) The figure below shows the feasible solutions for a linear programming problem. The objective function is #math.equation(block: false, alt: "R equals x plus 5 y")[$R = x + 5 y$]. #figure(figph[system of inequalities defining the feasible solutions], alt: "system of inequalities defining the feasible solutions", caption: none) + Sketch lines for objective values of #math.equation(block: false, alt: "R equals 5")[$R = 5$], #math.equation(block: false, alt: "R equals 15")[$R = 15$], #math.equation(block: false, alt: "R equals 25")[$R = 25$], and #math.equation(block: false, alt: "R equals 35")[$R = 35$]. + Evaluate the objective function at each vertex of the shaded region. + Which vertex corresponds to the maximum value of the objective function? What is the maximum value? + Which vertex corresponds to the minimum value of the objective function? What is the minimum value? #solutionbox[ + #figure(figph[feasible solutions and objective function lines], alt: "feasible solutions and objective function lines", caption: none) + At #math.equation(block: false, alt: "open parenthesis 2 , 1 close parenthesis")[$( 2 , 1 )$], #math.equation(block: false, alt: "R equals 7")[$R = 7$]; at #math.equation(block: false, alt: "open parenthesis 0 , 5 close parenthesis")[$( 0 , 5 )$], #math.equation(block: false, alt: "R equals 25")[$R = 25$]; at #math.equation(block: false, alt: "open parenthesis 7 , 2 close parenthesis")[$( 7 , 2 )$], #math.equation(block: false, alt: "R equals 17")[$R = 17$] + The maximum value of #math.equation(block: false, alt: "R")[$R$] occurs at #math.equation(block: false, alt: "open parenthesis 0 , 5 close parenthesis")[$( 0 , 5 )$]. The maximum value is #math.equation(block: false, alt: "25")[$25$]. + The minimum value of #math.equation(block: false, alt: "R")[$R$] occurs at #math.equation(block: false, alt: "open parenthesis 2 , 1 close parenthesis")[$( 2 , 1 )$]. The minimum value is #math.equation(block: false, alt: "7")[$7$]. ] We can now formulate a strategy for solving problems by linear programming. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[To Solve a Linear Programming Problem:] + Represent the unknown quantities by variables. Write the objective function and the constraints in terms of the variables. + Graph the solutions to the constraint inequalities. + Find the coordinates of each vertex of the solution set. + Evaluate the objective function at each vertex. + The maximum and minimum values of the objective function occur at vertices of the set of feasible solutions. ] Linear programming is used to \_\_\_\_\_ #solutionbox[ find an optimal solution subject to a set of constraints. ] Linear programming is used to + find the vertices of a region. + solve a system of inequalities. + write a set of inequalities in two variables. + find an optimal solution subject to a set of constraints. In Example, the set of feasible solutions is an unbounded region. #examplebox("Example 4")[][ Each week, the Healthy Food Store buys both granola and muesli in bulk from two cereal companies. The store requires at least #math.equation(block: false, alt: "12")[$12$] kilograms of granola and #math.equation(block: false, alt: "9")[$9$] kilograms of muesli. - Company A charges \$#math.equation(block: false, alt: "15")[$15$] for a package that contains #math.equation(block: false, alt: "2")[$2$] kilograms of granola and #math.equation(block: false, alt: "1")[$1$] kilogram of muesli. - Company B charges \$#math.equation(block: false, alt: "25")[$25$] for a package of #math.equation(block: false, alt: "3")[$3$] kilograms of granola and #math.equation(block: false, alt: "3")[$3$] kilograms of muesli. How much should the Healthy Food Store purchase from each company in order to minimize its costs and still meet its needs for granola and muesli? What is the minimum cost? #solutionbox[ + #math.equation(block: true, alt: "Number of packages purchased from Company A: x; Number of packages purchased from Company B: y")[$"Number of packages purchased from Company A: " " " " " x \ "Number of packages purchased from Company B: " " " " " y$] First, we write the objective function. The store would like to minimize its cost, so #math.equation(block: true, alt: "C equals 15 x plus 25 y")[$C = 15 x + 25 y$] Next, we write the constraints. These will be a system of inequalities. It may help to organize the information into a table.#figure(table( columns: 4, align: left, inset: 6pt, table.header([], [Company A], [Company B], [Required]), [Granola], [#math.equation(block: false, alt: "2 x")[$2 x$]], [#math.equation(block: false, alt: "3 y")[$3 y$]], [12], [Muesli], [#math.equation(block: false, alt: "x")[$x$]], [#math.equation(block: false, alt: "3 y")[$3 y$]], [9], )) #linebreak() The Healthy Food Store will have #math.equation(block: false, alt: "2 x")[$2 x$] kilograms of granola and #math.equation(block: false, alt: "x")[$x$] kilograms of muesli from Company A, and #math.equation(block: false, alt: "3 y")[$3 y$] kilograms of granola and #math.equation(block: false, alt: "3 y")[$3 y$] kilograms of muesli from Company B. The store requires that #math.equation(block: true, alt: "2 x plus 3 y, greater than or equal to 12; x plus 3 y, greater than or equal to 9")[$2 x + 3 y & ≥ 12 \ x + 3 y & ≥ 9$] Because the store cannot purchase negative quantities, we also have #math.equation(block: true, alt: "x greater than or equal to 0 , y greater than or equal to 0")[$x ≥ 0 , " " " " " " " " " " y ≥ 0$] + We graph the solutions to the constraint system. The feasible solutions form the shaded region shown below. Any ordered point on this graph corresponds to a way to purchase granola and muesli that meets the store’s needs, but some of these choices cost more than others. #figure(figph[unbounded set of feasible solutions], alt: "unbounded set of feasible solutions", caption: none) + We know that the minimum cost will occur at one of the vertex points, which are labeled in the figure. The coordinates of #math.equation(block: false, alt: "P")[$P$] and #math.equation(block: false, alt: "R")[$R$] are easy to see. To find the coordinates of #math.equation(block: false, alt: "Q")[$Q$], we notice that it is the intersection of the lines #math.equation(block: false, alt: "2 x plus 3 y equals 12")[$2 x + 3 y = 12$] and #math.equation(block: false, alt: "x plus 3 y equals 9")[$x + 3 y = 9$]. Thus, we must solve the system #math.equation(block: true, alt: "2 x plus 3 y, equals 12; x plus 3 y, equals 9")[$2 x + 3 y & = 12 \ x + 3 y & = 9$] Subtracting the second equation from the first, we find that #math.equation(block: false, alt: "x equals 3")[$x = 3$]. Substituting this value into either of the original two equations, we find that #math.equation(block: false, alt: "y equals 2")[$y = 2$]. Thus the point #math.equation(block: false, alt: "Q")[$Q$] has coordinates #math.equation(block: false, alt: "open parenthesis 3 , 2 close parenthesis")[$( 3 , 2 )$]. + Now we evaluate the objective function at each of the three vertices. #math.equation(block: true, alt: "At P open parenthesis 0 , 4 close parenthesis :, C, equals 15 open parenthesis 0 close parenthesis plus 25 open parenthesis 4 close parenthesis equals 100; At P open parenthesis 3 , 2 close parenthesis :, C, equals 15 open parenthesis 3 close parenthesis plus 25 open parenthesis 2 close parenthesis equals 95, Minimum cost; At P open parenthesis 9 , 0 close parenthesis :, C, equals 15 open parenthesis 9 close parenthesis plus 25 open parenthesis 0 close parenthesis equals 135")[$& "At " P ( 0 , 4 ) : & C & = 15 ( 0 ) + 25 ( 4 ) = 100 \ & "At " P ( 3 , 2 ) : & C & = 15 ( 3 ) + 25 ( 2 ) = 95 & & "Minimum cost" \ & "At " P ( 9 , 0 ) : & C & = 15 ( 9 ) + 25 ( 0 ) = 135 &$] The minimum cost occurs at point #math.equation(block: false, alt: "Q")[$Q$]. + The Healthy Food Store should buy three packages from Company A and two packages from Company B. It will pay \$#math.equation(block: false, alt: "95")[$95$] for its stock of granola and muesli. ] ] Find the maximum value of the objective function, #math.equation(block: false, alt: "O equals 5 x plus 3 y")[$O = 5 x + 3 y$], subject to the constraints #math.equation(block: true, alt: "x plus y, greater than or equal to 7; 5 x plus 2 y, greater than or equal to 20; x greater than or equal to 0 , y, greater than or equal to 0")[$x + y & ≥ 7 \ 5 x + 2 y & ≥ 20 \ x ≥ 0 , " " " " y & ≥ 0$] Answer: \_\_\_\_\_ #solutionbox[ The maximum value is #math.equation(block: false, alt: "25")[$25$] (which occurs at the vertex #math.equation(block: false, alt: "open parenthesis 2 , 5 close parenthesis")[$( 2 , 5 )$]). ] Find the maximum value of the objective function, #math.equation(block: false, alt: "O equals 5 x plus 3 y")[$O = 5 x + 3 y$], subject to the constraints #math.equation(block: true, alt: "x plus y, greater than or equal to 7; 5 x plus 2 y, greater than or equal to 20; x greater than or equal to 0 , y, greater than or equal to 0")[$x + y & ≥ 7 \ 5 x + 2 y & ≥ 20 \ x ≥ 0 , " " " " y & ≥ 0$] #solutionbox[ The maximum value is #math.equation(block: false, alt: "25")[$25$] (which occurs at the vertex #math.equation(block: false, alt: "open parenthesis 2 , 5 close parenthesis")[$( 2 , 5 )$]). ] What fact helps us find the optimal solution? \_\_\_\_\_ What fact helps us find the optimal solution? #notebox("Technology", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Using a Graphing Calculator] You can use your graphing calculator to solve the problem in Example. Set the window values at #math.equation(block: true, alt: "Xmin, equals 0, Xmax equals 9.4; Ymin, equals 0, Ymax equals 6.2")[$"Xmin" & = 0 & & "Xmax" = 9.4 \ "Ymin" & = 0 & & "Ymax" = 6.2$] Next, graph the set of feasible solutions. We have already taken care of the constraints #math.equation(block: false, alt: "x greater than or equal to 0")[$x ≥ 0$] and #math.equation(block: false, alt: "y greater than or equal to 0")[$y ≥ 0$] by setting Xmin and Ymin to zero. Solve each of the other constraints for #math.equation(block: false, alt: "y")[$y$] to get #math.equation(block: true, alt: "y, greater than or equal to open parenthesis 12 minus 2 x close parenthesis / 3; y, greater than or equal to open parenthesis 9 minus x close parenthesis / 3")[$y & ≥ ( 12 − 2 x ) / 3 \ y & ≥ ( 9 − x ) / 3$] For each constraint, the set of feasible solutions lies above the boundary line, because #math.equation(block: false, alt: "y")[$y$] is greater than the expression in #math.equation(block: false, alt: "x")[$x$]. To shade the regions above the graphs of #math.equation(block: false, alt: "Y sub 1")[$Y_(1)$] and #math.equation(block: false, alt: "Y sub 2")[$Y_(2)$], move the cursor onto the backslash in front of the equations and press ENTER twice, as shown in figure (a). Then press GRAPH. Your display should look like figure (b). #figure(figph[GCdisplays for graphing systems of inequalities], alt: "GCdisplays for graphing systems of inequalities", caption: none) The feasible solutions lie in the crosshatched region that is shaded with both the vertical and horizontal lines. We will use the calculator to evaluate the objective function at each vertex. First, use the TRACE (or #emph[value] or #emph[intersect] feature) to find the coordinates of one of the vertices, say #math.equation(block: false, alt: "open parenthesis 0 , 4 close parenthesis")[$( 0 , 4 )$]. Then press 2nd QUIT to get back to the #emph[Home] screen; enter the formula for the objective function by keying in #math.equation(block: true, alt: "15 X plus 25 Y")[$15 X + 25 Y$] (Enter #math.equation(block: false, alt: "Y")[$Y$] by pressing ALPHA #math.equation(block: false, alt: "1")[$1$].) Your calculator has stored the values #math.equation(block: false, alt: "x equals 0")[$x = 0$] and #math.equation(block: false, alt: "y equals 4")[$y = 4$] from the TRACE key, so when you press ENTER, the calculator returns #math.equation(block: false, alt: "100")[$100$] for the value of #math.equation(block: false, alt: "C")[$C$] at that point. Thus, when #math.equation(block: false, alt: "x equals 0")[$x = 0$] and #math.equation(block: false, alt: "y equals 4")[$y = 4$], #math.equation(block: false, alt: "C equals 100")[$C = 100$]. Similarly, you can verify that #math.equation(block: false, alt: "C equals 135")[$C = 135$] when #math.equation(block: false, alt: "x equals 9")[$x = 9$] and #math.equation(block: false, alt: "y equals 0")[$y = 0$], and that when #math.equation(block: false, alt: "x equals 3")[$x = 3$] and #math.equation(block: false, alt: "y equals 2")[$y = 2$], #math.equation(block: false, alt: "C minus 95")[$C − 95$]. Thus, the minimum cost of #math.equation(block: false, alt: "$ 95")[$upright(\$) 95$] occurs when #math.equation(block: false, alt: "x equals 3")[$x = 3$] and #math.equation(block: false, alt: "y equals 2")[$y = 2$]. ] === Section Summary ==== Vocabulary Look up the definitions of new terms in the Glossary. - Objective function - Constraint - Feasible solution - Optimal solution ==== CONCEPTS + #strong[Linear programming] is a technique for finding the maximum or minimum value of an #strong[objective function], subject to a system of #strong[constraints]. + The optimal solution occurs at one of the vertices of the set of #strong[feasible solutions]. + #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[To Solve a Linear Programming Problem:] + Represent the unknown quantities by variables. Write the objective function and the constraints in terms of the variables. + Graph the solutions to the constraint inequalities. + Find the coordinates of each vertex of the solution set. + Evaluate the objective function at each vertex. + The maximum and minimum values of the objective function occur at vertices of the set of feasible solutions. ] ==== STUDY QUESTIONS + Explain the terms #strong[objective function], #strong[constraints], and #strong[feasible solution]. + Explain how to solve a linear programming problem by graphing. + How can you find the vertices of the set of feasible solutions? + Where do the maximum and minimum values of the objective function occur? ==== SKILLS Practice each skill in the Homework problems listed. + Find the maximum or minimum value for an objective function and a given set of feasible solutions: \#1–12 + Solve a linear programming problem by graphing: \#13–32 + Write the objective function and the constraints for a linear programming problem: \#19–24 === Homework 8.5 For Problems 1–4, find the minimum value of the cost function #math.equation(block: false, alt: "C equals 3 x plus 4 y")[$C = 3 x + 4 y$] subject to following constraints: #math.equation(block: true, alt: "x plus y greater than or equal to 10 , x less than or equal to 8 , y less than or equal to 7 , x greater than or equal to 0 , y greater than or equal to 0")[$x + y ≥ 10 , " " " " x ≤ 8 , " " " " y ≤ 7 , " " " " x ≥ 0 , " " " " y ≥ 0$] The graph of the feasible solutions is shown in in the figure. #figure(figph[feasible set, C=3x+4y], alt: "feasible set, C=3x+4y", caption: none) Use a graph to explain why it is impossible in this situation to have a cost as low as \$#math.equation(block: false, alt: "12")[$12$]. Draw the graph of #math.equation(block: false, alt: "12 equals 3 x plus 4 y")[$12 = 3 x + 4 y$] on the graph of the feasible solutions. The graph of #math.equation(block: false, alt: "12 equals 3 x plus 4 y")[$12 = 3 x + 4 y$] does not intersect the set of feasible solutions. Use a graph to explain why the cost will not be as great as \$#math.equation(block: false, alt: "60")[$60$]. Draw the graph of #math.equation(block: false, alt: "60 equals 3 x plus 4 y")[$60 = 3 x + 4 y$] on the graph of the feasible solutions. Use a graph to determine which vertex of the shaded region will correspond to the minimum cost. What is the minimum cost? #math.equation(block: false, alt: "open parenthesis 8 , 2 close parenthesis")[$( 8 , 2 )$]; \$#math.equation(block: false, alt: "32")[$32$] Use a graph to determine which vertex of the shaded region will correspond to the maximum cost. What is the maximum cost? For Problems 5–8, find the minimum value of the profit function #math.equation(block: false, alt: "P equals 4 x minus 2 y")[$P = 4 x − 2 y$] subject to the following constraints: #math.equation(block: true, alt: "5 x minus y greater than or equal to 22 , x plus y less than or equal to 8 , x greater than or equal to 0 , y greater than or equal to 0")[$5 x − y ≥ 22 , " " " " x + y ≤ 8 , " " " " x ≥ 0 , " " " " y ≥ 0$] The graph of the feasible solutions is shown in the figure. #figure(figph[feasible set, P=4x-2y], alt: "feasible set, P=4x-2y", caption: none) Graph the line that corresponds to a profit of #math.equation(block: false, alt: "$ 8")[$upright(\$) 8$]. Find the coordinates of at least one feasible solution that gives a profit of \$#math.equation(block: false, alt: "8")[$8$]. #math.equation(block: true, alt: "open parenthesis 2 , 0 close parenthesis")[$( 2 , 0 )$] Graph the line that corresponds to a profit of \$#math.equation(block: false, alt: "22")[$22$]. Find the coordinates of at least one feasible solution that gives a profit of #math.equation(block: false, alt: "$ 22")[$upright(\$) 22$]. + Which line is farther from the origin, the line for a profit of \$#math.equation(block: false, alt: "8")[$8$] or the line for the profit of \$#math.equation(block: false, alt: "22")[$22$]? + Use a graph to determine which vertex corresponds to a maximum profit. + Find the maximum profit. + \$#math.equation(block: false, alt: "22")[$22$] + #math.equation(block: false, alt: "open parenthesis 8 , 0 close parenthesis")[$( 8 , 0 )$] + \$#math.equation(block: false, alt: "32")[$32$] + Use a graph to determine which vertex corresponds to a minimum profit. + Find the minimum profit. For Problems 9–12, objective functions and the graphs of the feasible solutions are given. + Use the graph to find the vertex that yields the minimum value of the objective function, and find the minimum value. + Use the graph to find the vertex that yields the maximum value of the objective function, and find the maximum value. #math.equation(block: true, alt: "C equals 3 x plus y")[$C = 3 x + y$] #figure(figph[feasible points], alt: "feasible points", caption: none) + #math.equation(block: false, alt: "open parenthesis 1 , 4 close parenthesis")[$( 1 , 4 )$]; #math.equation(block: false, alt: "7")[$7$] + #math.equation(block: false, alt: "open parenthesis 4 , 5 close parenthesis")[$( 4 , 5 )$]; #math.equation(block: false, alt: "17")[$17$] #math.equation(block: true, alt: "C equals x plus 4 y")[$C = x + 4 y$] #figure(figph[feasible points], alt: "feasible points", caption: none) #math.equation(block: true, alt: "C equals 5 x minus 2 y")[$C = 5 x − 2 y$] #figure(figph[feasible points], alt: "feasible points", caption: none) + #math.equation(block: false, alt: "open parenthesis 0 , 5 close parenthesis")[$( 0 , 5 )$]; #math.equation(block: false, alt: "minus 10")[$− 10$] + #math.equation(block: false, alt: "open parenthesis 5 , 0 close parenthesis")[$( 5 , 0 )$]; #math.equation(block: false, alt: "25")[$25$] #math.equation(block: true, alt: "C equals 2 x minus y")[$C = 2 x − y$] #figure(figph[feasible points], alt: "feasible points", caption: none) For Problems 13–18, + Graph the set of feasible solutions. + Find the vertex that gives the minimum of the objective function, and find the minimum value. + Find the vertex that gives the maximum of the objective function, and find the maximum value. Objective function #math.equation(block: false, alt: "C equals 3 x plus 2 y")[$C = 3 x + 2 y$] with constraints #math.equation(block: true, alt: "2 x plus y, less than or equal to 8; 4 x plus 6 y, less than or equal to 24; x greater than or equal to 0 , y, greater than or equal to 0")[$2 x + y & ≤ 8 \ 4 x + 6 y & ≤ 24 \ x ≥ 0 , " " " " y & ≥ 0$] b. #math.equation(block: false, alt: "open parenthesis 0 , 0 close parenthesis")[$( 0 , 0 )$]; #math.equation(block: false, alt: "0")[$0 #hide($000$)$]c. #math.equation(block: false, alt: "open parenthesis 3 , 2 close parenthesis")[$( 3 , 2 )$]; #math.equation(block: false, alt: "13")[$13$] Objective function #math.equation(block: false, alt: "C equals minus 2 x plus y")[$C = − 2 x + y$] with constraints #math.equation(block: true, alt: "x minus 2 y, greater than or equal to minus 10; 2 x plus y, less than or equal to 10; x greater than or equal to 0 , y, greater than or equal to 0")[$x − 2 y & ≥ − 10 \ 2 x + y & ≤ 10 \ x ≥ 0 , " " " " y & ≥ 0$] Objective function #math.equation(block: false, alt: "C equals 3 x minus y")[$C = 3 x − y$] with constraints #math.equation(block: true, alt: "x plus y, less than or equal to 14; 5 x plus y, less than or equal to 50; x greater than or equal to 0 , y, greater than or equal to 0")[$x + y & ≤ 14 \ 5 x + y & ≤ 50 \ x ≥ 0 , " " " " y & ≥ 0$] b. #math.equation(block: false, alt: "open parenthesis 0 , 14 close parenthesis")[$( 0 , 14 )$]; #math.equation(block: false, alt: "minus 14")[$− 14 #hide($000$)$]c. #math.equation(block: false, alt: "open parenthesis 0 , 0 close parenthesis")[$( 0 , 0 )$]; #math.equation(block: false, alt: "30")[$30$] Objective function #math.equation(block: false, alt: "C equals 5 x plus 4 y")[$C = 5 x + 4 y$] with constraints #math.equation(block: true, alt: "2 x plus y, less than or equal to 10; x minus 3 y, greater than or equal to minus 3; x greater than or equal to 0 , y, greater than or equal to 0")[$2 x + y & ≤ 10 \ x − 3 y & ≥ − 3 \ x ≥ 0 , " " " " y & ≥ 0$] Objective function #math.equation(block: false, alt: "C equals 200 x minus 20 y")[$C = 200 x − 20 y$] with constraints #math.equation(block: true, alt: "3 x plus 2 y, less than or equal to 24; x plus y, less than or equal to 9; x plus 2 y, less than or equal to 16; x greater than or equal to 0 , y, greater than or equal to 0")[$3 x + 2 y & ≤ 24 \ x + y & ≤ 9 \ x + 2 y & ≤ 16 \ x ≥ 0 , " " " " y & ≥ 0$] b. #math.equation(block: false, alt: "open parenthesis 0 , 8 close parenthesis")[$( 0 , 8 )$]; #math.equation(block: false, alt: "minus 160")[$− 160 #hide($000$)$]c. #math.equation(block: false, alt: "open parenthesis 8 , 0 close parenthesis")[$( 8 , 0 )$]; #math.equation(block: false, alt: "1600")[$1600$] Objective function #math.equation(block: false, alt: "C equals 54 x plus 24 y")[$C = 54 x + 24 y$] with constraints #math.equation(block: true, alt: "3 x plus 2 y, less than or equal to 24; 3 x minus y, less than or equal to 15; 3 x minus 4 y, greater than or equal to minus 12; x greater than or equal to 0 , y, greater than or equal to 0")[$3 x + 2 y & ≤ 24 \ 3 x − y & ≤ 15 \ 3 x − 4 y & ≥ − 12 \ x ≥ 0 , " " " " y & ≥ 0$] For Problems 19–26, solve each linear programming problem by graphing. + Write a formula for the objective function. + Write a system of inequalities for the constraints. + Graph the set of feasible solutions. + Find the optimum solution. The math club is selling tickets for a show by a mathemagician. Student tickets will cost \$#math.equation(block: false, alt: "1")[$1$] and faculty tickets will cost \$#math.equation(block: false, alt: "2")[$2$]. The ticket receipts must be at least #math.equation(block: false, alt: "$ 250")[$upright(\$) 250$] to cover the fee for the performer. An alumna promises to donate one calculator for each student ticket sold and three calculators for each faculty ticket sold. What is the minimum number of calculators that the alumna will donate? + #math.equation(block: false, alt: "C equals x plus 3 y")[$C = x + 3 y$] + #math.equation(block: false, alt: "x greater than or equal to 0 , y greater than or equal to 0 , x plus 2 y greater than or equal to 250")[$x ≥ 0 , " " y ≥ 0 , " " x + 2 y ≥ 250$] + #figure(figph[system of inequalities], alt: "system of inequalities", caption: none) + #math.equation(block: false, alt: "250")[$250$] The math department is having a book sale of unwanted textbooks to raise funds for \$#math.equation(block: false, alt: "300")[$300$] in scholarships. Paperback textbooks will be sold for \$#math.equation(block: false, alt: "2")[$2$] and the hardcover textbooks will be sold for \$#math.equation(block: false, alt: "5")[$5$]. If paperback texts weigh #math.equation(block: false, alt: "2")[$2$] pounds each and hardcover books weigh #math.equation(block: false, alt: "3")[$3$] pounds each, find the minimum weight of textbooks the department must sell in order to raise its required funds. Jeannette has #math.equation(block: false, alt: "180")[$180$] acres of farmland for growing wheat or soy. Each acre of wheat requires two hours of labor at harvest time, and each acre of soy needs one hour of labor. Jeannette will have #math.equation(block: false, alt: "240")[$240$] hours of labor available at harvest time. Find the maximum profit Jeannette can make from her two crops if she can get a profit of \$#math.equation(block: false, alt: "36")[$36$] per acre for wheat and \$#math.equation(block: false, alt: "24")[$24$] per acre for soy. + #math.equation(block: false, alt: "P equals 36 x plus 24 y")[$P = 36 x + 24 y$] + #math.equation(block: false, alt: "x greater than or equal to 0")[$x ≥ 0$], #math.equation(block: false, alt: "y greater than or equal to 0")[$" " y ≥ 0$], #math.equation(block: false, alt: "x plus y less than or equal to 180")[$" " x + y ≤ 180$], #math.equation(block: false, alt: "2 x plus y less than or equal to 240")[$" " 2 x + y ≤ 240$] + #figure(figph[set of feasible solutions], alt: "set of feasible solutions", caption: none) + \$#math.equation(block: false, alt: "5040")[$5040$] Vassilis has at most \$#math.equation(block: false, alt: "10 , 000")[$10 , 000$] to invest in two banks. Alpha Bank will pay #math.equation(block: false, alt: "6 %")[$6 upright(%)$] annual interest and Bank Beta pays #math.equation(block: false, alt: "5 %")[$5 upright(%)$] annual interest. Alpha Bank will only insure up to \$#math.equation(block: false, alt: "6000")[$6000$], so Vassilis will invest no more than that with Alpha. What is the maximum amount of interest Vassilis can earn in #math.equation(block: false, alt: "1")[$1$] year? Gary's pancake recipe includes corn meal and whole wheat flour. Corn meal has #math.equation(block: false, alt: "2.4")[$2.4$] grams of linoleic acid and #math.equation(block: false, alt: "2.5")[$2.5$] milligrams of niacin per cup. Whole wheat flour has #math.equation(block: false, alt: "0.8")[$0.8$] gram of linoleic acid and #math.equation(block: false, alt: "5.2")[$5.2$] milligrams of niacin per cup. These two dry ingredients do not exceed #math.equation(block: false, alt: "3")[$3$] cups total. They combine for at least #math.equation(block: false, alt: "3.2")[$3.2$] grams of linoleic acid and at least #math.equation(block: false, alt: "10")[$10$] milligrams of niacin. Minimize the number of calories possible in the recipe if corn meal has #math.equation(block: false, alt: "433")[$433$] calories per cup and whole wheat flour has #math.equation(block: false, alt: "400")[$400$] calories per cup. + #math.equation(block: false, alt: "C equals 433 x plus 400 y")[$C = 433 x + 400 y$] + #math.equation(block: false, alt: "x greater than or equal to 0")[$x ≥ 0$], #math.equation(block: false, alt: "y greater than or equal to 0")[$" " y ≥ 0$], #math.equation(block: false, alt: "2.4 x plus 0.8 y greater than or equal to 3.2")[$" " 2.4 x + 0.8 y ≥ 3.2$], #math.equation(block: false, alt: "2.5 x plus 5.2 y greater than or equal to 10")[$" " 2.5 x + 5.2 y ≥ 10$] + #figure(figph[system of inequalities], alt: "system of inequalities", caption: none) + #math.equation(block: false, alt: "967.7")[$967.7$] cal Cho requires #math.equation(block: false, alt: "1")[$1$] hour of cutting and #math.equation(block: false, alt: "2")[$2$] hours of sewing to make a Batman costume. He requires #math.equation(block: false, alt: "2")[$2$] hours of cutting and #math.equation(block: false, alt: "1")[$1$] hour of sewing to make a Wonder Woman costume. At most #math.equation(block: false, alt: "10")[$10$] hours per day are available for cutting and at most #math.equation(block: false, alt: "8")[$8$] hours per day are available for sewing. At least one costume must be made each day to stay in business. Find Cho's maximum income from selling one day's costumes if a Batman costume costs \$#math.equation(block: false, alt: "68")[$68$] and a Wonder Woman costume costs \$#math.equation(block: false, alt: "76")[$76$]. For Problems 25–30, use a graphing calculator to find approximate values for the maximum and minimum of the objective function. Objective function #math.equation(block: false, alt: "C equals 8.7 x minus 4.2 y")[$C = 8.7 x − 4.2 y$] with constraints #math.equation(block: true, alt: "1.7 x minus 4.5 y, greater than or equal to minus 9; 14.3 x plus 10.9 y, less than or equal to 28.6; x greater than or equal to 0 , y, greater than or equal to 0")[$1.7 x − 4.5 y & ≥ − 9 \ 14.3 x + 10.9 y & ≤ 28.6 \ x ≥ 0 , " " " " y & ≥ 0$] Maximum #math.equation(block: false, alt: "17.4")[$17.4$]; minimum #math.equation(block: false, alt: "minus 8.4")[$− 8.4$] Objective function #math.equation(block: false, alt: "C equals minus 142 x plus 83 y")[$C = − 142 x + 83 y$] with constraints #math.equation(block: true, alt: "21 x minus 49 y, greater than or equal to minus 147; 19 x plus 21 y, less than or equal to 171; x greater than or equal to 0 , y, greater than or equal to 0")[$21 x − 49 y & ≥ − 147 \ 19 x + 21 y & ≤ 171 \ x ≥ 0 , " " " " y & ≥ 0$] Objective function #math.equation(block: false, alt: "C equals 312 x plus 92 y")[$C = 312 x + 92 y$] with constraints #math.equation(block: true, alt: "18 x plus 17 y, less than or equal to 284; 51 x plus 11 y, less than or equal to 656; x greater than or equal to 0 , y, greater than or equal to 0")[$18 x + 17 y & ≤ 284 \ 51 x + 11 y & ≤ 656 \ x ≥ 0 , " " " " y & ≥ 0$] Maximum #math.equation(block: false, alt: "4112")[$4112$]; minimum #math.equation(block: false, alt: "0")[$0$] Objective function #math.equation(block: false, alt: "C equals 5.3 x plus 4.2 y")[$C = 5.3 x + 4.2 y$] with constraints #math.equation(block: true, alt: "2.5 x plus 1.7 y, less than or equal to 20.1; 0.09 x minus 0.31 y, greater than or equal to minus 0.39; x greater than or equal to 0 , y, greater than or equal to 0")[$2.5 x + 1.7 y & ≤ 20.1 \ 0.09 x − 0.31 y & ≥ − 0.39 \ x ≥ 0 , " " " " y & ≥ 0$] Objective function #math.equation(block: false, alt: "C equals 202 x plus 220 y")[$C = 202 x + 220 y$] with constraints #math.equation(block: true, alt: "38 x plus 24 y, less than or equal to 294; 35 x plus 34 y, less than or equal to 310; 13 x plus 29 y, less than or equal to 197; x greater than or equal to 0 , y, greater than or equal to 0")[$38 x + 24 y & ≤ 294 \ 35 x + 34 y & ≤ 310 \ 13 x + 29 y & ≤ 197 \ x ≥ 0 , " " " " y & ≥ 0$] Maximum #math.equation(block: false, alt: "1908")[$1908$]; minimum #math.equation(block: false, alt: "0")[$0$] Objective function #math.equation(block: false, alt: "C equals 54 x plus 24 y")[$C = 54 x + 24 y$] with constraints #math.equation(block: true, alt: "43 x plus 32 y, less than or equal to 333; 23 x minus 9 y, less than or equal to 152; 73 x minus 94 y, greater than or equal to minus 296; x greater than or equal to 0 , y, greater than or equal to 0")[$43 x + 32 y & ≤ 333 \ 23 x − 9 y & ≤ 152 \ 73 x − 94 y & ≥ − 296 \ x ≥ 0 , " " " " y & ≥ 0$]