Linear Programming Problems and Solutions
Problem #B-1
Solve these problems using simultaneous equations to determine the optimal values of the decision variables and the objective function.
a. Maximize Z = 4×1 + 3×2
Subject to:
Material: 6×1 + 4×2
Labor: 4×1 + 8×2
x1, x2 >= 0
b.
Maximize Z = 6A + 3B
Subject to:
Material: 20A + 6B
Machinery: 25A + 20B
A, B >= 0
Problem #B-2
An appliance manufacturer produces two models of microwave ovens: H and W. Both models require fabrication and assembly work; each H uses four hours of fabrication and two hours of assembly, and each W uses two hours of fabrication and six hours of assembly. There are 600 fabrication hours available this week and 480 hours of assembly. Each H contributes $40 to profits, and each W contributes $30 to profits. What quantities of H and W will maximize profit? What is the maximum profit?
Problem #B-3
Solve each of these problems using Excel and obtain the optimal values of the decision variables and the objective function. Print the Excel “Answer Report”.
a.
Maximize Z = 4×1 + 2×2 + 5×3
Subject to:
1×1 + 2×2 + 1×3
1×1 + 4×2 + 2×3
3×1 + 3×2 + 1×3
x1, x2, x3 >= 0
b.
Max Z = 10×1 + 6×2 + 3×3
Subject to
1×1 + 1×2 + 2×3
2×1 + 1×2 + 4×3
1×1 + 2×2 + 3×3
x1, x2, x3 >= 0
Problem #B-4
The Erlanger Manufacturing Company makes two products. The profit estimates are $25 for each unit of product 1 sold and $30 for each unit of product 2 sold. The labor-hour requirements for the products in the three production departments are shown in the following table.
Product
Department 1 2
A 1.50 3.00
B 2.00 1.00
C 0.25 0.25
The departments’ production supervisors estimate that the following number of labor-hours will be available during the next month: 450 hours in department A, 350 hours in department B, and 50 hours in department C.
a. Develop a linear programming model to maximize profits.
b. Find the optimal solution. How much of each product should be produced, and what is the projected profit?
c. What are the scheduled production time and slack time in each department?
Problem #B-5
M&D Chemicals produces two products sold as raw materials to companies manufacturing bath soaps, laundry detergents, and other soap products. Based on an analysis of current inventory levels and potential demand for the coming month, M&D’s managers have specified that the total production of products 1 and 2 combined must be at least 350 gallons. Also, a major customer’s order for 125 gallons of product 1 must be satisfied. Product 1 requires two hours of processing time per gallon, and product 2 requires one hour; 600 hours of processing time are available in the coming month. Production costs are $2 per gallon for product 1 and $3 per gallon for product 2.
a. Determine the production quantities that will satisfy the specified requirements at minimum cost.
b. What is the total product cost?
c. Identify the amount of any surplus production.
Problem #B-6
Photo Chemicals produces two types of photograph-developing fluids. Both products cost Photo Chemicals $1 per gallon to produce. Based on an analysis of current inventory levels and outstanding orders for the next month, Photo Chemicals managers have specified that at least 30 gallons of product 1 and at least 20 gallons of product 2 must be produced during the next two weeks. They have also stated that an existing inventory of highly perishable raw material required in the production of both fluids must be used within the next two weeks. The current inventory of the perishable raw material is 80 pounds. Although more of this raw material can be ordered if necessary, any of the current inventory that is not used within the next two weeks will spoil—hence the management requirement that at least 80 pounds be used in the next two weeks. Furthermore, it is known that product 1 requires 1 pound of this perishable raw material per gallon and product 2 requires 2 pounds per gallon. Since the firm’s objective is to keep its production costs at the minimum possible level, the managers are looking for a minimum-cost production plan that uses all the 80 pounds of perishable raw material and provides at least 30 gallons of product 1 and at least 20 gallons of product 2. What is the minimum-cost solution?
Problem #B-7
A wood products firm uses available time at the end of each week to make goods for stock. Currently, two products on the list of items are produced for stock: a chopping board and a knife holder. Both items require three operations: cutting, gluing, and finishing. The manager of the firm has collected the following data on these products:
Time per unit (minutes)
Item Profit/unit Cutting Gluing Finishing
Chopping board $2 1.4 5 12
Knife holder $6 0.8 13 3
The manager has also determine that, during each week, 56 minutes are available for cutting, 650 minutes are available for gluing and 360 minutes are available for finishing.
a. Determine the optimal quantities of the decision variable
b. Which resources are not completely used by you solution? How much of each resource is unused.
Problem #B-8:
Given this linear programming model, solve the model and then answer the following questions:
Max z = 12×1 + 18×2 + 15×3
Subject to:
Machine 5×1 + 4×2 +3×3
Labor 4×1 +10×2 + 4×3
Materials 2×1 + 2×2 + 4×3
Product 2 x2
x1, x2, x3 >= 0
- Are any constraints binding?
- If the profit on product 3 was changes to $22 a unit, what would the values of the decision variables be? The objective function? Explain.
- If the profit on product 1 was changed to $22 a unit, what would the values of the decision variables be? The objective function? Explain.
- If 10 hours less of labor time were available, what would the values of the decision variables be? The objective function? Explain.
- If the manager decided that as many as 20 units of product 2 could be produced (instead of 16), how much additional profit would be generated?
Problem #B-9:
A garden store prepares various grades of pine back for mulch: nuggets (x1), mini-nuggets (x2), and chips (x3). The process requires pine bark, machine time, labor time and storage space. The following model has been developed:
Max z = 9×1 + 9×2 + 6×3
Subject to:
Bark 5×1 + 6×2 + 3×3
Machine 2×1 + 4×2 + 5×3
Labor 2×1 + 4×2 + 3×3
Storage 1×1 + 1×2 + 1×3
x1, x2, x3 >= 0
- What is the shadow price of a pound of pine bark? Over what range is this price value appropriate?
- What is the maximum price the store would be justified in paying for additional pine bark?
- What is the shadow price of labor? Over what range is this value in effect?
- The manager obtained additional machine time though better scheduling. How much additional machine time can be effectively used for this operation? Why?
- If the manager can obtain either additional pine bark or additional storage space, which one should he choose and how much (assuming additional quantities cost the same as usual)?
- If a change in the chip operation increased the profit on chips from $6 per bag to $7 per bag, would the value of the objective function change? If so, what would the new value be?
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Solution #B-1:
a.
x1 = 2
x2 = 9
Profit = 35
b.
A = 24
B = 20
Profit = 204
Solution #B-2:
Max z = $40H + $30W
Subject to:
Fabrication: 4H + 2W
Assembly: 2H + 6W
H = 132
W = 36
Profit = $6,360
Solution #B-3:
a.
x1 = 4, x2 = 0, x3 = 18
Profit = 106
b.
x1 = 15, x2 = 10, x3 = 0
Profit = 210
Solution #B-4:
a.Max 25X1 + 30X2
1.5X1 + 3X2 £ 450 (Dept A)
2X1 + 1X2 £ 350 (Dept B)
.25X1 + .25X2 £ 50 (Dept C)
X1, X2 ³ 0
b.X1 = 100, X2 = 100, Profit = 5500
c.Substituting the optimal values into the constraints we find that we use all the capacity in departments A and C but only 300 hours in department B. Thus, department B has 50 hours of slack.
Solution #B-5:
a.Min 2X1 + 3X2
X1 ³ 125 (Product 1 demand)
X1 + X2 ³ 350 (Total production)
2X1 + X2 £ 600 (Processing time)
X1, X2 ³ 0
b.X1 = 250, X2 = 100, Total production cost = $800
c.There is a surplus production of 125 gallons of product 1.
Solution #B-6:
Min 1X1 + 1X2
1X1 ³ 30 (Product 1 min)
1X2 ³ 20 (Product 2 min)
1X1 + 2X2 ³ 80 (Raw material)
X1, X2 ³ 0
The optimal solution is X1 = 30, X2 = 25, Cost = $55.
Solution #B-7:
a. Board = 0, Holder = 50, Profit = $300
b. Cutting = 16 minutes
Gluing = 0 minutes
Finishing = 210 minutes
Solution #B-8:
a. The first constraint (machine) and the third constraint (material) are binding. In other words, there are no excess machine hours or materials.
b. The range of optimality for the objective function coefficient of product 3 is from 13.5 to 36. Therefore an increase from 15 to 22 would not change the value of the decision variables. However, the objective function value would increase from 792 to 792 + 48 (22 – 15). Therefore the new value of z = 1128.
c. The range of optimality for the objective function coefficient of product 1 is from –¥ to 22.2. Since 22 is within the range, the change would not affect the value of decision variables. Since x1 is not a basic variable, the objective function value will not be affected (we are not producing any units of product 1).
d. We have a slack of 56 hours, and the range of feasibility lower limit for the second constraint is 232. Therefore, reducing the available labor hours by 10 (288 – 10 = 278) will not affect the value of the decision variables. The objective function value will not change either. However, there will be 10 hours less slack.
e. If no additional machine hours and materials are obtained, there would not be any change in the profit (z). No change is allowed in the objective function value because all machine hours and all materials are used (constraint 1 and constraint 3 are binding).
Solution #B-9:
a. The shadow price of a pound of bark is $1.50. This shadow price is in effect from 550 lbs. to 750 lbs. of bark (range of feasibility for the first constraint right hand side).
b. 1.50 per pound.
c. The shadow price of 1 labor hour is zero because we currently have 105 excess labor hours remaining. This shadow price is in effect from 375 hours to infinity.
d. We can not use any additional machine hours because we currently have 75 minutes of excess machine time.
e. Maximum possible increase for pine bark constraint is 150 lbs. (750 – 600). Maximum possible increase for storage constraint is 7.89 bags.
(1.50) (150) = $225 (expected increase in profit for pine bark)
(1.50) (7.89) = $11.83 (expected increase in profit for storage)
Therefore, add 150 pounds of pine bark.
f. The range of optimality for the objective function coefficient of chips (x3) is from 5.4 to 9. Therefore an increase from $6 to $7 would not change the value of the decision variables. However, the optimal objective function value (z) would increase from 1125 to 1125 + 1(75 units) = $1200.