OPIM101 Decision Analysis or Management Science PDF

Preview

Summary

Summary of the book and the entire course...

Description

1- Introduction to Modeling & Decision Analysis Wednesday, 2 July 2014

23:50

Introduction - Computer Model: set of mathematical relationships and logical assumptions implemented in a computer representing real world d ecision problem or phenomenon ○ Spreadsheet Model: computer model implemented via a spreadsheet - Management Science: field of study using computers, statistics, and mathematics to solve business problems ○ Application of scientific method to managerial and personal decision-making - Potential applications ○ Finance — portfolio analysis, securities pricing, risk management ○ Marketing — distribution channels, pricing, merchandizing, forecasting ▪ Different means of advertising (mix) ▪ Contractual agreements (minimum number of ads) ○ Production — production decisions, workforce assignment ○ Logistics — vehicle routing, capacity allocation, supplier selection ○ Telecom — network design, call routing ○ Manufacturing — production planning, plant location Modeling Approach to Decision Making - Mental modeling, visual modeling, physical/scale models, mathematical model - Model: abstract representation of an existing problem ○ Realistic, solvable, and understandable mathematical statement showing relationships among variables - Variables in a model ○ Decision variables → controllable ○ Parameters → uncontrollable EOQ Assumptions - Known and constant demand - Known and constant lead time - Delivery in one batch - No quantity discounts - No shortages/stock-outs allowed - Only order/setup cost and holding cost

Pros of Mathematical Modelling - Simplified versions of object or decision problem ○ Valid Model: accurately represents relevant characteristics of object or decision problem - Saves time and money and can be the only way to solve large/complex problems - Frequently helpful in examining things that would be impossible to do in reality - Allow us to gain insight and understanding about object or decision problem under investigation ○ Reduces uncertainty surrounding business plans and actions Cons of Mathematical Modelling - May be expensive and time-consuming to develop and test - Often misused and misunderstood due to their complexity - Often make oversimplifying assumptions - Tend to downplay value of qualitative information Categories of Mathematical Models

- Prescriptive Models: solutions tell decision maker what actions to take - Predictive Models: f(•) might be unknown and must be estimated to predict Y - Descriptive Models: where decision problem has a very precise, well -defined functional relationship f(•) between independent variables and dependent variable ○ Might be great uncertainty as to exact values assumed by independent variables ▪ Hence, objective is to describe outcome or behaviour of given operation or system ○ Likely to encounter in business world Problem-Solving Process

- Formulate model → mental/visual/scale/mathematical depending on nature of problem Anchoring & Framing Effects - Anchoring and framing causes errors in human judgment ○ Anchoring effects arise when a seemingly trivial factor serves as a starting point for estimations in a decision-making problem

Management Science Page 1

▪ Adjustments from anchor are too close (under-adjusted) ○ Framing effects refer to how decision maker views alternatives in a decision problem — often involving win/loss perspective

▪ Alternative A is consistent and should be chosen

Management Science Page 2

2- Introduction to Optimization & Linear Programming Sunday, 6 July 2014

17:15

Introduction - Mathematical Programming: field of MS that finds the optimal, or more efficient, way of using limited resources (minimise costs or maximise profits) ○ Referred to as "optimization"

