Linear Programming: Two GoalsWhere These Skills Fit in the Abstraction ProcessSpreadsheet DesignSteps in Formulating a Linear Programming Problem: Take #1Formulating a Linear Programming Problem: Take #2Common Types of LPs (aka Beginning of Your “Toolbox”)Product Mix & Make vs. Buy Pbs#1: Product Mix Decisions (Like Howie’s Hot Tub Problem)#2: Make vs. Buy DecisionsMake vs. Buy DecisionsMake vs. Buy Textbook Example: Weedwacker CompanyGeneralize Make vs. Buy(Investment Portfolio) Allocation Pbs#3: Investment Portfolio AllocationAllocation Problems Beyond Investment Portfolios#6: Multi-period Planning ProblemsKey Idea Elaborated#6a: Using Inventory to Meet Time Varying DemandExamples#6b: Multi-period Financial PlanningExamples1Linear Programming:Two GoalsFormulate LP’sFormulating LP’s is an artMany problems are variants on a standard problem“Pattern match” your current problem to one of those classicsLike brainteasers: can be frustrating but also funSolve LP’s in ExcelThink ahead about layout/design of spreadsheetCan use text’s examples as templates2Where These Skills Fit in the Abstraction ProcessReal world “problem opportunity”big confusing messProfessional assignmentObject/scope defined; rest is murkyTextbook level natural language descriptionall and only the relevant info includedCareful natural language descriptionfairly unambiguous but not compactMathematical formulationformal, precise, unambiguous, compactTractable implementation usually on computer, e.g., in Excel3Spreadsheet DesignObjectivesClear (communicate results/intuition to others)Reliable (is error-free)Auditable (can understand & know it’s error-free)Modifiable (re-use code rather than reinventing)GuidelinesBuild model around display of dataDon’t bury constants in formulasLogically close quantities should be physically closeDesign so formulae can be copiedUse color, shading, borders, and protectionDocument with text boxes & cell notes4Steps in Formulating a Linear Programming Problem: Take #1Understand the problem(Be willing to “get your hand’s dirty”)Identify the Decision Maker (DM)Identify the decision variables (DV’s)(This is often the key step.)State objective function as a linear combination of the DV’sState constraints as a linear combination of the DV’sIdentify upper or lower bounds on DV’s5Formulating a Linear Programming Problem: Take #2Master a “toolbox” of standard problem typesUnderstand the particular problem at handBe willing to “get your hand’s dirty”Identify the Decision Maker (DM), DM’s goals, etc.Recognize what type of problem it isUsually will be a “base type” + “whistles and bells”Sometimes need to blend several base typesSometimes won’t match any & have to start from scratchImport notation for DV’s from standard problem typeWrite down objective, constraints, bounds, etc.6Common Types of LPs (aka Beginning of Your “Toolbox”)1) Product mix2) Make vs. buy3) Investment/Portfolio allocation4) Transportation (will do in Chapter 5)5) Assignment Problem (will do in Chapter 5)6) Blending (will do with Chapter 5)7) Multi-period planningproduction schedulesfinancial flows8) DEA (covered in 94-833)We did product mix already. (Howie’s Pb.)We’ll cover three more of these today.7Product Mix & Make vs. Buy Pbs8#1: Product Mix Decisions(Like Howie’s Hot Tub Problem)Decision: How many of each type of product should be made (offered)Decision variablesXi = amount of product i to make (offer)ConstraintsNonnegative productionProduction capacity constraints (e.g., limits on resources which are consumed in the process of producing products)Objective: Maximize profit (or min cost)9#2: Make vs. Buy DecisionsSeveral products, each can be made in house or purchased from vendorsDecision: How much to make and how much to buy (separate sources), so ...Decision variablesfor each product i:Mi = amount of product i to make in houseBi = amount of product i to purchase10Make vs. Buy DecisionsConstraintsMeet demandProduction capacity constraintsNonnegativityObjective: Minimize cost (or max profit)ExamplesCHAMPUSOutsourcing/privatizationStaffing courses with adjuncts11Make vs. Buy Textbook Example: Weedwacker CompanyMeet demand for two types of trimmers30,000 electric & 15,000 gasCheaper to make than to buy $55 vs. $67 and $85 vs. $95, respectivelyBut producing in-house constrained by limited time in three departments10,000 hours in production department15,000 hours in assembly department5,000 hours in packaging departmentObjective: Minimize cost12Generalize Make vs. BuyProducts can be obtained through more than two sourcesDecision variablesXij = amount of product i obtained from source jConstraintsSupply constraints on each source jDemand constraints on each product iProduction capacity constraints on own productionNon-negativity13(Investment Portfolio) Allocation Pbs14#3: Investment Portfolio AllocationAllocate a pool of resources (e.g., money or workers) across several available “instruments”Decision variables – one for each instrumentXi = amount invested in instrument iConstraintsAll resources allocatedDiversity constraints on amount invested in any one instrument or type of instrumentNon-negativityObjective: Maximize return/benefitClassic Example: Ragsdale’s Blacksburg National Bank Problem15Allocation ProblemsBeyond Investment PortfoliosOther examples that fit the problem structureDollars to development projectsDollars to public works projectsStaff/personnel to work projectsDollars to media outlets in marketing campaignsCase 3.4: Saving the Manatee16#6: Multi-period Planning ProblemsShow up in many contexts, e.g.production planning (over time) investing (over time)Workforce or demographic planning (over time)Key characteristicsdecisions about multiple time periodssome quantity is “conserved” over time, creating constraints that link different time periodsThis is the classic example used in most textbooks.This is the classic example used in most textbooks.Also useful; Wolverine Retirement Case is great example.Also useful; Wolverine Retirement Case is great example.Mention just to show MPP as a class of pbs,