Introduction to the Linear Programming Algorithm
Q: Is this going to hurt?
A: I’ll make it as painless as possible.
Q: Where do we start?
A: With the outline for a search algorithm:
1. organize your data
2. set up an initial solution
3. identify search directions
4. evaluate search directions
5. select the best and generate a new solution
6. repeat, until…
Q: What else do we need?
A: We need the word problem we were working on before.
Q: Didn’t we already solve that problem?
A: We solved it using a graph, but a graph is not a particularly good solution technique.
Q: What’s wrong with using a graph?
A: It is limited to problems having only two variables, and very few problems have only two variables.
Q: Then why did you make us learn how to graph a problem?
A: I am going to use the graph to illustrate all the calculations, but if don’t know how to read a graph you will have a hard time following my explanations. Here, I have copied word problem for you:
You run a small pottery business, making ceramic bowls ($2.20 profit) and cups ($2.50 profit). Your only raw material is the clay you use. A cup uses 500 grams of clay, while a bowl uses 1 & 1/4 kilograms. It takes you 25 minutes to shape a bowl on your wheel and 45 minutes to shape a cup. A bowl must be “fired” for an hour and a cup for 48minutes in your kiln, which can hold 2 items at a time. You have on hand 40 kilograms of clay and you expect to put in 30 hours at the wheel next week. The kiln must be preheated every day, so it is available only 20 hours per week. Set up your production plan for next week.
Q: Are we ready to start the algorithm?
A: Yes.
Q: How do we organize the data?
A: Two ways: first by formulation and then by drawing the graph. I have copied both of these for you as Figures 1 and 2 at the top of the next page. Technically speaking, drawing the graph is not a normal part of organizing the data, but we will need it for this lecture, so I am including it here.
Q: Why do we need it?
A: I am going to illustrate each step of the solution process on the graph, hopefully making it easier for you to follow what I am doing.
B º # of bowls to make
C º # of cups to make
Max Z = $2.20 B + $2.50 C
s.t. 1250 B + 500 C < 40,000 grams of clay
25 B + 45 C < 1,800 minutes - wheel
60 B + 48 C < 2,400 minutes – kiln
B, C, > 0 non-negativity
Figure 1: Problem Formulation
Figure 2: Graph of Problem
Q: Is this the same graph we used before?
A: In essence, yes, but I have removed the objective function line and added numbers to indicate the four corner points.
Q: Are we ready to start?
A: Not quite. We need to re-write the formulation to include some auxiliary, or supplemental, variables.
Q: Why do we need these other variables?
A: They make the solution process easier to understand, and serve a definite purpose when interpreting the output.
Q: How do we include the new variables?
A: We use them to convert the constraints from inequalities (<) to equalities without changing the meaning of the equations. To understand this, take the first constraint equation and put its components into words:
1250 B + 500 C < 40,000 grams of clay
Q: How would you put into words the right-hand side of the equation: 40,000 grams of clay?
A: There are 40,000 grams of clay available to use.
Q: Why did you underline “available to use?”
A: To set up the next question.
Q: How do we use clay?
A: By making bowls and cups.
Q: How many bowls are we going to make?
A: Ummmm…
D: That’s the answer I usually get. I also get guesses, such as 1250 (mistaking the coefficient for a value) and 40,000 (confusing the constraint limit with the value), but the sad part is that the answer was given to you earlier in this lecture.
Q: So, how many bowls are we going to make?
A: B
Q: B?
A: Yes, B. The variable B is defined as the number of bowls to make. Therefore, if I want to know how many bowls I am going to make, I can use the variable to answer that question.
Q: How can you do that? I thought you were looking for a number.
A: I was, and a variable is a number (go back to the lecture notes on formulating if you don’t remember that). Most of you don’t believe that variables are numbers, but you need to.
Q: Ok, fine, so we are making B bowls. How does that help?
A: We’ll use that information to answer the next question.
Q: How would you put the left-hand side of the equation into words?
A: That is a little trickier, so let’s take it in pieces.
Q: OK, what does the variable B stand for?
A: It is the number of bowls to make.
Q: Good, and what about its coefficient 1250?
A: That is the number of grams used to make one bowl.
Q: Good, so how do you put 1250*B into words?
A: That would be the total grams of clay used to make bowls.
Q: And how would you put 500*C into words?
A: That is the total grams of clay used to make cups.
Q: So how would you put the entire left-hand side of the equation, 1250*B + 500*C, into words?
A: The total grams of clay used to …
Q: Stop right there, with the word “used.” Now taking the two parts, left-hand side and right-hand side, how would you put the whole equation into words?
A: Grams of clay used must be less than or equal to grams of clay available to use.
Q: I said earlier we wanted to use the new variables to turn the constraints into equalities, so let’s start: How would your words read for an equality constraint?
A: Grams of clay used must be equal to grams of clay available.
Q: Does that statement say the same thing as the previous one?
A: Not even close. The first says you don’t have to use all the clay, but the second one says you do have to use all the clay.
Q: How could we change the second statement, leaving it as an equality constraint, so that it means the same thing as the first statement?
A: Well, the first statement allows there to be some unused clay, so how about:
grams of clay used plus grams of clay not used must be equal to grams of clay available.
Q: See why I emphasized “available to use?” So, how many grams of clay will be left over – unused?
A: We don’t know. That will depend on how many grams of clay are used.
Q: If there is a number we want to know, but we don’t have a precise value for it, what do we use?
A: A variable.
D: Good. We will call this type of variable, one representing unused resources, a “slack” variable, since it represents slack (unused) resources.
Q: Do we do this for all constraints?
A: All < constraints, because all < constraints can be interpreted as resources (though sometimes it’s a bit of a stretch), so they can have leftover resources.
Q: What do we do for a > constraint?
A: Well, let’s make up a > constraint. Suppose you have a standing order (an order that is placed every week) for five items from a local shop. That means you must make at least a total of five items, and maybe more. The equation for this would be as shown at the top of the next page.
B + C > 5
This time, the right-hand side of the equation is the minimum amount we need (rather than the maximum amount we can use, as with the < constraints) and the left-hand side is the amount we have to meet (or exceed) the minimum.
Q: How do we insert the supplementary variable?
A: Again, start by converting the equation to words, then to an equality and then make whatever changes are needed so the equality constraint means the same as the original constraint, like this:
B + C > 5
is the same as
units made must be greater than or equal to the minimum number ordered.
which as an equality would be
units made must be equal to the minimum number ordered
which is wrong. To make it mean the same as the original constraint, we could write:
units made minus units not ordered must be equal to the minimum numbered ordered.
Q: What was different this time?
A: You said “minus.”
Q: So how many units will be surplus – unsold?
A: We don’t know; that would be the slack variable.
Q: Doesn’t a slack variable represent unused resources?
A: Yes.
Q: Can we use a slack variable here?
A: No, because we are not dealing with a resources (maximum available) constraint; we are dealing with a contract (minimum required) constraint.
Q: What kind of variable do we use for a contract constraint?
A: We use a “surplus” variable, to represent the surplus amount that has been produced.
D: Actually, I really don’t like the terms “slack” and “surplus” because it is too easy to get them confused. Unfortunately, nobody really much cares what I think (except, of course, my students), so we are stuck with them.
Q: Can you summarize the difference between a slack variable and a surplus variable?
A: A slack variable is added to the left-hand side of a <-constraint. A <-constraint is a maximum (upper) limit and the slack variable represents the how much is leftover, unused. A surplus variable is subtracted from the left-hand side of a >-constraint. A >-constraint is a minimum (lower) limit and the surplus variable represents how much we have exceeded, surpassed, the limit.
Q: Are we ready to re-write the formulation?
A: Yes, and it would look like:
Max Z = $2.20 B + $2.50 C + 0 S1 + 0 S2 + 0 S3
s.t. 1250 B + 500 C + S1 = 40,000 grams of clay
25 B + 45 C + S2 = 1,800 minutes - wheel
60 B + 48 C + S3 = 2,400 minutes – kiln
B, C, S1, S2, S3 > 0 non-negativity
Figure 3: Problem Formulation Re-written
Q: Now, are we ready to start the algorithm?
A: Yes, but there are two things I would like you to notice. One is that the slack variables are listed in the non-negativity constraints. The other is that the slack variables are listed in the objective with a profit of zero.
Q: Why do the slack variables have a profit of zero?
A: They represent leftover resources, and resources (raw materials) left sitting in your warehouse contribute nothing to total profit.
Q: Should the slack variables have a negative profit, showing the cost of storing idle inventory?
A: You can do that, or you can argue that idle inventory is part of overhead, which is a fixed cost and has no part of decision making. Most of the time we simply leave the profit as zero.
Q: What do we do next in the algorithm?
A: We’ve organized the data, so we need to come up with an initial solution.
Q: Do we use the Northwest Corner method, as we did in the Transportation Algorithm?
A: No.
Q: Do we get to choose one of a bunch of different starting solutions?
A: No, we will always use the same starting solution.
Q: Is that because it is the best starting solution?
A: Not the best, necessarily, but certainly the most convenient, and is it is very easy to calculate.
Q: What is the initial solution?
A: The origin.
Q: You mean where the axes cross?
A: Right, where B and C are both equal to zero.
Q: Why do we start there?
A: Well, one answer is because it is literally correct. We are planning how much to make and right now we haven’t made anything. The more important reason, though, is that the origin is a corner point.
Q: What’s a corner point?
A: You may remember from the “Introduction to Graphing” lecture notes that a corner point is where two (or more) constraints intersect.
Q: Isn’t the optimal solution always found on a corner point?
A: Yes, it is, and that’s another part of the reason we start at the origin.
Q: So, what’s the whole explanation of why we start at the origin?
A: Begin with the fact that the optimal solution will always be at a corner point. It is also true that it easy (mathematically) to move from a corner point to another corner point, but very hard to move from a non-corner point to a corner point. That tells us that, if at all possible, we would like to start on a corner point. That brings up a new problem, though. If corner points are defined by the constraints, and the constraints are different for every problem, then the corner points are different for every problem.
Q: Couldn’t we just pick any two constraints and find their intersection?
A: You could, but then you wouldn’t know whether to search up or down (further from the origin or closer to it). The origin has two great properties: it is always a corner point (intersection of constraint lines) and …
Q: Which two constraints intersect at the origin?
A: The non-negativity constraints, which are a part of every problem. …and it is the lowest point in the first quadrant, where all our solution will lie, so we know to search up (further from the origin) for the optimal solution.
Q: OK, so the origin is always our initial solution. What do we do next?
A: Identify and evaluate search directions.
Q: What do we use for the search directions?
A: Something similar to what we used in the Transportation algorithm.
Q: Something similar to an empty route?
A: Yes. We looked at the empty routes to see if bringing them into use would save us any money. What we need is something that we can move from a value of zero to a positive value and in doing so, improve the objective value.
Q: Don’t some of the variables have a value of zero?
A: Yes, the two decision variables, B and C, have values of zero because the current solution point is the origin. At the origin, all decision variables have a value of zero.