The Art of Linear Programming

by
Jeffrey S. Kane, Ph.D., Professional Statistical Services

Over the last six years I have assisted numerous students enrolled in graduate level courses in quantitative methods for business. These courses used to be called Operations Research, but their preferred titles in current times include Management Science, Decision Methods for Business, Decision Modeling, or simply, Quantitative Methods for Business. These courses generally include such topics as:

• Linear Programming
• Transportation, Transshipment, and Assignment Problems
• Network Flow Problems
• Critical Path Modeling (i.e., CPM/PERT)
• Multicriteria Decision Making
• Queuing Analysis
• Simulation
• Forecasting and Time Series
• Inventory Management

Linear programming is a central component of these courses, and its fundamental approach to the optimization of an outcome under constraints extends to several other topics in such courses. My interest in this method grew as I encountered a wide range of problems that had been devised for these courses. It increased further as I began to receive requests from business organizations to solve very complex problems that turned out to be amenable to linear programming approaches. I didn't study this methodology in graduate school, and only decided to learn it when numerous students (typically in MBA programs) began to contact me in a state of bewilderment. Initially, I shared their bewilderment, but as I began to figure out more and more of these problems, I started to get good at it. I also came to an appreciation of the enormous power of this technique. It can produce optimal solutions to ridiculously complex problems that would be next to impossible to arrive at through trial and error. Moreover, the range of problems to which it can be applied is remarkable: product mix determination, material and equipment allocation, profit maximization, personnel allocation, to mention just a few.

After having worked with linear programming for the past 6 years, I thought I would share some observations that may prove helpful to others seeking to gain some proficiency with this method. These observations are rooted in a common theme that is expressed in the title of this article. Despite being a quantitative method that produces unique numeric solutions, it relies heavily on what I can only describe as an art. Specifically, it is the art of identifying key elements of a problem and structuring them in a manner that can be acted upon by a linear programming software tool that produces the solution. Surely the most widely used of these tools is Solver, the basic version of which is supplied with Microsoft Excel. This tool is great for producing the solution once you have a problem set up to run, but it provides no help in the setting-up process.

A variety of Excel templates have been offered to assist in the setting-up process, but all of the ones that I have tried (and there have been many) are good for only one type of LP problem and usually just lead to confusion when applied to problems that have a different structure. However, there is a basic conceptual framework that I have found useful. I will explain this framework and provide examples of the "art" that goes into the solution of linear programming problems.

I start by picking a cell in the top row of an Excel worksheet and putting the label "Objective Function" next to it. This is the cell in which the value that you are trying to minimize or maximize is expressed. The value in this cell is always determined by a formula (i.e., an expression following an equal sign in Excel). It can be the total value of sales, the total value of loss, the total value of production, the total number of people hired -- the possibilities are nearly limitless. The point is that it is ultimate outcome of whatever problem you are seeking to solve using linear programming.

The formula for the objective function will be a linear composite, meaning that it will be the sum of the products of the quantities of some variables and the values per unit of the respective variables. This will always be the case in linear programming; in nonlinear programming the formula will be a nonlinear function of the values of the variables. Don't put anything in the objective function cell yet until you have identified the variables on which the objective function is based.

The variables on which the value of the objective function is based are called "decision variables". Each of these variables refers to a type input that contributes to the value of the objective function. The first step in the process of setting up any linear programming problem is to specify these decision variables. Let's look at an example.

Wineco produces wine coolers and sells them to retail distributors. One popular blend consists of wine, apple juice, and grape juice. Operators must adhere to certain guidelines when preparing the wine cooler:

A. At least 10 percent of the mix must be grape juice.

B. The ratio of apple juice to grape juice must be 2 1/2:1.

C. The mix must contain between 20 percent and 25 percent wine.

The company pays $1.20 per gallon for wine, $1.40 per gallon for grape juice, and $.60 per gallon for apple juice. Formulate and solve an LP model that will help the owner to determine how much wine cooler to mix each day if the capacity of the mixing equipment is 200 gallons per day and the wine cooler is sold for $4 a gallon. The owner wants to maximize profits. Ignore mixing and bottling costs.

