Unformatted text preview:

Linear ProgrammingSlide 2Slide 3Formulating a ProblemFormulating a Problem Example E.1Formulating a Problem Example E.1 continuedFormulating a Problem Example E.1 continuedSlide 8Formulating a Problem with InequalitiesFormulating a Problem Application E.1Application E.1Graphic AnalysisGraphic Analysis Example E.2Graphic Analysis Example E.3Graphic Analysis Identify the feasible regionPlotting Crandon Mfg. ConstraintsSlide 17Slide 18Slide 19Slide 20Slide 21Iso-profit Line and Visual Solution for Crandon Mfg.Slide 23Algebraic Solution for Crandon Mfg.Slack & Surplus VariablesSlack Variables for Crandon Mfg.Sensitivity AnalysisComputer SolutionsComputer Solution Output from OM Explorer for the Stratton CompanyComputer Solution Output from OM Explorer for the Stratton CompanyComputer SolutionSlide 32Slide 33Slide 34Product Mix Problem Application E.6Product Mix Problem Application E.6Process Design Application E.7Process Design Application E.7Blending Problem Application E.8Blending Problem Application E.8Portfolio Selection Application E.9Portfolio Selection Application E.9Shift Scheduling Application E.10Shift Scheduling Application E.10Production Planning Application E.11Production Planning Application E.11Slide 47Solved Problem 1Slide 49Slide 50Slide 51© 2007 Pearson EducationLinear ProgrammingSupplement E© 2007 Pearson EducationLinear programming: A technique that is useful for allocating scarce resources among competing demands.Objective function: An expression in linear programming models that states mathematically what is being maximized (e.g., profit or present value) or minimized (e.g., cost or scrap).Decision variables: The variables that represent choices the decision maker can control.Constraints: The limitations that restrict the permissible choices for the decision variables.Linear Programming© 2007 Pearson EducationFeasible region: A region that represents all permissible combinations of the decision variables in a linear programming model. Parameter: A value that the decision maker cannot control and that does not change when the solution is implemented.Certainty: The word that is used to describe that a fact is known without doubt.Linearity: A characteristic of linear programming models that implies proportionality and additivity – there can be no products or powers of decision variables.Nonnegativity: An assumption that the decision variables must be positive or zero.Linear Programming© 2007 Pearson EducationFormulating a ProblemStep 1. Define the Decision Variables.Step 2.Write Out the Objective Function.Step 3. Write Out the Constraints.Product-mix problem: A one-period type of planning problem, the solution of which yields optimal output quantities (or product mix) of a group of services or products subject to resource capacity and market demand constraints.© 2007 Pearson EducationThe Stratton Company produces 2 basic types of plastic pipe. Three resources are crucial to the output of pipe: extrusion hours, packaging hours, and a special additive to the plastic raw material. Below is next week’s situation. Formulating a ProblemExample E.1ProductResource Type 1 Type 2Resource AvailabilityExtrusion 4 hr 6 hr 48 hrPackaging 2 hr 2 hr 18 hrAdditive mix 2 lb 1 lb 16 lb© 2007 Pearson Educationx1 = amount of type 1 pipe produced and sold next week, 100-foot incrementsx2 = amount of type 2 pipe produced and sold next week, 100-foot incrementsStep 1 – Define the decision variablesFormulating a ProblemExample E.1 continuedProductResource Type 1 Type 2Resource AvailabilityExtrusion 4 hr 6 hr 48 hrPackaging 2 hr 2 hr 18 hrAdditive mix 2 lb 1 lb 16 lb© 2007 Pearson EducationStep 2 – Define the objective functionProductResource Type 1 Type 2Resource AvailabilityExtrusion 4 hr 6 hr 48 hrPackaging 2 hr 2 hr 18 hrAdditive mix 2 lb 1 lb 16 lbFormulating a Problem Example E.1 continuedMax Z = $34 x1 + $40 x2Objective is to maximize profits (Z)Each unit of x1 yields $34, and each unit of x2 yields $40.© 2007 Pearson EducationStep 3 – Formulate the constraintsFormulating a Problem Example E.1 continuedProductResource Type 1 Type 2Resource AvailabilityExtrusion 4 hr 6 hr 48 hrPackaging 2 hr 2 hr 18 hrAdditive mix 2 lb 1 lb 16 lb4 x1 + 6 x2  482 x1 + 2 x2  18 2 x1 + x2  16 ExtrusionPackagingAdditive mix© 2007 Pearson EducationTypically the constraining resources have upper or lower limits. e.g., for the Stratton Company, the total extrusion time must not exceed the 48 hours of capacity available, so we use the ≤ sign.Negative values for constraints x1 and x2 do not make sense, so we add nonnegativity restrictions to the model:x1 ≥ 0 and x2 ≥ 0 (nonnegativity restrictions)Other problem might have constraining resources requiring >, >, =, or < restrictions.Formulating a Problem with Inequalities© 2007 Pearson EducationFormulating a ProblemApplication E.1The Crandon Manufacturing Company produces two principal product lines. One is a portable circular saw, and the other is a precision table saw. Two basic operations are crucial to the output of these saws: fabrication and assembly. The maximum fabrication capacity is 4000 hours per month; each circular saw requires 2 hours, and each table saw requires 1 hour. The maximum assembly capacity is 5000 hours per month; each circular saw requires 1 hour, and each table saw requires 2 hours. The marketing department estimates that the maximum market demand next year is 3500 saws per month for both products. The average contribution to profits and overhead is $900 for each circular saw and $600 for each table saw.© 2007 Pearson EducationApplication E.1Management wants to determine the best product mix for the next year so as to maximize contribution to profits and overhead. Also, it is interested in the payoff of expanding capacity or increasing market share.Maximize: 900x1 + 600x2 = ZSubject to: 2x1 + 1x2  4,000 (Fabrication) 1x1 + 2x2  5,000 (Assembly) 1x1 + 1x2  3,500 (Demand) x1, x2 ≥ 0 (Nonnegativity)© 2007 Pearson EducationGraphic AnalysisMost linear programming problems are solved with a computer. However, insight into the meaning of the computer output, and linear programming concepts in general, can be gained by analyzing a simple two-variable problem graphically. Graphic method of linear programming: A type of graphic analysis that involves the following five steps: plotting the


View Full Document

WU BU 347 - Linear Programming

Download Linear Programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linear Programming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linear Programming 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?