Applications of Mathematical Optimization - Determining product mix: how many products to produce to maximise profits or satisfy demand at minimum cost - Manufacturing: efficiency determine drilling order to minimize total distance drill must move - Routing and logistics: transferring merchandise and determining amounts required at each store - Financial planning withdrawing money while minimizing taxes payable Characteristics of Optimization Problems - Each problem involves one or more decisions to be made - Constraints (restrictions) are likely to be placed on alternatives available to decision maker - Existence of a goal or objective decision maker considers when deciding which course of action is best Expressing Optimization Problems Mathematically - Decisions ○ Decision variables: X1, X2, … , Xn - Constraints ○ f(X1, X2, … , Xn) ≤ b ○ f(X1, X2, … , Xn) ≥ b ○ f(X1, X2, … , Xn) = b - Objective ○ MAX (or MIN): f(X1, X2, … , Xn) ○ Objective function identifies some function of decision variables that decision maker either MAXimize or MINimize ▪ MAX (or MIN): f0(X1, X2, … , Xn) ▪ Subject to: □ f1(X1, X2, … , Xn) ≤ b1 □ … □ fk(X1, X2, … , Xn) ≤ bk □ … □ fm(X1, X2, … , Xn) ≤ bm Linear Programming: involves creating and solving optimization problems with linear objective functions and linear constraints - If a solution exists, LP always finds the optimal solution - Objective: maximize or minimize a quantity - Output: recommended course of action from list of possible alternatives - Assumptions ○ Linearity (all relationships are expressed in linear equations) ▪ Proportionality → change in one is always accompanied by a change in the other ▪ Additivity ○ Certainty → parameters and relationships are known ○ Divisibility → fractional solutions are possible ○ Non-negativity Formulating LP Models 1. Define decision variables 2. State objective function as a linear combination of decision variables 3. State constraints as linear combinations of decision variables 4. Identify any upper or lower bounds on decision variables General Form of an LP Model - MAX (or MIN): c1X1 + c2X2 + … + cnXn - Subject to: ○ a11X1 + a12X2 + … + a1nXn ≤ b1 … ○ ak1X1 + ak2X2 + … + aknXn ≤ bk … ○ am1X1 + am2X2 + … + amnXn ≤ bm - Objective function coefficients: c 1, c2, … , cn ○ Might represent marginal profits (or costs) associated with decision variables X1, X2, … , Xn respectively - Numeric/technological coefficients: a…

Solving LP Problems: A Graphical Approach - Plot constraints and identify feasible region → by plotting boundary lines of constraints and identifying point that satisfy all constraints - MAX: 350X1 + 300X2 - Subject to: ○ 1X1 + 1X2 ≤ 200 ○ 9X1 + 6X2 ≤ 1566 ○ 12X1 + 16X2 ≤ 2880 ○ 1X1, 1X2 ≥0 X1 + X2 = 200 Plotting 2nd constraint 9X1 + 6X2 = 1566 - Plotting 1st constraint

Management Science Page 3

- Plotting 3rd constraint

- Plotting objective function ○ To determine which point in feasible region will maximize value of objective function ○ An optimal solution with finite objective function value will always occur at point in feasible region where two or more boundary lines of constraints intersect ▪ Known as Corner/Extreme points of feasible region → calculate profit for each corner → highest profit is optimal solution

- Finding optimal solution using level curves ○ Level curves: lines representing objective function values (as they represent different levels or values of objective)

○ ○ ○ ○ ○

Largest possible level curve intersects feasible region at a single point (optimal feasible solution) X1 + X2 = 200 9X1 + 6X2 = 1566 9X1 + 6(200 - X1) = 1566 X1 = 122, X2 = 78

Management Science Page 4

- Corner point with largest objective function value is the optimal solution to the problem - Summary 1. Plot boundary line of each constraint in the model 2. Identify feasible region 3. Locate optimal solution by one of the following methods: i. ISO-PROFIT/COST LINE → Plot one or more level curves for objective function and determine direction in which parallel shifts in this line product improved objective function values; shift level curve in parallel manner in improving direction till it intersects feasible region at single point; coordinates at this point is the optimal solution ii. Identify coordinates of all extreme points of feasible region and calculate objective function values associated with each point □ If feasible region is bounded, point with best objective function value is optimal solution

- Pros ○ Easy to understand ○ Provides insights in structure of LP solutions - Cons ○ Only possible for problems with 2 variables - If changes occur in any coefficients in objective function or constraints then level curve, feasible region, and optimal solution also might change Special Conditions in LP Models (Anomalies: alternate optimal solutions, redundant constraints; Problems: unbounded solutions, infeasibility) - Alternate optimal solutions

○ Where objective changes (MAX/MIN) but none of the constraints changed (hence feasible region is still the same) - Redundant constraints

○ Constraint that plays no role in determining the feasible region of the problem ▪ Usually with non-negativity constraints present - Unbounded solutions

Management Science Page 5

○ Objective function made infinitely large (for MAX) and infinitely small (for MIN) ▪ Feasible region AND optimal solution not bounded ▪ However, optimal solution can be bounded while feasible region is unbounded ○ Indicates something wrong with formulation - Infeasibility

○ No way to satisfy all constraints in problem simultaneously → no feasible region ○ May occur due to error in formulation ▪ Eliminate or loosen constraints to obtain feasible area □ Loosening: increasing upper limits (or reducing lower limits) to expand range of feasible solutions

Management Science Page 6

3- Modeling & Solving LP Problems in a Spreadsheet Monday, 7 July 2014

13:24