The objective function in this problem refers to the profit that will be made per day. The decision variables -- the variables for which quantities will be determined -- are wine, grape juice, and apple juice. The objective function and decision variables can be arranged as follows on an Excel worksheet:

The Decision Variables:

The table above shows the three decision variables -- wine, grape juice, and apple juice -- which are the inputs to the wine cooler production process. In the column to the right of each of these 3 decision variables is the cost per gallon of each of these inputs. The column headed, # Gallons, contains a question mark to the right of the Cost/Gallon of each decision variable. These are the quantities to be determined by the linear programming process. The question marks are only there for the purpose of this explanation of how to set-up the problem; in actual use you would leave these spaces blank.

The column headed, Total cost/DV, contains formulas that express for each of the three decision variables the product of the number of gallons to be used and the cost per gallon.

The Totals/day Values:

The sum of the number of gallons that will be determined for the three decision variables is in the bottom row of the # Gallons column next to the label, Totals/day. This quantity should in theory be 200, since that is the maximum daily capacity of the mixing equipment. However, rather than just assuming that the amounts will have to sum to 200, we have to allow for the possibility that the constraints may limit the maximum amount that can be produced to something less than 200 gallons. So a formula for the sum of the numbers of gallons of each decision variable to be used per day is entered for the total of the # Gallons column.

The sum of the 3 Total cost/DV values is entered in the bottom row of that column (i.e., cell D8 above). This total is a very important quantity for this problem because its value will determine how much profit can be made each day.

The Objective Function:

To determine the formula to be entered into the space for the objective function, we have to know how profit is arrived at. By the time you're learning about linear programming, you should be aware that profit (or loss) is the difference between revenue and cost. In the present case, we know that the selling price for Wineco's wine coolers is $4.00 per gallon. The revenue earned from selling a day's production of wine coolers is therefore $4.00 times the total number of gallons produced (we are assuming in this problem that all of the gallons of wine cooler that can be produced can be sold.) The total number of gallons that will be produced appears as the sum of number of gallons of each of the decision variables in cell C8. Thus, the total revenue on any day will be equal to the product of C8 times $4.00. The total costs are equal to the sum of the costs of the amounts of each of the inputs (i.e., decision variables; cells D4, D5, and D6). This total appears in cell D8. To get total daily profit, we subtract D8 from the product of C8 times $4.00. This is expressed as the formula: = (C8 * 4) - D8, which is the formula that appears in the Objective Function cell.

The Constraints:

If all it took to set up a linear programming problem were the steps I've described up to this point, it would be a breeze. What makes this method a bit trickier is that we have to arrive at a combination that not only maximizes or minimizes the objective function, but also conforms to various other requirements that the situation imposes on the solution. These other requirements are call constraints. Identifying and expressing these constraints is one of the areas in which the conceptual process becomes more "artistic" than purely technical. This is demonstrated by the constraints that should be identified for the above problem, as follows:

1.The mix must contain at least 20% wine.

2.The mix must contain no more than 25% wine.

3.At least 10% of the mix must be grape juice.

4.The ratio of grape juice to apple juice must be (exactly) 2.5 to 1.

5.The sum of the amounts of each ingredient must not exceed 200.

6.Since the product is sold by the gallon, the total number of gallons produced must be an integer number, since any odd amount will be left unbottled and unsold, and therefore wasted.

The first five of these constraints come straight from the problem statement and are easy to understand. We can express them as follows:

The statements of these first five constraints are simply transformations of the verbal statements of the constraints into logical expressions. However, in the case of the sixth constraint, we run into a problem. One of the options in Solver is to limit a number to an integer value, meaning that it can only be a whole number without a fractional part. However, if we try to specify in the constraints section of Solver that the total number of gallons produced must be an integer, we get an error message. This message says that the requirement for a number to be an integer can only be imposed on the value of a decision variable. Since the total number of gallons produced is not one of the decision variables, but rather only the sum of the quantities assigned to a decision variable, the integer constraint cannot be imposed directly on its value. To achieve this constraint, we must find another way to do it.

We can achieve the restriction of total gallons produced to an integer value in the following manner. Underneath the Objective Function create the following entry:

