The longest route from A to Z is AHDCEZ. The longest route from A to H is AH. The longest route A to D is AHD. The longest route from A to C is AHDC. The longest route from A to E is AHDCE. The longest route from H to D is HD. The longest route from H to C is HDC. The longest route from H to E is HDCE. The longest route from D to D to C is DC and the longest route from C to E is CE.
Corresponding results can also be given for the shortest route from A to Z.
This example illustrates a general principle – that the any part of a longest (shortest) path from one node to another in a directed network is itself a longest (shortest) path. This is called Bellman's Optimality Principle. It only applies to vertices on the longest (shortest) route and not between any two vertices.
]]>Example: Given the two player game with payoff matrix (for player A) given below, with strategies highlighted:
B 

A 
Strategy 
1 
2 
3 
1 
3 
3 
1 

2 
1 
4 
1 

3 
5 
2 
4 
First test the game for stability by finding the row maximin and the column minimax. If these are not the same, the game is not stable.
B 
Row Minimum 

A 
Strategy 
1 
2 
3 

1 
3 
3 
1 
3 

2 
1 
4 
1 
4 

3 
5 
2 
4 
5 

Column Maximum 
1 
3 
4 
The row maximin, the maximum value of the row minima, is 3. The column minimax, the minimum value of the column maxima, is 1. Since these are not the same the game is not stable.
To use the simplex algorithm to solve the game we need to make all the entries positive. We can do this by adding 6 to each element in the payoff matrix to give the matrix below.
B 

A 
Strategy 
1 
2 
3 
1 
3 
9 
7 

2 
7 
2 
5 

3 
1 
8 
10 
Letandbe the probabilities of player A choosing strategies 1 , 2 and 3 respectively. Obviously,Letbe the value of the game to player A after 6 has been added to each element of the matrix. Obviously we seek to maximiseThe constraints are given below.
If player B chooses strategy 1,whereis a slack variable.
If player B chooses strategy 2,whereis a slack variable.
If player B chooses strategy 3,where t is a slack variable.
]]>A\B  Clown  Skeleton  Space 
Clown  2  0  4 
Skeleton  0  2  1 
Space  1  4  0 
The table can be interpreted in this way. If both companies make clown costumes, then for every 20 sold, company A will lose two sames to company B. If company A makes clown costumes and B makes space costumes, then for every twenty costumes sold, company A will sell 4 more than company B. Company A can quickly decide not to make space costumes, because it will sell more skeleton costumes whatever company B make, since every entry in row 2 is greater than the corresponding entry in row 3. Hence we can ignore row 3 to give the matrix below. Row 2 is said to dominate row 3.
indicates the following payoff matrix, which shows the sales of each costume by each company:
A\B  Clown  Skeleton  Space 
Clown  2  0  4 
Skeleton  0  2  1 
Similarly company B will decide not to make space costumes, because the loss of sales to company A will be greater if company B makes space costumes than if it makes clown costumes. Hence company B will never make space costumes, and we can eliminate column 3. Column 1 is said to dominate column 3.
A\B  Clown  Skeleton 
Clown  2  0 
Skeleton  0  2 
Now it is easy to see that company A will sell most costumes by only making skeleton costumes, and company B will sell most costumes by only making clown costumes.
The entry in the second row, first column is a saddle point and the value of the game is 0.
Connect house 1 to electricity, gas and water.
Now connect house 2. Any pipe/cable from 1 to any of E, G, W cannot cross a pipe already drawn. Any routes from 2 to E, G and W must divide the plane into two parts A and B below.
The third house must lie in region A, B or C. If it lies in A there is no route to G or W. If it lies in B there is no route to E or G and if it lies in C there is no route to E.
This means that all three houses cannot be connect to gas, water and electricity without at least one crossing.
]]>We can go direct from A to C (distance 9), or A to C via B (distance 4+2=6), or from A to C via E (distance 5+3=8), or from A to C via E and D (distance 5+1+3=9), or from A to C via D (distance 7+3=10). The least of all these distance is 6, using the route A to C via B. Gong the the whole network in this way gives us the least distance matrix below.
A 
B 
C 
D 
E 

