A problem common to many different industries entails ‘‘trim'' losses in cutting rolls of paper, textiles, foil, or other material in the process of filling the orders of its customers. The problem arises from the fact that, due to production economies, a factory normally produces rolls of material in standard widths (for example, 100 inches) of fixed length (say, 500 feet). Customers who order from the factory, however, usually require rolls of smaller width for the purposes of their own industrial uses. The rolls are cut on a large cutting machine, the knives of which can be set for virtually any combination of widths so long as the combined total does not exceed the width of the roll. Thus the problem becomes one of assigning the orders in such a manner that the number of standard rolls used to fill the orders is minimized. All wasted material, or ‘‘trim loss,'' represents a loss to the firm. This loss can sometimes be alleviated, however, through recycling or selling as ‘‘scrap'' or ‘‘seconds.'' For purposes of illustration, assume that a factory produces newsprint in standard rolls, each having a width of 100 inches, and a fixed length of 500 feet. The factory must fill the following orders: 75 rolls of 24-inch width; 50 rolls of 40-inch width; and 110 rolls of 32-inch width. For simplicity, assume that the factory delivers all orders (no matter what the width) in the standard length of 500 feet. Further, assume that there are on hand as many standard rolls as necessary, and that only the widths on order are cut. Set up the problem as a linear program with integer variables that minimizes the trim losses.
(Hint: Completely itemize the number of possible ways n in which a 100-inch roll can be cut into combinations of 24-, 40-, and 32-inch widths; i.e., one 24-inch roll, one 40-inch roll, one 32-inch roll, with 4 inches of trim waste. Then let the decision variable xi represent the number of rolls cut as combination i,i = 1, 2, . . . , n. For simplicity in itemizing the possible combinations, assume that each standard roll is cut into as many smaller rolls as possible. Thus, if any smaller rolls are produced in excess of the number ordered, they are counted as waste.)