SECTION 11.8 Linear Programming 843 Steps for Solving a Linear Programming Problem Step 1 Assign symbols for the variables in the problem, and write an expression for the quantity to be maximized (or minimized). This expression is the objective function. Step 2 Write all the constraints as a system of linear inequalities. Step 3 Graph the system (the set of feasible points) and find the corner points. Step 4 Evaluate the objective function at each corner point. The largest (or smallest) of these is the solution. Solving a Minimum Linear Programming Problem Minimize the objective function = + z x y 2 3 subject to the constraints ≤ ≤ + ≥ ≥ ≥ y x x y x y 5 6 2 0 0 Solution EXAMPLE 3 Step 1 We want to minimize the objective function = + z x y 2 3 . Step 2 The constraints form the system of linear inequalities ≤ ≤ + ≥ ≥ ≥ ⎧ ⎨ ⎪⎪ ⎪⎪ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎪ y x x y x y 5 6 2 0 0 Step 3 The graph of this system (the set of feasible points) is shown as the shaded region plus the boundary lines in Figure 44. The corner points are labeled. Step 4 Table 1 lists the corner points and the corresponding values of the objective function. From the table, the minimum value of z is 4, and it occurs at the point ( ) 2, 0 . Figure 44 x y 24 7 22 (6, 5) (0, 5) (0, 2) 8 (2, 0) (6, 0) x 5 6 y 5 5 x 1 y 5 2 We do not consider linear programming problems that have no solution. As a result, we can outline the procedure for solving a linear programming problem as follows: Corner Point ( ) , x y Value of the Objective Function = + 2 3 z x y ( ) 0, 2 = ⋅ + ⋅ = z 2 0 3 2 6 ( ) 0, 5 = ⋅ + ⋅ = z 2 0 3 5 15 ( ) 6, 5 = ⋅ + ⋅ = z 2 6 3 5 27 ( ) 6, 0 = ⋅ + ⋅ = z 2 6 3 0 12 ( ) 2, 0 = ⋅ + ⋅ = z 2 2 3 0 4 Table 1 Now Work PROBLEMS 5 AND 11
RkJQdWJsaXNoZXIy NjM5ODQ=