Report

Chapter Topics Linear Programming: Formulation and Applications Model Formulation A Maximization Model Example Graphical Solutions of Linear Programming Models A Minimization Model Example Irregular Types of Linear Programming Models Characteristics of Linear Programming Problems Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-1 Linear Programming: An Overview Objectives of business decisions frequently involve maximizing profit or minimizing costs. Linear programming uses linear algebraic relationships to represent a firm’s decisions, given a business objective, and resource constraints. Model formulation steps: Step 1 : Clearly define the problem: Objectives and decision to be made Step 2 : Construct the objective function Step 3 : Formulate the constraints Step 4: Solve the model 2-2 LP Model Formulation Product mix problem - Beaver Creek Pottery Company Resource Requirements Labor (Hr./Unit) Clay (Lb./Unit) Profit ($/Unit) Bowl 1 4 40 Mug 2 3 50 Product • How many bowls and mugs should be produced to maximize profits given labor and materials constraints? LP Model Formulation Resource Availability: 40 hrs of labor per day 120 lbs of clay Decision Variables: B = number of bowls to produce per day M = number of mugs to produce per day Objective Function: Maximize Z = $40B + $50M Where Z = profit per day Resource 1B + 2M 40 hours of labor Constraints: 4B + 3M 120 pounds of clay Non-Negativity Constraints: B 0; M 0 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-4 LP Model Formulation Product mix problem - Beaver Creek Pottery Company Complete Linear Programming Model: Maximize Z = $40B + $50M subject to: 1B + 2M 40 4B + 3M 120 B, M 0 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-5 Feasible Solutions A feasible solution does not violate any of the constraints: Example: B = 5 bowls M = 10 mugs Z = $40B + $50M= $700 Labor constraint check: Clay constraint check: 1(5) + 2(10) = 25 ≤ 40 hours 4(5) + 3(10) = 70 ≤ 120 pounds Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-6 Infeasible Solutions An infeasible solution violates at least one of the constraints: Example: B = 10 bowls M = 20 mugs Z = $40B + $50M= $1400 Labor constraint check: 1(10) + 2(20) = 50 > 40 hours Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-7 Graphical Solution of LP Models Graphical solution is limited to linear programming models containing only two decision variables (can be used with three variables but only with great difficulty). Graphical methods provide visualization of how a solution for a linear programming problem is obtained. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-8 Coordinate Axes Graphical Solution of Maximization Model (1 of 12) M M is mugs B B is bowls Figure 2.2 Coordinates for graphical analysis Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-9 Optimal Solution Graphical Solution of Maximization Model (9 of 12) M 40M+50B B Figure 2.10 Identification of optimal solution point Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-10 Product mix problem - Beaver Creek Pottery Company • Gather information needed to conduct model building and analysis (steps 2 and 3) – Available capacity in each activity/process – How much capacity in each activity needed by each product – Profitability of each product Given parameters (known data) Unit Profit Bowl Mug $40 $50 Production Time (Hours ) Used Per Unit Produced Resources Available labor 1 2 40 clay 4 3 120 LP Model Formulation Product mix problem - Beaver Creek Pottery Company Complete Linear Programming Model: Maximize Z = $40B + $50M subject to: 1B + 2M 40 4B + 3M 120 B, M 0 Developing a Spreadsheet Model • Step #1: Data Cells – Enter all of the data for the problem on the spreadsheet. – Make consistent use of rows and columns. – It is a good idea to color code these “data cells” (e.g., light blue). Beaver Creek Pottery Company Unit Profit Bowl Mug 40 50 Resources Used Per Unit Produced Resources Available Labor 1 2 40 Clay 4 3 120 2-13 Developing a Spreadsheet Model • Step #2: Changing Cells – Add a cell in the spreadsheet for every decision that needs to be made. – If you don’t have any particular initial values, just enter 0 in each. – It is a good idea to color code these “changing cells” (e.g., yellow with border). Beaver Creek Pottery Company Unit Profit Bowl Mug 40 50 Resources Resources Used Per Unit Produced Available Labor 1 2 40 Clay 4 3 120 Units produced 2-14 Developing a Spreadsheet Model • Step #3: Target Cell – Develop an equation that defines the objective of the model. – Typically this equation involves the data cells and the changing cells in order to determine a quantity of interest (e.g., total profit or total cost). – It is a good idea to color code this cell (e.g., orange with heavy border). Beaver Creek Pottery Company Unit Profit Bowl Mug 40 50 Resources Resources Used Per Unit Produced Available Labor 1 2 40 Clay 4 3 120 Units produced total profit 2-15 Developing a Spreadsheet Model • Step #4: Constraints – For any resource that is restricted, calculate the amount of that resource used in a cell on the spreadsheet (an output cell). – Define the constraint in consecutive cells. For example, if Quantity A <= Quantity B, put these three items (Quantity A, <=, Quantity B) in consecutive cells. Beaver Creek Pottery Company Unit Profit Bowl Mug 40 50 Resources Labor Clay Units produced Resources Used Per Unit Produced 1 2 4 3 Bowl Mug resources used < < Available 40 120 total profit 2-16 A Trial Solution Let’s do this problem in Excel…. Pay attention to Model layout and organization Data accuracy Steps in the Solver Addin Max or Min non-negativity option Linear optimization 2-17 Identifying the Target Cell and Changing Cells (Excel 2010) • • • • Choose the “Solver” from the Data tab. Select the cell you wish to optimize in the “Set Target Cell” window. Choose “Max” or “Min” depending on whether you want to maximize or minimize the target cell. Enter all the changing cells in the “By Changing Cells” window. 2-18 Some Important Options (Excel 2007) • Click on the “Options” button, and click in both the “Assume Linear Model” and the “Assume Non-Negative” box. – “Assume Linear Model” tells the Solver that this is a linear programming model. – “Assume Non-Negative” adds nonnegativity constraints to all the changing cells. 2-19 The Complete Solver Dialogue Box (Excel 2007) 2-20 Template for Resource-Allocation Problems Activities Constraints Unit Prof it Level of A ctivit y profit per unit of ac ti vi ty Resources Used res ourc e us ed per unit of ac ti vi ty c hanging c ell s SU M P RO D U C T (res ourc e used per unit, c hanging c ell s ) Resources A vailable <= Total Prof it SU M P RO D U C T (profit per unit, c hanging c ell s) 3-21 LP Model Formulation – Minimization (1 of 7) Two brands of fertilizer available Super-gro, Crop-quick. Field requires at least 16 pounds of nitrogen and 24 pounds of phosphate. Super-gro costs $6 per bag, Cropquick $3 per bag. Problem: How much of each brand to purchase to minimize total cost of fertilizer given following data ? Nitrogen (lb/bag) Phosphate (lb/bag) Super-gro 2 4 Crop-quick 4 3 Brand Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Chemical Contribution 2-22 LP Model Formulation – Minimization (2 of 7) Decision Variables: x1 = bags of Super-gro x2 = bags of Crop-quick The Objective Function: Minimize Z = $6x1 + 3x2 Where: $6x1 = cost of bags of Super-Gro $3x2 = cost of bags of Crop-Quick Model Constraints: 2x1 + 4x2 16 lb (nitrogen constraint) 4x1 + 3x2 24 lb (phosphate constraint) x1, x2 0 (non-negativity constraint) Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-23 Constraint Graph – Minimization (3 of 7) Minimize Z = $6x1 + $3x2 subject to: 2x1 + 4x2 16 4x2 + 3x2 24 x1, x2 0 Figure 2.16 Constraint lines for fertilizer model Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-24 Feasible Region– Minimization (4 of 7) Minimize Z = $6x1 + $3x2 subject to: 2x1 + 4x2 16 4x2 + 3x2 24 x1, x2 0 Figure 2.17 Feasible solution area Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-25 Optimal Solution Point – Minimization (5 of 7) Minimize Z = $6x1 + $3x2 subject to: 2x1 + 4x2 16 4x2 + 3x2 24 x1, x2 0 The optimal solution of a minimization problem is at the extreme point closest to the origin. Figure 2.18 The optimal solution point Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 2-26 Template for Cost-Benefit Tradeoff Problems Activities Constraints Unit Cost Level of A ctivit y c ost per unit of ac t iv it y Benef it A chieved benefit ac hi eved per unit of ac t iv it y c hanging c ell s S U M P RO D U C T (benefi t per unit , c hanging c ell s ) Benef it Needed >= Total Cost S U M P RO D U C T(c ost per uni t, c hangi ng cel ls ) 3-27 Types of Functional Constraints Type Resource constraint Benefit constraint Fixed-requirement constraint Form* Typical Interpretation Main Usage LHS ≤ RHS For some resource, Amount used ≤ Amount available Resource-allocation problems and mixed problems LHS ≥ RHS For some benefit, Level achieved ≥ Minimum Acceptable Cost-benefit-trade-off problems and mixed problems LHS = RHS For some quantity, Amount provided = Required amount Transportation problems and mixed problems * LHS = Left-hand side (a SUMPRODUCT function). RHS = Right-hand side (a constant). 3-28 Template for Mixed Problems Activities Unit Prof it or Cost profit/c ost pe r uni t of ac ti v it y Resources Used Constraints res ourc e us e d per unit of act iv i ty Level of A ctivit y SU M P RO DU C T (re s ourc e use d pe r uni t, c hanging c e ll s ) Resources A vailable <= Benef it A chieved be ne fit ac hi e ve d pe r uni t of ac ti v it y c hanging c e ll s SU M P RO DU C T (be ne fi t pe r unit , c hanging c e ll s ) Benef it Needed >= = Total Prof it or Cost S U M P R O D U C T (profi t/c os t pe r uni t, c hanging c e ll s ) 3-29