Return to Decision Line Home Page
Return to DSI Home Page

PRODUCTION/OPERATIONS MANAGEMENT

KEONG LEONG, Feature Editor, Fisher College of Business,
The Ohio State University

My Operations Management Students Love Linear Programming

by Rohit Verma, Department of Management, DePaul University

My operations management students love linear programming. Really, they do! I have been teaching linear programming (LP) as part of the required MBA and undergraduate level operations management (OM) classes at DePaul for the last two years (and once at Helsinki School of Business and Economics) and, believe it or not, almost every student loved it. In fact, I have received several very positive comments on my teaching evaluations related to the LP class. One student even mentioned that it was the most interesting, applied and relevant technique he learned in the MBA program!

Most of DePaul MBA students are employed full-time in professional careers and take classes in the evening. The educational and professional background of our students varies greatly in terms of the length of work experience, the industry they are employed in, and undergraduate major. For example, our MBA students are employed in First Chicago/NBD, Arthur Anderson, Motorola, Lucent Technologies, US Robotics, Abbott Labs, ComEd, Ameritech, US Postal Service and a number of small manufacturing and service firms located in the Greater Chicago area. Formal/informal surveys conducted within the business school show that our students (and their employers) want us to teach them applied skills that can be incorporated in their jobs.

As business school (and especially OM) professors, we worry about the relevance of classroom teaching, about decreasing interest of students in our classes and about decreasing student enrollment. We also worry about the "optimum" mix of qualitative concepts and quantitative techniques that should be taught as part of introductory level OM classes for undergraduate and MBA classes. I know that several of my OM colleagues feel that LP is not necessary for introductory level OM classes. The purpose here is not to start a philosophical debate, but to present an approach for teaching LP in introductory OM classes. The reader can make his/her own judgment about the relevance of mathematical programming in their OM courses.

Multidisciplinary Approach

I spend approximately 3-4 hours on LP in a required 4.0 credit-hour OM course. The session starts with some general examples related to the use of LP in business application (for example, scheduling airlines, investment strategy for mutual funds, and production mix). This introduction generally leads to a good discussion on the multiple constraints present in businesses. For example, expensive resources, limited landing-takeoff slots available at major airports, staff scheduling, fuel requirements, flight times, number of seats in airplanes and customer demand are a few of the issues raised by the students for the airline scheduling problem. Since most of the undergraduate students do not have managerial experience, I show "The Overview of Management Science" video (approx. 25 minutes) which is the first part of the "For All Practical Purposes" series (COMAP/Allyn and Bacon, 1988) as an introduction to LP in undergraduate OM classes.

During the most recent LP session (for the MBA-level OM course) we conducted an "exploratory" group exercise. The class (approx. 40 students) was divided into ten groups and the students brainstormed to come up with ideas for solving the LP problems at hand. The groups had approx. 15 minutes to come up with a solution for one of the following types of problems: (1) production mix, (2) staff shift scheduling, (3) mutual fund investment, (4) advertising strategy, and (5) transportation. The group-exercise was extremely successful (much more than I had expected) in facilitating student comprehension of the complex and inter-related nature of the types of problems addressed by LP. Later I observed that the class participation during the formal LP formulation of the problems was higher than previous LP sessions.

The exploratory discussion helps get the students excited about learning the method(s) for solving constrained-optimization problems. Some students remember two-variable LP from their undergraduate courses, but a majority of them are not sure how to proceed and obtain the "optimum" solution. This sets the stage for formulating the problems formally as LP. We start by examining the product mix problem with two variables, three production constraints and two marketing constraints. We set up the problem together and solve it graphically. The coefficients for the objective function and constraints are chosen such that they easily lead to the identification of a feasible solution region and the corner points. Then I briefly present the differences between binding and non-binding constraints (I must admit that the difference is not very clear to several students at this time). We also discuss how the problem can be solved if there are three or more variables.

Use of Spreadsheets

After the break, we continue the discussion on solving an LP problem involving multiple variables. Since most of my students are working professionals and use spreadsheets (mostly Microsoft Excel) in their jobs, we use the Solver module in Excel to solve a sample LP problem. I have prepared a detailed hint sheet for solving LP using Excel (see Appendix). It takes about 15-20 minutes to go through all the steps presented in the Appendix. We then spend another 30 minutes or so going through the sensitivity analysis report (at this point the binding and non-binding constraints concept is a lot clearer). Several students get very excited about the shadow price concept and its impact on the objective function. Sometimes I lead the discussion by asking a question related to the objective function coefficients and/or constraints; however, most of the time students ask questions and facilitate the discussion.

