Introduction to Management Science (10th Edition)  page 70
SummaryIn this chapter we found that simply rounding off noninteger simplex solution values for models requiring integer solutions is not always appropriate. Rounding can often lead to suboptimal results. Therefore, direct solution approaches using the computer are needed to solve the three forms of linear integer programming modelstotal integer models, 01 integer models, and mixed integer models.
Having

ReferencesBaumol, W. J. Economic Theory and Operations Analysis , 4th ed. Upper Saddle River, NJ: Prentice Hall, 1977. Dantzig, G. B. "On the Significance of Solving Linear Programming Problems with Some Integer Variables." Econometrica 28 (1960): 3044. Gomory, R. E. "An Algorithm for Integer Solutions to Linear Programs." In Recent Advances in Mathematical Programming , edited by R. L. Graves and P. Wolfe. New York: McGrawHill, 1963. Lawler, E. L., and Wood, D. W. "Branch and Bound MethodsA Survey." Operations Research 14 (1966): 699719. Little, J. D. C., et al. "An Algorithm for the Traveling Salesman Problem." Operations Research 11 (1963): 97289. McMillan, C., Jr. Mathematical Programming . New York: John Wiley & Sons, 1970. Mitten, L. G. "BranchandBound Methods: General Formulation and Properties." Operations Research 18 (1970): 2434. Plane, D. R., and McMillan, C., Jr. Discrete Optimization . Upper Saddle River, NJ: Prentice Hall, 1971. Wagner, H. M. Principles of Operations Research , 2nd ed. Upper Saddle River, NJ: Prentice Hall, 1975. 
Example Problem Solution
The following example problem
The Problem Statement
A
Formulate this problem and solve it by using QM for Windows. SolutionStep 1: Formulate the Integer Programming Model
Step 2: Solve the Model Using QM for Windows 
Problems
1. 
Consider the following linear programming model:
Demonstrate the graphical solution of this model. 

2. 
Solve the following linear programming model by using the computer:


3. 
A tailor makes wool tweed sport coats and wool slacks. He is able to get a shipment of 150 square yards of wool cloth from Scotland each month to make coats and slacks, and he has 200 hours of his own labor to make them each month. A coat requires 3 square yards of wool and 10 hours to make, and a pair of slacks requires 5 square yards of wool and 4 hours to make. The tailor earns $50 in profit from each coat he makes and $40 from each pair of slacks. He wants to know how many coats and pairs of slacks to produce to maximize profit.


4. 
A jeweler and her apprentice make silver pins and necklaces by hand. Each week they have 80 hours of labor and 36 ounces of silver available. It requires 8 hours of labor and 2 ounces of silver to make a pin and 10 hours of labor and 6 ounces of silver to make a necklace. Each pin also contains a small gem of some kind. The demand for pins is no more than six per week. A pin earns the jeweler $400 in profit, and a necklace earns $100. The jeweler wants to know how many of each item to make each week to maximize profit.


5. 
A glassblower makes glass decanters and glass trays on a weekly basis. Each item requires 1


6. 
The Livewright Medical


7. 
Helen Holmes makes pottery by hand in her


8. 
Lauren Moore has sold her business for $500,000 and wants to invest in condominium units (which she intends to rent) and land (which she will lease to a farmer). She estimates that she will receive an annual return of $8,000 for each condominium and $6,000 for each acre of land. A condominium unit costs $70,000, and land costs $30,000 per acre. A


9. 
The owner of the Consolidated Machine Shop has $10,000 available to purchase a lathe, a press, a grinder, or some combination thereof. The following 01 integer linear programming model has been developed to determine which of the three machines (lathe, x _{ 1 } ; press, x _{ 2 } ; or grinder, x _{ 3 } ) should be purchased in order to maximize annual profit:
Solve this model by using the computer. 

10. 
Solve the following mixed integer linear programming model by using the computer:


11. 
Northwoods Backpackers is a retail catalog store in Vermont that specializes in outdoor clothing and camping equipment. Phone orders are taken each day by a large pool of computer operators, some of whom are permanent and some temporary. A permanent operator can process an average of 76 orders per day, whereas a temporary operator can process an average of 53 orders per day. The company averages at least 600 orders per day. The store has 10 computer workstations. A permanent operator processes about 1.3 orders with errors each day, whereas a temporary operator averages 4.1 orders with errors daily. The store wants to limit errors to 24 per day. A permanent operator is paid $81 per day, including benefits, and a temporary operator is paid $50 per day. The company wants to know the number of permanent and temporary operators to hire to minimize costs. Formulate an integer programming model for this problem and solve it by using the computer. 

12. 
Consider the following linear programming model:
Solve this problem by using the computer. 

13. 
In the example problem solution for this chapter on page 203, a




14. 
The Texas Consolidated Electronics Company is contemplating a research and development program encompassing eight research projects. The company is constrained from embarking on all projects by the number of available management scientists (40) and the budget available for R&D projects ($300,000). Further, if project 2 is selected, project 5 must also be selected (but not vice versa). Following are the resource requirements and the estimated profit for each project:
Formulate the integer programming model for this problem and solve it by using the computer. 

