Pace University DigitalCommons@Pace Faculty Working Papers Lubin School of Business 11-1-1999 The Mystery of Linear Programming Explained: Second Edition Jack Yurkiewicz Pace University Follow this and additional works at: http://digitalcommons. pace. edu/lubinfaculty_workingpapers Recommended Citation Yurkiewicz, Jack, "The Mystery of Linear Programming Explained: Second Edition" (1999). Faculty Working Papers. Paper 21.
http://digitalcommons. pace. edu/lubinfaculty_workingpapers/21 This Article is brought to you for free and open access by the Lubin School of Business at [email protected] has been accepted for inclusion in Faculty Working Papers by an authorized administrator of DigitalCommons@Pace. For more information, please contact rracelis@pace.
edu. WORKING PAPERS No. 191 November 1999 The Mystery of Linear Programming Explained: Second Edition by Jack Yurkewicz, Ph. D. Professor of Management Science and Director of the Advanced Professional Certificate Program Lubin School of Business Pace University THE MYSTERY OF LINEAR PROGRAMMING EXPLAINEDSECOND EDITION As Recounted by John H.
Watson, M. D.Edited by Jack Yurkiewicz, Ph. D. Jack Yurkiewicz is Professor of Management Science and Director of the Advanced Professional Certificate Program at the Lubin School of Business, Pace University. Introduction INTRODUCTION I hadn't seen my old friend and companion, Sir Sherlock Holmes (he had been knighted by the Queen and insisted that this appellation be used) in several months.
Feeling that I had slighted him, I rang him up and told him I would be stopping by the next day to see how his new business venture was progressing.Holmes was truly glad to hear my voice and urged that we have lunch together. While he hinted that his firm, of which he was the sole employee, was doing well, he did indeed wish to discuss a business proposition with me. Needless to say, I was intrigued. I won’t bother to bore you, dear reader, with some of our mundane conversation the next day save to say that I found Holmes to be moodier than ever.
The great detective had long ago become bored with crime solving, claiming there was little challenge in solving many of the violent crimes that seemed so prevalent in our society.The firm that he started provided consulting service to corporations, in which he would use his mental abilities to help managers solve their business-related problems. Holmes explained to me that he enjoyed the challenge of his new endeavors but was finding it increasingly difficult to converse with these "business types," as he called them. He just didn't have the patience to explain his findings to them, for he found them curiously dull. Holmes went on to say that he had no doubt that this fact was the cause of the country's lack of success in the international business environment.
I didn't want to say it, but I thought to myself that the fault might not be solely with the business managers he was dealing with, but partially with him, for I myself frequently found him short-tempered and impatient, even during his ordinary conversations with me. In any case, his proposition to me was simple. Holmes: Listen, Watson, I just can't bear the thought of explaining to these so-called “leaders” how they should be running their firms. They come to me with some specific problem, usually ill-defined, and then expect me to come up with a solution.
I have found that getting the solution is fairly trivial, but I have the dickens of a time trying to explain it to them! You have a solid head on your shoulders, old fellow. Suppose you became my partner. Your only job would be to explain to them the solution that I propose, for I fear that my patience is not as long as yours is. Watson: The thought intrigues me, for I have been cutting back on my practice lately and do find myself available with more free time.
What procedures do you use to get your results?Holmes: Mostly a branch of mathematics called "operations research," which incidentally has its roots in this country during the Second World War. I collect the data, enter it on a computer I have in my study, and in almost an instant, I get the results. Watson: Well, I am afraid that tears it, Holmes. I don't know the first thing about operations research and thus could not possibly explain it to others.
I did try to learn the subject several years back. I bought a college textbook on the subject and spent several frustrating days trying to learn linear programming.The subject seemed understandable enough, but I became hopelessly 1 The Mystery of Linear Program Explained lost on the mechanics of the simplex algorithm. I was working with equations and performing what the author called "elementary row operations. " Believe me, there was nothing elementary about it. After three days I threw the book down in disgust and came to the conclusion that only masochists or the temporarily insane would ever try to fathom such a subject.
Holmes: I fear you overestimate the subject's complexity, but the point is irrelevant.No one really does these things by hand anymore, and so it was just your poor fortune to buy a book that was obsolete. All is now done with the aid of the computer. In fact, I am using a program called Solver, which is a part of Excel which is unusually easy to use and powerful. I will explain the computer output to you, along with its ramifications, and then you in turn will explain it to the manager in question.
It really is quite simple, and if I may say, also lucrative. The more Holmes spoke, the more interested I became.His power of persuasion was truly formidable, and in the end, against much misgiving on my part, I agreed to enter into this venture on a trial basis. Holmes was satisfied with my decision and proposed that we start immediately with a problem that he had completed the other day that he was due to report on the following week.
HOLMES DESCRIBES THE CASE Holmes: The Maximus Computer Company (MCC) has four basic computers it sells to students and small business people. The first, called the Starter, is a basic, “no-frills” computer.It has most of the amenities that a new user or a buyer on a strict budget could want, including CDROM with sound, an entry-level processor, a small hard disk, a modem for Internet access, and a 15-inch monitor. The second model, called the Midrange, is for more demanding users.
This model offers a faster processor, larger hard disk, more RAM, a DVD player, and a 17-inch monitor. The third model, the Super, provides just about all the computing power a user could want. It offers even more RAM, a very fast processor, a large hard disk, a DVD player with hardware decoder, and a 17-inch monitor.All but the most demanding users would be very happy with the Super. However, for those who want the very “best,” the company offers the Extreme which offers a state-of-the-art processor, a huge hard disk, the best multimedia package (the latest generation DVD ROM with a five-piece speaker system), a CD re-writable drive, a 19inch monitor, etc.
Thus, while the company offers only four models, it feels there is enough flexibility to cover most of the target computer audience. It is a small start-up company and management knows it has to compete against the heavily entrenched products from Dell, IBM, Compaq, Hewlett-Packard, and Gateway.The company philosophy is to ship computers with brandknown components and offer superior service, all at a cost to consumers that is lower than the competition's. Watson: Well, Holmes, I believe I know about the philosophy of the company and its immediate goals. Can you please tell me more about the four models of computers we offer? 2 How the Operation Works Holmes: As I said, Maximus makes four models with different levels of features, all with the same customer support.
They believe that whatever the sophistication of the machine, customer support should be “top notch” and not deteriorate with the price.In the long run, that will generate customer good will and promote their growth in the market. Watson: I agree whole-heartedly. Tell me a bit more about the computers themselves.
HOW THE OPERATION WORKS Holmes: As you probably know, the computer industry is currently very competitive, and profit margins are low for each model. The net profit on a Starter is $50, for a Midrange it is $120, for a Super it is $250, and for an Extreme it is $300. These figures already take into account material, labor, depreciation, taxes, shipping, etc. In other words, these are the net profits to the company for each computer sold.Watson: Eventually we can delve into how these values are determined and perhaps how we can increase them, but for now, let’s assume that they are sacrosanct.
What else can you tell me about the operation? Holmes: Management has, what they call “three operations” that make a computer. They call the first operation manufacture. This includes taking the customer’s phone call and determining which computer and options he or she wants and getting that information to the management of the production staff. They in turn will get the necessary components and make them available to the workers on the assembly line.
The second operation is referred to as assembly, where the workers on the assembly line actually put together the computer, according the specifications of the customer’s order. These are skilled workers who take pride in their work, and even though they work on an assembly line, they do not have an “assembly line mentality,” for they believe they are making custom products for specific customers. The last operation is called inspection. Here we install the software, run various diagnostic tests, and generally check out and pack up the computer before we send it to the customer. Watson: I see.
operations?Do you have approximate time figures on how long it takes to do these Holmes: It is a function of the computer. However, they have been doing this for some time now and so the time values do not vary all that much from machine to machine. Thus, for instance, for a Starter, we can assume 0. 1 hours for manufacture, 0.
2 hours for assembly, and 0. 1 hours for inspection. Our units are always in hours,I hope that doesn’t confuse you. Watson: Not at all.
Actually, I’m used to minutes and so I am making mental transformations, but since the “company units” are always measured in hours, I will use those also.Tell me the corresponding values for the other computers. 3 The Mystery of Linear Programming Explained Holmes: For a Midrange, we use 0. 2 hours to manufacture, 0. 5 hours to assemble, and 0. 2 hours for inspection.
Each Super requires 0. 7 hours to manufacture, 0. 25 hours to assemble, and 0. 3 hours inspection and testing. Finally, the Extreme gets 0. 8 hours to manufacture, 0.
2 hours to assemble, and 0. 5 hours for inspection. As I said, these numbers really don’t vary all that much from machine to machine, but as you can see, they do differ from model to model.Watson: Very well.
What about your resources? How many people, or should I say, how many people-hours are available to do those three operations? Holmes: I agree with you that we should talk in terms of people-hours. I have been using the term “man-hours” for many years and if I lapse into that gender-specific term, please forgive me. To avoid offending you, I will just use the word “hours” from now on, but I hope you know I mean “people-hours” when I say it. Watson: Have no fear on my account, Holmes. My sensibilities will not be hurt if you use the older term “man-hours.
What numbers do you have? Holmes: On a daily basis, management informed me that the company has 250 hours available for manufacture, 350 hours available for assembly, and 150 hours to do the inspection and testing. Watson: I presume that with all this information, we can proceed to model the problem as a linear program. Holmes: Indeed, Watson. As I intimated earlier, we can solve linear programs with Excel.
Excel comes with an add-on package called Solver that is easy to use and yet powerful enough to solve most mathematical programming problems.All we have to do is make a spreadsheet model of the problem and Solver will do the rest. Watson: Well, that certainly is good news. I use Excel and I have made many models. But how do you make a linear program model in Excel? MODELING THE PROBLEM IN EXCEL Holmes: Have a look at the Excel spreadsheet model here on my computer, Watson. It is imperative that you first learn how to model a problem in a spreadsheet.
Once you master this skill, we can then proceed to discuss how Solver can be used to get the answer for us.Cells B1, C1, D1, and E1 give the labels of our computers, which in linear programming terminology are called decision variables. We want the values of these variables to appear in cells B2, C2, D2, and E2. Excel’s Solver will call these cells the changing cells.
We put the per-unit profit of each computer into cells B4 through D4. These numbers are traditionally called the objective function coefficients. We must enter a formula into cell I2 (which we labeled as the Profit in cell I1) that will give the net profit for all the computer’s made. 4 Modeling the Program in ExcelA 1 2 3 4 5 6 7 8 B Starter 0 50 0. 1 0.
2 0. 1 C Midrange 0 120 0. 2 0. 5 0.
2 D Super 0 250 0. 7 0. 25 0. 3 E Extreme 0 300 F G H I Profit 0 max manufacture assembly inspection Available 0. 8 250 0.
2 350 0. 5 150 Used Slack 0 250 0 350 0 150 Watson: I know how to do that. We would type in cell I2 the formula: =B2*B4 + C2*C4 + D2*D4 + E2*E4 Algebraically, we are saying, with this formula: 50(Starters) + 120(Midrange) + 250(Super) + 300(Extreme) Of course, the value in cell I2 is zero because we have zero values for the number of computers made in cells B2 through E2.Holmes: Well done, Watson! You should know that there is a shortcut to this rather tedious formula. Excel has the built-in function, SUMPRODUCT, which will save us much typing.
That is, in cell I2 we can simply type: =SUMPRODUCT(B2:E2,B4:E4) That says: multiply the values in cells B2 through E2 by the corresponding values in the cells B4 through E4 respectively, and then add up the results. That gives us the same result as your formula. However, it is easier to input, since we need just type in the =sumproduct, highlight the ranges, and type the parentheses.The result is our total profit, which Solver calls the target cell. Watson: I suspect that we will be using that sumproduct function again. Tell me about the other items I see in your spreadsheet.
Holmes: Our model is incomplete. We need to specify the constraints. These account for the technological, economic, or other limitations of the system, and restrict the values of the decision variables to some feasible set. We have three constraints in our problem: manufacturing, assembly, and inspection. Our manufacturing constraint is: 0.
1(Starter) + 0. 2(Midrange) + 0. 7(Super) + 0. 8(Extreme)
