LINEAR PROGRAMMING for Optimal Shipping

1、LINEAR PROGRAMMING for Optimal ShippingLINEAR PROGRAMMINGfor Optimal ShippingMathematical Modeling Tool Used for Complex Problem Solving and Optimization of Limited Resources2005/4/11OPERMGT-3451Well be discussing problem solving using Linear Programming Modelswithin Microsoft Excel spreadsheets thr

2、ough several examples and a hands-on exercise.1Agenda?Introduction?Creating LP Models?Fertile-Earth Example?Spreadsheet Guidelines?Spud-Man Exercise?LP Model Summary?Reading/Reference List2005/4/11OPERMGT-3452Introduction: A brief review of several of the underlying reasons, tools, and techniques th

3、at support the development and use of LP Models.Creating LP Models: A look at different approaches of LP Models and the steps involved in their creation.Fertile-Earth Example: This is an optimization of a simple blending problem first shown Graphical and then developed in a MS-Excel Spreadsheet.Spre

4、adsheet Guidelines: Building LP Model spreadsheets is more art than science. Well discuss some effective design guidelines. Spud-Man Exercise: This will be your chance to optimize a given shipping problem. Dont worry, well provide you with one the way of implementing a solution to the problem.LP Mod

5、el Summary: Wrap up of mathematical modeling using Linear Programming and how you can use it in your organization. Reading/Reference List: Other sources of information and reading. 2Introduction ?Problem Solving?Mathematical Models?Linear Programming?LP Model Applications2005/4/11OPERMGT-3453Problem

6、 Solving: Effective modeling requires understanding how modeling fits into a problem solving process.Mathematical Models: What are these and how are they described.Linear Programming: Sounds intimidating, but its just a type of mathematical model. Well define it and break it out into its components.

7、LP Model Applications: What can you use LP Models for? 3Problem Solving DefineFormulateAnalyzeImplementTest ResultsProblemModelModelSolutionUnsatisfactory Results2005/4/11OPERMGT-3454Define Problem: This is the most important step, as all the work that followsdepends on the correct definition of the

8、 problem to be modeled. A well-defined statement of the problem is the end result.Formulate Model: Create and “solve”the appropriate model using a spreadsheet. Spreadsheet models lend themselves to organizing the data in a way that is necessary for solving complex problems and the many changes invol

9、ved in the iterative nature of the optimization. Analyze Model: Generate and evaluate the alternatives that may lead to the bestsolution to the defined problem. Is the model a good representation of the environment of the problem? Test Results: Test the feasibility and the quality of the results pro

10、duced by the model verifying the solution against known results and simple common sense. If results are unsatisfactory, update, re-implement, and reanalyze the model. Implement Solution: This is not as easy as it may seem because most people are resistant to change. Good interpersonal skills are nee

11、ded now, and throughout the project in order to have a successful implementation. Early participation, continual buy in, and a shared sense of ownership during all phases of the project go a long way to ensure success. 4Mathematical Models?Definition A functional relationship, like the simple model

12、of PROFIT = ?(REVENUE EXPENSES)?CategoriesPrescriptive, Predictive, and DescriptiveLinear Programming is a prescriptive technique because it prescribes actions that should be taken 2005/4/11OPERMGT-3455Definition: Usually describe functional relationships like: PROFIT = ?(REVENUE EXPENSES). Categori

13、es: Mathematical models can be categorized as follows: Prescriptive: Suggests to the decision maker to take certain actions. Linear Programming (LP) and Critical Path Method (CPM) are some techniques.Predictive: Forecasting a dependent variable based on specific independentvariable values. Regressio

14、n and Time Series Analysis are some techniques.Descriptive: Describing outcomes of systems. Project Evaluation and ReviewTechnique (PERT) and Economic Order Quantity (EOQ) are some techniques.5Linear Programming?Definition A model of linear relationships representing an objective within specific res

15、ource constraints?ElementsDecision Variables, Constraints, Objective Function?MethodsGraphical or Spreadsheet 2005/4/11OPERMGT-3456Definition:A common LP problem is to determine how much product to produce to maximize profit subject to resource constraints such as labor and materials. The components

16、 that make up the problem are expressed as mathematical linear relationships that together form a model.Elements:Decision Variablesare mathematical symbols representing levels of activity.Constraintsare linear relationships representing decision making restrictions.Objective Functionis a linear rela