15. 
Mazy's Department Store has decided to stay
Store personnel must report to work at the beginning of one of these time periods and must work for 8 consecutive hours. The store manager wants to know the minimum number of employees to assign to each 4hour segment to minimize the total number of


16. 
The athletic boosters club for Beaconville has planned a 2day fundraising drive to purchase
The boosters club has gotten several businesses and car dealers to donate gasoline and
The president of the boosters club wants to know how many different types of donor contacts to schedule during the drive to maximize total donations. Formulate and solve an integer programming model for this problem. What is the difference in the total maximum value of donations between the integer and noninteger roundeddown solutions to this problem? 

17. 
The Metropolitan Arts Council (MAC) wants to advertise its upcoming
A newspaper ad costs $7,000, and the newspaper claims that its ads will reach an audience of 30,000 potential arts customers, broken down as follows:
A radio ad costs $9,000, and it is estimated to reach an audience of 41,000 arts customers, with the following audience breakdown:
The arts council has established several marketing guidelines. It wants to reach at least 200,000 potential arts customers. It believes older people are more likely to buy tickets than


18. 
Juan Hernandez, a Cuban athlete who
Juan wants to determine the combination of items he should pack in his duffel bag to maximize his profit. This problem is an example of a type of integer programming problem known as a "knapsack" problem. Formulate and solve this problem. 

19. 
The Avalon Floor Cleaner Company is trying to determine the number of salespeople it should allocate to its three regionsthe East, the Midwest, and the West. The company has 100 salespeople that it wants to assign to the three regions. The annual average unit sales volume achieved by a salesperson in each region is as follows:
Because travel distances, costs of living, and other factors vary among the three regions, the annual cost of having a salesperson is $5,000 in the East, $11,000 in the Midwest, and $7,000 in the West. The company has $700,000 budgeted for expenses. To ensure


20. 
During the war with Iraq in 1991, the Terraco Motor Company produced a lightweight, allterrain vehicle codenamed "J99 Terra" for the military. The company is now planning to sell the Terra to the public. It has five plants that manufacture the vehicle and four regional distribution centers. The company is unsure of public demand for the Terra, so it is considering reducing its fixed operating costs by closing one or more plants, even though it would incur an increase in transportation costs. The relevant costs for the problem are provided in the following table. The transportation costs are per thousand vehicles shipped; for example, the cost of shipping 1,000 vehicles from plant 1 to warehouse C is $32,000.
Formulate and solve an integer programming model for this problem to assist the company in determining which plants should


21. 
The Otter Creek Winery produces three kinds of table winea blush, a white, and a red. The winery has 30,000 pounds of grapes available to produce wine this season. A cask of blush requires 360 pounds of grapes, a cask of white requires 375 pounds, and a cask of red requires 410 pounds. The winery has enough storage space in its aging room to store 67 casks of wine. The winery has 2,200 hours of production capacity, and it requires 14 hours to produce a cask of blush, 10 hours to produce a cask of white, and 18 hours to produce a cask of red. From records of previous


22. 
Brenda Last, an
{% if main.adsdop %}{% include 'adsenceinline.tpl' %}{% endif %}
An A in a course earns 4 quality credits per hour, a B earns 3 quality credits, a C earns 2 quality credits, a D earns 1 quality credit, and an F earns no quality credits per hour. Brenda wants to select a schedule that will provide at least a 2.0 grade point average. In order to remain a


23. 
The artisans at Jewelry Junction in Phoenix are preparing to make gold jewelry during a 2month period for the Christmas season. They can make bracelets, necklaces, and pins. Each bracelet requires 6.3 ounces of gold and 17 hours of labor, each necklace requires 3.9 ounces of gold and 10 hours of labor, and each pin requires 3.1 ounces of gold and 7 hours of labor.


24. 
Harry and Melissa Jacobson produce handcrafted furniture in a workshop on their farm. They have obtained a load of 600 board feet of


25. 
The Jacobsons in Problem 24 have been approached by a home furnishings company that needs a wooden stool for its catalog. The company has asked the Jacobsons to produce a batch of 20 wooden stools, and the Jacobsons would realize a profit of $65 for each stool. A stool will require 4 board feet of wood and 5 hours to produce. Formulate and solve an integer programming model to help the Jacobsons determine whether they should produce the stools. 

26. 
The Skimmer Boat Company manufactures three kinds of molded fiberglass


27. 
The Reliance Manufacturing Company produces an aircraft part. The company can produce the part entirely at a flexible work center with multiple computerized machines. The company has four work centers, all of which are different because they were purchased at different times. Each work center has a single operator; however, the company's operators have different skill levels, resulting in different levels of daily output and product quality. The following tables show the average daily output and average number of defects per day for each of the company's five operators who are capable of producing the aircraft part:
The company wants to determine which operator to assign to each machine to maximize daily output and keep the percentage of defects to less than 4%.


