COMP4041-LDO Workshop 3 Product-Mix Optimization as LP and IP
Purpose: Develop, solve and interpret LP and IP models for various product-mix optimization problems.
Develop the optimization model in Excel and LP-Solve to solve each of the product-mix optimization problems below. Aim to approach each problem with the following steps: 1) identify data, 2) identify decision variables, 3) formulate objective function and 4) formulate constraints.
Also, for each problem: reflect on the optimal solution obtained, determine if there might be multiple optimal solutions, identify binding and non-binding functional constraints, solve as LP and as IP. For each algebraic model, practice writing the ‘compact’ algebraic notation.
CARGO AIRPLANE Problem
A cargo airplane has three compartments of certain limited weight and space capacity for storing cargo: front, centre and back compartments. The weight of the cargo shipped in all the compartments must be in the same proportion with respect to the compartments’ weight capacity to maintain balance of the airplane. For example, if the front compartment takes 6 tons, then the centre compartment must take 9 tons and the back compartment must take 5 tons.
Compartment
Front Centre Back
Weight Capacity (Tons)
Space Capacity (ft3)
The total amount of cargoes shown below is available for shipment and any part of each cargo can be accepted subject to the compartments’ capacity. Each compartment can take more than one type of cargo, i.e. cargoes can be mixed in a compartment. The problem is to determine the amount in tons of each available cargo should be shipped in each compartment in order to maximize the total profit.
Cargo Weight (Tons) Volume (ft3/Ton) Profit (£/Ton)
1 20 500 320 2 16 700 400 3 25 600 360 4 13 400 290
NURSERY FOOD Problem
The directors of a day care nursery want to decide what mix of food to feed to the children. They want to minimize their costs, but also need to meet some nutritional requirements. They have already decided to give each child one sandwich filled with peanut butter and strawberry jam. They also want to give each child some combination of crackers, milk and orange juice. The nutritional content of each food choice and its cost are given in the table.
Bread (1 slice)
Peanut butter (1 tablespoon) (1 tablespoon) Cracker (1 piece)
Milk (1 cup)
Orange Juice (1 cup)
Calories from fat 10 75
Total Vitamin C calories (milligrams)
70 0 100 0 50 3 60 0 150 2
Protein Cost (grams) (pence)
3 5 4 4 0 7 1 8 8 15 1 35
The nutritional requirements are as follows. Each child must consume between 400 and 600 calories. No more than 30 percent of the total calories consumed should come from fat. Each child must consume at least 60 milligrams of vitamin C and at least 12 grams of protein. Each child needs exactly 2 slices of bread (to make the sandwich), at least twice as much peanut butter as strawberry jam, and at least 1 cup of liquid (milk and/or juice). The directors want to select the food for each child which minimizes the cost while meeting the above requirements.
Slide 42 of lecture 2 illustrates a case with two conflicting constraints replacing one constraint in the original LP model. It was concluded that adding these two constraints makes the model infeasible.
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒: 𝑍 = 5𝑋1 + 4𝑋2 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜: 6𝑋1 + 4𝑋2 ≤ 24 (1) 𝑋1 + 2𝑋2 ≤ 6 (2) −𝑋1 + 𝑋2 ≤ 1 (3)
𝑋2 ≤ 1 (4𝑎) 𝑋2 ≥ 2 (4𝑏) 𝑋1,𝑋2≥0 (5)
In lecture 3, a technique was illustrated to deal with a situation like the one above. Apply that technique and implement the model in LP-Solve. Compare the solution obtained for the modified model to the solutions obtained solving the model without (4b) and without (4a).
This in a suggested step that will not be included in the test for this workshop.
Until now, we have covered several optimization problems in the lectures and workshops (including taster one): Research Institute, Bank ABC, Apex, Vegetables Distribution, Apples,
Toy Builder, Atlas, Good Burger, , Furniture, Paper Recycling.
Solve each of the above mathematical optimization models (Excel and/or LP-Solve) as LP and as IP. Compare the solutions obtained for each case and reflect on the concepts of ‘lower bound’ and ‘upper bound’ in respect of the optimal solution for the IP case.