Integer Programming PDF

b. Instead of feeding the leftover apples to the livestock, the Friendlys are thinking about producing apple cider. Cider will require 1.5 hours of cooking, 0.5 hour of labor, and 60 apples per batch, and it will sell for $45 per batch. Should the Friendlys use all their apples...

b. Instead of feeding the leftover apples to the livestock, the Friendlys are thinking about producing apple cider. Cider will require 1.5 hours of cooking, 0.5 hour of labor, and 60 apples per batch, and it will sell for $45 per batch. Should the Friendlys use all their apples and produce cider along with their other three products? CHAPTER 5: INTEGER PROGRAMMING Overview In the linear programming models formulated and solved in the previous chapters, the implicit assumption was that solutions could be fractional or real numbers (i.e., non-integer). However, non-integer solutions are not always practical. When only integer solutions are practical or logical, it is sometimes assumed that noninteger solution values can be ―rounded off‖ to the nearest feasible integer values. However, if we are considering the production of jet aircraft and x1 = 7.4 jet airliners, rounding off could affect profit (or cost) by millions of dollars. In this case we need to solve the problem so that an optimal integer solution is guaranteed. Learning Outcomes At the end of this lesson, students should be able to 1. Differentiate and analyze the integer programming models 2. Apply Excel and QM for windows as computer solutions for integer programming problems COURSE MATERIALS Integer Programming Models There are three basic types of integer linear programming models—a total integer model, a 0–1 integer model, and a mixed integer model. In a total integer model, all the decision variables are required to have integer solution values. In a 0–1 integer model, all the decision variables have integer values of zero or one. Finally, in a mixed integer model, some of the decision variables (but not all) are required to have integer solutions. The following three examples demonstrate these types of integer programming models. A Total Integer Model Example The owner of a machine shop is planning to expand by purchasing some new machines— presses and lathes. The owner has estimated that each press purchased will increase profit by $100 per day and each lathe will increase profit by $150 daily. The machine purchase prices 55 and space requirements are as follows: The owner has a budget of $40,000 for purchasing machines and 200 square feet of available floor space. The owner wants to know how many of each type of machine to purchase to maximize the daily increase in profit. The linear programming model for an integer programming problem is formulated in exactly the same way as the linear programming examples in Chapters 2, 3, and 4. The only difference is that in this problem, the decision variables are restricted to integer values because the owner cannot purchase a fraction, or portion, of a machine. The linear programming model follows: maximize Z = $100x1 + 150x2 subject to $8,000x1 + 4,000x2 ≤ $40,000 15x1 + 30x2 ≤ 200 ft.² x1, x2 ≥ 0 and integer where x1 = number of presses x2 = number of lathes The decision variables in this model are restricted to whole machines. The fact that both decision variables, x1 and x2, can assume any integer value greater than or equal to zero is what gives this model its designation as a total integer model. A 0–1 Integer Model Example A community council must decide which recreation facilities to construct in its community. Four new recreation facilities have been proposed—a swimming pool, a tennis center, an athletic field, and a gymnasium. The council wants to construct facilities that will maximize the expected daily usage by the residents of the community, subject to land and cost limitations. The expected daily usage and cost and land requirements for each facility follow: The community has a $120,000 construction budget and 12 acres of land. Because the swimming pool and tennis center must be built on the same part of the land parcel, however, only one of these two facilities can be constructed. The council wants to know which of the 56 recreation facilities to construct to maximize the expected daily usage. The model for this problem is formulated as follows: maximize Z = 300x1 + 90x2 + 400x3 + 500x4 subject to $35,000x1 + 10,000x2 + 25,000x3 + 90,000x4