Theory questions Flashcards
In a Markov chain, one state in a class is transient. Prove that every state in the class is transient.
[4m]
- Say T is the transient state; let x be any other state in the same class
- Let P be a path of transition arcs from x to T & let Q be a path of transition arcs from T to a state Z, which cannot reach T
- There must also be no path from Z to x (or else we can continue along P to T, contradicting the unreachability of T from Z)
- So, there is a path from x to Z and no path back, implying that x is transient
EOQ inventory model with SHORTFALL {shortages allowed}
Write down an expression for the total ordering cost per order cycle. Justify each term in this expression very briefly.
[3m]
- The immediate ordering cost is K + cQ
- Stock is POSITIVE for time S/d, NEGATIVE for (Q-S)/d
- Over the positive-stock duration S/d, on AVERAGE there are __ items on hand, at a COST h per unit, for TOTAL HOLDING COST __
- Over the negative-stock duration (Q-S)/d, on AVERAGE there is __ shortfall at a COST p per unit time, for TOTAL SHORTFALL COST __
- The total order cost per cycle is ___
EOQ inventory model with NO shortfalls allowed
Write the total cost per time, and derive the optimal order quantity Q*.
[3m]
- Take S=Q, so p is irrelevant
- The total order cost per cycle is __
- Divide by the CYCLE TIME {CYCLE LENGTH} Q/d…
- …giving the total order cost per time
- Differentiate with respect to Q to get __
- Optimality occurs when derivative = 0, so we get Q* = ___
For a queueing model with Poisson arrivals, exponential service times, and a single server, use the principle of balance to derive the stationary probabilities.
[4m]
- For any state i, the system must be EQUALLY LIKELY to make transitions from states i and below to to states i+1 and above; otherwise it would not be STATIONARY
- The only such transitions are those from i to i+1, which happen at rate piλ and…
- …from i+1 to i, which happen at rate p_i+1μ
- They must be EQUAL, hence giving p_i+1 = piρ where ρ=λ/μ
- Then, pi = p0ρ^i
- The sum of all pi is p0(1/1-ρ) = 1
- So, p0 = 1-ρ and pi = ρ^i(1-ρ)
Describe an example where y is dual optimal but x is not optimal.
[2m]
There are many possibilities.
eg. with an LP in canonical form, y is an optimal dual solution, while x = 0 is a feasible solution but not optimal.
Give an example showing that the NECESSARY condition for optimality (one of the dual weights of the defining constraints is 0) is NOT a SUFFICIENT condition.
[4m]
- Consider a 2-dimensional example where one constraint A is parallel to the objective function, and two other constraints B and C intersect it to define two optimal extreme solutions x1 and x2.
- Constraints B and C will get DUAL WEIGHT 0.
- Now, shift those two constraints until they intersect A in the same point, x1 = x2.
- We can still choose either of two sets of defining constraints, but now they define just the one extreme optimum.
Dijkstra’s algorithm is run on a directed graph with positive edge weights, from some source node s. At an intermediate state of the algorithm, the set R of “reached” nodes contains k nodes.
1. What is the key property of this set?
2. Why is that property maintained from this step to the next,
3. and why does it depend on the edge weights being nonnegative?
- R is the set of the k nodes NEAREST to the source s. {have the shortest distance from s}
- Dijkstra adds to R the node z reachable most cheaply at one hop from R, i.e., the node v giving the
minimum in minr∈R,v̸R(d(r) + c(r, z)) - How do we know that z is the node next nearest to s?
- For any node x ∈/ R, consider the SHORTEST PATH P from s to x.
- P starts in R (at s) and ends outside of R (at x).
- Consider the first time P leaves R, going say from u ∈ R to v ∈/ R.
- Because the edge weights are positive, d(s, x) ≥ d(s, v) = minu∈R(d(u) + c(u, v)) ≥ minr∈R,v̸R(d(r) + c(r, z)) = d(z).
Show that any two states in the same class of a Markov chain have the same period.
In a Markov chain, one state A has period p. Another state, x, is in the same class as A. Prove that x has the same period.
[5m]
- We know there is a path from x to A and a path back; suppose they have combined length k.
- Let R be the set of times that A can be revisited; by definition, p is the GCD of R (and 0 ∈ R)
- Then x can be revisited (possibly among other times) at times R + k, including k.
- The period q of x must divide all of these — all elements of R + k — therefore q divides k, therefore q divides every element of R,
- and (since p is the GCD of R), q divides p.
- By the symmetric argument, p divides q. Therefore p = q.
Prove or refute the following claim: Let P be a shortest path from s to t, and let u be an arbitrary vertex between them on the path P. Then the part of P from s to u is a shortest path from s to u.
TRUE
1. Let P’ be the initial part of path P, from s to u, and P’’ be the rest, from u to t
2. If there were a shorter path Q from s to u, then following Q from s to u, then P’’ from u to t would give a shorter way to t,
3. a contradiction since P is meant to be the shortest.
What is the algorithm to find a topological order for the nodes, to find a project management critical path?
- Take as the next node any activity v with no predecessor {and add it to the end of the order}
- Delete v from the network (erasing v from the set of predecessors of any remaining activity)
- Repeat until there are no nodes left
How to prove that a network has no topological order but a cycle (and produce one)?
- Take any remaining node v1 and any of its predecessors v2, then take a predecessor v3 of v2, etc.
- Since there are finitely many nodes, eventually some vj must have a predecessor v_j+1 equal to some earlier node vi
- In this case, vi,vi+1,…,vj,v_j+1 = vi is a cycle of predecessors: each of these nodes DEPENDS on the one AFTER
Prove the easier direction: show that if there is a topological order then there is no directed cycle.
- For the first direction, consider a directed cycle with vertices u1, u2, . . . , uk and arcs (u1,u2),(u2,u3),…,(uk−1,uk),(uk,u1).
- Assume there is a topological ordering, and let ui be the first cycle vertex in this order.
- Then the arc (ui−1, ui) (interpreted as (uk, u1), if i = 1) VIOLATES the topological order, as it goes BACKWARDS with respect to the order.
^basically showing that if there’s a cycle, there is no topological order. hence a topological order means no cycle.
For an inventory model with perishable goods, let cu be the per-unit regret from underordering, and co that from overordering. For a given order level and random demand, there will be a probability pu of having underordered, and po of having overordered.
Argue that the optimal order level balances these costs and probabilities, giving pucu = poco.
[4m]
- At the optimal order level X, the derivative of profit with respect to X should be 0
- Consider a discrete equivalent of that: the profit with ordering X should be about equal to that with ordering X + 1
- Imagine X to be large, so that the case that the +1 moved us from underordering to overordering is negligible
- With probability pu we have underordered, so X + 1 means we’ve underordered by 1 unit less, gaining us cu, for an expected gain of pucu.
- With probability po we have overordered (in both cases), so X +1 means we’ve overordered by 1 unit more, losing us cu, for an expected gain of −poco.
- The total expected gain is pucu − poco, and setting this to 0 gives us the optimal order level.
Dijkstra’s algorithm - Why do we require that all ARC COSTS are NONNEGATIVE? Give an example.
Dijkstra’s algorithm FAILS if there are negative weights, eg.
1. Let A be the starting point and B the target point
2. At initialisation, the algorithm sets R={A}, d(B)=2 and d(C)=3
3. Since d(B)<d(C), B will be added to R in the next iteration
4. B has no out-neighbours, hence no distances d change
5. The algorithm terminates here as B is reached
6. However, the shortest path from A to B is A-C-B, with length 3 + (-2) =1 < d(B)=2