A 
 
4 
6 
6 
5 
B 
4 
 
2 
5 
5 
C 
6 
2 
 
3 
3 
D 
6 
5 
3 
 
1 
E 
5 
5 
3 
1 
 
Notice that the only blank spaces are between vertices and themselves.
]]>
A 
B 
C 
Supply 

1 
25 
20 
10 
40 
2 
40 
15 
30 
80 
3 
20 
50 
40 
60 
Demand 
40 
60 
80 
180 
The cost associated with each route from a supply depot to a demand depot are highlighted.
The North West Corner solution is
A 
B 
C 
Supply 

1 
40 
0 
40 

2 
60 
20 
80 

3 
60 
60 

Demand 
40 
60 
80 
180 
The total cost of this solution is C=40*25+0*20+60*15+20*30+60*40=4900
The supply and demand for each depot can also be satisfied by placing the zero is cell 2A instead of 1B, to give a total cost of C=40*25+0*40+60*15+20*30+60*40=4900.
These costs are the same so the solution is degenerate.
Notice that the number of rows isand the number of columns is
There are only 4 non zero cells used in the solution. Since The number of cells used is less than the number of rows plus the number of columns less one, the solution is degenerate.
]]>If John committed the murder, then he was in the victim's apartment and did not leave before 11. John was in the victim's apartment. If he left before 11, then the doorman saw him but it is not the case either that the doorman saw him or that he committed the murder.
Define the statements:
p: John committed the murder.
q: John was in the victim’s apartment.
r: John left before 11.
s: The doorman saw him.
The first sentence becomes (1)
The second sentence becomes q (2)
The third sentence becomes(3)
We construct two truth tables – one for each of (1) and (3)
The first is
1 
0 
1 
0 
0 
1 
1 
1 
1 
1 
1 
0 
1 
0 
0 
0 
0 
1 
1 
0 
0 
0 
1 
0 
0 
1 
1 
0 
0 
1 
0 
1 
1 
1 
1 
0 
0 
1 
0 
0 
0 
1 
0 
1 
0 
0 
1 
0 
The second is

Examination of the tables gives that the statements are consistent ifand
]]>For example, the payoff matrix for player 1 is given in the table below.

Player 2 

Player 1 

1 
2 
3 
1 
5 
2 
8 

2 
2 
5 
7 

3 
8 
3 
8 
Strategy 3 for player 1 dominates strategy 1, since the winnings for player 1 from playing strategy 3 are always at least as great as the winnings from playing strategy 1.
The row corresponding to strategy 1 can be removed to give the table below.

Player 2 

Player 1 

1 
2 
3 
2 
2 
5 
7 

3 
8 
3 
8 
If pl;ayer 1 is less lucky, he is making losses. The table shows the losses for player 1 for each combination of strategies.

Player 2 

Player 1 

1 
2 
3 
1 
5 
1 
7 

2 
2 
0 
7 

3 
0 
3 
8 
The losses for player 1 for strategy 2 are at most equal to the losses for playing strategy 1, so player 1 always plays strategy 2 in preference 1to 1. Strategy 2 is said to dominate strategy 1.
The row corresponding to strategy 1 can be removed to give the table below.

Player 2 

Player 1 

1 
2 
3 
2 
2 
0 
7 

3 
0 
3 
8 
]]>
In the table below C cannot start until A has finished and D cannot start until both A and B have finished.
Activity 
Preceding Activities 
A 
 
B 
 
C 
A 
D 
A, B 
We need to include a dummy to show D cannot start until B has finished. The dummy is shown below.
Sometimes we need two dummies – or even more – at a time, to show how activities depend on each other.
Activity 
Preceding Activities 
A 
 