28. 
Corsouth Mortgage Associates is a large home mortgage firm in the Southeast. It has a pool of permanent and temporary computer operators who process mortgage accounts, including posting payments and updating escrow accounts for insurance and taxes. A permanent operator can process 220 accounts per day, and a temporary operator can process 140 accounts per day. On average, the firm must process and update at least 6,300 accounts daily. The company has 32 computer workstations available. Permanent and temporary operators work 8 hours per day. A permanent operator averages about 0.4 errors per day, whereas a temporary operator averages 0.9 errors per day. The company wants to limit errors to 15 per day. A permanent operator is paid $120 per day, whereas a temporary operator is paid $75 per day. Corsouth wants to determine the number of permanent and temporary operators it needs to minimize cost. Formulate and solve an integer programming model for this problem and compare this solution to the noninteger solution. 

29. 
In Problem 28, Corsouth Mortgage Associates is considering hiring some hourly, parttime computer operators in addition to its permanent and temporary operators. A parttime operator can process 12 accounts per hour, averages 0.16 errors per hour, and is paid $4.50 per hour. Corsouth wants to know the number of permanent and temporary employees it should use, plus the number of


30. 
Rowntown Cab Company has 70 drivers that it must schedule in three 8hour shifts. However, the demand for cabs in the metropolitan area varies dramatically according to the time of day. The slowest period is between midnight and 4:00 A.M. The dispatcher receives few calls, and the calls that are received have the smallest fares of the day. Very few people are going to the airport at that time of night or taking other longdistance trips. It is estimated that a driver will average $80 in fares during that period. The largest fares result from the airport runs in the morning. Thus, the drivers who start their shift during the period from 4:00 A.M. to 8:00 A.M. average $500 in total fares, and drivers who start at 8:00 A.M . average $420. Drivers who start at noon average $300, while drivers who start at 4:00 P.M. average $270. Drivers who start at the beginning of the 8:00 P.M. to midnight period earn an average of $210 in fares during their 8hour shift. To retain customers and acquire new ones, Rowntown must maintain a high customer service level. To do so, it has determined the minimum number of drivers it needs working during every 4hour time segment10 from midnight to 4:00 A.M. , 12 from 4:00 to 8:00 A.M. , 20 from 8:00 A.M. to noon, 25 from noon to 4:00 P.M. , 32 from 4:00 to 8:00 P.M. , and 18 from 8:00 P.M. to midnight.




31. 
Globex Investment Capital Corporation owns six companies that have the following estimated returns (in millions of dollars) if sold in 1 of the next 3 years:
To generate operating funds, the company must sell at least $20 million worth of assets in year 1, $25 million in year 2, and $35 million in year 3. Globex wants to develop a plan for selling these companies during the next 3 years to maximize return. Formulate an integer programming model for this problem and solve it by using the computer. 

32. 
The Heartland Distribution Company is a food warehouse and distributor that has a contract with a grocery store chain in several Midwest and Southeast cities. The company wants to construct new warehouses/distribution centers in some of the cities it services to serve the stores in those cities plus all the other stores in the other cities that don't have distribution centers. A distribution center can effectively service all stores within a 300mile radius. The company also wants to limit its fixed annual costs to under $900,000. The company wants to build the minimum number of distribution centers possible.
The following table shows the cities within 300 miles of every city and the




33. 
The Kreeger Grocery Store chain has bought out a competing grocery store chain. However, it now has too many stores in close proximity to each other in certain cities. In Roanoke the chain has 10 stores, and it does not want any stores closer than 2 miles to each other. Following are the monthly
Develop and solve an integer programming model to determine which stores the Kreeger chain should keep open in Roanoke. 

34. 
A youth soccer club has contracted with Holiday Helpers, a local travel agency, to broker hotel rooms for outoftown
Determine a revised hotel room allocation to assign rooms to all teams while reflecting their preferences to the greatest possible extent. 

35. 
The Tech Software School contracts to train employees of companies in the use of various software products and packages. The training programs are all delivered on 3 consecutive days but require different daily durations, depending on the software product. For a specific 7day week (including weekends), the school has contracted with eight different companies for training sessions for different software products. The companies can send their employees to the Tech training facility only on certain days, as shown in the following table, with the hourly training requirements per day:
The school has 20 staffhours per day available for these training sessions.


36. 
Each day Seacoast Food Services makes deliveries to four restaurants it supplies in the metro Atlanta area. The service uses one truck that starts at its warehouse, makes a delivery to each restaurant, and then returns to the warehouse. The mileage between the warehouse, 1, and each of the
Formulate and solve an integer programming model to determine the route (or tour) the truck should take to start at the warehouse, visit each restaurant once, and return to the warehouse with the minimum total distance traveled. 

37. 
HTM Realty has a storefront rental property in downtown Draperton, a small college town next to the Tech campus. The property encompasses four business spaces that open onto College Avenue. HTM has a long
HTM wants to lease each space to businesses that will maximize their expected lease payments. It also wants a likelihood of at least 3 of the businesses staying in business. Formulate and solve an integer programming model for this problem. 