Simplex Method - Efficient algorithm to solve LP problems - Inspects corners of feasible region systematically and iteratively - Provides sensitivity analysis output - Able to recognize infeasibility and unboundedness Steps in Implementing an LP Model in a Spreadsheet - Organize data for model on spreadsheet 1. Coefficients in objective function 2. Various coefficients in constraints 3. Right-hand-side values for constraints - Reserve separate cells in spreadsheet to represent each decision variable in algebraic model - Create a formula in a cell in the spreadsheet that corresponds to objective function in algebraic model - For each constraint, create a formula in a separate cell in the spreadsheet that corresponds to LHS of the constraint

A Spreadsheet Model for the Blue Ridge Hot Tubs Problem - Organizing data

- Representing decision variables

- Representing objective function

- Representing constraints

- Representing bounds on decision variables ○ Solver allows us to specify simple upper and lower bounds for decision variables by referring directly to cells representing decision variables

How Solver Views the Model 1. Set (or target) cell: represents objective function 2. Variable (or changing) cells: represent decision variables

Management Science Page 7

3. Constraint cells: represent LHS formulas of constraints (and any upper/lower bounds that apply to these formulas)

Using Solver - Define set/target cell, variable cells, constraint cells, non-negativity conditions, review model, options, solve model Goals & Guidelines for Spreadsheet Design - Communication: clear and intuitive - Reliability: output should be correct and consistent - Auditability: easy to retrace steps to generate different outputs from model - Modifiability: easy to change or enhance model

Management Science Page 8

4- Sensitivity Analysis & the Simplex Method Tuesday, 8 July 2014

11:25

Purpose of Sensitivity Analysis - Increases insight and confidence in optimal solution ○ Challenges assumption of certainty ○ Checks robustness of optimal solution - Consider LP model's solution's sensitivity to changes or estimation errors that may occur in: 1. Objective function coefficients 2. Constraint coefficients (changes frequently and are never fixed) 3. RHS values for constraints Approaches to Sensitivity Analysis - Trial-and-error ○ Iteratively solve the LP problem with different parameters and compare solutions - (Excel) Sensitivity report ○ Preferred method that does not require resolving the problem ○ But limited to one change at a time - Simplex method provides information about: ○ Range of values objective function coefficients can assume without changing optimal solution ○ Impact on optimal objective function value of increases/decreases in availability of various constrained resources ○ Impact on optimal objective function value of forcing changes in values of certain decision variables away from their optimal values ○ Impact on optimal solution by changes in constraint coefficients Answer Report - Binding/active constraint: satisfied as a strict equality in the optimal solution (no slack; all used) ○ Otherwise nonbinding/inactive ○ Act as a cap (MAX/MIN) - Slack values for non-negativity conditions indicate amounts by which decision variables exceed respective lower bounds of zero Sensitivity Report 1. Changes in objective function coefficients ○ Only way to change level curve for objective function is by changing its coefficients ○ Change slope of iso-profit line ▪ Change total profit ▪ May change optimal solution

○ Final value → optimal product mix ○ Allowable increase/decrease: increase/decrease in objective coefficient such that final value does not change, assuming all other coefficients remain constant ○ Reduced cost: how much objective coefficient needs to be "improved" in order for corresponding decision variable to become non-zero ▪ Positive final value → reduced cost = zero ▪ Zero final value → reduced cost indicates change in objective function if final value of that cell is increased by one unit (optimality check) ▪ Minimization problem → "improved" means reduced ▪ Maximization problem → "improved" means increased - Alternate optimal solutions exist where allowable increase/decrease equals zero ○ To get solver to produce optimal solutions (if they exist): 1. Add a constraint that holds objective function at current optimal value 2. Then attempt to maximize/minimize value of each decision variables that had an objective function coefficient with an allowable increase/decrease of zero 2. Changes in RHS values (resource availability/constraints) ○ May change feasible region ○ May change optimal solution and total profit

○ Shadow price: increase/decrease in objective function value for a unit increase/decrease in the constraint RHS (all others remaining constant) ▪ Applies ONLY if increase/decrease in RHS value falls in the allowable increase/decrease limits ▪ Active/binding constraint → +ve shadow price ▪ Inactive constraint → 0 shadow price ▪ Changes to RHS value may lead to a new optimal solution □ However, shadow prices do not tell you which values the decision variables need to assume to achieve the new objective function value - Shadow prices and value of additional resources ○ Where increases to RHS value leads to an improved objective function value, how much are we willing to pay to acquire those i ncreases? ▪ Change in Profit due to change in RHS value is the maximum we are willing to pay - Shadow prices show profitability if new decision variables are introduced ○ May change optimal solution and total profit ○ Total Profitability = New Profit - Reduction in Profits (due to reduction of resources for original decision variables) ○ Only estimate change of one parameter at a time → other values must be 0 - Reduced cost (marginal profit - marginal value of resources it consumes)