17、tionship reflecting a specific objective.Methods:Graphicalmethod of solving LP problems is valid but generally cumbersomeand sometimes misleading. Spreadsheetsare the preferred method of solving LP problems for businesses.Today, LP solvers are built into spreadsheet packages in a way that makes them

18、 easy to construct and use. 6LP Model Applications?OptimizationThe name of the game?ApplicationsProduct MixLogisticsManufacturingOthers2005/4/11OPERMGT-3457Optimization: Linear programming models find the most efficient ways of using limited resources to achieve an objective. In this way, the techni

19、que is referred to as “Optimization”. Applications:Product Mixis how much of each product to produce to maximize profit.Logisticsis determining the least costly method/route of shipping product.Manufacturingis the optimizing of a manufacturing process or technique (i.e.minimizing the distance a dril

20、l must move in a repetitive drilling process consisting of thousands of holes that are to be drilled on a circuit board). Othersconsists of a variety of ways to use LP Models that include: Financial, Forecasting, Marketing, Engineering, Scheduling, Capacity Utilization, etc. 7Creating LP Models?Unde

21、rstand the Problem?Identify the Decision Variables?State the Objective Function?State the Constraints?Identify Decision Variable Bounds2005/4/11OPERMGT-3458Understand the Problem: As stated earlier in problem solving, this also is the most important step in creating an LP Model. If you do not fully

22、understand the problem, it is unlikely that your model of the problem will be correct.Identify the Decision Variables: What are the fundamental decisions to be made in order to solve the problem? The answers to this questions will often help you identify appropriate decision variable for your model.

23、State the Objective Function: This function expresses the mathematical relationship between the decision variables to be maximized/minimized. State the Constraints: There are usually some limitations on the values that can be assumed by the decision variables in an LP Model. These restrictions must

24、be identified and stated in the form of constraints.Identify Decision Variable Bounds: Often simple upper or lower bounds apply to decision variables. You can think of these as additional constraints.8Fertile-Earth ExampleDefining the Problem?Fertile-Earth wants to know how much of each of their fer

25、tilizer products it needs to produce and sell in order to make the most profit. 2005/4/11OPERMGT-3459This is the introduction to the problem. Fertile-Earth is a fertilizer producer that wants to maximize its profits by mixing and selling it two products in an optimal way.9Fertile-Earth ExampleDefini

26、ng the Problem?Fertilizer productsGiant-Grow (GG) and Super-Start (SS)?Net contributionGG nets $18.50/ton and SS nets $20.00/ton?IngredientsNitrogen (N) 1100 Tons, Phosphorous (P) 1800 TonsPotassium (K) 2000 Tons?Product recipeGG: 5(N), 5(P), 10(K) and SS: 5(N), 10(P), 5(K)2005/4/11OPERMGT-34510Here

27、 are the elements needed to define the problem.Fertilizer products: Decision Variables, products GG and SS.Net contribution: Objective Function based on cost per ton of products.Ingredients: Constraints, how much of each mineral.Product recipe: Linear Relationship, percent of ingredient in each prod

28、uct. 10Fertile-Earth ExampleDefining the Problem?Maximize:(18.50)GG + (20.00)SS?Subject to:N: (0.05)GG + (0.05)SS <= 1100P: (0.05)GG + (0.10)SS <= 1800K: (0.10)GG + (0.05)SS <= 20002005/4/11OPERMGT-34511What are we trying to do, expressed algebraically. 11Fertile-Earth ExampleFormulating th

29、e Model?Graphical MethodSS(000s)“Feasible” area40N: (0.05)GG + (0.05)SS <= 110030P: (0.05)GG + (0.10)SS <= 180020K: (0.10)GG + (0.05)SS <= 2000100GG (000s)0 10 20 30 402005/4/11OPERMGT-34512Here we have plotted each linear relationship to arrive at a “feasible”solution area on the graph.12F

30、ertile-Earth ExampleFormulating the Model?Graphical Method SS(000s)40Its reasonable to expect that the highest profit will be at one of these 30corner points: a,b,8c,d,e20bc10da0eGG (000s)0 10 20 30 402005/4/11OPERMGT-34513Of the “feasible”solution area, there are several reasonable points that coul

31、d indicate the highest profit within the set constraints.13Fertile-Earth ExampleFormulating the Model?Graphical MethodSSProfit = 18.5GG + 20.00SS(000s)40The graph suggests that “c” is the highest profit 30point of the feasible area.$360,00020$428,000bc10$413,000$0d$370,000a0eGG (000s)0 10 20 30 4020

