Applications of Linear and Integer Programming Models 3

1 113 Applications of Linear and Integer Programming ModelsChapter3 WITH APPROXIMATELY$20 BILLIONin revenues,FedEx Corporation ( )has become a world leader in providing integratedtransportation, information, and logistics solutions. Asthe company has expanded, it has created a high-levelmanagement science group to provide senior manage-ment with recommendations on a wide variety of group uses state-of-the-art computer-based mathe-matical Models to analyze a broad range of complexcorporate problems with an overall goal of maintainingand increasing company profits while continuing to pro-vide a consistently high level of service to its of the Models developed by this group is itsGlobal Supply Chain model , built to redesign its supplychain for revenue packaging. The model has helpedmanagement answer the following questions: Should FedEx pursue offshore production ofpackaging?

2 If so, which items and where? Should FedEx consolidate nearby warehouses andpick centers into a new form of distribution center? Should FedEx pursue expansion of distributioncenter locations? What transportation modes on each link would mostreliably get packaging from suppliers to stationswhile reducing costs? What should the service area boundaries be for eachdistribution center?The Global Supply Chain model uses, among othertechniques, a large-scale mixed Integer programmingapproach. This model has already resulted in a cost sav-ings to FedEx of over $10 Applications of Linear and Integer Programming Evolution of LinearProgramming Models in Business and GovernmentFollowing World War II, the Air Force sponsored research for solving mili-tary planning and distribution Models . In 1947, the simplex algorithm was devel-oped for solving these types of Linear Models . Not long after, the first commercialuses of Linear Programming were reported in large businesses that had access todigital computers.

3 Seemingly unrelated industries, such as agriculture, petroleum,steel, transportation, and communications, saved millions of dollars by successfullydeveloping and solving Linear Models for complex computing power has become more accessible, the realm of businesses andgovernment entities using Linear Models has expanded exponentially. In this chap-ter we present numerous small examples selected from a wide variety of applica-tions areas, designed to accomplish four examine potential Applications areas where Linear Models may be develop good modeling demonstrate how to develop use of the power of spreadsheets toeffectively represent the model in unambiguous terms and generate gain confidence in interpreting and analyzing results from spreadsheetreportsAlthough the examples illustrated in this chapter represent scaled-down ver-sions of potential real-life situations, today Linear and Integer Programming mod-els proliferate in a wide variety of actual business and government Models , large economic/financial Models , marketing strategy Models ,production scheduling and labor force planning Models , computer design and net-working Models .

4 And health care and medical Models are but a few notable exam-ples of successful Linear Programming Applications . Below is just a sampling of thethousands of actual documented uses of Linear Programming Models . Aircraft fleet assignments Telecommunications network expansion Air pollution control Health care Bank portfolio selection Agriculture Fire protection Defense/aerospace contracting Land use planning Dairy production Military deploymentAn example of each of the above is detailed in Appendix on the accom-panying CD-ROM. The reader is encouraged to reference this subfolder are but a few of the numerous Applications areas of Linear optimizationmodels. Additional Applications include traffic analysis, fast-food operations, trans-portation, assignment of medical personnel, coal, steel, gas, chemical, and paperproduction, recycling, educational assignments, worker evaluations, awarding ofcontracts, manufacturing, railroads, forestry, school desegregation, governmentplanning, tourism, and sports scheduling.

5 Each year hundreds of new applicationsappear in the professional literature. Add to that the numerous unreported modelsthat are regularly utilized in business and government, and you can see that linearprogramming continues to play a significant role in today s Good Linear and Integer Programming ModelsGiven the widespread use of Linear Models today, it has become increasingly im-portant for practitioners to be able to develop good, efficient Models to aid themanager in the decision-making process. Three factors familiarity, simplifica-tion, and clarity are important considerations when developing such greater the modeler s familiaritywith the relationships between compet-ing activities, the limitations of the resources, and the overall objective, the greaterthe likelihood of generating a usable model . Viewing the problem from as manyperspectives as possible ( , those of various management levels, front-line work-ers, and accounting) helps in this Models are always simplificationsof real-life situations.

