LP Formulation Additional Examples Example 1: A cargo plane has three compartments for storing cargo: front, center, and back. These compartments have capacity limits on both weight and space, as summarized below: Compartment Front Center Back Weight Capacity (Tons) 12 18 10 Space Capacity (Cubic Feet) 7,000 9,000 5,000 Furthermore, the weight of the cargo in the respective compartments must be the same proportion of that compartment's weight capacity to maintain the balance of the airplane. The following four cargoes have been offered for shipment on an upcoming flight as space is available: Cargo 1 2 3 4 Weight (Tons) 20 16 25 13 Volume (Cubic Feet/ Ton) 500 700 600 400 Profit ($/Ton) 320 400 360 290 Any portion of these cargoes can be accepted. The objective is to determine how much (if any) of each cargo should be accepted and how to distribute each among the compartments to maximize the total profit for the flight. Formulate a linear programming model for this problem. Problem Solving x Decision Variables: Let ij denote the number of tons of cargo type i stowed in compartment j. Cargo type Cargo type (i=1, 2, 3, 4) Compartment (j =1, 2, 3) Front: ( F = 1 ) Center: ( C = 2 ) Back: ( B = 3 ) The Objective Function: C1 Max Profit = 320 j j C2 C3 x j + 400 x j + 360 x j + 290 1 j 2 xj 4 C1, C2, C3, C4 are Model Parameters. Subject to: Resource Constraints from Weight Capacity x x x i i1 = X11 + X21 + X31 +X41 12 i i2 = X12 + X22 + X32 + X42 18 i i3 = X13 + X23 + X33 + X43 10 Resource Constraints from Space Capacity 500X11 + 700X21 + 600X31 + 400X41 7000 500X12 + 700X22 + 600X32 + 400X42 9000 500X13 + 700X23 + 600X33 + 400X43 5000 Weight Constraints X11 + X12 + X13 20 X21 +X22 + X23 16 C4 j 3 X31 +X32 + X33 25 X41 +X42 + X43 13 Proportionality Constraints X11 + X12 + X31 + X41 = i x i2 = i x 12 8 i3 1 10 Non-negativity Constraints xj 0 i (for all i = 1, 2, 3, 4 j = 1, 2, 3 ) Example 2: An investor has money-making activities A and B available at the beginning of each of the next 5 years (call them years 1 to 5). Each dollar invested in A at the beginning of a year returns $ 1.40 (a profit of $0.40) two years later (in time for reinvestment). Each dollar invested in B at the beginning of a year returns $ 1.70 three years later. In addition, money-making activities C and D will each be available at one time in the future. Each dollar invested in C at the beginning of year 2 returns $ 1.90 at the end of year 5. Each dollar invested in D at the beginning of year 5 returns $ 1.30 at the end of year 5. The investor begins with $60,000 and wishes to know which investment plan maximizes the amount of money that can be accumulated by the beginning of year 6. Formulate a linear programming model for this problem. Problem Solving Year 0 now 1 2 3 4 5 6 the end of the 1st year = the beginning of the 2nd year Decision variables: At: the amount of money invested in activity A at the beginning of year t Bt: the amount of money invested in activity B at the beginning of year t Ct: the amount of money invested in activity C at the beginning of year t Dt: the amount of money invested in activity D at the beginning of year t Rt: the Remaining amount of Money reserved on hand at the beginning of year t Constraints: Now (Year 0) beginning of year 1 60000 = A1 + B1 +R1 Beginning of Year 2 R1 = A2 + B2 + C2 + R2 Beginning of Year 3 1.4 A1 + R2 = A3 + B3 + R3 Beginning of Year 4 1.4 A2 + 1.7 B1 + R3 = A4 + B4 + R4 Beginning of Year 5 1.4 A3 + 1.7 B2 + R5 = A5 + B5 + D5 + R5 Non-negativity Constraints A1, A2, A3, A4, A5, B1, B2, B3, B4, B5, C2, D5, R1, R2, R3, R4, R5 0 Beginning of Year 6 Max Profit = 1.4 A4 + 1.7 B3 + 1.9 C2 + 1.3 D5 + R5