Linear Programming -Two Hypothetical Examples

University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

233

Pages:

10
Author:

Urechsei6w

TWO HYPOTHETICAL EXAMPLES 1. A furniture manufacturer produces two types of desks: Standard and Executive. These desks are sold to an office furniture wholesaler, and for all practical purposes, there is an unlimited market for any mix of these desks, at least within the manufacturer’s production capacity. Each desk has to go through four basic operations: cutting of the lumber, joining of the pieces, prefinishing, and final finish. Each unit of the Standard desk produced takes 48 minutes of cutting time, 2 hours of joining, 40 minutes of prefinishing, and 5 hours and 20 minutes of final finishing time. Each unit of the Executive desk requires 72 minutes of cutting, 3 hours of joining, 2 hours of prefinishing, and 4 hours of final finishing time. The daily capacity for each operation amounts to 16 hours of cutting, 30 hours of joining, 16 hours of prefinishing, and 64 hours of final finishing time. The profit per unit produced is $40 for the Standard desk and $50 for the Executive desk. What product mix is optimal? 2. A firm produces 3 types of refined chemicals: A, B, and C. At least 4 tons of A, 2 tons of B, and 1 ton of C have to be produced per day. The inputs used are compounds X and Y. Each ton of X yields 1/4 ton of A, 1/4 ton of B, and 1/12 ton of C. Each ton of Y yields 1/2 ton of A, 1/10 ton of B, and 1/12 ton of C. Compound X costs $250 per ton, compound Y $400 per ton. The cost of processing is $250 per ton of X and $200 per ton of Y. Amounts produced in excess of daily requirements have no value as the products undergo chemical changes if not used immediately. The problem is to find the minimum cost input mix. E (0, 40/3) 4/5 S + 6/5 E <= 16 (20, 0) S E 2 S + 3 E <= 30 (0, 10) (15, 0) S E 2/3 S + 2 E <= 16 (0, 8) (24, 0) S E (0, 16) 16/3 S + 4 E <= 64 (12, 0) S E (0, 16) (0, 40/3) (0, 10) (0, 8) (12, 0) (15, 0) (20, 0) (24, 0) S E (0, 8) (6, 6) (9, 4) (0, 0) (12, 0) S E Z = 800 Z = 560 (0, 8) (6, 6) (9, 4) Z = 400 (0, 0) (12, 0) S Y (0, 8) X/4 + Y/2 >= 4 (16, 0) X (0, 20) Y X/4 + Y/10 >= 2 X (8, 0) Y (0, 12) X/12 + Y/12 >= 1 (12, 0) X Y (0, 20) Z=9K Z = 6.4K (16/3, 20/3) (8, 4) Z=4K (16, 0) X OBSERVATIONS ON THE GRAPHICAL METHOD FOR SOLVING A LINEAR PROGRAM 1. The set of feasible plans is called the feasible set or feasible region. It is always polygonal or polyhedral. 2. A constraint is said to be binding or active if it is satisfied at equality at the optimal solution. 3. Every equality (=) constraint is binding. 4. A constraint is said to be inactive or non binding if it is satisfied with strict inequality at the optimal solution. 5. Geometrically, an active constraint is one that passes through the optimal solution. 6. Geometrically, an inactive constraint is one that does not pass through the optimal solution. 7. There may be more than one optimal solution to a linear program, i.e., there may be multiple optima. 8. A linear program is unbounded if there exist feasible plans with arbitrarily large (if a max problem) or arbitrarily small (if a min problem) objective values. If this happens in practice, the formulation has been mis-specified. 9. A linear program is infeasible if there is no plan that satisfies all of the constraints.