The formula in cell G8 creates a number equal to the actual total number of gallons with any fractional part removed. All that remains is to specify the following additional constraint:

Browse the best online HTML tools: editor, tags, cheat sheet, character codes, tag generators, website templates and more.

This will have the effect of forcing Solver to keep rejecting solutions until the Total Number of Gallons is a pure integer with no fractional part.

Entering the address of the cell with the Objective Function formula, the Decision Variable cell addresses, and the constraints specified above into Solver will produce the optimum solution to the problem. This illustrates how linear programming problems – even seemingly simple ones -- commonly push the analyst to devise novel workarounds to produce optimal solutions. Excel has numerous ways of coordinating results between cells, and exploiting these capabilities is one way to employ one's creativity in the application of linear programming.

A Second Type of Linear Programming Artfulness

The example presented above illustrates one general type of demand for creativity or artfulness that linear programming can impose – specifically, finding ways express constraints by exploiting Excel's capabilities. A second type of demand arises when a problem is insufficiently explicit about what would constitute an optimal solution. Here again, an example will best illustrate this particular demand for creative insight. Consider this problem:

A forest fire is burning down a narrow valley 3 miles wide at a speed of 40 feet per minute. The fire can be contained by cutting a firebreak through the forest across the valley. It takes 30 seconds for one person to clear one foot of the firebreak. The value of the lost timber is $4,000 per square mile. Each person hired is paid $12 per hour, and it costs $30 to transport and supply each person with the appropriate equipment.

Develop a model for determining how many people should be sent to contain the fire and for determining the best location for the firebreak.

As this problem is stated, we could hire 7920 firefighters and have them each work for 1 minute and the firebreak would be complete. It takes a certain amount of creativity, or at least willingness to go beyond the stated facts, to recognize that there must be some principle for establishing a more reasonable upper limit to the number of firefighters to employ in this task. This principle is that each additional unit of a resource to be used to solve a problem should not cost more than the value of the damage that would be averted by adding that unit of the resource. In the context of the present problem, this means that additional firefighters should be hired to help cut the firebreak as long as the cost of each additional firefighter does not exceed the value of the timber that would be saved by hiring him/her. Recognizing this principle allows us to establish a constraint on the number of firefighters that should be hired.

The full set-up for the solution to this problem consequently appears as follows:

	A	B
1	Objective Function	=B12/B4	(minutes needed to cut firebreak)
2
3	Decision variables:
4	Number of firefighters:	2	(starting value = 2)
5
6	Relevant Variables:
7	Feet of firebreak to cut:	15840
8	Cost per foot to cut:	0.1	(=$12.00/120)
9	Hourly pay cost to cut firebreak:	1584	(= b8 * b7)
10	Cost per firefighter:	30
11	Cost per minute of burn:	$90.91
12	Person minutes to cut firebreak:	7920	(= 15840/2) loss of timber would equal 7920 * $90.91 = $720,000 if one firefighter were used
13	Total cost of firefighters:	=(30*B4) + B9
14	Total cost of burn:	=(B12/B4) * B11
15	Prev. Value of Timber Saved	=720000 – ((7920/(B4 -1)) * 90.91)
16	Current value of timber saved:	=720000 – ((7920/(B4)) * 90.91)
17	Incremental Value of Timber Saved:	=B16 – B15
18	Cost of last firefighter hired:	= 30 + ((B7/(B4 * 2)) *0.2)
19
20	Constraints:	LHS	Constraint	RHS
21	B18	<=	B17
22	B4	EQ	Integer
23	B4	>=	2
24
25	Where to cut firebreak:	=ROUNDUP(B14,0) * 40	feet from current position of fire

This problem illustrates not only that it is often necessary to use one's creativity to devise reasonable constraints on the solution to an LP problem, but also that it is necessary equally often to utilize the given data in creative ways to produce the numbers that actually implement the constraints that one has devised.

A More Extreme Challenge to LP Creativity

Sometimes a problem is encountered that just doesn't look like a typical LP problem. It may require that costs be minimized or profit maximized, but the constraints do not seem capable of being expressed in conventional ways. The following problem is an excellent example of this kind of brain twister:

