370 CHAPTER 6 Algebra, Graphs, and Functions Linear Programming Linear programming provides businesses and governments with a mathematical tool for determining the most efficient use of resources. Linear programming is used to solve problems in many areas of business, science, medicine, and the military by using a technique called the simplex method , which was developed in the 1940’s by George Dantzig. In a linear programming problem, restrictions called constraints are represented with a system of linear inequalities. When the system is graphed, a shaded region (Fig. 6.37), called the feasible region, is obtained. As seen in Fig. 6.37, the vertices are the corner points of the feasible region. For each linear programming problem, we will obtain a formula of the form K Ax By, = + called the objective function . The objective function represents a model for the quantity, in this case K, that we want to maximize or minimize. For example, a typical objective function that might be used to maximize a company’s profit, P, is P x y 3 7 . = + We determine the maximum profit by substituting the ordered pairs x y ( , ) of the vertices of the feasible region into the objective function to see which ordered pair yields the maximum profit. The fundamental principle of linear programming provides a rule for determining the maximum or minimum value of an objective function used in a linear programming problem. Example 6 A System of Inequalities with Horizontal and Vertical Boundary Lines Graph the following system of inequalities and indicate the solution set. x y 2 3 ≥ − < Solution Graph the inequality x 2; ≥ − see Fig. 6.36(a). On the same axes, graph the inequality y 3; < see Fig. 6.36(b). The solution set is represented by the region of the graph that is shaded in both colors and the part of the solid blue line that satisfies the inequality y 3. < The point of intersection of the two lines, ( 2, 3), − is not part of the solution because it does not satisfy the inequality y 3. < x x > 22 y 1 2 23 24 25 21 1 2 3 4 5 21 22 y , 3 (22, 3) y 23 24 25 4 5 1 2 21 x 21 22 1 2 Solution x > 22 (a) (b) 22 22 3 Figure 6.36 7 Now try Exercise 37 Profile in Mathematics George B. Dantzig The simplex method, a technique used to solve linear programming problems, was developed by George B. Dantzig (1914–2005) in the 1940s. Dantzig’s career included implementing the simplex method on computers for the RAND Corporation and teaching operations research and computer science at Stanford University. His book, Linear Programming and Extensions , is considered one of the classic books on linear programming. As a graduate student at the University of California, Berkeley, Dantzig became legendary in the mathematics field for solving several problems he mistakenly thought were homework exercises. It turned out the problems were famous unsolved problems in mathematics. Graph of one constraint Vertices Graph of other constraint Feasible region Figure 6.37 Fundamental Principle of Linear Programming If the objective function, K Ax By, = + is evaluated at each point in a feasible region, the maximum and minimum values of the equation occur at vertices of the region.
RkJQdWJsaXNoZXIy NjM5ODQ=