6 Usually, some orall of the required Linear Programming assumptions discussed in Chapter 2 are vi-olated by an actual situation. Because of the efficiency with which they are solvedand the associated sensitivity analysis reports generated, however, Linear modelsare generally preferable to more complicated forms of mathematical developing a model , it is important to address the following question: Is a very sophisticated model needed, or will a less sophisticated model that givesfairly good results suffice? The answer, of course, will guide the level of detail re-quired in the a model should reflect the real-life situation, one should not try tomodel every aspect or contingency of the situation. This could get us boggeddown in minutiae, adding little, if any, real value to the model while unnecessarilycomplicating the solution procedure, delaying solution time, and compromisingthe usefulness of the model .

7 As George Dantzig, the developer of the simplex al-gorithm for solving Linear Programming Models , points out, however, What con-stitutes the proper simplification, is subject to individual judgment and often disagree on the adequacy of a certain model to describe the situa-tion. 1In other words, although experience is the best teacher, you should beaware that even experienced management scientists may disagree as to what levelof simplification is realistic or warranted in a , a Linear Programming model should be clear; that is, it should be easyto follow and as transparent as possible to the layperson. From a practitioner spoint of view, the model should also be easy to input and yield accurate results in atimely VARIABLES AND CONSTRAINTSIn an effort to make the model easier to understand and debug, we can introducesummation variablesand corresponding summation constraintsinto the for-mulation.

8 A summation variable is the sum of two or more of the decision vari-ables. It is particularly useful when there are constraints involving maximum orminimum percentages for the value of one or more of the decision illustrate the use of a summation variable, consider the situation in whichX1, X2, and X3represent the production quantities of three television Models to beproduced during a production run in which 7000 pounds of plastic are Building Good Linear and Integer Programming Models1151 George B. Dantzig, Linear Programming and Extensions(Princeton, NJ: Princeton University Press, 1963).116 CHAPTER3 Applications of Linear and Integer Programming ModelsThe unit profits are $23, $34, and $45, and the amount of plastic required to pro-duce each is 2 pounds, 3 pounds, and 4 pounds, respectively. In addition, manage-ment does not want any model to exceed 40% of total production (X1 X2 X3).First, we note that although the proportion of model 1 televisions producedduring the production run is X1/(X1 X2 X3).

9 However a constraint of theform: X1/(X1 X2 X3) .4 is not a Linear constraint. But, because we know thatthe total production, X1 X2 X3is positive, we could multiply both sides ofthis constraint by the denominator to obtain the equivalent Linear constraint: X1 .4(X1 X2 X3). The constraints X2 .4(X1 X2 X3) and X3 .4(X1 X2 X3) require that Models 2 and 3 represent no more than 40% of the totalproduction. Thus, the model could be written as:MAX23X1 34X2 45X3ST2X1 3X2 4X3 7000X1 .4(X1 X2 X3)X2 .4(X1 X2 X3)X3 .4(X1 X2 X3)X1, X2, X3 0or,MAX23X1 34X2 45X3ST2X1 3X2 4X3 .4X2 .4X3 0 .4X1 .6X2 .4X3 0 .4X1 .4X2 .6X3 0X1, X2, X3 0 Written in this form, not only are the coefficients cumbersome to input into aspreadsheet, but the last three constraints do not immediately convey the fact thateach television model is not to exceed 40% of the total clarify the above formulation, a summation variablerepresenting the totalproduction and a summation constraintexpressing this relationship may be intro-duced into the model as follows: Define the summation variable: X4 the total production of televisions during a production run.

10 Add the following summation constraint: X1 X2 X3 X4or equivalently X1 X2 X3 X4 0 to the modelformulation. The 40% production limit constraints can now be written as: X1 .4X4, X2 .4X4, and X3 . subtracting .4X4from both sides of each of the above production limit con-straints, the complete set of constraints can now be written as:MAX23X1 34X2 45X3ST2X1 3X2 4X3 7000X1 X2 X3 X4 0 (Summation Constraint)X1 .4X4 0X2 .4X4 0X3 .4X4 0 All X s 0 Although by adding the summation variable and the summation constraint wehave increased the number of constraints and number of variables each by one, thenew set of constraints is easier to input and easier to read and interpret whenchecking the using spreadsheets, a convenient way of modeling this situation withoutlisting all the percentage constraints explicitly is shown in Figure In this fig-ure, cells B2, C2, and D2 are used for the decision variables, while another cell(H2) is set aside to represent total production.