Chapter 3 Introduction to Linear Programming3.1 What Is a Linear Programming Problem?Example 1: Giapetto’s WoodcarvingEx. 1 - continuedExample 1: SolutionEx. 1 - Solution continuedEx. 1 - Solution continuedSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 153.2 – The Graphical Solution to a Two-Variable LP ProblemSlide 17Slide 18Slide 19Slide 20Slide 21Example 2 : Dorian AutoEx. 2: continuedExample 2: SolutionEx. 2 – Solution continuedSlide 26Slide 27Slide 283.3 Special CasesSlide 30Slide 31Example 6: Diet ProblemEx. 6 - continuedExample 6: SolutionEx. 6 – Solution continuedSlide 363.5 A Work-Scheduling Problem3.6 A Capital Budgeting ProblemSlide 393.7 Short-Term Financial Planning3.8 Blending Problems3.9 Production Process Models3.10 Using Linear Programming to Solve Multiperiod Decision Problems: An Inventory ModelExample 14: Sailco InventoryEx. 14 - continuedExample 14: SolutionEx. 14 – Solution continuedSlide 48Slide 493.11 Multiperiod Financial Models3.12 Multiperiod Work SchedulingChapter 3Introduction to Linear Programmingto accompanyOperations Research: Applications and Algorithms 4th editionby Wayne L. WinstonCopyright (c) 2004 Brooks/Cole, a division of Thomson Learning, Inc.23.1 What Is a Linear Programming Problem?Linear Programming (LP) is a tool for solving optimization problems.Linear programming problems involve important terms that are used to describe linear programming.3Example 1: Giapetto’s WoodcarvingGiapetto’s, Inc., manufactures wooden soldiers and trains. Each soldier built:Sell for $27 and uses $10 worth of raw materials.Increase Giapetto’s variable labor/overhead costs by $14.Requires 2 hours of finishing labor.Requires 1 hour of carpentry labor.Each train built:Sell for $21 and used $9 worth of raw materials. Increases Giapetto’s variable labor/overhead costs by $10.Requires 1 hour of finishing labor.Requires 1 hour of carpentry labor.4 Ex. 1 - continuedEach week Giapetto can obtain:All needed raw material. Only 100 finishing hours.Only 80 carpentry hours. Demand for the trains is unlimited.At most 40 soldiers are bought each week. Giapetto wants to maximize weekly profit (revenues – costs). Formulate a mathematical model of Giapetto’s situation that can be used to maximize weekly profit.5Example 1: Solution The Giapetto solution model incorporates the characteristics shared by all linear programming problems. Decision variables should completely describe the decisions to be made.x1 = number of soldiers produced each weekx2 = number of trains produced each weekThe decision maker wants to maximize (usually revenue or profit) or minimize (usually costs) some function of the decision variables. This function to maximized or minimized is called the objective function. For the Giapetto problem, fixed costs do not depend upon the the values of x1 or x2.6Ex. 1 - Solution continuedGiapetto’s weekly profit can be expressed in terms of the decision variables x1 and x2:Weekly profit = weekly revenue – weekly raw material costs – the weekly variable costs = 3x1 + 2x2Thus, Giapetto’s objective is to chose x1 and x2 to maximize weekly profit. The variable z denotes the objective function value of any LP.Giapetto’s objective function is Maximize z = 3x1 + 2x2The coefficient of an objective function variable is called an objective function coefficient.7 Ex. 1 - Solution continuedAs x1 and x2 increase, Giapetto’s objective function grows larger. For Giapetto, the values of x1 and x2 are limited by the following three restrictions (often called constraints):Each week, no more than 100 hours of finishing time may be used. (2 x1 + x2 ≤ 100)Each week, no more than 80 hours of carpentry time may be used. (x1 + x2 ≤ 80)Because of limited demand, at most 40 soldiers should be produced. (x1 ≤ 40)8 The coefficients of the decision variables in the constraints are called the technological coefficients. The number on the right-hand side of each constraint is called the constraint’s right-hand side (or rhs).To complete the formulation of a linear programming problem, the following question must be answered for each decision variable.Can the decision variable only assume nonnegative values, or is the decision variable allowed to assume both positive and negative values?If the decision variable can assume only nonnegative values, the sign restriction xi ≥ 0 is added. If the variable can assume both positive and negative values, the decision variable xi is unrestricted in sign (often abbreviated urs).9 Ex. 1 - Solution continuedFor the Giapetto problem model, combining the sign restrictions x1≥0 and x2≥0 with the objective function and constraints yields the following optimization model: Max z = 3x1 + 2x2 (objective function)Subject to (s.t.)2 x1 + x2 ≤ 100 (finishing constraint) x1 + x2 ≤ 80 (carpentry constraint) x1 ≤ 40 (constraint on demand for soldiers) x1 ≥ 0 (sign restriction) x2 ≥ 0 (sign restriction)10 A function f(x1, x2, …, xn) of x1, x2, …, xn is a linear function if and only if for some set of constants, c1, c2, …, cn, f(x1, x2, …, xn) = c1x1 + c2x2 + … + cnxn.For any linear function f(x1, x2, …, xn) and any number b, the inequalities f(x1, x2, …, xn) ≤ b and f(x1, x2, …, xn) ≥ b are linear inequalities.11 A linear programming problem (LP) is an optimization problem for which we do the following:Attempt to maximize (or minimize) a linear function (called the objective function) of the decision variables.The values of the decision variables must satisfy a set of constraints. Each constraint must be a linear equation or inequality.A sign restriction is associated with each variable. For any variable xi, the sign restriction specifies either that xi must be nonnegative (xi ≥ 0) or that xi may be unrestricted in sign.12 The fact that the objective function for an LP must be a linear function of the decision variables has two implications:1. The contribution of the objective function from each decision variable is proportional to the value of the decision variable. For example, the contribution to the objective function for 4 soldiers is exactly fours times the contribution of 1 soldier.2. The contribution to the objective function for any variable is independent of the other decision variables. For