For the remaining 45-50 minutes we formulate three or four more LP problems. The first problem involves finding investments that maximizes the rate-of-return for a mutual fund while incorporating investment in various stocks in three different industries. The constraints deal with the expected risk levels and the Mutual Fund guidelines regarding investment in different industries. Next we formulate one of the following types of marketing research problem: (1) cost minimizing advertising strategy; (2) cost minimizing interview (with households with predetermined demographic characteristics) scheduling problem. The last two problems discussed are the standard transportation problem and a labor shift-scheduling problem.

Assignments

The students are assigned two LP problems to solve using Excel: (1) a product-mix problem (similar to the first problem discussed in class); and (2) any one of the other problems formulated in class. I assign a few follow-up questions based on the sensitivity analysis for each of the problems assigned. Generally, most of the students have no difficulty setting up and solving the problems using Excel. Common difficulties include the following: (1) the Solver module in Excel is not installed on their PC; (2) wrong answers because of input error; and (3) Solver is unable to solve the problemþoften because they might have entered some non-numeric character in the cells representing the decision variables or because they forgot to put an = before some equation and, therefore, Excel failed to recognize the equation. However most of the problems are minor in nature and can be fixed easily. We spend 15-30 minutes during the following class session discussing the printouts for the assigned problems.

Why It Works?

I think the students like the use of LP in my OM classes for three main reasons. First, use of multidisciplinary approach to teaching LP. The discussion of finance, marketing and transportation problems (in addition to product mix and scheduling) effectively demonstrates the wide applicability of LP models in day-to-day business operations. Second, use of spreadsheets. Building spreadsheet LP models is relatively easy and intuitive for the students and enhances their current spreadsheet skills (refer to Plane, 1994, 1997, for further discussions on the use of spreadsheets in OM classes). The third reason is that LP concepts are fully integrated with the rest of the topics covered in the course. For example, one of the assignments for the course is to write a book report on The Goal (Goldratt and Cox, 1992). It is not difficult to identify the similarities between the "binding constraints" of LP and "bottlenecks" described in The Goal. Similarly "critical path" in PERT/CPM analyses can also be explained in terms of binding and non-binding constraints.

As I mentioned earlier, sensitivity analysis and post-optimal analysis generally leads to a very interesting discussion in the classroom. For example, during one of the sessions, a student asked if it is good managerial practice to always operate around optimum? That question led to an interesting discussion about the stochastic nature of business problems, the nature of "upper and lower bounds" of LP solutions, and the assumptions of mathematical modeling (see Clauss, 1997, for more discussion on the above issues). I finished the discussion by pointing out that all of the models are just an abstraction of reality and not reality itself.

The discussion of LP in my OM classes has worked well. The students learn a valuable technique which they can apply in their jobs. At the very least, they feel more confident about using mathematical techniques for solving "real life" business problems. For example, a couple of months ago I met a student from the Autumn 95 class who currently works as a manager of a 24-hour photocopy shop. He used LP to schedule the labor force for his store and was able to reduce labor-costs by 15%.

Acknowledgments

I would like to thank Quality of Instruction Council, DePaul University, for providing a grant for developing and incorporating spreadsheet-based techniques in operations management classes. I would also like to thank Ken Boyer for providing feedback on the earlier draft of this write-up.

References

COMAP/Allyn and Bacon Video in Decision Sciences (1988). Overview of Management Science. Produced by The Consortium for Mathematics and Its Applications (with major funding by the Annenberg/CPB Project).

Clauss, F.J. (1997). The Trouble With Optimal. OR/MS Today, February, 32-35.

Goldratt, E.M. and Cox, J. (1992). The Goal: A Process of Ongoing Improvement, second revised edition, North River Press, Croton-on-Hudson, New York.

Plane, D.R. (1994). Spreadsheet Power. OR/MS Today, December, 32-38.

Plane, D.R. (1997). How to Build Spreadsheet Models for Production and Operations Management. OR/MS Today, February, 50-54.

Appendix: Solving Linear Programming Problems Using Excel Solver

Sample Problem

Fashionable Bikes Inc. (FBI) has the hottest new product on the upscale toy marketþhigh quality boys and girls bikes in bright fashion colors. Due to seller's market for high-quality toys for the newest baby boomers, FBI can sell bikes at the following profit margin: boys' bikes -- $30, girls' bikes -- $50. The marketing department recommends that at least 250 bikes of each type be produced per day. A boy's bike requires 4 labor-hours in the fabrication department and 1 labor-hour in the assembly department. A girl's bike requires 4 labor-hours in the fabrication department and 2 labor-hours in the assembly department. Currently FBI employs 200 workers in the fabrication department and 100 workers in the assembly department each shift. There are three 8 hour shifts per day (overtime is not permitted). Formulate the above information as a linear programming problem. How many boys and girls bike should FBI produce per day to maximize profit?

Linear Programming Formulation

Objective Function:

