Linear and Integer Programming Models2.1 Introduction to Linear ProgrammingIntroduction to Linear ProgrammingSlide 4Slide 5The Galaxy Industries Production Problem – A Prototype ExampleSlide 7Slide 8Slide 9Slide 10The Galaxy Linear Programming ModelSlide 122.3 The Graphical Analysis of Linear ProgrammingSlide 14Graphical Analysis – the Feasible RegionSlide 16Slide 17Solving Graphically for an Optimal SolutionThe search for an optimal solutionSummary of the optimal solutionExtreme points and optimal solutionsMultiple optimal solutions2.4 The Role of Sensitivity Analysis of the Optimal SolutionSensitivity Analysis of Objective Function Coefficients.Slide 25Slide 26Slide 27Sensitivity Analysis of Right-Hand Side ValuesSlide 29Shadow PricesShadow Price – graphical demonstrationRange of FeasibilitySlide 33Slide 34Slide 35The correct interpretation of shadow pricesOther Post - Optimality Changes2.5 Using Excel Solver to Find an Optimal Solution and Analyze ResultsUsing Excel SolverSlide 40Using Excel Solver – Optimal SolutionSlide 42Using Excel Solver –Answer ReportUsing Excel Solver –Sensitivity ReportSlide 45Infeasible ModelSolver – Infeasible ModelUnbounded solutionSolver – Unbounded solutionSolver – An Alternate Optimal SolutionSlide 512.8 Cost Minimization Diet ProblemCost Minimization Diet ProblemThe Diet Problem - Graphical solutionSlide 55Computer Solution of Linear Programs With Any Number of Decision VariablesSlide 571Linear and Integer Linear and Integer Programming ModelsProgramming ModelsLinear and Integer Linear and Integer Programming ModelsProgramming ModelsChapter 22•A Linear Programming model seeks to maximize or minimize a linear function, subject to a set of linear constraints.•The linear model consists of the followingcomponents:– A set of decision variables.– An objective function.– A set of constraints.2.1 Introduction to Linear Programming2.1 Introduction to Linear Programming3Introduction to Linear ProgrammingIntroduction to Linear Programming•The Importance of Linear Programming–Many real world problems lend themselves to linear programming modeling. –Many real world problems can be approximated by linear models.–There are well-known successful applications in:•Manufacturing•Marketing•Finance (investment)•Advertising•Agriculture4•The Importance of Linear Programming–There are efficient solution techniques that solve linear programming models.–The output generated from linear programming packages provides useful “what if” analysis.Introduction to Linear ProgrammingIntroduction to Linear Programming5Introduction to Linear ProgrammingIntroduction to Linear Programming•Assumptions of the linear programming model–The parameter values are known with certainty.–The objective function and constraints exhibit constant returns to scale.–The Additivity assumption): There are no interactions between the decision variables.–The Continuity assumption: Variables can take on any value within a given feasible range.6The Galaxy Industries Production Problem – The Galaxy Industries Production Problem – A Prototype ExampleA Prototype Example•Galaxy manufactures two toy doll models:–Space Ray. –Zapper. •Two resources are used in the production process. The resources are limited to–1000 pounds of special plastic.–40 hours of production time per week.7•Marketing requirement–Total production cannot exceed 700 dozens.–Number of dozens of Space Rays cannot exceed number of dozens of Zappers by more than 350.•Technological input–Space Rays requires 2 pounds of plastic and 3 minutes of labor per dozen.– Zappers requires 1 pound of plastic and 4 minutes of labor per dozen.The Galaxy Industries Production Problem – The Galaxy Industries Production Problem – A Prototype ExampleA Prototype Example8• The current production plan calls for: –Producing as much as possible of the more profitable product, Space Ray ($8 profit per dozen).–Use resources left over to produce Zappers ($5 profit per dozen), while remaining within the marketing guidelines.•The current production plan consists of:Space Rays = 450 dozenZapper = 100 dozenProfit = $4100 per weekThe Galaxy Industries Production Problem –The Galaxy Industries Production Problem – A Prototype Example A Prototype Example8(450) + 5(100)9Management is seeking a production schedule that will increase the company’s profit.10A linear programming model can provide an insight and an intelligent solution to this problem.11•Decisions variables::–X1 = Weekly production level of Space Rays (in dozens) –X2 = Weekly production level of Zappers (in dozens).•Objective Function:– Weekly profit, to be maximizedThe Galaxy Linear Programming ModelThe Galaxy Linear Programming Model12Max 8X1 + 5X2 (Weekly profit)subject to2X1 + 1X2  1000 (Plastic)3X1 + 4X2  2400 (Production Time) X1 + X2  700 (Total production) X1 - X2  350 (Mix) Xj> = 0, j = 1,2 (Nonnegativity)The Galaxy Linear Programming ModelThe Galaxy Linear Programming Model132.3 2.3 The Graphical Analysis of Linear The Graphical Analysis of Linear ProgrammingProgramming The set of all points that satisfy all the constraints of the model is called aFEASIBLE REGIONFEASIBLE REGION14 Using a graphical presentation we can represent all the constraints, the objective function, and the three types of feasible points.15The non-negativity constraintsX2X1Graphical Analysis – the Feasible RegionGraphical Analysis – the Feasible Region161000500FeasibleX2InfeasibleProduction Time3X1+4X2  2400 Total production constraint: X1+X2  700 (redundant)500700The Plastic constraint2X1+X2  1000X1700Graphical Analysis – the Feasible RegionGraphical Analysis – the Feasible Region171000500FeasibleX2InfeasibleProduction Time3X1+4X22400 Total production constraint: X1+X2 700 (redundant)500700Production mix constraint:X1-X2  350The Plastic constraint2X1+X2 1000X1700Graphical Analysis – the Feasible RegionGraphical Analysis – the Feasible Region•There are three types of feasible pointsInterior points.Boundary points. Extreme points.18Solving Graphically for an Solving Graphically for an Optimal SolutionOptimal Solution19The search for an optimal solutionThe search for an optimal solutionStart at some arbitrary profit, say profit = $2,000...Then increase the profit, if