Erick C. Jones Jr., PhD, PE

IE 5301 Worked Examples

Teaching · IE 5301 Advanced Operations Research · Worked examples

IE 5301 covers the deterministic core of operations research at graduate depth, then adds the stochastic tools. Each section has one idea, a short explanation and something to try; the worked example is folded underneath.

The deterministic core

Interactive on the IE 3315 page:

  1. Simplex, corner to corner
  2. Shadow prices and KKT
  3. A transportation network
  4. Branch and bound
  5. Convexity: Hessians and Sylvester
  6. Nonconvex problems and global solvers

The stochastic three: one fast charger

The setting. A workplace has one EV fast charger, open 12 hours a day. About 3 cars arrive an hour, at random, and a charge takes 15 minutes on average. Sometimes it breaks. Should the site add a second one?

  1. How often is it working? A Markov chain.
  2. How long do drivers wait? A queue.
  3. Is a second charger worth it when demand is uncertain? A decision tree.

1. A Markov chain: how often is it working?

  • Define the states and build the transition matrix
  • Find n-step probabilities
  • Solve for the steady state

The charger is Up or Down each morning, and tomorrow depends only on today. Put the daily chances in a transition matrix PP (rows sum to 1). Multiplying by PP steps a day ahead, and the steady state solves π=πP\pi = \pi P with ∑π=1\sum \pi = 1 (drop one redundant equation).

Try it. Change how often the charger breaks and how fast it gets fixed.

Worked example: breaks 5% of days, fixed half the time
  1. Transition matrix: P=UpDown ⁣ ⁣[0.950.050.500.50]P = \begin{array}{c} \text{Up} \\ \text{Down} \end{array}\!\!\begin{bmatrix} 0.95 & 0.05 \\ 0.50 & 0.50 \end{bmatrix}
  2. Two days after a breakdown: (0.5)(0.95)+(0.5)(0.5)=0.725(0.5)(0.95) + (0.5)(0.5) = 0.725.
  3. Steady state: πU=0.95πU+0.5πD\pi_U = 0.95\pi_U + 0.5\pi_D, so 0.05πU=0.5πD0.05\pi_U = 0.5\pi_D; with πU+πD=1\pi_U + \pi_D = 1, πU=10/11≈0.909\pi_U = 10/11 \approx 0.909
  4. Two independent chargers are both down only (1/11)2≈0.8%(1/11)^2 \approx 0.8\% of days.
UpDown0.05: breaks0.50: repaired0.950.50
The chain as a diagram: each arrow is one entry of P.
02468100.000.250.500.751.00days since it brokeP(up)steady state 10/11 ≈ 0.9090.50 after 1 day0.725 after 2
From a breakdown, the chance of being up settles within about a week.

2. A queue: how long is the wait?

  • Identify the arrival rate λ and service rate μ
  • Find the average number waiting
  • Use Little's law to turn numbers into waiting times

Cars arrive at random at rate λ\lambda and charge at rate μ\mu. Utilization ρ=λ/μ\rho = \lambda/\mu must stay below 1. For one charger (M/M/1), Lq=ρ2/(1−ρ)L_q = \rho^2/(1-\rho) cars wait on average, and Little's law, L=λWL = \lambda W, turns that into time: Wq=Lq/λW_q = L_q/\lambda.

Try it. Push the arrival rate toward the charging rate and watch the wait explode. Press Play to watch a simulated day.

Worked example: 3 cars an hour, 15-minute charges
  1. Rates: λ=3\lambda = 3, μ=4\mu = 4, ρ=0.75\rho = 0.75.
  2. State probabilities: the queue is a Markov chain too, so pn=(1−ρ)ρnp_n = (1-\rho)\rho^n: idle p0=25%p_0 = 25\% of the time.
  3. Average number: L=ρ/(1−ρ)=3L = \rho/(1-\rho) = 3, Lq=ρ2/(1−ρ)=2.25L_q = \rho^2/(1-\rho) = 2.25.
  4. Little's law: W=3/3=1W = 3/3 = 1 hour, Wq=2.25/3=0.75W_q = 2.25/3 = 0.75 hours: 45 minutes.
  5. At 3.5 cars an hour the wait is 105 minutes; a second charger (M/M/2) cuts it to about 3.6.
01234…λ = 3μ = 4λ = 3μ = 4λ = 3μ = 4λ = 3μ = 4
The queue as a chain: up at rate λ, down at rate μ.
0.000.250.500.751.0004080120160utilization ρ = λ/μaverage wait in line (minutes)λ = 2: 15 minλ = 3: 45 minλ = 3.5: 105 minρ = 1: no steady state
Wait against utilization: the last few points cost the most.

3. A decision tree: add a second charger?

  • Draw a tree of decisions (squares) and chance events (circles)
  • Fold back the tree to find the best decision by expected value
  • Find the expected value of perfect information

Value each ending, then fold the tree back: average at each circle (expected value), and take the best branch at each square. Here each ending's value comes from the first two tools: revenue times availability, minus the cost of waiting, minus the second charger's cost.

Try it. How sure do you have to be that demand will grow before a second charger pays?

Worked example: a 40% chance of high demand

Low demand is 2 cars an hour (probability 0.6), high is 3.5 (0.4). A charge earns $8, a waiting hour costs $10, a second charger $150 a day.

Option, demandRevenueWaiting costValue a day
One charger, low$174.55$60.00$114.55
One charger, high$305.45$735.00−$429.55
Two chargers, low$190.41$4.00$36.41
Two chargers, high$333.22$24.86$158.37
  1. Fold back: one charger 0.6(114.55)+0.4(−429.55)=−103.090.6(114.55) + 0.4(-429.55) = -103.09; two 0.6(36.41)+0.4(158.37)=85.200.6(36.41) + 0.4(158.37) = 85.20.
  2. Decide: add the second charger, EV $85.20 a day
  3. EVPI: 0.6(114.55)+0.4(158.37)−85.20=46.880.6(114.55) + 0.4(158.37) - 85.20 = 46.88 dollars a day. The options tie at about a 12% chance of high demand.
decidekeep one chargeradd a second ($150/day)EV −$103.09EV $85.20low demand, 0.6high demand, 0.4low demand, 0.6high demand, 0.4$114.55 a day−$429.55 a day$36.41 a day$158.37 a day
The tree folded back.

Revenue is 12λ×$8×A12\lambda \times \$8 \times A with availability AA = 0.909 (one) or 0.992 (two); waiting is 12Lq×$1012 L_q \times \$10. Breakdowns scale revenue, but the queue is computed as if the chargers never break; a simulation would combine the two.

More worked material: basics of Markov chains, the basics of simulation and the quadratic programming examples, in Python.

← IE 5301 Advanced Operations Research