32、05/4/11OPERMGT-34514After doing the math, we see that point “c”is the point where the highest profit is achieved within the existing constraints.14Fertile-Earth ExampleFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34515Now to build a Linear Programming Model in a spreadsheet for thesame p

33、roblem we just resolved graphically. We are using Microsofts Excel with the solver “add-in”.Notice that we have organized the data in a way that is easy t-i understand in context to the problem. Decision Variables and Decision Bounds are together. Constraints and Linear Relationships are together. T

34、ake some time and review the formulas in the various cells. Ifyou they are not familiar with them, you will need to bone-up on them by referring to the HELP feature of MS-Excel. Be sure you understand the “SUMPRODUCT”function, as it is most critical to spreadsheet LP Modeling. 15Fertile-Earth Exampl

35、eFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34516After the spreadsheet LP model has been set up, you need to invoke the “solver”in MS-Excel to get a solution to the problem.16Fertile-Earth ExampleFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34517There are several parameters

36、 that the solver needs to be supplied with. In addition, the solver needs to know if you are maximizing or minimizing to a solution What cell is the Objective Function located in?. 17Fertile-Earth ExampleFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34518What cell(s) are the Decision Vari

37、able located in?18Fertile-Earth ExampleFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34519What cell(s) are the Constraints located in?19Fertile-Earth ExampleFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34520Generally, you should keep to the default settings when just starting.

38、 Once youve gotten the hang of LP Modeling in spreadsheets, you may want to experiment with the various options.20Fertile-Earth ExampleFormulating the Model?Spreadsheet Method2005/4/11OPERMGT-34521Here is the “solved”LP Model. Notice that the Objective Function is the same as the highest profit poin

39、t in the graphical solution (it should be). 21Spreadsheet Guidelines?Organize the Data?Dont Imbed Constants?Group Related Items?Be Able to Copy Formulas2005/4/11OPERMGT-34522Now we need to take some time and discuss guidelines for effective design of spreadsheet LP Models. Organize the Data: First o

40、rganize the data, then build the model around the data. Once the data is arranged, logical locations for the Decision Variables, Constraints, and Objective Function tend to naturally suggest themselves.Dont Imbed Constants: Numeric constants should be placed in separate cells and labeled appropriate

41、ly. Group Related Items: Things that are logically related should be arranged in close proximity to one another. This enhances functionality andreadability. Be Able to Copy Formulas: Design the model so that formulas can be copied. Once you understand one cells formula, you would then understand a s

42、eries of similar cells and would be able to then just copy the formula tothem.22Spreadsheet Guidelines?Put Totals Close to Sum Fields?Organize Left-Right, Top-Bottom?Use Distinguishable Formatting?Document Model Elements2005/4/11OPERMGT-34523Put Totals Close to Sum Fields: Column or row totals shoul

43、d be in close proximity to the column or rows being totaled.Organize Left-Right, Top-Bottom: English reading people scan from left to right, top to bottom. This fact should be reflected in your spreadsheet design.Use Distinguishable Formatting: Use color, shading, borders, and protection to distingu

44、ish changeable parameters from other elements of the model.Document Model Elements: Use text boxes and cell comments to document various elements of the model.23Spud-Man ExerciseDefining the Problem?Spud-Man is a local trucking company specializing in hauling potatoes from local fields to collection

45、 points in Buhl, Gooding, and Rupert Idaho. Currently, they have three clients: Mr. Doe, Mr. Jones, and Mr. Smith.?Spud-Man wants to know how many pounds of potatoes to truck from each clients field to each citys collection point in order to minimize to total number of miles the spuds must be shippe

46、d.?The mileage saved translates into fuel savings, labor time savings, savings on vehicle wear and tear, etc. 2005/4/11OPERMGT-34524Now, we have an exercise we would like you to try. Please read the problem carefully, define the problem, formulate a spreadsheet LP Model,and solve for the Objective F

47、unction.We have provided you with our model formulation and solution if you get stuck and need some guidance or want to compare your work against ours. 24Spud-Man ExerciseDefining the Problem?Mr. Does field has 275,000 lbs of potatoes Mr. Jonesfield has 400,000 lbs of potatoes Mr. Smiths field has 3

48、00,000 lbs of potatoes.?Buhl collection point can handle 200,000 lbs Gooding collection point can handle 600,000 lbs Rupert collection point can handle 225,000 lbs.?Distance between fields and collection points:BuhlGoodingRupertMr. Doe215040Mr. Jones353022Mr. Smith5520252005/4/11OPERMGT-34525Remember, there are Decision Variables, Constraints, an