CUTTING STOCK PROBLEM INTEGER LINEAR PROGRAMMING A film comp

CUTTING STOCK PROBLEM... INTEGER LINEAR PROGRAMMING

A film company needs to cut 15 long rolls and 10 short rolls of film from stock pieces. Each stock piece can be cut in one of two patterns. The first produces 5 long and 2 short rolls; the second yields 3 long and 5 short. Once a stock piece is cut the rest is wasted. Neither pattern can be used more than 4 times because the jig used to cut it will become too inaccurate. The company wants to find the allowable combination of patterns that will minimize the number of stock pieces needed. Formulate the problem as an integer linear programming (ILP) model.

Solution

Let X1 be the number of stock pieces of pattern 1 and X2 be the number of stock peices of pattern2

minimize the number of stock pieces z =X1+X2

Neither pattern can be used more than 4 times.

so X1<=4; X2<=4

for pattern1 , the number of long rolls are 5X1 and short rolls are 2X1

for pattern 2 , the number of long rolls are 3X2 and short rolls are 5X2

5X1+3X2 =15; 2X1+5X2 =10

where X1 and X2 are positive.

The ILP is

Minimize z = X1+X2

subject to 5X1+3X2 =15; 2X1+5X2 =10; X1<=4; X2<=4

X1, X2 >=0