GYAAN KOSH
TERM 2
Decision Models and Optimization
This document covers the basic concepts of Decision Models and
Optimization covered in Term 2. The document only summarizes
the main concepts and is not intended to be an instructive
material on the subject.
Also note that since this is a Quantitative Subject, only concepts
that you might need to know for tackling an interview are included
here along with some sample problems. For details of solving
problems, please refer to the detailed notes.
Gyaan Kosh Term 2 DMOP
CONTENTS
1. The Optimization Tree and Taxonomy of Decision Models
2. Linear Programming
i. Basic LP Assumptions
ii. Gaining Insights through LP Model
iii. What does it mean to spot patterns in an LP solution
iv. LP Geometry Basics
v. LP States
vi. Sensitivity Analysis – Shadow Price and Reduced Costs
3. Introduction to Network Models
4. Modeling Business Logic
5. Newsvendor problem
6. Decision Trees
7. Monty Hall Problem
8. Random Variables
9. EMV and EVPI
Gyaan Kosh Term 2 DMOP
Basic LP Assumptions
Proportionality:
Contribution from a decision variable is proportional to the decision variable.
Additivity:
Contribution to objective from one decision variable is independent of another decision variable
Divisibility:
Each variable is allowed to assume fractional values.
Data certainty:
Coefficients are not random variables.
Gaining Insights through LP Model
The optimal solution tells a story about a pattern of economic priorities, and it’s the recognition of
these priorities that provides insight.
When we know the pattern, we can explain the solution more convincingly than when we simply read
the algorithm’s output.
When we know the pattern, we can also anticipate some of the answers to “what if” questions. In
short, the pattern provides a level of understanding that enhances decision making.
What does it mean to spot patterns in an LP Solution
Spotting a pattern involves observations about both variables and constraints. In the optimal solution we
should ask ourselves, which constraints are binding and which are not? Which variables are positive and
which are zero?
Grasping the pattern of binding constraints and positive variables allows us to reconstruct the solution
in a sequential fashion.
This allows us an opportunity to discern an economic imperative at the heart of the situation
depicted in the model.
Gyaan Kosh Term 2 DMOP
LP Geometry Basics
The number of decision variables determines the problem space’s dimensionality
Two-variable problems can be plotted on a 2-D graph
Pick an axis for each variable
The constraints define the set of feasible solutions
Each inequality defines a feasible half-plane
The problem’s feasible region is the intersection of the half-planes
To draw a constraint: calculate the two intercepts; draw a line between them
An optimal solution can always be found at a vertex (corner point)
Pick an arbitrary objective function and draw “test” iso-profit line using intercepts
Find the improving direction for the objective function, locate candidate optimal vertices
Calculate the solution corresponding to each candidate vertex by solving the
simultaneous equations of the vertex’s binding constraints
Compare the objective function value by plugging solution coordinates into the objective function
Example of Graphical Representation of a LP
LP States
1. An LP can be in one of these three states – Unbounded, Infeasible, Bounded
feasible with an optimal solution (at least one corner-point solution)
Gyaan Kosh Term 2 DMOP
2. An LP can have many optimal solutions
3. An LP can have redundant constraints
This happens when a constraint can be expressed as a linear combination of other constraints
4. An LP can have a degenerate vertex
When one or more “basic” variables are zero at a particular vertex
Think of an “over-defined” vertex (though degeneracy cannot always be depicted
graphically) A 2-D LP never has a degenerate vertex.
Sensitivity Analysis – Shadow Price and Reduced Costs
Shadow prices and validity range
Relaxing the right-hand side (RHS) of a binding constraint improves the optimal objective function value
Relaxing the constraint enlarges the feasible region
As the optimal vertex moves, its objective function value improves
The marginal improvement in the objective function value caused by relaxing the RHS one unit is called
the constraint’s shadow price
Shadow prices are also called dual variables.
Computing the validity-range of a shadow price
The shadow price is valid when the RHS changes within an interval, if all other data remains the same
(one change at a time.)
In 2 dimensions, this means that the shadow price is valid when the RHS is in an interval in which the
same “corner point” solution remains.
In multiple dimensions, it means that the shadow price is valid when the RHS changes so long as the
optimal “basic” variables remain optimal.
Perturbing the objective function
The optimal solution remains unchanged as long as the objective function lies between the slopes of the
constraints.
Gyaan Kosh Term 2 DMOP
A large enough change in an objective function coefficient can cause the optimal solution to change
A change in one coefficient causes the objective function to “rotate”.
With a sufficiently large change, the objective function becomes parallel to one of the binding constraints,
creating multiple optimal solutions
If the coefficient continues to change, the optimal solution “jumps” to an adjoining vertex
The amount a coefficient can increase or decrease before the optimal vertex changes is called
the coefficient’s allowable increase / decrease
The reduced cost of a variable
The reduced cost associated with the non-negativity constraint for each variable is the shadow price of that
constraint, i.e., the corresponding change in the objective function per unit increase in the lower bound of
the variable
The reduced cost for all decision variables can be directly computed from the shadow prices on the
“structural” constraints and the objective coefficient
In this view, the shadow prices are thought of as the opportunity costs associated with diverting resources
away from the optimal production mix.
Computing the reduced cost
The operation of computing the reduced cost from shadow prices is called pricing-out. If yi is the shadow
price of the ith constraint (there are m constraints), cj is the objective coefficient of the jth activity, and aij is
the amount of the ith resource consumed by the jth activity, then the reduced cost for the jth activity is
computed as
Quick Summary
Shadow price of a constraint
Defines the price you are willing to pay to relax the RHS by one unit, or the price you must be
paid to tighten the RHS by one unit.
Gyaan Kosh Term 2 DMOP
Non-binding constraints have 0 shadow price; i.e. either the constraint has a slack (surplus)with
zero shadow price or the shadow price is non-zero and the constraint is tight. Reduced Cost of a
decision variable
Indicates how much more attractive (i.e., higher in profit or lower in cost) its coefficient in the objective
function must be before this variable is worth using.
Ignore the sign. Sign conventions differ across different LP solvers; just remember that the
objective coefficient must be made more attractive by this magnitude.
Unless the problem is degenerate “basic” variables are positive and their reduced costs are 0.
Gyaan Kosh Term 2 DMOP
Network Terminologies
Application Areas
Gyaan Kosh Term 2 DMOP
Sample Transportation Problem and Its LP Formulation
LP Formulation
Gyaan Kosh Term 2 DMOP
Modeling Business Logic
Why Integer Programming
Advantages of restricting variables to take on integer values:
1. More realistic (economic indivisibilities)
2. More flexibility (use of binary variables, logical constraints)
Disadvantages
1. More difficult to model
2. Can be much more difficult to solve
Binary Integer Variables
Binary variables can take values of 0 or 1; This is also equivalent to 0 ≤ Xj ≤ 1 Binary
variable are very useful in modeling several business situations:
1. Logical constraints (e.g., if-then-else, go-no/go decisions)
2. Application areas include supply-chain optimization models (transportation, facility location),
financial models (budget models), and many more
Types of Integer Programming
All integer programs have linear equalities and inequalities and some or all of the variables are required to be
integer
If all variables are required to be integer, then it is usually called a pure integer program
If all variables are required to be 0 or 1, it is called a binary integer program, or a 0-1 integer Program
If some variables can be fractional and others are required to be integers, it is called a mixed linear
integer program (MILP)
Gyaan Kosh Term 2 DMOP
Examples of Application: Fixed Charge Problems
Modeling the Fixed Charge Problem:
Modeling the discrete choice of keeping a facility open:
Gyaan Kosh Term 2 DMOP
The Constraints:
Demand Side Constraints:
Supply Side Constraints:
Gyaan Kosh Term 2 DMOP
The Newspaper Vendor Problem
The newsvendor sells newspapers:
Buys them for $0.25 each
Sells them for $0.50 each
Returns unsold papers for $0.10 each
Has to place the order, q, for papers the night before. Next day’s demand, D, is uncertain.
Demand estimate is based on past data is Approximated by N(98,312)
How many papers to order?
System Mechanics
Monty Hall Problem
Assume that a room is equipped with three doors. Behind two are goats, and behind the third is a shiny new car. You
are asked to pick a door, and will win whatever is behind it. Let's say you pick door 1. Before the door is opened,
however, someone who knows what's behind the doors (Monty Hall) opens one of the other two doors, revealing a goat,
and asks you if you wish to change your selection to the third door (i.e., the door which neither you picked nor he
opened). The Monty Hall problem is deciding whether you do.
Random Variable
A random variable (r.v.) is a “rule” that assigns a numerical value to each possible outcome of a probabilistic
experiment. Typically, we denote it using a capital letter (say “X”) In other words, a random variable involves
a probability model where all of the outcomes are numbers (real-valued).
Discrete Random Variable: Binomial, Poisson
Continuous Random Variable: Uniform, Normal
Decision Trees
A decision tree is a systematic way of organizing and representing the various decisions and uncertainties that
a decision maker faces. Important Charecteristics:
1. Time Flows from Left to Right
2. Placement of Decision and Chance nodes logically consistent with the ways events play out
3. Branches represent possible outcomes and corresponding probabilities
4. Each Final Node has a numerical outcome associated with it
EMV (Expected Monetary Value)
For an event node, compute its EMV by computing the weighted average of all possible numerical
outcomes with the probabilities of each of the possible outcomes used as the weights
For a decision node, compute its EMV as the EMV of the best alternative. Cross off the inferior branches by
drawing a double line through them.
The EMV of the optimal decision strategy is the EMV computed for the starting node of the tree
EVPI (EMV with Perfect Information)
The decision with perfect information/hindsight, that is, after observing whether the transformer fails or not
Eg: Consider a situation where we must decide whether or not to insure an expensive transformer before
placing it into a very hazardous work environment. If the uninsured
transformer fails, then it costs us $1M. On the other hand, we can purchase insurance which costs $0.5M, but
will provide us with a new transformer at no additional cost if
our transformer fails. We believe that there’s a 60% chance that our transformer will fail. What should we do?
Should we purchase insurance or not?