Script

LINEAR PROGRAMMING – Graphical Approach

Slide 1

  • Welcome back.
  • In this module we present a graphical solution procedure for linear programs with two variables.

Slide 2

  • Linear programming models
  • with two variables can be solved using a graphical approach.
  • While there are few, if any, real life problems that can be expressed in only two variables ..
  • Using a graphical approach allows us to introduce some of the terminology and basic concepts that apply to larger models as well.

Slide 3

  • Here we present a 5 step approach for solving 2-variable linear programming models.
  • The first step is to graph both the non-negativity and functional constraints in the problem.
  • The resulting intersection is the set of possible or feasible values that satisfy all the constraints and hence is called the feasible region.
  • Then while we cannot graph a function, we can graph an equation, so we set the objective function equal to any value and graph this line.
  • Then we move or picture moving the line in the direction of higher values for the function (if it is a maximization problem or lower values if it is a minimization problem) until it touches the last point or points of the feasible region.
  • This last point touched is the optimal solution.
  • We then solve algebraically for the x and y values of that point.
  • This involves solving 2 equations in 2 unknowns.
  • And finally we solve for the optimal value of the objective function by
  • Substituting the values at the optimal point into the objective function.

Slide 4

  • So let’s employ this procedure for the Galaxy Industries model. Here is the constraint set we developed and as you can see we have already graphed the two non-negativity constraints represented by the shaded area – this is the entire first quadrant.

Slide 5

  • We now add the constraints one by one. Here we add the plastic constraint 2X1 + 1X2 ≤ 1000. With positive coefficients it is easy to draw the line by setting X1 = 0 and solving for X2 = 1000 – that’s one point on the line and setting X2 to 0 and solving for X1 = 500 that’s a second point on the line. We then draw the line that represents all the points where 2X1 + 1X2 = 1000. The “less than” part is on one side or the other of the line. While it is usually easy to tell which is the less than side, when there is doubt, substitute X1 = 0 and X2 = 0 into the expression – this gives 0 which is less than 1000. So the side that has 0,0 on it is the less than side. The triangular shaped area is now all the points that satisfy X1 ≥ 0, X2 ≥ 0, and 2X1 + 1X2 ≤ 1000.

Slide 6

  • Adding the production time constraint of 3X1 + 4X2 ≤ 2400 further reduces the set of feasible solutions to the quadrangle shown here.

Slide 7

  • Now adding the maximum production limit constraint, X1 + X2 ≤ 700, does not further reduce the set of possible solutions.
  • When this happens -- a constraint that can be removed without affecting the shape of the set of feasible solutions – this is called a redundant constraint. Redundant constraints can be theoretically removed from the problem formulation except that they may have an affect later on when sensitivity analyses are performed.

Slide 8

  • We now add the last constraint, the product mix constraint, X1 - X2 ≤ 350. This one is a little tougher to graph and to determine which side is the “less than” side. Of course when X2 is set to 0, X1 = 350. But when X1 is set to 0, X2 = -350 which is not shown here. That’s okay – instead of that, let’s take a larger value for X1, say 500 and solve for X2. In this case X2 would equal 150 so X1 = 350, X2 = 150 is a second point on the line. We can then connect and extend a line from (350, 0) through (500, 150). Then we use the technique of determining the “less than” side of substituting the values of X1 = 0 and X2 = 0. When we do this we see that the “less than” side is the area to the left of the line.
  • The resulting pentagon is the set of all possible or feasible points and is called the feasible region.

Slide 9

  • Before we go on, let’s introduce the terms we use to describe particular points in linear programming.
  • The point (200,700) lies outside the feasible region – it is infeasible – and hence is called an infeasible point.
  • The point (200,200) is in the middle or interior of the feasible region and is called an interior point.
  • The point (200,450) lies on one of the constraints that determines the boundary of the feasible region, It is called a boundary point.
  • And last we come to the most important points, extreme points, which are the points at the corners of the feasible region. They lie on two lines – that is they satisfy two of the constraints with equality. If we had a 3 variable problem an extreme point would have to satisfy 3 of the constraints with equality and so forth.

Slide 10

  • So we have now finished step 1 of our 5 step procedure – graphing the feasible region.
  • Now we go to step 2 – we set the objective function 8X1 + 5X2 equal to any number and graph it. Ideally we should choose a number so that the line will go through the middle of the feasible region.
  • Let’s set it to 2000 and graph the line. The thick blue line then gives all points that give an objective function value of 2000. Since there are points in the feasible region on this line, we know we can do no worse than an objective function value of 2000, because we have found some points that already give us this value.

Slide 11

  • To determine the optimal point
  • we picture moving the objective function line parallel to itself moving upward
  • This gives larger and larger values of the right hand side of 8X1 + 5X2. So we move the line parallel to itself until it touches the last point of the feasible region.

Slide 12

  • Here we see that this optimal point is at the intersection of the boundaries of the plastic equation 2X1 + X2 = 1000 and the production time equation 3X1 + 4X2 = 2400.
  • We now solve these two equations in 2 unknowns by any method we wish.
  • Here let’s multiply the top equation by 4 giving
  • 8X1 + 4X2 = 4000 and 3X1 + 4X2 = 2400.
  • Subtracting the second equation from the first gives
  • 5X1 = 1600. Dividing through by 5 gives X1 = 320.
  • We can now substitute this value into any equation we have considered – here we use the very first equation. So we have …
  • 2 times 320 plus X2 equals 1000 or 640 + X2 = 1000 or X2 = 360.
  • Thus the optimal point is X1 = 320, X2 = 360.

Slide 13

  • We now substitute these values into the objective function to determine the optimal profit.
  • 8 times 320 plus 5 times 360 is
  • 4360. You might note that this is the same solution and objective function value that we got solving the problem by Excel --- it better be!

Slide 14

  • Let’s review what we’ve done in this module.
  • We introduced the 5-step graphical procedure for solving linear programs having only two variables. The steps included
  • Graphing the constraints to get a feasible region
  • Setting the objective equal to some value and graphing it.
  • Moving the objective function line out until it touches the last point of the feasible region.
  • Solving 2 equations in 2 unknowns to determine the optimal point.
  • And substituting these values into to the objective function to determine its optimal value.
  • We illustrated the concept of a redundant constraint
  • And we classified points as being
  • Infeasible points
  • Interior points
  • Boundary points or
  • Extreme points.

That’s it for this module. Do any assigned homework and I’ll be back to talk to you again next time.