Graphing an LP Problem



Graphing an LP Problem

Q: What is the purpose of graphing an LP problem?

A: It helps us to organize the data, which is the first step of an algorithm.

D: We have already organized the data twice. The first time was when we set up a table to group the data from the word problem. The second time was when we set up the formulation. Graphing is a third way of organizing the data given in the word problem.

Q: Why should we graph LP problems if we have already organized the data twice?

A: The graph will help us to find the solution.

D: The table organized the data so we could see the connections between the pieces of the data. The formulation organized the data so it would be ready for the computer. The graph organizes the data for us, because most of humans can read a graph a lot better than we can a set of equations.

Q: Do most businesses use graphs to solve LP problems?

A: No, very few (I’m tempted to say “None.”).

Q: Then why do we have to learn to solve LP problems using graphs?

A: A graph will allow me to illustrate almost everything about the LP algorithm, which means you don’t have to learn all the calculations. I can either show you what is going on with a graph, or have you learn the math. Most students prefer the graphs.

Q: In that case, how do we get started graphing?

A: You begin with the formulation, shown next:

B ( # of bowls to make

C ( # of cups to make

Max Z = $2.20 B + $2.50 C

s.t. 1000 B + 500 C < 40,000 grams of clay

25 B + 50 C < 2,000 minutes - wheel

60 B + 60 C < 3,000 minutes – kiln

B, C > 0 non-negativity

Q: What next?

A: Draw the axes of the graph (properly called a Cartesian Coordinate system – see the note on René DesCarte if you are interested in learning why, and don’t mind one really bad pun) and labeling each axis with one of the variables from your problem, as in Figure 1 on the next page.

D: That should tell you why most businesses cannot use graphs to solve LP problems. Every decision variable must have its own axis, and that limits us to two decision variables. I suppose that with the right software we might be able to handle as many as three decision variables, but even so, I’ve never heard of a real-world problem with only three decision variables. Business problems start at about fifty variables, and often have more than 1,000. They also usually have at least twice as many constraints as variables, which would make them even more difficult to graph. The problems we will graph are deliberately simple, two variables, three to five constraints, but still complex enough to show everything you need to understand what is going on in the LP algorithm. Remember that the heart of

Figure 1: Axes Labeled for Variables B and C

an algorithm is repetition – which means that the only difference between a small problem and a big on is the number times you repeat everything.

Q: What does the graph represent?

A: All possible solutions to the LP problem.

D: Every point on the graph is a possible solution to the problem. The location of every point can be found by measuring along the two axes (this was DesCarte’s insight). For us, the axes are our variables, so the point (4, 3) translates into 4 on the horizontal axis (by convention, we always list the value on the horizontal axis first) which is our variable B and 3 on the vertical axis, our variable C. This is one possible solution to the problem.

Q: How many possible solutions are shown on the graph?

A: An infinite number.

Q: How long will it take us to check an infinite number of possible solutions?

A: It would take an infinite amount of time to check each of an infinite number of solutions, but fortunately we don’t have to do that. What we need to do is narrow down the number of solutions we need to look at.

Q: Why have you shown only the first quadrant of the graph?

A: We are interested in only the first quadrant because that is where all the values for the variables are positive. We are interested in only positive values for the variables because of the non-negativity constraints. That means that we have already eliminated a lot of the possible solutions, three-fourths of them to be precise.

Q: If we have discarded three-quarters of the solutions, how many are left?

A: Three-fourth’s of infinity is still infinity. Understanding things like that is why most mathematicians are so weird. I’m not really sure I understand how you can throw away ¾’s of something and still have just as much as you started with, but I can live with it.

Q: Is there anything we can do to eliminate even more of the possible solutions?

A: We could graph the constraint lines.

Q: How do we graph constraint lines?

A: One of two ways: the slope-intercept method or the two-intercepts method.

Q: Which is easier?

A: To my mind, the two-intercepts method is easier.

D: The slope-intercept method is probably the one you learned in algebra, where you put the equation in the form:

Y = mX + b

plot the intercept and then use the slope to find another point. The difficulty is that our equations aren’t in the proper form, so we have to do more work.

Q: How does the two-intercepts method work?

A: It starts by realizing two things: most constraint lines intersect both axes and one variable is equal to zero when the constraint intersects an axis.

Q: How can a constraint line miss the axes?

A: A constraint line can’t miss both axes, but it can miss one of them (it must intersect the other).

Q: What kind of constraint line intersects only one of the axes?

A: If the constraint line is a horizontal or vertical line it will miss the axis it is parallel to.

Q: How can you tell if a constraint is a horizontal or vertical line?

A: The constraint equation will have only one variable in it.

D: The constraint will intersect the axis for the variable it shows in the equation. It will be parallel to the axis for the variable that is not in the equation. To graph a horizontal or vertical line, simply find the one intercept and draw a line through that point and parallel to the other axis.

Q: How do you graph a constraint that does have both variables in it, so it does intercept both axes?

A: Set one variable equal to zero and calculate the intercept for the other variable. That is one point on the constraint line. Now set the other variable equal to zero, and find the intercept for the other axis. That is another point on the constraint line. Since you need only two points to draw a line, you can now draw the constraint line.

Q: Is that all there is to it?

A: Since constraints are usually inequalities (< or >), you must also shade one side of the constraint or the other.

Q: Is it true that you always shade below a < constraint and above a > constraint?

A: No.

D: That is only true if the constraint has a negative slope. Consider the following pair of constraints:

(a) X + Y < 2

(b) X – Y < 1

Constraint (a) has a negative slope and constraint (b) has a positive slope. The graph for this pair looks like Figure 2:

[pic]

Figure 2: Two < Constraints

Q: How should you shade constraint lines (a) and (b)?

A: Shade constraint line (a) down and constraint line (b) up.

Q: How can you tell?

A: Pick a point on the graph and use it to test the equation. If the point satisfies the equation (the result is true), shade the side of the line that includes that point. If the point does not satisfy the equation (the result is false) shade the side of the line that does not include the point.

Q: What point should we pick?

A: I recommend picking the origin (0, 0).

Q: Why should we use the origin?

A: It makes the math really easy. No matter what is on the left-hand side of the equation (the side with the variables), that side of the equation is reduced to zero. So you simply compare zero to the constraint limit.

Q: Does that mean a < constraint always shades toward the origin and a > constraint always shades away from the origin?

A: No, because the constraint limit might be negative. You must always check the equation by using the origin.

Q: Should we always use the origin?

A: Unless the constraint line goes through the origin, yes. If the constraint line goes through the origin, pick some other simple point, such as (1, 1), or any similar point that is not on the constraint line.

Q: How do we use all this to graph the constraints of the LP problem we showed earlier?

A: Take the first constraint (1000*B + 500*C < 40,000) and calculate the two intercepts by letting first B then C equal zero:

1000*0 + 500*C = 40,000

1000*B + 500*0 = 40,000

Solving the two equations for each variable gives you (0, 80) and (40, 0). Plot these two points on the axes, and connect them to form the constraint line, as shown in Figure 3:

Figure 3: Constraint 1 Graphed

When we check, 0 < 40,000 is true, so we shade toward the origin, as indicated by the arrow pointing from the constraint line down and left.

Q: How do we graph the remaining constraints?

A: Taking the remaining constraints one at a time, calculate the intercepts for each, plot them, draw the line, and test each line to see which side should be shaded. The intercepts for the second constraint are (80, 0) and (0, 40), while the intercepts for the third constraint are (50, 0) and (0, 50). For both constraints you shade toward the origin, giving us the graph in Figure 4:

Figure 4: Graph with Three Constraints

Q: Are we finished?

A: Except for graphing the objective, yes.

Q: How do you graph the objective?

A: That is explained in the lecture notes “Introduction to Constrained Optimization” so return to those notes and keep reading.

-----------------------

20

X

Y

Variable B

Variable B

Variable C

90

80

70

60

50

40

30

20

10

90

80

70

60

50

40

30

20

10

Variable C

3

2

1

Constraint (b)

-1

-2

-3

3

2

1

Constraint (a)

-1

-2

-3

90

80

70

60

50

40

30

20

10

90

80

70

60

50

40

30

10

Clay

Kiln

Wheel

Clay

Variable B

Variable C

90

80

70

60

50

40

30

20

10

90

80

70

60

50

40

30

Z´

10

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download