Maximize Profit: 30 * Boys_Bikes + 50 * Girls_Bikes     (1)

Subject to Constraints:

Fabrication:
     4 * Boys_Bikes + 4 * Girls_Bikes <= 4800           (2)

Assembly:
     4 * Boys_Bikes + 2 * Girls_Bikes <= 2400           (3)

Marketing (Boys)
     4 * Boys_Bikes                   >= 250            (4)

Marketing (Girls)
                          Girls_Bikes >= 250            (5)

The sample problem contains two variables (Boys_Bikes and Girls_Bikes), one objective function (equation 1) and four constraints (equations 2-5). A cell is needed for each variable and for each equation in the linear programming (LP) formulation. Therefore, a total of 7 cells (Boys_Bikes, Girls_Bikes and 5 equations) are needed to represent the above problem in Excel.

EXCEL Steps

We will represent the two variables (Boys_Bikes and Girls_Bikes) by cells A1 and B1, Profit (objective function) by cell D1 and the four constraints by cells C1 through C4.

Step I (Naming Cells)

  1. Click on cell A1.
  2. Click on the name box at the left end of the formula bar.
  3. Type Boys_Bikes
  4. Press Enter.
  5. Similar to steps 1-4 above, input the names for the other cells to be used in this problem:

In the name box for 

    B1    type    Girls_Bikes
    C1    type    Fabrication
    C2    type    Assembly
    C3    type    Market_Boys
    C4    type    Market_Girls
    D1    type    Profit

Step II (Objective Function)

1. Click on D1 2. Enter Profit function in terms of variable names as 
     = 30 * Boys_Bikes + 50 * Girls_Bikes

Step III (Constraints)

1. Click on C1; enter left-hand-side of equation (2) as 
     = 4 * Boys_Bikes + 4 * Girls_Bikes
2. Click on C2; enter left-hand-side of equation (3) as 
     = Boys_Bikes + 2 * Girls_Bikes
3. Click on C3; enter left-hand-side of equation (4) 
     = Boys_Bikes
4. Click on C4; enter left-hand-side of equation (5) as = A1 
     = Girls_Bikes

Step IV (Solver Steps)

  1. Open Solver from the Tools menu. Note: If you don't see Solver as an option under Tools menu, that means this module was not installed during Excel setup. Re-install Excel completely with all options (Microsoft Office CD-ROM or installation disks allow the user to add/delete components of pre-installed programs).
  2. Set Target Cell represents the objective function. Make sure that this space is highlighted (completely black) and click on D1 to enter the objective function. This space should now contain: $D$1. Alternatively, you can type Profit (name of cell D1) directly in this space.
  3. The sample problem requires maximization of the objective. Make sure that Max is highlighted (by a black circle).
  4. Click on By Changing Cells. You need to input the location of the two decision variables (Boys_Bikes and Girls_Bikes) here. Therefore highlight cells A1 and B1. The By Changing Cells space should now contain $A$1:$B$1. Alternatively, you can type Boys_Bikes, Girls_Bikes in this space.
  5. Click on Add to begin adding constraints.
  6. Add constraint 1 (equation 2): Click Cell Reference. Click on cell C1. $C$1 should appear in Cell Reference (alternatively type Fabrication). Make sure that Constraint shows <= sign. If not, then click on the and select <=. Enter 4800 in the right cell. Click on Add.
  7. Add constraint 2 (similar to steps 5-6).
  8. Add constraint 3 (equation 4): Click Cell Reference. Click on cell C3. $C$3 should appear in Cell Reference (alternatively type Boys_Bikes). Make sure that Constraint shows >= sign. If not, then click on the and select >=. Enter 250 in the right cell. Click on Add.
  9. Add constraint 4 (similar to step 8). After adding the last constraint, click OK (instead of clicking Add). The Solver template will reappear.
  10. Click Options. A new template will open up. Click Assume Linear Models ( a will appear in the box). Click OK, the Solver template will reappear.
  11. Click on Solve. The solver will return with the following values in the cells:
    A1 = 250; B1 = 950; C1 = 4800; C2 = 2150; C3 = 250; C4 = 950; D1 = 55000
  12. Press Ctrl and click on Answer Report and Sensitivity Report. The reports will appear as separate sheets. The reports (Table A1 and Table A2) show that FBI should produce 250 boys bikes and 950 girls bikes per day (which result in optimum profit of $55000/day). Available labor hours in the fabrication department and minimum production requirement for boys bikes are binding constraints. Therefore each additional labor hour in fabrication department can add $12.50 to profit (see Table 2, shadow price). Similarly, each additional boys bikes produced per day will reduce profit by $20.
  13. Print the two reports. Now you're ready for a coffee break.


Download julyfigs.zip for TIF version of Tables A1 and A2.