Management Science Page 9

○ Current solution will remain profitable provided that marginal profit of Typhoon-Lagoons ≤ 320 + 13.33 ▪ Otherwise Typhoon-Lagoons is profitable and optimal solution will change

-

-

-

○ Shadow prices (marginal values) of resources = marginal profits, at optimality, assume values between simple lower and upper bounds ▪ In optimal solution to LP, variables that assume values between their simple lower and upper bounds always have reduced cost values of 0 ○ Generally, at optimality, a variable assumes its largest possible value (or = simple upper bound) if it helps improve objective function value ▪ Maximization problem → variable's postive reduced cost → if variable's value increased, objective value would increase (improve) ▪ Minimization problem → variable's negative reduced cost → if variable's value increased, objective value would decrease (improve) ○ At optimality, a variable assumes its smallest possible value (or = simple lower bound) if it cannot be used to improve objective value ▪ Maximization problem → variable's negative reduced cost → if variable's value increased, objective value would decrease (worsen) ▪ Minimization problem → variable's postive reduced cost → if variable's value increased, objective value would increase (worsen) Analysing changes in constraint coefficients ○ 320 - 200 x 1 - 16.67L - 0 x 13 ≥ 0 (profitable) → L = 7.2 Simultaneous changes in objective function coefficients ○ 100% Rule determines if the current solution remains optimal when more than one objective function coefficient changes; situations that arise when applying rule 1. All variables whose objective function coefficients change have nonzero reduced costs □ Current solution remains optimal provided that objective function coefficient of each changed variable remains within allowable increase/decrease range 2. At least one variable whose objective function coefficient changes has a reduced cost of 0 Warning about degeneracy ○ Degeneracy: mathematical anomaly in solution to LP problem ▪ Occurs if RHS values of any constraints have an allowable increase/decrease of 0 ○ When a solution is degenerate: ▪ Methods mentioned earlier for detecting alternate optimal solutions are inapplicable ▪ Reduced costs for variable cells may not be unique □ Also, objective function coefficients for variable cells must change by at least as much as their respective reduced costs before optimal solution would change ▪ Allowable increases/decreases for objective function coefficients still hold and might have to be changed substantially beyond allowable increase/decrease limits before optimal solution changes ▪ Given shadow prices and their ranges still might be interpreted in the usual way but they might not be unique □ Meaning that a different set of shadow prices and ranges also might apply to the problem (even if optimal solution is unique) Limitations of sensitivity report ○ Only one parameter at a time ○ Only within allowable range

Limits Report - Values in lower limits column indicate the smallest value each variable cell can assume (other values constant; all constraints satisfied) - Values in upper limits column indicate the largest value each variable cell can assume (other values constant; all constraints satisfied)

Sensitivity Assistant Add-in (Optional) - Creating spider tables and plots

Management Science Page 10

- Creating a solver table

Simplex Method (Optional) - Creating equality constraints using slack variables ○ Solver temporarily turns all inequality constraints into quality constraints by adding one new variable to each ≤ constraint and substrating one from each ≥ constraint ▪ New variables are called slack variables ▪ Ak1X1 + Ak2X2 + … + AknXn ≤ bk -> Ak1X1 + Ak2X2 + … + AknXn + Sk = bk ▪ Ak1X1 + Ak2X2 + … + AknXn ≥ bk -> Ak1X1 + Ak2X2 + … + AknXn - Sk = bk ▪ MAX: 350X1 + 300X2 ▪ Subject to: ▪ 1X1 + 1X2 ≤ 200 ≤ 1566 ▪ 9X1 + 6X2 ▪ 12X1 + 16X2 ≤ 2880 ▪ X 1 , X 2 , S1 , S 2 , S3 ≥ 0  Where X1, X2 are known as structural variables - Basic feasible solutions ○ If there are a total of n variables in a system of m equations, to find a solution: ▪ Select any m variables and try to find values of them that solve the system, assuming all other vari...