Market Research Corporation of Toledo Inc. (MRCT) has to finalize its recommendation for the 2006 advertising campaign for Miracle Motors Inc. (MMI), a major hydrogen-powered automobile manufacturer. MRCT has developed 5 distinct campaigns for MM Inc. MM Inc. has 7 distinct customer segments, and it wants all of its customers to be "hit" by at least one of its campaigns. It wants to minimize the total cost of reaching its customer base through these campaigns. The chart below depicts the cost and customers hit by each of the five campaigns MRCT has developed for MMI.

	B	C	D	E	F	G	H	I
1	Objective Function: Minimum Cost
2	=SUMPRODUCT(C13:G13,C15:G15)
3
4	Campaign
5	Customer	1	2	3	4	5	Customer Hit?
6	1	1	1	0	0	1	=IF(C15=1,0,IF(D15= 1,0, IF(G15=1,0,1)))
7	2	0	1	0	0	0	=IF(D15=1,0,1)
8	3	0	0	1	1	0	=IF(E15=1,0,IF(F15= 1,0,1))
9	4	1	0	0	0	1	=IF(C15=1,0,IF(G15= 1,0,1))
10	5	0	0	1	0	1	=IF(E15=1,0,IF(G15= 1,0,1))
11	6	0	0	0	1	1	=IF(F15=1,0,IF(G15= 1,0,1))
12	7	0	0	1	1	0	=IF(E15=1,0,IF(F15 = 1,0,1))
13	Campaign Cost:	$12,000	$15,000	$30,000	$20,000	$10,000	SUM OF HITS:	=SUM(I6:I12)
14
15	Selected:	0	0	0	0	0
16
17	Constraints:
18	c15:g15	=	binary
19	I6:I12	=	0
20	I13	=	0

I solved this by first transposing the original table so that I had 7 rows of customers and 5 columns of campaigns. The 5 binary (i.e., can take values of 0 or 1) decision variables are highlighted in yellow under the campaign columns. The key to this solution is the Customer Hit? column. Each of the seven cells under this column represents the status of a customer. Each of these cells is linked by a formula to the decision variables in such a way that if any of the campaigns are selected that "hit" the customer that the cell represents, the cell's value becomes zero. A solution is reached only when all the cells, representing all seven of the customers, have values of zero. As a double check on this, the sum of these seven cells must also be zero in order for the solution to be accepted. Both of these requirements are represented in the constraints, along with the binary nature of the decision variables.

The objective function is the sum of the products of the selected campaigns and their costs.

As far as I can determine, the only way to set up this problem for solution by linear programming is the approach I have described. This involves setting up a rather complex system of detecting which customers have been "hit" and which remain to be "hit' at each step of the process. There is nothing in the statement of this problem that hints at the complexity of the set-up that is required to solve it. This particular problem can be solved without using LP, but the problem illustrates the kind of creative set-ups that must be devised in order to solve more complex problems that can only be solved by the use of LP.

Conclusion

This paper has sought to convey the extra dimension of skill, cleverness, artistry, creativity, or whatever else you might want to call it, that is called into play by linear programming problems. Most texts on linear programming or quantitative business methods avoid mentioning this additional element of the capability to use LP to solve these constrained optimization problems. This is actually a disservice to students, because it implies that these problems can be solved by merely following a set of steps to reach the solution. When students hit a brick wall in trying to solve such problems in a cookbook manner, their confidence in their ability to make the "system" work can be shaken.

The truth is that linear programming is not a cookbook method, and the only way to become competent at it is to gain experience in using it to solve numerous problems differing widely in the kinds of set-ups they require. This is a slow process, and some people are going to acquire much greater facility with the method than others due to differences in the aptitudes that this method calls upon.

What is really a bit scary about the kinds of problems that LP addresses is that no matter how successful you've been in using LP to solve problems, the next problem you confront may defy your best efforts to get a handle on it. For this reason, it is useful to have people like me available who may be able to offer suggestions or insights that can help you break through the conceptual stumbling blocks that are thwarting you efforts to set up the problem so that it can be solved.