A linear programming problem may be defined as the problem of maximizing or min- imizingalinear function subject to line arconstraints . The constraints maybe equalities or inequalities. Here is a simple example. Find numbers x 1 and x 2 that maximize the sum x 1 + x 2 subject to the constraints x 1 ? 0, x 2 ? 0, and x 1 +2 x 2 ? 4 4 x 1 +2 x 2 ? 12 ?x 1 + x 2 ? 1 In this problem there are two unknowns, and five constraints. All the constraints are inequalities and they are all linear in the sense that each involves an inequality in some linear function of the variables. The first two constraints, x 1 ? 0and x 2 ? 0, are special. These are called nonnegativity constraints and are often found in linear programming problems. The other constraints are then called the main constraints . The function to be maximized (or minimized) is called the objective function . Here, the objective function is x 1 + x 2 . Since there are only two variables, we can solve this problem by graphing the set of points in the plane that satisfies all the constraints (called the constraint set) and then finding which point of this set maximizes the value of the objective function. Each inequality constraint is satisfied by a half-plane of points, and the constraint set is the intersection of all the half-planes. In the present example, the constraint set is the five- sided figure shaded in Figure 1. We seek the point ( x 1 ,x 2 ), that achieves the maximum of x 1 + x 2 as ( x 1 ,x 2 ) ranges over this constraint set. The function x 1 + x 2 is constant on lines with slope ? 1, for example the line x 1 + x 2 =1, and as we move this line further from the origin up and to the right, the value of x 1 + x 2 increases. Therefore, we seek the line of slope ? 1thatis farthest from the origin and still touches the constraint set. This occurs at the intersection of the lines x 1 +2 x 2 =4 and4 x 1 +2 x 2 =12,namely, ( x 1 ,x 2 )=(8 / 3 , 2 / 3). The value of the objective function there is (8 / 3) + (2 / 3) =10 / 3. Exercises 1and 2 can be solved as above by graphing the feasible set…

Download LINEAR PROGRAMMING.Pdf