# OR-Notes

## J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

#### Markov processes tutorial solution

Here we have a Markov process with three states (oil, gas and electric).

To calculate the long-run situation let [x1,x2,x3] represent the long-run system state, then we have

[x1,x2,x3] = [x1,x2,x3](P) where x1 + x2 + x3 = 1

Hence we have the four equations

x1 = 0.825x1 + 0.060x2 + 0.049x3
x2 = 0.175x1 + 0.919x2
x3 = 0.021x2 + 0.951x3
x1 + x2 + x3 = 1

or

```0.175x1 - 0.060x2 - 0.049x3 = 0  (1)
0.175x1 - 0.081x2 = 0            (2)
-0.021x2 + 0.049x3 = 0           (3)
x1 + x2 + x3 = 1                 (4) ```

To solve these four simultaneous linear equations we have that from equation (2)

`x2 = (0.175/0.081)x1      (5) `

and from (3) and (5)

`x3 = (0.021/0.049)x2 `
`= (0.021/0.049)(0.175/0.081)x1   (6) `

Substituting (5) and (6) into (4) we get

x1[1 + (0.175/0.081) + (0.021/0.049)(0.175/0.081)] = 1

i.e. x1 = 0.2447

From (5) we get x2 = 0.5287 and from (6) we get x3 = 0.2266.

Hence in the long-run oil will have 24.47% of the market, gas 52.89% of the market and electric 22.66% of the market.

Note here that it is often worth substituting the values you have found back into the original equations as a numerical check on your results.

With the revised transition matrix we are still seeking the long-run system state and we proceed as above but with the new transition matrix.

Note here that as the long-run system state is independent of the initial state there is no need to calculate the state of the system in two years time (when the new transition matrix comes into effect). Hence we have

[x1,x2,x3] = [x1,x2,x3](P)

where x1 + x2 + x3 = 1

This gives the four equations

x1 = 0.93x1 + 0.07x2 + 0.09x3
x2 = 0.07x1 + 0.91x2 + 0.02x3
x3 = 0.02x2 + 0.89x3
x1 + x2 + x3 = 1

or

```0.07x1 - 0.07x2 - 0.09x3 = 0    (1)
-0.07x1 + 0.09x2 - 0.02x3 = 0   (2)
0.11x3 - 0.02x2 = 0             (3)
x1 + x2 + x3 = 1                (4) ```

From (4) we have that x1=1-x2- x3 and so substituting for x1 in (1) we get

0.07(1-x2-x3) - 0.07x2 - 0.09x3 = 0

`i.e. 0.14x2 + 0.16x3 = 0.07    (5) `

Now from (3) we have that x3 = (0.02/0.11)x2 and substituting for x3 in (5) we get

0.14x2 + 0.16(0.02/0.11)x2 = 0.07

or x2[0.14 + 0.16(0.02/0.11)] = 0.07

i.e. x2 = 0.4140

Hence from (5) we get

0.14(0.4140) + 0.16x3 = 0.07

or x3 = 0.0753

and from (4) we have

x1 + 0.4140 + 0.0753 = 1

i.e. x1 = 0.5107

Hence with this new transition matrix the long-run system state is that oil will have 51.07% of the market, gas 41.40% of the market and electric 7.53% of the market.

To work out the state of the system in three years time (i.e. in year 4) we have that the initial state s1 is given by s1 = [0.26, 0.6, 0.14].

Hence the state of the system in year 2 is given by s2 = s1P = [0.257, 0.597, 0.146]

Here we have (arbitrarily) chosen to round to three decimal places and note that, as required, the elements of s2 sum to one.

In year 3 the state of the system is given by s3 = s2P = [0.255, 0.594, 0.151]

In year 4 the state of the system is given by s4 = s3P where P is now the revised transition matrix = [0.292, 0.561, 0.146]

Note here that as we have rounded figures to three decimal places the elements of s4 only add to 0.999 and not to one. Errors of this kind (inevitably) sometimes occur.

Hence in three years time the market share for oil will be 29.2%, for gas 56.1% and for electric 14.6%.