944 CHAPTER 9 Systems and Matrices x y (0, 0) 0 2000 2000 (0, 4000) (6000, 0) (8000, 0) (4000, 2000) (0, 6000) Region of feasible solutions x ≥ 0 y ≥ 0 x + y ≤ 6000 x + 2y ≤ 8000 Figure 21 Step 3 The problem may now be stated as follows: Find values of x and y in the region of feasible solutions as shown in Figure 21 that will produce the maximum possible value of 6x + 10y. It can be shown that any optimum value (maximum or minimum) will always occur at a vertex (or corner point) of the region of feasible solutions. The vertices are 10, 02, 10, 40002, 14000, 20002, and 16000, 02. Step4 To locate the point 1x, y2 that gives the maximum value, substitute the coordinates of the vertices into the objective function. See the table below. Find the number of people served that corresponds to each coordinate pair. Step 5 The vertex 14000, 20002 gives the maximum number. The maximum number of people served is 44,000, when 4000 medical kits and 2000 containers of water are sent. S Now Try Exercise 85. Vertex Number of People Served =6x +10y 10, 02 6102 + 10102 = 0 10, 40002 6102 + 10140002 = 40,000 14000, 20002 6140002 + 10120002 = 44,000 16000, 02 6160002 + 10102 = 36,000 44,000 is the maximum number. 0 Vertices are from Figure 21. To justify the procedure used in a linear programming problem, suppose that we wish to determine the values of x and y that maximize the objective function 30x + 70y with the constraints 10 … x … 50, 10 … y … 60, and y Ú x. Figure 22 shows this region of feasible solutions. To locate the point 1x, y2 that gives the maximum objective function value, add to the graph of Figure 22 lines corresponding to arbitrarily chosen values of 0, 1000, 3000, and 7000. 30x + 70y = 0 30x + 70y = 1000 30x + 70y = 3000 30x + 70y = 7000 x y (50, 60) (10, 60) (50, 50) (10, 10) 0 Region of feasible solutions Figure 22
RkJQdWJsaXNoZXIy NjM5ODQ=