B 
 
C 
A 
D 
B 
E 
A, B 
Dummies are also needed because of what may seem a technical reason. It is not allowed to have two activities between the same two nodes, as shown below.
This is because although two or more activities may depend on the same preceding activities, the finishing of each activity are separate events, so must end at separate nodes. This is only relevant at the terminal node of an activity network, where some of the last activities depend on the same events.
H and G are the last activities. Without the dummy both activities would link to same two nodes. Notice that the length of the dummy is 0, so it is usual to place the dummy between the activity of least duration – G above – and ther terminal node.
]]>
Months 
January 
February 
March 
April 
May 
Number of Clocks Scheduled for Delivery 
1 
5 
3 
3 
2 
The clocks are delivered at the end of each month. The clockmaker can make up to four clocks a month, but if more than two clocks are made in any month, he has to hire an assistant at £400 per month. Workshop costs are £250 in any month in which clocks are made and the workshop has storage space for two clocks, with each clock costing £50 a month to store. He starts in January with no clocks in stock and aims to finish in May with no clocks in stock.
To solve the problem, draw up the table below.
Stage 
Demand (Number of clocks to be delivered that month) 
Number of clocks in storage at start of month 
Production 
Number of clocks in storage at end of month 
Cost 





We work backwards from the end of the last month, stage 1. There can be 0, 1 or 2 clocks in storage at the start of the month but there must be no clocks in storage at the end. The number of clocks in storage plus the number of clocks produced must equal two, the number of clocks to be delivered at the end of the month.
Stage 
Demand (Number of clocks to be delivered that month) 
Number of clocks in storage at start of month 
Production 
Number of clocks in storage at end of month 
Cost in £ 
1 
2 
0 
2 
0 
250* 


1 
1 
0 
50+250=300* 


2 
0 
0 
2*50=100* 
For the second stage, we include all possible options, as we did for the first stage. We must however, make the stock levels correspond, so that the stock levels at the end of the month for the second stage correspond to the stock levels at the start of the month for the first stage. A * on a cost indicates the lowest cost route backwards to that state of having a certain amount of stock at the start of that month. The total costs for first and second stage are calculated for each possible option.
Stage 
Demand (Number of clocks to be delivered that month) 
Number of clocks in storage at start of month 
Production 
Number of clocks in storage at end of month 
Cost in £ 
1 
2 
0 
2 
0 
250* 


1 
1 
0 
50+250=300* 


2 
0 
0 
2*50=100* 
2 
3 
0 
3 
0 
250+400++250=900* 


0 
4 
1 
250+400+300=950 


1 
2 
0 
50+250+250=550* 


1 
3 
1 
50+250+400+300=1000 


1 
4 
2 
50+250+400+100=800 


2 
1 
0 
2*50+250+250=600* 


2 
2 
1 
2*50+250+300=650 


2 
3 
2 
2*50+400+100=600 
3 
3 
0 
3 
0 
250+400+900=1550 


0 
4 
1 
250+400+550=1200* 


1 
2 
0 
50+250+900=1200* 


1 
3 
1 
50+250+400+550=1250 


1 
4 
2 
50+250+400+600=1300 


2 
1 
0 
2*50+250+900=1250 


2 
2 
1 
2*50+250+550=900* 


2 
3 
2 
2*50+250+400+600=1350 
4 
5 
1 
4 
0 
50+250+400+1200=1900* 


2 
3 
0 
2*50+250+400+1200=1950 


2 
4 
1 
2*50+250+400+900=1650* 
5 
1 
0 
1 
0 
Not feasible since there must be at least one clock in stock at the end of the month to satisfy demand in February 


0 
2 
1 
250+1900=2150 


0 
3 
2 
250+400+1650=2300 
The least cost option is to produce two clocks in January, four clocks in February, four clocks in March, two clocks in April and two clocks in May.
]]>