842 CHAPTER 11 Systems of Equations and Inequalities Solution Figure 43(a) shows the graph of the constraints. We superimpose on this graph the graph of the objective function for the given values of I, as shown in Figure 43(b). For = I 0, the objective function is the line = +x y 0 0.02 0.03 . For = I 0.3, the objective function is the line = +x y 0.3 0.02 0.03 . For = I 0.45, the objective function is the line = +x y 0.45 0.02 0.03 . For = I 0.55, the objective function is the line = +x y 0.55 0.02 0.03 . For = I 0.6, the objective function is the line = +x y 0.6 0.02 0.03 . THEOREM Location of the Solution of a Linear Programming Problem • If a linear programming problem has a solution, it is located at a corner point of the graph of the feasible points. • If a linear programming problem has multiple solutions, at least one of them is located at a corner point of the graph of the feasible points. • In either case, the corresponding value of the objective function is unique. RECALL The graph of a system of linear inequalities is bounded if it can be enclosed by a circle of sufficiently large radius. j DEFINITION Solution to a Linear Programming Problem A solution to a linear programming problem consists of a feasible point that maximizes (or minimizes) the objective function, together with the corresponding value of the objective function. (b) x y 30 20 5 10 25 15 10 5 x 1 y 5 25 x 5 15 y 5 5 (20, 5) (15, 5) (15, 0) (25, 0) (in thousands) I 5 0.6 I 5 0.55 I 5 0.45 I 5 0.3 I 5 0 Figure 43 x y 30 20 5 10 25 15 10 5 x 1 y 5 25 x 5 15 y 5 5 (20, 5) (15, 5) (15, 0) (25, 0) (in thousands) (a) One condition for a linear programming problem in two variables to have a solution is that the graph of the feasible points be bounded. If none of the feasible points maximizes (or minimizes) the objective function or if there are no feasible points, the linear programming problem has no solution. Consider the linear programming problem posed in Example 2, and look again at Figure 43(b). The feasible points are the points that lie in the shaded region. For example, ( ) 20, 3 is a feasible point, as are ( ) 15, 5 , ( ) 20, 5 , ( ) 18, 4 , and so on. Identifying the solution of the problem requires finding a feasible point ( ) x y , that makes = + I x y 0.02 0.03 as large as possible. Notice that as I increases in value from = I 0 to = I 0.3 to = I 0.45 to = I 0.55 to = I 0.6, the result is a collection of parallel lines. Further, notice that the largest value of I that can be obtained using feasible points is = I 0.55, which corresponds to the line = +x y 0.55 0.02 0.03 . Any larger value of I results in a line that does not pass through any feasible points. Finally, notice that the feasible point that yields = I 0.55 is the point ( ) 20, 5 , a corner point.These observations form the basis of the following results, which are stated without proof.
RkJQdWJsaXNoZXIy NjM5ODQ=