Linear Programming - Intro, Formulations & Geometry

Short-Run Manufacturing Problems at DEC In the fourth quarter of 1989, the corporate demand/supply group of Digital Equipment Corporation (DEC) was under pressure to come up with a manufacturing plan for dealing with a series of major supply shortfalls that were impacting on the production, revenue, and customer satisfaction of one of DEC's new family of general purpose computer systems and workstations. The critical components for this family of systems that were going to be in short supply in the first quarter of 1989 were CPU chip sets, 1meg memory boards, 256K memory boards, and disk drives. Pertinent data for these components and their usage in the family of systems is given below: System List Price Chip Sets 1-Meg Memory GP-1 $60,000 1 2 – 0.3 GP-2 $40,000 1 – 2 1.7 GP-3 $30,000 1 – 1 – WS-1 $30,000 1 – 1 1.4 WS-2 $15,000 1 – 1 – 7,000 4,000 8 – 16,000 3 – 7,000 1989 First Quarter Availability: 256K Memory Disk Drive Avg. Brian Shannahan of corporate supply/demand was asked on short notice to formulate a manufacturing strategy given these shortfalls. Brian wanted to take into account both the importance of revenue for DEC as well as the maintenance of DEC's reputation for customer satisfaction and service. Brian took a quick stab at the market/sales situation and then developed the following target data for the first quarter of 1989: System Minimum Acceptable Supply Maximum Customer Demand GP-1 – 1,800 GP-2 500 – GP-3 – 300 WS-1 500 – WS-2 400 – GP FAMILY – 3,800 WS FAMILY – 3,200 Brian Shannahan then proceeded to analyze DEC's problem and to formulate a manufacturing strategy. Formulation of Sample DEC Manufacturing Problem Common Type of Mathematical Model New Bedford Steel DEC Manufacturing An objective to be optimized minimize procurement cost maximize quarterly revenue A set of decision variables amount of coal to contract with each supplier A,B,...,H number of units of each family to produce G1, G2, G3, W1, W2 49.50A + ...+ 80.00H 60G1 + ... + 15W2 An objective function that expresses the objective in terms of the decision variables Constraints that limit or otherwise impose requirements on the relationships between (Rail capacity) A + C + G + H £ 650 (Demand for GP family) G1 + G2 + G3 £ 3,800 A ≥ 0, B ≥ 0 G1 ≥ 0, ..., W2 ≥ 0 the decision variables Nonnegativity conditions on the decision variables Constraints can be equality or inequality constraints. If inequality, they can be less than or equal to (£) or greater than or equal to (≥). Each constraint can be rearranged to have the format, e.g., G1 + G2 + G3 £ constraint function relation 3800 right-hand side (RHS) A feasible plan or feasible solution is an assignment of decision variables that satisfies all constraints and nonnegativity conditions. The goal of the problem is to find a feasible plan that optimizes the objective function, i.e., an assignment of decision variables that satisfies all constraints and optimizes the objective. This is called a constrained optimization problem. An optimal plan or optimal solution is a feasible plan that achieves the best value of the objective function over all other feasible plans. Finally, we call the problem a linear program if all constraint functions are linear, and if the objective function is linear, i.e., of the form, e.g., A + 2B – 5C + 7D, not not A2 + B + C + D, not AB + C + D, (A2 – sin(B/C)) log (D). How Linear Programs are Solved on the Computer 1. A linear programming model is solved on a computer by a technique called the Simplex Method, developed by Dantzig in 1947. (Some commercial codes now use an alternative method, called the Interior Point method, developed by Karmarkar in 1984.) 2. The simplex method works by performing a sequence of pivots. Each pivot starts with a feasible solution and either generates an improved feasible solution or concludes that the current feasible solution is the optimal solution. 3. At each pivot, the computer must solve a system of m equations in m variables, where m is the number of constraints in the problem. 4. Typically, the number of pivots that must be performed is roughly proportional to the number n of decision variables in the problem. Therefore, the more constraints the problem has ( m ) and the more decision variables the problem has ( n ) , the more computer time will be needed to solve the problem. 5. The simplex method is conceptually simple and easy to learn. We will teach it to you in about one hour. 6. Today – solve LP’s with 1000’s of constraints, 10,000’s of decision variables on a desk top machine with commercial packages. Excel Spreadsheet for DEC Short Run Manufacturing Problem Short Run Manufacturing Problems at DEC GP-1 Production of Minimum supply Maximum demand GP-2 GP-3 WS-1 WS-2 0 1800 500 3800 0 300 500 3200 400 3200 1 2 1 1 1 1 2 1.70 1 1 1.40 1 0.30 1 1 1 1 30 15 Total Chip sets 1 Meg Mem 256K Mem Disk Drives Supply 7000 4000 16000 3000 0 0 0 0 GP Family WS Family Demand 3800 3200 0 0 1 0 60 Revenue 40 30 Microsoft Excel 4.0 Answer Report Worksheet: DEC Target Cell (Max) Cell $C$24 Name Revenue Total Original Value Final Value 0 213912 Original Value Final Value 0 0 0 0 0 1800 1035.29 300 500 2700 Adjustable Cells Cell $D$8 $E$8 $F$8 $G$8 $H$8 Name Production of GP-1 Production of GP-2 Production of GP-3 Production of WS-1 Production of WS-2 Microsoft Excel 4.0 Sensitivity Report Worksheet: DEC Changing Cells Cell $D$8 $E$8 $F$8 $G$8 $H$8 Name Production of GP-1 Production of GP-2 Production of GP-3 Production of WS-1 Production of WS-2 Final Value Reduced Cost Objective Coefficient Allowable Increase Allowable Decrease 1800 1035.29 300 500 2700 52.94 0 30 -17.94 0 60 40 30 30 15 1E+30 1E+30 1E+30 17.94 1E+30 52.94 21.79 30 1E+30 15 Final Value Shadow Price Constraint R.H. Side Allowable Increase Allowable Decrease 6335 3600 5571 3000 3135 3200 0 0 0 24 0 15 7000 4000 16000 3000 3800 3200 1E+30 1E+30 1E+30 1130 1E+30 500 664.71 400 10429.41 910 664.71 2300 Constraints Cell $C$15 $C$16 $C$17 $C$18 $C$21 $C$22 Name Chip sets Total 1 Meg Mem Total 256K Mem Total Disk Drives Total GP Family Total WS Family Total